Algorithm-Dependent Generalization Bounds for Overparameterized Deep Residual Networks

Spencer Frei, Yuan Cao, Quanquan Gu

Introduction

In modern deep learning, models are frequently "overparameterized"—meaning they possess vastly more parameters than there are training examples. From a classical statistical perspective, these models have the capacity to perfectly memorize noise, yet in practice, they generalize remarkably well to unseen data. While researchers have developed generalization bounds to explain this phenomenon, existing theories for standard fully connected networks face a major hurdle: as a network gets deeper, it becomes exponentially or polynomially harder to guarantee good generalization. The theoretical bounds simply explode with depth.

This paper provides a rigorous theoretical explanation for why Deep Residual Networks (ResNets)—which utilize "skip-connections"—avoid this pitfall. The authors prove that for ResNets, the amount of overparameterization (specifically, network width) required to guarantee good performance only needs to grow logarithmically with the depth of the network.

Theoretical Framework and Methodology

Rather than analyzing the properties of all possible neural networks, the authors perform an algorithm-dependent analysis. They focus specifically on the subset of network weights that Gradient Descent (GD) actually reaches when starting from a random Gaussian initialization.

Because this is a theoretical work, it does not rely on empirical benchmarks like ImageNet. Instead, it establishes a rigorous mathematical framework where data points are assumed to lie on a unit sphere and are drawn from a distribution that can be classified with a certain margin $\gamma$ by a function in a high-dimensional space (specifically, the "random kitchen sinks" function class).

To bridge the gap between training optimization and test-time classification accuracy, the authors analyze a surrogate error related to the cross-entropy loss. Their methodology relies on several key technical components:

  • Stability Analysis: They prove that during training, the network weights remain within a small "neighborhood" of their initial random values.
  • Scaling Factor: The analysis assumes a scaling parameter ($\theta = 1/L$) for the residual branches. This is a common theoretical technique to ensure the signal doesn't explode as it passes through many layers.
  • Rademacher Complexity: They bound the complexity of the function class reachable by GD to demonstrate that the "generalization gap" (the difference between training and test error) remains small.

Key Insights: Why ResNets Generalize

The paper highlights several mechanisms that allow ResNets to remain stable and effective at extreme depths:

  • The Logarithmic Advantage: The most significant breakthrough is showing that skip-connections allow the network's Lipschitz constant—a measure of how much the output changes relative to the input—to depend only logarithmically on depth. In non-residual networks, this dependence is usually polynomial or worse, necessitating massive widths to maintain stability.
  • Gradient Descent as a Regularizer: The analysis reinforces the concept of "algorithmic stability." Gradient descent doesn't just find any solution that fits the data; it finds a "simple" one near the starting point. This prevents the model from exploiting its massive capacity to overfit.
  • Feature Persistence: Skip-connections allow features learned in early layers to be passed directly to the end of the network. This mitigates the vanishing gradient problem and ensures the network doesn't have to re-learn representations at every single layer.

Main Results

The authors provide two primary guarantees for overparameterized ResNets trained by GD:

  1. Optimization Guarantee: GD will find a point with very low training error in a number of steps that is entirely independent of the network's depth.
  2. Generalization Guarantee: The learned ResNet will achieve a small test error, provided the width $m$ is at least $\tilde{O}(\text{poly}(\gamma^{-1}, \epsilon^{-1}))$. Crucially, the required width's dependence on the depth $L$ is only $\text{polylog}(L)$.

This represents a massive theoretical improvement over previous bounds for non-residual networks, which required the number of parameters to scale much more aggressively with depth to achieve similar guarantees.

Limitations and Future Work

While a significant step forward, the paper's theoretical framework has a few limitations that present opportunities for future research:

  • Binary Classification: The current proofs are limited to binary classification tasks. Extending these bounds to multi-class problems is a natural next step.
  • Specific Architecture: The analysis assumes a specific type of ResNet where the residual branch is scaled by a factor related to depth ($1/L$). Practical ResNets (like ResNet-50) typically use Batch Normalization instead of this explicit scaling.
  • Data Assumptions: The results rely on the data being "separable" by a specific class of functions. Understanding generalization on truly noisy, non-separable, or messy real-world data remains an open challenge in deep learning theory.

Summary updated

Abstract

The skip-connections used in residual networks have become a standard architecture choice in deep learning due to the increased generalization and stability of networks with this architecture, although there have been limited theoretical guarantees for this improved performance. 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, which helps explain why residual networks are preferable to fully connected 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