mlsanityData to 7 Oct 2026

Information Theoretic Lower Bounds for Information Theoretic Upper Bounds

arXiv 2302.04925 ↗First posted 9 Feb 2023cs.LG stat.MLcited by 16

Not on the map. Why?

Abstract (arXiv)

We examine the relationship between the mutual information between the output model and the empirical sample and the generalization of the algorithm in the context of stochastic convex optimization. Despite increasing interest in information-theoretic generalization bounds, it is uncertain if these bounds can provide insight into the exceptional performance of various learning algorithms. Our study of stochastic convex optimization reveals that, for true risk minimization, dimension-dependent mutual information is necessary. This indicates that existing information-theoretic generalization bounds fall short in capturing the generalization capabilities of algorithms like SGD and regularized ERM, which have dimension-independent sample complexity.

Key facts. Cited by 16 papers in the map (data through 7 Oct 2026). Builds on 25 of its 46 references that are in the map. First posted on arXiv 9 Feb 2023.

Builds on

25 of 46 references.

References · 25

  1. 2020Extracting Training Data from Large Language Modelscited by 2,144
  2. 2019Introduction to Online Convex Optimizationcited by 793
  3. 2019Does Learning Require Memorization? A Short Tale about a Long Tailcited by 452
  4. 2014In Search of the Real Inductive Bias: On the Role of Implicit Regularization in Deep Learningcited by 339
  5. 2017Information-theoretic analysis of generalization capability of learning algorithmscited by 299
  6. 2020Stability of Stochastic Gradient Descent on Nonsmooth Convex Lossescited by 172
  7. 2020Reasoning About Generalization via Conditional Mutual Informationcited by 145
  8. 2019Information-Theoretic Generalization Bounds for SGLD via Data-Dependent Estimatescited by 118
  9. 2019Tightening Mutual Information Based Bounds on Generalization Errorcited by 117
  10. 2018Privately Learning High-Dimensional Distributionscited by 103
  11. 2015How much does your data exploration overfit? Controlling bias via information usagecited by 95
  12. 2020Sharpened Generalization Bounds based on Conditional Mutual Information and an Application to Noisy, Iterative Algorithmscited by 89
13 more
  1. 2021Information-Theoretic Generalization Bounds for Stochastic Gradient Descentcited by 84
  2. 2013Fingerprinting Codes and the Price of Approximate Differential Privacycited by 81
  3. 2018Generalization Error Bounds for Noisy, Iterative Algorithmscited by 79
  4. 2020An Equivalence Between Private Classification and Online Predictioncited by 63
  5. 2021SGD Generalizes Better Than GD (And Regularization Doesn't Help)cited by 38
  6. 2016Generalization of ERM in Stochastic Convex Optimization: The Dimension Strikes Backcited by 37
  7. 2014Interactive Fingerprinting Codes and the Hardness of Preventing False Discoverycited by 35
  8. 2020Individually Conditional Individual Mutual Information Bound on Generalization Errorcited by 30
  9. 2020On Random Subset Generalization Error Bounds and the Stochastic Gradient Langevin Dynamics Algorithmcited by 28
  10. 2020A Limitation of the PAC-Bayes Frameworkcited by 24
  11. 2022Limitations of Information-Theoretic Generalization Bounds for Gradient Descent Methods in Stochastic Convex Optimizationcited by 18
  12. 2021Never Go Full Batch (in Stochastic Convex Optimization)cited by 14
  13. 2022Finite Littlestone Dimension Implies Finite Information Complexitycited by 7

Built on by

Cited by year (2026 to 7 Oct)

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

16 papers.

Sort:

By area:

  1. 2025Does Generation Require Memorization? Creative Diffusion Models using Ambient Diffusioncited by 17
  2. 2023Time-Independent Information-Theoretic Generalization Bounds for SGLDcited by 12
  3. 2024Information Complexity of Stochastic Convex Optimization: Applications to Generalization and Memorizationcited by 12
  4. 2023Data-dependent Generalization Bounds via Variable-Size Compressibilitycited by 9
  5. 2023Select without Fear: Almost All Mini-Batch Schedules Generalize Optimallycited by 5
  6. 2023Sample-Conditioned Hypothesis Stability Sharpens Information-Theoretic Generalization Boundscited by 5
  7. 2024The Sample Complexity of Gradient Descent in Stochastic Convex Optimizationcited by 5
  8. 2025Trade-offs in Data Memorization via Strong Data Processing Inequalitiescited by 5
  9. 2024Not Every Image is Worth a Thousand Words: Quantifying Originality in Stable Diffusioncited by 4
  10. 2024Generalization Bounds via Conditional f-Informationcited by 3
  11. 2025Generalization Guarantees for Representation Learning via Data-Dependent Gaussian Mixture Priorscited by 2
  12. 2026Leveraging Flatness to Improve Information-Theoretic Generalization Bounds for SGDcited by 2
4 more
  1. 2025Multiview Representation Learning via Distributed Joint Latent Space Structuringcited by 1
  2. 2025Reconstructing Template-Memorized Images from Natural Promptscited by 1
  3. 2026All ERMs Can Fail in Stochastic Convex Optimization Lower Bounds in Linear Dimensioncited by 0
  4. 2026We Should Separate Memorization from Copyrightcited by 0