DP-SPRT : Differentially Private Sequential Probability Ratio Tests
Thomas Michel, Debabrota Basu, Emilie Kaufmann · 2025
Read DP-SPRT : Differentially Private Sequential Probability Ratio Tests by Thomas Michel, Debabrota Basu, Emilie Kaufmann (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-06377.txt.
Introduction
Thomas Michel, Debabrota Basu, and Emilie Kaufmann add privacy to a classic test that decides between two claims as data roll in. The classic test, Wald's sequential probability ratio test, stops as soon as the proof is strong enough. Their 2025 version, DP-SPRT, wraps the test so each person's data stays private under set error rates.
The wrapper rests on a private tool that watches a stream of answers and stops when they leave a set band. That tool halves the privacy cost of older methods. The team proves bounds on errors and sample size for two kinds of added noise. In one key case they show no private test can do much better. Trials confirm the method works well in practice.
Catalog record
| CREATOR | Thomas Michel, Debabrota Basu, Emilie Kaufmann |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 106 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2508-06377
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
DP-SPRT : Differentially Private Sequential Probability Ratio Tests Thomas Michel, Debabrota Basu, Emilie Kaufmann Abstract We revisit Wald’s celebrated Sequential Probability Ratio Test for sequential tests of two simple hypotheses, under privacy constraints. We propose DP-SPRT , a wrapper that can be calibrated to achieve desired error probabilities and privacy constraints, addressing a significant gap in previous work. DP-SPRT relies on a private mechanism that processes a sequence of queries and stops after privately determining when the query results fall outside a predefined interval. This OutsideInterval mechanism improves upon naive composition of existing techniques like AboveThreshold, potentially benefiting other sequential algorithms. We prove generic upper bounds on the error and sample complexity of DP-SPRT that can accommodate various noise distributions based on the practitioner’s privacy needs. We exemplify them in two settings: Laplace noise (pure Differential Privacy) and Gaussian noise (Rényi differential privacy). In the former setting, by providing a lower bound on the sample complexity of any ε \varepsilon -DP test with prescribed type I and type II errors, we show that DP-SPRT is near optimal when both errors are small and the two hypotheses are close. Moreover, we conduct an experimental study revealing its good practical performance. 1 Introduction Sequential hypothesis testing offers an elegant solution when data collection is costly or time-consuming, allowing decisions to be reached with fewer observations on average compared to fixed-sample approaches. The Sequential Probability Ratio Test (SPRT), developed by Wald, 1945 , is the foundational algorithm in this field, achieving optimal performance for simple hypothesis testing with independent and identically distributed observations. Sequential testing procedures are evaluated based on their error rates (Type I and Type II errors) and expected sample size (or sample complexity ) under each hypothesis. Wald, 1948 proved that SPRT minimizes sample complexities subject to error probability constraints—a remarkably strong optimality result in statistical decision theory. Despite its theoretical optimality and applications in clinical trials ( Armitage, 1950 ; Armitage, 1954 ) , quality control, and manufacturing ( Wald, 2004 ; Siegmund, 2013 ) , SPRT faces a significant modern challenge: privacy . When applied to sensitive data, such as patient records in medical trials, financial information, or personal behavior patterns, sequential testing procedures risk exposing confidential information. Privacy concerns are particularly acute for the most recent observations, as the decision to terminate data collection can reveal information about them. Consider a clinical trial where patients sequentially receive treatments and their responses are recorded. With the classical SPRT, if the test concludes that a drug increases the chance of observing an undesirable effect, then we can deduce the effect actually happened to the last participant in the study. More sophisticated attacks could deduce many other pieces of private information about participants throughout the trial. Even if individual patient responses are kept confidential, the pattern of treatment assignments and the stopping decision itself can leak sensitive information about participants. This privacy risk requires a formal framework for privacy-preserving sequential testing. Related Work. Differential privacy (DP) ( Dwork et al., 2006 ) has emerged as the standard framework for addressing privacy concerns in statistical analyses. By ensuring that the presence or absence of any single data point cannot significantly affect the outcome, DP offers a principled method to protect individual data while enabling meaningful statistical inference. Researchers have explored DP hypothesis testing– primarily in the fixed-sample setting. For example, Gaboardi et al., 2016 studies private chi-squared testing. Canonne et al., 2019 and Couch et al., 2019 investigate on optimal private tests for simple hypotheses, and nonparametric hypothesis testing with DP, respectively. These approaches, however, are not directly applicable to sequential testing due to the adaptive nature of sample collection. Wang et al., 2022 explored the privatization of SPRT by adding Laplace noise to thresholds and using the exponential mechanism for the final decision. However, due to their specific use case, their approach provides a weaker notion of privacy that only requires that critical privacy failures do not happen only for a subset of plausible datasets. In contrast, our work maintains DP throughout the testing process while working to minimize stopping time. Zhang et al., 2022 developed PrivSPRT, a private version of the SPRT using Gaussian noise with Renyi DP guarantees ( Mironov, 2017 ) . The authors provide upper bounds on the error probabilities given fixed thresholds and noise level, but do not specify how to calibrate these thresholds to achieve desired Type I and Type II error rates while maintaining a desired privacy guarantee. In practice, this forces to rely on Monte Carlo simulation to determine appropriate thresholds, a process that may itself leak privacy in certain scenarios ( Papernot and Steinke, 2021 ) . In this work, we overcome this limitation and provide an explicit threshold calibration to guarantee specified upper bounds on the errors as well as the desired privacy guarantees. Additionally, we provide a more general method supporting multiple noise mechanisms, and subsampling methods. Another related line of work is Differentially Private Best Arm Identification (DP-BAI) in bandits ( Sajed and Sheffet, 2019 ; Kalogerias et al., 2021 ; Azize et al., 2023 ; Azize et al., 2024 ) . BAI is a generalization of sequential hypothesis testing, where we simultaneously test means of multiple distributions to identify the largest one. ( Azize et al., 2023 ; Azize et al., 2024 ) design algorithms for \varepsilon -DP-BAI whose sample complexity has irreducible problem-dependent constants compared to the lower bound, keeping the optimal algorithm design open. Thus, we focus on the archetypal setup of testing two hypotheses, and aim to explicate the privacy-utility trade-offs. Contributions. (1) We introduce a general framework for differentially private SPRTs, called DP-SPRT , that supports various noise mechanisms while providing privacy guarantees and error control. We propose a generic sample complexity analysis of DP-SPRT for Bernoulli observations and particularize it to Gaussian noise (for Renyi DP) and Laplace noise (for \varepsilon -DP). (2) This framework is based on the novel OutsideInterval mechanism for differentially privately comparing a sequence of queries to two thresholds. This might be of independent interest for applications for DP problems with or without continual observations. (3) We further prove a lower bound on the sample complexity of any \varepsilon -DP algorithm that achieves prescribed type I and type II errors. This lower bound reveals two distinct regimes: one where privacy has minimal impact on sample complexity, and another where higher privacy requirements substantially increase the expected sample size. It also shows that DP-SPRT with Laplace noise is near optimal in a regime of small errors and when the two hypotheses are close . (4) On the practical side, we use subsampling to propose a practical improvement of DP-SPRT with better privacy-utility trade-off, especially in high privacy regimes. Our analysis of DP-SPRT is conducted for Bernoulli observations, which model binary outcomes present in applications such as clinical trials, quality control, and A/B testing. Bernoulli distributions form a one-dimensional exponential family with bounded support in [0,1] , making them suitable for DP mechanisms requiring bounded sensitivity. This setting provides an illustration of privacy-utility trade-offs while maintaining mathematical tractability. 2 Preliminaries: Sequential Tests, Differential Privacy, and SPRT Sequential hypothesis testing allows collecting data incrementally and making decisions as soon as sufficient