技术摘要：近优广义私有测试

1. 问题定义

本文解决了广义私有测试问题，这是由 Liu 和 Talwar (STOC 2019) 引入的差分隐私 (DP) 中的基本挑战。与在具有有界 Lipschitz 敏感性的实值输入上运行的标准私有阈值测试不同，广义私有测试在一系列黑盒 $\varepsilon_t$-DP 机制 $(M_t)_{t \ge 1}$ 上运行。

形式化设置：

• 输入： 私有数据集 $X$（或数据集流 $X_t$）、目标成功概率 $p^* \in (0, 1)$，以及机制序列 $M_t: \mathcal{X} \to \{-1, +1\}$，其中每个 $M_t$ 满足 $(\varepsilon_t, \delta_t)$-DP。
• 目标： 识别第一个索引 $t$，使得成功概率 $p_t = \Pr[M_t(X) = +1]$ 超过阈值 $p^*$。
• 约束： 测试过程本身必须满足全局 $\varepsilon$-DP 保证。
• 准确性： 由拒绝阈值 $\bar{p} < p^*$ 定义。以高概率，如果 $p_t \le \bar{p}$，则机制继续运行；如果 $p_t \ge p^*$，则停止。目标是缩小差距 $p^* - \bar{p}$。

现有解决方案面临显著的权衡：

1. Liu 和 Talwar [LT19]： 实现了按 $\bar{p} \approx p^* (\beta^2/T)^{12\varepsilon_1/\varepsilon}$ 缩放的拒绝阈值，但需要纯 DP 输入，且仅实现近似 DP 输出。其样本复杂度随流长度 $T$ 表现不佳。
2. Cohen 等人 [CLN+23] 和 Ghazi 等人 [GKK+25]： 为纯 DP 输入提供纯 DP 输出，但遭受按 $\bar{p} \approx p^* \beta/T$ 缩放的拒绝阈值，对于大 $T$ 而言，渐近表现不如 [LT19]。

2. 方法论：广义阈值机制 (GTM)

作者引入了一种新算法，即广义阈值机制 (GTM)，该算法在无论输入是纯 DP 还是近似 DP 的情况下均提供纯 DP 保证，同时实现了近优的准确性和样本复杂度。

核心技术见解

GTM 依赖于三项主要技术创新：

1. 泊松采样与随机化速率：
   算法不从固定数量的评估中抽取，而是从泊松分布 $N_t \sim \text{Po}(\lambda_t)$ 中抽取评估次数 $N_t$。速率参数 $\lambda_t$ 被随机化以掩盖真实的成功概率 $p_t$。具体而言，$\lambda_t = \rho_t \exp(\varepsilon_t Z_t)$，其中 $Z_t$ 是从指数分布导出的噪声变量。这种结构允许使用类似于稀疏向量技术 (SVT) 的耦合论证，但针对概率机制进行了调整。

2. 方向适应性（翻转变体）：
   该机制基于方向参数 $s_t \in \{+1, -1\}$ 在两种模式下运行：

   • 直接模式 ($s_t = +1$)： 如果 $+1$ 结果的计数 $K_t$ 超过阈值，则停止。当 $p^*$ 较小时，这是最优的。
   • 翻转模式 ($s_t = -1$)： 如果 $K_t$ 低于阈值则停止（实际上是对 $1-p_t$ 与 $1-p^*$ 进行测试）。当 $p^*$ 接近 1 时，这是最优的。
     算法自适应地选择方向以最小化拒绝阈值差距，实现 $\bar{p}_t = \max\left(\frac{p^*_t}{\gamma \Lambda_t}, 1 - \gamma \Lambda_t (1 - p^*_t)\right)$。

3. 通过随机响应进行净化：
   为了处理近似 DP 输入 $(\varepsilon_t, \delta_t)$，GTM 应用“净化”步骤。对 $M_t$ 的每次评估都通过一个交叉概率为 $\phi_t \approx \delta_t/\varepsilon_t$ 的二元对称信道。这将近似 DP 机制转换为纯 $\varepsilon_t$-DP 机制，且对成功概率的扰动可忽略不计，从而使 GTM 能够为输出保持纯 $\varepsilon$-DP 保证。

参数调整

该机制引入了一个“噪声惩罚”因子 $\Lambda_t$，决定了准确性损失。作者表明，通过调整参数 $\theta$ 和 $\gamma$，$\Lambda_t$ 可以按以下方式缩放：
$$\Lambda_t = \left( \frac{t}{\beta} \right)^{(2+\theta)\varepsilon_t/\varepsilon} \cdot \left( \frac{1}{\beta} \right)^{(3+\theta+2/\theta)\varepsilon_t/\varepsilon}$$
关键在于，$t$ 和 $\beta$ 的指数可以被驱动得任意接近理论下界。

3. 主要贡献与结果

理论上限

本文证明，对于任意 $\theta > 0$ 和 $\gamma \in (1, 2]$，GTM 实现了：

• 隐私： 纯 $\varepsilon$-DP，即使输入机制仅为 $(\varepsilon_t, \delta_t)$-DP。
• 准确性： 拒绝阈值 $\bar{p}_t$，使得比率 $p^*/\bar{p}_t$ 按 $\tilde{O}((t/\beta)^{(2+\theta)\varepsilon_t/\varepsilon})$ 缩放。这改进了 [LT19] 中的指数 $12\varepsilon_1/\varepsilon$ 以及 [CLN+23] 中的线性 $\beta/T$ 缩放。
• 样本复杂度： 步骤 $t$ 处的评估次数 $N_t$ 以高概率被限制为：
  $$N_t = O\left( \frac{\ln(t/\beta)}{(\gamma-1)^2} \cdot \max\left( \frac{\Lambda_t}{p^*_t}, \frac{1}{1-p^*_t} \right) \right)$$
  在特定参数设置下，摊销样本复杂度随 $t$ 对数缩放。

下界

作者证明了任何广义私有测试器的匹配下界。他们表明，准确性损失因子 $\Lambda_T$ 本质上必须按 $(T/\beta)^{c \cdot \varepsilon_1/\varepsilon}$ 缩放，其中 $c$ 为某个常数。这证实了 GTM 对 $T$ 和 $\beta$ 的依赖性是近优的，仅在指数上的常数项存在微小差异。

事后隐私保证

本文引入了一种事后隐私变体，其中隐私损失 $\tilde{\varepsilon}$ 随流长度对数缩放（$\tilde{\varepsilon} \approx \varepsilon + \varepsilon_t \ln(t/\beta)$）。在这种设置下，噪声惩罚 $\Lambda_t$ 变为与 $t$ 无关的通用常数，显著提高了长流的准确性。

4. 应用：连续观察 (CO) 归约

提出的主要应用之一是从连续观察 (CO) 优化到批量设置的黑盒归约。

• 问题： 在 CO 中，数据以流的形式到达，必须在每一步输出解决方案，同时保持全局 DP。标准技术（如稀疏向量技术）在此处失效，因为优化中的效用函数（例如次模最大化）通常缺乏有界 Lipschitz 敏感性。
• 解决方案： GTM 允许系统监控批量算法的输出质量是否显著下降。通过将批量算法视为黑盒机制，GTM 仅在必要时触发重新计算。
• 影响： 这产生了 CO 设置中一大类最大化问题（包括基数/拟阵约束下的次模最大化、最密子图和 Max-Cut）的首个 DP 算法。
• 优势： 与之前需要通过组合实现 $\sqrt{t}$ 缩放的方法不同，该方法实现了隐私参数按 $\varepsilon_t \approx \varepsilon / \ln^2(t/\beta)$ 缩放的准确性保证，从而在长流中保持高准确性。

5. 意义与主张

本文声称解决了广义私有测试中隐私、准确性和样本复杂度之间的张力：

1. 最优性： GTM 实现了近优的准确性和样本复杂度，缩小了现有上界和下界之间的差距。
2. 鲁棒性： 它为近似 DP 输入提供纯 DP 保证，这是 [LT19] 等先前工作所缺乏的特性。
3. 实用性： 自适应阈值和事后隐私设置允许灵活的权衡，特别有利于超参数优化和流长度无界的持续学习场景。
4. 新能力： 归约到 CO 设置使得现有的批量 DP 算法能够应用于动态数据流，而无需以前认为此类归约所必需的有界 Lipschitz 敏感性假设。

作者强调，虽然该机制引入了噪声惩罚 $\Lambda_t$，但正如下界所示，这种惩罚是不可避免的，并且通过他们的构造将其最小化到了最大可能程度。这项工作并未声称完全消除对 $T$ 和 $\beta$ 的多项式依赖，但证明了指数可以被驱动得任意接近理论最小值。