No bad local minima: Data independent training error guarantees for multilayer neural networks

By Daniel Soudry, Yair Carmon. 2016

244 citations recorded by the source corpus.

We use smoothed analysis techniques to provide guarantees on the training loss of Multilayer Neural Networks (MNNs) at differentiable local minima. Specifically, we examine MNNs with piecewise linear activation functions, quadratic loss and a single output, under mild over-parametrization. We prove that for a MNN with one hidden layer, the training error is zero at every differentiable local minimum, for almost every dataset and dropout-like noise realization. We then extend these results to the case of more than one hidden layer. Our theoretical guarantees assume essentially nothing on the training data, and are verified numerically. These results suggest why the highly non-convex loss of such MNNs can be easily optimized using local updates (e.g., stochastic gradient descent), as observed empirically.

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

In Scaling & Learning Theory

Citations in the corpus

Scaling description of generalization with number of parameters in deep learning (2019, background): “Numerical and theoretical studies [6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17] show that in the overparametrized regime, the loss landscape of DNNs is not rough with isolated minima as initially thought [18, 19], but instead has connected level sets and presents many flat directions, even near its g”
The jamming transition as a paradigm to understand the loss landscape of deep neural networks (2018, background): “[22] Daniel Soudry and Yair Carmon, “No bad local minima:”
A Convergence Theory for Deep Learning via Over-Parameterization (2018, background): “The result of Soudry and Carmon [52] shows that under over-parameterization and under random input perturbation, there is bad local minima for multi-layer neural networks.”
Learning Overparameterized Neural Networks via Stochastic Gradient Descent on Structured Data (2018, background): “There also exists a large body of work that analyzes the optimization landscape of learning neural networks [13, 26, 30, 10, 25, 29, 6, 32, 17, 5].”
On Large-Batch Training for Deep Learning: Generalization Gap and Sharp Minima (2016, background): “Finally, in Section 5 we briefly discuss the relationship between our results and theoretical work [9, 38, 40, 29].”
Gradient Descent Provably Optimizes Over-parameterized Neural Networks (2018, methodology): “For example, previous work (Soudry and Carmon, 2016) showed m ≥ nd is enough to make all differentiable local minima global.”
On the Optimization of Deep Networks: Implicit Acceleration by Overparameterization (2018, background): “…linear networks (see for example Kawaguchi (2016); Hardt & Ma (2016) or Baldi & Hornik (1989) for a classic account), or for speciﬁc non-linear networks under different restrictive assumptions ( cf. Choromanska et al. (2015); Haeffele & Vidal (2015); Soudry & Carmon (2016); Safran & Shamir (2017)).”
A Convergence Analysis of Gradient Descent for Deep Linear Neural Networks (2018, background): “While condition (i) does not always hold ( cf. Safran and Shamir (2018)), it has been established for various simple settings ( e.g. Soudry and Carmon (2016); Kawaguchi (2016)).”
Essentially No Barriers in Neural Network Energy Landscape (2018, background): “…and non-convex loss functions are few or based on strong assumptions such as the eigenvalues of the Hessian at critical points being random (Dauphin et al., 2014), linear activations (Choro-manska et al., 2014; Kawaguchi, 2016) or wide hidden layers (Soudry & Carmon, 2016; Nguyen & Hein, 2017).”
Identity Matters in Deep Learning (2016, methodology): “In analogy with residual networks, we will instead parameterize the objective function as min A1,...,A` E‖y − (I +A`) · · · (I +A1)x‖2 .”
Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks (2019, neutral): “…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; Haeﬀele & Vidal, 2015).”
Theoretical Insights Into the Optimization Landscape of Over-Parameterized Shallow Neural Networks (2017, background): “For a 2-layered network with leaky ReLU activation, [46] showed that gradient descent on a modified loss function can obtain a global minimum of the modified loss function; however, this does not imply reaching a global minimum of the original loss function.”
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): “…functions [Soudry and Hoffer, 2017, Safran and Shamir, 2018, 2016, Zhou and Liang, 2017, Freeman and Bruna, 2016, Hardt and Ma, 2016, Nguyen and Hein, 2017, Kawaguchi, 2016, Venturi et al., 2018, Soudry and Carmon, 2016, Du and Lee, 2018, Soltanolkotabi et al., 2018, Haeffele and Vidal, 2015].”
An Analytical Formula of Population Gradient for two-layered ReLU network and its Applications in Convergence and Critical Point Analysis (2017, background): “(Soudry & Carmon, 2016) shows the global optimality of the local minimum in a two-layered ReLU network, when independent multiplicative Bernoulli noise is applied to the activations.”
Topology and Geometry of Half-Rectified Network Optimization (2016, background): “…[2] and resolves the linear case by showing that no poor local minima exist; [14] which also discusses the impact of stochastic vs plain gradient, [17], that studies Empirical Risk Mini-mization for piecewise multilayer neural networks under overparametrization (which needs to grow with the…”
Recovery Guarantees for One-hidden-layer Neural Networks (2017, methodology): “(Soudry & Carmon, 2016) consider over-speciﬁed NNs, where the number of samples is smaller than the number of weights.”