Adding One Neuron Can Eliminate All Bad Local Minima

Shiyu Liang, Ruoyu Sun, Jason D. Lee, R. Srikant

Introduction

Training deep neural networks is notoriously difficult because their loss functions are highly non-convex. In theory, an optimizer could easily get stuck in a "bad" local minimum—a point where the loss is high, but any small change to the weights makes the loss worse. While empirical evidence suggests that modern architectures (like ResNets) often avoid these traps, theoretical proof has remained elusive. Previous proofs typically relied on highly restrictive assumptions, such as requiring the network to be linear, massively overparameterized, or trained on specific data distributions like Gaussian noise.

This paper introduces a general architectural "trick" to ensure a benign loss landscape for binary classification tasks. By adding just one "special" neuron (such as an exponential neuron) with a skip connection and a specific regularizer to any neural network, you can mathematically guarantee that the loss landscape has no bad local minima. Under mild assumptions, every local minimum becomes a global minimum, ensuring that if your optimizer converges, it has found an optimal solution.

The Architectural Modification

The authors propose a remarkably simple modification that can be applied to any existing neural network $f(x; \theta)$. The core method involves introducing an augmented "special" neuron, primarily focusing on an exponential neuron: $a \exp(w^\top x + b)$.

This neuron can be integrated into the network in two primary ways:

  1. The Skip Connection (Theorem 1): The special neuron is added as a skip connection routing directly from the input to the output.
  2. Per-Layer Addition (Theorem 2): Alternatively, one such special neuron is added to every hidden layer of a standard feedforward network.
Architectural modifications: (a) adding a single special neuron with a skip connection, and (b) adding one special neuron per layer.

To make the math work, the authors also add a quadratic regularizer specifically for the weight of this new neuron (e.g., $\frac{\lambda a^2}{2}$). The proofs assume the loss function is a "smooth hinge loss" (monotonically non-decreasing and twice differentiable) and that the dataset is "realizable"—meaning there exists some set of parameters within the hypothesis space that can classify the data perfectly.

Key Insights: The "Catalyst" Neuron

Perhaps the most surprising insight from the paper is that at every local minimum, the added neuron is actually inactive ($a=0$). It acts much like a chemical catalyst: it alters the "energy landscape" (the loss surface) to remove obstacles during training, but it does not actually change the final model's output or complexity once the minimum is reached.

The presence of the exponential neuron provides a "path" for the gradient to follow. If the original network is stuck in a sub-optimal spot, the exponential neuron's parameters can be adjusted to decrease the loss, effectively pulling the optimizer out of the local trap.

Crucially, this result is architecture-agnostic. It applies whether the base network is a CNN, a ResNet, or a simple MLP, and regardless of the activation functions (ReLU, Sigmoid, etc.) used in the rest of the network. This work also provides a rigorous theoretical motivation for skip connections, suggesting that bypassing complex layers can simplify the optimization landscape without needing to drastically increase the width of the entire network.

Theoretical Guarantees

Because this is a theoretical paper, it does not rely on empirical experiments on standard benchmarks like CIFAR or ImageNet. Instead, it provides mathematical proofs that hold for any dataset satisfying the realizability assumption.

  • No Bad Local Minima: For any neural network, adding one exponential neuron with a skip connection and a regularizer ensures that every local minimum is a global minimum achieving zero misclassification error.
  • Alternative Neurons: The "special" neuron does not strictly have to be exponential. A high-degree monomial neuron $(w^\top x + b)^p$ can also work, provided the degree $p$ is sufficiently high relative to the dataset.
  • Handling Noisy Labels: The authors relax the realizability assumption in Proposition 2. If the loss function is convex (like logistic loss), the "no bad local minima" property holds even if the data contains random or conflicting labels.

Limitations and Open Questions

While the theoretical guarantees are strong, the paper notes several limitations:

  • Optimization Speed: Proving that bad local minima do not exist is not the same as proving how fast an algorithm like Stochastic Gradient Descent (SGD) will find the global minimum. The landscape is "nice," but it could still feature extremely flat regions that slow down training.
  • Differentiability: The per-layer version of the proof (Theorem 2) requires the activation functions to be differentiable. This technically excludes the standard ReLU, though it applies to alternatives like Leaky ReLU or Swish.
  • Generalization: The paper focuses entirely on the training loss landscape. It does not address generalization—whether the model found at the global minimum will perform well on unseen data.
  • Scope: The current proofs are tailored specifically for binary classification. Extending this "one-neuron trick" to multi-class problems or regression remains an open challenge for future work.

Summary updated

Abstract

One of the main difficulties in analyzing neural networks is the non-convexity of the loss function which may have many bad local minima. In this paper, we study the landscape of neural networks for binary classification tasks. Under mild assumptions, we prove that after adding one special neuron with a skip connection to the output, or one special neuron per layer, every local minimum is a global minimum.
BibTeX
@inproceedings{liang2018adding,
  author = {Shiyu Liang and Ruoyu Sun and Jason D. Lee and R. Srikant},
  title = {{Adding One Neuron Can Eliminate All Bad Local Minima}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2018},
  url = {https://openreview.net/forum?id=BkEQmKWubH},
}
Figure