# Generalization Error Bounds of Gradient Descent for Learning Over-parameterized Deep ReLU Networks

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

## Key facts

- Cited by 60 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 Feb 2019.

## Built on by (most cited first, 30 of 60)

- [Neural Networks can Learn Representations with Gradient Descent](https://mlsanity.com/paper/2206.15144/) (2022)
- [Understanding Emergent Abilities of Language Models from the Loss Perspective](https://mlsanity.com/paper/2403.15796/) (2024)
- [Pixelated Butterfly: Simple and Efficient Sparse training for Neural Network Models](https://mlsanity.com/paper/2112.00029/) (2021)
- [Benign Overfitting without Linearity: Neural Network Classifiers Trained by Gradient Descent for Noisy Linear Data](https://mlsanity.com/paper/2202.05928/) (2022)
- [Generalization Bounds using Lower Tail Exponents in Stochastic Optimizers](https://mlsanity.com/paper/2108.00781/) (2021)
- [Convergence of gradient descent for deep neural networks](https://mlsanity.com/paper/2203.16462/) (2022)
- [Proxy Convexity: A Unified Framework for the Analysis of Neural Networks Trained by Gradient Descent](https://mlsanity.com/paper/2106.13792/) (2021)
- [Generalization and Stability of Interpolating Neural Networks with Minimal Width](https://mlsanity.com/paper/2302.09235/) (2023)
- [Dropout-Based Rashomon Set Exploration for Efficient Predictive Multiplicity Estimation](https://mlsanity.com/paper/2402.00728/) (2024)
- [Provable Generalization of SGD-trained Neural Networks of Any Width in the Presence of Adversarial Label Noise](https://mlsanity.com/paper/2101.01152/) (2021)
- [Learning Neural Contextual Bandits Through Perturbed Rewards](https://mlsanity.com/paper/2201.09910/) (2022)
- [Curvature-Informed SGD via General Purpose Lie-Group Preconditioners](https://mlsanity.com/paper/2402.04553/) (2024)
- [A proof of convergence for gradient descent in the training of artificial neural networks for constant target functions](https://mlsanity.com/paper/2102.09924/) (2021)
- [The Separation Capacity of Random Neural Networks](https://mlsanity.com/paper/2108.00207/) (2021)
- [Understanding Square Loss in Training Overparametrized Neural Network Classifiers](https://mlsanity.com/paper/2112.03657/) (2021)
- [Quantifying Epistemic Uncertainty in Deep Learning](https://mlsanity.com/paper/2110.12122/) (2021)
- [Benign Overfitting in Deep Neural Networks under Lazy Training](https://mlsanity.com/paper/2305.19377/) (2023)
- [Efficient Uncertainty Quantification and Reduction for Over-Parameterized Neural Networks](https://mlsanity.com/paper/2306.05674/) (2023)
- [Differentially Private Non-convex Learning for Multi-layer Neural Networks](https://mlsanity.com/paper/2310.08425/) (2023)
- [On the Generalization Ability of Unsupervised Pretraining](https://mlsanity.com/paper/2403.06871/) (2024)
- [Soft Mode in the Dynamics of Over-realizable On-line Learning for Soft Committee Machines](https://mlsanity.com/paper/2104.14546/) (2021)
- [Can DPO Learn Diverse Human Values? A Theoretical Scaling Law](https://mlsanity.com/paper/2408.03459/) (2024)
- [Provably and Practically Efficient Neural Contextual Bandits](https://mlsanity.com/paper/2206.00099/) (2022)
- [Adversarial Robustness is at Odds with Lazy Training](https://mlsanity.com/paper/2207.00411/) (2022)
- [Random Smoothing Regularization in Kernel Gradient Descent Learning](https://mlsanity.com/paper/2305.03531/) (2023)
- [Test-Time Dynamic Image Fusion](https://mlsanity.com/paper/2411.02840/) (2024)
- [Provably Neural Active Learning Succeeds via Prioritizing Perplexing Samples](https://mlsanity.com/paper/2406.03944/) (2024)
- [Generalization Performance of Empirical Risk Minimization on Over-parameterized Deep ReLU Nets](https://mlsanity.com/paper/2111.14039/) (2021)
- [Homotopy Relaxation Training Algorithms for Infinite-Width Two-Layer ReLU Neural Networks](https://mlsanity.com/paper/2309.15244/) (2023)
- [An Improved Finite-time Analysis of Temporal Difference Learning with Deep Neural Networks](https://mlsanity.com/paper/2405.04017/) (2024)

## Abstract (arXiv)

Empirical studies show that gradient-based methods can learn deep neural networks (DNNs) with very good generalization performance in the over-parameterization regime, where DNNs can easily fit a random labeling of the training data. Very recently, a line of work explains in theory that with over-parameterization and proper random initialization, gradient-based methods can find the global minima of the training loss for DNNs. However, existing generalization error bounds are unable to explain the good generalization performance of over-parameterized DNNs. The major limitation of most existing generalization bounds is that they are based on uniform convergence and are independent of the training algorithm. In this work, we derive an algorithm-dependent generalization error bound for deep ReLU networks, and show that under certain assumptions on the data distribution, gradient descent (GD) with proper random initialization is able to train a sufficiently over-parameterized DNN to achieve arbitrarily small generalization error. Our work sheds light on explaining the good generalization performance of over-parameterized deep neural networks.