🤖 machine learning

How Well Can Differential Privacy Be Audited in One Run?

This paper characterizes the theoretical limits of one-run differential privacy auditing by identifying interference between data elements as the primary barrier to precision and proposes new conceptual approaches to overcome this limitation for improved auditing of machine learning algorithms.

Original authors: Amit Keinan, Moshe Shenfeld, Katrina Ligett

Published 2026-02-23

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Amit Keinan, Moshe Shenfeld, Katrina Ligett

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 secret recipe for a delicious cake. You want to prove to your friends that the recipe is "private," meaning that if they taste the cake, they can't figure out exactly which specific ingredient (like a pinch of salt or a specific brand of vanilla) you used.

In the world of machine learning, this "recipe" is a model trained on private data, and the "ingredients" are individual people's data. Differential Privacy (DP) is the mathematical guarantee that says, "No matter what, you can't tell if a specific person was in the training data."

But how do you test if this guarantee is real? That's where Privacy Auditing comes in.

The Problem: The "One-Shot" Test

Traditionally, to test if a recipe is private, you'd have to bake the cake hundreds of times: once with a pinch of salt, once without, and compare the results. This is slow and expensive.

Recently, researchers invented a faster method called "One-Run Auditing" (ORA). Instead of baking the cake hundreds of times, you bake it once, but you sneak in many different "test ingredients" at the same time. Then, you try to guess which test ingredients were actually used based on the taste of that single cake.

The big question this paper asks is: How good is this "one-shot" test? Can it actually tell us the true level of privacy, or does it miss the mark?

The Three Reasons the "One-Shot" Test Fails

The authors discovered that the One-Run Auditor is like a detective trying to solve a crime with a blurry photo. There are three specific reasons why the detective might fail, even if they are very smart:

1. The "Bad Apple" Problem (Non-Worst-Case Privacy)

Imagine a security guard who is super vigilant 99% of the time but falls asleep for 1 minute every day.

The Reality: The "privacy guarantee" is based on the worst-case scenario (the 1 minute they are asleep).
The Audit: If the One-Run Auditor happens to check the guard during the 99% of the time they are awake, they will think the security is perfect. They miss the "bad apple" moment.
The Result: The audit says, "You are super safe!" but the reality is, "You are vulnerable for a tiny bit." The audit underestimates the risk.

2. The "Lucky Break" Problem (Non-Worst-Case Outputs)

Imagine a magician who usually fails to make a rabbit disappear, but once in a blue moon, they accidentally make it vanish completely.

The Reality: The privacy guarantee is based on that one time the rabbit vanished (the worst case).
The Audit: If the auditor only watches the magician perform once, and that time the rabbit didn't vanish, the auditor thinks, "Wow, the rabbit is safe!"
The Result: The audit misses the rare, dangerous event because it only gets one shot at the performance.

3. The "Noise" Problem (Interference)

This is the biggest issue. Imagine you are trying to hear one person whispering in a crowded room.

The Reality: Differential Privacy assumes the auditor knows everyone else's whispers and is only trying to figure out one person's.
The Audit: In a "One-Run" test, the auditor is in the room with everyone whispering at once. They don't know what the others are saying. The whispers mix together (interfere), making it impossible to isolate the specific person they are trying to identify.
The Result: The auditor gets confused by the crowd noise and gives up, saying, "I can't tell who said what," even if the system is actually leaking secrets.

The Solution: The "Smart Detective" (Adaptive ORA)

The paper proposes a clever fix for the "Noise Problem."

Instead of guessing all the whispers at once, imagine the detective guesses the first whisper, then listens to the answer, and uses that new information to guess the second whisper more easily.

This is called Adaptive One-Run Auditing (AORA).

How it works: The auditor guesses a few elements, sees the result, and then uses that knowledge to "cancel out" the noise for the next guesses.
The Analogy: It's like playing a game of "20 Questions" where you get to hear the answer to the first question before asking the second. This helps the detective cut through the crowd noise and find the secrets much more accurately.

The Takeaway

The paper teaches us three main lessons:

One-shot tests are fast but flawed. They often give a false sense of security because they miss rare bad events or get confused by mixed-up data.
There are three specific "gaps" (Bad Apples, Lucky Breaks, and Noise) that prevent these tests from being perfect.
We can do better. By using "Adaptive" methods (where the auditor learns as they go), we can fix the "Noise" problem and get a much truer picture of how private a machine learning algorithm really is.

In short: If you want to know if your data is truly safe, don't just take a quick, single look. You need a smarter, adaptive detective who can learn from the clues as they go, or you might miss the danger hiding in the noise.

1. Problem Statement

Differential Privacy (DP) is the standard for protecting training data in machine learning. While theoretical proofs provide upper bounds on privacy parameters ( $\epsilon$ ), these bounds are often loose or incorrect due to implementation bugs. Privacy auditing aims to provide empirical lower bounds on $\epsilon$ to detect such issues.

Traditional "classic" auditing requires running the algorithm thousands of times on neighboring datasets to estimate output distributions, which is computationally expensive. One-Run Auditing (ORA), introduced by Steinke et al., improves efficiency by auditing multiple data points simultaneously in a single training run. While Steinke et al. proved ORA is valid (it never overestimates privacy), it remained unclear how tight these bounds are. Specifically, does ORA converge to the true privacy parameter as the number of audited elements increases, or are there inherent limitations?

2. Methodology and Framework

The authors analyze ORA through a guessing game framework:

Setup: An auditor selects a dataset where each of $n$ entries is chosen from a pair of options $\{x_i, y_i\}$ based on a random bit $S_i \in \{-1, 1\}$ .
Process: The algorithm $M$ runs once on this dataset, producing an output $O$ .
Guessing: A guesser $G$ attempts to predict the random bits $S$ based on $O$ . The guesser can abstain (output 0) for uncertain entries.
Metric: The efficacy is measured by the ratio of correct guesses to total guesses taken. The authors define Asymptotic Tightness as the ability of ORA to approach the true $\epsilon$ as the number of guesses approaches infinity.

The paper introduces the concept of Distributional Privacy Loss ( $\ell$ ), which measures the log-likelihood ratio of an output given different input choices, accounting for the uncertainty of other elements in the dataset.

3. Key Contributions: The Three Fundamental Gaps

The paper identifies three fundamental "gaps" that prevent ORA from being asymptotically tight for certain algorithms. These gaps arise because ORA's threat model (partial knowledge of other inputs) differs from the standard DP definition (adversary knows all inputs except one).

Non-Worst-Case Privacy for Elements:
- Issue: DP is defined by the worst-case privacy loss of any single element. ORA, however, must guess on all elements to achieve high statistical power. If an algorithm only leaks information about a tiny fraction of inputs (e.g., the "Name and Shame" algorithm which outputs one random element), the auditor is forced to guess on the remaining elements where no information exists, dragging down the average efficacy.
Non-Worst-Case Outputs:
- Issue: DP considers the worst-case output. ORA runs the algorithm only once. If the algorithm rarely produces a "bad" output (one that reveals significant privacy loss), the single run will likely be a "good" output, leading the auditor to underestimate the true $\epsilon$ .
Interference (The Primary Focus):
- Issue: When an algorithm aggregates multiple inputs (e.g., summing gradients), the output depends on the combination of inputs. To guess one specific input, the auditor needs to know the others. In ORA, the auditor does not know the other inputs (they are random variables), creating uncertainty.
- Example: The XOR algorithm (outputting the XOR of all bits) has infinite true $\epsilon$ (no privacy), but ORA efficacy is $1/2$ (random guessing) because the output reveals nothing about a specific bit without knowing the others.

4. Theoretical Characterization

The authors formalize these gaps using relaxed privacy definitions:

DDP (Distributional DP): Captures the interference gap.
AC-DDP (Average-Case DDP): Captures the non-worst-case output gap.
AE-AC-DDP (Average-Element, Average-Case DDP): Captures the non-worst-case element gap.

Key Theorems:

Theorem 5.1 & 5.2: The optimal efficacy of ORA is bounded by these relaxed privacy notions. Specifically, the efficacy is determined by the average distinguishability of elements given the uncertainty of others.
Theorem 5.3 (Condition for Tightness): ORA is asymptotically tight if and only if the number of elements with high distributional privacy loss approaches infinity.
- Implication: ORA is tight for Local Algorithms (where elements are processed independently, e.g., Local Randomized Response) but fails for algorithms with high interference (like global counting queries) unless specific conditions are met.

5. Case Study: DP-SGD

The paper applies these insights to DP-SGD (Differentially Private Stochastic Gradient Descent), the workhorse of private learning.

The Problem: DP-SGD aggregates gradients, creating interference. The standard "Dirac Canary" attack (using one element per coordinate) avoids interference but limits the number of auditable elements to the model dimension $d$ , which is often small.
Proposed Solution 1: Multi-Element per Coordinate: The authors show that assigning multiple auditing elements to the same coordinate can increase the number of high-confidence guesses, provided the interference doesn't overwhelm the signal. Experiments show an optimal trade-off exists (e.g., 8 elements per coordinate performed better than 1).
Proposed Solution 2: Adaptive ORA (AORA):
- Mechanism: AORA allows the guesser to use the true values of previously guessed elements to inform guesses for subsequent elements.
- Validity: The authors prove AORA remains a valid auditing method (it still provides a lower bound on $\epsilon$ ).
- Performance: By resolving the interference gap, AORA significantly outperforms non-adaptive ORA. In experiments on DP-SGD, AORA maintained tight bounds even as the number of elements per coordinate increased, whereas non-adaptive ORA bounds degraded due to interference.

6. Results and Significance

Theoretical Limits: The paper proves that ORA is not universally asymptotically tight. It provides a precise characterization of when it fails, distinguishing between algorithms that can be tightly audited in one run (local) and those that cannot (aggregating).
Interference Gap: The identification of the "interference gap" is a major conceptual contribution, explaining why previous one-run auditing methods struggle with complex models like neural networks.
Practical Improvements:
- AORA is introduced as a superior auditing strategy that leverages adaptivity to mitigate interference.
- Experiments on DP-SGD demonstrate that using multiple elements per coordinate combined with AORA yields significantly tighter privacy bounds than previous state-of-the-art methods.
Implications: This work cautions against using ORA as a "fig leaf" for algorithms with poor privacy guarantees. It provides a framework for interpreting auditing results: if an algorithm has high interference or rare worst-case outputs, a one-run audit may significantly underestimate the true privacy risk.

Conclusion

The paper establishes that while One-Run Auditing is computationally efficient, its efficacy is fundamentally limited by interference between data elements and the rarity of worst-case outputs. By characterizing these limits and proposing Adaptive ORA, the authors provide a path toward more accurate and reliable empirical privacy auditing for modern machine learning systems.