mlsanityData to 14 Oct 2026

On Learning Over-parameterized Neural Networks: A Functional Approximation Perspective

arXiv 1905.10826 ↗First posted 26 May 2019cs.LG stat.MLcited by 28

Not on the map. Why?

Abstract (arXiv)

We consider training over-parameterized two-layer neural networks with Rectified Linear Unit (ReLU) using gradient descent (GD) method. Inspired by a recent line of work, we study the evolutions of network prediction errors across GD iterations, which can be neatly described in a matrix form. When the network is sufficiently over-parameterized, these matrices individually approximate em an integral operator which is determined by the feature vector distribution ρ only. Consequently, GD method can be viewed as em approximately applying the powers of this integral operator on the underlying/target function f^* that generates the responses/labels. We show that if f^* admits a low-rank approximation with respect to the eigenspaces of this integral operator, then the empirical risk decreases to this low-rank approximation error at a linear rate which is determined by f^* and ρ only, i.e., the rate is independent of the sample size n. Furthermore, if f^* has zero low-rank approximation error, then, as long as the width of the neural network is Omega(nlog n), the empirical risk decreases to Theta(1/√n). To the best of our knowledge, this is the first result showing the sufficiency of nearly-linear network over-parameterization. We provide an application of our general results to the setting where ρ is the uniform distribution on the spheres and f^* is a polynomial. Throughout this paper, we consider the scenario where the input dimension d is fixed.

Key facts. Cited by 28 papers in the map (data through 14 Oct 2026). First posted on arXiv 26 May 2019.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 8; 2022: 5; 2023: 3; 2024: 5; 2025: 5; 2026: 2.

28 papers.

Sort:

By area:

  1. 2021FedKD: Communication Efficient Federated Learning via Knowledge Distillationcited by 187
  2. 2023NTK-SAP: Improving neural network pruning by aligning training dynamicscited by 30
  3. 2021The Eigenlearning Framework: A Conservation Law Perspective on Kernel Regression and Wide Neural Networkscited by 26
  4. 2021Subquadratic Overparameterization for Shallow Neural Networkscited by 26
  5. 2021Spectral Analysis of the Neural Tangent Kernel for Deep Residual Networkscited by 21
  6. 2024Tuning Frequency Bias of State Space Modelscited by 17
  7. 2021On the Convergence of Shallow Neural Network Training with Randomly Masked Neuronscited by 11
  8. 2022Spectral Bias Outside the Training Set for Deep Networks in the Kernel Regimecited by 11
  9. 2024Finding Lottery Tickets in Vision Models via Data-driven Spectral Foresight Pruningcited by 10
  10. 2022Implicit Bias of MSE Gradient Optimization in Underparameterized Neural Networkscited by 9
  11. 2022Approximation results for Gradient Descent trained Shallow Neural Networks in 1dcited by 7
  12. 2022Synergy and Symmetry in Deep Learning: Interactions between the Data, Model, and Inference Algorithmcited by 6
16 more
  1. 2022Global Convergence of SGD On Two Layer Neural Netscited by 5
  2. 2021Universal scaling laws in the gradient descent training of neural networkscited by 4
  3. 2024Generalization Analysis of Online Stochastic Gradient Descent for Overparameterized Two-Layer Neural Networkscited by 4
  4. 2021One-pass Stochastic Gradient Descent in Overparametrized Two-layer Neural Networkscited by 3
  5. 2023Global Convergence of SGD For Logistic Loss on Two Layer Neural Netscited by 3
  6. 2025Optimal Rates for Generalization of Gradient Descent for Deep ReLU Classificationcited by 3
  7. 2023Approximation Results for Gradient Descent trained Neural Networkscited by 2
  8. 2024Gradient Descent Finds Over-Parameterized Neural Networks with Sharp Generalization for Nonparametric Regressioncited by 2
  9. 2024Approximation and Gradient Descent Training with Neural Networkscited by 1
  10. 2025Langevin Monte-Carlo Provably Learns Depth Two Neural Nets at Any Size and Datacited by 1
  11. 2025VQC-MLPNet: An Unconventional Hybrid Quantum-Classical Architecture for Scalable and Robust Quantum Machine Learningcited by 1
  12. 2021Dynamics of Local Elasticity During Training of Neural Netscited by 0
  13. 2025Optimizing Basis Function Selection in Constructive Wavelet Neural Networks and Its Applicationscited by 0
  14. 2025Shallow Neural Networks Learn Low-Degree Spherical Polynomials with Feature Learning by Learnable Channel Attentioncited by 0
  15. 2026Gradient Descent with Projection Finds Over-Parameterized Neural Networks for Learning Low-Degree Polynomials with Nearly Minimax Optimal Ratecited by 0
  16. 2026Optimal Rates for Generalization of Gradient Descent Methods with Deep Neural Networkscited by 0