# On Rademacher Complexity-based Generalization Bounds for Deep Learning

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

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 42 references that are in the map.
- First posted on arXiv 8 Aug 2022.

## Builds on (most cited first, 17 of 17)

- [Spectrally-normalized margin bounds for neural networks](https://mlsanity.com/paper/1706.08498/) (2017)
- [Computing Nonvacuous Generalization Bounds for Deep (Stochastic) Neural Networks with Many More Parameters than Training Data](https://mlsanity.com/paper/1703.11008/) (2017)
- [A PAC-Bayesian Approach to Spectrally-Normalized Margin Bounds for Neural Networks](https://mlsanity.com/paper/1707.09564/) (2017)
- [Information-theoretic analysis of generalization capability of learning algorithms](https://mlsanity.com/paper/1705.07809/) (2017)
- [Norm-Based Capacity Control in Neural Networks](https://mlsanity.com/paper/1503.00036/) (2015)
- [Size-Independent Sample Complexity of Neural Networks](https://mlsanity.com/paper/1712.06541/) (2017)
- [Uniform convergence may be unable to explain generalization in deep learning](https://mlsanity.com/paper/1902.04742/) (2019)
- [Non-Vacuous Generalization Bounds at the ImageNet Scale: A PAC-Bayesian Compression Approach](https://mlsanity.com/paper/1804.05862/) (2018)
- [Generalization Error Bounds Via R'enyi-, f-Divergences and Maximal Leakage](https://mlsanity.com/paper/1912.01439/) (2019)
- [Generalization Error in Deep Learning](https://mlsanity.com/paper/1808.01174/) (2018)
- [Differentiable PAC-Bayes Objectives with Partially Aggregated Neural Networks](https://mlsanity.com/paper/2006.12228/) (2020)
- [Estimating the Mixing Time of Ergodic Markov Chains](https://mlsanity.com/paper/1902.01224/) (2019)
- [Learning Theory and Algorithms for Revenue Optimization in Second-Price Auctions with Reserve](https://mlsanity.com/paper/1310.5665/) (2013)
- [A Multistep Lyapunov Approach for Finite-Time Analysis of Biased Stochastic Approximation](https://mlsanity.com/paper/1909.04299/) (2019)
- [Wide stochastic networks: Gaussian limit and PAC-Bayesian training](https://mlsanity.com/paper/2106.09798/) (2021)
- [Generalization Error Bounds on Deep Learning with Markov Datasets](https://mlsanity.com/paper/2201.11059/) (2021)
- [Generalization Bounds on Multi-Kernel Learning with Mixed Datasets](https://mlsanity.com/paper/2205.07313/) (2022)

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

- [How Does Information Bottleneck Help Deep Learning?](https://mlsanity.com/paper/2305.18887/) (2023)
- [Out-of-distributional risk bounds for neural operators with applications to the Helmholtz equation](https://mlsanity.com/paper/2301.11509/) (2023)
- [Sequence Length Independent Norm-Based Generalization Bounds for Transformers](https://mlsanity.com/paper/2310.13088/) (2023)
- [How DNNs break the Curse of Dimensionality: Compositionality and Symmetry Learning](https://mlsanity.com/paper/2407.05664/) (2024)
- [Global Convergence Rate of Deep Equilibrium Models with General Activations](https://mlsanity.com/paper/2302.05797/) (2023)
- [On Generalisation Error Bounds for Transformers](https://mlsanity.com/paper/2410.11500/) (2024)
- [Length independent generalization bounds for deep SSM architectures via Rademacher contraction and stability constraints](https://mlsanity.com/paper/2405.20278/) (2024)
- [On Discriminative Probabilistic Modeling for Self-Supervised Representation Learning](https://mlsanity.com/paper/2410.09156/) (2024)
- [Process-Guided Concept Bottleneck Model](https://mlsanity.com/paper/2601.10562/) (2026)
- [A Statistical Guarantee for Representation Transfer in Multitask Imitation Learning](https://mlsanity.com/paper/2311.01589/) (2023)
- [Multi-View Majority Vote Learning Algorithms: Direct Minimization of PAC-Bayesian Bounds](https://mlsanity.com/paper/2411.06276/) (2024)
- [Lossy Common Information in a Learnable Gray-Wyner Network](https://mlsanity.com/paper/2601.21424/) (2026)
- [Understanding Generalization from Embedding Dimension and Distributional Convergence](https://mlsanity.com/paper/2601.22756/) (2026)
- [Transfer Learning Through Conditional Quantile Matching](https://mlsanity.com/paper/2602.02358/) (2026)
- [PAC-Bayes Bounds for Gibbs Posteriors via Singular Learning Theory](https://mlsanity.com/paper/2604.17219/) (2026)
- [A Rigorous, Tractable Measure of Model Complexity](https://mlsanity.com/paper/2605.21167/) (2026)

## Abstract (arXiv)

We show that the Rademacher complexity-based framework can establish non-vacuous generalization bounds for Convolutional Neural Networks (CNNs) in the context of classifying a small set of image classes. A key technical advancement is the formulation of novel contraction lemmas for high-dimensional mappings between vector spaces, specifically designed for general Lipschitz activation functions. These lemmas extend and refine the Talagrand contraction lemma across a broader range of scenarios. Our Rademacher complexity bound provides an enhancement over the results presented by Golowich et al. for ReLU-based Deep Neural Networks (DNNs). Moreover, while previous works utilizing Rademacher complexity have primarily focused on ReLU DNNs, our results generalize to a wider class of activation functions.