Small nonlinearities in activation functions create bad local minima in neural networks

Chulhee Yun, Suvrit Sra, Ali Jadbabaie

In the realm of deep learning theory, researchers have long sought to understand why simple gradient descent is so remarkably effective at training highly complex, non-convex neural networks. For years, a prevailing source of optimism came from deep linear networks—models without nonlinear activation functions. In these idealized networks, local minima are frequently also global minima. If this property extended to real-world nonlinear networks, it would perfectly explain our empirical successes.

However, in their ICLR 2019 paper, Yun, Sra, and Jadbabaie deliver a sobering reality check. They mathematically prove that introducing even the "slightest" nonlinearity to a network is enough to create spurious (bad) local minima, trapping models far from the optimal solution.

The Core Problem: The Gap Between Linear Theory and Nonlinear Reality

When training a neural network, the goal is to find the absolute bottom of a "loss landscape." If a landscape is convex, any local low point is guaranteed to be the global minimum. While neural networks are inherently non-convex, theoretical work on deep linear networks showed that they often lack spurious local minima.

This led to a natural question: Does the "no spurious minima" property hold when we introduce standard nonlinearities like ReLU, sigmoid, or tanh? The authors address this gap, investigating whether the comforting insights derived from linear models are robust enough to apply to practical deep learning.

Methodology: Constructing the Traps

Rather than relying on empirical observation, the authors use rigorous mathematical analysis to constructively prove the existence of bad local minima. Their approach is divided into three main pillars:

  1. ReLU-like Analysis: The authors define a class of "ReLU-like" functions (piecewise linear, nonnegative, and homogeneous). They analyze these activations on generic, practical datasets—specifically, any dataset whose outputs cannot be perfectly represented as a linear combination of its inputs.
  2. General Activation Counterexamples: For smoother activations (such as sigmoid, tanh, and arctan), they design a specific, "realizable" synthetic dataset. Using just three data points—$X = \begin{bmatrix} 1 & 0 & 1/2 \\ 0 & 1 & 1/2 \end{bmatrix}$ and $Y = \begin{bmatrix} 0 & 0 & 1 \end{bmatrix}$—they prove that bad local minima exist even when a perfect zero-loss global minimum is possible.
  3. Linear Network Unification: To complete the theoretical picture, they provide a generalized theorem for deep linear networks that unifies disparate previous results, precisely defining when their local minima are global.

Key Findings and Theorems

The paper's mathematical constructions yield several striking results that fundamentally challenge how we view the loss surface:

  • Theorem 1 (The ReLU-like Trap): For a one-hidden-layer network with at least two hidden units, if the dataset is not perfectly linearly fittable, there exist infinitely many spurious local minima. The authors demonstrate how to "push" inputs to the positive side of a ReLU to make neurons act locally linear, creating stable but sub-optimal points.
  • Theorem 2 (General Activations): For networks using sigmoid, tanh, arctan, ELU, or SELU activations, there exists a dataset and architecture where the network gets stuck in a local minimum with a loss of $1/3$, despite the existence of a global minimum with a loss of $0$.
  • Theorem 4 (Linear Networks): In deep linear networks, the "type" of a critical point (minimum, maximum, or saddle) is directly inherited from the behavior of the underlying linear loss function, provided the hidden layers are sufficiently wide.

Insights and Implications

The most critical takeaway from this work is that nonlinearity is a trap creator. The "no spurious minima" property is a unique artifact of purely linear systems. Even a slight deviation into nonlinearity shatters this global optimality. Consequently, intuitions built upon linear networks are highly fragile and do not safely transfer to nonlinear realities.

Furthermore, the paper proves that "realizability" doesn't save you: even if your network is perfectly capable of modeling the true underlying data relationship, the loss landscape can still trap your optimizer.

Limitations and Future Directions

While theoretically rigorous, the paper's findings come with practical caveats that open doors for future research:

  • Network Depth: The formal proofs for nonlinear networks focus primarily on one-hidden-layer architectures. While the authors suspect these traps exist in deeper networks, it remains to be formally proven.
  • The "Sub-optimality Gap": The paper proves that bad local minima exist, but it does not quantify how bad they are on average. In practice, a spurious local minimum that is "close enough" to the global minimum might be perfectly acceptable for real-world tasks.
  • Regularization: The analysis explores the unregularized parameter space. Adding regularizers like weight decay fundamentally alters the loss landscape and may eliminate many of these spurious minima.
  • Optimization Trajectories: Proving that a bad minimum exists is different from proving that gradient descent will actually find it. Future work must investigate the probability of standard training trajectories falling into these mathematical traps.

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 minima in most cases. Our results thus indicate that in general "no spurious local minim" 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{yun2019small,
  author = {Chulhee Yun and Suvrit Sra and Ali Jadbabaie},
  title = {{Small nonlinearities in activation functions create bad local minima in neural networks}},
  booktitle = {International Conference on Learning Representations},
  year = {2019},
  url = {https://openreview.net/forum?id=Px_4W2sQ_6W},
}
Figure