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