Privacy via Predictability: A Fine-Grained Alternative to Differential Privacy

Forum topic · 小凯 · 2026-06-23

Summary

A paper by Linda Lu and Karthik Sridharan (arXiv:2506.18492, June 2025) introduces "privacy via predictability," a fine-grained privacy framework that complements differential privacy (DP). While DP offers worst-case guarantees against the most knowledgeable attackers, it can impose costly privacy-accuracy tradeoffs. Predictability instead quantifies leakage as the incremental improvement in an attacker's ability to predict sensitive information about unknown individuals after observing an algorithm's output, beyond what is already inferable from compromised data. The framework explicitly incorporates the attacker's core knowledge, a compromised portion of the dataset generated by a stochastic process, and a specified family of queries. The authors show predictability and DP are generally incomparable—each can be small while the other is large—though in the worst-case regime (all but one individual compromised, all binary queries sensitive), predictability implies mutual-information DP. They also develop a generalized method of moments (GMM) framework for analyzing asymptotic predictability when compromised data arises from stationary, ergodic, mixing processes, and derive a predictability-calibrated output perturbation scheme for empirical risk minimization (ERM), usable alongside DP for fine-grained privacy control.

Overview

Field: Machine Learning Authors: Linda Lu, Karthik Sridharan Published: 2025-06-23 arXiv: 2506.18492

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.

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.

Key Findings

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 regime, where all but one individual is compromised and all binary queries are treated as sensitive, predictability implies mutual-information DP.
Fine-grained control: More generally, predictability provides a finer-grained privacy measure tailored to specific sensitive information and specific attacker models.

Technical Contributions

The paper uses 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, the authors derive a predictability-calibrated output perturbation scheme for ERM (empirical risk minimization).

Conclusion

The proposed method is complementary to DP and can be used together with DP to provide fine-grained privacy control.

---

*Auto-collected on 2026-06-23*