# Identifying good directions to escape the NTK regime and efficiently learn low-degree plus sparse polynomials

arXiv: https://arxiv.org/abs/2206.03688 · HTML: https://mlsanity.com/paper/2206.03688/

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- Builds on 38 of its 54 references that are in the map.
- First posted on arXiv 8 Jun 2022.

## Builds on (most cited first, 30 of 38)

- [Neural Tangent Kernel: Convergence and Generalization in Neural Networks](https://mlsanity.com/paper/1806.07572/) (2018)
- [A Convergence Theory for Deep Learning via Over-Parameterization](https://mlsanity.com/paper/1811.03962/) (2018)
- [Wide Neural Networks of Any Depth Evolve as Linear Models Under Gradient Descent](https://mlsanity.com/paper/1902.06720/) (2019)
- [On Lazy Training in Differentiable Programming](https://mlsanity.com/paper/1812.07956/) (2018)
- [Gradient Descent Provably Optimizes Over-parameterized Neural Networks](https://mlsanity.com/paper/1810.02054/) (2018)
- [Gradient Descent Finds Global Minima of Deep Neural Networks](https://mlsanity.com/paper/1811.03804/) (2018)
- [On Exact Computation with an Infinitely Wide Neural Net](https://mlsanity.com/paper/1904.11955/) (2019)
- [Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks](https://mlsanity.com/paper/1901.08584/) (2019)
- [Learning and Generalization in Overparameterized Neural Networks, Going Beyond Two Layers](https://mlsanity.com/paper/1811.04918/) (2018)
- [Kernel and Rich Regimes in Overparametrized Models](https://mlsanity.com/paper/2002.09277/) (2020)
- [How to Escape Saddle Points Efficiently](https://mlsanity.com/paper/1703.00887/) (2017)
- [Learning Overparameterized Neural Networks via Stochastic Gradient Descent on Structured Data](https://mlsanity.com/paper/1808.01204/) (2018)
- [Deep learning: a statistical viewpoint](https://mlsanity.com/paper/2103.09177/) (2021)
- [Generalization Bounds of Stochastic Gradient Descent for Wide and Deep Neural Networks](https://mlsanity.com/paper/1905.13210/) (2019)
- [Finite Versus Infinite Neural Networks: an Empirical Study](https://mlsanity.com/paper/2007.15801/) (2020)
- [Linearized two-layers neural networks in high dimension](https://mlsanity.com/paper/1904.12191/) (2019)
- [When Do Neural Networks Outperform Kernel Methods?](https://mlsanity.com/paper/2006.13409/) (2020)
- [Neural Tangents: Fast and Easy Infinite Neural Networks in Python](https://mlsanity.com/paper/1912.02803/) (2019)
- [Stochastic Gradient Descent Optimizes Over-parameterized Deep ReLU Networks](https://mlsanity.com/paper/1811.08888/) (2018)
- [Regularization Matters: Generalization and Optimization of Neural Nets v.s. their Induced Kernel](https://mlsanity.com/paper/1810.05369/) (2018)
- [Theoretical insights into the optimization landscape of over-parameterized shallow neural networks](https://mlsanity.com/paper/1707.04926/) (2017)
- [Matrix Completion has No Spurious Local Minimum](https://mlsanity.com/paper/1605.07272/) (2016)
- [Spectral Methods for Data Science: A Statistical Perspective](https://mlsanity.com/paper/2012.08496/) (2020)
- [Generalization error of random features and kernel methods: hypercontractivity and kernel matrix concentration](https://mlsanity.com/paper/2101.10588/) (2021)
- [On the Power and Limitations of Random Features for Understanding Neural Networks](https://mlsanity.com/paper/1904.00687/) (2019)
- [On the Power of Over-parametrization in Neural Networks with Quadratic Activation](https://mlsanity.com/paper/1803.01206/) (2018)
- [Dynamics of Deep Neural Networks and Neural Tangent Hierarchy](https://mlsanity.com/paper/1909.08156/) (2019)
- [What Can ResNet Learn Efficiently, Going Beyond Kernels?](https://mlsanity.com/paper/1905.10337/) (2019)
- [Limitations of Lazy Training of Two-layers Neural Networks](https://mlsanity.com/paper/1906.08899/) (2019)
- [The Interpolation Phase Transition in Neural Networks: Memorization and Generalization under Lazy Training](https://mlsanity.com/paper/2007.12826/) (2020)

## Built on by (most cited first, 13 of 13)

- [Transformers Learn Shortcuts to Automata](https://mlsanity.com/paper/2210.10749/) (2022)
- [SGD learning on neural networks: leap complexity and saddle-to-saddle dynamics](https://mlsanity.com/paper/2302.11055/) (2023)
- [Grokking as the Transition from Lazy to Rich Training Dynamics](https://mlsanity.com/paper/2310.06110/) (2023)
- [Learning Single-Index Models with Shallow Neural Networks](https://mlsanity.com/paper/2210.15651/) (2022)
- [What can a Single Attention Layer Learn? A Study Through the Random Features Lens](https://mlsanity.com/paper/2307.11353/) (2023)
- [SGD Finds then Tunes Features in Two-Layer Neural Networks with near-Optimal Sample Complexity: A Case Study in the XOR problem](https://mlsanity.com/paper/2309.15111/) (2023)
- [Provable Guarantees for Nonlinear Feature Learning in Three-Layer Neural Networks](https://mlsanity.com/paper/2305.06986/) (2023)
- [Universal Scaling Laws of Absorbing Phase Transitions in Artificial Deep Neural Networks](https://mlsanity.com/paper/2307.02284/) (2023)
- [Tight conditions for when the NTK approximation is valid](https://mlsanity.com/paper/2305.13141/) (2023)
- [Compact Vision Transformer by Reduction of Kernel Complexity](https://mlsanity.com/paper/2507.12780/) (2025)
- [Shallow Neural Networks Learn Low-Degree Spherical Polynomials with Feature Learning by Learnable Channel Attention](https://mlsanity.com/paper/2512.20562/) (2025)
- [Gradient Descent with Projection Finds Over-Parameterized Neural Networks for Learning Low-Degree Polynomials with Nearly Minimax Optimal Rate](https://mlsanity.com/paper/2603.21062/) (2026)
- [Kernel Reboot: Breaking the Boundaries of Neural Tangent Kernels for Neural Fields](https://mlsanity.com/paper/2609.03117/) (2026)

## Abstract (arXiv)

A recent goal in the theory of deep learning is to identify how neural networks can escape the "lazy training," or Neural Tangent Kernel (NTK) regime, where the network is coupled with its first order Taylor expansion at initialization. While the NTK is minimax optimal for learning dense polynomials (Ghorbani et al, 2021), it cannot learn features, and hence has poor sample complexity for learning many classes of functions including sparse polynomials. Recent works have thus aimed to identify settings where gradient based algorithms provably generalize better than the NTK. One such example is the "QuadNTK" approach of Bai and Lee (2020), which analyzes the second-order term in the Taylor expansion. Bai and Lee (2020) show that the second-order term can learn sparse polynomials efficiently; however, it sacrifices the ability to learn general dense polynomials. In this paper, we analyze how gradient descent on a two-layer neural network can escape the NTK regime by utilizing a spectral characterization of the NTK (Montanari and Zhong, 2020) and building on the QuadNTK approach. We first expand upon the spectral analysis to identify "good" directions in parameter space in which we can move without harming generalization. Next, we show that a wide two-layer neural network can jointly use the NTK and QuadNTK to fit target functions consisting of a dense low-degree term and a sparse high-degree term -- something neither the NTK nor the QuadNTK can do on their own. Finally, we construct a regularizer which encourages our parameter vector to move in the "good" directions, and show that gradient descent on the regularized loss will converge to a global minimizer, which also has low test error. This yields an end to end convergence and generalization guarantee with provable sample complexity improvement over both the NTK and QuadNTK on their own.