Is the Skip Connection Provable to Reform the Neural Network Loss Landscape?

Lifu Wang, Bo Shen, Ning Zhao, Zhiyuan ZhangIJCAI 2020 · DOI

TL;DR

This paper provides a theoretical explanation for why skip connections, a key component of modern deep neural networks like ResNets, improve performance. They prove that skip connections help to "flatten" the loss landscape, making it easier to find good solutions by ensuring that suboptimal local minima are not too "deep" and thus easier to escape.

What Problem Does This Paper Address?

Deep neural networks are incredibly powerful but notoriously difficult to train due to their non-convex loss landscapes, which are riddled with local minima and saddle points. While skip connections (as used in ResNets) have empirically proven to be highly effective, allowing for much deeper networks without performance degradation, the theoretical reasons behind their success have remained unclear. Specifically, it's been a challenge to prove whether these connections can eliminate or mitigate the impact of "bad" local minima that could lead to poor performance. This paper aims to bridge this gap by theoretically analyzing the loss landscape of deep ReLU networks with skip connections.

Methods

The authors build upon previous work that analyzed the loss landscape of two-layer ReLU networks by studying the "sub-level sets" of the loss function. A sub-level set $\Omega_F(\lambda) = \{\xi; F(\xi) \leq \lambda\}$ represents all parameter configurations $\xi$ where the loss $F(\xi)$ is below a certain threshold $\lambda$. The connectedness of these sub-level sets is a crucial property, as it implies that local minima are more likely to be global minima or easily escapable.

The core of their approach involves:

  • Comparing Network Architectures: They compare a standard two-layer ReLU network ($f_2(x) = W_2 \sigma(W_1 x)$) with a similar network augmented with a skip connection ($f_1(x) = W_2[\sigma(W_1 x) + V_1 g(\theta, V_2 \sigma(W_1 x))]$), where $g$ is a deep neural network with ReLU activations.
  • Theoretical Analysis of Sub-level Sets: They extend the analysis of sub-level set connectedness to deep ReLU networks with skip connections.
  • Defining and Bounding "Depth" of Local Minima: They introduce and analyze the "depth" of local minima, which quantifies how difficult it is to escape a local minimum. Their main theoretical contribution is a theorem that bounds this depth for local minima that are worse than the global minimum of the simpler two-layer network.
  • Constructing Paths: A key technique involves constructing continuous paths in the parameter space to demonstrate the connectedness of sub-level sets and to bound the loss along these paths.

Datasets

Not discussed in the paper. The analysis is theoretical and focuses on the properties of the loss function itself, rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • Skip Connections "Flatten" Bad Minima: The most significant insight is that skip connections provably reform the loss landscape by making "bad" local minima (those worse than the global minimum of a simpler two-layer network) very "shallow." This means they are easier to escape using gradient-based optimization methods.
  • Inheriting Good Properties: The skip connection network inherits the good properties of the simpler two-layer network's loss landscape, particularly regarding the connectedness of sub-level sets, especially when the network is over-parameterized (i.e., has many hidden units).
  • Theoretical Justification for ResNets: This work provides a theoretical foundation for why ResNets and similar architectures are so effective in practice, offering a principled explanation beyond empirical observations.
  • Depth of Local Minima: The "depth" of these suboptimal local minima is theoretically bounded by $O(m^{\eta-1})$, where $m$ is the number of hidden nodes in the first layer and $\eta < 1$. As $m$ grows (over-parameterization), this depth approaches zero, implying that such minima become insignificant.

Key Results

The main theoretical result is Theorem 1 (informal): For a suitable loss function and regularization, any strict local minimum of a deep ReLU network with a skip connection, if it is worse than a certain baseline (related to the global minimum of a two-layer network), has a depth of at most $O(m^{\eta-1})$. This implies that as the width of the network ($m$) increases, the loss landscape becomes increasingly well-behaved, with nearly all local minima being close to the global optimum.

Limitations and Future Work

  • Assumptions: The theoretical results rely on several assumptions, including the convexity of the loss function with respect to its output, the Lipschitz continuity of the loss function, and specific forms of regularization. The applicability to all real-world loss functions and regularization schemes might be limited.
  • Specific Architecture: The analysis focuses on a particular form of skip connection ($f_1(x) = W_2[\sigma(W_1 x) + V_1 g(\theta, V_2 \sigma(W_1 x))]$), which is similar to pre-activation ResNets. Generalizing to all possible skip connection implementations might require further work.
  • "Shallow" vs. "Non-existent": While the paper shows that bad local minima are "shallow," it doesn't necessarily prove their complete absence in all practical scenarios.
  • Future Work: The authors suggest that their work provides a step towards understanding the effectiveness of deep learning networks and that further theoretical analysis of loss landscapes is warranted. They also mention that their results can be extended to more general convex functions and multi-layer residual units.

Summary updated

BibTeX
@inproceedings{wang2020is,
  author = {Lifu Wang and Bo Shen and Ning Zhao and Zhiyuan Zhang},
  title = {{Is the Skip Connection Provable to Reform the Neural Network Loss Landscape?}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2020},
  doi = {10.24963/ijcai.2020/387},
}
Figure