How Much Over-parameterization Is Sufficient to Learn Deep ReLU Networks?
Not on the map. Why?
Abstract (arXiv)
A recent line of research on deep learning focuses on the extremely over-parameterized setting, and shows that when the network width is larger than a high degree polynomial of the training sample size n and the inverse of the target error ε-1, deep neural networks learned by (stochastic) gradient descent enjoy nice optimization and generalization guarantees. Very recently, it is shown that under certain margin assumptions on the training data, a polylogarithmic width condition suffices for two-layer ReLU networks to converge and generalize (Ji and Telgarsky, 2019). However, whether deep neural networks can be learned with such a mild over-parameterization is still an open question. In this work, we answer this question affirmatively and establish sharper learning guarantees for deep ReLU networks trained by (stochastic) gradient descent. In specific, under certain assumptions made in previous work, our optimization and generalization guarantees hold with network width polylogarithmic in n and ε-1. Our results push the study of over-parameterized deep neural networks towards more practical settings.
Key facts. Cited by 84 papers in the map (data through 14 Oct 2026). First posted on arXiv 27 Nov 2019.
Builds on
No reference list yet.
Built on by
Citing papers per year: 2021: 26; 2022: 26; 2023: 10; 2024: 11; 2025: 6; 2026: 5.
84 papers.
Sort:
- 2021Toward Understanding the Feature Learning Process of Self-supervised Contrastive Learningcited by 119
- 2022Benign Overfitting in Two-layer Convolutional Neural Networkscited by 91
- 2022Understanding the Generalization Benefit of Normalization Layers: Sharpness Reductioncited by 86
- 2021Gradient Descent on Two-layer Nets: Margin Maximization and Simplicity Biascited by 83
- 2021Small random initialization is akin to spectral learning: Optimization and generalization guarantees for overparameterized low-rank matrix reconstructioncited by 78
- 2021Training Multi-Layer Over-Parametrized Neural Network in Subquadratic Timecited by 62
- 2021Exploring Memorization in Adversarial Trainingcited by 55
- 2021Understanding the Generalization of Adam in Learning Neural Networks with Proper Regularizationcited by 49
- 2021On the Proof of Global Convergence of Gradient Descent for Deep ReLU Networks with Linear Widthscited by 44
- 2022The Neural Covariance SDE: Shaped Infinite Depth-and-Width Networks at Initializationcited by 41
- 2023On the Optimization and Generalization of Multi-head Attentioncited by 37
- 2022Memorization and Optimization in Deep Neural Networks with Minimum Over-parameterizationcited by 36
38 more
- 2024Large Stepsize Gradient Descent for Logistic Loss: Non-Monotonicity of the Loss Improves Optimization Efficiencycited by 35
- 2021Early-stopped neural networks are consistentcited by 34
- 2021The Future is Log-Gaussian: ResNets and Their Infinite-Depth-and-Width Limit at Initializationcited by 33
- 2021Properties of the After Kernelcited by 27
- 2021Subquadratic Overparameterization for Shallow Neural Networkscited by 26
- 2023Mind the spikes: Benign overfitting of kernels and neural networks in fixed dimensioncited by 26
- 2023Generalization and Stability of Interpolating Neural Networks with Minimal Widthcited by 21
- 2021Reproducing Activation Function for Deep Learningcited by 19
- 2022Robustness in deep learning: The good (width), the bad (depth), and the ugly (initialization)cited by 18
- 2021Provable Generalization of SGD-trained Neural Networks of Any Width in the Presence of Adversarial Label Noisecited by 17
- 2022Learning Neural Contextual Bandits Through Perturbed Rewardscited by 17
- 2022Bounding the Width of Neural Networks via Coupled Initialization -- A Worst Case Analysiscited by 15
- 2021The Discovery of Dynamics via Linear Multistep Methods and Deep Learning: Error Estimationcited by 14
- 2021The Separation Capacity of Random Neural Networkscited by 14
- 2022Feature selection with gradient descent on two-layer networks in low-rotation regimescited by 14
- 2022Generalization Properties of NAS under Activation and Skip Connection Searchcited by 14
- 2024Differential Privacy Mechanisms in Neural Tangent Kernel Regressioncited by 14
- 2021Actor-critic is implicitly biased towards high entropy optimal policiescited by 13
- 2023On the Convergence of Encoder-only Shallow Transformerscited by 13
- 2021The Dynamics of Gradient Descent for Overparametrized Neural Networkscited by 11
- 2023Benign Overfitting in Deep Neural Networks under Lazy Trainingcited by 10
- 2021Stationary Density Estimation of Ito Diffusions Using Deep Learningcited by 9
- 2022Spectrally Adapted Physics-Informed Neural Networks for Solving Unbounded Domain Problemscited by 9
- 2022On the Omnipresence of Spurious Local Minima in Certain Neural Network Training Problemscited by 8
- 2022When Expressivity Meets Trainability: Fewer than n Neurons Can Workcited by 8
- 2024Understanding the training of infinitely deep and wide ResNets with Conditional Optimal Transportcited by 8
- 2022Approximation results for Gradient Descent trained Shallow Neural Networks in 1dcited by 7
- 2024Sharper Guarantees for Learning Neural Network Classifiers with Gradient Methodscited by 7
- 2021Deep Networks Provably Classify Data on Curvescited by 6
- 2021On the Provable Generalization of Recurrent Neural Networkscited by 6
- 2022Adversarial Robustness is at Odds with Lazy Trainingcited by 6
- 2022On the Convergence of Certified Robust Training with Interval Bound Propagationcited by 5
- 2022Global Convergence of SGD On Two Layer Neural Netscited by 5
- 2023Convergence beyond the over-parameterized regime using Rayleigh quotientscited by 5
- 2024Provably Neural Active Learning Succeeds via Prioritizing Perplexing Samplescited by 5
- 2021A Convergence Theory Towards Practical Over-parameterized Deep Neural Networkscited by 4
- 2021Generalization Performance of Empirical Risk Minimization on Over-parameterized Deep ReLU Netscited by 4
- 2022Deep Architecture Connectivity Matters for Its Convergence: A Fine-Grained Analysiscited by 4
50 most cited of 84 All 84 (JSON)
- 2026Geometric Dyson Brownian Motions and the Free Log-Normal Limit for a Non-Square Gaussian Matrix Product29 Jun 2026
- 2026Optimal Rates for Generalization of Gradient Descent Methods with Deep Neural Networks4 Jun 2026
- 2026On the global convergence of gradient flow for wide shallow models beyond homogeneous nonlinearities11 May 2026
- 2026Towards Initialization-dependent and Non-vacuous Generalization Bounds for Overparameterized Shallow Neural Networks1 Apr 2026
- 2026Optimization, Generalization and Differential Privacy Bounds for Gradient Descent on Kolmogorov-Arnold Networks29 Jan 2026
- 2025Optimal Rates for Generalization of Gradient Descent for Deep ReLU Classification3 Oct 2025
- 2025Gradient Flow Convergence Guarantee for General Neural Network Architectures28 Sep 2025
- 2025Data Uniformity Improves Training Efficiency and More, with a Convergence Framework Beyond the NTK Regime30 Jun 2025
- 2025Global Convergence and Rich Feature Learning in L-Layer Infinite-Width Neural Networks under μP Parametrization12 Mar 2025
- 2025Disentangling Feature Structure: A Mathematically Provable Two-Stage Training Dynamics in Transformers28 Feb 2025
- 2025Random Sparse Lifts: Construction, Analysis and Convergence of finite sparse networks10 Jan 2025
- 2024Understanding Transfer Learning via Mean-field Analysis22 Oct 2024
38 more
- 2024Sharper Guarantees for Learning Neural Network Classifiers with Gradient Methods13 Oct 2024
- 2024Component-based Sketching for Deep ReLU Nets21 Sep 2024
- 2024On the Convergence Analysis of Over-Parameterized Variational Autoencoders: A Neural Tangent Kernel Perspective9 Sep 2024
- 2024Differential Privacy Mechanisms in Neural Tangent Kernel Regression18 Jul 2024
- 2024Provably Neural Active Learning Succeeds via Prioritizing Perplexing Samples6 Jun 2024
- 2024Approximation and Gradient Descent Training with Neural Networks19 May 2024
- 2024Error Analysis of Three-Layer Neural Network Trained with PGD for Deep Ritz Method19 May 2024
- 2024Understanding the training of infinitely deep and wide ResNets with Conditional Optimal Transport19 Mar 2024
- 2024Large Stepsize Gradient Descent for Logistic Loss: Non-Monotonicity of the Loss Improves Optimization Efficiency24 Feb 2024
- 2024The effect of Leaky ReLUs on the training and generalization of overparameterized networks19 Feb 2024
- 2023On the Convergence of Encoder-only Shallow Transformers2 Nov 2023
- 2023On the Optimization and Generalization of Multi-head Attention19 Oct 2023
- 2023Fundamental Limits of Deep Learning-Based Binary Classifiers Trained with Hinge Loss13 Sep 2023
- 2023Approximation Results for Gradient Descent trained Neural Networks9 Sep 2023
- 2023On Achieving Optimal Adversarial Test Error13 Jun 2023
- 2023Benign Overfitting in Deep Neural Networks under Lazy Training30 May 2023
- 2023Mind the spikes: Benign overfitting of kernels and neural networks in fixed dimension23 May 2023
- 2023Generalization and Stability of Interpolating Neural Networks with Minimal Width18 Feb 2023
- 2023Convergence beyond the over-parameterized regime using Rayleigh quotients19 Jan 2023
- 2023Pruning Before Training May Improve Generalization, Provably1 Jan 2023
- 2022Improved Convergence Guarantees for Shallow Neural Networks5 Dec 2022
- 2022A Functional-Space Mean-Field Theory of Partially-Trained Three-Layer Neural Networks28 Oct 2022
- 2022When Expressivity Meets Trainability: Fewer than n Neurons Can Work21 Oct 2022
- 2022Global Convergence of SGD On Two Layer Neural Nets20 Oct 2022
- 2022Overparameterized ReLU Neural Networks Learn the Simplest Models: Neural Isometry and Exact Recovery30 Sep 2022
- 2022Approximation results for Gradient Descent trained Shallow Neural Networks in 1d17 Sep 2022
- 2022Robustness in deep learning: The good (width), the bad (depth), and the ugly (initialization)15 Sep 2022
- 2022Generalization Properties of NAS under Activation and Skip Connection Search15 Sep 2022
- 2022Feature selection with gradient descent on two-layer networks in low-rotation regimes4 Aug 2022
- 2022Informed Learning by Wide Neural Networks: Convergence, Generalization and Sampling Complexity2 Jul 2022
- 2022Bounding the Width of Neural Networks via Coupled Initialization -- A Worst Case Analysis26 Jun 2022
- 2022Adversarial Robustness is at Odds with Lazy Training18 Jun 2022
- 2022Understanding the Generalization Benefit of Normalization Layers: Sharpness Reduction14 Jun 2022
- 2022The Neural Covariance SDE: Shaped Infinite Depth-and-Width Networks at Initialization6 Jun 2022
- 2022Blind Estimation of a Doubly Selective OFDM Channel: A Deep Learning Algorithm and Theory30 May 2022
- 2022Memorization and Optimization in Deep Neural Networks with Minimum Over-parameterization20 May 2022
- 2022Deep Architecture Connectivity Matters for Its Convergence: A Fine-Grained Analysis11 May 2022
- 2022On the Convergence of Certified Robust Training with Interval Bound Propagation16 Mar 2022
50 newest of 84 All 84 (JSON)
- 2021Toward Understanding the Feature Learning Process of Self-supervised Contrastive Learningcited by 119
- 2022Benign Overfitting in Two-layer Convolutional Neural Networkscited by 91
- 2022Understanding the Generalization Benefit of Normalization Layers: Sharpness Reductioncited by 86
- 2021Gradient Descent on Two-layer Nets: Margin Maximization and Simplicity Biascited by 83
- 2021Small random initialization is akin to spectral learning: Optimization and generalization guarantees for overparameterized low-rank matrix reconstructioncited by 78
- 2021Training Multi-Layer Over-Parametrized Neural Network in Subquadratic Timecited by 62
- 2021Exploring Memorization in Adversarial Trainingcited by 55
- 2021Understanding the Generalization of Adam in Learning Neural Networks with Proper Regularizationcited by 49
- 2021On the Proof of Global Convergence of Gradient Descent for Deep ReLU Networks with Linear Widthscited by 44
- 2022The Neural Covariance SDE: Shaped Infinite Depth-and-Width Networks at Initializationcited by 41
- 2023On the Optimization and Generalization of Multi-head Attentioncited by 37
- 2022Memorization and Optimization in Deep Neural Networks with Minimum Over-parameterizationcited by 36
12 most cited of 84 All 84 (JSON)
- 2026Geometric Dyson Brownian Motions and the Free Log-Normal Limit for a Non-Square Gaussian Matrix Product29 Jun 2026
- 2026Optimal Rates for Generalization of Gradient Descent Methods with Deep Neural Networks4 Jun 2026
- 2026On the global convergence of gradient flow for wide shallow models beyond homogeneous nonlinearities11 May 2026
- 2026Towards Initialization-dependent and Non-vacuous Generalization Bounds for Overparameterized Shallow Neural Networks1 Apr 2026
- 2026Optimization, Generalization and Differential Privacy Bounds for Gradient Descent on Kolmogorov-Arnold Networks29 Jan 2026
- 2025Optimal Rates for Generalization of Gradient Descent for Deep ReLU Classification3 Oct 2025
- 2025Gradient Flow Convergence Guarantee for General Neural Network Architectures28 Sep 2025
- 2025Data Uniformity Improves Training Efficiency and More, with a Convergence Framework Beyond the NTK Regime30 Jun 2025
- 2025Global Convergence and Rich Feature Learning in L-Layer Infinite-Width Neural Networks under μP Parametrization12 Mar 2025
- 2025Disentangling Feature Structure: A Mathematically Provable Two-Stage Training Dynamics in Transformers28 Feb 2025
- 2025Random Sparse Lifts: Construction, Analysis and Convergence of finite sparse networks10 Jan 2025
- 2024Understanding Transfer Learning via Mean-field Analysis22 Oct 2024
12 newest of 84 All 84 (JSON)