Predictability as a Fine-Grained Measure for Privacy

Forum topic · 小凯 · 2026-06-22

Summary

This post summarizes an arXiv paper (2506.17581) by Linda Lu and Karthik Sridharan introducing 'privacy via predictability,' a fine-grained alternative to differential privacy (DP). Instead of worst-case guarantees, predictability measures privacy leakage as the additional gain an attacker achieves in predicting an individual's sensitive information after observing an algorithm's output, beyond what can be inferred from an already-released dataset. The framework explicitly incorporates the attacker's side knowledge, the portion of the data generated by a stochastic process, and a specified family of queries. The authors show that predictability and DP are generally incomparable, but in the worst case—when only one person is unreleased and all binary queries are sensitive—predictability implies mutual-information DP. They also present a general framework using the generalized method of moments (GMM) to analyze asymptotic predictability when released 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.

Paper Overview

Research area: cs.LG Authors: Linda Lu, Karthik Sridharan Published: 2026-06-21 arXiv: 2506.17581

Abstract

Differential privacy (DP) ensures rigorous individual-level privacy guarantees even against the most informed attackers, but its worst-case nature can lead to costly privacy-accuracy trade-offs. This paper introduces privacy via predictability, a fine-grained framework that explicitly incorporates:

the attacker's side knowledge,
the portion of the already-released dataset generated by a stochastic process,
and a specified family of queries.

Predictability measures privacy leakage as the additional gain an attacker achieves in predicting an individual's unknown sensitive information after observing the algorithm's output, compared to what can be inferred from the released data alone.

Key findings

Predictability and DP are generally incomparable: either one can be much smaller than the other.
In the worst case—when only one person remains unreleased and all binary queries are considered sensitive—predictability implies mutual-information DP.
More generally, predictability provides a finer-grained privacy measure tailored to specific sensitive information and specific attacker models.

Methodology

The authors introduce a general framework based on the generalized method of moments (GMM) to analyze asymptotic predictability when the released data is generated by stationary, ergodic, mixing processes. Building on this analysis, they derive predictability-calibrated output perturbation schemes for empirical risk minimization (ERM).

Conclusion

This approach is complementary to DP and can be used alongside it to achieve fine-grained privacy control.

---

*Auto-collected on 2026-06-21*