Abstract
In this paper, we prove that depth with nonlinearity creates no bad local minima in a type of arbitrarily deep ResNets with arbitrary nonlinear activation functions, in the sense that the values of all local minima are no worse than the global minimum value of corresponding classical machine-learning models, and are guaranteed to further improve via residual representations. As a result, this paper provides an affirmative answer to an open question stated in a paper in the conference on Neural Information Processing Systems 2018. This paper advances the optimization theory of deep learning only for ResNets and not for other network architectures.
Introduction
Training deep neural networks is notoriously difficult because it involves solving high-dimensional, non-convex optimization problems. Theoretically, such problems are often NP-hard, and there is a persistent fear that training might get stuck in "bad" local minima—points where the loss is high, but the optimizer cannot find a way down.
While previous research suggested that "every local minimum is a global minimum" under very restrictive conditions (like massive over-parameterization or simplified linear models), a 2018 paper by Ohad Shamir showed a more practical result for Residual Networks (ResNets). However, Shamir’s proof was limited to networks with a single output unit (scalar output). Since most real-world tasks, such as 10-class image classification, use multiple output units, a major question remained: Does this "no bad local minima" property hold for vector-valued outputs? This paper provides a definitive affirmative answer to this open question, demonstrating that depth with nonlinearity serves to eliminate bad local minima in a broad class of ResNets.
Methodology
The authors analyze a specific type of deep ResNet where the final output is represented as:
$$h(x, W, V, \theta) = W(x + Vz(x, \theta))$$
In this model, $x$ is the input, $W$ and $V$ are trainable weight matrices, and $z(x, \theta)$ represents an arbitrarily deep residual branch that can include non-differentiable nonlinearities like ReLUs.
The key mathematical approach involves using first-order necessary conditions for local minima. By analyzing the gradients with respect to $W$ and $V$, the authors show that at any local minimum, the network effectively induces a globally optimal predictor for a specific basis-function model. Unlike previous work, this paper does not require the loss function to be twice-differentiable or the network to have only one output. It only assumes that the output dimension is smaller than or equal to the input and residual dimensions ($d_y \le \min(d_x, d_z)$), a condition easily met in most classification tasks. For instance, standard benchmarks like MNIST, CIFAR-10, and SVHN satisfy this, as the number of classes (output units) is significantly smaller than the input dimensionality.
Key Insights and Theoretical Contributions
- The "Deepening" Map: The paper views a ResNet as a "deepened" version of a classical basis-function model. They show that this deepening process is "safe"—it doesn't introduce new, poor local minima that didn't exist in the simpler model.
- The Further Improvement Term: One of the most significant contributions is the quantification of the "residual representation." They prove that the loss at a local minimum is not just "not bad," but is exactly equal to the global minimum of a model that uses both the raw inputs and the features learned by the deep residual branch.
- Nonlinearity as an Advantage: While nonlinearities usually make optimization harder to analyze, here they are shown to be the mechanism that allows the network to capture complex patterns that a linear model would miss, directly lowering the value of the local minima.
Main Results
The main result is summarized in Theorem 1, which states that at any local minimum, the loss $L$ satisfies:
$$L(W, V, \theta) = L^*_{\{x\}} - \text{Improvement Term}$$
Where $L^*_{\{x\}}$ is the global minimum of a standard linear model.
In Theorem 2, they specialize this for squared loss, showing that the improvement is the (averaged) norm of the target data projected onto the space captured by the residual branch $z(x, \theta)$. This proves that as long as the residual branch learns anything useful that isn't already in the raw input, the local minima of the deep ResNet will be strictly better than the global minimum of a shallow model.
Discussion and Limitations
While this paper provides a theoretical breakthrough in understanding ResNet effectiveness, several constraints remain:
- Dimensionality Constraint: The proof relies on the assumption that the output dimension $d_y$ is not larger than the input or residual dimensions. While common, there are cases (like some autoencoders or high-dimensional regression) where this might not hold.
- Unconstrained Weights: The matrix $V$ is assumed to be a fully trainable, unconstrained matrix. In practice, $V$ often represents a convolutional layer, which has a specific sparse structure. Extending these proofs to include structural constraints like convolutions remains a challenge.
- Global Convergence: While the paper proves local minima are "good," it doesn't strictly prove that gradient descent will always reach one in polynomial time, though it removes one of the biggest theoretical hurdles—the existence of bad traps.
Summary updated