# On-Average KL-Privacy and its equivalence to Generalization for Max-Entropy Mechanisms

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 May 2016.

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

- [Information-theoretic generalization bounds for black-box learning algorithms](https://mlsanity.com/paper/2110.01584/) (2021)
- [Limitations of Information-Theoretic Generalization Bounds for Gradient Descent Methods in Stochastic Convex Optimization](https://mlsanity.com/paper/2212.13556/) (2022)
- [Federated Learning in Non-IID Settings Aided by Differentially Private Synthetic Data](https://mlsanity.com/paper/2206.00686/) (2022)
- [Certifiably Robust Interpretation via Renyi Differential Privacy](https://mlsanity.com/paper/2107.01561/) (2021)
- [Initialization Matters: Privacy-Utility Analysis of Overparameterized Neural Networks](https://mlsanity.com/paper/2310.20579/) (2023)
- [Active Privacy-utility Trade-off Against a Hypothesis Testing Adversary](https://mlsanity.com/paper/2102.08308/) (2021)
- [Active Privacy-Utility Trade-off Against Inference in Time-Series Data Sharing](https://mlsanity.com/paper/2202.05833/) (2022)
- [Majority Vote for Distributed Differentially Private Sign Selection](https://mlsanity.com/paper/2209.04419/) (2022)
- [Differential privacy from axioms](https://mlsanity.com/paper/2511.21876/) (2025)
- [Stabilizing Private LASSO under Heterogeneous Covariates via Anisotropic Objective Perturbation](https://mlsanity.com/paper/2605.01492/) (2026)

## Abstract (arXiv)

We define On-Average KL-Privacy and present its properties and connections to differential privacy, generalization and information-theoretic quantities including max-information and mutual information. The new definition significantly weakens differential privacy, while preserving its minimalistic design features such as composition over small group and multiple queries as well as closeness to post-processing. Moreover, we show that On-Average KL-Privacy is **equivalent** to generalization for a large class of commonly-used tools in statistics and machine learning that samples from Gibbs distributions---a class of distributions that arises naturally from the maximum entropy principle. In addition, a byproduct of our analysis yields a lower bound for generalization error in terms of mutual information which reveals an interesting interplay with known upper bounds that use the same quantity.