# A PAC-Bayesian Analysis of Randomized Learning with Application to Stochastic Gradient Descent

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

## Key facts

- Cited by 29 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 Sep 2017.

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

- [User-friendly introduction to PAC-Bayes bounds](https://mlsanity.com/paper/2110.11216/) (2021)
- [Heavy Tails in SGD and Compressibility of Overparametrized Neural Networks](https://mlsanity.com/paper/2106.03795/) (2021)
- [Stability and Generalization of Stochastic Gradient Methods for Minimax Problems](https://mlsanity.com/paper/2105.03793/) (2021)
- [On the Generalization of Models Trained with SGD: Information-Theoretic Bounds and Implications](https://mlsanity.com/paper/2110.03128/) (2021)
- [Generalization Bounds for Meta-Learning via PAC-Bayes and Uniform Stability](https://mlsanity.com/paper/2102.06589/) (2021)
- [Variance Reduced Training with Stratified Sampling for Forecasting Models](https://mlsanity.com/paper/2103.02062/) (2021)
- [PAC-Bayes Bounds for Meta-learning with Data-Dependent Prior](https://mlsanity.com/paper/2102.03748/) (2021)
- [Generalization Bounds for Stochastic Gradient Descent via Localized varepsilon-Covers](https://mlsanity.com/paper/2209.08951/) (2022)
- [Improved Stability and Generalization Guarantees of the Decentralized SGD Algorithm](https://mlsanity.com/paper/2306.02939/) (2023)
- [Optimal Rates for Random Order Online Optimization](https://mlsanity.com/paper/2106.15207/) (2021)
- [Uniform Generalization Bounds on Data-Dependent Hypothesis Sets via PAC-Bayesian Theory on Random Sets](https://mlsanity.com/paper/2404.17442/) (2024)
- [Uniform Stability for First-Order Empirical Risk Minimization](https://mlsanity.com/paper/2207.08257/) (2022)
- [On the Importance of Gradient Norm in PAC-Bayesian Bounds](https://mlsanity.com/paper/2210.06143/) (2022)
- [Sample-Conditioned Hypothesis Stability Sharpens Information-Theoretic Generalization Bounds](https://mlsanity.com/paper/2310.20102/) (2023)
- [Generalization Bounds for Gradient Methods via Discrete and Continuous Prior](https://mlsanity.com/paper/2205.13799/) (2022)
- [High Probability Analysis for Non-Convex Stochastic Optimization with Clipping](https://mlsanity.com/paper/2307.13680/) (2023)
- [PAC-Bayesian Learning of Optimization Algorithms](https://mlsanity.com/paper/2210.11113/) (2022)
- [Generalization Error Matters in Decentralized Learning Under Byzantine Attacks](https://mlsanity.com/paper/2407.08632/) (2024)
- [Enhance Diffusion to Improve Robust Generalization](https://mlsanity.com/paper/2306.02618/) (2023)
- [Leveraging Gradients for Unsupervised Accuracy Estimation under Distribution Shift](https://mlsanity.com/paper/2401.08909/) (2024)
- [Minimax Excess Risk of First-Order Methods for Statistical Learning with Data-Dependent Oracles](https://mlsanity.com/paper/2307.04679/) (2023)
- [Information-Theoretic Generalization Bounds for Transductive Learning and its Applications](https://mlsanity.com/paper/2311.04561/) (2023)
- [Demystify Optimization and Generalization of Over-parameterized PAC-Bayesian Learning](https://mlsanity.com/paper/2202.01958/) (2022)
- [Super-model ecosystem: A domain-adaptation perspective](https://mlsanity.com/paper/2208.14092/) (2022)
- [Convex SGD: Generalization Without Early Stopping](https://mlsanity.com/paper/2401.04067/) (2024)
- [A Generalization Result for Convergence in Learning-to-Optimize](https://mlsanity.com/paper/2410.07704/) (2024)
- [Randomized Pairwise Learning with Adaptive Sampling: A PAC-Bayes Analysis](https://mlsanity.com/paper/2504.02957/) (2025)
- [Scaling Law Analysis in Federated Learning: How to Select the Optimal Model Size?](https://mlsanity.com/paper/2511.12188/) (2025)
- [Overfitting and Generalizing with (PAC) Bayesian Prediction in Noisy Binary Classification](https://mlsanity.com/paper/2603.22644/) (2026)

## Abstract (arXiv)

We study the generalization error of randomized learning algorithms -- focusing on stochastic gradient descent (SGD) -- using a novel combination of PAC-Bayes and algorithmic stability. Importantly, our generalization bounds hold for all posterior distributions on an algorithm's random hyperparameters, including distributions that depend on the training data. This inspires an adaptive sampling algorithm for SGD that optimizes the posterior at runtime. We analyze this algorithm in the context of our generalization bounds and evaluate it on a benchmark dataset. Our experiments demonstrate that adaptive sampling can reduce empirical risk faster than uniform sampling while also improving out-of-sample accuracy.