Optimal Rates for Differentially Private Hypothesis Testing with E-values

• URL: http://arxiv.org/abs/2605.28952v2
• Date: Fri, 29 May 2026 03:39:02 GMT
• Title: Optimal Rates for Differentially Private Hypothesis Testing with E-values
• Abstract summary: Given two distributions $mathbbP$ and $mathbbQ$, what is the maximum achievable e-power when testing $Xsim mathbbPn$ against $XsimmathbbQn$ with e-values that satisfy $varepsilon$-differential privacy?<n>We characterize the optimal rate for this problem and provide an algorithm which matches it exactly.<n>In the sequential setting, when observations arrive one-by-one and the analyst chooses when to halt, we give matching upper and lower bounds on the stopping times of
• Score: 38.69101315030117
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: E-values have attracted considerable interest in recent years as flexible tools for enabling anytime-valid and adaptive data analysis. Hypothesis testing is at the core of many of these applications, which can often involve private or sensitive data. In this work, we answer a simple but important question: given two distributions $\mathbb{P}$ and $\mathbb{Q}$, what is the maximum achievable e-power when testing $X\sim \mathbb{P}^n$ against $X\sim\mathbb{Q}^n$ with e-values that satisfy $\varepsilon$-differential privacy? We characterize the optimal rate for this problem and provide an algorithm which matches it exactly. In the sequential setting, when observations arrive one-by-one and the analyst chooses when to halt, we give matching upper and lower bounds on the stopping times of any private e-process. Numerical experiments confirm the practicality of our algorithms, which require less data than the recently proposed DP-SPRT across a range of sequential testing problems and privacy levels.

Related papers

• Provably Adaptive Linear Approximation for the Shapley Value and Beyond [73.0940890296463]
  A fundamental and long-standing challenge is their efficient approximation.<n>We develop a linear-space algorithm that requires $P(|hatboldsymbol-boldsymbol|_2geq)leq $ for all commonly used semi-values.<n>Our algorithm allows explicit minimization of the mean square error for each specific utility function.
  arXiv  Detail & Related papers  (2026-04-09T16:38:14Z)
• Minimax optimal differentially private synthetic data for smooth queries [6.093338631816647]
  We study the problem of generating $(varepsilon,)$-differentially private synthetic data from a dataset of size $n$ supported on the hypercube.<n>We propose a minimax error rate of $n-min 1, frackd$, up to a $log(n)$ factor. This characterization uncovers a phase transition at $k=d$.
  arXiv  Detail & Related papers  (2026-02-02T03:54:11Z)
• DP-SPRT: Differentially Private Sequential Probability Ratio Tests [18.783606628556342]
  We revisit Wald's celebrated Sequential Probability Ratio Test for sequential tests of two simple hypotheses, under privacy constraints.<n>We propose DP-SPRT, a wrapper that can be calibrated to achieve desired error probabilities and privacy constraints.
  arXiv  Detail & Related papers  (2025-08-08T15:09:13Z)
• Optimized Tradeoffs for Private Prediction with Majority Ensembling [59.99331405291337]
  We introduce the Data-dependent Randomized Response Majority (DaRRM) algorithm.<n>DaRRM is parameterized by a data-dependent noise function $gamma$, and enables efficient utility optimization over the class of all private algorithms.<n>We show that DaRRM provably enjoys a privacy gain of a factor of 2 over common baselines, with fixed utility.
  arXiv  Detail & Related papers  (2024-11-27T00:48:48Z)
• On Differentially Private U Statistics [25.683071759227293]
  We propose a new thresholding-based approach using emphlocal H'ajek projections to reweight different subsets of the data. This leads to nearly optimal private error for non-degenerate U-statistics and a strong indication of near-optimality for degenerate U-statistics.
  arXiv  Detail & Related papers  (2024-07-06T03:27:14Z)
• On the Complexity of Differentially Private Best-Arm Identification with Fixed Confidence [16.295693624977563]
  We study the problem of Best Arm Identification with fixed confidence under $epsilon$-global Differential Privacy. Our lower bound suggests the existence of two privacy regimes depending on the privacy budget. We propose AdaP-TT, an $epsilon$-global DP variant of the Top Two algorithm.
  arXiv  Detail & Related papers  (2023-09-05T13:07:25Z)
• Sequential Kernelized Independence Testing [77.237958592189]
  We design sequential kernelized independence tests inspired by kernelized dependence measures.<n>We demonstrate the power of our approaches on both simulated and real data.
  arXiv  Detail & Related papers  (2022-12-14T18:08:42Z)
• Analyzing Privacy Leakage in Machine Learning via Multiple Hypothesis Testing: A Lesson From Fano [83.5933307263932]
  We study data reconstruction attacks for discrete data and analyze it under the framework of hypothesis testing. We show that if the underlying private data takes values from a set of size $M$, then the target privacy parameter $epsilon$ can be $O(log M)$ before the adversary gains significant inferential power.
  arXiv  Detail & Related papers  (2022-10-24T23:50:12Z)
• Adaptive Private-K-Selection with Adaptive K and Application to Multi-label PATE [19.344510696808282]
  We provide an end-to-end Renyi DP based-framework for differentially private top-$k$ selection. We show that our construction improves the privacy-utility trade-offs compared to the previous top-$k$ selection algorithms.
  arXiv  Detail & Related papers  (2022-03-30T07:11:01Z)
• Locally Private Hypothesis Selection [96.06118559817057]
  We output a distribution from $mathcalQ$ whose total variation distance to $p$ is comparable to the best such distribution. We show that the constraint of local differential privacy incurs an exponential increase in cost. Our algorithms result in exponential improvements on the round complexity of previous methods.
  arXiv  Detail & Related papers  (2020-02-21T18:30:48Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.