Overparameterized Nonlinear Learning: Gradient Descent Takes the Shortest Path?

Abstract

Many modern learning tasks involve fitting nonlinear models to data which are trained in an overparameterized regime where the parameters of the model exceed the size of the training dataset. Due to this overparameterization, the training loss may have infinitely many global minima and it is critical to understand the properties of the solutions found by first-order optimization schemes such as (stochastic) gradient descent starting from different initializations. In this paper we demonstrate that when the loss has certain properties over a minimally small neighborhood of the initial point, first order methods such as (stochastic) gradient descent have a few intriguing properties: (1) the iterates converge at a geometric rate to a global optima even when the loss is nonconvex, (2) among all global optima of the loss the iterates converge to one with a near minimal distance to the initial point, (3) the iterates take a near direct route from the initial point to this global optima. As part of our proof technique, we introduce a new potential function which captures the precise tradeoff between the loss function and the distance to the initial point as the iterations progress. For Stochastic Gradient Descent (SGD), we develop novel martingale techniques that guarantee SGD never leaves a small neighborhood of the initialization, even with rather large learning rates. We demonstrate the utility of our general theory for a variety of problem domains spanning low-rank matrix recovery to neural network training. Underlying our analysis are novel insights that may have implications for training and generalization of more sophisticated learning problems including those involving deep neural network architectures.

Cited by in corpus (41)

• Compressed Sensing with Deep Image Prior and Learned Regularization
• Implicit Regularization in Deep Learning May Not Be Explainable by Norms
• Identity Crisis: Memorization and Generalization under Extreme Overparameterization
• The Impact of Neural Network Overparameterization on Gradient Confusion and Stochastic Gradient Descent
• Stochastic Mirror Descent on Overparameterized Nonlinear Models: Convergence, Implicit Regularization, and Generalization
• Gram-Gauss-Newton Method: Learning Overparameterized Neural Networks for Regression Problems
• How Much Over-parameterization Is Sufficient to Learn Deep ReLU Networks?
• Mathematical Models of Overparameterized Neural Networks
• 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
• Small random initialization is akin to spectral learning: Optimization and generalization guarantees for overparameterized low-rank matrix reconstruction
• Path Length Bounds for Gradient Descent and Flow
• Directional Pruning of Deep Neural Networks
• Understanding Overparameterization in Generative Adversarial Networks
• Learning Parities with Neural Networks
• Loss landscapes and optimization in over-parameterized non-linear systems and neural networks
• Learning a Single Neuron with Gradient Methods
• Label-Imbalanced and Group-Sensitive Classification under Overparameterization
• Information-Theoretic Generalization Bounds for Stochastic Gradient Descent
• Robust Recovery via Implicit Bias of Discrepant Learning Rates for Double Over-parameterization
• Memorizing Gaussians with no over-parameterizaion via gradient decent on neural networks
• Hardness of Learning Neural Networks with Natural Weights
• Implicit Regularization in ReLU Networks with the Square Loss
• Generalization Guarantees for Neural Architecture Search with Train-Validation Split
• Exploring Weight Importance and Hessian Bias in Model Pruning
• Multi-Point Bandit Algorithms for Nonstationary Online Nonconvex Optimization
• The Utility of Feature Reuse: Transfer Learning in Data-Starved Regimes
• Implicit Gradient Regularization
• Dimension-Free Bounds on Chasing Convex Functions
• Which Minimizer Does My Neural Network Converge To?
• The Dynamics of Gradient Descent for Overparametrized Neural Networks
• Subquadratic Overparameterization for Shallow Neural Networks
• Implicit Regularization in Tensor Factorization
• Effect of the initial configuration of weights on the training and function of artificial neural networks
• Linear Convergence of Generalized Mirror Descent with Time-Dependent Mirrors
• Layer-Wise Interpretation of Deep Neural Networks Using Identity Initialization
• Asymptotics of Ridge Regression in Convolutional Models
• Neurons learn slower than they think
• Training Linear Neural Networks: Non-Local Convergence and Complexity Results
• Invexifying Regularization of Non-Linear Least-Squares Problems
• Painless step size adaptation for SGD