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