在隐私保护下实现高效序列假设检验，误差与隐私可调。
DP-SPRT: Differentially Private Sequential Probability Ratio Tests
- 设计私有机制，在序列查询中动态判断是否超出阈值区间。
- 理论证明其样本复杂度近最优，且在小误差下表现接近理想极限。
- 适用于需持续监控数据的场景，如隐私敏感的在线实验分析。
我们重新审视沃尔德经典的序列概率比检验（SPRT），在隐私约束下提出DP-SPRT，一种可调节误差概率与隐私水平的通用框架。该方法基于一个私有机制，对连续查询进行处理，并在查询结果超出预设区间时停止。该机制通过改进传统技术（如AboveThreshold）的简单组合，实现隐私预算减半的提升，从而为其他持续监控任务带来潜在收益。我们给出了通用的误差与样本复杂度上界，支持多种噪声分布，包括拉普拉斯噪声（纯差分隐私）和高斯噪声（Rényi差分隐私）。在拉普拉斯情形下，我们建立了任意ε-差分隐私测试的样本复杂度下界，证明当两类错误概率均较小时，且两假设接近，DP-SPRT近乎最优。实验验证了其良好的实际性能。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。