Home
›
Blog
›
AGI Researcher Foundations — Generalization & Learning Theory
AGI Researcher Foundations · Article 5 of 11
📊
Generalization & Learning Theory: Why Models Work on Data They've Never Seen
Article 4 ended with a genuine puzzle — deep double descent, where classical statistics gets the wrong answer about model complexity. This article gives that puzzle a name and a history: PAC learning, VC dimension, the bias-variance tradeoff, and the specific, well-documented ways modern deep learning breaks the classical story — with real papers, a working self-assessment, and honest acknowledgment of what's still unsolved.
FL
FrontierAGI Team
September 14, 2026 · 70 min read
The Question Underneath Every Training Run
Every article in this series so far has assumed something without stating it outright: that a model trained on one set of examples will do something useful on examples it has never seen. That assumption has a name — generalization — and a whole field of mathematics, learning theory, dedicated to asking exactly when and why it's justified. This article covers what a working researcher actually needs from that field: not the full proofs, but the concepts, the historical classical story, and — more interestingly — the specific, well-documented ways deep learning breaks that classical story, which Article 4 already previewed via deep double descent without fully explaining.
As with Article 3's math scoping, this article draws a line: classical statistical learning theory (PAC learning, VC dimension) gives you the right vocabulary and intuitions, even though its precise numerical predictions frequently fail for modern deep networks — knowing both the classical theory and exactly where it breaks is more useful than either alone.
1984
Year Valiant's PAC learning framework formalized what "learning from examples" even means mathematically
2017
Year Zhang et al. showed deep networks can perfectly memorize random labels, yet still generalize on real data
2019
Year "Deep Double Descent" (Article 4) formally documented test error falling, rising, then falling again with model size
2
Competing explanations for why overparameterized models generalize — neither fully settled as of 2026
Part 1 — The Classical Story
PAC Learning and VC Dimension: What "Learnable" Used to Mean
Before deep learning, learning theory had a fairly clean, mathematically rigorous story about when a model can be trusted to generalize.
1PAC learning ("Probably Approximately Correct") — Leslie Valiant's
1984 framework formalizes what it means for an algorithm to "learn" a concept from examples: given enough examples, the learned model should be
approximately correct with
high probability — not perfect, not certain, but bounded and quantifiable. This is the mathematical foundation underneath every claim in this article about "how many examples are enough."
2VC dimension (Vapnik & Chervonenkis) — a way of measuring a model class's capacity: roughly, the largest number of points the model class can perfectly separate in every possible arrangement. Classical theory says higher VC dimension (more capacity) requires more training data to generalize reliably, and predicts that a model with capacity far exceeding its training data size should overfit badly.
3Generalization bounds — formulas (built on VC dimension or related measures like Rademacher complexity, Bartlett & Mendelson, 2002) that give a mathematical upper bound on the gap between training performance and true, real-world performance, as a function of model capacity and dataset size.
This classical picture is elegant, and it's also — as Part 3 covers directly — a poor numerical predictor for modern deep networks, which routinely have far more parameters than training examples yet still generalize well. That gap is this article's central subject, not a footnote to skip past.
Part 2 — The Bias-Variance Tradeoff
The Classical Tradeoff Everyone Learns First
Geman, Bienenstock & Doursat's 1992 paper on the "bias-variance dilemma" formalized the tradeoff every introductory ML course teaches: a model with too little capacity has high bias (it's systematically wrong — too simple to capture the real pattern); a model with too much capacity has high variance (it fits training-set noise, and performs wildly differently depending on exactly which training examples it happened to see). The classical prescription: find the "sweet spot" in the middle, since total error is bias plus variance, and both can't be minimized simultaneously by capacity alone.
| Model Regime | Bias | Variance | Classical Prediction |
|---|
| Too simple (underfit) | High | Low | Poor performance everywhere — model can't capture the pattern |
| "Just right" capacity | Moderate | Moderate | Best generalization — the classical sweet spot |
| Too complex (overfit) | Low | High | Great training performance, poor test performance |
| Far beyond training-data size (modern deep nets) | Low | Classically predicted "very high" | Classical theory predicts disaster — Part 3 shows this frequently doesn't happen |
Every ML course teaches the bias-variance U-curve as if it's the whole story. It's the right story for the classical regime — and modern deep learning routinely operates well past where that U-curve predicts things should go wrong.
Part 3 — Where Deep Learning Breaks the Classical Story
The Puzzle: Networks That Should Overfit, and Don't
This is the part of learning theory a working AI researcher actually needs to know cold, because it's directly, practically relevant to every model discussed elsewhere on this site.
1Zhang et al.'s "rethinking generalization" result (2017) —
arXiv:1611.03530. This is the single most important paper in this article: the authors show that standard deep networks can achieve near-perfect training accuracy on a dataset with
completely random labels — meaning the network has enough raw capacity (VC dimension, in the classical sense) to memorize pure noise. Classical theory would predict such a high-capacity model should therefore generalize terribly on real, correctly-labeled data. In practice, the same architectures generalize well on real data. Classical capacity measures alone cannot explain this gap.
2Overparameterization is the norm, not the exception — modern LLMs (referenced throughout this series) routinely have far more parameters than there are unique training examples, in direct violation of the classical "capacity should roughly match data size" intuition from Part 2, yet they generalize usefully rather than catastrophically overfitting.
3Two competing explanations, neither fully settled — one line of work (implicit regularization) argues that gradient descent itself, as an optimization procedure, has a built-in bias toward simpler, smoother solutions among the many that fit the training data equally well, so the network never actually "chooses" the wild, poorly-generalizing solutions classical theory worries about. A second line of work (the Neural Tangent Kernel, Jacot, Gabriel & Hongler, 2018,
arXiv:1806.07572) shows that in a certain mathematical limit, very wide networks behave like a much simpler, classically well-understood model (kernel regression) during training — offering one path to a new, non-classical generalization theory, though it's debated how well this limit describes realistic, finite-width networks actually used in practice.
Part 4 — Double Descent, Formalized
Revisiting Article 4's Puzzle With the Right Vocabulary
Article 4 introduced Nakkiran et al.'s "Deep Double Descent" (2019) as a strange empirical result. With Parts 1–3 of this article in hand, it can now be stated precisely: classical bias-variance theory predicts test error should rise monotonically once model capacity exceeds the "sweet spot" (Part 2's table). Double descent shows test error can rise and then fall again as capacity keeps increasing past the point where the model can exactly fit ("interpolate") its training data — a second, non-classical regime the classical U-curve has no vocabulary for at all. A companion result, Belkin et al.'s 2019 PNAS paper, frames this explicitly as "reconciling" modern practice with classical theory — the title itself is an admission that the two didn't fit together cleanly before this work.
Being direct about the state of the field: as of September 2026, there is no single, universally accepted theory that fully explains double descent and overparameterized generalization together — the NTK framework and implicit-regularization arguments each explain part of the picture, in certain regimes, but a complete, practically predictive theory (one that could, say, tell you in advance exactly how large to make a specific model) does not yet exist. This is presented as an open problem because it is one, not because this article is being falsely modest.
Part 5 — Papers & Courses
Key Papers to Read First
| Paper | Why It's Foundational | Link |
|---|
| Valiant — "A Theory of the Learnable" (1984) | Founds PAC learning, the formal vocabulary for "learning from examples" | PDF |
| Geman, Bienenstock & Doursat — "Neural Networks and the Bias/Variance Dilemma" (1992) | Formalizes the classical tradeoff every ML course starts from | IEEE Xplore |
| Zhang et al. — "Understanding Deep Learning Requires Rethinking Generalization" (2017) | Shows classical capacity measures can't explain deep networks' generalization behavior | arXiv:1611.03530 |
| Jacot, Gabriel & Hongler — "Neural Tangent Kernel" (2018) | One leading candidate explanation for overparameterized generalization | arXiv:1806.07572 |
| Belkin et al. — "Reconciling Modern Machine Learning Practice and the Classical Bias-Variance Trade-off" (2019) | Directly names and frames the classical-vs-modern gap this article covers | arXiv:1812.11118 |
| Nakkiran et al. — "Deep Double Descent" (2019, previously cited in Article 4) | The empirical phenomenon this entire article builds toward explaining | arXiv:1912.02292 |
Courses to Complete
Part 6 — Real Scenarios
Real Scenario Walkthroughs
🎲Scenario A — Running Zhang et al.'s Random-Label Experiment Yourself
A genuinely eye-opening exercise for a newcomer: take one of Article 2's reproduction projects (a small image classifier), randomly shuffle the training labels so they're pure noise, and train the same architecture on it. Watching the network achieve high training accuracy on labels that are, by construction, meaningless is the fastest way to viscerally understand why Zhang et al.'s 2017 result mattered — the network clearly has the raw capacity to memorize anything, which immediately raises the question this article spends Part 3 on: so why doesn't it just memorize noise when the labels are real and meaningful?
The lesson: capacity to memorize and tendency to generalize are not the same property, and classical theory conflates them in a way that doesn't survive contact with this experiment.
📈Scenario B — Reading a Paper's Learning Curve Like a Skeptic
Applying "How to Read a Paper Like a Researcher"'s framework directly: when a paper reports a model's train-vs-validation loss curve, check specifically whether the model size is in the classical "sweet spot" regime (Part 2) or the overparameterized regime where double descent (Part 4) can produce misleadingly reassuring-looking curves — a validation loss that looks stable can behave differently than classical intuition predicts, depending on which side of the interpolation threshold the model sits.
The lesson: "the validation loss looks fine" means something different in the overparameterized regime than it did in the classical courses that first taught you to read a learning curve.
Self-Assessment Checklist
1Can you explain, in plain language, what "PAC" stands for and why "probably" and "approximately" are both doing real work in that name, not just hedging?
2Can you draw the classical bias-variance U-curve from memory, and explain why it predicts overfitting for high-capacity models?
3Can you explain why Zhang et al.'s random-label result is a genuine problem for classical learning theory, not just a curious side note?
4Do you know the difference between the "classical regime" and the "overparameterized regime" in the double-descent picture, and which one most modern LLMs operate in?
5Can you name, honestly, that this is an unsolved area of theory — rather than presenting NTK or implicit regularization as a fully settled explanation?
⚠️ What's Genuinely Unsolved
This entire article's Part 3 and Part 4 describe an active area of open research, not settled science. Neither the Neural Tangent Kernel framework nor implicit-regularization arguments constitute a complete, agreed-upon explanation for why overparameterized deep networks generalize as well as they do — both are genuine, serious contributions, and both have known limitations in explaining realistic, finite-width networks trained the way models in this series actually are. Presenting either as "the answer" would misrepresent the current state of the field.
Where This Series Goes Next
Article 6 moves from generalization theory to reinforcement learning foundations — the mathematical framework underneath RLHF (Articles 1, 2, and this series' "After Transformers" companion piece), covering value functions, policy gradients, and the exploration-exploitation tradeoff. From there, the series continues through interpretability, alignment, world models, systems, and research methodology, before a capstone article ties every foundational concept back into one unified map.
🔗 Additional Reference Links
🎥 Recommended Videos
🧭 Closing — The Theory Is Genuinely Behind the Practice, and That's Worth Saying Plainly
🎯 The Bottom Line
Classical learning theory (PAC learning, VC dimension, the bias-variance tradeoff) gives real, useful vocabulary and correctly describes a wide range of models — but it demonstrably fails to predict how modern, overparameterized deep networks actually behave, a gap Zhang et al.'s 2017 paper and the double-descent phenomenon (Article 4, and Part 4 above) document directly rather than merely suggest. Knowing this gap exists, and knowing the current leading (partial) explanations for it, is itself the actual research-literacy skill this article is teaching — not memorized confidence in a theory that, as of 2026, doesn't yet fully exist. The next article moves to reinforcement learning foundations, where a parallel gap between classical theory and practical RLHF systems shows up again.