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 minima 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.
Introduction
A central mystery in deep learning is why high-dimensional, non-convex optimization problems can be solved efficiently using simple gradient-based methods. To address this, researchers have historically turned to deep linear networks—models without nonlinear activation functions—as a simplified proxy. A landmark finding in this area is that deep linear networks possess a "clean" loss surface: every local minimum is also a global minimum.
However, the transition from linear to nonlinear models remains a theoretical hurdle. While practitioners have long suspected the existence of "spurious" (bad) local minima, proving their existence under realistic conditions has been difficult. Previous proofs often relied on restrictive assumptions, such as Gaussian input distributions or the requirement that the model be "realizable" (capable of achieving zero loss). This paper by Yun, Sra, and Jadbabaie (ICLR 2019) provides a rigorous reality check, demonstrating that even the slightest nonlinearity fundamentally alters the geometry of the loss surface, introducing traps that do not exist in the linear regime.
The Nonlinearity Trap
The authors focus on one-hidden-layer networks to show that complexity arises almost immediately upon the introduction of nonlinearity. They categorize their analysis into two primary types of activation functions: ReLU-like and smooth general activations.
1. ReLU-like Activations and the Linear Fit Trap
The authors define "ReLU-like" functions as those that are piecewise linear, non-negative, and homogeneous. For these networks, the paper presents a striking result: if a dataset cannot be perfectly fit by a simple linear model—a condition met by almost every real-world dataset—then a one-hidden-layer ReLU network will possess infinitely many spurious local minima.
Theorem 1 proves that the risk at these spurious minima is exactly equal to the risk of the best possible linear least-squares fit. Essentially, the optimizer becomes trapped in a state where the network "gives up" on its nonlinear expressive power and behaves like a simple linear regressor. Despite the existence of a superior nonlinear solution elsewhere in the weight space, the gradient-based optimizer cannot escape this linear-equivalent local minimum.
2. General Activations and Realizability
For smoother activations such as Sigmoid, Tanh, or ELU, the authors utilize Taylor series expansions to construct counterexamples. A common intuition in the field was that "easy to fit" problems (realizable datasets where zero loss is possible) might be easier to optimize.
Theorem 2 contradicts this intuition. The authors provide a constructive counterexample showing that for a wide range of activations, there exists a bad local minimum even on a realizable dataset. This suggests that realizability is not a shield against optimization traps; even when a perfect solution exists, the network can still be lured into a high-error local optimum.
Unifying Linear Theory
To provide a complete context for their findings, the authors also revisit deep linear networks. They present Theorem 4, which offers a comprehensive characterization of global optimality. By establishing necessary and sufficient conditions for a critical point to be a global minimum based on the rank of the weight matrices, they unify several disparate results in the literature. This serves to highlight exactly why linear networks are the exception: their unique algebraic structure prevents the formation of the spurious minima that appear the moment a "kink" or curve is added to the activation function.
Discussion and Implications
The core insight of this work is that the "no spurious local minima" property is a unique quirk of linear models. It is not a robust property that survives the transition to nonlinear neural networks.
Key Takeaways:
- Nonlinearity is the Source of Complexity: Even a tiny deviation from linearity creates a fundamentally different loss surface geometry.
- The Linear Baseline: In ReLU networks, bad local minima often represent the network failing to utilize its hidden layer effectively, reverting to a linear approximation of the data.
- Least Restrictive Assumptions: Unlike prior work, these results apply to almost all practical datasets and do not require specific data distributions.
Limitations and Future Directions
While this paper proves that bad local minima exist, it does not quantify how often optimization algorithms actually encounter them in practice. Modern deep learning often employs extreme over-parameterization—using networks with far more parameters than data points. Some researchers hypothesize that this over-parameterization "smooths" the landscape or creates higher-dimensional escape routes that make these minima less problematic.
Future research directions suggested by the authors include:
- Analyzing how the gap between local and global minima changes as network width or depth increases.
- Investigating the role of regularization (e.g., weight decay) in eliminating or mitigating these spurious minima.
- Studying the specific trajectories of Gradient Descent to determine if certain initialization schemes naturally avoid the traps identified in this paper.
Summary updated