DP-SPRT: Differentially Private Sequential Probability Ratio Tests
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, achieving a factor-of-2 privacy improvement and thus potentially benefiting other continual monitoring procedures. 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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Using transcription-based detectors to emulate the behaviour of sequential probability ratio-based concentration detectors
The sequential probability ratio test (SPRT) from statistics is known to have the least mean decision time compared to other sequential or fixed-time tests for given error rates. In some circumstances, cells need to make…
Decision MakingOptimal Rates for Differentially Private Hypothesis Testing with E-values
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 invo…
Sequential Density Ratio Estimation for Simultaneous Optimization of Speed and Accuracy
Classifying sequential data as early and as accurately as possible is a challenging yet critical problem, especially when a sampling cost is high. One algorithm that achieves this goal is the sequential probability ratio…
Decision MakingDensity Ratio EstimationThe Power of Log-Sum-Exp: Sequential Density Ratio Matrix Estimation for Speed-Accuracy Optimization
We propose a model for multiclass classification of time series to make a prediction as early and as accurate as possible. The matrix sequential probability ratio test (MSPRT) is known to be asymptotically optimal for th…
Action RecognitionDensity Ratio EstimationEarly ClassificationTime Series+1Toward Asymptotic Optimality: Sequential Unsupervised Regression of Density Ratio for Early Classification
Theoretically-inspired sequential density ratio estimation (SDRE) algorithms are proposed for the early classification of time series. Conventional SDRE algorithms can fail to estimate DRs precisely due to the internal o…
ClassificationDensity Ratio EstimationEarly Classificationregression+2