mlsanityData to 7 Oct 2026

Limitations of Information-Theoretic Generalization Bounds for Gradient Descent Methods in Stochastic Convex Optimization

arXiv 2212.13556 ↗First posted 27 Dec 2022cs.LG stat.MLcited by 18

Not on the map. Why?

Abstract (arXiv)

To date, no "information-theoretic" frameworks for reasoning about generalization error have been shown to establish minimax rates for gradient descent in the setting of stochastic convex optimization. In this work, we consider the prospect of establishing such rates via several existing information-theoretic frameworks: input-output mutual information bounds, conditional mutual information bounds and variants, PAC-Bayes bounds, and recent conditional variants thereof. We prove that none of these bounds are able to establish minimax rates. We then consider a common tactic employed in studying gradient methods, whereby the final iterate is corrupted by Gaussian noise, producing a noisy "surrogate" algorithm. We prove that minimax rates cannot be established via the analysis of such surrogates. Our results suggest that new ideas are required to analyze gradient descent using information-theoretic techniques.

Key facts. Cited by 18 papers in the map (data through 7 Oct 2026). Builds on 44 of its 74 references that are in the map. First posted on arXiv 27 Dec 2022.

Builds on

44 of 74 references.

References · 44

  1. 2021Convex optimizationcited by 2,479
  2. 2020Sharpness-Aware Minimization for Efficiently Improving Generalizationcited by 1,404
  3. 2014Convex Optimization: Algorithms and Complexitycited by 569
  4. 2015Train faster, generalize better: Stability of stochastic gradient descentcited by 547
  5. 2017Computing Nonvacuous Generalization Bounds for Deep (Stochastic) Neural Networks with Many More Parameters than Training Datacited by 527
  6. 2019Online Learning: A Modern Introduction Using Convex Optimizationcited by 407
  7. 2017A PAC-Bayesian Approach to Spectrally-Normalized Margin Bounds for Neural Networkscited by 309
  8. 2017Information-theoretic analysis of generalization capability of learning algorithmscited by 299
  9. 2020Stability of Stochastic Gradient Descent on Nonsmooth Convex Lossescited by 172
  10. 2020Reasoning About Generalization via Conditional Mutual Informationcited by 145
  11. 2019Information-Theoretic Generalization Bounds for SGLD via Data-Dependent Estimatescited by 118
  12. 2019Tightening Mutual Information Based Bounds on Generalization Errorcited by 117
32 more
  1. 2019High probability generalization bounds for uniformly stable algorithms with nearly optimal ratecited by 97
  2. 2015How much does your data exploration overfit? Controlling bias via information usagecited by 95
  3. 2020Sharpened Generalization Bounds based on Conditional Mutual Information and an Application to Noisy, Iterative Algorithmscited by 89
  4. 2021Information-Theoretic Generalization Bounds for Stochastic Gradient Descentcited by 84
  5. 2017Entropy-SGD optimizes the prior of a PAC-Bayes bound: Generalization properties of Entropy-SGD and data-dependent priorscited by 81
  6. 2018Generalization Error Bounds for Noisy, Iterative Algorithmscited by 79
  7. 2020On the role of data in PAC-Bayes boundscited by 64
  8. 2019On Generalization Error Bounds of Noisy Gradient Methods for Non-Convex Learningcited by 57
  9. 2018Generalization Bounds for Uniformly Stable Algorithmscited by 56
  10. 2021Information-theoretic generalization bounds for black-box learning algorithmscited by 49
  11. 2019In Defense of Uniform Convergence: Generalization via derandomization with an application to interpolating predictorscited by 44
  12. 2021Tighter expected generalization error bounds via Wasserstein distancecited by 43
  13. 2019The intriguing role of module criticality in the generalization of deep networkscited by 40
  14. 2021SGD Generalizes Better Than GD (And Regularization Doesn't Help)cited by 38
  15. 2021PAC-Bayes, MAC-Bayes and Conditional Mutual Information: Fast rate bounds that handle general VC classescited by 31
  16. 2021On the Generalization of Models Trained with SGD: Information-Theoretic Bounds and Implicationscited by 31
  17. 2020Individually Conditional Individual Mutual Information Bound on Generalization Errorcited by 30
  18. 2021Towards a Unified Information-Theoretic Framework for Generalizationcited by 29
  19. 2020On Random Subset Generalization Error Bounds and the Stochastic Gradient Langevin Dynamics Algorithmcited by 28
  20. 2020A Limitation of the PAC-Bayes Frameworkcited by 24
  21. 2018Spread Divergencecited by 23
  22. 2021SGD: The Role of Implicit Regularization, Batch-size and Multiple-epochscited by 22
  23. 2022Rate-Distortion Theoretic Generalization Bounds for Stochastic Learning Algorithmscited by 22
  24. 2022Benign Underfitting of Stochastic Gradient Descentcited by 18
  25. 2022Understanding Generalization via Leave-One-Out Conditional Mutual Informationcited by 16
  26. 2016On-Average KL-Privacy and its equivalence to Generalization for Max-Entropy Mechanismscited by 10
  27. 2022Stability Based Generalization Bounds for Exponential Family Langevin Dynamicscited by 8
  28. 2022Finite Littlestone Dimension Implies Finite Information Complexitycited by 7
  29. 2020Upper Bounds on the Generalization Error of Private Algorithms for Discrete Datacited by 5
  30. 2022Benefits of Additive Noise in Composing Classes with Bounded Capacitycited by 4
  31. 2022Formal limitations of sample-wise information-theoretic generalization boundscited by 3
  32. 2021Information-Theoretic Bayes Risk Lower Bounds for Realizable Modelscited by 1

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 10; 2024: 2; 2025: 4; 2026: 2.

18 papers.

Sort:

  1. 2023Tighter Information-Theoretic Generalization Bounds from Supersamplescited by 21
  2. 2023More PAC-Bayes bounds: From bounded losses, to losses with general tail behaviors, to anytime validitycited by 17
  3. 2023Information Theoretic Lower Bounds for Information Theoretic Upper Boundscited by 16
  4. 2024Information Complexity of Stochastic Convex Optimization: Applications to Generalization and Memorizationcited by 12
  5. 2023Data-dependent Generalization Bounds via Variable-Size Compressibilitycited by 9
  6. 2023Lessons from Generalization Error Analysis of Federated Learning: You May Communicate Less Often!cited by 8
  7. 2023Select without Fear: Almost All Mini-Batch Schedules Generalize Optimallycited by 5
  8. 2023Sample-Conditioned Hypothesis Stability Sharpens Information-Theoretic Generalization Boundscited by 5
  9. 2023Exactly Tight Information-Theoretic Generalization Error Bound for the Quadratic Gaussian Problemcited by 4
  10. 2023Generalization Guarantees via Algorithm-dependent Rademacher Complexitycited by 4
  11. 2024Generalization Bounds via Conditional f-Informationcited by 3
  12. 2025Generalization Guarantees for Representation Learning via Data-Dependent Gaussian Mixture Priorscited by 2
6 more
  1. 2026Leveraging Flatness to Improve Information-Theoretic Generalization Bounds for SGDcited by 2
  2. 2023Generalization error bounds for iterative learning algorithms with bounded updatescited by 1
  3. 2025Multiview Representation Learning via Distributed Joint Latent Space Structuringcited by 1
  4. 2025Information-theoretic Generalization Analysis for VQ-VAEs: A Role of Latent Variablescited by 0
  5. 2025Tight Generalization Error Bounds for Stochastic Gradient Descent in Non-convex Learningcited by 0
  6. 2026Generalization Bounds of Stochastic Gradient Descent in Homogeneous Neural Networkscited by 0