Quantifying the Benefit of Using Differentiable Learning over Tangent Kernels

Eran Malach, Pritish Kamath, Emmanuel Abbe, Nathan Srebro

TL;DR

This paper investigates whether the success of deep learning can be fully explained by the Neural Tangent Kernel (NTK) approximation. The authors prove that while gradient descent (GD) requires the NTK to have at least a "weak learning" edge under unbiased initialization, a biased initialization allows GD to succeed even when no kernel method can perform better than random guessing.

What Problem Does This Paper Address?

A major trend in deep learning theory seeks to understand neural networks through the lens of the Neural Tangent Kernel (NTK). In the "lazy training" regime, the dynamics of a neural network are approximately linear, meaning training the network with gradient descent is equivalent to using a kernel method with a fixed kernel defined at initialization.

However, researchers have long suspected that real-world deep learning goes beyond this "lazy" regime to perform active feature learning. The central question this paper tackles is: Is gradient descent just a way to "boost" a pre-existing edge in the tangent kernel, or can it succeed in regimes where the kernel has no edge at all?

The authors explore the boundary between these two learning paradigms, specifically looking at how initialization (biased vs. unbiased) and knowledge of the input distribution change what is learnable.

Methods

The authors use a combination of theoretical proofs and constructive examples to establish "separations" between GD and kernel methods.

  1. Theoretical Bounds: They prove Theorem 1, which states that for any smooth loss, if GD succeeds from an unbiased initialization (where the model outputs zero at the start), the NTK must have a non-trivial (polynomial) edge over random guessing.
  2. Constructive Separations: To show where GD outperforms kernels, they design specific learning problems based on sparse parities. They construct a differentiable model that combines a linear predictor with a "selected-parity" module.
  3. Model Architecture: As shown in Figure 2, their model uses trainable weights $\theta$ to first "pick up" relevant features via a linear correlation, which then triggers a non-linear parity function $\mathcal{G}$ to achieve zero error.
Figure 2: Schematic diagram for the construction of fθ, as used in Claim 3.1, with only trainable parameters being θ1, θ2, . . . , θn. The sub-network G is a fixed module implementing the “selected-parity” function.

Datasets

The paper relies on synthetic, mathematically rigorous learning problems rather than standard benchmarks like ImageNet:

  • Biased Sparse Parities: A problem where the target is a parity of $k$ bits, and the input bits are slightly biased. This bias gives the NTK a tiny "weak learning" edge that GD can amplify.
  • Leaky Parities: A more difficult problem where the support of the parity is "leaked" through the input distribution's marginals, but the labels themselves are uncorrelated with individual bits at initialization.
  • Empirical Verification: The authors also provide experimental results using a standard two-layer fully-connected ReLU network (128 units) trained on these parity problems to show that the theoretical separations hold in more "natural" architectures.

Key Insights and Ideas

  • The Power of Bias: The most surprising finding is the role of biased initialization. If a model starts with a non-zero output, GD can use the resulting gradients to explore the input distribution's structure in a way that is fundamentally impossible for fixed kernel methods.
  • Weak vs. Strong Learning: The authors show that for unbiased models, GD is essentially a "booster"—it needs the NTK to provide a starting point (weak learning) to reach high accuracy (strong learning).
  • Distribution Dependence: The paper highlights a subtle distinction: if you allow your kernel to depend on the input distribution (e.g., via unlabeled data), it can sometimes match GD. However, for distribution-independent learning, GD remains strictly more powerful.
  • Initialization Matters: The results, summarized in the table below (Figure 3), provide a complete map of how large an edge the NTK must have in different scenarios.
Summary of results showing the required NTK edge for GD success across different initialization and kernel types.

Key Results

  • Separation 1 & 2: The authors demonstrate cases where GD achieves zero error while the NTK (and any other poly-sized kernel) has an edge that vanishes at a polynomial rate.
  • Separation 3 & 4: With biased initialization, they show GD can succeed even when the NTK edge is exactly zero or exponentially small.
  • Theorem 2: They prove that for the square loss, if GD succeeds from any initialization, there exists some alternate randomized initialization where the NTK has an edge. Crucially, this alternate initialization must depend on the input distribution.

Limitations and Future Work

  • "Unnatural" Models: The models used for the proofs are highly specialized (e.g., using piece-wise quadratic sigmoidal activations and fixed sub-networks). While empirical tests on ReLU networks suggest the findings generalize, a formal proof for standard architectures remains open.
  • Optimization Path: The analysis often relies on a single large gradient step. Extending this to continuous gradient flow or many small steps would make the results more robust.
  • Fixed vs. Variable Problems: Some separations (3 and 4) involve constructing a different problem for every desired error level $\epsilon$, rather than showing GD converges to zero error on a single fixed problem where kernels fail. Strengthening these to fixed problems is a suggested direction for future research.

Summary updated

Abstract

We study the relative power of learning with gradient descent on differentiable models, such as neural networks, versus using the corresponding tangent kernels. We show that under certain conditions, gradient descent achieves small error only if a related tangent kernel method achieves a non-trivial advantage over random guessing (a.k.a. weak learning), though this advantage might be very small even when gradient descent can achieve arbitrarily high accuracy. Complementing this, we show that without these conditions, gradient descent can in fact learn with small error even when no kernel method, in particular using the tangent kernel, can achieve a non-trivial advantage over random guessing.
BibTeX
@inproceedings{malach2021quantifying,
  author = {Eran Malach and Pritish Kamath and Emmanuel Abbe and Nathan Srebro},
  title = {{Quantifying the Benefit of Using Differentiable Learning over Tangent Kernels}},
  booktitle = {International Conference on Machine Learning},
  year = {2021},
  url = {https://openreview.net/forum?id=olSVLiCXuUm},
}
Figure