mlsanityData to 7 Oct 2026

Generalization Error Bounds for Noisy, Iterative Algorithms

arXiv 1801.04295 ↗First posted 12 Jan 2018cs.LG cs.IT math.ITcited by 79

Not on the map. Why?

Abstract (arXiv)

In statistical learning theory, generalization error is used to quantify the degree to which a supervised machine learning algorithm may overfit to training data. Recent work [Xu and Raginsky (2017)] has established a bound on the generalization error of empirical risk minimization based on the mutual information I(S;W) between the algorithm input S and the algorithm output W, when the loss function is sub-Gaussian. We leverage these results to derive generalization error bounds for a broad class of iterative algorithms that are characterized by bounded, noisy updates with Markovian structure. Our bounds are very general and are applicable to numerous settings of interest, including stochastic gradient Langevin dynamics (SGLD) and variants of the stochastic gradient Hamiltonian Monte Carlo (SGHMC) algorithm. Furthermore, our error bounds hold for any output function computed over the path of iterates, including the last iterate of the algorithm or the average of subsets of iterates, and also allow for non-uniform sampling of data in successive updates of the algorithm.

Key facts. Cited by 79 papers in the map (data through 7 Oct 2026). First posted on arXiv 12 Jan 2018.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 13; 2022: 18; 2023: 18; 2024: 9; 2025: 13; 2026: 8.

79 papers.

Sort:

By area:

  1. 2021Information-Theoretic Generalization Bounds for Stochastic Gradient Descentcited by 84
  2. 2023To Compress or Not to Compress- Self-Supervised Learning and Information Theory: A Reviewcited by 72
  3. 2021Information-theoretic generalization bounds for black-box learning algorithmscited by 49
  4. 2021Generalization Bounds For Meta-Learning: An Information-Theoretic Analysiscited by 45
  5. 2021On the Generalization of Models Trained with SGD: Information-Theoretic Bounds and Implicationscited by 31
  6. 2021Towards a Unified Information-Theoretic Framework for Generalizationcited by 29
  7. 2021PAC-Bayes Information Bottleneckcited by 28
  8. 2021Generalization Bounds using Lower Tail Exponents in Stochastic Optimizerscited by 27
  9. 2021Time-independent Generalization Bounds for SGLD in Non-convex Settingscited by 27
  10. 2024Knowledge Overshadowing Causes Amalgamated Hallucination in Large Language Modelscited by 24
  11. 2023Tighter Information-Theoretic Generalization Bounds from Supersamplescited by 21
  12. 2021RATT: Leveraging Unlabeled Data to Guarantee Generalizationcited by 20
38 more
  1. 2022Beyond Lipschitz: Sharp Generalization and Excess Risk Bounds for Full-Batch GDcited by 19
  2. 2022Limitations of Information-Theoretic Generalization Bounds for Gradient Descent Methods in Stochastic Convex Optimizationcited by 18
  3. 2023Information Theoretic Lower Bounds for Information Theoretic Upper Boundscited by 16
  4. 2021Generalization Bounds for Noisy Iterative Algorithms Using Properties of Additive Noise Channelscited by 15
  5. 2022Information-Theoretic Analysis of Unsupervised Domain Adaptationcited by 15
  6. 2023Generalization Bounds with Data-dependent Fractal Dimensionscited by 15
  7. 2023Time-Independent Information-Theoretic Generalization Bounds for SGLDcited by 12
  8. 2021Information-Theoretic Characterization of the Generalization Error for Iterative Semi-Supervised Learningcited by 11
  9. 2022On the Generalization for Transfer Learning: An Information-Theoretic Analysiscited by 11
  10. 2022Two Facets of SDE Under an Information-Theoretic Lens: Generalization of SGD via Training Trajectories and via Terminal Statescited by 11
  11. 2024Information-Theoretic Generalization Bounds for Deep Neural Networkscited by 10
  12. 2022Generalisation under gradient descent via deterministic PAC-Bayescited by 9
  13. 2024Generalization and Informativeness of Conformal Predictioncited by 9
  14. 2024Uniform Generalization Bounds on Data-Dependent Hypothesis Sets via PAC-Bayesian Theory on Random Setscited by 9
  15. 2022Stability Based Generalization Bounds for Exponential Family Langevin Dynamicscited by 8
  16. 2022Improved Information Theoretic Generalization Bounds for Distributed and Federated Learningcited by 8
  17. 2022On Leave-One-Out Conditional Mutual Information For Generalizationcited by 8
  18. 2022SketchySGD: Reliable Stochastic Optimization via Randomized Curvature Estimatescited by 8
  19. 2023Algorithm-Dependent Bounds for Representation Learning of Multi-Source Domain Adaptationcited by 7
  20. 2022From Generalisation Error to Transportation-cost Inequalities and Backcited by 6
  21. 2022On the Importance of Gradient Norm in PAC-Bayesian Boundscited by 6
  22. 2025Implicit Regularisation in Diffusion Models: An Algorithm-Dependent Generalisation Analysiscited by 6
  23. 2022On generalization bounds for deep networks based on loss surface implicit regularizationcited by 5
  24. 2022Generalization Bounds for Gradient Methods via Discrete and Continuous Priorcited by 5
  25. 2023Learning Trajectories are Generalization Indicatorscited by 5
  26. 2023Recognizable Information Bottleneckcited by 5
  27. 2023Understanding the Generalization Ability of Deep Learning Algorithms: A Kernelized Renyi's Entropy Perspectivecited by 5
  28. 2023Select without Fear: Almost All Mini-Batch Schedules Generalize Optimallycited by 5
  29. 2023Sample-Conditioned Hypothesis Stability Sharpens Information-Theoretic Generalization Boundscited by 5
  30. 2023Exactly Tight Information-Theoretic Generalization Error Bound for the Quadratic Gaussian Problemcited by 4
  31. 2025Algorithm- and Data-Dependent Generalization Bounds for Diffusion Modelscited by 4
  32. 2022Protecting Split Learning by Potential Energy Losscited by 3
  33. 2023Information-theoretic Analysis of Test Data Sensitivity in Uncertaintycited by 3
  34. 2023Generalization Bounds for Label Noise Stochastic Gradient Descentcited by 3
  35. 2024How Does Distribution Matching Help Domain Generalization: An Information-theoretic Analysiscited by 3
  36. 2024Generalization Bounds via Conditional f-Informationcited by 3
  37. 2023Generalization Error Bounds for Noisy, Iterative Algorithms via Maximal Leakagecited by 2
  38. 2023Information-Theoretic Generalization Analysis for Topology-aware Heterogeneous Federated Edge Learning over Noisy Channelscited by 2

50 most cited of 79 All 79 (JSON)