Reliable Estimation of Differential Privacy under Selection Bias

Valentin Dorseuil, Meenatchi Sundaram Muthu Selva Annamalai, Jamal Atif, Olivier Cappé, Nicolas PapernotarXiv 2026 · arXiv

TL;DR

Many statistical audits used to verify Differential Privacy (DP) guarantees are technically "invalid" because they cherry-pick the most successful attack parameters without adjusting for statistical noise. This paper identifies a widespread "selection bias" in prior research and introduces robust statistical corrections—like K-fold selection and the DKW inequality—to ensure privacy lower bounds are reliable and don't trigger false alarms.

What Problem Does This Paper Address?

Differential Privacy (DP) is the gold standard for protecting individual data in machine learning. It provides a mathematical upper bound on how much information can leak. To verify these guarantees, researchers perform "privacy audits" using Membership Inference Attacks (MIAs). An MIA tries to guess if a specific data point was in the training set; if the attack is too successful, it provides an empirical lower bound on the actual privacy leakage.

The problem? To get the "tightest" (highest) lower bound, auditors often test many different decision thresholds and report only the one that performed best. While this seems intuitive, it introduces selection bias. By choosing the threshold after seeing which one worked best on a specific sample of data, auditors inadvertently overfit to statistical noise. This leads to "inflated" lower bounds that claim a privacy violation exists when, in reality, the mechanism might be perfectly fine.

Methods

The authors formalize privacy auditing as a parametric statistical estimation problem and adapt tools from the "multiple-comparisons" and "post-selection inference" literature to fix the bias:

  • The "Max" (Invalid) Method: The status quo, where the best threshold is chosen from the same data used to calculate the bound.
  • Bonferroni Correction: A classic approach that divides the allowed error rate (significance level) by the number of thresholds tested. It’s simple but can be overly conservative.
  • DKW Inequality: A "distribution-free" method that provides a uniform bound over all possible thresholds simultaneously. It’s robust but struggles in the "tails" (very low or very high error regions).
  • K-Fold Selection: Borrowed from cross-validation, this splits the data into $K$ parts. It selects the threshold on one part and computes the bound on the others, ensuring the selection is independent of the final calculation.
  • Holdout Sets: Splitting the data into two: one to find the "best" attack and one to measure it.

Datasets

The researchers evaluated these methods using both theoretical simulations and real-world benchmarks:

  • Synthetic Gaussian Distributions: Used to simulate a "perfect" attack where the ground truth privacy parameter ($\mu$) is known, allowing for precise measurement of "miscoverage" (how often the lower bound is wrong).
  • Fashion-MNIST & CIFAR-10: Standard image datasets used to audit Deep Learning models (CNNs and Wide ResNets) trained with DP-SGD.
  • Housing Dataset: Used to audit models in the "hidden state" threat model.

Key Insights and Ideas

  • Noise is the Culprit: Even if a privacy mechanism is perfectly implemented, empirical samples will always have some variance. If you look at 100 different thresholds, one will look "better" just by pure luck.
  • The "False Alarm" Risk: An invalid audit is dangerous because it might flag a compliant implementation as a privacy failure. In a regulatory context, this could lead to unnecessary panic or the rejection of safe models.
  • Invariance is a Myth in Practice: Prior work argued that because the theoretical privacy curve is the same everywhere, picking the "best" point shouldn't matter. The authors prove this only holds for infinite data; with finite samples, the "best" point is almost always an outlier.
  • K-Fold is the "Goldilocks" Solution: It consistently provided the best balance between being statistically valid and maintaining a tight, informative bound.

Key Results

  • Widespread Invalidity: Without correction, prior audits violated their claimed confidence levels up to four times more often than they should have (e.g., a 19.4% error rate when they claimed only 5%).
  • Significant Corrections: When re-analyzing influential papers, the authors found that valid lower bounds were 5% to 93% smaller than originally reported.
  • Tightness vs. Validity: In one example, a prior audit claimed to reach 88% of the theoretical privacy limit. After correcting for selection bias, the valid bound was actually less than 50% of the limit—showing a much larger gap between theory and practice than previously thought.

Limitations and Future Work

The primary limitation is that all the "valid" methods presented are conservative. Because they are designed to never exceed the true privacy parameter, they often significantly underestimate it.

The authors suggest that while their work provides a "safe" floor for privacy auditing, the next frontier is developing tighter valid bounds. They also note that their analysis focused on frequentist statistics, leaving the exploration of Bayesian "credible intervals" for future research. Finally, they emphasize that a lower bound is only as good as the attack—better statistical tools don't replace the need for stronger, more creative Membership Inference Attacks.

Summary updated

Abstract

Statistical privacy audits are essential for verifying the theoretical privacy guarantees of differentially private (DP) mechanisms. Auditors typically use Membership Inference Attacks (MIAs) to estimate a lower bound on the true privacy leakage of DP mechanisms at a specified confidence level, which should not exceed the theoretical privacy upper bound guaranteed by DP. However, we found that many auditing implementations in prior work introduce a selection bias when running MIAs, which leads to statistically invalid and overestimated lower bounds. Because most audits are not tight, this bias has thus far gone unnoticed: the estimated lower bounds remained well below the theoretical upper bounds. Nevertheless, accurately evaluating this lower bound is critical, as a flawed statistical assessment could lead to false alarms on correct mechanisms or an incorrect evaluation of the guarantee's tightness. This work employs tools from the statistical literature to correct this bias. We present an overview of the different correction methods and assess their respective advantages. Furthermore, we perform a comprehensive re-analysis of results returned by prior audit implementations and show that without statistical correction, these audits violate the theoretical upper bounds up to four times more often than their claimed confidence level implies. With correction applied, the resulting lower bounds are statistically valid, and violations occur at no more than the nominal rate.
BibTeX
@misc{dorseuil2026reliable,
  author = {Valentin Dorseuil and Meenatchi Sundaram Muthu Selva Annamalai and Jamal Atif and Olivier Cappé and Nicolas Papernot},
  title = {{Reliable Estimation of Differential Privacy under Selection Bias}},
  year = {2026},
  eprint = {2610.27021},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.27021},
}
Figure