💻 computer science

Optimal Rates for Differentially Private Hypothesis Testing with E-values

This paper establishes the optimal rates and provides a matching algorithm for differentially private hypothesis testing using e-values, demonstrating superior data efficiency compared to existing methods like DP-SPRT in both fixed and sequential settings.

Original authors: Ben Jacobsen, Tomas Gonzales, Gavin Brown, Kassem Fawaz, Aaditya Ramdas

Published 2026-05-29

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Ben Jacobsen, Tomas Gonzales, Gavin Brown, Kassem Fawaz, Aaditya Ramdas

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

The Big Picture: Testing Secrets Without Tipping Your Hand

Imagine you are a detective trying to figure out if a suspect is guilty (Hypothesis Q) or innocent (Hypothesis P). You have a pile of evidence (data). In the old days, you would look at all the evidence at once, make a binary "Guilty/Not Guilty" decision, and stop.

However, modern science often uses a smarter tool called an E-value. Instead of a simple "Yes/No," an E-value is like a scorecard.

If the score is 1, the evidence is neutral.
If the score is 10, the evidence is 10 times more likely to be from the "Guilty" scenario than the "Innocent" one.
If the score is 100, it's a slam dunk.

The beauty of E-values is that you can keep collecting evidence and updating the scorecard as you go. You can stop whenever you want, or keep going if the score is low, without breaking the rules of statistics.

The Problem:
Often, this evidence contains sensitive personal information (like medical records or browsing history). We need to protect people's privacy. This is where Differential Privacy (DP) comes in. It's like putting a "privacy filter" on your scorecard. The filter adds a tiny bit of "static" or noise so that no one can tell if a specific person's data was included or not.

The Dilemma:
Adding privacy noise makes the scorecard less accurate. If you add too much noise to protect privacy, the score might stay low even when the suspect is actually guilty. The big question this paper asks is: "What is the absolute best scorecard we can build that is both private and powerful?"

Part 1: The "Batch" Setting (Looking at the Whole Pile at Once)

Imagine you are given a whole box of evidence all at once. You need to calculate one final E-value score.

The Discovery:
The authors figured out the mathematical "speed limit" for how good a private scorecard can be. They found that there is a specific, optimal way to construct this scorecard.

The Analogy: The "Clamped" Scorecard
Imagine the raw evidence suggests a score of 1,000,000. But because of privacy rules, we can't let the score jump that high instantly; it would reveal too much about a single piece of evidence.

The authors designed a method that "clamps" or caps the score. It says, "Okay, we'll let the score go up, but we'll smooth out the jumps."
They proved that their specific method of smoothing is the best possible way to do it. No other private method can give you a higher score (more power) for the same amount of privacy.

They also created a "bridge" distribution (a theoretical middle-ground scenario) that helps them calculate exactly how much privacy costs you in terms of statistical power.

Part 2: The "Sequential" Setting (The Live Stream)

Now, imagine the evidence arrives one by one, like a live stream of video. You want to stop the stream the moment you are confident enough to make a call. This is called Sequential Testing.

The Challenge:
In a private setting, if you check the score after every single piece of evidence, you have to add noise every single time. This adds up quickly, making the score very "fuzzy" and slow to rise. You might need to watch 1,000 hours of video to get a clear answer, whereas without privacy, you might only need 100.

The Solution: The "Batched" Stream
The authors realized that checking the score after every single frame is inefficient. Instead, they proposed a smart batching strategy:

Don't check every frame. Watch a small chunk of the video (a batch), calculate the score for that chunk, and then add the privacy noise once.
The Algorithm: They built a specific algorithm (Algorithm 1) that decides exactly how big these chunks should be.
- If you are early in the stream, you might wait for a slightly larger chunk to get a better signal before adding noise.
- As you get more data, the chunks adjust to keep the score rising as fast as possible.

The Result:
They proved that their algorithm is optimal. It stops the experiment (the stream) as quickly as mathematically possible while still respecting the privacy rules.

Part 3: The Race Against the Competition

The authors tested their new algorithm against a recently proposed method called DP-SPRT (a private version of a standard statistical test).

The Race:

The Track: They ran simulations using simple coin-toss scenarios (Bernoulli distributions).
The Outcome: Their new "Private E-Process" crossed the finish line (stopped the test) significantly earlier than the DP-SPRT.
Why it matters: In the real world, "stopping earlier" means you need less data. This saves time, money, and reduces the burden on the people providing the data, all while keeping their privacy just as safe.

Summary of Key Takeaways

The Limit: They found the exact mathematical limit of how powerful a private statistical test can be. You can't beat this limit; it's the "speed of light" for private testing.
The Tool: They built a tool (an algorithm) that hits this limit exactly. It works for any type of data distribution, not just simple ones.
The Strategy: In live, sequential testing, the secret is batching. Don't add noise to every single data point; group them, calculate, then add noise. This keeps the signal strong and the privacy safe.
The Win: Their method requires less data to reach a conclusion than previous methods, making private data analysis more practical and efficient.

What they did NOT do:
The paper focuses strictly on the math of simple hypothesis testing (comparing two specific scenarios). They did not apply this to complex real-world medical trials, specific clinical diagnoses, or future policy changes. They built the engine; they didn't drive the car to a specific destination.

Technical Summary: Optimal Rates for Differentially Private Hypothesis Testing with E-values

Problem Statement

This work addresses the fundamental problem of simple hypothesis testing under the constraints of central Differential Privacy (DP). Specifically, the authors investigate testing a dataset $X \sim P^n$ (null hypothesis) against $X \sim Q^n$ (alternative hypothesis) using e-values.

In the classical setting, the performance of a test is measured by its power (true positive rate). In the e-value framework, performance is measured by e-power, defined as $\mathbb{E}_Q[\log E]$ , where $E$ is a non-negative random variable satisfying $\mathbb{E}_P[E] \le 1$ . The central question is: What is the maximum achievable e-power for an $\varepsilon$ -DP e-value when testing $P$ against $Q$ ?

The authors consider two settings:

Batch Setting: All $n$ data points are available simultaneously.
Sequential Setting: Data arrives one-by-one, and the analyst chooses a stopping time $N$ adaptively. The goal is to minimize the expected stopping time $\mathbb{E}_Q[N]$ required to achieve a specific level of statistical evidence.

While prior work exists on differentially private hypothesis testing in the decision-theoretic setting (binary outputs) and on e-values under local DP, this paper focuses on central DP e-values, a setting where only limited prior work exists (specifically Csillag and Mesquita [10], which was restricted to bounded likelihood ratios).

Methodology

1. Characterization of Optimal E-power (Batch Setting)

The authors decouple the privacy mechanism from the e-variable construction. They observe that for any fixed $\varepsilon$ -DP mechanism $M$ , the optimal post-processing to create an e-variable is the likelihood ratio of the output distributions, $dM(Q^n)/dM(P^n)$ . Thus, the problem reduces to maximizing the Kullback-Leibler (KL) divergence between the output distributions of the mechanism:
$R_{\varepsilon}(Q \| P) = \lim_{n \to \infty} \sup_{M \in \varepsilon\text{-DP}} \frac{1}{n} KL(M(Q^n) \| M(P^n))$

To solve this, the authors introduce an intermediate distribution $\tilde{Q}$ . They construct $\tilde{Q}$ by modifying the density of $Q$ relative to $P$ in specific regions defined by the likelihood ratio $q(x)/p(x)$ :

Region A (Low Likelihood Ratio): $q(x) < c_1 p(x)$ . Here, $\tilde{q}(x) = c_1 p(x)$ .
Region B (High Likelihood Ratio): $q(x) > c_2 p(x)$ . Here, $\tilde{q}(x) = c_2 p(x)$ .
Region M (Intermediate): $\tilde{q}(x) = q(x)$ .

The constants $c_1, c_2$ and the regions are determined by a Lagrange multiplier $\lambda^*$ that solves an implicit equation ensuring $\tilde{Q}$ is a valid probability distribution. This construction minimizes the functional $KL(Q' \| P) + \varepsilon \cdot TV(Q', Q)$ .

The authors prove that the optimal rate is exactly:
$R_{\varepsilon}(Q \| P) = KL(\tilde{Q} \| P) + \varepsilon \cdot TV(\tilde{Q}, Q)$

They then construct a non-private e-variable $E^*$ based on this $\tilde{Q}$ (specifically, a clipped likelihood ratio) which has bounded log-sensitivity $\varepsilon$ . To privatize this, they propose a merging function $\Lambda_n$ based on Vovk and Wang's work, adding Laplacian noise with a carefully calibrated compensator to maintain the e-variable property while preserving asymptotic optimality.

2. Sequential Setting and Stopping Times

In the sequential setting, the authors define an $\varepsilon$ -DP e-process as a sequence of e-values generated by an $\varepsilon$ -DP mechanism. They establish a lower bound on the expected stopping time for any such process.

Using a potential function argument involving a coupling between the true distribution $Q$ and the intermediate distribution $\tilde{Q}$ , they prove that for any stopping time $N$ :
$\mathbb{E}_Q[\log E_N] \le \mathbb{E}_Q[N] \cdot R_{\varepsilon}(Q \| P)$
This implies a lower bound on the sample complexity required to achieve a certain power.

To match this bound, they propose Algorithm 1, a "Batch to E-process Conversion." This algorithm:

Takes a non-private e-variable with bounded log-sensitivity.
Processes data in batches of increasing size.
Applies a privatized merging function (similar to the batch case) at the end of each batch.
Uses a specific recurrence relation to determine batch sizes, optimizing the trade-off between the initial "startup" time and the long-term competitive ratio.

Key Contributions and Results

Instance-Specific Hardness Result (Theorem 2.2): The paper provides an explicit, computable formula for the maximum achievable e-power under $\varepsilon$ -DP. This rate is characterized by the KL divergence to an intermediate distribution $\tilde{Q}$ plus a total variation penalty.
Optimal Algorithm Construction (Theorem 2.4): The authors construct an $\varepsilon$ -DP e-variable that achieves this optimal rate asymptotically. The construction involves a specific clipping of the likelihood ratio followed by a privatization scheme using Laplacian noise and a compensator term.
Sequential Lower Bound (Theorem 3.1): They derive a universal lower bound on the expected stopping time of any $\varepsilon$ -DP e-process, showing it is inversely proportional to the optimal e-power rate $R_{\varepsilon}(Q \| P)$ .
Optimal Sequential Algorithm (Theorem 3.2): They present Algorithm 1, which converts a non-private e-variable into an $\varepsilon$ -DP e-process. This algorithm matches the theoretical lower bound on stopping times up to a constant multiplicative factor (competitive ratio) for all sufficiently large stopping times.
Distribution-Independent Alternative (Appendix C): Recognizing that computing the optimal $\tilde{Q}$ may be intractable for complex distributions, they propose a "truncated and scaled likelihood ratio" (tsLR) statistic. This distribution-independent statistic achieves a rate within a constant factor of the optimal rate.

Experimental Validation

The authors conducted numerical experiments comparing their Algorithm 1 against DP-SPRT (Differentially Private Sequential Probability Ratio Test) proposed by Michel et al. [25].

Setup: Testing $P = \text{Bernoulli}(0.3)$ against $Q = \text{Bernoulli}(q)$ .
Metric: Empirical Cumulative Distribution Functions (CDFs) of stopping times.
Result: Across various privacy levels ( $\varepsilon$ ) and alternative distributions ( $q$ ), the proposed private e-process consistently stopped earlier than DP-SPRT. Notably, this performance gain was achieved even though the proposed algorithm makes no parametric assumptions about the data, whereas DP-SPRT is designed specifically for exponential families.

Significance and Claims

The paper claims to provide a complete understanding of the fundamental limits of simple hypothesis testing using e-values under central differential privacy.

Theoretical Foundation: By characterizing the optimal rate $R_{\varepsilon}(Q \| P)$ and providing an algorithm that matches it, the work establishes a baseline for what is achievable in privacy-preserving sequential analysis.
Practical Utility: The proposed algorithms require less data (fewer stopping times) than existing state-of-the-art methods (DP-SPRT) across a range of settings.
Future Directions: The authors suggest that their hardness results and techniques (specifically the use of least-favorable pairs) can serve as a foundation for extending these results to composite hypothesis testing and instance-optimal DP estimation, similar to how foundational work in non-private settings has driven progress in those areas. They also note that extending these results to approximate DP ( $\delta > 0$ ) remains an open question.