Foundation 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

Open Demo All Foundations

#17TheoryTheory

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

Selected Foundation Object

Keep the equation fixed; move through the evidence.

Concept 17 of 100TheoryTheory / Phase 8: Scaling, theory & multimodal

Current question

How to connect formal sample-complexity bounds to actual overparameterized models that interpolate

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

PredictionCommit before the demo.

Ask what should change when the equation is manipulated, then let the visualization test that expectation.

EvidenceCompare local witness and source.

Use the runnable panel, the key equation, and canonical papers as separate forms of evidence for the same object.

InvariantName what survives notation changes.

The useful learning product is the reusable mechanism you can carry into another model, paper, or engineering tradeoff.

Next moveContinue through the atlas.

Use prerequisites, dependents, and semantic links to repair the next gap without leaving the object behind.

Open demo Inspect equation Browse atlas Next foundation

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.