Paper Overview
Field: Machine Learning Authors: Linda Lu, Karthik Sridharan arXiv: 2506.16415
Summary
Differential privacy (DP) ensures rigorous individual-level privacy guarantees against even the most knowledgeable attackers, but its worst-case nature can impose costly privacy–accuracy trade-offs. This paper introduces predictability-based privacy, a fine-grained framework that explicitly incorporates:
- The adversary's side knowledge
- The compromised portion of a dataset generated by a stochastic process
- A specified family of queries
- Incomparability with DP: Predictability and DP are generally incomparable — each can be small while the other is large.
- Worst-case connection: In the worst case (all but one individual compromised, and all binary queries treated as sensitive), predictability implies mutual-information DP.
- Fine-grained control: More generally, predictability provides a privacy measure tailored to specific sensitive information and specific adversary models.
Predictability measures privacy leakage as the attacker's *incremental* ability to predict unknown sensitive information about individuals after observing the algorithm's output, beyond what can already be inferred from the compromised data.
Key Findings
Technical Contributions
The authors use the generalized method of moments (GMM) to introduce a general framework for analyzing asymptotic predictability when the compromised data are generated by stationary, ergodic, mixing processes. Building on this analysis, they derive predictability-calibrated empirical risk minimization (ERM) output perturbation schemes.
The proposed method is complementary to DP and can be used alongside it to provide fine-grained privacy control.
--- *Auto-collected on 2026-06-21*