For years, a "theory gap" has existed in machine learning. In practice, deep residual networks (ResNets) achieve massive success on complex tasks like CIFAR-10, while kernel methods—once the gold standard of theoretical machine learning—lag significantly behind.
Recent theoretical work on Neural Tangent Kernels (NTK) attempted to bridge this gap by showing that very wide neural networks behave like kernels. However, this created a new paradox: if neural networks are mathematically just kernels in the over-parameterized regime, why do they perform so much better in the real world?
This NeurIPS 2019 paper by Zeyuan Allen-Zhu and Yuanzhi Li tackles this fundamental question, providing the first provable "separation" between neural networks and kernel methods in a distribution-free setting. They demonstrate that three-layer ResNets can efficiently learn hierarchical functions that would require exponentially more data for any kernel method to master.
The Target Concept Class and Learner
To prove this separation, the authors analyze the learnability of a specific Concept Class of functions. They define a target function $H(x)$ as a composition:
$$H(x) = F(x) + \alpha G(F(x))$$
Here, $F$ represents a relatively simple "base signal," and $G$ represents a more complex "composite signal."
To learn this function, the authors employ a three-layer ResNet with ReLU activations, trained via standard Stochastic Gradient Descent (SGD).
Crucially, this network utilizes a "single-skip" architecture. As shown in the figure above, the second hidden layer receives the output of the first layer via a residual connection, allowing the network to process hierarchical information effectively.
Key Insights: Why ResNets Outperform Kernels
The paper's mathematical analysis reveals several core reasons why the ResNet architecture succeeds where kernel methods fail:
- Implicit Hierarchical Learning: The authors show that ResNets do not just learn a flat mapping. Instead, they use different layers to "disentangle" the function. The first layer learns the base signal $F$, and the subsequent layers use that extracted information to learn the more complex composite signal $G$.
- The Failure of "One-Shot" Learning: Kernel methods attempt to learn the entire complex mapping $H(x)$ in a single, "one-shot" process. Because they lack a multi-layer structure to break the problem down hierarchically, their sample complexity (the amount of data needed to generalize) explodes as the target function becomes more complex.
- Residual Links as Complexity Reducers: The residual connection is vital to this process. It allows the network to pass the "simple" part of the signal forward, freeing the deeper layers to focus exclusively on the "residual" complex part. This effectively reduces the difficulty of the optimization landscape.
Provable Separation and Efficiency
The theoretical results provide a stark contrast in performance:
- Sample Complexity Separation: For a target function with a degree-$k$ polynomial component, the paper proves that a ResNet needs roughly $O(d)$ samples to learn it. In contrast, any kernel method (including NTKs) requires $\Omega(d^{k/2})$ samples. When the dimensionality $d$ is large, this difference is astronomical.
- Optimization Efficiency: The authors prove that ResNets can learn these functions in polynomial time using standard SGD. This does not require specialized initialization or unrealistic assumptions like Gaussian input distributions.
- Computational Advantage: Beyond data efficiency, ResNets exhibit a computational complexity advantage. They are mathematically proven to be faster than performing linear regression over arbitrary feature mappings for this specific class of functions.
Limitations and Future Directions
While a significant breakthrough, the paper notes a few theoretical boundaries. The current proof establishes that ResNets can reach a specific error level (bounded by an $\alpha^4$ error floor), but it does not guarantee zero error for every possible distribution. Additionally, the rigorous analysis is constrained to three-layer networks. While the authors suggest these principles extend to arbitrary depths with "backward feature correction," this specific proof focuses on the foundational three-layer case. Finally, while the negative results cover a vast range of kernels, certain highly specialized kernels might require further analysis.
Summary updated