A Critical View of Global Optimality in Deep Learning

Chulhee Yun, Suvrit Sra, Ali Jadbabaie

Abstract

We investigate the loss surface of neural networks, proving that even for one-hidden-layer networks with minimal nonlinearity, empirical risks frequently possess spurious local minima. Our results indicate that the "no spurious local minima" property is largely restricted to deep linear networks. For ReLU-like networks, we constructively prove the existence of infinitely many local minima for almost all practical datasets. We also provide counterexamples for general activations like sigmoid and tanh. These findings suggest that insights from linear networks regarding global optimality are not robust when applied to nonlinear architectures.

Introduction

A central mystery in deep learning is why simple gradient-based optimization algorithms, such as Stochastic Gradient Descent (SGD), consistently find high-quality solutions despite the non-convex nature of neural network loss surfaces. Historically, theoretical explanations have often relied on the study of deep linear networks. These models possess a convenient property: every local minimum is a global minimum.

However, the transition from linear to nonlinear models—the very essence of deep learning's power—remains theoretically fraught. Previous attempts to extend the "no bad local minima" guarantee to nonlinear networks often relied on restrictive assumptions, such as Gaussian input distributions or perfect realizability (where a "teacher" network generates the data). This paper critically examines these assumptions, demonstrating that even the slightest nonlinearity can introduce a proliferation of spurious local minima.

The Fragility of the Linear Guarantee

The authors demonstrate that the absence of bad local minima is a brittle property. By introducing even a "slight" nonlinearity, such as a Leaky-ReLU with nearly identical slopes (e.g., 1.0 and 1.001), the landscape changes fundamentally.

ReLU and Leaky-ReLU Networks

For networks using ReLU or Leaky-ReLU activations, the paper provides a constructive proof (Theorem 1). It shows that for any 1-hidden-layer network with at least two hidden units, if the dataset cannot be perfectly fitted by a linear model, the loss surface contains infinitely many spurious local minima. These minima are "bad" in a specific sense: their performance is no better than a simple linear least-squares model, yet they are stable points from which gradient descent cannot escape. Since almost all real-world datasets are non-linear, this implies that spurious minima are the rule rather than the exception in practical applications.

General Smooth Activations

The investigation extends to smooth activations like sigmoid, tanh, arctan, ELU, and SELU. The authors present a concrete counterexample using a simple three-point dataset ($X = [[1, 0, 1/2], [0, 1, 1/2]]$, $Y = [0, 0, 1]$). They prove that even when a global minimum with zero loss exists (the realizable case), these networks can become trapped in a local minimum with a significantly higher loss (e.g., a squared error of 1/3). This challenges the notion that the ability of a network to represent a function (expressivity) or the existence of a perfect solution (realizability) prevents the formation of bad local optima.

Methodology: Constructive Perturbation Analysis

The findings are derived through rigorous mathematical proof rather than empirical simulation. The authors employ two primary techniques:

  1. Weight Construction: They mathematically define specific parameter configurations that trap the network's hidden units in "locally linear" regimes.
  2. Perturbation Analysis: Using Taylor series expansions and directional derivatives, they demonstrate that any infinitesimal change to these weights results in a strict increase in loss. This confirms the points are true local minima rather than saddle points.

Unifying Deep Linear Theory

While the findings for nonlinear networks are sobering, the paper provides a comprehensive characterization of deep linear networks. The authors prove that in deep linear architectures, as long as the hidden layers are at least as wide as the input or output dimensions, the multilinear parameterization does not create new local minima. It only introduces saddle points. This result unifies and generalizes previous work, confirming that the "all local minima are global" property is a unique feature of the linear setting.

Implications and Limitations

These results suggest a significant gap between the theoretical properties of linear models and the practical reality of nonlinear deep learning. If bad local minima are ubiquitous, why does SGD work so well?

The authors suggest several avenues for future research:

  • Optimization Trajectories: While bad minima exist, the path taken by SGD might naturally avoid them. The existence of a trap does not mean the algorithm will necessarily fall into it.
  • Overparameterization: Modern networks are often much wider than the theoretical minimums studied here. Increasing the number of parameters may "smooth out" the landscape or create more paths to global minima.
  • Regularization: Techniques like weight decay or dropout, which were not considered in these proofs, may alter the loss surface to eliminate or mitigate the impact of spurious minima.

In conclusion, this work serves as a cautionary note for deep learning theory: the landscape of nonlinear networks is fundamentally more complex than that of their linear counterparts, and global optimality is not a guaranteed property of the architectures we use in practice.

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 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{yun2019critical,
  author = {Chulhee Yun and Suvrit Sra and Ali Jadbabaie},
  title = {{A Critical View of Global Optimality in Deep Learning}},
  booktitle = {International Conference on Learning Representations},
  year = {2019},
  url = {https://openreview.net/forum?id=Px_4W2sQ_6W},
}
Figure