Toward Moderate Overparameterization: Global Convergence Guarantees for Training Shallow Neural Networks

By Samet Oymak, M. Soltanolkotabi. 2019

349 citations recorded by the source corpus.

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).

Subfields: Scaling & Learning Theory, 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 Scaling & Learning Theory

In Statistical Learning Theory

Citations in the corpus

Generalization Guarantees for Neural Networks via Harnessing the Low-rank Structure of the Jacobian (2019, methodology): “Proof The result on spectral norm and Lipschitzness of J (W ) have been proven in [48].”
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].”
Provable Continual Learning via Sketched Jacobian Approximations (2021, methodology): “The model is linear in the model parameter for all kernel methods, and is approximately linear for wide neural networks, as established by the recent theory on the neural tangent kernel (Jacot et al., 2018; Lee et al., 2018; Du et al., 2018; Oymak and Soltanolkotabi, 2020).”
Fast Convergence of Natural Gradient Descent for Overparameterized Neural Networks (2019, methodology): “Following Du et al. [2018b], Oymak and Soltanolkotabi [2019], Wu et al. [2019], we only optimize the weights of the ﬁrst layer 2 , i.e., θ = w .”
Over-parameterized Adversarial Training: An Analysis Overcoming the Curse of Dimensionality (2020, background): “…been a tremendous progress in understanding the "small training loss" phenomenon in standard (non-adversarial) training [Li and Liang, 2018, Du et al., 2019b, Allen-Zhu et al., 2019b,c, Du et al., 2019a, Arora et al., 2019b,a, Song and Yang, 2019, Zou et al., 2018, Oymak and Soltanolkotabi, 2019].”
Pixelated Butterfly: Simple and Efficient Sparse training for Neural Network Models (2021, methodology): “…used in analyzing overparameterized models’ convergence [Li and Liang, 2018, Du et al., 2019, AllenZhu et al., 2019b,c, Song and Yang, 2019], generalization [Allen-Zhu et al., 2019a], connection to data separability [Oymak and Soltanolkotabi, 2020], and cost per iteration [Brand et al., 2021]).”
Refined Generalization Analysis of Gradient Descent for Over-parameterized Two-layer Neural Networks with Smooth Activations on Classification Problems (2019, background): “[21] Samet Oymak and Mahdi Soltanolkotabi.”
Generalization of Two-layer Neural Networks: An Asymptotic Viewpoint (2020, background): “Previous works (e.g. Du et al. (2018); Oymak and Soltanolkotabi (2019)) have proved (non-asymptotically) that the two paths (145) and (146) are close if the model is overparameterized, i.e. h ∈ poly( n ) , under no assumptions on the teacher model.”
Loss landscapes and optimization in over-parameterized non-linear systems and neural networks (2020, background): “There has also been a rich literature that particularly focuses on the optimization of wide neural networks using gradient descent [33, 12, 11, 20, 3, 2, 17, 30], and SGD [1, 38], especially after the discovery of the constancy of neural tangent kernels (NTK) for certain neural networks [16].”
Towards Understanding the Spectral Bias of Deep Learning (2019, background): “As mentioned above, (Du et al., 2019b; Allen-Zhu et al., 2019; Du et al., 2019a; Zou et al., 2019; Oymak and Soltanolkotabi, 2019; Zou and Gu, 2019) proved the global convergence of (stochastic) gradient descent regardless of the target function, at the expense of requiring an extremely wide neural ”
Compressive sensing with un-trained neural networks: Gradient descent finds the smoothest approximation (2020, methodology): “This general strategy has been utilized in a number of recent publications [Sol+18; Du+18; Aro+19; OS19b; Oym+19; HS20].”
Gradient Descent with Early Stopping is Provably Robust to Label Noise for Overparameterized Neural Networks (2019, neutral): “[5] Samet Oymak and Mahdi Soltanolkotabi.”
An Improved Analysis of Training Over-parameterized Deep Neural Networks (2019, methodology): “Note that the dimension of the output is k = 1 in Du et al. (2018b,a); Wu et al. (2019); Oymak and Soltanolkotabi (2019).”
Global Guarantees for Enforcing Deep Generative Priors by Empirical Risk (2017, background): “Regarding theoretical motivation, recent papers have show that gradient methods for sufficiently overparameterized neural networks provably converge to a point of small or zero loss under various conditions on the training data [68]–[71].”