mlsanityData to 14 Oct 2026

Tighter expected generalization error bounds via Wasserstein distance

arXiv 2101.09315 ↗First posted 22 Jan 2021stat.ML cs.IT cs.LGcited by 43

Not on the map. Why?

Abstract (arXiv)

This work presents several expected generalization error bounds based on the Wasserstein distance. More specifically, it introduces full-dataset, single-letter, and random-subset bounds, and their analogues in the randomized subsample setting from Steinke and Zakynthinou [1]. Moreover, when the loss function is bounded and the geometry of the space is ignored by the choice of the metric in the Wasserstein distance, these bounds recover from below (and thus, are tighter than) current bounds based on the relative entropy. In particular, they generate new, non-vacuous bounds based on the relative entropy. Therefore, these results can be seen as a bridge between works that account for the geometry of the hypothesis space and those based on the relative entropy, which is agnostic to such geometry. Furthermore, it is shown how to produce various new bounds based on different information measures (e.g., the lautum information or several f-divergences) based on these bounds and how to derive similar bounds with respect to the backward channel using the presented proof techniques.

Key facts. Cited by 43 papers in the map (data through 14 Oct 2026). Builds on 20 of its 48 references that are in the map. First posted on arXiv 22 Jan 2021.

Builds on

20 of 48 references.

References · 20

  1. 2016Concentrated Differential Privacy: Simplifications, Extensions, and Lower Boundscited by 346
  2. 2017Information-theoretic analysis of generalization capability of learning algorithmscited by 303
  3. 2020Reasoning About Generalization via Conditional Mutual Informationcited by 147
  4. 2017On the Properties of the Softmax Function with Application in Game Theory and Reinforcement Learningcited by 142
  5. 2019A Primer on PAC-Bayesian Learningcited by 132
  6. 2019Information-Theoretic Generalization Bounds for SGLD via Data-Dependent Estimatescited by 119
  7. 2019Tightening Mutual Information Based Bounds on Generalization Errorcited by 117
  8. 2015How much does your data exploration overfit? Controlling bias via information usagecited by 95
  9. 2019Sharper bounds for uniformly stable algorithmscited by 93
  10. 2020Sharpened Generalization Bounds based on Conditional Mutual Information and an Application to Noisy, Iterative Algorithmscited by 89
  11. 2015Generalization in Adaptive Data Analysis and Holdout Reusecited by 83
  12. 2018Chaining Mutual Information and Tightening Generalization Boundscited by 65
8 more
  1. 2019Generalization Error Bounds Via R'enyi-, f-Divergences and Maximal Leakagecited by 48
  2. 2020Generalization Bounds via Information Density and Conditional Information Densitycited by 43
  3. 2020Individually Conditional Individual Mutual Information Bound on Generalization Errorcited by 30
  4. 2017Calibrating Noise to Variance in Adaptive Data Analysiscited by 29
  5. 2020On Random Subset Generalization Error Bounds and the Stochastic Gradient Langevin Dynamics Algorithmcited by 28
  6. 2019Information-Theoretic Understanding of Population Risk Improvement with Model Compressioncited by 11
  7. 2018An Optimal Transport View on Generalizationcited by 5
  8. 2020Upper Bounds on the Generalization Error of Private Algorithms for Discrete Datacited by 5

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 5; 2022: 13; 2023: 9; 2024: 9; 2025: 5; 2026: 2.

43 papers.

Sort:

By area:

  1. 2021User-friendly introduction to PAC-Bayes boundscited by 239
  2. 2023On the Generalization of Diffusion Modelcited by 30
  3. 2022Generalization Bounds via Convex Analysiscited by 27
  4. 2022Single Trajectory Nonparametric Learning of Nonlinear Dynamicscited by 26
  5. 2023Tighter Information-Theoretic Generalization Bounds from Supersamplescited by 22
  6. 2022Integral Probability Metrics PAC-Bayes Boundscited by 19
  7. 2022Limitations of Information-Theoretic Generalization Bounds for Gradient Descent Methods in Stochastic Convex Optimizationcited by 19
  8. 2021Generalization Bounds for Noisy Iterative Algorithms Using Properties of Additive Noise Channelscited by 15
  9. 2022Information-Theoretic Analysis of Unsupervised Domain Adaptationcited by 15
  10. 2023Online-to-PAC Conversions: Generalization Bounds via Regret Analysiscited by 14
  11. 2022Empirical Risk Minimization with Relative Entropy Regularizationcited by 13
  12. 2021Information-Theoretic Bounds on the Moments of the Generalization Error of Learning Algorithmscited by 12
31 more
  1. 2023Learning via Wasserstein-Based High Probability Generalisation Boundscited by 12
  2. 2022Tighter Expected Generalization Error Bounds via Convexity of Information Measurescited by 11
  3. 2022On the Generalization for Transfer Learning: An Information-Theoretic Analysiscited by 11
  4. 2022Chained Generalisation Boundscited by 10
  5. 2023On the Validation of Gibbs Algorithms: Training Datasets, Test Datasets and their Aggregationcited by 10
  6. 2024Information-Theoretic Generalization Bounds for Deep Neural Networkscited by 10
  7. 2022Learning Algorithm Generalization Error Bounds via Auxiliary Distributionscited by 6
  8. 2023A unified framework for information-theoretic generalization boundscited by 6
  9. 2023Sample-Conditioned Hypothesis Stability Sharpens Information-Theoretic Generalization Boundscited by 6
  10. 2024The Method of Gaps: Exact Expressions for the Generalization Error of Supervised Learning Algorithmscited by 5
  11. 2025Selective Risk Certification for LLM Outputs via Information-Lift Statistics: PAC-Bayes, Robustness, and Skeleton Designcited by 5
  12. 2021Learning distinct features helps, provablycited by 4
  13. 2023Learning Against Distributional Uncertainty: On the Trade-off Between Robustness and Specificitycited by 4
  14. 2024A General Theory for Compositional Generalizationcited by 4
  15. 2024Generalization Bounds via Conditional f-Informationcited by 4
  16. 2021Characterizing the Generalization Error of Gibbs Algorithm with Symmetrized KL informationcited by 3
  17. 2022Formal limitations of sample-wise information-theoretic generalization boundscited by 3
  18. 2023Wasserstein PAC-Bayes Learning: Exploiting Optimisation Guarantees to Explain Generalisationcited by 3
  19. 2024How Does Distribution Matching Help Domain Generalization: An Information-theoretic Analysiscited by 3
  20. 2025Fairness Overfitting in Machine Learning: An Information-Theoretic Perspectivecited by 3
  21. 2022Distributional Robustness Bounds Generalization Errorscited by 2
  22. 2024Class-wise Generalization Error: an Information-Theoretic Analysiscited by 2
  23. 2025Bayesian Experimental Design for Model Discrepancy Calibration: An Auto-Differentiable Ensemble Kalman Inversion Approachcited by 2
  24. 2025Information Science Principles of Machine Learning: A Causal Chain Meta-Framework Based on Formalized Information Mappingcited by 2
  25. 2022An Information-Theoretic Analysis of Bayesian Reinforcement Learningcited by 1
  26. 2024Generalization of Graph Neural Networks through the Lens of Homomorphismcited by 1
  27. 2025Learning to Substitute Components for Compositional Generalizationcited by 1
  28. 2024A note on generalization bounds for losses with finite momentscited by 0
  29. 2024Error Bounds of Supervised Classification from Information-Theoretic Perspectivecited by 0
  30. 2026Bayesian Experimental Design for Model Discrepancy Calibration: A Rivalry between Kullback--Leibler Divergence and Wasserstein Distancecited by 0
  31. 2026A Hierarchical Sampling Framework for bounding the Generalization Error of Federated Learningcited by 0