Mysteries of Deep Learning
Why deep learning works so well — approximation, generalization and optimization — and the parts nobody can explain yet.
By Zach Furman (The University of Melbourne)
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
Lecture
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?
What distinguishes the three classical mysteries discussed in the talk from each other? Which ones depend on the training procedure?
Overview
Deep Learning as Program Synthesis
(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?
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?
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?
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?
Approximation
Approximation is expensive, but the lunch is cheap
Why and When Can Deep – but Not Shallow – Networks Avoid the Curse of Dimensionality: a Review
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?
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?
Generalization
The paper that killed deep learning theory
Deep Learning is Not So Mysterious or Different
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?
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?
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?
Optimization
Understanding Machine Learning: From Theory to Algorithms, 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?
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"?
Representational alignment
The Platonic Representation Hypothesis
Discussion questions:
What is the new1 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"?
In-context learning
In-context Learning and Induction Heads
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?
Further reading
- Deep learning theory lecture notes (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
- 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
- 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
- SGD learning on neural networks: leap complexity and saddle-to-saddle dynamics
- The No Free Lunch Theorem, Kolmogorov Complexity, and the Role of Inductive Biases in Machine Learning
- The Scaling Hypothesis
- Quite polemical. Nevertheless, very influential "ideas piece"
- Getting aligned on representational alignment
- A broader overview of the representational alignment phenomenon
- Exact solutions to the nonlinear dynamics of learning in deep linear neural networks
- 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
- A nice paper investigating stagewise learning in small LLMs. Requires some SLT knowledge
- Emergent Misalignment: Narrow finetuning can produce broadly misaligned LLMs
- Training on "evil" data in narrow domains (like, code with vulnerabilities) generalizes to "evil" more broadly (praising Hitler, etc)
Footnotes
-
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. ↩