# Predictability as a Fine-Grained Measure for Privacy

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 16 of its 54 references that are in the map.
- First posted on arXiv 18 Jun 2026.

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

- [Communication-Efficient Learning of Deep Networks from Decentralized Data](https://mlsanity.com/paper/1602.05629/) (2016)
- [Deep Learning with Differential Privacy](https://mlsanity.com/paper/1607.00133/) (2016)
- [Extracting Training Data from Large Language Models](https://mlsanity.com/paper/2012.07805/) (2020)
- [Deep Leakage from Gradients](https://mlsanity.com/paper/1906.08935/) (2019)
- [Renyi Differential Privacy](https://mlsanity.com/paper/1702.07476/) (2017)
- [Reasoning About Generalization via Conditional Mutual Information](https://mlsanity.com/paper/2001.09122/) (2020)
- [Deep Learning with Label Differential Privacy](https://mlsanity.com/paper/2102.06062/) (2021)
- [Distributed Differential Privacy via Shuffling](https://mlsanity.com/paper/1808.01394/) (2018)
- [R-GAP: Recursive Gradient Attack on Privacy](https://mlsanity.com/paper/2010.07733/) (2020)
- [Differential Privacy as a Mutual Information Constraint](https://mlsanity.com/paper/1608.03677/) (2016)
- [LinkedIn's Audience Engagements API: A Privacy Preserving Data Analytics System at Scale](https://mlsanity.com/paper/2002.05839/) (2020)
- [Attribute Privacy: Framework and Mechanisms](https://mlsanity.com/paper/2009.04013/) (2020)
- [Blowfish Privacy: Tuning Privacy-Utility Trade-offs using Policies](https://mlsanity.com/paper/1312.3913/) (2013)
- [OSDP: Optimal Sharded Data Parallel for Distributed Deep Learning](https://mlsanity.com/paper/2209.13258/) (2022)
- [Inferential Privacy Guarantees for Differentially Private Mechanisms](https://mlsanity.com/paper/1603.01508/) (2016)
- [Tumult Analytics: a robust, easy-to-use, scalable, and expressive framework for differential privacy](https://mlsanity.com/paper/2212.04133/) (2022)

## Abstract (arXiv)

Differential privacy (DP) ensures rigorous individual-level privacy guarantees against even the most knowledgeable attackers, but its worst-case nature can impose a costly privacy-accuracy tradeoff. We introduce privacy via predictability, a fine-grained framework that explicitly incorporates the attacker's core knowledge, a compromised portion of the dataset generated by a stochastic process, and a specified family of queries. Predictability measures privacy leakage as the incremental gain in an attacker's ability to predict sensitive information about unknown individuals after observing the algorithm's output, beyond what can already be inferred from the compromised data. We show that predictability and DP are generally incomparable: each can be small while the other is large. However, in the worst-case regime where all but one individual is compromised, and all binary queries are considered sensitive, predictability implies mutual-information DP. More generally, predictability provides a finer-grained privacy metric tailored to specific sensitive information and specific attacker models. We introduce a general framework, using the generalized method of moments (GMM), to analyze asymptotic predictability when the compromised data is generated by a stationary, ergodic, mixing process. Using this analysis, we derive a predictability-calibrated output perturbation scheme for ERM. Our approach is complementary to DP and can be used alongside DP to provide fine-grained privacy control.