Formal Learning Theory Kernel: Blueprint v1
1
Introduction
▶
Scope
Relationship to the companion textbook
How to read this document
2
Primitives
▶
2.1
Atomic vocabulary
2.2
The concept class
2.3
Batch learner
2.4
Sample, loss, and error
3
PAC Learning and the Fundamental Theorem
▼
3.1
The PAC Framework
3.2
The VC Characterization
▶
3.2.1
Stage 1: Sauer–Shelah (Statement)
3.2.2
Stage 2: Uniform Convergence
3.2.3
Stage 3: Uniform Convergence Implies ERM Succeeds
3.2.4
Stage 4: Infinite VC Dimension Implies Failure
3.3
The Fundamental Theorem of Statistical Learning
▶
3.3.1
The Proof Architecture
3.3.2
The Compression Direction (Sketch)
3.4
The Agnostic Setting and the \(\varepsilon ^2\) Price
3.5
Lower Bounds and the No-Free-Lunch Theorem
▼
3.5.1
The PAC Lower Bound
3.5.2
The No-Free-Lunch Theorem (Full Proof)
3.6
Computational Interlude
3.7
What This Chapter Established
▶
Exercises
4
Online Learning and the Littlestone Dimension
▶
4.1
The Online Learning Game
4.2
Mistake Trees and the Littlestone Dimension
4.3
The Standard Optimal Algorithm
4.4
The Lower Bound: The Adversary Strategy
4.5
Regret Bounds and the Multiplicative Weights Framework
4.6
The PAC–Online Gap
4.7
What This Chapter Established
5
Identification in the Limit
▶
5.1
Gold’s Question
5.2
Ex-Learning and Gold’s Impossibility Theorem
5.3
The Identification Hierarchy
▶
5.3.1
Finite Identification
5.3.2
Behaviorally Correct Learning
5.4
Relaxations of Identification
▶
5.4.1
Anomalous Learning
5.4.2
Monotonic Learning
5.4.3
Vacillatory Learning
5.4.4
Trial and Error
5.5
Mind-Change Complexity
5.6
Three Paradigms, Incomparable
5.7
What This Chapter Established
▶
Exercises
6
What Does Not Imply What
▶
6.1
The Separation Lattice
6.2
Separations Between Paradigms
6.3
Strict Strength Hierarchy
6.4
What the Negative Layer Reveals
7
The Measurability Layer
▶
7.1
Borel parameterization and the symmetrization route
7.2
The analytic measurability bridge
7.3
The Borel-analytic separation theorem
8
Closing Notes and Forward Pointers
A
Key Lean 4 Declarations
▶
A.1
Core types
A.2
Combinatorial dimensions
A.3
Learnability predicates
A.4
The fundamental theorem (5-way equivalence)
A.5
Characterization theorems
A.6
Paradigm separations
A.7
Measurability layer (kernel’s novel contribution)
B
Bibliography
3.5 Lower Bounds and the No-Free-Lunch Theorem