# Learning Over-Parametrized Two-Layer ReLU Neural Networks beyond NTK

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

## Key facts

- Cited by 18 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Jul 2020.

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

- [Neural Networks can Learn Representations with Gradient Descent](https://mlsanity.com/paper/2206.15144/) (2022)
- [Toward Understanding the Feature Learning Process of Self-supervised Contrastive Learning](https://mlsanity.com/paper/2105.15134/) (2021)
- [Vision Transformers provably learn spatial structure](https://mlsanity.com/paper/2210.09221/) (2022)
- [Small random initialization is akin to spectral learning: Optimization and generalization guarantees for overparameterized low-rank matrix reconstruction](https://mlsanity.com/paper/2106.15013/) (2021)
- [A Local Convergence Theory for Mildly Over-Parameterized Two-Layer Neural Network](https://mlsanity.com/paper/2102.02410/) (2021)
- [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)
- [The Mechanism of Prediction Head in Non-contrastive Self-supervised Learning](https://mlsanity.com/paper/2205.06226/) (2022)
- [Over-Parameterization Exponentially Slows Down Gradient Descent for Learning a Single Neuron](https://mlsanity.com/paper/2302.10034/) (2023)
- [Proxy Convexity: A Unified Framework for the Analysis of Neural Networks Trained by Gradient Descent](https://mlsanity.com/paper/2106.13792/) (2021)
- [Provable Generalization of SGD-trained Neural Networks of Any Width in the Presence of Adversarial Label Noise](https://mlsanity.com/paper/2101.01152/) (2021)
- [Why Do Local Methods Solve Nonconvex Problems?](https://mlsanity.com/paper/2103.13462/) (2021)
- [Deep Networks Provably Classify Data on Curves](https://mlsanity.com/paper/2107.14324/) (2021)
- [On the Provable Generalization of Recurrent Neural Networks](https://mlsanity.com/paper/2109.14142/) (2021)
- [Efficiently Learning Any One Hidden Layer ReLU Network From Queries](https://mlsanity.com/paper/2111.04727/) (2021)
- [How Learnable Grids Recover Fine Detail in Low Dimensions: A Neural Tangent Kernel Analysis of Multigrid Parametric Encodings](https://mlsanity.com/paper/2504.13412/) (2025)
- [Muon Learns More Robust and Transferable Features than Adam](https://mlsanity.com/paper/2606.09658/) (2026)
- [Feature learning is decoupled from generalization in high capacity neural networks](https://mlsanity.com/paper/2507.19680/) (2025)
- [Unintended Effects on Adaptive Learning Rate for Training Neural Network with Output Scale Change](https://mlsanity.com/paper/2103.03466/) (2021)

## Abstract (arXiv)

We consider the dynamic of gradient descent for learning a two-layer neural network. We assume the input x∈ℝd is drawn from a Gaussian distribution and the label of x satisfies fstar(x) = atop|Wstarx|, where a∈ℝd is a nonnegative vector and Wstar ∈ℝd× d is an orthonormal matrix. We show that an over-parametrized two-layer neural network with ReLU activation, trained by gradient descent from random initialization, can provably learn the ground truth network with population loss at most o(1/d) in polynomial time with polynomial samples. On the other hand, we prove that any kernel method, including Neural Tangent Kernel, with a polynomial number of samples in d, has population loss at least Omega(1 / d).