mlsanityData to 7 Oct 2026

Information Complexity of Stochastic Convex Optimization: Applications to Generalization and Memorization

arXiv 2402.09327 ↗First posted 14 Feb 2024cs.LGcited by 12

Not on the map. Why?

Abstract (arXiv)

In this work, we investigate the interplay between memorization and learning in the context of stochastic convex optimization (SCO). We define memorization via the information a learning algorithm reveals about its training data points. We then quantify this information using the framework of conditional mutual information (CMI) proposed by Steinke and Zakynthinou (2020). Our main result is a precise characterization of the tradeoff between the accuracy of a learning algorithm and its CMI, answering an open question posed by Livni (2023). We show that, in the L2 Lipschitz--bounded setting and under strong convexity, every learner with an excess error varepsilon has CMI bounded below by Omega(1/varepsilon2) and Omega(1/varepsilon), respectively. We further demonstrate the essential role of memorization in learning problems in SCO by designing an adversary capable of accurately identifying a significant fraction of the training samples in specific SCO problems. Finally, we enumerate several implications of our results, such as a limitation of generalization bounds based on CMI and the incompressibility of samples in SCO problems.

Key facts. Cited by 12 papers in the map (data through 7 Oct 2026). Builds on 52 of its 68 references that are in the map. First posted on arXiv 14 Feb 2024.

Builds on

52 of 68 references.

References · 52

  1. 2016Membership Inference Attacks against Machine Learning Modelscited by 2,221
  2. 2020Extracting Training Data from Large Language Modelscited by 2,144
  3. 2016Understanding deep learning requires rethinking generalizationcited by 1,657
  4. 2018The Secret Sharer: Evaluating and Testing Unintended Memorization in Neural Networkscited by 847
  5. 2021Membership Inference Attacks From First Principlescited by 839
  6. 2022Quantifying Memorization Across Neural Language Modelscited by 755
  7. 2020What Neural Networks Memorize and Why: Discovering the Long Tail via Influence Estimationcited by 492
  8. 2019Does Learning Require Memorization? A Short Tale about a Long Tailcited by 452
  9. 2017Information-theoretic analysis of generalization capability of learning algorithmscited by 299
  10. 2021User-friendly introduction to PAC-Bayes boundscited by 234
  11. 2020Stability of Stochastic Gradient Descent on Nonsmooth Convex Lossescited by 172
  12. 2020Reasoning About Generalization via Conditional Mutual Informationcited by 145
38 more
  1. 2022Reconstructing Training Data from Trained Neural Networkscited by 129
  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. 2019A Short Note on Concentration Inequalities for Random Vectors with SubGaussian Normcited by 105
  5. 2018Privately Learning High-Dimensional Distributionscited by 103
  6. 2020When is Memorization of Irrelevant Training Data Necessary for High-Accuracy Learning?cited by 102
  7. 2019High probability generalization bounds for uniformly stable algorithms with nearly optimal ratecited by 97
  8. 2015How much does your data exploration overfit? Controlling bias via information usagecited by 95
  9. 2020Sharpened Generalization Bounds based on Conditional Mutual Information and an Application to Noisy, Iterative Algorithmscited by 89
  10. 2019VC Classes are Adversarially Robustly Learnable, but Only Improperlycited by 83
  11. 2013Fingerprinting Codes and the Price of Approximate Differential Privacycited by 81
  12. 2022A Characterization of Multiclass Learnabilitycited by 66
  13. 2023Generalization Bounds: Perspectives from Information Theory and PAC-Bayescited by 60
  14. 2020Proper Learning, Helly Number, and an Optimal SVM Boundcited by 52
  15. 2021Information-theoretic generalization bounds for black-box learning algorithmscited by 49
  16. 2015Sample compression schemes for VC classescited by 46
  17. 2021SGD Generalizes Better Than GD (And Regularization Doesn't Help)cited by 38
  18. 2016Generalization of ERM in Stochastic Convex Optimization: The Dimension Strikes Backcited by 37
  19. 2021PAC-Bayes, MAC-Bayes and Conditional Mutual Information: Fast rate bounds that handle general VC classescited by 31
  20. 2020Individually Conditional Individual Mutual Information Bound on Generalization Errorcited by 30
  21. 2021Towards a Unified Information-Theoretic Framework for Generalizationcited by 29
  22. 2020On Random Subset Generalization Error Bounds and the Stochastic Gradient Langevin Dynamics Algorithmcited by 28
  23. 2020Reducing Adversarially Robust Learning to Non-Robust PAC Learningcited by 28
  24. 2020A Limitation of the PAC-Bayes Frameworkcited by 24
  25. 2021Adversarially Robust Learning with Unknown Perturbation Setscited by 24
  26. 2023Optimal Learners for Realizable Regression: PAC Learning and Online Learningcited by 23
  27. 2022Benign Underfitting of Stochastic Gradient Descentcited by 18
  28. 2022Limitations of Information-Theoretic Generalization Bounds for Gradient Descent Methods in Stochastic Convex Optimizationcited by 18
  29. 2022Adversarially Robust Learning: A Generic Minimax Optimal Learner and Characterizationcited by 17
  30. 2020Can Implicit Bias Explain Generalization? Stochastic Convex Optimization as a Case Studycited by 16
  31. 2022Understanding Generalization via Leave-One-Out Conditional Mutual Informationcited by 16
  32. 2023Information Theoretic Lower Bounds for Information Theoretic Upper Boundscited by 16
  33. 2021Never Go Full Batch (in Stochastic Convex Optimization)cited by 14
  34. 2014A Compression Technique for Analyzing Disagreement-Based Active Learningcited by 11
  35. 2022Evaluated CMI Bounds for Meta Learning: Tightness and Expressivenesscited by 11
  36. 2022Strong Memory Lower Bounds for Learning Natural Modelscited by 10
  37. 2017Nearest-Neighbor Sample Compression: Efficiency, Consistency, Infinite Dimensionscited by 7
  38. 2018Agnostic Sample Compression Schemes for Regressioncited by 7

50 most cited of 52 All 52 (JSON)

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 6; 2025: 3; 2026: 3.

12 papers.

  1. 2024Are we making progress in unlearning? Findings from the first NeurIPS unlearning competitioncited by 48
  2. 2025Does Generation Require Memorization? Creative Diffusion Models using Ambient Diffusioncited by 17
  3. 2024The Pitfalls of Memorization: When Memorization Hurts Generalizationcited by 16
  4. 2024Improved Localized Machine Unlearning Through the Lens of Memorizationcited by 6
  5. 2024The Sample Complexity of Gradient Descent in Stochastic Convex Optimizationcited by 5
  6. 2024Not Every Image is Worth a Thousand Words: Quantifying Originality in Stable Diffusioncited by 4
  7. 2024Provable Privacy Attacks on Trained Shallow Neural Networkscited by 4
  8. 2026Is your algorithm unlearning or untraining?cited by 3
  9. 2026Cram Less to Fit More: Training Data Pruning Improves Memorization of Factscited by 2
  10. 2025A Lightweight Method to Disrupt Memorized Sequences in LLMcited by 1
  11. 2025Lower Bounds for Public-Private Learning under Distribution Shiftcited by 0
  12. 2026All ERMs Can Fail in Stochastic Convex Optimization Lower Bounds in Linear Dimensioncited by 0