🤖 machine learning

Privacy Amplification in Differentially Private Zeroth-Order Optimization with Hidden States

本文通过引入一种混合噪声机制和一种新颖的耦合分析方法，克服了各向异性更新导致的标准移位散度框架的局限性，从而首次给出了零阶优化的收敛差分隐私界。

原作者： Eli Chien, Wei-Ning Chen, Pan Li

发布于 2026-05-04

📖 1 分钟阅读☕ 轻松阅读

原作者： Eli Chien, Wei-Ning Chen, Pan Li

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

以下是用简单语言和创造性类比对该论文的解读。

宏观图景：在修复巨型拼图时隐藏踪迹

想象你有一个巨大且复杂的拼图（一个庞大的 AI 模型）需要解决。你希望使用一种称为零阶优化（Zeroth-Order Optimization）的特定方法来求解。

问题所在：
通常，要解决拼图，你需要观察拼图块并精确判断移动它们的方向（梯度）。但在“零阶”方法中，你被禁止直接观察拼图块。相反，你必须猜测一个移动方向，看看画面效果如何；再猜测另一个方向，看看效果如何；然后对这些猜测取平均值，从而推断出最佳方向。这就像试图通过撞墙和听回声来寻找黑暗迷宫的出口，而不是查看地图。

隐私挑战：
你希望利用来自许多人的数据来求解这个拼图，但必须保护他们的隐私（差分隐私）。为此，你通常需要在你的猜测中添加“噪声”（干扰），以便没人能判断是否使用了某个特定人的数据。

旧方法（“组合”陷阱）
以往的方法将拼图求解过程中的每一步都视为独立事件。它们认为：“如果我在第 1 步、第 2 步、第 3 步……都添加噪声，那么总的隐私成本会像账单一样累加。”如果你走了 1,000 步，隐私成本就会变得巨大，最终你不得不因为“花光”了所有隐私预算而停止。这就像每开一英里路都要付过路费；最终，你无法负担完成旅程的费用。

该论文的突破：
这篇论文指出：“等一下！如果我们保持中间步骤隐藏，就不需要为每一步都付过路费了。”

他们引入了一个称为迭代隐私放大（Privacy Amplification by Iteration, PABI）的概念。可以这样理解：

旧方法：你每走 10 英尺就告诉所有人你的位置。他们可以追踪你的确切路径。
新方法：你只告诉所有人起点和终点。你让中间的路径保持秘密。因为路径被隐藏了，你在开始时添加的“噪声”在到达终点时实际上能更好地保护你的身份。隐私成本停止增长，甚至趋于平稳。

他们克服的具体障碍

作者在尝试将这种“隐藏路径”的想法应用于零阶方法时，面临两个主要问题：

1. “各向异性”噪声问题（单向干扰）
在标准方法中，你在所有方向添加噪声（就像电视屏幕上的全屏雪花点）。而在零阶方法中，你只在猜测的特定方向添加噪声（就像只有一条线上的雪花点）。

问题：用于证明“全方向”噪声隐私性的数学工具不适用于“单方向”噪声。这就像试图把方钉子塞进圆孔里。标准数学指出：“这行不通，因为噪声不是均匀的。”

2. “利普希茨”（Lipschitz）
为了证明隐私性，数学家通常需要证明系统是“稳定”的——即输入的微小变化会导致输出的微小且可预测的变化。

问题：在零阶方法中，由于方向是随机的，系统并非始终完全稳定。它只是大多数时候稳定。旧的数学工具要求它必须始终稳定，因此失效了。

解决方案：混合引擎与“幽灵”过程

作者构建了一个新引擎来解决这些问题：

1. 混合噪声机制
他们不再在“全方向噪声”和“单方向噪声”之间二选一，而是创造了一种混合方案。

他们在猜测的特定方向添加噪声（以保持拼图求解的高效性）。
他们同时在所有其他方向添加极少量的噪声（仅足以满足数学要求）。
结果：这让他们兼得两者之长：良好的拼图求解性能，以及允许进行隐私证明的数学结构。

2. “幽灵”过程（耦合技巧）
由于无法使用旧的数学工具，他们发明了一个新技巧。

想象两个人，Alice 和 Bob，试图用略有不同的数据解决同一个拼图。
作者创建了一个“幽灵”版本的过程，它恰好位于 Alice 和 Bob 的中间。
他们证明了 Alice 与“幽灵”非常接近，Bob 与“幽灵”也非常接近。
通过利用这个“幽灵”作为桥梁，他们能够证明 Alice 和 Bob 也足够接近，从而被视为具有隐私性，即使没有使用旧的数学工具。

令人惊讶的发现：更多方向 = 更好的隐私

该论文中一个最酷的发现是关于 $K$ （即你一次猜测的方向数量）的。

旧观念：使用更多方向（ $K > 1$ ）使拼图更容易解决（更好的效用），但代价是更高的隐私成本。
新发现：在这种新的“隐藏路径”分析下，使用更多方向实际上在保持拼图求解质量的同时改善了隐私。
类比：想象试图在干草堆里找一根针。如果你只看一个点，你需要大量的“掩护”（噪声）来隐藏你的行为。如果你同时看 10 个点，“掩护”就能更有效地分散开来，使观察者更难判断你具体在看哪个点。

他们主张的内容总结

他们创建了首个数学证明，表明零阶优化可以具有收敛的隐私成本。这意味着隐私成本在达到一定步数后停止增长，而不是无限增长。
他们证明了通过隐藏优化的中间步骤，可以获得比以往认为可能的更强的隐私保证。
他们表明，同时使用多个随机方向（正交方向）不仅有利于速度，实际上还是隐私的“秘密武器”。
他们提供了一种新的“混合噪声”方案，使这一切成为可能。

他们未主张的内容：

他们并未声称这能立即适用于所有类型的 AI 模型或数据集；他们的数学依赖于特定假设（例如损失函数是“平滑”且“凸”的）。
他们并未声称这解决了 AI 中的所有隐私问题，仅表明它为这种特定类型的优化方法提供了更好的理论边界。
他们尚未为公众提供现成的软件工具；这是一个理论框架，为未来的工具铺平了道路。

以下是论文《具有隐藏状态的不同隐私零阶优化中的隐私增强》的详细技术总结。

1. 问题陈述

本文解决了在差分隐私（DP）约束下训练大规模模型（如大型语言模型）时，同时管理严格内存限制所面临的挑战。

背景： 标准的一阶 DP 方法（如 DP-SGD）需要在反向传播期间存储每个样本的梯度，导致巨大的内存开销，且该开销随模型规模扩大而表现不佳。
解决趋势： 零阶优化（ZO）方法作为一种内存高效的替代方案应运而生，因为它们仅需前向传播（损失评估），而无需计算显式梯度。
差距： 虽然现有的 ZO 方法（如 DPZero）在经验上表现良好，但其理论隐私分析依赖于标准组合定理。这导致隐私成本随训练步数（ $T$ ）线性增长，迫使在效用和隐私之间进行权衡。
核心挑战： 将迭代隐私增强（PABI）——一种为一阶方法提供收敛（常数）隐私界的技术——扩展到零阶方法。
- 难点所在： 一阶 PABI 依赖于向梯度添加各向同性（与方向无关）的高斯噪声，从而允许使用“移位 Rényi 散度”引理。相比之下，高效的 ZO 方法沿随机更新方向添加各向异性（与方向相关）的标量噪声。这种各向异性破坏了标准移位散度框架所需的整体 Lipschitz 性质，使得现有的 PABI 工具无法适用。

2. 方法论

作者提出了一种结合混合噪声机制和耦合分析的新颖框架，以绕过标准分析的局限性。

A. 混合噪声机制（Noisy-ZOGD）

与其在纯方向性噪声（高效但难以分析）或纯各向同性噪声（易于分析但浪费效用）之间做出选择，作者提出了一种统一的更新规则：
$w_{t+1} = \Pi_{\mathcal{B}_R} \left[ w_t - \frac{\eta}{K} \sum_{k=1}^K \hat{g}_t(w_t; u_{t,k}) + \frac{\eta}{\sqrt{K}} \sum_{k=1}^K G^{(1)}_{t,k} u_{t,k} + \eta \sqrt{d} G^{(2)}_t \right]$

$K$ 维更新： 每步使用 $K$ 个随机方向以减少梯度估计方差。
混合噪声：
1. 方向性噪声（ $G^{(1)}$ ）： 沿更新方向 $u_{t,k}$ 添加标量高斯噪声。通过将噪声集中在敏感度存在的区域，从而保留效用。
2. 各向同性噪声（ $G^{(2)}$ ）： 在所有维度上添加微小的各向同性高斯噪声。这对于理论分析至关重要，用于处理耦合过程中的“移位”。
正交方向： 更新方向 $\{u_{t,k}\}$ 作为正交集从 Stiefel 流形中采样（而非独立同分布的随机向量），从而收紧隐私界。

B. 新颖的耦合分析（绕过移位散度）

标准的 PABI 证明依赖于移位 Rényi 散度引理，该引理要求满足整体 Lipschitz条件。由于 ZO 更新映射并非整体 Lipschitz（仅以高概率满足逐点 Lipschitz），作者构建了一个耦合辅助过程 $\tilde{W}_t$ ：

构建： 他们定义了一个辅助轨迹 $\tilde{W}_t$ ，使其位于两个相邻训练过程（数据集 $D$ 上的 $W_t$ 和数据集 $D'$ 上的 $W'_t$ ）的“中间”。
分解： 隐私分析被分为两部分：
- 全变差（TV）界： 衡量耦合失败的概率（即 $W_t$ 和 $\tilde{W}_t$ 发散）。这利用 ZO 更新的逐点 Lipschitz性质（以高概率成立）进行界定。
- Rényi 散度界： 衡量辅助过程 $\tilde{W}_t$ 与相邻过程 $W'_t$ 之间的散度。由于 $\tilde{W}_t$ 的构建使其与噪声结构对齐，这部分可以使用标准的移位高斯机制进行分析。
结果： 该方法避免了对整体 Lipschitz 常数的需求，从而即使在存在各向异性噪声的情况下也能实现收敛的隐私界。

3. 主要贡献

首个零阶收敛 PABI： 本文提供了首个理论证明，表明具有隐藏状态的零阶优化实现了收敛的隐私界（隐私成本在固定步数后饱和），而非随 $T$ 线性增长。
混合噪声机制： 引入了一种噪声注入方案，通过方向性噪声平衡效用，并通过微小的各向同性分量确保分析的可处理性。
更新维度（ $K$ ）的作用：
- 揭示在隐藏状态分析下，增加更新方向数量 $K$ 会降低隐私损失（这与标准组合分析中 $K$ 增加成本的结论相反）。
- 证明使用正交更新方向相比独立同分布的随机方向显著改善了隐私界。
新颖的耦合技术： 开发了一种特定的辅助过程构建方法，以绕过整体 Lipschitz 障碍，该技术可能适用于其他非平滑或非 Lipschitz 优化场景。

4. 主要结果

隐私界： 对于平滑、强凸损失函数，所提出的 Noisy-ZOGD 算法满足 $(\epsilon, \delta)$ $(ϵ, δ)$ -DP，其中：
$\epsilon = O\left( \sqrt{\frac{\Delta^2 \log(1/\delta)}{n^2 \sigma^2} \min\left(T, \frac{R n \sqrt{d}}{K \Delta}\right)} \right)$
- 该界在 $T \approx \frac{R n \sqrt{d}}{K \Delta}$ 处饱和，意味着进一步的迭代不会增加隐私成本。
- 该界与 $K$ 成反比，表明使用更多方向可以改善隐私。
比较：
- vs. 标准组合： 标准分析得出 $\epsilon \propto \sqrt{T}$ ，呈无界增长。所提出的方法则实现收敛。
- vs. 输出扰动： 虽然输出扰动（仅在最后添加噪声）独立于 $T$ ，但在实际 $T$ 下通常较弱。所提出的方法为中间 $T$ 提供了更紧的界。
效用： 混合噪声机制保持了与纯方向性噪声（DPZero）相同的效用保证，因为总噪声方差得以保留。

5. 意义

可扩展性： 这项工作为在 DP 和有限内存条件下训练大规模模型（数十亿参数）提供了理论依据，这是当前大语言模型微调的关键瓶颈。
算法设计： 它颠覆了“使用多个零阶方向（ $K > 1$ ）纯粹是效用权衡”的观念。本文证明这也是一种隐私收益，鼓励在 DP-ZO 算法中使用更高维度的更新。
理论进步： 通过解决 PABI 中的“各向异性噪声”问题，本文弥合了一阶和零阶隐私理论之间的显著鸿沟，为在隐私约束下分析复杂的非 Lipschitz 优化动力学提供了新工具包（结合辅助过程的耦合）。
实际影响： 为从业者提供了具体指导：使用正交方向、调整混合噪声参数 $\beta_t$ ，并利用更大的 $K$ 来实现更好的隐私 - 效用权衡，而无需增加内存成本。