How Much Over-parameterization Is Sufficient to Learn Deep ReLU Networks?
arXiv:1911.12360
Abstract
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 and the inverse of the target error , 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 and . Our results push the study of over-parameterized deep neural networks towards more practical settings.
arXiv comment21 pages, 1 figure, 1 table. In ICLR 2021
References in corpus (31)
- Reconciling modern machine learning practice and the bias-variance trade-off
- Neural Tangent Kernel: Convergence and Generalization in Neural Networks
- A Convergence Theory for Deep Learning via Over-Parameterization
- On Exact Computation with an Infinitely Wide Neural Net
- A PAC-Bayesian Approach to Spectrally-Normalized Margin Bounds for Neural Networks
- On Lazy Training in Differentiable Programming
- The generalization error of random features regression: Precise asymptotics and double descent curve
- Stochastic Gradient Descent Optimizes Over-parameterized Deep ReLU Networks
- Characterizing Implicit Bias in Terms of Optimization Geometry
- The loss surface of deep and wide neural networks
- Generalization Bounds of Stochastic Gradient Descent for Wide and Deep Neural Networks
- On the Power of Over-parametrization in Neural Networks with Quadratic Activation
- Spurious Local Minima are Common in Two-Layer ReLU Neural Networks
- On the Convergence Rate of Training Recurrent Neural Networks
- Global Optimality in Tensor Factorization, Deep Learning, and Beyond
- Towards moderate overparameterization: global convergence guarantees for training shallow neural networks
- Norm-Based Capacity Control in Neural Networks
- Polylogarithmic width suffices for gradient descent to achieve arbitrarily small test error with shallow ReLU networks
- Regularization Matters: Generalization and Optimization of Neural Nets v.s. their Induced Kernel
- Diverse Neural Network Learns True Target Functions
- Risk and parameter convergence of logistic regression
- Overparameterized Nonlinear Learning: Gradient Descent Takes the Shortest Path?
- Generalization Error Bounds of Gradient Descent for Learning Over-parameterized Deep ReLU Networks
- Global optimality conditions for deep neural networks
- Implicit Bias of Gradient Descent on Linear Convolutional Networks
- Critical Points of Neural Networks: Analytical Forms and Landscape Properties
- On the Power and Limitations of Random Features for Understanding Neural Networks
- Lexicographic and Depth-Sensitive Margins in Homogeneous and Non-Homogeneous Deep Models
- Gradient Descent can Learn Less Over-parameterized Two-layer Neural Networks on Classification Problems
- Over Parameterized Two-level Neural Networks Can Learn Near Optimal Feature Representations
- Algorithm-Dependent Generalization Bounds for Overparameterized Deep Residual Networks
Cited by in corpus (24)
- Towards Understanding the Spectral Bias of Deep Learning
- Two-Layer Neural Networks for Partial Differential Equations: Optimization and Generalization Theory
- On the Benefit of Width for Neural Networks: Disappearance of Bad Basins
- A Generalized Neural Tangent Kernel Analysis for Two-layer Neural Networks
- Deep learning versus kernel learning: an empirical study of loss landscape geometry and the time evolution of the Neural Tangent Kernel
- Recent advances in deep learning theory
- Gradient Descent can Learn Less Over-parameterized Two-layer Neural Networks on Classification Problems
- A Corrective View of Neural Networks: Representation, Memorization and Learning
- Reproducing Activation Function for Deep Learning
- On the Proof of Global Convergence of Gradient Descent for Deep ReLU Networks with Linear Widths
- Can Temporal-Difference and Q-Learning Learn Representation? A Mean-Field Theory
- The Discovery of Dynamics via Linear Multistep Methods and Deep Learning: Error Estimation
- Is deeper better? It depends on locality of relevant features
- Global Convergence of Deep Networks with One Wide Layer Followed by Pyramidal Topology
- Training Two-Layer ReLU Networks with Gradient Descent is Inconsistent
- The Dynamics of Gradient Descent for Overparametrized Neural Networks
- Label-Aware Neural Tangent Kernel: Toward Better Generalization and Local Elasticity
- On the Stability Properties and the Optimization Landscape of Training Problems with Squared Loss for Neural Networks and General Nonlinear Conic Approximation Schemes
- A Convergence Theory Towards Practical Over-parameterized Deep Neural Networks
- Actor-critic is implicitly biased towards high entropy optimal policies
- On the Provable Generalization of Recurrent Neural Networks
- Achieving Small Test Error in Mildly Overparameterized Neural Networks
- Training Linear Neural Networks: Non-Local Convergence and Complexity Results
- On Assessing the Quantum Advantage for MaxCut Provided by Quantum Neural Network Ansätze