# Algorithm-Dependent Generalization Bounds for Overparameterized Deep Residual Networks

arXiv: https://arxiv.org/abs/1910.02934 · HTML: https://mlsanity.com/paper/1910.02934/

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 Oct 2019.

## Built on by (most cited first, 16 of 16)

- [Deja Vu: Contextual Sparsity for Efficient LLMs at Inference Time](https://mlsanity.com/paper/2310.17157/) (2023)
- [Benign Overfitting without Linearity: Neural Network Classifiers Trained by Gradient Descent for Noisy Linear Data](https://mlsanity.com/paper/2202.05928/) (2022)
- [Implicit Bias in Leaky ReLU Networks Trained on High-Dimensional Data](https://mlsanity.com/paper/2210.07082/) (2022)
- [Overparameterization of deep ResNet: zero loss and mean-field analysis](https://mlsanity.com/paper/2105.14417/) (2021)
- [Proxy Convexity: A Unified Framework for the Analysis of Neural Networks Trained by Gradient Descent](https://mlsanity.com/paper/2106.13792/) (2021)
- [Implicit regularization of deep residual networks towards neural ODEs](https://mlsanity.com/paper/2309.01213/) (2023)
- [Provable Generalization of SGD-trained Neural Networks of Any Width in the Presence of Adversarial Label Noise](https://mlsanity.com/paper/2101.01152/) (2021)
- [Scaling Properties of Deep Residual Networks](https://mlsanity.com/paper/2105.12245/) (2021)
- [On the Global Convergence of Gradient Descent for multi-layer ResNets in the mean-field regime](https://mlsanity.com/paper/2110.02926/) (2021)
- [On the Convergence of Shallow Neural Network Training with Randomly Masked Neurons](https://mlsanity.com/paper/2112.02668/) (2021)
- [On the generalization of learning algorithms that do not converge](https://mlsanity.com/paper/2208.07951/) (2022)
- [Generalization Performance of Empirical Risk Minimization on Over-parameterized Deep ReLU Nets](https://mlsanity.com/paper/2111.14039/) (2021)
- [Asymptotic Analysis of Deep Residual Networks](https://mlsanity.com/paper/2212.08199/) (2022)
- [Generalization of Scaled Deep ResNets in the Mean-Field Regime](https://mlsanity.com/paper/2403.09889/) (2024)
- [Convergence Analysis of Deep Residual Networks](https://mlsanity.com/paper/2205.06571/) (2022)
- [Self-Regularity of Non-Negative Output Weights for Overparameterized Two-Layer Neural Networks](https://mlsanity.com/paper/2103.01887/) (2021)

## Abstract (arXiv)

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.