mlsanityData to 14 Oct 2026

f-divergences and their applications in lossy compression and bounding generalization error

arXiv 2206.11042 ↗First posted 21 Jun 2022cs.IT cs.LG math.ITcited by 7

Not on the map. Why?

Abstract (arXiv)

In this paper, we provide three applications for f-divergences: (i) we introduce Sanov's upper bound on the tail probability of the sum of independent random variables based on super-modular f-divergence and show that our generalized Sanov's bound strictly improves over ordinary one, (ii) we consider the lossy compression problem which studies the set of achievable rates for a given distortion and code length. We extend the rate-distortion function using mutual f-information and provide new and strictly better bounds on achievable rates in the finite blocklength regime using super-modular f-divergences, and (iii) we provide a connection between the generalization error of algorithms with bounded input/output mutual f-information and a generalized rate-distortion problem. This connection allows us to bound the generalization error of learning algorithms using lower bounds on the f-rate-distortion function. Our bound is based on a new lower bound on the rate-distortion function that (for some examples) strictly improves over previously best-known bounds.

Key facts. Cited by 7 papers in the map (data through 14 Oct 2026). Builds on 18 of its 71 references that are in the map. First posted on arXiv 21 Jun 2022.

Builds on

18 of 71 references.

References · 18

  1. 2015Train faster, generalize better: Stability of stochastic gradient descentcited by 552
  2. 2018Learning Models with Uniform Performance via Distributionally Robust Optimizationcited by 335
  3. 2017Information-theoretic analysis of generalization capability of learning algorithmscited by 303
  4. 2019Tightening Mutual Information Based Bounds on Generalization Errorcited by 117
  5. 2015How much does your data exploration overfit? Controlling bias via information usagecited by 95
  6. 2018Chaining Mutual Information and Tightening Generalization Boundscited by 65
  7. 2019Generalization Error Bounds Via R'enyi-, f-Divergences and Maximal Leakagecited by 48
  8. 2020Generalization Bounds via Information Density and Conditional Information Densitycited by 43
  9. 2020Minimum Excess Risk in Bayesian Learningcited by 35
  10. 2022Rate-Distortion Theoretic Generalization Bounds for Stochastic Learning Algorithmscited by 22
  11. 2020Jensen-Shannon Information Based Characterization of the Generalization Error of Learning Algorithmscited by 19
  12. 2021Information-Theoretic Bounds on the Moments of the Generalization Error of Learning Algorithmscited by 12
6 more
  1. 2022Tighter Expected Generalization Error Bounds via Convexity of Information Measurescited by 11
  2. 2021Rate-Distortion Analysis of Minimum Excess Risk in Bayesian Learningcited by 10
  3. 2017Distributionally Robust Games: f-Divergence and Learningcited by 5
  4. 2018Generalizing Bottleneck Problemscited by 5
  5. 2021Characterizing the Generalization Error of Gibbs Algorithm with Symmetrized KL informationcited by 3
  6. 2020Distributionally Robust Variance Minimization: Tight Variance Bounds over f-Divergence Neighborhoodscited by 1

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2023: 2; 2024: 1; 2025: 1; 2026: 3.

7 papers.

  1. 2023Data-dependent Generalization Bounds via Variable-Size Compressibilitycited by 9
  2. 2023Generalization Analysis of Machine Learning Algorithms via the Worst-Case Data-Generating Probability Measurecited by 7
  3. 2024The Method of Gaps: Exact Expressions for the Generalization Error of Supervised Learning Algorithmscited by 5
  4. 2025Proofs for Folklore Theorems on the Radon-Nikodym Derivativecited by 4
  5. 2026Empirical Risk Minimization with f-Divergence Regularizationcited by 0
  6. 2026Tighter Information-Theoretic Generalization Bounds via a Novel Class of Change of Measure Inequalitiescited by 0
  7. 2026Bounded-Rationality, Hedging, and Generalizationcited by 0