mlsanityData to 14 Oct 2026

Generalization Error Bounds Via R'enyi-, f-Divergences and Maximal Leakage

arXiv 1912.01439 ↗First posted 1 Dec 2019cs.IT cs.LG math.ITcited by 48

Not on the map. Why?

Abstract (arXiv)

In this work, the probability of an event under some joint distribution is bounded by measuring it with the product of the marginals instead (which is typically easier to analyze) together with a measure of the dependence between the two random variables. These results find applications in adaptive data analysis, where multiple dependencies are introduced and in learning theory, where they can be employed to bound the generalization error of a learning algorithm. Bounds are given in terms of Sibson's Mutual Information, α-Divergences, Hellinger Divergences, and f-Divergences. A case of particular interest is the Maximal Leakage (or Sibson's Mutual Information of order infinity), since this measure is robust to post-processing and composes adaptively. The corresponding bound can be seen as a generalization of classical bounds, such as Hoeffding's and McDiarmid's inequalities, to the case of dependent random variables.

Key facts. Cited by 48 papers in the map (data through 14 Oct 2026). First posted on arXiv 1 Dec 2019.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 8; 2022: 14; 2023: 8; 2024: 5; 2025: 9; 2026: 4.

48 papers.

Sort:

By area:

  1. 2021Information-theoretic generalization bounds for black-box learning algorithmscited by 49
  2. 2021Tighter expected generalization error bounds via Wasserstein distancecited by 43
  3. 2022Generalization Bounds via Convex Analysiscited by 27
  4. 2022Rate-Distortion Theoretic Generalization Bounds for Stochastic Learning Algorithmscited by 22
  5. 2022An Information-theoretical Approach to Semi-supervised Learning under Covariate-shiftcited by 18
  6. 2023More PAC-Bayes bounds: From bounded losses, to losses with general tail behaviors, to anytime validitycited by 17
  7. 2022On Rademacher Complexity-based Generalization Bounds for Deep Learningcited by 16
  8. 2021Generalization Bounds for Noisy Iterative Algorithms Using Properties of Additive Noise Channelscited by 15
  9. 2021Characterizing and Understanding the Generalization Error of Transfer Learning with Gibbs Algorithmcited by 14
  10. 2022Empirical Risk Minimization with Relative Entropy Regularizationcited by 13
  11. 2021Information-Theoretic Bounds on the Moments of the Generalization Error of Learning Algorithmscited by 12
  12. 2021Information-Theoretic Characterization of the Generalization Error for Iterative Semi-Supervised Learningcited by 11
36 more
  1. 2022Tighter Expected Generalization Error Bounds via Convexity of Information Measurescited by 11
  2. 2022Chained Generalisation Boundscited by 10
  3. 2023On the Validation of Gibbs Algorithms: Training Datasets, Test Datasets and their Aggregationcited by 10
  4. 2024Information-Theoretic Generalization Bounds for Deep Neural Networkscited by 10
  5. 2021Generalization Error Bounds on Deep Learning with Markov Datasetscited by 9
  6. 2023Data-dependent Generalization Bounds via Variable-Size Compressibilitycited by 9
  7. 2022Improved Information Theoretic Generalization Bounds for Distributed and Federated Learningcited by 8
  8. 2022f-divergences and their applications in lossy compression and bounding generalization errorcited by 7
  9. 2022Finite Littlestone Dimension Implies Finite Information Complexitycited by 7
  10. 2022From Generalisation Error to Transportation-cost Inequalities and Backcited by 6
  11. 2022Learning Algorithm Generalization Error Bounds via Auxiliary Distributionscited by 6
  12. 2023A unified framework for information-theoretic generalization boundscited by 6
  13. 2022How Does Pseudo-Labeling Affect the Generalization Error of the Semi-Supervised Gibbs Algorithm?cited by 5
  14. 2024The Method of Gaps: Exact Expressions for the Generalization Error of Supervised Learning Algorithmscited by 5
  15. 2023Global Convergence Rate of Deep Equilibrium Models with General Activationscited 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. 2024An Information-Theoretic Framework for Out-of-Distribution Generalization with Applications to Stochastic Gradient Langevin Dynamicscited by 3
  19. 2023Generalization Error Bounds for Noisy, Iterative Algorithms via Maximal Leakagecited by 2
  20. 2023Lower Bounds on the Bayesian Risk via Information Measurescited by 2
  21. 2023Information-Theoretic Generalization Bounds for Transductive Learning and its Applicationscited by 2
  22. 2025Generalization Guarantees for Representation Learning via Data-Dependent Gaussian Mixture Priorscited by 2
  23. 2024Which Algorithms Have Tight Generalization Bounds?cited by 1
  24. 2025Multiview Representation Learning via Distributed Joint Latent Space Structuringcited by 1
  25. 2025Generalization Bounds for Quantum Learning via R'enyi Divergencescited by 1
  26. 2025A DPI-PAC-Bayesian Framework for Generalization Boundscited by 1
  27. 2025A Dual Optimization View to Empirical Risk Minimization with f-Divergence Regularizationcited by 1
  28. 2024Tighter Learning Guarantees on Digital Computers via Concentration of Measure on Finite Spacescited by 0
  29. 2025Bounds on the Excess Minimum Risk via Generalized Information Divergence Measurescited by 0
  30. 2025Overfitting has a limitation: a model-independent generalization gap bound based on R'enyi entropycited by 0
  31. 2025PAC-Bayesian Generalization Bounds for Graph Convolutional Networks on Inductive Node Classificationcited by 0
  32. 2025An Information-Theoretic Analysis of OOD Generalization in Meta-Reinforcement Learningcited by 0
  33. 2026Empirical Risk Minimization with f-Divergence Regularizationcited by 0
  34. 2026Privacy Implies Stability: Information-Theoretic Generalization Bounds for Quantum Learningcited by 0
  35. 2026Tighter Information-Theoretic Generalization Bounds via a Novel Class of Change of Measure Inequalitiescited by 0
  36. 2026Block-Sample MAC-Bayes Generalization Boundscited by 0