Overparameterized Nonlinear Learning: Gradient Descent Takes the Shortest Path?

By Samet Oymak, M. Soltanolkotabi. 2018

200 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computational Mechanics, Optimization & Training, Statistical Learning Theory

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

In Optimization & Training

In Statistical Learning Theory

Citations in the corpus

On Lazy Training in Differentiable Programming (2018, background): “Other works in this line of research have appeared since the first version of this article was communicated, studying the optimization and statistical properties of various neural networks architectures in what we refer to as the lazy regime [5, 33, 32, 29, 46, 8, 27, 16, 4, 43].”
Stochastic Mirror Descent on Overparameterized Nonlinear Models (2019, methodology): “Denoting the initialization by w 0 , Oymak & Soltanolkotabi (2019) showed that for SGD, w ∞ − w 0 (cid:107) is bounded by a constant factor of (cid:107) w ∗ − w 0 (cid:107) .”
Over Parameterized Two-level Neural Networks Can Learn Near Optimal Feature Representations (2019, background): “…can be regarded as a linear model with infinite dimensional feature (Jacot et al., 2018; Li & Liang, 2018; Du et al., 2019a; Arora et al., 2019; Du et al., 2019b; Allen-Zhu et al., 2018; Allen-Zhu & Li, 2019; Allen-Zhu et al., 2019; Du et al., 2019a; Zou et al., 2018; Oymak & Soltanolkotabi, 2018).”
Gradient Descent with Early Stopping is Provably Robust to Label Noise for Overparameterized Neural Networks (2019, background): “We would also like to note that the importance of the Jacobian for overparameterized neural network analysis has also been noted by other papers including [21, 39, 49] and also [16, 30] which investigate the optimization landscape and properties of SGD for training neural networks.”
A type of generalization error induced by initialization in deep neural networks (2019, methodology): “Oymak & Soltanolkotabi (2018), Jacot et al. (2018) show that in an over-parameterized regime, the convergence point in the parameter space of a DNN remains close to the initialization.”
CLUB: A Contrastive Log-ratio Upper Bound of Mutual Information (2020, methodology): “…the network capacity ( i.e. , adding layers and neurons) and applying gradient-ascent to the log-likelihood L ( θ ) , we can obtain far more accurate approximation q θ ( y | x ) to p ( y | x ) , thanks to the high expressiveness of neural networks (Hu et al., 2019; Oymak & Soltanolkotabi, 2019).”
Training Over-parameterized Deep ResNet Is almost as Easy as Training a Two-layer Network (2019, background): “Oymak and Soltanolkotabi [2018], Fu et al. [2018], Zhou and Liang [2017] study the local geometry of neural networks that are responsible for the behavior of gradient descent.”
Implicit Regularization in Deep Learning May Not Be Explainable by Norms (2020, background): “Works along this line have treated: linear (single-layer) predictors ([67, 31, 40, 2]); normalized linear models ([71]); certain polynomially parameterized linear models ([70]); homogeneous (and sum of homogeneous) models ([53, 49]); ultra-wide neural networks ([38, 51, 14, 58]); linear neural netwo”
Refined Generalization Analysis of Gradient Descent for Over-parameterized Two-layer Neural Networks with Smooth Activations on Classification Problems (2019, methodology): “[35] Samet Oymak and Mahdi Soltanolkotabi.”
Loss landscapes and optimization in over-parameterized non-linear systems and neural networks (2020, background): “The paper [4] proved fast convergence of stochastic gradient descent with constant step size for over-parameterized models, while [29] reﬁned this result showing SGD convergence within a ball with a certain radius.”
Toward Moderate Overparameterization: Global Convergence Guarantees for Training Shallow Neural Networks (2019, methodology): “2) To prove this theorem we will utilize a result from [10] stated below.”