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

arXiv: https://arxiv.org/abs/2206.11042 · HTML: https://mlsanity.com/paper/2206.11042/

## 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 (most cited first, 18 of 18)

- [Train faster, generalize better: Stability of stochastic gradient descent](https://mlsanity.com/paper/1509.01240/) (2015)
- [Learning Models with Uniform Performance via Distributionally Robust Optimization](https://mlsanity.com/paper/1810.08750/) (2018)
- [Information-theoretic analysis of generalization capability of learning algorithms](https://mlsanity.com/paper/1705.07809/) (2017)
- [Tightening Mutual Information Based Bounds on Generalization Error](https://mlsanity.com/paper/1901.04609/) (2019)
- [How much does your data exploration overfit? Controlling bias via information usage](https://mlsanity.com/paper/1511.05219/) (2015)
- [Chaining Mutual Information and Tightening Generalization Bounds](https://mlsanity.com/paper/1806.03803/) (2018)
- [Generalization Error Bounds Via R'enyi-, f-Divergences and Maximal Leakage](https://mlsanity.com/paper/1912.01439/) (2019)
- [Generalization Bounds via Information Density and Conditional Information Density](https://mlsanity.com/paper/2005.08044/) (2020)
- [Minimum Excess Risk in Bayesian Learning](https://mlsanity.com/paper/2012.14868/) (2020)
- [Rate-Distortion Theoretic Generalization Bounds for Stochastic Learning Algorithms](https://mlsanity.com/paper/2203.02474/) (2022)
- [Jensen-Shannon Information Based Characterization of the Generalization Error of Learning Algorithms](https://mlsanity.com/paper/2010.12664/) (2020)
- [Information-Theoretic Bounds on the Moments of the Generalization Error of Learning Algorithms](https://mlsanity.com/paper/2102.02016/) (2021)
- [Tighter Expected Generalization Error Bounds via Convexity of Information Measures](https://mlsanity.com/paper/2202.12150/) (2022)
- [Rate-Distortion Analysis of Minimum Excess Risk in Bayesian Learning](https://mlsanity.com/paper/2105.04180/) (2021)
- [Distributionally Robust Games: f-Divergence and Learning](https://mlsanity.com/paper/1702.05371/) (2017)
- [Generalizing Bottleneck Problems](https://mlsanity.com/paper/1802.05861/) (2018)
- [Characterizing the Generalization Error of Gibbs Algorithm with Symmetrized KL information](https://mlsanity.com/paper/2107.13656/) (2021)
- [Distributionally Robust Variance Minimization: Tight Variance Bounds over f-Divergence Neighborhoods](https://mlsanity.com/paper/2009.09264/) (2020)

## Built on by (most cited first, 7 of 7)

- [Data-dependent Generalization Bounds via Variable-Size Compressibility](https://mlsanity.com/paper/2303.05369/) (2023)
- [Generalization Analysis of Machine Learning Algorithms via the Worst-Case Data-Generating Probability Measure](https://mlsanity.com/paper/2312.12236/) (2023)
- [The Method of Gaps: Exact Expressions for the Generalization Error of Supervised Learning Algorithms](https://mlsanity.com/paper/2411.12030/) (2024)
- [Proofs for Folklore Theorems on the Radon-Nikodym Derivative](https://mlsanity.com/paper/2501.18374/) (2025)
- [Empirical Risk Minimization with f-Divergence Regularization](https://mlsanity.com/paper/2601.13191/) (2026)
- [Tighter Information-Theoretic Generalization Bounds via a Novel Class of Change of Measure Inequalities](https://mlsanity.com/paper/2602.07999/) (2026)
- [Bounded-Rationality, Hedging, and Generalization](https://mlsanity.com/paper/2605.15340/) (2026)

## 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.