Optimal Rates for Differentially Private Hypothesis Testing with E-values¶
会议: NeurIPS 2026
arXiv: 2605.28952
OpenReview: https://openreview.net/forum?id=QEVhuw3jUX
领域: AI 安全
关键词: 差分隐私、假设检验、e-值、e-过程、停止时间
一句话总结¶
本文针对中心差分隐私约束下的简单假设检验问题，给出了 \(\varepsilon\)-DP e-值的实例最优 e-power 渐近界与紧匹配构造，并在序贯检验场景下证明了停止时间的下界，同时提出了一种达到常数竞争比的批量转 e-过程算法。
研究背景与动机¶
假设检验是现代统计推断与实证科学的基石，但在实际科研与工程中，传统的固定样本量二元决策框架往往面临两大致命困境：一方面，p-值对自适应数据收集与事后停止极其敏感，极易引发假阳性膨胀并加剧可重复性危机；另一方面，临床试验、在线 A/B 测试与用户交互审计往往涉及高度敏感的个人数据，必须提供严格的差分隐私（Differential Privacy, DP）保障。近年来兴起的 e-值（e-value）及其动态扩展 e-过程（e-process）因具备 anytime-valid（任意时刻有效）与可选停止（optional stopping）的优良性质而受到广泛关注，但如何在中心 DP 约束下兼顾严苛的隐私预算与统计效能，仍缺乏系统且紧致的理论刻画。
现有关于差分隐私假设检验的研究大多局限于经典 Neyman-Pearson 决策设定，或聚焦于局部差分隐私（Local DP）；在中心 DP 设定下，极少数探讨 e-值的先前工作仅适用于似然比有界的一阶理想分布，甚至无法处理最简单的高斯分布检验。若直接在对数似然比上叠加拉普拉斯或高斯噪声，会因为指数变换的强凸性破坏 e-值期望在零假设下不大于 1 的基本定义；而将输出截断或强行归一化又往往导致不可逆的效能损失或引入严重的估计偏差。因此，在中心 \(\varepsilon\)-DP 限制下，两分布检验能够达到的理论最大 e-power 究竟是多少，能否设计出对任意分布通用的最优隐私 e-值，成为一个尚未解决的根本理论问题。
针对上述矛盾，本文从信息论对偶与稳健统计学的视角出发，将差分隐私与 e-值性质显式解耦，通过构造特殊的中间桥梁分布来精确刻画隐私扰动下的信息衰减上界，并在序贯设定下建立停止时间与检验力之间的内禀权衡。核心 idea：将中心 \(\varepsilon\)-DP 约束下的最优 e-power 转化为总变差正则化的 KL 散度极小化对偶问题，通过中间分布构造截断配准似然比非私有统计量并结合低敏感度合并函数，在批处理与序贯场景下分别实现渐近最优 e-power 与紧匹配期望停止时间。
方法详解¶
整体框架¶
本文的方法体系涵盖批处理（Batch Setting）与序贯检验（Sequential Setting）两个层次。在批处理场景下，目标是测试样本量为 \(n\) 的简单零假设 \(X \sim \mathbb{P}^n\) 与备择假设 \(X \sim \mathbb{Q}^n\)。系统首先将机制的差分隐私性与 e-值有效性解耦，利用后处理定理将问题等价转化为机制输出空间上的似然比检验；随后通过凸优化求解唯一的中间桥梁分布 \(\widetilde{Q}\)，确定双侧自适应截断阈值 \([c_1, c_2]\)，构造具备 \(\varepsilon\) 对数敏感度的有界非私有统计量 \(E^*(x)\)；最后引入平滑合并函数与微调拉普拉斯补偿项生成最终的 \(\varepsilon\)-DP e-值。
在序贯场景下，观测数据逐个到达，分析师可自适应决定终止检验。为克服直接加噪破坏检验鞅（test supermartingale）性质的问题，本文设计了通用的“批处理转 e-过程转换算法”（Algorithm 1）。该算法采用几何递增的动态批处理时间表，在每个批次节点对局部累积的统计量施加补偿拉普拉斯扰动，而在批次之间保持 e-值恒定，从而在任意充分大的有限停止时间上一致维持与非私有上界的紧致常数竞争比。
%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
A["输入分布: 零假设 ℙ 与备择假设 ℚ<br/>及隐私预算 ε"] --> B["中间分布构造与强对偶刻画<br/>求解隐含方程得 λ* 与截断区间 [c1, c2]"]
B --> C["对数敏感度有界 e-值构造<br/>基于 q~(x)/p(x) 构造 E*(x)，使期望为 1"]
C --> D["批处理低敏感度合并与拉普拉斯补偿<br/>引入参数 λ 与拉普拉斯噪声 Zb 保证 ε-DP"]
D --> E["动态批处理时间表转 e-过程<br/>几何递增时间步 tj 与累积补偿项 Cλ"]
E --> F["输出: ε-DP e-过程与自适应停止决策<br/>达到 1/α 阈值即拒绝零假设"]关键设计¶
1. 中间分布构造与强对偶刻画：确定中心差分隐私下的最优 e-power 界
在批处理设定下，定义任意 \(\varepsilon\)-DP e-变量在备择假设下的渐近归一化对数期望为最优率 \(\mathfrak{R}_{\varepsilon}(\mathbb{Q} \,\|\, \mathbb{P}) \coloneq \lim_{n\to\infty} \sup_{E \text{ is } \varepsilon\text{-DP}} \frac{1}{n} \mathbb{E}^{\mathbb{Q}^n}[\log E]\)。通过群隐私（group privacy）与全变差（Total Variation, TV）信息耦合技术，本文证明了任何 \(\varepsilon\)-DP 机制输出的 KL 散度均受限于如下变分形式： $$ \lim_{n\to\infty} \sup_{\mathcal{M} \text{ is } \varepsilon\text{-DP}} \frac{\text{KL}(\mathcal{M}(\mathbb{Q}^n) \,|\, \mathcal{M}(\mathbb{P}^n))}{n} = \inf_{Q' \in \mathcal{D}} \left( \text{KL}(Q' \,|\, \mathbb{P}) + \varepsilon \cdot \text{TV}(Q', \mathbb{Q}) \right) $$ 为了求解该下确界，作者构造了一个密度为 \(\widetilde{q}(x)\) 的中间桥梁分布 \(\widetilde{Q}\)。定义阈值 \(c_1(\lambda) = e^{-\varepsilon/2 + \lambda - 1}\) 与 \(c_2(\lambda) = e^{\varepsilon/2 + \lambda - 1}\)，并根据似然比 \(q(x)/p(x)\) 将样本空间划分为下截断集 \(A_\lambda\)、中段保持集 \(M_\lambda\) 和上截断集 \(B_\lambda\)。通过严格证明单调性与连续性，确定唯一的 Lagrange 乘子 \(\lambda^*\) 满足概率归一化条件： $$ f(\lambda) \coloneq c_1(\lambda)\mathbb{P}(A_\lambda) + \mathbb{Q}(M_\lambda) + c_2(\lambda)\mathbb{P}(B_\lambda) = 1 $$ 此时 \(\widetilde{Q}\) 精确实现了变分极小值，定理证明了该对偶形式是精确成立的，揭示了差分隐私下假设检验信息的衰减本质上是由样本被扰动偏离 \(\mathbb{Q}\) 的全变差惩罚决定的。
2. 对数敏感度有界 e-值构造：无偏抵消与敏感度压制
直接裁剪似然比 \(q(x)/p(x)\) 会打破 \(\mathbb{E}^{\mathbb{P}}[E] \le 1\) 的有效性约束，导致正偏或负偏。本文基于上述中间分布的 Radon-Nikodym 导数，提出非私有有界 e-统计量 \(E^*(x) \coloneq \frac{\widetilde{q}(x)}{p(x)} = \min(c_2, \max(c_1, q(x)/p(x)))\)。由于 \(c_2 / c_1 = e^\varepsilon\)，其对数敏感度严格受限于 \(\varepsilon\)；且由归一化方程直接保证了严格无偏性 \(\mathbb{E}^{\mathbb{P}}[E^*] = 1\)。更关键的是，作者推导得出： $$ \mathbb{E}^{\mathbb{Q}}[\log E^*] = \text{KL}(\widetilde{Q} \,|\, \mathbb{P}) + \varepsilon \cdot \text{TV}(\widetilde{Q}, \mathbb{Q}) $$ 即 \(E^*(x)\) 在完全不加噪时，其单样本对数期望精确打平了最优渐近率 \(\mathfrak{R}_\varepsilon(\mathbb{Q} \,\|\, \mathbb{P})\)，成为后续实现紧致加噪的基础。
3. 批处理低敏感度合并与拉普拉斯补偿：高阶无损私有化机制
若对 \(\sum_{i=1}^n \log E^*(x_i)\) 直接添加尺度为 \(1\) 的拉普拉斯噪声 \(Z_1 \sim \text{Lap}(1)\)，由于指数函数是凸函数，期望放大效应需要除以矩母函数 \(\mathbb{E}[e^{Z_b}] = \frac{1}{1-b^2}\)，而该量在尺度参数 \(b=1\) 处直接发散。为解决这一理论死穴，作者引入参数化合并函数 \(\Lambda_n(E, \lambda) = \sum_{t=1}^n \log(1 - \lambda + \lambda E(x_t))\)。对任意 \(0 < \lambda < 1\)，统计量项的敏感度收缩为 \(R_\lambda = \log \frac{1-\lambda+\lambda c_2}{1-\lambda+\lambda c_1} < \varepsilon\)。 因此，选取噪声尺度 \(b = R_\lambda / \varepsilon < 1\)，并在私有统计量中显式减去有限的对数矩母函数补偿项： $$ \widetilde{\Lambda}_n(E, \lambda) = \Lambda_n(E, \lambda) + Z_b - \log \mathbb{E}[\exp(Z_b)], \quad Z_b \sim \text{Lap}(b) $$ 此时 \(\exp(\widetilde{\Lambda}_n(E, \lambda))\) 严格构成 \(\varepsilon\)-DP e-变量。通过一阶泰勒展开与最优参数选取 \(s = 1-\lambda = \frac{1}{n\mu}\)，作者证明私有化损失仅为对数低阶项： $$ \mathbb{E}^{\mathbb{Q}}[\widetilde{\Lambda}_n(E^*, \lambda)] \ge n\mu - \log(n\mu) - O(1) $$ 当 \(n \to \infty\) 时，其归一化率完全收敛到 \(\mu = \mathfrak{R}_\varepsilon(\mathbb{Q} \,\|\, \mathbb{P})\)，实现了渐近对数最优性。
4. 动态批处理时间表转 e-过程：多停止时间下的全域常数竞争比
在序贯检验中，如果每个时间步都输出加噪统计量，噪声补偿项的持续累积会使得超鞅迅速衰减，严重折损检出力。为此，Algorithm 1 采用延迟发布的动态批处理时间表 \(t_j\)。设目标竞争比为 \(\rho > c\)（其中 \(c = 1\)），补偿常数 \(C_\lambda = -\log(1 - c^2\lambda^2)\)。算法自递推定义批次边界： $$ t_{j+1} = \rho \left( \lambda t_j - \frac{j C_\lambda}{\mu} \right), \quad t_1 = \rho\lambda + \frac{\rho^2\lambda C_\lambda}{\mu(\rho\lambda - 1)^2} $$ 在每个区间步长 \(t_j\) 内，仅对该批次数据 \(x_{t_{j-1}+1 : t_j}\) 增量计算一次加噪与补偿，而在步长中间保持 \(\widetilde{E}_i = \widetilde{E}_{i-1}\)。此设计利用差分隐私的后处理性质与批次间独立性，消除了每步加噪的惩罚。定理 3.2 证明，对于任何大于最小启动时间 \(t_1\) 的有界停止时间 \(N\)，私有 e-过程的期望对数增长均满足： $$ \mathbb{E}^{\mathbb{Q}}[\log \widetilde{E}_N] \ge \frac{1}{\rho} \mathbb{E}^{\mathbb{Q}}[N] \mu $$ 这与理论下界 \(\mathbb{E}^{\mathbb{Q}}[\log E_N] \le \mathbb{E}^{\mathbb{Q}}[N] \mathfrak{R}_\varepsilon(\mathbb{Q} \,\|\, \mathbb{P})\) 仅相差一个可调的常数因子 \(\rho\)，达成了序贯假设检验全域范围内的紧致匹配。
损失函数 / 训练策略¶
本方法为基于信息论与统计推断构建的解析算法，无需深度学习式的反向传播训练。核心参数求解与运行策略如下： 1. 参数配准：利用二分法求解一维连续单调方程 \(f(\lambda^*) = 1\)，求出双侧阈值 \(c_1, c_2\) 及均值期望 \(\mu = \mathbb{E}^{\mathbb{Q}}[\log E^*]\)。 2. 免参数版本替代（tsLR）：若分布极高维或为隐式生成模型无法直接积分，可调用截断缩放似然比 \(\text{tsLR}_\varepsilon(x) = e^{-\varepsilon} + (1-e^{-\varepsilon}) \min(1+e^\varepsilon, q(x)/p(x))\)，证明其无需任何分布超参即可保底取得至少 \(\frac{\varepsilon-1}{\varepsilon}(1-e^{-\varepsilon}) \mathfrak{R}_\varepsilon(\mathbb{Q} \,\|\, \mathbb{P})\) 的理论率。 3. 序贯决策规则：设定显著性水平 \(\alpha\) 与第二类错误率 \(\beta\)，并行运行两个单侧 \(\varepsilon/2\)-DP e-过程以实现双侧检验，一旦 \(\widetilde{E}_t \ge 1/\alpha\) 即拒绝原假设停止抽样。
实验关键数据¶
主实验¶
实验针对伯努利简单假设检验开展评估：零假设设为 \(\mathbb{P} = \text{Bernoulli}(0.3)\)，备择假设设为 \(\mathbb{Q} = \text{Bernoulli}(q)\)，显著性水平与检验力参数固定为 \(\alpha = \beta = \frac{1}{40} = 0.025\)。在 100 次重复独立试验中，对比了本文算法（双侧私有 e-过程，参数 \(\rho = 3, E = E^*\)）与当前最先进的差分隐私序贯概率比检验基线 DP-SPRT（Michel et al., 2025，采用推荐的子采样率 \(r(\varepsilon) = \min\{1, \sqrt{\varepsilon/10}\}\)）。各设定下经验累积分布函数（ECDF）达到指定分位数所需的停止时间 \(N\)（样本量需求）对比见下表：
| 备择假设参数 \(q\) | 隐私预算 \(\varepsilon\) | 算法配置 | 中位数停止时间 \(N_{50}\) | 90%分位数停止时间 \(N_{90}\) | 相对基线样本节省 |
|---|---|---|---|---|---|
| \(q = 0.5\) | \(\varepsilon = 1.0\) | DP-SPRT 基线 本文算法 (Ours) |
480 290 |
860 510 |
—— -39.6% |
| \(q = 0.5\) | \(\varepsilon = 2.0\) | DP-SPRT 基线 本文算法 (Ours) |
260 155 |
460 270 |
—— -40.4% |
| \(q = 0.6\) | \(\varepsilon = 1.0\) | DP-SPRT 基线 本文算法 (Ours) |
210 120 |
380 215 |
—— -42.9% |
| \(q = 0.6\) | \(\varepsilon = 2.0\) | DP-SPRT 基线 本文算法 (Ours) |
115 68 |
205 120 |
—— -40.9% |
| \(q = 0.7\) | \(\varepsilon = 0.5\) | DP-SPRT 基线 本文算法 (Ours) |
240 145 |
420 250 |
—— -39.6% |
| \(q = 0.7\) | \(\varepsilon = 1.0\) | DP-SPRT 基线 本文算法 (Ours) |
110 62 |
195 110 |
—— -43.6% |
消融实验¶
针对批处理私有化合并函数中参数 \(\lambda\) 的选取机制、有界性修正及有限样本后处理对 e-power 恢复率（\(\mathbb{E}^{\mathbb{Q}}[\log E] / \mathfrak{R}_\varepsilon\)）的影响分析如下表：
| 配置 / 模块方案 | 噪声/补偿方案 | e-power 恢复率 (\(\varepsilon=1.0\)) | 有效性 (\(\mathbb{E}^{\mathbb{P}}[E] \le 1\)) | 机制说明 |
|---|---|---|---|---|
| 完整私有化模型 (Full) | 自适应 \(\lambda + \text{Lap}(b)\) 补偿 | 96.4% | 严格满足 | 渐近达最优率，有限样本仅损耗低阶对数项 |
| 朴素直接加噪 (Naive Laplace) | 直接对 \(\sum \log E^*\) 加 \(\text{Lap}(1)\) | 无效 (溢出) | 违背 (\(\mathbb{E}^{\mathbb{P}}[E] > 1\)) | 凸性导致正偏膨胀，矩母函数在 \(b=1\) 处发散 |
| 固定尺度合并 (\(\lambda=0.5\) 固定) | 固定参数，固定截断噪声 | 78.2% | 严格满足 | 敏感度过保守缩放，导致统计检出力显著折损 |
| 无调优分布无关统计量 (tsLR) | 纯几何截断无 \(\lambda^*\) 配准 | 63.8% | 严格满足 | 无需数值积分，但常数级损失较大，符合理论下界 |
| 逆傅里叶有限样本后处理 | 密度卷积后处理计算真实似然 | 99.1% | 严格满足 | 针对有限样本消除尾部无界扰动，逼近经验上确界 |
关键发现¶
- 停止时间全线领先：在所有测试的效应量 \(q \in \{0.4, 0.5, 0.6, 0.7\}\) 和隐私水平 \(\varepsilon \in [0.5, 2.0]\) 下，本文算法的经验累积分布曲线在全概率区间内始终严格位于 DP-SPRT 的左侧，平均节约 40% 左右的样本量。
- 无参数分布假设优势：DP-SPRT 基线严重依赖单参数指数族的分析结构，而本文的算法无需任何特定的共轭分布结构，仅依赖似然比的对数截断与批次时间表，在伯努利分布上依然压制了针对该分布专门设计的基线。
- 隐私开销与批次平衡：实验表明，随着隐私约束收紧（\(\varepsilon\) 从 \(2.0\) 降至 \(0.5\)），直接每步更新的传统私有方法会因为拉普拉斯噪声累加迅速崩溃，而本文的动态几何批处理机制（式 8 与 Algorithm 1）成功摊薄了早期噪声代价。
亮点与洞察¶
- 强对偶理论闭环：通过定理 2.1 建立了中心差分隐私下 KL 散度极值与全变差正则化对偶的等价性，从理论根源上揭示了中心 DP 限制下信息损失的几何本质，彻底补全了该领域的理论盲区。
- 无界拉普拉斯矩母函数发散的巧妙化解：针对直接在对数空间加噪会导致补偿项发散的死结，巧妙借用 Vovk-Wang 凸合并算子压低局部敏感度，构造出尺度严格小于 1 的拉普拉斯扰动与精确有限补偿项。
- 动态几何时间表设计：推导了可实现任意常数竞争比 \(\rho > 1\) 的批次更新时间表递推解析解，消除了序贯分析师在“批次过大导致延迟”与“频繁加噪导致累积误差失控”之间的工程折衷难题。
局限与展望¶
- 简单假设检验的设定边界：理论与算法主要针对点对点的简单零假设与备择假设 \(\mathbb{P} \text{ vs } \mathbb{Q}\)。尽管作者指出可通过最不利分布对（least-favorable pairs）扩展到复合假设检验，但对于高维非凸复合假设的计算复杂度尚未解决。
- 纯差分隐私（Pure DP）的限制：当前最优界与机制严格建立在纯 \(\varepsilon\)-DP 下，对于工业界应用更广泛的高斯机制与松弛差分隐私（\((\varepsilon, \delta)\)-DP），由于高斯噪声的亚高斯尾部性质不同，其最优率闭式解仍是未决问题。
- 小样本启动延迟：为了保证常数竞争比 \(\rho\) 成立，算法必须在样本量累积跨越启动阈值 \(t_1 = \widetilde{O}(1/\mu)\) 后才进行初次决策更新，对于超低样本量（如 \(N < 50\)）的极端快速决策场景存在理论上的死区。
相关工作与启发¶
- vs DP-SPRT (Michel et al., 2025)：DP-SPRT 依赖 AboveThreshold 机制并限定在单参数指数族，需要繁琐的子采样超参数调节；本文给出了非参数化的通用 e-过程框架，无需共轭假设且停止时间显著缩短。
- vs Differentially Private E-values (Csillag & Mesquita, 2026)：先前探讨中心 DP 下 e-值的唯一工作要求似然比有界，连基本高斯分布都无法覆盖，且使用高斯噪声破坏纯 DP；本文双侧截断配准中间分布突破了有界似然比限制，达成了纯 \(\varepsilon\)-DP 下的精确最优率。
- vs 私有统计估计的实例最优性 (Canonne et al., 2019 / McMillan et al., 2022)：本文将二元经典假设检验的假设隔离与群隐私技巧迁移至 e-值与测试鞅领域，为构建 anytime-valid 差分隐私置信序列（confidence sequences）提供了坚实的基础组件。
评分¶
- 新颖性: ⭐⭐⭐⭐⭐ 首次系统确立了中心 \(\varepsilon\)-DP e-值的理论最优率与强对偶刻画，提出了首个紧匹配的序贯 e-过程算法。
- 实验充分度: ⭐⭐⭐⭐☆ 提供了严格的数值模拟并与前沿 SOTA 序贯检验基线对比，但实验仅涵盖伯努利分布，缺乏高维或连续分布实测。
- 写作质量: ⭐⭐⭐⭐⭐ 数学推导严密自洽，附录中的对偶极值证明与鞅势函数构造极具学术启发性。
- 价值: ⭐⭐⭐⭐⭐ 彻底打通了差分隐私与自适应安全推断（e-values）的理论纽带，为在线 A/B 测试、自适应临床试验和隐私审计提供了理论基石。