Exponentially vanishing sub-optimal local minima in multilayer neural networks

By Daniel Soudry, Elad Hoffer. 2017

105 citations recorded by the source corpus.

Background: Statistical mechanics results (Dauphin et al. (2014); Choromanska et al. (2015)) suggest that local minima with high error are exponentially rare in high dimensions. However, to prove low error guarantees for Multilayer Neural Networks (MNNs), previous works so far required either a heavily modified MNN model or training method, strong assumptions on the labels (e.g., "near" linear separability), or an unrealistic hidden layer with $\Omega\left(N\right)$ units. Results: We examine a MNN with one hidden layer of piecewise linear units, a single output, and a quadratic loss. We prove that, with high probability in the limit of $N\rightarrow\infty$ datapoints, the volume of differentiable regions of the empiric loss containing sub-optimal differentiable local minima is exponentially vanishing in comparison with the same volume of global minima, given standard normal input of dimension $d_{0}=\tilde{\Omega}\left(\sqrt{N}\right)$, and a more realistic number of $d_{1}=\tilde{\Omega}\left(N/d_{0}\right)$ hidden units. We demonstrate our results numerically: for example, $0\%$ binary classification training error on CIFAR with only $N/d_{0}\approx 16$ hidden neurons.

Subfields: Artificial Intelligence, Statistical and Nonlinear Physics, Model Architectures, 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 Statistical and Nonlinear Physics

In Model Architectures

In Scaling & Learning Theory

Citations in the corpus

High-dimensional dynamics of generalization error in neural networks (2017, neutral): “7A), consistent with recent results on the error landscape of ReLU networks (Soudry and Hoffer, 2017).”
Train longer, generalize better: closing the generalization gap in large batch training of neural networks (2017, background): “It has been argued that saddle-points can be avoided (Ge et al., 2015) and that sub-optimal local minima in the training error vanish exponentially (Dauphin et al., 2014; Choromanska et al., 2015; Soudry & Hoffer, 2017).”
Visualizing the Loss Landscape of Neural Nets (2017, background): “Theoretical results usually make restrictive assumptions about the sample distributions, non-linearity of the architecture, or loss functions [16, 31, 40, 36, 9, 39].”
Theoretical Insights Into the Optimization Landscape of Over-Parameterized Shallow Neural Networks (2017, background): “Another recent paper [47] by Soudry and Hoffer suggests that “most” local minima are global in the over-parameterized regime.”
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 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.,…”
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.”
Exploring Model-based Planning with Policy Networks (2019, background): “On the other hand, we are inspired by the recent research into understanding deep neural networks [30, 24, 37].”
SGD Learns Over-parameterized Networks that Provably Generalize on Linearly Separable Data (2017, background): “By Theorem 8 in (Soudry & Hoﬀer, 2017) we immediately get the following.”
Fix your classifier: the marginal value of training the last weight layer (2018, background): “Moreover, many recent theoretical results related to neural network training (Soudry & Hoffer, 2017; Xie et al., 2016; Safran & Shamir, 2016; Soltanolkotabi et al., 2017; Soudry & Carmon, 2016) and even generalization (Gunasekar et al., 2017; Advani & Saxe, 2017; Wilson et al., 2017) usually assume…”
A Generalization Theory of Gradient Descent for Learning Over-parameterized Deep ReLU Networks (2019, background): “Soudry and Carmon (2016); Soudry and Hoffer (2017) explained why over-parametrization can remove bad local minima.”
Augment your batch: better training with larger batches (2019, background): “When our model is sufﬁciently rich and over-parameterized (e.g., deep networks), we typically converge to a minimum w ∗ which is a global minimum on all data points in the training set (Zhang et al., 2017; Soudry & Hoffer, 2017).”
On the Power of Over-parametrization in Neural Networks with Quadratic Activation (2018, background): “…Ge et al., 2017; Safran and Shamir, 2017; Soltanolkotabi et al., 2017; Poston et al., 1991; Haeffele and Vidal, 2015; Haeffele et al., 2014; Soudry and Hoffer, 2017) In particular, Haeffele and Vidal (2015); Poston et al. (1991); Nguyen and Hein (2017a;b)studied the effect of…”
Depth Creates No Bad Local Minima (2017, unknown): “Kawaguchi, 2016; Swirszcz et al., 2016; Arora et al., 2016; Freeman & Bruna, 2016; Soudry & Hoffer, 2017).”
Optimization Landscape and Expressivity of Deep CNNs (2017, unknown): “…have been recently developed (Andoni et al., 2014; Sedghi & Anandkumar, 2015; Janzamin et al., 2016; Gautier et al., 2016; Haeffele & Vidal, 2017; Soudry & Hoffer, 2017; Goel & Klivans, 2017; Li & Yuan, 2017; Zhong et al., 2017; Tian, 2017; Brutzkus & Globerson, 2017; Soltanolkotabi, 2017; Du et…”
The loss surface and expressivity of deep convolutional neural networks (2017, unknown): “…Sedghi & Anandkumar, 2015; Janzamin et al., 2016; Haeffele & Vidal, 2015; Gautier et al., 2016; Brutzkus & Globerson, 2017; Soltanolkotabi, 2017; Soudry & Hoffer, 2017; Goel & Klivans, 2017; Du et al., 2017; Zhong et al., 2017; Tian, 2017; Li & Yuan, 2017) in order to identify conditions under…”
On the Power and Limitations of Random Features for Understanding Neural Networks (2019, background): “, [30, 36, 37, 31, 10, 35]), or allows them to learn in various settings (e.”
The Loss Surface of Deep and Wide Neural Networks (2017, background): “On the theoretical side there have been several interesting developments recently, see e.g. (Brutzkus & Globerson, 2017; Lee et al., 2016; Poggio & Liao, 2017; Rister & Rubin, 2017; Soudry & Hoffer, 2017; Zhou & Feng, 2017).”
Universal statistics of Fisher information in deep neural networks: mean field approach (2018, background): “For instance, the loss landscape without spurious local minima is important for easier optimization and theoretically guaranteed in single-layer models [15], shallow piecewise linear ones [16], and extremely wide deep networks with the number of training samples smaller than the width [17].”
Implicit Self-Regularization in Deep Neural Networks: Evidence from Random Matrix Theory and Implications for Learning (2018, background): “(More recently, this fact seems to have been rediscovered [108, 37, 56, 135].”