Descend or Rewind? Stochastic Gradient Descent Unlearning

本文通过引入扰动或偏置梯度系统分析框架，为随机梯度下降中的“下降删除”（D2D）和“回退删除”（R2D）算法在强凸、凸及非凸损失函数下提供了$(\varepsilon, \delta)$ 认证遗忘的理论保证，并揭示了两者在不同函数场景下的适用性差异。

要点

这篇论文探讨了一个非常有趣且重要的问题：当用户要求“忘记”他们之前上传的数据时，人工智能模型该如何优雅地“失忆”，而不需要把整个大脑（模型）重新训练一遍？

想象一下，你教了一个超级聪明的学生（AI 模型）认字。后来，这个学生发现其中有一页书（某位用户的数据）是错的，或者用户要求删除这页书。

• 传统做法：把整本书撕掉，重新从第一页开始教。这太慢了，太费钱了。
• 本文的做法：研究两种“快速失忆”的魔法，看看哪种更有效。

核心概念：两种“失忆”魔法

论文比较了两种主要的“失忆”策略，我们可以用**“登山”和“时光倒流”**来比喻：

1. 下山法 (Descent-to-Delete, D2D)

• 比喻：想象学生已经爬到了山顶（模型训练完成）。现在要删除一些数据，就像要把山顶的一块石头移走。
  • 做法：学生直接从山顶出发，沿着新的路径（没有那块石头的路）往下走几步，试图找到一个新的平衡点。
  • 优点：对于非常规则、平滑的山（数学上叫“强凸函数”），这种方法很精准，能很快找到新位置。
  • 缺点：现实中的山往往坑坑洼洼、有很多小坑（数学上叫“非凸函数”，比如现在的深度学习模型）。如果从山顶直接往下走，很容易掉进旁边的小坑里（陷入局部最优解），或者根本走不动。这就好比学生从山顶往下跳，结果卡在了半山腰的一个小土坑里，根本没把那块石头的影响真正消除。

2. 时光倒流法 (Rewind-to-Delete, R2D)

• 比喻：还是那个学生爬到了山顶。
  • 做法：学生不直接从山顶开始改，而是坐时光机回到过去，回到还没爬到山顶、还在半山腰的一个安全 checkpoint（检查点）。然后，从这个旧位置开始，重新沿着没有那块石头的路往上爬。
  • 优点：因为是从一个比较“早”且“安全”的位置重新开始，它不容易掉进小坑。无论山多崎岖（非凸函数），它都能更稳健地找到正确的新路径。
  • 缺点：需要多爬一段路（计算量比直接下山法稍大，但比重头学要快得多）。

论文发现了什么？

作者通过严密的数学证明和实验，得出了以下结论：

1. 没有“万能钥匙”：

   • 如果山非常平滑（强凸函数），“下山法”（D2D）可能更精准，因为它离目标更近。
   • 但是，现实中的 AI 模型（如大语言模型）对应的山通常非常崎岖（非凸函数）。在这种情况下，“下山法”经常失效，学生容易卡在原地不动。
   • “时光倒流法”（R2D）才是现实世界的赢家。它虽然需要多走几步，但能确保学生真正摆脱了那块石头的影响，不会卡在错误的地方。

2. 数学上的“保险”：

   • 以前大家用“下山法”做微调（Finetuning）时，其实没有数学保证说这样真的能“忘记”。
   • 这篇论文给这两种方法都穿上了“防弹衣”（数学证明）。他们证明了：只要我们在最后加一点点“噪音”（就像给学生的记忆加了一层模糊滤镜），就能从数学上保证：新模型和重新训练出来的模型，在概率上是无法区分的。 这意味着用户的数据真的被“忘记”了。

3. 效率惊人：

   • 对于“时光倒流法”，如果训练时间很长，那么“失忆”所需的时间甚至可能是一个常数（不管之前训练了多久，失忆只需要固定的一小段时间）。这就像你读了一万页书，要忘掉其中一页，只需要花几分钟重读最后几十页，而不是重新读一万页。

总结与启示

这就好比你要从一张复杂的地图中擦掉一个点：

• 下山法就像是从地图边缘直接涂改，容易涂花或者涂不干净，特别是在地图很复杂的时候。
• 时光倒流法就像是回到涂改前的状态，重新画一遍那一部分，虽然多花了一点时间，但画出来的地图清晰、准确，而且保证那个点真的被擦掉了。

这篇论文的核心贡献是：
它告诉开发者，在处理复杂的现代 AI 模型时，不要盲目使用“下山法”（直接微调），而应该尝试**“时光倒流法”（R2D）**。这不仅更安全、更可靠，而且从数学上保证了用户的隐私权利（即“被遗忘权”）真正得到了落实，同时还能节省大量的计算资源和能源。

简单来说：想真正“忘记”过去，有时候“回到过去”比“直接向前冲”更有效。

技术摘要

这是一份关于论文 《Descend or Rewind? Stochastic Gradient Descent Unlearning》（下降还是回退？随机梯度下降遗忘）的详细技术总结。

1. 研究背景与问题 (Problem)

机器遗忘 (Machine Unlearning) 旨在从训练好的模型中移除特定数据的影响，而无需从头重新训练（Retraining from scratch）。这在满足隐私法规（如 GDPR 的“被遗忘权”）和降低计算成本方面至关重要。

核心挑战：

• 现有方法的局限性： 大多数现有的认证遗忘（Certified Unlearning）算法要么基于二阶方法（需要 Hessian 矩阵，计算昂贵），要么基于全批量梯度下降（Full-batch GD），难以应用于现代大规模深度学习模型。
• 随机梯度下降 (SGD) 的理论空白： 虽然 SGD 是训练大模型的标准方法，但现有的 SGD 遗忘算法要么仅适用于凸函数，要么只能提供较弱的“后处理”定义，缺乏对非凸函数（如深度神经网络）的严格 $(\epsilon, \delta)$ 认证遗忘保证。
• 现有基线的矛盾： "Descent-to-Delete" (D2D) 算法在理论上仅针对强凸函数设计，但其随机版本常被用作“微调”遗忘的基线，尽管它在非凸设置下表现不佳。"Rewind-to-Delete" (R2D) 算法针对非凸函数设计，但此前缺乏 SGD 版本的理论证明。

研究目标： 为 SGD 版本的 D2D 和 R2D 算法提供严格的 $(\epsilon, \delta)$ 认证遗忘理论保证，并分析它们在强凸、凸和非凸损失函数下的表现。

---

2. 方法论 (Methodology)

本文提出了两种基于 SGD 的遗忘框架：SGD-R2D（回退）和 SGD-D2D（下降），并引入了新的分析视角。

2.1 核心算法

• SGD-R2D (Rewind-to-Delete):
  • 机制： 在遗忘阶段，算法不从头开始，而是“回退”到训练过程中的某个早期检查点（第 $T-K$ 步），然后仅使用保留数据集（Retained Set）进行 $K$ 步 SGD 更新。
  • 噪声注入： 在遗忘过程结束后，向最终参数添加高斯噪声以满足差分隐私要求。
• SGD-D2D (Descent-to-Delete):
  • 机制： 在遗忘阶段，从最终训练好的模型（第 $T$ 步）开始，仅使用保留数据集进行 $K$ 步 SGD 更新。
  • 噪声注入： 同样在结束时添加高斯噪声。

2.2 理论分析框架

作者通过扰动梯度系统 (Disturbed Gradient Systems) 的视角来分析遗忘过程，将遗忘轨迹视为在保留数据集损失函数上的“有偏”或“受扰动”的 SGD。

• 耦合论证 (Coupling Argument):
  • 为了最小化“遗忘模型”与“从头重训模型”之间的距离，作者设计了一种耦合策略：在训练和重训过程中，尽可能让随机采样的批次（Mini-batches）重合。
  • 通过控制两个随机轨迹（训练轨迹 vs. 重训/遗忘轨迹）之间的耦合，推导出期望意义下的敏感度界限（Sensitivity Bound）。
• 基于矩的界限 (Moment Bounds):
  • 利用马尔可夫不等式，将期望距离界限转化为高概率的尾部界限，从而得到 $(\epsilon, \delta)$ 的不可区分性保证。
  • 强凸函数： 利用强凸函数的收缩性（Contractive），推导出二阶矩界限，获得更紧的隐私保证。
  • 凸/非凸函数： 利用半收缩或扩张性质，推导出一阶矩界限。

2.3 关键假设

• 损失函数满足 Lipschitz 光滑性。
• 对于无界域（SGD-R2D），假设随机梯度的二阶矩相对有界（Assumption 4.7），且初始损失有限。
• 对于 SGD-D2D，假设遗忘数据比例较小，使得有偏项可以被“折叠”进标准 SGD 收敛分析中。

---

3. 主要贡献 (Key Contributions)

1. 理论证明：
   • 首次证明了 SGD-R2D 在强凸、凸和非凸损失函数下（无论是否有投影）均满足 $(\epsilon, \delta)$ 认证遗忘。
   • 证明了 SGD-D2D 在强凸损失函数下满足 $(\epsilon, \delta)$ 认证遗忘，并采用了不同于原始 D2D 证明的新方法，摆脱了强 Lipschitz 连续性的严格限制。
2. 隐私 - 效用 - 复杂度权衡分析：
   • 推导了不同函数类型下的噪声界限 $\Sigma$。
   • 发现对于强凸函数，SGD-D2D 能提供比 R2D 更紧的界限；但对于凸和非凸函数，SGD-R2D 是更合适的选择。
   • 证明了在强凸函数下，随着训练步数 $T$ 增加，所需的遗忘步数 $K$ 会收敛到一个常数，意味着遗忘的计算优势 ($T-K$) 可能是无限的。
3. 实证研究：
   • 在真实数据集（eICU 和 Lacuna-100）上对比了 SGD-R2D 和 SGD-D2D。
   • 揭示了 D2D 在非凸设置下容易陷入驻点（Stalling）或导致过拟合，而 R2D 能更可靠地移除数据影响。

---

4. 实验结果 (Results)

实验在 eICU（医疗表格数据，MLP 模型）和 Lacuna-100（人脸数据，ResNet-18 模型）上进行。

• 遗忘效果 (L2 距离与性能):
  • SGD-R2D: 在 eICU 和 Lacuna-100 上均表现出可靠的效果。随着回退步数 $K$ 增加，遗忘模型参数向重训模型靠近，且在遗忘数据集上的性能显著下降（表明数据被移除），同时保持保留集和测试集性能稳定。
  • SGD-D2D: 在非凸设置下表现不佳。在 eICU 上，它导致模型性能在所有数据集上提升（意味着未真正遗忘，而是找到了新的下降方向）；在 Lacuna-100 上，参数空间几乎无移动，表明模型在初始化点陷入了驻点。
• 成员推理攻击 (MIA):
  • R2D 能更有效地降低 MIA 的成功率（AUC 接近 0.5），表明其更好地保护了隐私。
  • D2D 由于可能陷入驻点或过拟合，对 MIA 的防御效果不如 R2D 稳定。
• 计算效率:
  • R2D 总是比从头重训更高效。对于强凸函数，随着训练时间增长，R2D 的遗忘步数趋于常数，具有巨大的计算优势。

---

5. 意义与结论 (Significance & Conclusion)

• 理论突破： 填补了 SGD 在非凸函数下认证遗忘的理论空白，证明了“回退”策略（R2D）在随机设置下对于非凸深度学习模型是理论上可行且必要的。
• 实践指导： 明确了 D2D 和 R2D 的适用场景：
  • 强凸问题： D2D 可能提供更紧的隐私界限。
  • 凸/非凸问题（如深度神经网络）： R2D 是更优选择，因为它能避免陷入局部极小值，并能更有效地移除数据影响。
• 黑盒特性： 这两种算法都是“黑盒”的，只需在训练和遗忘结束时注入噪声，无需修改训练过程，易于集成到现有的深度学习流水线中。
• 未来方向： 论文指出了无放回采样（Sampling without replacement）的理论扩展以及结合其他遗忘框架（如 PABI）的潜力。

总结： 该论文通过严谨的数学分析和实证实验，确立了 SGD-R2D 作为处理非凸深度学习模型机器遗忘问题的首选方法，解决了现有基线方法在理论保证和实际效果上的不足。