mlsanityData to 7 Oct 2026

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

arXiv 1709.06617 ↗First posted 19 Sep 2017cs.LGcited by 29

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 8; 2022: 7; 2023: 6; 2024: 5; 2025: 2; 2026: 1.

29 papers.

Sort:

  1. 2021User-friendly introduction to PAC-Bayes boundscited by 234
  2. 2021Heavy Tails in SGD and Compressibility of Overparametrized Neural Networkscited by 44
  3. 2021Stability and Generalization of Stochastic Gradient Methods for Minimax Problemscited by 35
  4. 2021On the Generalization of Models Trained with SGD: Information-Theoretic Bounds and Implicationscited by 31
  5. 2021Generalization Bounds for Meta-Learning via PAC-Bayes and Uniform Stabilitycited by 29
  6. 2021Variance Reduced Training with Stratified Sampling for Forecasting Modelscited by 13
  7. 2021PAC-Bayes Bounds for Meta-learning with Data-Dependent Priorcited by 11
  8. 2022Generalization Bounds for Stochastic Gradient Descent via Localized varepsilon-Coverscited by 11
  9. 2023Improved Stability and Generalization Guarantees of the Decentralized SGD Algorithmcited by 10
  10. 2021Optimal Rates for Random Order Online Optimizationcited by 9
  11. 2024Uniform Generalization Bounds on Data-Dependent Hypothesis Sets via PAC-Bayesian Theory on Random Setscited by 9
  12. 2022Uniform Stability for First-Order Empirical Risk Minimizationcited by 8
17 more
  1. 2022On the Importance of Gradient Norm in PAC-Bayesian Boundscited by 6
  2. 2022Generalization Bounds for Gradient Methods via Discrete and Continuous Priorcited by 5
  3. 2023High Probability Analysis for Non-Convex Stochastic Optimization with Clippingcited by 5
  4. 2023Sample-Conditioned Hypothesis Stability Sharpens Information-Theoretic Generalization Boundscited by 5
  5. 2022PAC-Bayesian Learning of Optimization Algorithmscited by 4
  6. 2024Generalization Error Matters in Decentralized Learning Under Byzantine Attackscited by 4
  7. 2023Enhance Diffusion to Improve Robust Generalizationcited by 3
  8. 2024Leveraging Gradients for Unsupervised Accuracy Estimation under Distribution Shiftcited by 3
  9. 2023Minimax Excess Risk of First-Order Methods for Statistical Learning with Data-Dependent Oraclescited by 2
  10. 2023Information-Theoretic Generalization Bounds for Transductive Learning and its Applicationscited by 2
  11. 2022Demystify Optimization and Generalization of Over-parameterized PAC-Bayesian Learningcited by 1
  12. 2022Super-model ecosystem: A domain-adaptation perspectivecited by 1
  13. 2024Convex SGD: Generalization Without Early Stoppingcited by 1
  14. 2024A Generalization Result for Convergence in Learning-to-Optimizecited by 1
  15. 2025Randomized Pairwise Learning with Adaptive Sampling: A PAC-Bayes Analysiscited by 1
  16. 2025Scaling Law Analysis in Federated Learning: How to Select the Optimal Model Size?cited by 0
  17. 2026Overfitting and Generalizing with (PAC) Bayesian Prediction in Noisy Binary Classificationcited by 0