# PAC-Bayes bounds for stable algorithms with instance-dependent priors

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

## Key facts

- Cited by 21 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Jun 2018.

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

- [On Convergence of FedProx: Local Dissimilarity Invariant Bounds, Non-smoothness and Beyond](https://mlsanity.com/paper/2206.05187/) (2022)
- [Generalization Bounds for Meta-Learning via PAC-Bayes and Uniform Stability](https://mlsanity.com/paper/2102.06589/) (2021)
- [PAC-Bayes Information Bottleneck](https://mlsanity.com/paper/2109.14509/) (2021)
- [Non-Vacuous Generalisation Bounds for Shallow Neural Networks](https://mlsanity.com/paper/2202.01627/) (2022)
- [On Margins and Derandomisation in PAC-Bayes](https://mlsanity.com/paper/2107.03955/) (2021)
- [Differentially Private Algorithms for the Stochastic Saddle Point Problem with Optimal Rates for the Strong Gap](https://mlsanity.com/paper/2302.12909/) (2023)
- [PAC-Bayes Bounds for Meta-learning with Data-Dependent Prior](https://mlsanity.com/paper/2102.03748/) (2021)
- [Scalable PAC-Bayesian Meta-Learning via the PAC-Optimal Hyper-Posterior: From Theory to Practice](https://mlsanity.com/paper/2211.07206/) (2022)
- [Tighter PAC-Bayes Generalisation Bounds by Leveraging Example Difficulty](https://mlsanity.com/paper/2210.11289/) (2022)
- [PAC-Bayes Bounds for Bandit Problems: A Survey and Experimental Comparison](https://mlsanity.com/paper/2211.16110/) (2022)
- [Sample-Conditioned Hypothesis Stability Sharpens Information-Theoretic Generalization Bounds](https://mlsanity.com/paper/2310.20102/) (2023)
- [PAC Bayesian Performance Guarantees for Deep (Stochastic) Networks in Medical Imaging](https://mlsanity.com/paper/2104.05600/) (2021)
- [Controlling Multiple Errors Simultaneously with a PAC-Bayes Bound](https://mlsanity.com/paper/2202.05560/) (2022)
- [STEEL: Singularity-aware Reinforcement Learning](https://mlsanity.com/paper/2301.13152/) (2023)
- [Leveraging Gradients for Unsupervised Accuracy Estimation under Distribution Shift](https://mlsanity.com/paper/2401.08909/) (2024)
- [Probabilistic fine-tuning of pruning masks and PAC-Bayes self-bounded learning](https://mlsanity.com/paper/2110.11804/) (2021)
- [Information-Theoretic Generalization Bounds for Transductive Learning and its Applications](https://mlsanity.com/paper/2311.04561/) (2023)
- [Generalization of Hamiltonian algorithms](https://mlsanity.com/paper/2405.14469/) (2024)
- [Stability and Sharper Risk Bounds with Convergence Rate tildeO(1/n2)](https://mlsanity.com/paper/2410.09766/) (2024)
- [Higher-Order Generalization Bounds: Learning Deep Probabilistic Programs via PAC-Bayes Objectives](https://mlsanity.com/paper/2203.15972/) (2022)
- [Randomized Pairwise Learning with Adaptive Sampling: A PAC-Bayes Analysis](https://mlsanity.com/paper/2504.02957/) (2025)

## Abstract (arXiv)

PAC-Bayes bounds have been proposed to get risk estimates based on a training sample. In this paper the PAC-Bayes approach is combined with stability of the hypothesis learned by a Hilbert space valued algorithm. The PAC-Bayes setting is used with a Gaussian prior centered at the expected output. Thus a novelty of our paper is using priors defined in terms of the data-generating distribution. Our main result estimates the risk of the randomized algorithm in terms of the hypothesis stability coefficients. We also provide a new bound for the SVM classifier, which is compared to other known bounds experimentally. Ours appears to be the first stability-based bound that evaluates to non-trivial values.