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

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

## Key facts

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

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

- [FedKD: Communication Efficient Federated Learning via Knowledge Distillation](https://mlsanity.com/paper/2108.13323/) (2021)
- [NTK-SAP: Improving neural network pruning by aligning training dynamics](https://mlsanity.com/paper/2304.02840/) (2023)
- [The Eigenlearning Framework: A Conservation Law Perspective on Kernel Regression and Wide Neural Networks](https://mlsanity.com/paper/2110.03922/) (2021)
- [Subquadratic Overparameterization for Shallow Neural Networks](https://mlsanity.com/paper/2111.01875/) (2021)
- [Spectral Analysis of the Neural Tangent Kernel for Deep Residual Networks](https://mlsanity.com/paper/2104.03093/) (2021)
- [Tuning Frequency Bias of State Space Models](https://mlsanity.com/paper/2410.02035/) (2024)
- [On the Convergence of Shallow Neural Network Training with Randomly Masked Neurons](https://mlsanity.com/paper/2112.02668/) (2021)
- [Spectral Bias Outside the Training Set for Deep Networks in the Kernel Regime](https://mlsanity.com/paper/2206.02927/) (2022)
- [Finding Lottery Tickets in Vision Models via Data-driven Spectral Foresight Pruning](https://mlsanity.com/paper/2406.01820/) (2024)
- [Implicit Bias of MSE Gradient Optimization in Underparameterized Neural Networks](https://mlsanity.com/paper/2201.04738/) (2022)
- [Approximation results for Gradient Descent trained Shallow Neural Networks in 1d](https://mlsanity.com/paper/2209.08399/) (2022)
- [Synergy and Symmetry in Deep Learning: Interactions between the Data, Model, and Inference Algorithm](https://mlsanity.com/paper/2207.04612/) (2022)
- [Global Convergence of SGD On Two Layer Neural Nets](https://mlsanity.com/paper/2210.11452/) (2022)
- [Universal scaling laws in the gradient descent training of neural networks](https://mlsanity.com/paper/2105.00507/) (2021)
- [Generalization Analysis of Online Stochastic Gradient Descent for Overparameterized Two-Layer Neural Networks](https://mlsanity.com/paper/2407.07670/) (2024)
- [One-pass Stochastic Gradient Descent in Overparametrized Two-layer Neural Networks](https://mlsanity.com/paper/2105.00262/) (2021)
- [Global Convergence of SGD For Logistic Loss on Two Layer Neural Nets](https://mlsanity.com/paper/2309.09258/) (2023)
- [Optimal Rates for Generalization of Gradient Descent for Deep ReLU Classification](https://mlsanity.com/paper/2510.02779/) (2025)
- [Approximation Results for Gradient Descent trained Neural Networks](https://mlsanity.com/paper/2309.04860/) (2023)
- [Gradient Descent Finds Over-Parameterized Neural Networks with Sharp Generalization for Nonparametric Regression](https://mlsanity.com/paper/2411.02904/) (2024)
- [Approximation and Gradient Descent Training with Neural Networks](https://mlsanity.com/paper/2405.11696/) (2024)
- [Langevin Monte-Carlo Provably Learns Depth Two Neural Nets at Any Size and Data](https://mlsanity.com/paper/2503.10428/) (2025)
- [VQC-MLPNet: An Unconventional Hybrid Quantum-Classical Architecture for Scalable and Robust Quantum Machine Learning](https://mlsanity.com/paper/2506.10275/) (2025)
- [Dynamics of Local Elasticity During Training of Neural Nets](https://mlsanity.com/paper/2111.01166/) (2021)
- [Optimizing Basis Function Selection in Constructive Wavelet Neural Networks and Its Applications](https://mlsanity.com/paper/2507.09213/) (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)
- [Optimal Rates for Generalization of Gradient Descent Methods with Deep Neural Networks](https://mlsanity.com/paper/2606.06764/) (2026)

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