# An Accuracy-Information Tradeoff for Loss-Difference Conditional Mutual Information

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 22 of its 50 references that are in the map.
- First posted on arXiv 6 Oct 2026.

## Builds on (most cited first, 22 of 22)

- [Membership Inference Attacks From First Principles](https://mlsanity.com/paper/2112.03570/) (2021)
- [Private Stochastic Convex Optimization with Optimal Rates](https://mlsanity.com/paper/1908.09970/) (2019)
- [Reasoning About Generalization via Conditional Mutual Information](https://mlsanity.com/paper/2001.09122/) (2020)
- [Privacy Auditing with One (1) Training Run](https://mlsanity.com/paper/2305.08846/) (2023)
- [Differentially Private Empirical Risk Minimization: Efficient Algorithms and Tight Error Bounds](https://mlsanity.com/paper/1405.7085/) (2014)
- [When is Memorization of Irrelevant Training Data Necessary for High-Accuracy Learning?](https://mlsanity.com/paper/2012.06421/) (2020)
- [Tight Lower Bounds for Differentially Private Selection](https://mlsanity.com/paper/1704.03024/) (2017)
- [New Lower Bounds for Private Estimation and a Generalized Fingerprinting Lemma](https://mlsanity.com/paper/2205.08532/) (2022)
- [Towards a Unified Information-Theoretic Framework for Generalization](https://mlsanity.com/paper/2111.05275/) (2021)
- [Tighter Information-Theoretic Generalization Bounds from Supersamples](https://mlsanity.com/paper/2302.02432/) (2023)
- [Adapting to Function Difficulty and Growth Conditions in Private Optimization](https://mlsanity.com/paper/2108.02391/) (2021)
- [Limitations of Information-Theoretic Generalization Bounds for Gradient Descent Methods in Stochastic Convex Optimization](https://mlsanity.com/paper/2212.13556/) (2022)
- [Information Theoretic Lower Bounds for Information Theoretic Upper Bounds](https://mlsanity.com/paper/2302.04925/) (2023)
- [Bounding Membership Inference](https://mlsanity.com/paper/2202.12232/) (2022)
- [Information Complexity of Stochastic Convex Optimization: Applications to Generalization and Memorization](https://mlsanity.com/paper/2402.09327/) (2024)
- [Privacy Risk in Machine Learning: Analyzing the Connection to Overfitting](https://mlsanity.com/paper/1709.01604/) (2017)
- [Modelling and Quantifying Membership Information Leakage in Machine Learning](https://mlsanity.com/paper/2001.10648/) (2020)
- [Sample-Conditioned Hypothesis Stability Sharpens Information-Theoretic Generalization Bounds](https://mlsanity.com/paper/2310.20102/) (2023)
- [Trade-offs in Data Memorization via Strong Data Processing Inequalities](https://mlsanity.com/paper/2506.01855/) (2025)
- [Generalization Bounds via Conditional f-Information](https://mlsanity.com/paper/2410.22887/) (2024)
- [On Traceability in ℓp Stochastic Convex Optimization](https://mlsanity.com/paper/2502.17384/) (2025)
- [Tighter CMI-Based Generalization Bounds via Stochastic Projection and Quantization](https://mlsanity.com/paper/2510.23485/) (2025)

## Abstract (arXiv)

Loss-difference conditional mutual information (ld-CMI) uses the smallest of the standard observations in the supersample hierarchy of generalization bounds: it measures what a learner's loss differences reveal about which candidate of each pair it was trained on. Accuracy is known to force information into the model; data processing does not carry such lower bounds to losses. We show, by bounding three moments of the loss differences, that accuracy also forces ld-CMI. For linear predictors with a smooth convex loss of nonzero slope at zero, such as the logistic loss, plus a regularizer whose curvature and growth are both of power r≥2, on product distributions over a scaled sign cube in dimension at least linear in n, every proper learner with expected excess risk at most varepsilon on these distributions at the optimal sample size nasympvarepsilon-2+2/r has worst-case ld-CMI of order n bits, and Theta(n/(1+(τ/varepsilon)2)) bits under Gaussian noise of standard deviation τ on the loss differences. The same holds without a regularizer, at nasympvarepsilon-2. Consequently, range-scaled ld-CMI bounds cannot vanish on these distributions, although every proper learner's generalization gap is O(n-1/2). We also show that model-level information does not determine noisy loss-difference information, and that the growth, slope and dimension conditions are needed, the last up to a logarithm.