Quantifying the Benefit of Using Differentiable Learning over Tangent Kernels

Eran Malach, Pritish Kamath, Emmanuel Abbe, Nathan Srebro

Introduction

The Neural Tangent Kernel (NTK) theory has been a cornerstone of recent deep learning theory, suggesting that wide neural networks trained with gradient descent (GD) often behave like simple linear models with a fixed kernel. This "lazy training" regime has provided many theoretical breakthroughs, but it leaves a burning question: Is there something more to deep learning? Can gradient descent on a non-convex model learn things that a kernel method simply cannot?

Previous research showed GD can outperform kernels, but in those examples, the NTK still provided at least a "weak learning" edge (performing slightly better than random guessing). This paper investigates whether GD can succeed even when the NTK has no significant edge over a trivial "null" predictor.

Methodology

To explore this, the authors use a combination of formal proofs and constructive examples. They define specific learning problems involving "sparse parities"—functions that depend on a small subset of input bits.

To prove their points, they construct a specific differentiable model that combines a linear predictor with a "selected-parity" gadget.

Schematic diagram of the constructed differentiable model

This architecture allows them to mathematically track how a single step of gradient descent can identify relevant features and then "boost" them to perfect accuracy. They contrast this with the behavior of the NTK at initialization to see if it could have achieved the same result. The paper primarily uses synthetic, mathematically defined datasets designed to highlight theoretical separations, such as Biased Sparse Parities ($P^{bsp}$) and Leaky Parities ($P^{lp}$).

Key Insights

  • The Role of Initialization: The "unbiasedness" of initialization (where the model outputs zero at the start) is a critical dividing line. If initialization is unbiased, the authors prove that GD success guarantees the NTK has at least a polynomial edge over random guessing.
  • Biased Initialization as a Power-Up: Surprisingly, with a biased initialization, GD can learn problems where the NTK (and indeed any reasonably sized kernel) has absolutely zero edge. This suggests that "bias" isn't always a bad thing; it can be a tool for learning.
  • Distribution Dependence: Kernel methods are typically distribution-independent—the kernel is fixed before seeing data. The authors show that GD's ability to adapt to the input distribution is a fundamental advantage that standard kernel methods cannot replicate.

Empirical and Theoretical Results

The authors prove that for certain problems, GD achieves zero error while any polynomial-sized kernel method is stuck at a loss of 0.5 (random guessing). Furthermore, they provide a formal lower bound: if GD achieves low error from an unbiased start, the NTK must have an edge that is at least polynomial in the algorithm's parameters.

Beyond the proofs, they test their theories on a standard two-layer fully-connected ReLU network trained on the $P^{bsp}$ distribution.

Test loss of a two-layer ReLU network vs. kernel lower bounds

As demonstrated in the empirical results, as the "bias" ($\alpha$) in the input bits decreases (making the problem harder), the NTK's performance (horizontal lines) stays near 0.5, while GD (solid lines) still manages to drive the test loss to zero.

Limitations and Future Work

The authors acknowledge that their constructed models and learning problems are "artificially extreme" to allow for clean analytical study. While they show the same behavior in a standard ReLU network, a major future direction is extending these results to more "natural" datasets and architectures.

Additionally, their analysis of biased initialization opens up new questions: if biased starts allow us to learn things kernels can't, how should we design initialization schemes to maximize this "non-lazy" learning potential? This work suggests that the common practice of initializing to near-zero output might actually be limiting what our models can discover.

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