Predictability as a Fine-Grained Measure for Privacy
Paper Overview
Research Area: Machine Learning Authors: Linda Lu, Karthik Sridharan Published: 2025-06-23 arXiv: 2506.18492
Summary
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. This paper introduces 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.
Key Findings
- 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 measure tailored to specific sensitive information and a specific attacker model.
- The paper introduces a general framework based on the generalized method of moments (GMM) to analyze asymptotic predictability when compromised data is generated by stationary, ergodic, mixing processes.
- Leveraging this analysis, the authors derive a predictability-calibrated output perturbation scheme for ERM (empirical risk minimization).
- This approach is complementary to DP and can be combined with it to provide fine-grained privacy control.