Explore the fundamentals of learning theory and incentives in this comprehensive lecture from the Learning and Games Boot Camp. Delve into the concept of learnability in the presence of strategic and adversarial behavior, drawing insights from a decade of research. Examine stochastic (offline) and online learning settings, understanding their formal setups and real-world applications. Investigate the role of VC dimension in characterizing learnability, and discover why it may not be sufficient in online scenarios. Analyze the Littlestone dimension and its importance in online learning algorithms. Gain valuable knowledge on solution concepts and their applications in modern machine learning challenges.
Overview
Syllabus
Intro
Learning and Learnability One of the goals of theory of ML
Learnability for Today's World
Learnability Q1. What concepts can be learned in presence of strategic and adversarial behavior? → Lessons for todays world from decade of efforts for understanding
Tutorial Overview
Stochastic (Offline) Settings Usage Example: Learning to detect natural phenomenon or fixed distribution objects, eg, trees, animals, etc.
Formal Setup: Stochastic setting
Alternative Setup: (Stochastic) Offline Learning
What characterizes offline learnability?
VC Dimension Example
Why VC Dimension?
Stochastic (Offline) Settings Usage Examples Controlling the content quality, face adversarial manipulation of future instances and have to updated
Formal Setup: Online vs Stochastic Setting
Characterizing Online Learnability Role of VC dimension - Finite VC dimension is not sufficient, because of thresholds on a line. • VC dimension focuses on labeling a set . But we need to consider labelings of sequences.
Characterization of Online Learnability
Algorithms based on Littlestone Dimension
Solution Concepts
Taught by
Simons Institute
