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.
Introduction
The non-convexity of loss functions is a central challenge in deep learning theory. While neural networks achieve remarkable empirical success, their loss landscapes are typically riddled with "bad" local minima—points where optimization algorithms like gradient descent may get stuck despite the loss being far from the global optimum. Traditional approaches to addressing this issue involve massive over-parameterization or specific architectural constraints. This paper explores a simpler alternative: can a minimal architectural change guarantee a "good" landscape?
The Landscape Modification Trick
The authors propose a "landscape modification" strategy for binary classification. Given a standard neural network $f(x; \theta)$, a modified architecture $\tilde{f}$ is constructed by adding a single exponential neuron.
In the first variant (Figure 1a), the output is defined as: $$\tilde{f}(x; \tilde{\theta}) = f(x; \theta) + a \exp(w^\top x + b)$$ A quadratic regularizer ($\frac{\lambda a^2}{2}$) is applied to the weight $a$ of this new neuron. This modification, under mild assumptions, ensures that every local minimum is a global minimum.
Theoretical Foundations
The proof relies on two primary assumptions:
- Loss Function Properties: The loss function must be a "smooth hinge loss" (like polynomial hinge loss) that is monotonically non-decreasing and twice differentiable.
- Realizability: The dataset must be theoretically separable by the chosen architecture.
Using high-order Taylor expansions, the authors demonstrate that the gradient and higher-order derivatives of the exponential term effectively "push" the network out of suboptimal states. If the network is at a local minimum, the mathematical properties of the exponential neuron force the training error to zero.
Why the Exponential Neuron?
The choice of an exponential function is strategic. Because the derivative of an exponential is the function itself, the first-order optimality conditions (where the gradient is zero) become directly linked to the loss values. This link is what allows the proof to show that a zero gradient implies zero loss.
Key Results
The paper presents several significant findings regarding the optimization landscape:
- Theorem 1: For binary classification with smooth hinge loss, adding one exponential neuron via a skip connection to the output eliminates all bad local minima.
- Theorem 2: A similar result holds without a skip connection if one special neuron is added to every layer of a fully connected network (Figure 1b).
- Monomial Neurons: The exponential neuron can be substituted with a high-degree monomial neuron (e.g., $(w^\top x + b)^p$) if the degree $p$ is sufficiently large relative to the dataset size.
- Robustness to Noise: If the loss function is convex, the requirement for data realizability can be relaxed, meaning the landscape remains "good" even with noisy or random labels.
Discussion and Limitations
While these results are theoretically groundbreaking, they come with specific constraints. Currently, the proof is limited to binary classification; extending these guarantees to multi-class problems like ImageNet remains a significant open question. Additionally, the results depend on specific loss functions like the smooth hinge loss, rather than the more common Cross-Entropy or standard ReLU-based hinge loss.
Crucially, the authors prove that at every local minimum, the added neuron becomes inactive ($a=0$). This means the modification acts as "scaffolding" that helps the optimization process find a global minimum without actually changing the final function the network learns. However, while the paper proves that bad local minima are eliminated, it does not provide a bound on the convergence rate. The landscape might still contain plateaus or saddle points that could slow down training.
Conclusion
This work suggests that the gap between a "difficult" non-convex landscape and a "well-behaved" one is surprisingly small—just a single neuron. By providing a mathematical guarantee that "local is global," this research offers a new perspective on how architectural design can simplify the optimization hurdles of deep learning.
Summary updated