---
cluster: "B"
day: "B.2"
title: Mysteries of Deep Learning
summary: Why deep learning works so well — approximation, generalization and optimization — and the parts nobody can explain yet.
contributors:
- Zach Furman (The University of Melbourne)
slides: https://drive.google.com/drive/folders/1SV-VYOSTzEGcRxw5GuDBCLbwQWj3k0Ym
---
## Prerequisites
* Basic awareness of Solomonoff induction and the high-level ideas behind it
* Basic understanding of deep learning, sufficient to read non-specialist ML papers
* Knowledge of mechanistic interpretability (Day C.2) is very helpful motivation but not logically necessary
* Students can explain and distinguish the three classical mysteries of why deep learning performs well: approximation, generalization, and optimization.
* Students understand why each of the three classical mysteries implicitly requires leveraging structure in reality: learning is not tractable for arbitrary tasks, so deep learning must be using non-generic properties of real-world tasks to succeed.
* Students are aware of the key empirical mysteries of deep learning: data-dependent generalization despite overparameterization, effectiveness of SGD on non-convex landscapes, representational alignment across architectures, and in-context learning
* Students have encountered at least one candidate explanation for each mystery and can articulate what it does and doesn't explain
* Students understand the "program synthesis" hypothesis as one proposed framework connecting deep learning to Solomonoff induction, and can evaluate its strengths and limitations
* Students can articulate why solving these mysteries matters for AI safety: understanding the basic mechanisms by which deep learning works is necessary for any *systematic* (generalizing OOD) alignment interventions or measurements to even be possible
## Fast-track
The content is already attempting to compress a somewhat disjointed research field, so it may be difficult to compress further. At a minimum, read the lecture slides for the overall framing, then read "Deep Learning as Program Synthesis" (skimming any sections one is already familiar with, and optionally deferring the "path forward" section). This gives a high level overview of various empirical mysteries. Then skim as many papers on the list as you have time/interest (possibly none).
## Reading guide
{/* Every discussion question below carries the author's written-out answer.
They were provisional TA-facing notes — shorthand in places, one of them
still TODO — never meant to be read by students, so each is commented out
here rather than published (author's call, 2026-07-29). Un-comment a block
to bring it back; nothing inside one has been edited. */}
### Lecture
[Slides.](https://drive.google.com/drive/folders/1SV-VYOSTzEGcRxw5GuDBCLbwQWj3k0Ym)
*Discussion questions:*
From an AI safety perspective, why is it worth trying to scientifically figure out how deep learning works? Why would we need scientific understanding for safety if such understanding seems to have been unnecessary for capabilities?
{/*
Answer: many answers are acceptable here. A few points one might mention:
* It seems increasingly likely that AGI/ASI will be based on deep learning
* Safety is intrinsically hard to hill-climb in the way that capabilities benchmarks are. Failures can be rare and have heavy-tail costs
* Historical comparisons (steam engine safety, aviation safety, etc)
*/}
What distinguishes the three classical mysteries discussed in the talk from each other? Which ones depend on the training procedure?
{/*
Answer: TODO
*/}
### Overview
[Deep Learning as Program Synthesis](https://www.lesswrong.com/posts/Dw8mskAvBX37MxvXo/deep-learning-as-program-synthesis-1)
(Note that this post presents an opinionated hypothesis (deep learning is performing something analogous to Solomonoff induction) alongside relatively consensus discussion of empirical mysteries. The post is largely being shared for the latter, though students may find the hypothesis itself useful pedagogically.)
*Discussion questions:*
Intuitively, what is Solomonoff induction and why do we care about it?
{/*
Answer: people should mention the universality hypothesis class, the simplicity prior, optimality results.
*/}
One can trivially say that a neural network "learns programs" because a neural network runs on a computer. Then one could say that e.g. linear regression "learns programs" too. What distinguishes the author's hypothesis from this more trivial fact?
{/*
Answer: this is answered in the post under the "Clarifying the hypothesis" expandable section. See in particular the FPGA analogy and the point about general-purpose search. It is also discussed further in the "representation problem" section where a possible mechanism is sketched
*/}
Where in the post do the three theoretical mysteries from the opening lecture (approximation, generalization, optimization) appear? Why does the post put the section related to "optimization" in a separate place from the other two mysteries?
{/*
Answer: they map to the "paradox of approximation" section, the "paradox of generalization" section, and the "search problem" section. Optimization shows up in the "search problem" section within "path forward" because it's the only one of the three mysteries which Solomonoff induction can't explain.
*/}
The post insists on maintaining the distinction between "functions" and "programs" - why? Why would we care to distinguish two networks that implement the same function by different means?
{/*
Answer: they may *train* differently; the gradients can be different even if the function implemented is the same. For instance, suppose network A is an LLM that has never learned about bioweapons, and network B is an LLM who learned about bioweapons but was trained to suppress this knowledge in the last layer. They may behave the same right now, but under fine-tuning one can easily recover dangerous capabilities in B but not A.
* One may be tempted to say that we should care because even if networks implement the same function in-distribution, they may behave differently out-of-distribution. But, while true and important, this is actually denying the premise of the question, because behaving differently out-of-distribution means the two functions really *are* different. The strong claim here is that you should care about implementation *even if no possible input/output test could distinguish between the two networks*.
*/}
### Approximation
[Approximation is expensive, but the lunch is cheap](https://www.lesswrong.com/posts/gq9GR6duzcuxyxZtD/approximation-is-expensive-but-the-lunch-is-cheap)
[Why and When Can Deep – but Not Shallow – Networks Avoid the Curse of Dimensionality: a Review](https://arxiv.org/pdf/1611.00740)
*Discussion questions:*
The Universal Approximation Theorem says a one-hidden-layer network can approximate any continuous function to arbitrary accuracy. Why is this *not* an explanation for deep learning's success?
{/*
Answer: because the number of neurons required is exponential, for generic smooth functions. The UAT is essentially a proof that *with exponential resources you can build a continuous lookup table.* This would require more parameters than are atoms in the universe just to e.g. approximate MNIST
*/}
If approximating *arbitrary* smooth functions provably requires exponentially many parameters (the curse of dimensionality), then what must be true about the functions deep learning actually faces for it to work at all? What is a "depth separation" result and what does it suggest about the answer to this question?
{/*
Answer: real target functions *provably* must have some non-generic structure beyond that of generic Lipschitz functions, if realistic-size deep neural networks are to be capable of representing them at all. Depth separation results are theoretical results showing that there exist target functions that require exponentially many more parameters for a shallow network to approximate compared to a deep network. They hint that the non-generic target structure neural networks are exploiting may be *compositional* structure, as deep but not shallow networks can exploit this structure. Bonus points for relating this to program structure discussed in the "program synthesis" post
*/}
### Generalization
[The paper that killed deep learning theory](https://www.lesswrong.com/posts/ZvQfcLbcNHYqmvWyo/the-paper-that-killed-deep-learning-theory)
[Deep Learning is Not So Mysterious or Different](https://arxiv.org/abs/2503.02113)
*Discussion questions:*
There are different notions of "generalization" that aren't equivalent. What precisely do these resources mean by the word "generalization"? How does it differ from out-of-distribution (OOD) generalization?
{/*
Answer: The resources here deliberately refer to *in-distribution generalization*, that is the gap between test loss and train loss where the train loss is sampled from the same distribution the test loss is evaluated over. This excludes OOD generalization, which would require evaluating the test loss against a different input/label distribution than the training samples are sampled from. Historically, the word "generalization" within statistical learning theory has typically referred to in-distribution generalization, but in common ML usage the word increasingly refers to OOD generalization. It is therefore *very common* for students to conflate in-distribution and OOD generalization, but they are totally different notions within a statistical learning theory context, and OOD generalization is almost impossible to prove useful results about in generality (the test distribution can change to anything!) despite sounding more appealing. There is still no consensus explanation for in-distribution generalization, and OOD generalization is strictly harder to explain.
* "The framework imagined a data distribution $D$ over inputs $X$ and outputs $Y$ where the goal was to fit a hypothesis $h : X \to Y$ that minimized the expected test loss for a loss function $L : X \times Y \to R$ over $D$. A learning algorithm would receive $n$ samples from the data distribution, and would minimize the training loss averaged across the sample $L(h(x), y)$."
*/}
Why are the experimental results of Zhang et al. fatal to capacity-based generalization bounds (VC dimension, Rademacher complexity, etc)? What does this imply for explanations about generalization and what they must depend on?
{/*
Answer: the architecture and algorithm are *fixed* across the two runs, so any complexity measure that depends only on the hypothesis class and the (data-independent) algorithm must give the same number in both - yet one generalizes and one doesn't. Therefore generalization is not a property of the model; it's an emergent property of model × algorithm × *data structure*.
*/}
The first post is rather pessimistic in tone, declaring deep learning theory (or at least the theory surrounding generalization) to have been "killed." Meanwhile "Deep Learning is Not So Mysterious or Different" seems to take precisely the opposite attitude, that such empirical results are not too surprising under preexisting theoretical frameworks. Despite the difference in tone, how compatible are these results on the object level? What common picture do they paint?
{/*
Answer: They're fully compatible - Zhang et al. is a negative result and Wilson is a positive proposal in the space it leaves open. Both say generalization is not a uniform property of the model class: capacity measures like VC dimension or Rademacher complexity can't explain it, since the same network generalizes on real data and memorizes random labels. Zhang stops there (an experimental result ruling out capacity-based explanations); Wilson supplies a candidate replacement - soft inductive biases, a flexible hypothesis space with a data-dependent preference for simpler solutions - which is exactly the kind of non-uniform, data-dependent explanation Zhang leaves room for. The "killed vs not mysterious" clash is one of tone, not content.
*/}
### Optimization
[Understanding Machine Learning: From Theory to Algorithms](https://www.cambridge.org/core/books/understanding-machine-learning/3059695661405D25673058E43C8BE2A6), Section 8.4 (Hardness of learning)
*Discussion questions:*
These cryptographic hardness arguments apply to neural networks, since neural networks can implement one-way functions. What does this imply about how long SGD will take to learn such functions? By contrast, how will Bayesian learning behave in such a scenario (and why are hardness arguments vacuous for Bayes)? What does this imply about how approximation and generalization come apart from optimization?
{/*
Answer: the hardness argument means that (under cryptographic assumptions) SGD can't learn hard targets in polynomial time. Bayes, meanwhile, will rapidly concentrate posterior mass on the target because it's realizable and gets zero train loss. Bayes doesn't run in polynomial time, so hardness arguments are vacuously true here and don't force poor performance. In this way, Bayesian learning gives an algorithm with good approximation and generalization, but terrible optimization efficiency, because it can't run in polynomial time.
*/}
Despite the fact that neural networks can realize worst-case targets, neural networks train well in practice. Why care about these pathological examples, then? What makes the takeaway different from the obvious "algorithms can have typical-case performance which is much better than their worst-case performance"?
{/*
Answer: one can make a few points here.
* As discussed in the previous question, this phenomenon separates approximation and generalization from optimization difficulty. This is especially important because while e.g. Solomonoff induction gives us a good model of how one can simultaneously achieve good approximation and generalization, it gives no answer as to the optimization problem. It separates the questions we have an in-principle explanation of from the one we don't
* It constrains explanation for the optimization problem. Any explanation for why training succeeds (in poly time) which works uniformly across all targets must be wrong. Instead, you *must* engage with the target structure, in such a way that your explanation applies for typical targets but does not apply for worst-case targets. (Emphasize: there's a pattern here, the approximation and generalization problems *also* force us to provide explanations which depend on non-generic target structure.)
* As a kicker, it's not obvious at all how such worst-case functions can easily be separated from the typical ones. They're realizable, they lie inside your hypothesis class. They show up *automatically* and *inevitably* in any model which can perform sufficiently general computation (because then you can implement one-way functions.) In fact, you can't even distinguish worst-case functions from typical ones *by any black box (purely input/output) procedure whatsoever*, since that would break the cryptographic hardness assumption as well. So the explanation for the typical/worst-case gap must really be sophisticated.
* Re: the program synthesis hypothesis, note also that the explanation here can't be "optimization succeeds because real-world targets have compositional/program structure and generic functions don't," because the worst-case targets obviously have program structure, and they're rather short and simple programs at that. One must distinguish between different types of programs.
*/}
### Representational alignment
[The Platonic Representation Hypothesis](https://arxiv.org/abs/2405.07987)
*Discussion questions:*
What is the new[^prh-novelty] hypothesis that paper promotes, versus what are the observations already established by prior literature? What evidence do they cite for their hypothesis? What distinguishes their hypothesis from merely "models converge to shared representations"?
{/*
Answer: The *observation* that independently trained models learn similar representations is old and well-established - it predates the paper by years (model stitching, CKA/RSA similarity, "convergent learning," universal Gabor filters, vision models predicting visual cortex). What's *new* is not that models resemble each other but a claim about where they're heading: representations are converging toward a single endpoint, and that endpoint is a representation of the underlying reality - the statistical structure of the world that generated the data (their "platonic" representation, idealized as a kernel reflecting how real-world events co-occur). The evidence they cite for *this* is (i) convergence that grows with model scale and competence, (ii) convergence that holds *across modalities* - vision and language models becoming more alignable as they get more capable - and (iii) a theoretical argument that multitask pressure, capacity, and simplicity bias funnel diverse models toward the same solution. The distinction from "models converge to shared representations" is the addition of a *limit point* and its *identity*: plain convergence is just pairwise similarity, and is equally consistent with models merely sharing architectures, objectives, or training data; PRH claims they share a *destination*, and that the destination is reality's structure - which is what licenses its signature prediction that convergence should cross modalities. That cross-modal and scaling evidence is exactly the novel, load-bearing, and most-contested part; the bare convergence phenomenon is the consensus part.
* Note that papers like "[Revisiting the PRH: An Aristotelian View](https://arxiv.org/abs/2602.14486)" have criticized some of the evidence in the PRH paper and propose a slightly weaker hypothesis. However their critiques only apply to evidence based on CKA, a particular technique, and other evidence appears to survive
*/}
### In-context learning
[In-context Learning and Induction Heads](https://transformer-circuits.pub/2022/in-context-learning-and-induction-heads/index.html)
*Discussion questions:*
What is an induction head, and what relationship does the paper draw between induction-head formation and in-context learning over training? Why treat the simultaneity as evidence of a mechanistic link rather than coincidence?
{/*
An induction head is a circuit implementing the rule \[A\]\[B\] … \[A\] → \[B\] - find the previous occurrence of the current token, see what followed it, predict that again ("complete the pattern" by copying). Mechanically it's two heads composed across layers (a previous-token head feeding the induction head), so it cannot exist in a 1-layer model. In-context learning is operationalized as the drop in loss from early to late token positions (the model predicting better the more context it has seen). Early in training there is a phase change, visible as a bump in the training loss, during which induction heads form and the bulk of in-context-learning ability appears simultaneously - for models of every size with more than one layer. Simultaneity alone would only be suggestive; the case is carried by co-perturbation (when they modify the architecture to move when induction heads can form, the in-context-learning jump moves to match) and by direct ablation (knocking out induction heads in small models sharply reduces in-context learning)
*/}
## Further reading
* [Deep learning theory lecture notes](https://mjt.cs.illinois.edu/dlt/) (Telgarsky)
* A rigorous course-long treatment of statistical learning theory, following the same approximation/generalization/optimization error decomposition we use
* [The other paper that killed deep learning theory](https://www.lesswrong.com/posts/zcGmdQHX66NhC69v6/the-other-paper-that-killed-deep-learning-theory)
* Discusses a 2019 result by Nagarajan and Kolter that doomed the worst-case *uniform convergence* framework for explaining neural network generalization
* [Understanding deep learning requires rethinking generalization](https://arxiv.org/abs/1611.03530)
* Original paper which changed the field's mind on generalization, referenced by "The paper that killed deep learning theory"
* [Hidden Progress in Deep Learning: SGD Learns Parities Near the Computational Limit](https://arxiv.org/abs/2207.08799)
* [SGD learning on neural networks: leap complexity and saddle-to-saddle dynamics](https://arxiv.org/abs/2302.11055)
* [The No Free Lunch Theorem, Kolmogorov Complexity, and the Role of Inductive Biases in Machine Learning](https://arxiv.org/abs/2304.05366)
* [The Scaling Hypothesis](https://gwern.net/scaling-hypothesis)
* Quite polemical. Nevertheless, very influential "ideas piece"
* [Getting aligned on representational alignment](https://arxiv.org/abs/2310.13018)
* A broader overview of the representational alignment phenomenon
* [Exact solutions to the nonlinear dynamics of learning in deep linear neural networks](https://arxiv.org/abs/1312.6120)
* Classic paper which finds stagewise learning in neural networks with linear activation function; will be covered later in the course
* [Stagewise Development in Neural Networks](https://www.lesswrong.com/posts/Zza9MNA7YtHkzAtit/stagewise-development-in-neural-networks)
* A nice paper investigating stagewise learning in small LLMs. Requires some SLT knowledge
* [Emergent Misalignment: Narrow finetuning can produce broadly misaligned LLMs](https://arxiv.org/abs/2502.17424)
* Training on "evil" data in narrow domains (like, code with vulnerabilities) generalizes to "evil" more broadly (praising Hitler, etc)
[^prh-novelty]: One could argue that this hypothesis isn't novel either, see e.g. the natural abstraction hypothesis which significantly predates this, but this paper was the first major academic paper to promote the hypothesis.