Concept 17 of 100Learning TheoryTheory · Study phase 8: Scaling, theory & multimodal
Question
How can sample-complexity bounds be connected to overparameterized networks that fit their training data exactly, where classical VC bounds are vacuous?
How to study this pagePredict · Check · Generalize · Continue
PredictSay what you expect.
Before you move a control in the demo, say what you expect to change.
CheckCheck against the math and the papers.
Compare what the demo shows with the key equation and with the papers cited below.
GeneralizeName what stays the same.
Identify the part of the idea that survives a change of notation or model, so you can recognize it in another paper or system.
ContinueFollow the connections.
Use the prerequisites and related concepts at the end of the page to fill the next gap.
Why It Matters for Modern Models
PAC and VC theory give precise definitions and bounds for generalization and sample complexity.
MDL makes "prefer the simplest model that predicts well" precise: the best hypothesis is the one that gives the shortest total code for model plus data.
The information-bottleneck view proposes that deep networks first fit their training data and then compress their representations (Shwartz-Ziv & Tishby, 2017); whether this compression phase happens in general, and whether it explains generalization, is disputed (Saxe et al., 2018).
Questions to Think About
What would MDL look like for deep networks, for example when comparing the code lengths that different architectures give the same data?
Interactive Demo
Core Math
If you prefer intuition first, try the demo above, then come back for the math.
Key Equation
p(z∣x)maxI(Z;Y)−βI(Z;X)
PAC learning (Valiant, 1984): an algorithm PAC-learns a concept class C if, for every target concept in C, every data distribution and every ϵ,δ>0, it outputs with probability at least 1−δ a hypothesis with error at most ϵ, using a number of examples polynomial in 1/ϵ and 1/δ. For binary classification in the realizable case, a class of VC dimension d is learnable by empirical risk minimization with
MDL (Rissanen, 1978): choose the hypothesis H that minimizes the total description length L(D,H)=L(H)+L(D∣H) of the model plus the data encoded with it.
Information bottleneck (Tishby et al., 1999): learn a representation Z of the input X that keeps information about the target Y while compressing X:
Bias-variance puzzle: where Learning Theory breaks down, taken up in Double Descent. Open Double Descent
Classical bias-variance reasoning says that test error rises once a model is complex enough to fit the noise in its training data. Double descent adds a second fall: past the point where the model fits the training data exactly, larger models generalize better again (Belkin et al., 2019). Explaining this needed new theory, such as benign overfitting (Bartlett et al., 2020).
Where else does the same idea appear?
Human-aware utility: the same technique appears in KTO. Open KTO
KTO takes the shape of its loss from Kahneman and Tversky's prospect theory: outcomes are judged relative to a reference point, and losses weigh more than equal gains (Ethayarajh et al., 2024). It is an example of a training loss designed around a model of human judgment.
The negative log-likelihood −log₂ p_θ(x) is the length in bits of x under the code built from the model p_θ, so maximizing likelihood minimizes the length of the encoded data. MDL adds the length of the description of the model itself, which is what penalizes complex models.
Tokens ↔ Codelength: Tokenization is its mathematical dual. Open Tokenization
A tokenizer is a codebook: vocab size and token counts jointly define a compression scheme. MDL provides the "dual" way to reason about why changing vocab changes sequence length, capacity, and generalization behavior.
Bottleneck viewpoint: Embeddings is its mathematical dual. Open Embeddings
Representation learning is often "keep what matters, drop what doesn't." The information bottleneck formalizes that as maximizing I(Z;Y) while penalizing I(Z;X)—a dual language for the same design tradeoff.
Flatness ↔ Complexity: Sharpness is its mathematical dual. Open Sharpness
Flat minima correspond to larger volumes of parameter space that implement similar functions, which often aligns with lower effective complexity in PAC-Bayes and MDL-style arguments. The link is debated: sharpness can be changed by reparameterizing a network without changing the function it computes (Dinh et al., 2017).