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