Exponentially many local minima for single neurons

Peter Auer, Mark Herbster, Manfred K. WarmuthNeurIPS 1995 · OpenReview

TL;DR

Contrary to the intuition that single artificial neurons are simple and well-behaved, this paper proves that a single neuron using a logistic activation function and square loss can have a number of local minima that grows exponentially with the input dimension. However, the authors also demonstrate that this "nightmare" landscape disappears if you use a "matching loss" (such as entropic loss) or if the data is perfectly realizable by the neuron.

The Curse of Dimensionality in Single Neurons

In the mid-90s, the difficulty of training neural networks was often attributed to the complex, non-convex error surfaces of deep, multi-layer architectures. It was widely assumed that a single neuron—the most basic building block of these networks—was relatively immune to these issues.

This paper tackles a fundamental question: Can a single artificial neuron suffer from a "curse of dimensionality" regarding local minima? Specifically, the authors investigate how the choice of transfer function (like the sigmoid/logistic function) and loss function (like square loss) affects the number of traps a gradient descent algorithm might fall into.

A highly non-convex error surface demonstrating multiple local minima for a single neuron.

Theoretical Methods

Rather than relying on empirical simulations, the paper utilizes rigorous mathematical proofs to establish its claims. The key techniques include:

  • Minimum-Containing Sets: The authors define a topological tool to count minima. If one can find $n$ disjoint bounded sets where the error on the boundary is strictly greater than at some point inside, there are at least $n$ distinct local minima.
  • Saturation Construction: They exploit the "flat" regions of the logistic function (where the output is very close to 0 or 1). By placing training examples in these "saturated" regions, the error function becomes nearly flat, allowing the "bumps" created by other examples to manifest as independent local minima.
  • Additivity of Error: Since the total error is the sum of losses for each example, the authors show how to "nest" examples so that their individual minima don't cancel each other out. This effectively multiplies the number of minima as dimensions increase.

Because this is a theoretical paper, it does not use standard real-world datasets (like MNIST). Instead, the authors construct synthetic sequences of "non-realizable" training examples—meaning there is no single weight vector that can achieve zero error for all of them simultaneously.

Key Insights and Theorems

The Square Loss Trap and Exponential Complexity

Using square loss with a bounded transfer function like the sigmoid is mathematically dangerous. Because the sigmoid flattens out at its extremes, the square loss "saturates," creating flat regions where gradients vanish and local minima can easily hide.

By carefully arranging $n$ examples across $d$ dimensions, the authors prove that a single neuron can have an explosive number of local minima.

  • Theorem 3.4: For a neuron without bias, there exists a sequence of $n$ examples in $d$ dimensions that produces $\lfloor n/d \rfloor^d$ local minima under square loss.
  • Theorem 4.1: For a neuron with a bias term, the number of minima is at least $\lfloor n/2d \rfloor^d$.

This means that as you add features (dimensions), the potential for a training algorithm to get stuck grows exponentially.

The "Matching Loss" Cure

Fortunately, the authors derive a general framework for "matching" a loss function to a transfer function to guarantee a convex error surface (one with only a single global minimum). For any increasing transfer function, there exists a specific matching loss. For the logistic function, this matching loss is the entropic loss (cross-entropy). This theoretical foundation perfectly explains why cross-entropy is overwhelmingly preferred over square loss in modern classification tasks.

Realizability is a Safety Net

If the dataset is "realizable"—meaning a perfect solution exists where the error is zero—the spurious local minima vanish. The authors prove that if a weight vector $w_0$ exists such that $E(w_0) = 0$, then for any other weight vector $w_1$, the error monotonically increases as you move away from the solution, leaving no local traps.

Limitations and Practical Implications

While the proofs rely on specifically constructed, non-realizable examples, they highlight a critical structural vulnerability in neural network design. The authors acknowledge it remains an open question whether "natural" datasets encountered in the real world actually trigger this exponential growth of minima.

An error landscape showing a local minimum occurring even with moderate weight values.

Furthermore, while the mathematical construction sometimes requires very large input magnitudes or weights to force the neuron into saturation, the authors demonstrate that minima can still appear even with moderate values. Ultimately, while this paper provides a rigorous look at a single neuron, the interaction of these effects in multi-layer networks—where "realizability" is much harder to define—remains a complex area for broader research.

Summary updated

Abstract

We show that for a single neuron with the logistic function as the transfer function the number of local minima of the error function based on the square loss can grow exponentially in the dimension.
BibTeX
@inproceedings{auer1995exponentially,
  author = {Peter Auer and Mark Herbster and Manfred K. Warmuth},
  title = {{Exponentially many local minima for single neurons}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {1995},
  url = {https://openreview.net/forum?id=S1-DLwWdWr},
}

Loading related content...

Figure