Optimal Rates for Pure {\varepsilon}-Differentially Private Stochastic Convex Optimization with Heavy Tails

1. 研究背景与问题定义

核心问题：
在随机凸优化 (SCO) 问题中，给定来自未知分布 $P$ 的独立同分布数据 $Z = (z_1, \dots, z_n)$，目标是求解：
$$\min_{w \in W} \{F(w) := \mathbb{E}_{z \sim P}[f(w, z)]\}$$
其中 $W$ 是凸紧参数域，$f(\cdot, z)$ 是凸损失函数。

挑战：

1. 重尾梯度 (Heavy Tails)： 传统的差分隐私 (DP) SCO 研究通常假设损失函数具有全局有界的 Lipschitz 常数 $L$（即 $\|\nabla f(w, z)\| \le L$）。然而，在许多实际场景（如线性回归中的平方损失）中，若特征分布无界，则 $L$ 可能为无穷大。本文假设梯度仅满足有界 $k$ 阶矩条件（$k \ge 2$）：
   $$\mathbb{E}_{z \sim P} \left[ \sup_{w \in W} \|\nabla f(w, z)\|^k \right] \le G_k^k$$
   这允许梯度分布具有重尾特性，但控制了其平均行为。
2. 纯差分隐私 (Pure $\varepsilon$-DP)： 现有针对重尾数据的 DP 算法大多基于近似差分隐私 $(\varepsilon, \delta)$-DP，利用噪声截断梯度（Noisy Clipped Gradients）方法。然而，在纯 $\varepsilon$-DP（即 $\delta=0$，不允许任何隐私泄露概率）设定下，现有的截断梯度方法被认为次优，且该设定下的最优速率和高效算法此前一直是未解之谜。

目标：
确定纯 $\varepsilon$-DP 下重尾 SCO 的极小极大最优过剩风险 (Minimax Optimal Excess Risk) 速率，并设计能在多项式时间内达到该速率的算法。

---

2. 主要贡献

贡献 1：确定了最优过剩风险速率（对数因子内）

作者证明了在纯 $\varepsilon$-DP 和重尾假设下，过剩风险的上界为：
$$\tilde{O}\left( G_k D \left(\frac{d}{n\varepsilon}\right)^{1-1/k} + \frac{G_2 D}{\sqrt{n}} \right)$$
其中：

• $G_k$ 是 $k$ 阶矩界，$G_2$ 是二阶矩界。
• $d$ 是维度，$n$ 是样本量，$\varepsilon$ 是隐私预算，$D$ 是域直径。
• 第一项对应隐私误差（重尾影响），第二项对应非隐私统计误差。
• 作者还证明了几乎匹配的高概率下界，该下界比之前文献 [BD14] 的期望下界在对数因子更紧。

贡献 2：首个多项式时间的纯 $\varepsilon$-DP 算法

• 提出了名为 Localized Double Output Perturbation (LDOP) 的算法。
• 该算法以高概率在多项式时间内达到上述最优速率。
• 特殊情况： 如果最坏情况下的 Lipschitz 参数是多项式有界的，算法以概率 1 在多项式时间内运行。
• 结构化子类： 对于特定结构的问题（如欧几里得球、椭球、多面体上的 Hinge/ReLU 型损失和绝对值损失），即使最坏情况 Lipschitz 参数为无穷大，算法也能以概率 1 在多项式时间内达到最优速率。

贡献 3：基于 Lipschitz 扩展的新框架

• 摒弃了传统的“噪声截断梯度”方法。
• 引入了Lipschitz 扩展 (Lipschitz Extension) 技术：
  $$f_C(w, z) := \inf_{y \in W} [f(y, z) + C\|w - y\|]$$
  将重尾问题转化为有界 Lipschitz 常数的优化问题。
• 提出了一种联合凸重构 (Jointly Convex Reformulation) 和自适应（不精确）投影次梯度方法，能够在不知道具体 Lipschitz 常数的情况下，高效且确定性地优化扩展后的目标函数。
• 证明了在一般情况下，精确计算 Lipschitz 扩展在有限时间内是不可能的（Appendix B），因此必须依赖近似优化。

---

3. 方法论与技术细节

3.1 总体框架：人口级定位 (Population-Level Localization)

算法基于 [ALT24] 的框架，将 SCO 问题分解为一系列带正则化的经验风险最小化 (Regularized ERM) 子问题。通过多阶段迭代，逐步缩小解的搜索空间。

3.2 核心难点与解决方案

难点 1：截断梯度在纯 DP 下失效

• 截断梯度方法在 $(\varepsilon, \delta)$-DP 下有效，但在纯 $\varepsilon$-DP 下由于无法使用高级组合定理（Advanced Composition），导致隐私预算消耗过大或精度不足。
• 解决： 转向优化 Lipschitz 扩展 $f_C$。

难点 2：Lipschitz 扩展的优化与计算

• $f_C$ 的定义涉及内层优化，且 $f$ 本身可能无界，导致 $f_C$ 的 Lipschitz 常数未知。纯 DP 要求优化过程必须具有确定性的精度保证（不能以低概率失败）。
• 解决：
  1. 联合凸重构： 将最小化 $\sum f_C(w, z_i)$ 转化为最小化 $\sum [f(y_i, z_i) + C\|w - y_i\|]$，这是一个关于 $(w, y_1, \dots, y_n)$ 的联合凸问题。
  2. 自适应投影次梯度法： 使用 Algorithm 3，根据观测到的次梯度范数自适应调整步长，无需预先知道 Lipschitz 常数即可在有限步内收敛。

难点 3：Lipschitz 扩展的偏差 (Bias)

• 直接在原域 $W$ 上优化 $f_C$ 会引入与 $W$ 直径 $D$ 成正比的偏差，导致速率不优。
• 解决：输出扰动定位 (Output Perturbation Localization)
  1. 先对正则化后的 Lipschitz 扩展目标进行近似最小化。
  2. 添加拉普拉斯噪声并投影，得到一个较小的局部域 $W_0$（直径 $D_0 \ll D$）。
  3. 在 $W_0$ 上再次进行优化。由于 $W_0$ 直径小，Lipschitz 扩展引入的偏差显著降低。
  4. 最后对 $W_0$ 上的近似解再次进行输出扰动以保护隐私（双重输出扰动）。

3.3 算法流程 (Localized Double Output Perturbation)

1. 定位阶段： 使用输出扰动将解定位到小域 $W_0$。
2. 优化阶段： 在 $W_0$ 上，利用联合凸重构和自适应次梯度法，高效计算正则化 Lipschitz 扩展的近似解。
3. 隐私化阶段： 对近似解添加噪声并投影回 $W_0$，得到最终私有解。

---

4. 主要结果

4.1 理论界限

• 上界 (Theorem 3.1)： 算法输出的解 $\hat{w}$ 满足：
  $$F(\hat{w}) - F^* \le c_3 G_k D \left(\frac{d \log(1/\delta)}{n\varepsilon}\right)^{1-1/k} + c_4 G_2 D \sqrt{\frac{\log(1/\delta)}{n}}$$
  该速率在忽略对数因子后是极小极大最优的。
• 下界 (Theorem 4.1)： 证明了任何 $\varepsilon$-DP 算法的高概率过剩风险下界，与上界仅在对数因子（$d \log(1/\delta)$ vs $d + \log(1/\delta)$）上有微小差距。

4.2 计算效率

• 一般情况： 以高概率在多项式时间内运行。
• Lipschitz 有界情况： 若 $\sup \|\nabla f\|$ 多项式有界，则以概率 1 在多项式时间内运行。
• 结构化问题 (Corollary D.7)： 对于 Hinge/ReLU/绝对值损失，即使在 Lipschitz 参数无穷大的情况下，也能以概率 1 在多项式时间内运行。这是因为这些问题的 Lipschitz 扩展子梯度可以高效近似。

---

5. 意义与影响

1. 填补了理论空白： 首次解决了纯 $\varepsilon$-DP 下重尾 SCO 的极小极大速率问题，打破了此前只有近似 DP 有高效算法的局面。
2. 算法创新： 提出了一种全新的算法范式，利用 Lipschitz 扩展替代传统的梯度截断，成功克服了纯 DP 下对确定性优化精度的严格要求。
3. 实用性： 证明了在常见的机器学习损失函数（如 Hinge Loss, ReLU）和几何约束（球体、多面体）下，该理论算法是实际可执行的（多项式时间，概率 1）。
4. 下界改进： 提供了比现有文献更紧的高概率下界，为未来研究提供了更精确的基准。

总结： 这篇论文通过引入 Lipschitz 扩展和联合凸重构技术，成功地在纯差分隐私设定下，为具有重尾梯度的随机凸优化问题构建了最优且高效的算法，解决了该领域长期存在的开放性问题。