Predictability as a Fine-Grained Measure for Privacy

Summary

This post summarizes the arXiv paper 2506.17581 by Linda Lu and Karthik Sridharan, which introduces "privacy via predictability," a fine-grained alternative to differential privacy (DP). While DP offers worst-case guarantees against the most informed attackers—often at a steep privacy-accuracy cost—the predictability framework explicitly incorporates attacker core knowledge, the already-revealed portion of the dataset generated by a stochastic process, and a specified family of queries. Privacy leakage is measured as the attacker's additional predictive ability over sensitive information after observing an algorithm's output, beyond what the revealed data alone allows. The authors show predictability and DP are generally incomparable, but in the worst case (one unrevealed individual, all binary queries sensitive) predictability implies mutual-information DP. They develop a generalized method of moments (GMM) framework for asymptotic predictability analysis when revealed data comes from stationary, ergodic, mixing processes, and derive predictability-calibrated output perturbation schemes for empirical risk minimization (ERM). The approach is complementary to DP and can be combined with it for fine-grained privacy control.