Spurious local minima in neural networks: a critical view

Chulhee Yun, Suvrit Sra, Ali Jadbabaie

Abstract

This paper investigates the loss surface of neural networks, providing a rigorous reality check on the common assumption that neural networks are easy to optimize because they lack spurious local minima. We prove that for one-hidden-layer networks with even the slightest nonlinearity, empirical risks possess spurious local minima in most practical scenarios. These findings suggest that the "no spurious local minima" property is largely restricted to deep linear networks and that insights derived from linear models may not be robust when applied to nonlinear architectures. For ReLU and ReLU-like networks, we constructively prove the existence of infinitely many local minima for almost all practical datasets. Furthermore, we provide counterexamples for general activations (sigmoid, tanh, arctan, etc.) where bad local minima exist even when a zero-loss global minimum is attainable. We conclude by presenting a unified characterization of global optimality for deep linear networks.

Introduction: The Mystery of Neural Optimization

A central paradox in deep learning is the success of simple gradient-based optimization on highly non-convex loss surfaces. In the late 1980s and again during the mid-2010s, theoretical breakthroughs showed that "deep linear networks"—networks without nonlinear activation functions—possess a remarkably friendly landscape: every local minimum is also a global minimum.

This "local is global" property led many to hope that the same logic applied to the nonlinear networks used in practice. However, previous proofs for nonlinear networks often relied on restrictive assumptions, such as Gaussian data distributions or the assumption of "realizability" (where the model can perfectly fit the labels). This research asks a fundamental question: Does the absence of spurious local minima actually hold for nonlinear networks under realistic conditions?

The Impact of Nonlinearity

The study demonstrates that the transition from a linear network to a nonlinear one is not a smooth evolution of the loss surface but a fundamental break. Even a tiny deviation from linearity—such as a Leaky-ReLU with a slope of $1+\epsilon$—is sufficient to create spurious local minima.

The authors employ a constructive mathematical approach to analyze the empirical risk (the loss surface on a specific dataset). Rather than merely proving a minimum exists, they identify the specific parameter values that create these traps. Their analysis covers three primary categories: ReLU-like activations, general smooth activations (Sigmoid, Tanh), and deep linear networks.

Key Findings

1. ReLU Networks and Infinite Traps

For ReLU and ReLU-like activations (piecewise linear, non-negative homogeneous functions), the paper presents a sobering result: if a dataset cannot be perfectly fit by a simple linear model—a condition true for almost all real-world data—a one-hidden-layer network with at least two hidden units will have spurious local minima.

Crucially, the authors show there are often infinitely many such minima. This phenomenon occurs because the homogeneity of the ReLU function allows for scaling the weights in ways that keep the output identical, creating entire manifolds of suboptimal points that can trap an optimizer.

2. The Myth of Realizability

A common intuition in the field is that if a network is large enough to reach zero error (the realizable case), the landscape becomes easier to navigate. This research provides a definitive counterexample. For a wide range of smooth activations (including Sigmoid, Tanh, and ELU), the authors prove the existence of bad local minima even on simple datasets where a zero-loss global minimum is guaranteed to exist. This suggests that "capacity" alone does not guarantee a clean optimization path.

3. Linear Networks as a Special Case

To complete the picture, the paper provides a unified theory for deep linear networks. It proves that in these specific models, the "type" of a critical point (whether it is a minimum, maximum, or saddle) is directly inherited from the behavior of the underlying linear model. This explains why linear networks are uniquely well-behaved and why they are poor proxies for understanding the optimization of nonlinear systems.

Conclusion and Future Directions

The results indicate that the "no spurious local minima" property is a fragile feature of linear models that vanishes with nonlinearity. While this provides a more pessimistic view of the neural loss surface, it also clarifies the gap between theory and practice.

Several questions remain for future exploration:

  • Depth and Width: While these results focus on one-hidden-layer networks, the interaction between depth and the "gap" between local and global minima in deeper architectures is still being mapped.
  • Optimization Trajectories: The existence of bad minima does not guarantee that algorithms like SGD will fall into them. The "volume" of the basins of attraction for global minima may still be significantly larger than those of spurious ones.
  • Regularization: In practice, techniques like weight decay (L2 regularization) may smooth out these spurious minima. Investigating the loss surface of regularized objectives is a logical next step for bridging this theoretical work with practical deep learning engineering.

Summary updated

Abstract

We investigate the loss surface of neural networks. We prove that even for one-hidden-layer networks with slightest nonlinearity, the empirical risks have spurious local in most cases. Our results thus indicate that in general no spurious local minima is a property limited to deep linear networks, and insights obtained from linear networks may not be robust. Specifically, for ReLU(-like) networks we constructively prove that for almost all practical datasets there exist infinitely many local minima. We also present a counterexample for more general activations (sigmoid, tanh, arctan, ReLU, etc.), for which there exists a bad local minimum. Our results make the least restrictive assumptions relative to existing results on spurious local optima in neural networks. We complete our discussion by presenting a comprehensive characterization of global optimality for deep linear networks, which unifies other results on this topic.
BibTeX
@inproceedings{yun2019spurious,
  author = {Chulhee Yun and Suvrit Sra and Ali Jadbabaie},
  title = {{Spurious local minima in neural networks: a critical view}},
  booktitle = {International Conference on Learning Representations},
  year = {2019},
  url = {https://openreview.net/forum?id=Px_4W2sQ_6W},
}
Figure