Predictability: A Fine-Grained Privacy Measure Beyond Differential Privacy

Paper: 2606.20546 Authors: Linda Lu, Karthik Sridharan Categories: cs.LG

The Gap

Differential privacy (DP) guarantees that algorithm outputs look almost the same whether any single individual’s data is included or not. This worst-case bound holds even against an attacker who knows every other row in the dataset. But that strength is also its weakness: DP forces you to add noise large enough to protect against the most extreme possible attacker, which can crush accuracy for common cases. Prior attempts to relax DP (e.g., local DP, concentrated DP, or Renyi DP) still operate on the same indistinguishability principle — they only soften the notion of “almost the same” but don’t model what the attacker already knows or which specific secrets she cares about. The real gap is that no existing framework explicitly takes the attacker’s core knowledge (a compromised portion of the data) and sensitive query family as inputs to the privacy definition. This paper fills that gap by proposing predictability: the incremental gain in an attacker’s ability to predict a specific sensitive attribute after seeing the algorithm’s output, beyond what she could already infer from compromised data alone.

+--------------------------------------------------+
| Problem: DP is worst-case, ignores attacker prior |
| and target query, forces over-protection          |
+--------------------------------------------------+
          |
          v
+--------------------------------------------------+
| Assumption: Attacker has compromised data D_c     |
| from a stochastic process, and targets a specific |
| sensitive query L (e.g., a binary attribute)      |
+--------------------------------------------------+
          |
          v
+--------------------------------------------------+
| Method: Predictability = reduction in attacker's  |
| prediction error for L when given algorithm output|
| A, compared to using D_c alone                    |
+--------------------------------------------------+
          |
          v
+--------------------------------------------------+
| Evidence: Shows predictability and DP are         |
| incomparable (each can be small while other large)|
| Asymptotic analysis via GMM for stationary,       |
| ergodic, mixing processes. Provides perturbation  |
| scheme for ERM calibrated to predictability.      |
+--------------------------------------------------+
          |
          v
+--------------------------------------------------+
| Conclusion: Predictability is a fine-grained      |
| privacy measure complementary to DP, tailored to  |
| specific attacker models and sensitive queries    |
+--------------------------------------------------+

The Increment

One sentence: Before this paper, privacy guarantees were either worst-case indistinguishability (DP) or ad-hoc heuristics; after it, we have a principled, fine-grained measure that explicitly accounts for the attacker’s partial knowledge and the specific sensitive query, and can be analyzed asymptotically with a general statistical toolkit.

Core Mechanism

The paper defines predictability in a general setting. Let the full dataset be generated by a stochastic process. A portion of the data, (D_c), is compromised — the attacker sees it. The attacker wants to predict a sensitive function (L) of the unknown individuals (e.g., a binary label). She can form a prediction using only (D_c) (e.g., an estimator (\hat{L}_0) with some error). Then an algorithm (e.g., empirical risk minimizer) outputs a statistic (A) that depends on the entire dataset, including (L). The attacker updates her prediction to (\hat{L}_1) using both (D_c) and (A). The predictability leakage is the reduction in prediction error: (\text{Pred} = \mathbb{E}[\ell(L, \hat{L}_0)] - \mathbb{E}[\ell(L, \hat{L}_1)]) for some loss (\ell) (e.g., squared error or 0-1 loss). The larger this reduction, the more the algorithm leaks about that specific sensitive query.

To make this computable, the authors assume (D_c) is generated by a stationary, ergodic, mixing process. They use the Generalized Method of Moments (GMM) to derive the asymptotic distribution of the algorithm’s output (A) conditioned on (D_c) and (L). This allows them to compute the limiting predictability for a family of queries. They then design a predictability-calibrated perturbation scheme for ERM: instead of adding noise proportional to global sensitivity (as in DP), they add noise proportional to the inverse of the derivative of the predictability with respect to the output — essentially adding just enough noise to keep predictability below a user-specified threshold.

+-------------------+       +-------------------+
| Compromised Data  |       | Full Dataset      |
| D_c (attacker     |       | (includes         |
|  already knows)   |       |  sensitive label   |
|                   |       |  L for unknown)    |
+-------------------+       +-------------------+
         |                           |
         |                           v
         v               +-------------------+
+-------------------+   | ERM Training      |
| Attacker's        |   | (algorithm)       |
| Initial Predict   |   | Produces output A |
| using D_c only    |   +-------------------+
| error0            |          |
+-------------------+          |
         |                     |
         |                     v
         +-------------------+
         | Attacker updates  |
         | prediction using  |
         | D_c and A         |
         | error1            |
         +-------------------+
                   |
                   v
         +-------------------+
         | Predictability =  |
         | error0 - error1   |
         +-------------------+

Calibrated Perturbation:
+-------------------+     +-------------------+
| Predictability    |     | Add noise scale   |
| target threshold  | --> | proportional to   |
| tau               |     | 1 / dPred/dA      |
+-------------------+     +-------------------+
                              |
                              v
                    +-------------------+
                    | Noisy output A_tilde |
                    +-------------------+

Now let me explain this using a structural metaphor: think of the attacker as a detective investigating a crime. The compromised data (D_c) are eyewitness accounts from a few bystanders. The sensitive query (L) is whether the suspect is guilty (binary). The detective forms an initial suspicion based solely on the eyewitnesses (error0). Later, the police release a forensic report (algorithm output (A)). The detective updates her belief (error1). The predictability is how much the forensic report improves her accuracy beyond the eyewitnesses. The forensic report is generated by a lab that can choose how much detail to reveal — they can add noise to the report to limit the improvement. In DP, the lab would add noise so that even the most skilled detective with unlimited resources gains nothing. But in the predictability framework, the lab only cares about this specific detective with these specific eyewitnesses and this specific question about guilt. The lab uses a statistical model (GMM) to calculate how much the detective would improve if the report were perfectly accurate, then adds Gaussian noise just enough to cap that improvement to a target level. The analogy is load-bearing: each component maps — D_c (eyewitness accounts), L (guilt), A (forensic report), improvement (predictability), perturbation (noise in report), GMM (statistical reasoning about how much the detective can learn from reports of this type). Without the metaphor, the reader is back to staring at the GMM equations.

Key Concepts

• Predictability: It is not a property of the algorithm alone, but of the triple (algorithm, attacker’s core knowledge, sensitive query). Concretely, suppose Alice’s data is in a medical database. The attacker has already seen 90% of the records (compromised data) and wants to know whether Alice has diabetes (sensitive binary). Using only the compromised data, the attacker predicts “yes” with 70% confidence. After seeing the algorithm’s output (e.g., a regression coefficient), she updates to 95% confidence. The predictability leakage is the 25 percentage point gain. Note: this gain can be large even if the algorithm is differentially private, if the compromised data already gives a good base. Conversely, predictability can be small even if DP is not satisfied, if the attacker’s prior is weak and the output reveals little beyond it.

• Incomparability with DP: The paper proves that predictability and DP are not orderings — you can have an algorithm with small ((\varepsilon)) DP guarantee but large predictability, and vice versa. Example: A deterministic algorithm that outputs a constant has perfect DP ((\varepsilon=0)) but zero predictability (no gain). A non-private algorithm that outputs the exact sample mean might leak a lot about a specific individual’s value if the compromised data already implies that value, so DP is large but predictability is small. This means you cannot replace DP with predictability; they measure different things.

• GMM for Privacy: Generalized Method of Moments is usually a tool for estimating parameters from data with dependent errors. Here, the authors use it to approximate the distribution of the algorithm’s output as a function of the unknown sensitive label, conditional on the compromised data. This gives them a handle on the asymptotic predictability without assuming the data are i.i.d. — they only need stationarity, ergodicity, and mixing. The clever twist is using the moment conditions to capture the attacker’s optimal prediction rule.

Framework Shift

The old way (DP) treats privacy as a property of the mechanism in a vacuum: “no matter what the attacker knows, the output is almost independent of any single row.” The new way (predictability) treats privacy as a function of an explicit attacker model: “given that the attacker already knows these specific rows and cares about this specific query, how much does the output help?”

Before (mainstream approach):        After (this paper):
+----------------------------+       +----------------------------+
| Dataset D                  |       | Compromised D_c + Query Q  |
|        |                   |       |        |                   |
|        v                   |       |        v                   |
| Mechanism M (e.g., DP-SGD)|       | Mechanism M (e.g., ERM)    |
|        |                   |       |        |                   |
|        v                   |       |        v                   |
| Output A                   |       | Output A                   |
|        |                   |       |        |                   |
| Guarantee: for all D,D'   |       | Measure: Pred(A|D_c,Q)     |
| differing in one row,     |       | = attacker's reduction in  |
| M(D) ~= M(D')             |       | prediction error for Q     |
| (indistinguishability)    |       | given A vs. D_c alone      |
+----------------------------+       +----------------------------+

One sentence: From worst-case indistinguishability independent of attacker knowledge, to attacker-aware informational gain that depends on what the attacker already knows and what she wants to predict.

Expert Assessment

Problem choice: Real and well-motivated. The DP community has long acknowledged the “over-protection” problem, but few have proposed a rigorous alternative that explicitly models attacker background knowledge. This paper directly addresses that gap, and the incomparability result is a strong conceptual contribution.

Method maturity: Clever insight — using predictability as the primitive and GMM for asymptotic analysis is elegant. However, the theory assumes the compromised data is generated by a stationary, ergodic, mixing process, which may not hold for real-world attack scenarios (e.g., adversarial or non-stationary compromises). The calibrated perturbation scheme is a nice proof of concept but is not evaluated experimentally; the paper is entirely theoretical. A simpler approach might have been to directly use the influence function of the estimator, but that would have been less general.

Experimental integrity: No experiments. The paper is theoretical, so there are no numbers to check. That is acceptable for a theory paper, but it means the practical utility is unproven. The perturbation scheme is derived asymptotically; we don’t know how it behaves in finite samples or under model misspecification.

Writing quality: The abstract and introduction are clear. The main body gets dense, especially the GMM sections. The authors sometimes assume familiarity with moment conditions and mixing processes without enough intuition. Rewriting Section 3 (the definition of predictability) to include more concrete examples and fewer measure-theoretic details would elevate the whole paper.

Verdict: weak accept — The conceptual contribution is significant and the incomparability result is a genuine insight. But the lack of experiments and the heavy asymptotic assumptions limit immediate applicability.

Takeaways

• For practitioners: The idea of measuring privacy as predictive gain can be directly applied to any scenario where you have a model of the attacker’s prior distribution. Instead of blindly adding noise to meet a DP budget, you can calibrate noise to the actual threat: if the attacker already knows 99% of the data, you need much less noise to prevent them from learning the last 1% than if they knew nothing. This could significantly improve utility in settings like federated learning with partially public data.
• Conceptual tool: The incomparability result is a useful reminder that DP is not a universal privacy panacea. When auditing a system, you should consider both DP and predictability — they measure different risks.
• Analytical framework: The GMM-based asymptotic analysis can be borrowed to analyze the privacy leakage of other algorithms that can be expressed as solutions to moment conditions (e.g., M-estimators, GANs). This gives a statistical toolkit for privacy analysis beyond DP.
• One concrete takeaway: If you are using ERM on a dataset where a subset is already public, you can compute the predictability for each sensitive feature and add noise only to the extent needed to keep that gain below a threshold. The paper provides a first-order asymptotic formula for the required noise level. This is directly stealable.