Spurious Local Minima are Common in Two-Layer ReLU Neural Networks

By Itay Safran, Ohad Shamir. 2017

286 citations recorded by the source corpus.

We consider the optimization problem associated with training simple ReLU neural networks of the form $\mathbf{x}\mapsto \sum_{i=1}^{k}\max\{0,\mathbf{w}_i^\top \mathbf{x}\}$ with respect to the squared loss. We provide a computer-assisted proof that even if the input distribution is standard Gaussian, even if the dimension is arbitrarily large, and even if the target values are generated by such a network, with orthonormal parameter vectors, the problem can still have spurious local minima once $6\le k\le 20$. By a concentration of measure argument, this implies that in high input dimensions, \emph{nearly all} target networks of the relevant sizes lead to spurious local minima. Moreover, we conduct experiments which show that the probability of hitting such local minima is quite high, and increasing with the network size. On the positive side, mild over-parameterization appears to drastically reduce such local minima, indicating that an over-parameterization assumption is necessary to get a positive result in this setting.

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

In Optimization & Training

In Statistical Learning Theory

Citations in the corpus

A Convergence Theory for Deep Learning via Over-Parameterization (2018, background): “As a separate note, over-parameterization is suggested as the possible key to avoid bad local minima by Safran and Shamir [44] even for two-layer neural networks.”
Gradient Descent Provably Optimizes Over-parameterized Neural Networks (2018, methodology): “More recently, some negative results have also been discovered (Safran and Shamir, 2018; Yun et al., 2018a) and new procedures have been proposed to test local optimality and escape strict saddle points at non-differentiable points (Yun et al.”
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)).”
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; Haeﬀele…”
Gradient Descent Finds Global Minima of Deep Neural Networks (2018, background): “Ge et al., 2015, Lee et al., 2016, Du et al., 2017a] can ﬁnd a global minimum. Many previous works thus try to study the optimization landscape of neural networks with different activation functions [Safran and Shamir, 2018, 2016, Zhou and Liang, 2017, Freeman and Bruna, 2016, Hardt and Ma,2016,Nguy”
Stochastic Gradient Descent Optimizes Over-parameterized Deep ReLU Networks (2018, background): “…that over-parameterization and proper random initialization can help the optimization in training neural networks, and various theoretical results have been established (Safran and Shamir, 2017; Du and Lee, 2018; Arora et al., 2018a; Allen-Zhu et al., 2018c; Du et al., 2018b; Li and Liang, 2018).”
On the Convergence Rate of Training Recurrent Neural Networks (2018, background): “More recently, Safran and Shamir [43] provided evidence that, even when inputs are standard Gaus-sians, two-layer neural networks can indeed have spurious local minima, and suggested that over-parameterization (i.e., increasing the number of neurons) may be the key in avoiding spurious local minima.”
Algorithmic Regularization in Learning Deep Homogeneous Models: Layers are Automatically Balanced (2018, background): “…and Ma, 2016, Bartlett et al., 2018, Haeﬀele and Vidal, 2015, Freeman and Bruna, 2016, Vidal et al., 2017, Safran and Shamir, 2016, Zhou and Feng, 2017, Nguyen and Hein, 2017a,b, Zhou and Feng, 2017, Safran and Shamir, 2017], showing that the objective functions have properties (ii) and (iii).”
PAC Confidence Predictions for Deep Neural Network Classifiers (2020, background): “This phenomenon is most likely because DNNs are designed to overﬁt the training data ( e.g., to avoid local minima (Safran & Shamir, 2018)), which results in the predicted probabilities on the training data being very close to one for the correct prediction.”
Training Over-parameterized Deep ResNet Is almost as Easy as Training a Two-layer Network (2019, background): “In fact, Safran and Shamir [2017] have shown that spurious local minima are common in two-layer ReLU neural networks.”
Do We Actually Need Dense Over-Parameterization? In-Time Over-Parameterization in Sparse Training (2021, unknown): “Safran & Shamir, 2018; Soudry & Carmon, 2016; AllenZhu et al., 2019; Du et al., 2019; Zou et al., 2020; Zou & Gu, 2019).”
Toward Moderate Overparameterization: Global Convergence Guarantees for Training Shallow Neural Networks (2019, background): “However, a few publications [23], [24] demonstrate that the loss surface of nonlinear networks do indeed contains spurious local minima even when the input data are random and the labels are created according to a planted model.”
Understanding self-supervised Learning Dynamics without Contrastive Pairs (2021, background): “Many previous studies of deep learning dynamics made simplifying isotropic assumptions about data (Tian, 2017; Brutzkus & Globerson, 2017; Du et al., 2019; Bartlett et al., 2018; Safran & Shamir, 2018).”
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.”
Model Reconstruction from Model Explanations (2018, background): “non-trivial challenge en route to analyzing deeper non-linear models [11, 18, 21].”