Legacy Concept Lab

Theoretical Foundations: PAC Learning, MDL & Information Bottleneck

PAC/VC theory gives language and bounds for generalization and sample complexity

Concept 17 of 100TheoryPhase 8

#17TheoryTheory

key equation

\max_{p(z\mid x)} I(Z;Y) - \beta I(Z;X)

Phase 8: Scaling, theory & multimodalConcept 17 of 100

Why It Matters for Modern Models

PAC/VC theory gives language and bounds for generalization and sample complexity
MDL/compression perspectives underlie "good models should be simple and predictive"
Info-bottleneck motivates representation compression and what middle layers do

What Tutorials Skip

What is still poorly explained in textbooks and papers:

How to connect formal sample-complexity bounds to actual overparameterized models that interpolate
Intuitive, visual examples of MDL in deep nets (comparing code lengths of different architectures)

Interactive Visualization

Core Math (Optional Deep Dive)

If you want intuition first, start with the key equation and the visualization. Come back here for the full walkthrough.

Key Equation

\max_{p(z\mid x)} I(Z;Y) - \beta I(Z;X)

PAC learning: concept class $\mathcal C$ is PAC-learnable if algorithm uses $n = O\left(\frac{1}{\epsilon}\big(d \log \tfrac{1}{\epsilon} + \log\tfrac{1}{\delta}\big)\right)$ examples to output hypothesis with error ≤ $\epsilon$ with probability ≥ $1-\delta$ , where $d$ is VC dimension.