摘要
我们重新审视了Wald经典的序列概率比检验（SPRT），在隐私约束下对两个简单假设进行序列测试。针对现有工作的显著空白，我们提出DP-SPRT——一种可校准以满足预设错误概率和隐私约束的封装方法。DP-SPRT依赖一种私有机制，该机制处理查询序列并在私有判定查询结果超出预定义区间时终止。这一OutsideInterval机制优于类似AboveThreshold等现有技术的朴素组合，可能惠及其他序列算法。
我们证明了DP-SPRT在错误率和样本复杂度上的通用上界，可适配基于实践者隐私需求的不同噪声分布，并以两种设置为例：拉普拉斯噪声（纯差分隐私）与高斯噪声（Rényi差分隐私）。在前者中，通过给出满足指定I/II类错误的任何ε-DP检验的样本复杂度下界，我们证明当两类错误均较小且假设接近时，DP-SPRT接近最优。实验研究进一步验证了其优异实际性能。
关键内容
- 隐私机制设计：OutsideInterval通过动态处理查询序列提升效率，避免冗余计算。
- 理论贡献：
- 提供拉普拉斯与高斯噪声下的误差与样本复杂度上界。
- 证明小误差场景下DP-SPRT的近似最优性。
- 实验验证：实际测试显示其性能优于基线方法。
分类与引用
- 学科分类：机器学习（stat.ML）、密码学与安全（cs.CR）、统计理论（math.ST）
- arXiv引用：
arXiv:2508.06377 [stat.ML]