Theoretical Insights Into the Optimization Landscape of Over-Parameterized Shallow Neural Networks

By M. Soltanolkotabi, Adel Javanmard, Jason D. Lee. 2017

450 citations recorded by the source corpus.

In this paper, we study the problem of learning a shallow artificial neural network that best fits a training data set. We study this problem in the over-parameterized regime where the numbers of observations are fewer than the number of parameters in the model. We show that with the quadratic activations, the optimization landscape of training, such shallow neural networks, has certain favorable characteristics that allow globally optimal models to be found efficiently using a variety of local search heuristics. This result holds for an arbitrary training data of input/output pairs. For differentiable activation functions, we also show that gradient descent, when suitably initialized, converges at a linear rate to a globally optimal model. This result focuses on a realizable model where the inputs are chosen i.i.d. from a Gaussian distribution and the labels are generated according to planted weight coefficients.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition, Scaling & 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 Computer Vision and Pattern Recognition

In Scaling & Learning Theory

Citations in the corpus

Painless Stochastic Gradient: Interpolation, Line-Search, and Convergence Rates (2019, methodology): “important class of non-convex functions [16, 40, 44, 78, 79] satisfying the restricted secant inequality (RSI).”
Reconciling modern machine-learning practice and the classical bias–variance trade-off (2018, methodology): “There is a growing understanding that larger models are “easy” to optimize as local methods, such as SGD, converge to global minima of the training risk in over-parametrized regimes (e.g., [36]).”
Learning Overparameterized Neural Networks via Stochastic Gradient Descent on Structured Data (2018, background): “Moreover, most of the existing works trying to explain these phenomenons in general rely on unrealistic assumptions about the data distribution, such as Gaussian-ness and/or linear separability [32, 25, 10, 17, 7].”
Gradient Descent Provably Optimizes Over-parameterized Neural Networks (2018, background): “For other activation functions, some previous works showed the landscape does have the desired geometric properties (Du and Lee, 2018; Soltanolkotabi et al., 2018; Nguyen and Hein, 2017; Kawaguchi, 2016; Haeffele and Vidal, 2015; Andoni et al., 2014; Venturi et al., 2018; Yun et al., 2018a).”
Fast and Faster Convergence of SGD for Over-Parameterized Models and an Accelerated Perceptron (2018, background): “These include neural networks [18, 17, 35], matrix completion [36] and phase retrieval [6].”
Visualizing the Loss Landscape of Neural Nets (2017, background): “For restricted network classes, such as those with a single hidden layer, globally optimal or near-optimal solutions can be found by common optimization methods [35, 26, 38].”
Continual Learning in the Teacher-Student Setup: Impact of Task Similarity (2021, background): “, 1993; Engel & Van den Broeck, 2001; Zdeborová & Krzakala, 2016) and has recently experienced a surge of activity in the machine learning community (Zimmer et al., 2014; Zhong et al., 2017; Tian, 2017; Du et al., 2018; Soltanolkotabi et al., 2018; Aubin et al., 2018; Saxe et al., 2018; Baity-Jesi e”
Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks (2019, background): “Many papers tried to characterize geometric landscapes of objective functions (Safran & Shamir, 2017; Zhou & Liang, 2017; Freeman & Bruna, 2016; Hardt & Ma, 2016; Nguyen & Hein, 2017; Kawaguchi, 2016; Venturi et al., 2018; Soudry & Carmon, 2016; Du & Lee, 2018; Soltanolkotabi et al., 2018; Haeffele ”
Learning and Generalization in Overparameterized Neural Networks, Going Beyond Two Layers (2018, background): “1 What Can Neural Networks Provably Learn? Most existing works analyzing the learnability of neural networks [9, 12, 13, 20, 21, 28, 33, 34, 42, 43, 47, 49, 50, 56] make unrealistic assumptions about the data distribution (such as being random Gaussian), and/or make strong assumptions about the netw”
Gradient Descent Finds Global Minima of Deep Neural Networks (2018, background): “Many previous works thus try to study the optimization landscape of neural networks with different activation functions (Soudry & Hoffer, 2017; Safran & Shamir, 2018; 2016; Zhou & Liang, 2017; Freeman & Bruna, 2016; Hardt & Ma, 2016; Nguyen & Hein, 2017; Kawaguchi, 2016; Venturi et al., 2018; Soudry”
On the Global Convergence of Gradient Descent for Over-parameterized Models using Optimal Transport (2018, background): “It is known that in this context, Jm has less, or no, local minima in an over-parameterization regime and stochastic gradient descent (SGD) finds a global minimizer under restrictive assumptions [34, 35, 33, 23]; see [33] for an account of recent results.”
On the Convergence Rate of Training Recurrent Neural Networks (2018, methodology): “eural networks using more delicate algorithms—such as tensor decomposition [4, 13, 25, 43, 72] or tailored algorithm for the problem structure [3, 21, 80]— or design more special activation functions [2, 44, 47, 66]. In this paper, instead, we focus on why basic 2At a ﬁrst glance, one may question h”
On exponential convergence of SGD in non-convex over-parametrized learning (2018, background): “In particular, we note the recent work [11] which considers a class of neural networks that attain zero quadratic loss implying interpolation.”
Fast Neural Architecture Search of Compact Semantic Segmentation Models via Auxiliary Cells (2018, background): “Over-parameterisation is believed to be the primary reason behind the successes of deep learning models, and a few theoretical works have already addressed it in simplified cases [8, 37].”
Spurious Local Minima are Common in Two-Layer ReLU Neural Networks (2017, background): “(1), a few works have shown that there are no spurious local minima, or that gradient descent will succeed in reaching a global minimum, provided the v i vectors are in general position or orthogonal [Zhong et al., 2017, Soltanolkotabi et al., 2017, Tian, 2017].”
SGD Learns Over-parameterized Networks that Provably Generalize on Linearly Separable Data (2017, background): “Soltanolkotabi et al. (2017) analyze the optimization landscape of over-parameterized networks and give convergence guarantees for gradient descent to a global minimum when the data follows a Gaussian distribution and the activation functions are diﬀerentiable.”