📊 statistics

Sequential Auditing for f-Differential Privacy

This paper introduces adaptive, sequential auditing methods for $f$ -Differential Privacy that statistically detect violations across the full privacy spectrum without requiring a pre-specified sample size, thereby significantly reducing the computational cost of verifying privacy guarantees compared to traditional batch-based approaches.

Original authors: Tim Kutta, Martin Dunsche, Yu Wei, Vassilis Zikas

Published 2026-06-18

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Tim Kutta, Martin Dunsche, Yu Wei, Vassilis Zikas

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you have a magical machine that takes in sensitive data (like your medical records or bank details) and spits out a useful answer, like "how many people in this city have diabetes?" The promise is that the machine uses Differential Privacy (DP) to ensure that your specific data point cannot be reverse-engineered from the answer. It's like adding a little bit of "static" or "noise" to the answer so that no one can tell if you were in the database or not.

But here's the problem: How do you know the machine isn't broken? Maybe the engineer forgot to add enough noise, or maybe there's a bug that leaks your secrets. This is where auditing comes in. It's like a quality control inspector checking if the machine is actually keeping its promise.

The Old Way: The "Fixed-Size" Inspection

Traditionally, auditors worked like a factory inspector who decides in advance, "I will check exactly 10,000 items."

The Problem: If the machine is really broken, the inspector might find the error in the first 10 items. But because they promised to check 10,000, they waste a huge amount of time and money checking the rest.
The Risk: If the machine is only slightly broken, checking 10,000 items might still not be enough to be sure. The inspector has to guess the right number beforehand, and they usually guess way too high to be safe, wasting resources.

The New Way: The "Smart, Adaptive" Inspector

This paper introduces a new kind of auditor called Sequential Auditing for f-Differential Privacy. Think of this as a smart inspector who doesn't have a fixed number of items to check. Instead, they keep checking one by one and ask themselves, "Do I have enough evidence yet?"

Here is how it works, using some simple metaphors:

1. The "f-DP" Map (The Tradeoff Curve)

Instead of checking just one number (like "is the noise big enough?"), this new auditor looks at a map called an f-DP curve.

Analogy: Imagine a mountain range. The "safe" zone is the area above the mountain ridge. The "unsafe" zone is below it.
Old Auditors: They only check if you are standing on a specific spot on the map.
New Auditors: They check your entire position relative to the whole mountain range. If you are even slightly below the ridge anywhere, they know you are in trouble. This gives them a much clearer, more complete picture of safety.

2. The "Stop-When-Ready" Rule

The core innovation is Sequential Testing.

The Metaphor: Imagine you are trying to hear a whisper in a noisy room.
- Old Method: You stand there for exactly 1 hour, regardless of whether you heard the whisper at 5 minutes or 55 minutes.
- New Method: You listen. If you hear the whisper clearly after 10 seconds, you stop immediately and say, "I found the leak!" If the room is quiet, you keep listening for a bit longer. You stop the moment you are statistically sure.
The Benefit: If the machine is badly broken, the auditor stops almost instantly, saving massive amounts of computing power. If the machine is fine, it keeps going until it's sure, but it never wastes resources checking more than necessary.

3. The "Classifier" (The Detective)

To find the leak, the auditor uses a "classifier," which is like a detective trying to guess which of two groups a piece of data came from.

The Game: The auditor has two buckets of data: one from a normal database and one where a single person was swapped out.
The Test: The auditor tries to guess, "Did this output come from the normal bucket or the swapped bucket?"
The Logic: If the machine is working perfectly (good privacy), the buckets look identical, and the detective can't guess better than flipping a coin. If the machine is broken, the detective can guess correctly more often. The auditor watches the detective's success rate. If the detective starts guessing too well, the auditor sounds the alarm.

Why This Matters

The paper shows that this new method is much cheaper and faster than the old ways.

For expensive tasks: Training AI models (like the DP-SGD mentioned in the paper) is very expensive. Running an audit that requires 100 times more data than necessary is a waste of money. This new method adapts to the situation, often needing only a fraction of the samples.
For safety: It provides a mathematical guarantee that if the machine is broken, the auditor will eventually find it, and if it's safe, the auditor won't falsely accuse it.

Summary

The authors built a smart, adaptive inspector that checks if privacy algorithms are working correctly. Instead of blindly checking a huge, pre-set number of samples, it checks samples one by one and stops the moment it has enough proof. It uses a sophisticated "map" (f-DP) to see the whole picture of privacy, making it faster, cheaper, and more accurate than previous methods.

What the paper does NOT claim:

It does not claim to fix the privacy bugs itself; it only detects them.
It does not claim to work on any type of data without specific setup (it works on standard privacy mechanisms like Gaussian or Laplace noise).
It does not claim to predict future privacy laws or clinical outcomes; it is strictly a tool for testing current software implementations.

Technical Summary: Sequential Auditing for f-Differential Privacy

Problem Statement

Differential Privacy (DP) is the standard for quantifying privacy in data processing, yet verifying that a specific implementation adheres to its theoretical guarantees remains a critical challenge. Existing empirical auditors typically rely on fixed-sample (batch) procedures targeting the traditional $(\varepsilon, \delta)$ -DP notion. These approaches suffer from two primary limitations:

Inefficiency: They require a pre-specified sample size. Since the "effect size" (the magnitude of the privacy violation) is unknown prior to testing, practitioners often choose excessively large sample sizes to avoid inconclusive results, leading to prohibitive computational costs, especially for expensive training procedures like DP-SGD.
Limited Expressiveness: The $(\varepsilon, \delta)$ framework offers a "localized" view of privacy, failing to capture the full trade-off spectrum between privacy and utility. In contrast, $f$ -Differential Privacy ( $f$ -DP) characterizes the entire privacy behavior via a single tradeoff curve, making it more amenable to statistical testing and better suited for modern mechanisms like DP-SGD.

While recent work has introduced sequential testing for $(\varepsilon, \delta)$ -DP, there is a lack of sequential auditors for the more expressive $f$ -DP framework that can adaptively determine sample sizes while maintaining rigorous statistical guarantees.

Methodology

The authors propose APT (Advanced Privacy Testing), a sequential auditing framework for $f$ -DP. The core idea is to adaptively collect samples until a decision (violation or no violation) is reached with statistical significance, rather than using a fixed batch size.

1. Sequential Testing Framework

The auditor frames the problem as a hypothesis test:

$H_0$ : The mechanism satisfies the claimed $f$ -DP curve $f$ (i.e., the tradeoff function $T(\alpha) \geq f(\alpha)$ for all $\alpha$ ).
$H_1$ : The mechanism violates the claim (i.e., $\exists \alpha^*$ such that $T(\alpha^*) < f(\alpha^*)$ ).

Unlike naive sequential approaches that repeatedly apply fixed-sample tests (which inflate the false rejection rate), APT employs anytime-valid inference. It constructs a sequential test statistic based on the empirical classification errors $(\hat{\alpha}, \hat{\beta})$ and compares them against boundary functions derived from Gaussian approximation theory (specifically, the behavior of Brownian motion). This ensures the false rejection rate (significance level $\gamma$ ) is controlled even as the sample size grows indefinitely.

2. Classifier Construction

To estimate the tradeoff function, the auditor requires a classifier $\phi$ to distinguish between output distributions $P$ (from dataset $D$ ) and $Q$ (from neighboring dataset $D'$ ). The framework supports both:

Whitebox Setting: The analyst knows the mechanism's parameters (e.g., noise distribution). A parametric Likelihood Ratio classifier (e.g., Gaussian thresholding) is used.
Blackbox Setting: Only input/output access is available. The auditor uses Kernel Density Estimation (KDE) to approximate the densities of $P$ and $Q$ , constructing a perturbed Likelihood Ratio classifier.

3. Optimal Threshold Tuning

A critical component is selecting the optimal threshold $\eta$ for the classifier. The authors propose a new geometric strategy (Equation 8) that selects $\eta$ to maximize the Euclidean distance between the estimated error pair $(\hat{\alpha}, \hat{\beta})$ and the claimed curve $f$ along the 45-degree diagonal. This is shown to be more powerful for detecting violations than previous vertical-distance-based selection rules.

4. Algorithm Flow

The APT algorithm (Algorithm 1) proceeds as follows:

Burn-in: Draw a small initial sample to calibrate parameters and build an initial classifier.
Sequential Loop: Iteratively draw new samples $(X_k, Y_k)$ .
Update: Periodically update the classifier (if in blackbox mode) and re-estimate classification errors.
Decision: Apply confidence-adjusted estimators to check if the estimated errors fall significantly below the claimed curve $f$ . If the boundary is crossed, the algorithm halts and reports a violation.

Key Contributions

First Sequential $f$ -DP Auditor: The paper presents the first auditor capable of sequentially testing $f$ -DP claims, supporting both whitebox and blackbox settings.
Theoretical Guarantees: The authors provide proofs (Theorem 3.1) showing that:
- The false rejection rate is bounded by a user-specified $\gamma$ (even for infinite sample sizes).
- The sample size required to detect a violation is near-optimal, within a logarithmic factor of the theoretical minimum required by a fixed-sample test with known effect size.
Improved Classifier Tuning: A novel geometric strategy for selecting the optimal classifier threshold that improves detection power over existing fixed-batch methods.
Open-Source Implementation: The authors provide a public repository with code to reproduce results and apply the auditor.

Experimental Results

The authors evaluated APT on synthetic benchmarks (Gaussian and Laplace mechanisms) and a real-world DP-SGD scenario.

Sample Efficiency: In controlled experiments, APT detected violations with significantly fewer samples than fixed-batch baselines. For strong violations, detection often occurred within a few hundred samples.
Comparison with Prior Work: The paper compares APT against a recent sequential $(\varepsilon, \delta)$ $(ε, δ)$ -DP auditor [22] on additive-noise benchmarks.
- In small- $\varepsilon$ regimes, APT required roughly 10%–25% of the samples reported by [22] to reject buggy mechanisms.
- In larger- $\varepsilon$ regimes, the MMD-based surrogate used by [22] suffers from a "saturation effect" where the test margin vanishes, causing detection failure. APT remains effective over a wider range of privacy parameters because it does not rely on this surrogate.
Real-World DP-SGD: In a "one-run" auditing scenario on CIFAR-10, the sequential approach demonstrated that for clear violations, the number of canary scores needed to reach a decision was drastically reduced (dropping from thousands to hundreds) compared to running a fixed-batch test on the full set.

Significance and Claims

The paper claims that APT addresses the computational bottleneck in privacy auditing by eliminating the need for pre-specified, often excessive, sample sizes. By shifting the focus to $f$ -DP and utilizing sequential testing, the method allows for:

Cost Reduction: Particularly beneficial for expensive mechanisms like DP-SGD where re-running training or scoring large numbers of canaries is prohibitive.
Rigorous Control: Maintaining strict statistical significance guarantees without the "peeking" penalty associated with naive sequential testing.
Adaptability: The ability to detect violations quickly when they are large, while continuing to sample only as long as necessary for subtle violations.

The authors emphasize that this work is intended to complement existing auditing tools, providing a generic sequential wrapper that can be applied to any $f$ -DP auditor to improve sample efficiency. They explicitly note that their comparison with [22] is not a claim of universal dominance, as the two methods audit different privacy objects, but rather a demonstration of superior efficiency in specific, relevant regimes.