Towards moderate overparameterization: global convergence guarantees for training shallow neural networks

Abstract

Many modern neural network architectures are trained in an overparameterized regime where the parameters of the model exceed the size of the training dataset. Sufficiently overparameterized neural network architectures in principle have the capacity to fit any set of labels including random noise. However, given the highly nonconvex nature of the training landscape it is not clear what level and kind of overparameterization is required for first order methods to converge to a global optima that perfectly interpolate any labels. A number of recent theoretical works have shown that for very wide neural networks where the number of hidden units is polynomially large in the size of the training data gradient descent starting from a random initialization does indeed converge to a global optima. However, in practice much more moderate levels of overparameterization seems to be sufficient and in many cases overparameterized models seem to perfectly interpolate the training data as soon as the number of parameters exceed the size of the training data by a constant factor. Thus there is a huge gap between the existing theoretical literature and practical experiments. In this paper we take a step towards closing this gap. Focusing on shallow neural nets and smooth activations, we show that (stochastic) gradient descent when initialized at random converges at a geometric rate to a nearby global optima as soon as the square-root of the number of network parameters exceeds the size of the training data. Our results also benefit from a fast convergence rate and continue to hold for non-differentiable activations such as Rectified Linear Units (ReLUs).

References in corpus (17)

• A Convergence Theory for Deep Learning via Over-Parameterization
• A Mean Field View of the Landscape of Two-Layers Neural Networks
• Learning Overparameterized Neural Networks via Stochastic Gradient Descent on Structured Data
• Stochastic Gradient Descent Optimizes Over-parameterized Deep ReLU Networks
• Spectrally-normalized margin bounds for neural networks
• Empirical Analysis of the Hessian of Over-Parametrized Neural Networks
• No bad local minima: Data independent training error guarantees for multilayer neural networks
• Spurious Local Minima are Common in Two-Layer ReLU Neural Networks
• Recovery Guarantees for One-hidden-layer Neural Networks
• On the Optimization of Deep Networks: Implicit Acceleration by Overparameterization
• Learning One-hidden-layer Neural Networks with Landscape Design
• To understand deep learning we need to understand kernel learning
• Does data interpolation contradict statistical optimality?
• Spurious Valleys in Two-layer Neural Network Optimization Landscapes
• On the Local Minima of the Empirical Risk
• The Landscape of Deep Learning Algorithms
• The Global Optimization Geometry of Shallow Linear Neural Networks

Cited by in corpus (49)

• Compressed Sensing with Deep Image Prior and Learned Regularization
• Generalization Bounds of Stochastic Gradient Descent for Wide and Deep Neural Networks
• Gradient Descent with Early Stopping is Provably Robust to Label Noise for Overparameterized Neural Networks
• Towards Understanding Ensemble, Knowledge Distillation and Self-Distillation in Deep Learning
• Optimization for deep learning: theory and algorithms
• Polylogarithmic width suffices for gradient descent to achieve arbitrarily small test error with shallow ReLU networks
• Towards Understanding the Spectral Bias of Deep Learning
• Algorithmic Guarantees for Inverse Imaging with Untrained Network Priors
• Denoising and Regularization via Exploiting the Structural Bias of Convolutional Generators
• Fast Convergence of Natural Gradient Descent for Overparameterized Neural Networks
• An Improved Analysis of Training Over-parameterized Deep Neural Networks
• A Generalized Neural Tangent Kernel Analysis for Two-layer Neural Networks
• How Much Over-parameterization Is Sufficient to Learn Deep ReLU Networks?
• On Learning Over-parameterized Neural Networks: A Functional Approximation Perspective
• Learning with invariances in random features and kernel models
• A Mean-field Analysis of Deep ResNet and Beyond: Towards Provable Optimization Via Overparameterization From Depth
• Compressive sensing with un-trained neural networks: Gradient descent finds the smoothest approximation
• Gradient Descent can Learn Less Over-parameterized Two-layer Neural Networks on Classification Problems
• Network size and weights size for memorization with two-layers neural networks
• Generalization error of random features and kernel methods: hypercontractivity and kernel matrix concentration
• Neural Networks Learning and Memorization with (almost) no Over-Parameterization
• A Corrective View of Neural Networks: Representation, Memorization and Learning
• Mildly Overparametrized Neural Nets can Memorize Training Data Efficiently
• Optimization Theory for ReLU Neural Networks Trained with Normalization Layers
• Memory capacity of neural networks with threshold and ReLU activations
• Path Length Bounds for Gradient Descent and Flow
• Decoupling Gating from Linearity
• Effect of Activation Functions on the Training of Overparametrized Neural Nets
• Revisiting Landscape Analysis in Deep Neural Networks: Eliminating Decreasing Paths to Infinity
• Learning Parities with Neural Networks
• Neural tangent kernels, transportation mappings, and universal approximation
• Early-stopped neural networks are consistent
• The Local Elasticity of Neural Networks
• Memorizing Gaussians with no over-parameterizaion via gradient decent on neural networks
• Hardness of Learning Neural Networks with Natural Weights
• Approximation power of random neural networks
• FL-NTK: A Neural Tangent Kernel-based Framework for Federated Learning Convergence Analysis
• A Deep Conditioning Treatment of Neural Networks
• Plateau Phenomenon in Gradient Descent Training of ReLU networks: Explanation, Quantification and Avoidance
• Global Convergence of Deep Networks with One Wide Layer Followed by Pyramidal Topology
• Active Subspace of Neural Networks: Structural Analysis and Universal Attacks
• Temporal-difference learning with nonlinear function approximation: lazy training and mean field regimes
• Learning Boolean Circuits with Neural Networks
• Achieving Small Test Error in Mildly Overparameterized Neural Networks
• SGD Through the Lens of Kolmogorov Complexity
• Minimum complexity interpolation in random features models
• A Modular Analysis of Provable Acceleration via Polyak's Momentum: Training a Wide ReLU Network and a Deep Linear Network
• Understanding Modern Techniques in Optimization: Frank-Wolfe, Nesterov's Momentum, and Polyak's Momentum
• Nearly Minimal Over-Parametrization of Shallow Neural Networks