mlsanityData to 7 Oct 2026

Generalization Bounds for Noisy Iterative Algorithms Using Properties of Additive Noise Channels

arXiv 2102.02976 ↗First posted 5 Feb 2021stat.ML cs.IT cs.LGcited by 15

Not on the map. Why?

Abstract (arXiv)

Machine learning models trained by different optimization algorithms under different data distributions can exhibit distinct generalization behaviors. In this paper, we analyze the generalization of models trained by noisy iterative algorithms. We derive distribution-dependent generalization bounds by connecting noisy iterative algorithms to additive noise channels found in communication and information theory. Our generalization bounds shed light on several applications, including differentially private stochastic gradient descent (DP-SGD), federated learning, and stochastic gradient Langevin dynamics (SGLD). We demonstrate our bounds through numerical experiments, showing that they can help understand recent empirical observations of the generalization phenomena of neural networks.

Key facts. Cited by 15 papers in the map (data through 7 Oct 2026). Builds on 40 of its 82 references that are in the map. First posted on arXiv 5 Feb 2021.

Builds on

40 of 82 references.

References · 40

  1. 2016Communication-Efficient Learning of Deep Networks from Decentralized Datacited by 7,592
  2. 2019Advances and Open Problems in Federated Learningcited by 3,021
  3. 2016Deep Learning with Differential Privacycited by 2,682
  4. 2016Understanding deep learning requires rethinking generalizationcited by 1,657
  5. 2017Spectrally-normalized margin bounds for neural networkscited by 681
  6. 2019Fantastic Generalization Measures and Where to Find Themcited by 507
  7. 2014In Search of the Real Inductive Bias: On the Role of Implicit Regularization in Deep Learningcited by 339
  8. 2017Information-theoretic analysis of generalization capability of learning algorithmscited by 299
  9. 2017Non-convex learning via Stochastic Gradient Langevin Dynamics: a nonasymptotic analysiscited by 242
  10. 2015Escaping From Saddle Points --- Online Stochastic Gradient for Tensor Decompositioncited by 241
  11. 2020Reasoning About Generalization via Conditional Mutual Informationcited by 145
  12. 2015Adding Gradient Noise Improves Learning for Very Deep Networkscited by 144
28 more
  1. 2015Preconditioned Stochastic Gradient Langevin Dynamics for Deep Neural Networkscited by 121
  2. 2019Information-Theoretic Generalization Bounds for SGLD via Data-Dependent Estimatescited by 118
  3. 2019Tightening Mutual Information Based Bounds on Generalization Errorcited by 117
  4. 2018An Alternative View: When Does SGD Escape Local Minima?cited by 115
  5. 2014Preserving Statistical Validity in Adaptive Data Analysiscited by 102
  6. 2018Privacy Amplification by Iterationcited by 97
  7. 2017Global Convergence of Langevin Dynamics Based Algorithms for Nonconvex Optimizationcited by 96
  8. 2020Sharpened Generalization Bounds based on Conditional Mutual Information and an Application to Noisy, Iterative Algorithmscited by 89
  9. 2015Algorithmic Stability for Adaptive Data Analysiscited by 88
  10. 2021Information-Theoretic Generalization Bounds for Stochastic Gradient Descentcited by 84
  11. 2017Generalization Bounds of SGLD for Non-convex Learning: Two Theoretical Viewpointscited by 82
  12. 2018Generalization Error Bounds for Noisy, Iterative Algorithmscited by 79
  13. 2017A Hitting Time Analysis of Stochastic Gradient Langevin Dynamicscited by 70
  14. 2018Chaining Mutual Information and Tightening Generalization Boundscited by 65
  15. 2019On Generalization Error Bounds of Noisy Gradient Methods for Non-Convex Learningcited by 57
  16. 2019Generalization Error Bounds Via R'enyi-, f-Divergences and Maximal Leakagecited by 48
  17. 2020Generalization Bounds via Information Density and Conditional Information Densitycited by 43
  18. 2021Tighter expected generalization error bounds via Wasserstein distancecited by 43
  19. 2019A New Analysis of Differential Privacy's Generalization Guaranteescited by 36
  20. 2020Information-Theoretic Generalization Bounds for Meta-Learning and Applicationscited by 32
  21. 2020Individually Conditional Individual Mutual Information Bound on Generalization Errorcited by 30
  22. 2020On Random Subset Generalization Error Bounds and the Stochastic Gradient Langevin Dynamics Algorithmcited by 28
  23. 2019Privacy Amplification by Mixing and Diffusion Mechanismscited by 21
  24. 2020Information-Theoretic Bounds on the Generalization Error and Privacy Leakage in Federated Learningcited by 20
  25. 2020Jensen-Shannon Information Based Characterization of the Generalization Error of Learning Algorithmscited by 19
  26. 2020Tighter Generalization Bounds for Iterative Differentially Private Learning Algorithmscited by 14
  27. 2020Information-Theoretic Bounds on Transfer Generalization Gap Based on Jensen-Shannon Divergencecited by 11
  28. 2020Privacy Amplification of Iterative Algorithms via Contraction Coefficientscited by 7

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 3; 2023: 4; 2024: 3; 2025: 4; 2026: 1.

15 papers.

Sort:

  1. 2023Understanding Generalization of Federated Learning via Stability: Heterogeneity Matterscited by 27
  2. 2024Position: Understanding LLMs Requires More Than Statistical Generalizationcited by 20
  3. 2023Arbitrary Decisions are a Hidden Cost of Differentially Private Trainingcited by 19
  4. 2022Information-Theoretic Analysis of Unsupervised Domain Adaptationcited by 15
  5. 2023Time-Independent Information-Theoretic Generalization Bounds for SGLDcited by 12
  6. 2022Two Facets of SDE Under an Information-Theoretic Lens: Generalization of SGD via Training Trajectories and via Terminal Statescited by 11
  7. 2024Information-Theoretic Generalization Bounds for Deep Neural Networkscited by 10
  8. 2022Improved Information Theoretic Generalization Bounds for Distributed and Federated Learningcited by 8
  9. 2025Fairness Overfitting in Machine Learning: An Information-Theoretic Perspectivecited by 3
  10. 2023Generalization Error Bounds for Noisy, Iterative Algorithms via Maximal Leakagecited by 2
  11. 2024Class-wise Generalization Error: an Information-Theoretic Analysiscited by 2
  12. 2025Information-theoretic Generalization Analysis for VQ-VAEs: A Role of Latent Variablescited by 0
3 more
  1. 2025Generalization Bound of Gradient Flow through Training Trajectory and Data-dependent Kernelcited by 0
  2. 2025An Information-Theoretic Analysis of OOD Generalization in Meta-Reinforcement Learningcited by 0
  3. 2026Information-Theoretic Generalization Bounds for Sequential Decision Makingcited by 0