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 attacker'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 equivalence: In the worst case (all individuals except one are compromised, and all binary queries are treated as sensitive), predictability implies mutual-information DP.
- Fine-grained guarantees: More generally, predictability provides a finer privacy metric tailored to specific sensitive information and specific attacker models.
Predictability measures privacy leakage as the attacker's incremental ability to predict unknown individuals' sensitive information after observing the algorithm's output, beyond what can already be inferred from the compromised data.
Key Findings
Technical Contribution
The authors use the generalized method of moments (GMM) to introduce a general framework for analyzing asymptotic predictability when compromised data is generated by stationary, ergodic, mixing processes. Building on this analysis, they derive predictability-calibrated output perturbation schemes for empirical risk minimization (ERM). The approach is complementary to DP and can be combined with DP to provide fine-grained privacy control.
--- *Auto-collected on 2026-06-21*