mlsanityData to 7 Oct 2026

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

arXiv 2007.04596 ↗First posted 9 Jul 2020cs.LG math.OC stat.MLcited by 18

Not on the map. Why?

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

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 10; 2022: 3; 2023: 2; 2024: 0; 2025: 2; 2026: 1.

18 papers.

Sort:

  1. 2022Neural Networks can Learn Representations with Gradient Descentcited by 161
  2. 2021Toward Understanding the Feature Learning Process of Self-supervised Contrastive Learningcited by 119
  3. 2022Vision Transformers provably learn spatial structurecited by 92
  4. 2021Small random initialization is akin to spectral learning: Optimization and generalization guarantees for overparameterized low-rank matrix reconstructioncited by 77
  5. 2021A Local Convergence Theory for Mildly Over-Parameterized Two-Layer Neural Networkcited by 47
  6. 2022The Mechanism of Prediction Head in Non-contrastive Self-supervised Learningcited by 38
  7. 2023SGD Finds then Tunes Features in Two-Layer Neural Networks with near-Optimal Sample Complexity: A Case Study in the XOR problemcited by 36
  8. 2023Over-Parameterization Exponentially Slows Down Gradient Descent for Learning a Single Neuroncited by 25
  9. 2021Proxy Convexity: A Unified Framework for the Analysis of Neural Networks Trained by Gradient Descentcited by 21
  10. 2021Provable Generalization of SGD-trained Neural Networks of Any Width in the Presence of Adversarial Label Noisecited by 17
  11. 2021Why Do Local Methods Solve Nonconvex Problems?cited by 8
  12. 2021Deep Networks Provably Classify Data on Curvescited by 6
6 more
  1. 2021On the Provable Generalization of Recurrent Neural Networkscited by 6
  2. 2021Efficiently Learning Any One Hidden Layer ReLU Network From Queriescited by 6
  3. 2025How Learnable Grids Recover Fine Detail in Low Dimensions: A Neural Tangent Kernel Analysis of Multigrid Parametric Encodingscited by 3
  4. 2025Feature learning is decoupled from generalization in high capacity neural networkscited by 1
  5. 2026Muon Learns More Robust and Transferable Features than Adamcited by 1
  6. 2021Unintended Effects on Adaptive Learning Rate for Training Neural Network with Output Scale Changecited by 0