# Hypothesis Set Stability and Generalization

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

## Key facts

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

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

- [Topology-aware Generalization of Decentralized SGD](https://mlsanity.com/paper/2206.12680/) (2022)
- [Stability and Generalization of Stochastic Gradient Methods for Minimax Problems](https://mlsanity.com/paper/2105.03793/) (2021)
- [Churn Reduction via Distillation](https://mlsanity.com/paper/2106.02654/) (2021)
- [Generalization Bounds with Data-dependent Fractal Dimensions](https://mlsanity.com/paper/2302.02766/) (2023)
- [Uniform Generalization Bounds on Data-Dependent Hypothesis Sets via PAC-Bayesian Theory on Random Sets](https://mlsanity.com/paper/2404.17442/) (2024)
- [Exploring the Algorithm-Dependent Generalization of AUPRC Optimization with List Stability](https://mlsanity.com/paper/2209.13262/) (2022)
- [Sample-Conditioned Hypothesis Stability Sharpens Information-Theoretic Generalization Bounds](https://mlsanity.com/paper/2310.20102/) (2023)
- [Generalization Properties of Retrieval-based Models](https://mlsanity.com/paper/2210.02617/) (2022)
- [On the Algorithmic Stability and Generalization of Adaptive Optimization Methods](https://mlsanity.com/paper/2211.03970/) (2022)
- [The Price of Implicit Bias in Adversarially Robust Generalization](https://mlsanity.com/paper/2406.04981/) (2024)
- [Generalization Guarantees via Algorithm-dependent Rademacher Complexity](https://mlsanity.com/paper/2307.02501/) (2023)
- [Boosting the Confidence of Generalization for L2-Stable Randomized Learning Algorithms](https://mlsanity.com/paper/2206.03834/) (2022)
- [On the Stability and Generalization of Triplet Learning](https://mlsanity.com/paper/2302.09815/) (2023)
- [Stability and Sharper Risk Bounds with Convergence Rate tildeO(1/n2)](https://mlsanity.com/paper/2410.09766/) (2024)
- [Generalization at the Edge of Stability](https://mlsanity.com/paper/2604.19740/) (2026)
- [Teacher Guided Training: An Efficient Framework for Knowledge Transfer](https://mlsanity.com/paper/2208.06825/) (2022)
- [Stability, Complexity and Data-Dependent Worst-Case Generalization Bounds](https://mlsanity.com/paper/2507.06775/) (2025)
- [Revisiting Knowledge Distillation: The Hidden Role of Dataset Size](https://mlsanity.com/paper/2510.15516/) (2025)
- [Logarithmic-Free Moment and Generalization Bounds for Uniformly Stable Algorithms](https://mlsanity.com/paper/2608.09870/) (2026)
- [Improved Learning Rates for Stochastic Optimization](https://mlsanity.com/paper/2107.08686/) (2021)
- [Understanding Generalization of Federated Learning: the Trade-off between Model Stability and Optimization](https://mlsanity.com/paper/2411.16303/) (2024)
- [A Bootstrap Perspective on Stochastic Gradient Descent](https://mlsanity.com/paper/2512.07676/) (2025)
- [Disentangled and Distilled Encoder for Out-of-Distribution Reasoning with Rademacher Guarantees](https://mlsanity.com/paper/2512.10522/) (2025)

## Abstract (arXiv)

We present a study of generalization for data-dependent hypothesis sets. We give a general learning guarantee for data-dependent hypothesis sets based on a notion of transductive Rademacher complexity. Our main result is a generalization bound for data-dependent hypothesis sets expressed in terms of a notion of hypothesis set stability and a notion of Rademacher complexity for data-dependent hypothesis sets that we introduce. This bound admits as special cases both standard Rademacher complexity bounds and algorithm-dependent uniform stability bounds. We also illustrate the use of these learning bounds in the analysis of several scenarios.