What Can ResNet Learn Efficiently, Going Beyond Kernels?

Zeyuan Allen-Zhu, Yuanzhi Li

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).

Three-layer ResNet architecture with a single skip connection

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:

  1. 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.
  2. 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.
  3. 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

Abstract

How can neural networks such as ResNet \emph{efficiently} learn CIFAR-10 with test accuracy more than $96 \%$, while other methods, especially kernel methods, fall relatively behind? Can we more provide theoretical justifications for this gap? Recently, there is an influential line of work relating neural networks to kernels in the over-parameterized regime, proving they can learn certain concept class that is also learnable by kernels with similar test error. Yet, can neural networks provably learn some concept class \emph{better} than kernels? We answer this positively in the distribution-free setting. We prove neural networks can efficiently learn a notable class of functions, including those defined by three-layer residual networks with smooth activations, without any distributional assumption. At the same time, we prove there are simple functions in this class such that with the same number of training examples, the test error obtained by neural networks can be \emph{much smaller} than \emph{any} kernel method, including neural tangent kernels (NTK). The main intuition is that \emph{multi-layer} neural networks can implicitly perform hierarchal learning using different layers, which reduces the sample complexity comparing to ``one-shot'' learning algorithms such as kernel methods. In the end, we also prove a computation complexity advantage of ResNet with respect to other learning methods including linear regression over arbitrary feature mappings.
BibTeX
@inproceedings{allenzhu2019what,
  author = {Zeyuan Allen-Zhu and Yuanzhi Li},
  title = {{What Can ResNet Learn Efficiently, Going Beyond Kernels?}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2019},
  url = {https://openreview.net/forum?id=1dCWkwKD-nw},
}
Figure