技术摘要：关于具有私有查询（Private Oracles）的私有优化之梯度复杂度

问题陈述

本文研究了针对 Lipschitz 连续凸损失函数的差分隐私（DP）经验风险最小化（ERM）和随机凸优化（SCO）的查询复杂度（以一阶查询次数衡量的运行时间）。作者关注两种不同的设定：

1. 具有私有查询的非光滑损失： 优化器与一个“代理查询”（proxy oracle）进行交互，该查询处理一个小批量（minibatch）梯度并返回满足差分隐私（具体为 $\rho$-zCDP）的消息。这模拟了如 DP-SGD 等常见做法，即在传输前对梯度进行扰动。
2. 具有私有优化器的光滑损失： 放宽了假设，仅要求最终的优化过程满足 $(\epsilon, \delta)$-DP，而不限制内部查询机制的私有性。

主要目标是建立实现超额风险（excess risk）$\alpha$ 所需的梯度查询次数的下界，具体分析隐私约束和维度 $d$ 如何影响运行时间，并将其与非私有情况进行对比。

方法论

作者采用了“向量发现”（vector discovery）与信息论下界技术的混合方法。

硬问题构造

下界的证明核心依赖于一种受 Nemirovski 函数启发并增加了正则化项的特定损失函数构造。该损失函数定义为：
$$L(w) = \max \left\{ \max_{k \in [K]} \{ |\langle w, X_k \rangle - \alpha| \}, \| \Pi_V w \| \right\}$$
其中：

• $X_1, \dots, X_K$ 是 $\mathbb{R}^d$ 中的随机正交向量。
• $V$ 是与 $\text{span}(\{X_k\})$ 正交的随机子空间。
• $\Pi_V$ 是向 $V$ 的正交投影。
• 该损失在 ERM 设定中被复制 $n$ 次。

信息论分析

证明策略在于展示：为了最小化该损失，优化器必须“发现”每个向量 $X_k$。然而，不同于标准的向量发现（观察到向量即可），在这里优化器必须在隐私约束下获得关于每个 $X_k$ 的高互信息量。

• 互信息追踪： 作者追踪了条件互信息之和 $\sum I(X_k; W | X_{\neq k}, V)$，其中 $W$ 是输出解。他们指出，即使已知其他向量，估计 $X_k$ 仍然是一个高维问题。
• 隐私约束： 对于私有查询，作者利用 $\rho$-zCDP 和组隐私（group privacy）的性质来限制关于 $X_k$ 的信息泄露。他们证明，除非优化器进行 $\Omega(d)$ 次查询以学习子空间 $V$，否则无法有效地利用未加惩罚的子空间来估计 $X_k$。
• 信息受限的查询： 该技术扩展到了具有有限信息容量 $\Gamma$（比特）的查询，表明优化器必须进行足够多次的查询以积累足够的梯度信息。

核心贡献与结果

1. 具有私有查询的非光滑优化

论文得出结论：对于维度 $d \geq 1/\alpha^2$ 的情况，任何与 $\rho$-zCDP 代理查询交互的优化器，其期望运行时间为：
$$\Omega\left( \min\left\{ \frac{\sqrt{d}}{\alpha^2 \sqrt{\rho}} + \frac{d}{\bar{m}\rho}, \frac{d}{\log(1/\alpha)} \right\} \right)$$
其中 $\bar{m}$ 是最大小批量大小。

• 紧致性（Tightness）： 在 $d \geq 1/\alpha^4$ 的区间内，通过对 DP-SGD 的分析，该下界被证明是紧致的（忽略对数因子）。
• 批量大小的影响： 该结果明确表征了小批量大小（$\bar{m}$）对私有学习动态的负面影响。如果 $\bar{m} < \sqrt{d}$，运行时间惩罚会增加。
• 对 DP-SGD 的推论： 对于批量大小为 $m$ 的 DP-SGD，其运行时间为 $\Omega(\min\{ \frac{\sqrt{d} + d/m}{\alpha^2}, \frac{d}{m \log(1/\alpha)} \})$。

2. 具有信息受限查询的非光滑优化

通过扩展证明技术，作者表明，如果代理查询传输关于梯度的最多 $\Gamma$ 比特信息，则所需的查询次数为：
$$\Omega\left( \min\left\{ \frac{d}{\alpha^2 \Gamma}, \frac{d}{\log(1/\alpha)} \right\} \right)$$
这一结果突显了梯度量化技术在私有优化中的根本局限性，表明优化器必须有效地利用“全部”梯度信息才能成功。

3. 具有私有优化器的光滑优化

对于光滑损失（仅要求最终优化器满足 $(\epsilon, \delta)$-DP，而非查询本身），作者给出了期望查询次数的下界：
$$\tilde{\Omega}\left( \frac{\sqrt{d}}{\alpha} + \min\left\{ \frac{1}{\alpha^2}, n \right\} \right)$$

• 隐私独立性： 值得注意的是，该下界并不依赖于隐私参数 $\epsilon$（假设 $\alpha$ 固定）。作者认为，更强的隐私保证只会影响最小可达精度（$\alpha^*_{\epsilon, \delta}$），而一旦目标精度确定，则不会改变运行时间成本。
• 紧致性： 对现有算法（Phased SGD）的改进表明，该界限是近乎紧致的。

4. ERM 与 SCO 之间的归约

论文通过一种在运行时间和隐私上仅产生 $\text{polylog}(n)$ 开销的归约方法，证明了 DP-SCO 的难度并不高于 DP-ERM（在多项式对数因子范围内）。这意味着，刻画 DP-ERM 的复杂度足以理解大多数情形下的 DP-SCO 复杂度。

意义与主张

作者将这项工作定位为首个利用超越局部隐私模型的差分隐私来提供查询复杂度下界的研究。

• 运行时间惩罚： 结果正式证明，一类私有优化器（使用私有查询的优化器）相比于非私有优化器，会产生与维度相关的运行时间惩罚。在非私有设定下，非光滑函数的复杂度为 $\Theta(1/\alpha^2)$；而在私有设定下，根据不同区间，会引入 $\sqrt{d}$ 或 $d$ 的因子。
• 实际相关性： 私有查询模型受到联邦学习和分布式训练等实际场景的启发，在这些场景中，不可信的服务器会向节点查询梯度。研究结果表明，常用于隐私放大的小批量大小，从根本上降低了高维情况下的运行性能。
• 量化的局限性： 信息受限查询的结果为梯度量化在私有设置中的极限提供了理论依据，表明将梯度压缩到低于某一阈值会必然导致查询次数成比例增加。

论文总结道，尽管算法的进步提高了上界，但隐私在查询复杂度方面的基本代价现在得到了更好的刻画，揭示了维度、批量大小与隐私之间此前在中心 DP 模型中尚未被充分理解的权衡关系。