Privacy via Predictability: A Fine-Grained Measure Beyond Differential Privacy

Forum topic · 小凯 · 2026-06-20

Summary

Researchers Linda Lu and Karthik Sridharan propose 'privacy via predictability,' a fine-grained privacy framework presented in arXiv paper 2506.16801 (June 2025). Unlike differential privacy (DP), which offers worst-case guarantees against fully informed attackers at a steep privacy-accuracy cost, predictability explicitly accounts for an attacker's core knowledge, a compromised portion of the dataset generated by a stochastic process, and a specified family of queries. Privacy leakage is measured as the incremental gain in the attacker's ability to predict sensitive information about unknown individuals after observing an algorithm's output, beyond what the compromised data already reveals. The authors prove that predictability and DP are generally incomparable—either can be small while the other is large—though in the worst case (all but one record compromised, all binary queries sensitive), predictability implies mutual-information DP. They further develop a generalized method of moments framework for asymptotic predictability when compromised data comes from stationary, ergodic, mixing processes, yielding a predictability-calibrated output perturbation scheme for empirical risk minimization that composes with DP for fine-grained privacy control.

Overview

Field: Machine Learning
Authors: Linda Lu, Karthik Sridharan
Published: 2025-06-20
arXiv: 2506.16801

Abstract (translated)

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.

The authors show that predictability and DP are generally incomparable: each can be small while the other is large, and vice versa. However, in the worst-case setting—where all records but one are compromised and all binary queries are sensitive—predictability implies mutual-information DP. More broadly, predictability offers 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 comes from stationary, ergodic, mixing processes. From this they derive a predictability-calibrated output perturbation scheme for empirical risk minimization (ERM). This approach is complementary to DP and can be used alongside it for fine-grained privacy control.

Original Abstract (excerpt)

> 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. We introduce 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. We show that predictability and DP are generally incomparable: each can be small while the other is large...

Full paper: https://arxiv.org/abs/2506.16801