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.
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.
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