Paper Overview
Field: ML Authors: Linda Lu, Karthik Sridharan Published: 2025-06-20 arXiv: 2506.16801
Abstract
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.
- arXiv page: https://arxiv.org/abs/2506.16801
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.
The authors show that predictability and DP are generally incomparable: each can be small while the other is large. However, in the worst-case regime — all but one individual compromised, and all binary queries sensitive — predictability implies mutual-information DP. More broadly, predictability provides a finer-grained privacy measure tailored to specific sensitive information and specific attacker models.
The authors also build a general framework using the generalized method of moments (GMM) to analyze asymptotic predictability when the compromised data come from stationary, ergodic, mixing processes. This yields a predictability-calibrated output perturbation scheme for empirical risk minimization (ERM), which complements DP and can be combined with it for fine-grained privacy control.