unsolved.now

the board / Engineering & AI

The Generalization Puzzle

Deep learning works far better than our math says it should

open for 10 years

posed 2016 · Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals

Why do giant neural networks — big enough to simply memorize their training data — instead learn rules that work on data they have never seen?

The problem

Classical learning theory says a model with far more parameters than training examples should overfit: memorize the data and fail on anything new. Deep networks blow through that prediction daily, and a landmark 2016 experiment made the paradox undeniable — the same networks that generalize beautifully can also perfectly memorize completely random labels, so the standard theoretical guarantees explain essentially nothing about why they work. Since then the mystery has deepened with strange, reproducible phenomena: 'double descent', where making a model bigger first hurts and then helps, and 'grokking', where a network suddenly snaps from memorization to perfect generalization long after it seemed hopelessly overfit. Partial accounts exist, but no accepted theory yet predicts when and why deep learning generalizes.

Why it matters

Trillions of dollars of infrastructure now rest on an empirical recipe we cannot mathematically explain. A real theory would tell us how much data and compute a capability actually requires, when a model will fail on out-of-distribution inputs, and whether surprises like grokking lurk in the systems we deploy.

Progress so far

  • 2016Zhang et al. show state-of-the-art networks can perfectly fit random labels, demolishing classical explanations of their generalization
  • 2018Belkin et al. describe 'double descent': test error falls again beyond the point where models perfectly fit their training data
  • 2022Power et al. report 'grokking': sudden generalization on algorithmic tasks long after overfitting
  • 2026unifying frameworks (circuit competition, learning-speed decompositions) link grokking, double descent, and emergence, but remain partial and contested

References

  1. arXiv (Zhang et al., 2016) — the random-label experiment that crisply posed the modern generalization puzzle
  2. arXiv (Belkin et al., 2018) — 'Reconciling modern machine-learning practice and the classical bias–variance trade-off' — the double-descent curve
  3. arXiv (Power et al., 2022) — 'Grokking: Generalization Beyond Overfitting on Small Algorithmic Datasets'
Status: open. Verified still unsolved as of 2026-07-24. Every date, name, and claim above traces to the references; if this problem falls, the board will say so.
Suggest a problem for the board Follow the board