# Generalization Guarantees via Algorithm-dependent Rademacher Complexity

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 31 references that are in the map.
- First posted on arXiv 4 Jul 2023.

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

- [Stronger generalization bounds for deep nets via a compression approach](https://mlsanity.com/paper/1802.05296/) (2018)
- [Information-theoretic analysis of generalization capability of learning algorithms](https://mlsanity.com/paper/1705.07809/) (2017)
- [Reasoning About Generalization via Conditional Mutual Information](https://mlsanity.com/paper/2001.09122/) (2020)
- [Preserving Statistical Validity in Adaptive Data Analysis](https://mlsanity.com/paper/1411.2664/) (2014)
- [Algorithmic Stability for Adaptive Data Analysis](https://mlsanity.com/paper/1511.02513/) (2015)
- [Intrinsic Dimension, Persistent Homology and Generalization in Neural Networks](https://mlsanity.com/paper/2111.13171/) (2021)
- [Hausdorff Dimension, Heavy Tails, and Generalization in Neural Networks](https://mlsanity.com/paper/2006.09313/) (2020)
- [Heavy Tails in SGD and Compressibility of Overparametrized Neural Networks](https://mlsanity.com/paper/2106.03795/) (2021)
- [Compression based bound for non-compressed network: unified generalization error analysis of large compressible deep neural network](https://mlsanity.com/paper/1909.11274/) (2019)
- [Generalization Bounds using Lower Tail Exponents in Stochastic Optimizers](https://mlsanity.com/paper/2108.00781/) (2021)
- [Hypothesis Set Stability and Generalization](https://mlsanity.com/paper/1904.04755/) (2019)
- [Fractal Structure and Generalization Properties of Stochastic Optimization Algorithms](https://mlsanity.com/paper/2106.04881/) (2021)
- [Rate-Distortion Theoretic Generalization Bounds for Stochastic Learning Algorithms](https://mlsanity.com/paper/2203.02474/) (2022)
- [Limitations of Information-Theoretic Generalization Bounds for Gradient Descent Methods in Stochastic Convex Optimization](https://mlsanity.com/paper/2212.13556/) (2022)
- [Generalization Bounds for Stochastic Gradient Descent via Localized varepsilon-Covers](https://mlsanity.com/paper/2209.08951/) (2022)

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

- [Uniform Generalization Bounds on Data-Dependent Hypothesis Sets via PAC-Bayesian Theory on Random Sets](https://mlsanity.com/paper/2404.17442/) (2024)
- [The Method of Gaps: Exact Expressions for the Generalization Error of Supervised Learning Algorithms](https://mlsanity.com/paper/2411.12030/) (2024)
- [Generalization Error Matters in Decentralized Learning Under Byzantine Attacks](https://mlsanity.com/paper/2407.08632/) (2024)
- [Stability, Complexity and Data-Dependent Worst-Case Generalization Bounds](https://mlsanity.com/paper/2507.06775/) (2025)

## Abstract (arXiv)

Algorithm- and data-dependent generalization bounds are required to explain the generalization behavior of modern machine learning algorithms. In this context, there exists information theoretic generalization bounds that involve (various forms of) mutual information, as well as bounds based on hypothesis set stability. We propose a conceptually related, but technically distinct complexity measure to control generalization error, which is the empirical Rademacher complexity of an algorithm- and data-dependent hypothesis class. Combining standard properties of Rademacher complexity with the convenient structure of this class, we are able to (i) obtain novel bounds based on the finite fractal dimension, which (a) extend previous fractal dimension-type bounds from continuous to finite hypothesis classes, and (b) avoid a mutual information term that was required in prior work; (ii) we greatly simplify the proof of a recent dimension-independent generalization bound for stochastic gradient descent; and (iii) we easily recover results for VC classes and compression schemes, similar to approaches based on conditional mutual information.