Algorithm-Dependent Generalization Bounds for Overparameterized Deep Residual Networks

Spencer Frei, Yuan Cao, Quanquan Gu

Abstract

The skip-connections used in residual networks (ResNets) have become a standard architecture choice in deep learning due to increased training stability and superior generalization performance. However, theoretical understanding of this improvement has remained limited. In this work, we analyze overparameterized deep residual networks trained by gradient descent following random initialization. We demonstrate that (i) the class of networks learned by gradient descent constitutes a small subset of the entire neural network function class, and (ii) this subclass is sufficiently large to guarantee small training error. By establishing these properties, we show that deep ResNets trained with gradient descent exhibit a small generalization gap. Notably, our optimization and generalization guarantees require overparameterization that is only logarithmic in the depth of the network ($O(\log L)$), whereas known bounds for non-residual networks require overparameterization that is at least polynomial in depth. This provides a rigorous theoretical explanation for why residual networks are preferable to non-residual ones in deep architectures.

Introduction

In modern deep learning, models are frequently "overparameterized," meaning they possess far more parameters than training examples. While classical statistical theory suggests such models should overfit by memorizing noise, empirical evidence shows they generalize remarkably well. This phenomenon is particularly pronounced in Deep Residual Networks (ResNets), where skip-connections allow for the training of hundreds or even thousands of layers.

Despite their success, theoretical explanations for ResNets often struggle to account for the impact of depth. For standard feedforward networks, mathematical bounds on generalization error typically explode as depth increases. This paper bridges the gap between theory and practice by providing "algorithm-dependent" bounds that analyze the specific trajectory of gradient descent, explaining why ResNets are uniquely suited for deep architectures.

Theoretical Framework and Methodology

The authors perform a rigorous mathematical analysis of fully connected deep ReLU residual networks. The networks are trained via gradient descent using Gaussian (He) initialization. The analysis is built upon four primary pillars:

  1. Algorithm-Dependent Analysis: Rather than analyzing the entire hypothesis space of all possible network weights, the authors focus on the specific subset of functions reachable by gradient descent from a random starting point.
  2. Surrogate Loss Analysis: By analyzing the cross-entropy loss through a surrogate error metric, the authors can effectively bound the actual classification error.
  3. Rademacher Complexity: This tool measures the "richness" of the function class. The proof demonstrates that the class of functions learned by gradient descent is restricted enough to generalize well, yet expressive enough to achieve zero training error.
  4. Semismoothness and Lipschitz Continuity: A critical component of the proof involves showing that the network's output remains stable during weight updates. Skip-connections are shown to maintain this stability, preventing the vanishing or exploding gradient problems common in plain networks.

The Logarithmic Advantage

The core finding of this research is the "Logarithmic Advantage." In standard non-residual networks, the required width ($m$) of the network to guarantee convergence and generalization typically grows polynomially ($O(L^a)$) or even exponentially with depth ($L$).

In contrast, this paper proves that for ResNets, the required width only needs to grow logarithmically with depth ($O(\log L)$). This is because skip-connections keep the Lipschitz constant of the network output under control. This stability ensures that the influence of early layers is preserved throughout the network, allowing the model to remain in a "lazy training" regime where weights stay close to their initial values, yet still learn complex patterns.

Key Results

Optimization Guarantee

The authors prove that gradient descent will find a solution with an empirical surrogate error of at most $\epsilon$ in $O(\text{poly}(\gamma^{-1}) \cdot \epsilon^{-1})$ steps with high probability. This ensures that the overparameterized ResNet can efficiently minimize training loss.

Generalization Bound

The derived bound on test error is expressed as: $$P(y \cdot f_W(x) < 0) \leq 2\mathcal{E}_S(W) + \text{Complexity Terms}$$

Crucially, the complexity terms reveal that the "generalization gap"—the difference between training and test performance—remains small even as the network becomes arbitrarily deep, provided the width meets the logarithmic requirement. This explains why increasing depth in ResNets often leads to better performance rather than the catastrophic divergence predicted by earlier non-residual theories.

Discussion and Limitations

While this work provides a landmark explanation for the success of ResNets, several avenues for future research remain:

  • Task Complexity: The current proof is limited to binary classification. Extending these bounds to multi-class problems is a necessary next step.
  • Architecture Scope: The analysis focuses on fully connected residual layers. While the insights are applicable to Convolutional Neural Networks (CNNs), a formal proof for convolutional architectures would involve additional complexity.
  • Feature Learning vs. Lazy Training: The analysis assumes the "lazy training" regime where weights stay near initialization. Some researchers argue that practical deep learning involves more significant weight movement (feature learning) than these bounds currently cover.
  • Scaling Parameters: The results depend on a specific scaling parameter ($\theta = 1/L$) for residual branches. Future work could explore how other scaling strategies, such as Fixup or ReZero, influence these theoretical bounds.

Conclusion

By demonstrating that ResNets require significantly less overparameterization to handle depth compared to standard networks, this paper provides a theoretical foundation for the "depth curse"-breaking capabilities of residual architectures. The logarithmic dependence on depth justifies the industry-wide shift toward ResNet-based models for complex, high-dimensional tasks.

Summary updated

Abstract

The skip-connections used in residual networks have become a standard architecture choice in deep learning due to the increased training stability and generalization performance with this architecture, although there has been limited theoretical understanding for this improvement. In this work, we analyze overparameterized deep residual networks trained by gradient descent following random initialization, and demonstrate that (i) the class of networks learned by gradient descent constitutes a small subset of the entire neural network function class, and (ii) this subclass of networks is sufficiently large to guarantee small training error. By showing (i) we are able to demonstrate that deep residual networks trained with gradient descent have a small generalization gap between training and test error, and together with (ii) this guarantees that the test error will be small. Our optimization and generalization guarantees require overparameterization that is only logarithmic in the depth of the network, while all known generalization bounds for deep non-residual networks have overparameterization requirements that are at least polynomial in the depth. This provides an explanation for why residual networks are preferable to non-residual ones.
BibTeX
@inproceedings{frei2019algorithm,
  author = {Spencer Frei and Yuan Cao and Quanquan Gu},
  title = {{Algorithm-Dependent Generalization Bounds for Overparameterized Deep Residual Networks}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2019},
  url = {https://openreview.net/forum?id=NFCEXfxFpw},
}
Figure