Predictability as a Fine-Grained Measure for Privacy

Traditional differential privacy (DP) is often criticized for its rigid, worst-case nature, which can lead to excessive noise and poor model performance. The authors propose a new framework, 'privacy via predictability,' to address this. Instead of protecting against a hypothetical attacker who knows everything about the dataset except for one individual, this approach models the attacker as having 'core knowledge'—a compromised subset of data generated by a specific stochastic process. The authors define privacy as the degree to which an algorithm's output increases an attacker's ability to predict sensitive information about individuals not present in the compromised subset.

The authors demonstrate that predictability and DP are fundamentally incomparable: an algorithm can be highly private under one metric while failing the other. However, in the extreme case where an attacker has compromised all but one individual, predictability implies mutual-information differential privacy. To make this metric practical, the authors provide a framework using the Generalized Method of Moments (GMM) to analyze asymptotic predictability. This allows researchers to calculate privacy leakage when the compromised data follows a stationary, ergodic, mixing process. Finally, they derive a 'predictability-calibrated' output perturbation scheme for Empirical Risk Minimization (ERM) that adapts noise based on loss curvature and the attacker's specific knowledge, offering better accuracy than standard isotropic perturbation.

This work provides a more nuanced way to think about privacy in real-world systems where data breaches are often partial or targeted. By tailoring privacy guarantees to specific sensitive queries and known attacker capabilities, system designers can avoid the 'one-size-fits-all' penalty of DP. This approach is intended to be complementary to DP, allowing for a layered defense where predictability offers fine-grained control for specific sensitive information while DP maintains a baseline of individual-level protection.