TL;DR
This paper provides a theoretical breakthrough in understanding why Residual Networks (ResNets) are so effective. The authors prove that for a broad class of deep ResNets with arbitrary nonlinearities, there are no "bad" local minima; every local minimum is guaranteed to be at least as good as the global minimum of a corresponding classical machine-learning model, and depth actually serves to further improve this bound.
What Problem Does This Paper Address?
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 ResNets. However, Shamir’s proof was limited to networks with a single output unit (scalar output). Since most real-world tasks (like 10-class image classification) use multiple output units, a major question remained: Does this "no bad local minima" property hold for vector-valued outputs?
Methods
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 (e.g., 10 outputs for MNIST vs. 784 inputs).
Datasets
As a theoretical paper, it does not perform empirical experiments on specific datasets. However, the authors explicitly mention that their assumptions are satisfied by standard benchmarks like MNIST, CIFAR-10, and SVHN, where the number of classes (output units) is significantly smaller than the input dimensionality.
Key Insights and Ideas
- 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 is 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.
- Resolution of an Open Question: The paper provides a definitive "yes" to whether Shamir’s (2018) results extend to multi-output networks, which are the standard in deep learning practice.
Key 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.
Limitations and Future Work
- 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