Venue: A-PIC 2025 — African Summer School on Probability, Information and Computing, in Kigali, Rwanda [link] Dates: November 24–28, 2025 Instructor: Jonathan Shafer (MIT)

Abstract

Humans, animals, and, increasingly—machines—all learn from experience. But what, precisely, does “learning” mean? Just as physics seeks to uncover the laws that govern the physical world, and to express those laws in a mathematical language—learning theory seeks to uncover the mathematical laws that govern systems that learn (be they biological or otherwise).

This course is an introduction to learning theory. We will present a few definitions of learning, and then proceed to investigate what can (and cannot) be learned according to each definition, and what amount of computational resources (such as data and compute) are necessary in the cases where learning is possible. Attention will be devoted to understanding definitions and proofs.

Lecture Notes Scribed by Maren Dück

Part I: Online Learning

| 1 | November 24 | Realizable case — definition |H|-1 mistake upper bound Halving algorithm — log(|H|) mistake upper bound Littlestone dimension — definition and examples | Notes | | --- | --- | --- | --- | | 2 | November 25 | Littlestone dimension — further examples The Littlestone Theorem Standard Optimal Algorithm (SOA) Non-realizable / Agnostic case — definition Low regret — definition Weighted Majority algorithm (WM) Linear regret lower bound Randomized Agnostic case — definition | Notes | | 3 | November 26 | Randomized Weighted Majority algorithm (RWM) Littlestone theorem for randomized agnostic case | Notes |

Part II: Statistical Learning

| 4 | November 27 | PAC Learning — definition No Free Lunch Theorem | Notes | | --- | --- | --- | --- | | 5 | November 28 | Sample complexity of PAC learning finite classes VC dimension Examples of VC dimension Growth function Sauer Lemma The Fundamental Theorem — VC upper bound | TBA |

Suggested Reading — Online Learning

• Click to Open

Suggested Reading — Statistical Learning

• Click to Open

Bibliography

• Jonathan’s UC Berkeley lecture notes: “Computational Learning Theory” (CS 294-220) [link].
  • Includes links to lecture recordings.
• Shalev-Shwartz, Shai, and Shai Ben-David. Understanding Machine Learning: From Theory to Algorithms. Cambridge University Press, 2014. [link]
• Mohri, Mehryar, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of machine learning. MIT Press, 2018. [link]
• Karlin, Anna R., and Yuval Peres. Game Theory, Alive. American Mathematical Society, 2017. [link]