🤖 machine learning

Near-Optimal Pure Machine Unlearning for Smooth Strongly Convex Losses

本文为平滑强凸损失函数的机器学习遗忘统计代价建立了近乎最优的上界和下界，证明了最优误差率取决于遗忘参数 $\varepsilon$ 与模型维度 $d$ 之间的关系，并在从头开始重新训练与指数级更小的项之间进行插值。

原作者： Matthew Regehr, Gautam Kamath, Andrew Lowy

发布于 2026-06-02

📖 1 分钟阅读☕ 轻松阅读

原作者： Matthew Regehr, Gautam Kamath, Andrew Lowy

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

想象一下，你有一位超级聪明的巨型大厨，他用来自巨大市场的数千种食材烹饪了一锅巨大的炖菜。这锅炖菜代表了一个在海量数据集上训练的机器学习模型。

现在，想象一位顾客走进来说道：“我想把我贡献的那50根胡萝卜拿回去。请为我制作一个新版本的炖菜，让它的味道尝起来就像我从未给过你那些胡萝卜时一样。”这就是**机器学习遗忘（Machine Unlearning）**的概念。

这篇论文探讨了一个非常具体的问题：当我们试图移除那些胡萝卜时，炖菜的味道会遭受多大的损失？相比于直接把整锅扔掉重新从头开始煮，情况又是如何呢？

以下是他们使用简单类比得出的研究结果：

两种显而易见（但有缺陷）的做法

“忘记一切”法（差分隐私/Differential Privacy）：
想象大厨在任何人知道要移除哪些胡萝卜之前，决定在食谱中加入一点点“噪声”或“迷雾”。这样一来，没有人能分辨出是否使用了特定的胡萝卜。
- 问题在于： 这种做法过于谨慎了。大厨加入了太多的迷雾，导致即使只需要移除一根胡萝卜，炖菜的味道也会变得比实际需要的更差。
“从头开始”法（从零开始重新训练/Retraining from Scratch）：
大厨扔掉整锅炖菜，取出那50根胡萝卜，然后用剩余的食材从头开始重新烹饪整锅炖菜。
- 问题在于： 这种做法在移除胡萝卜方面是完美的（新炖菜的味道正是它应该有的样子），但它极其浪费且缓慢。你损失了原本那锅炖菜所做的一切工作。

论文的大发现：一次“魔法交换”

作者 Matthew Regehr、Gautam Kamath 和 Andrew Lowy 发现了一个处于这两者之间的“金发姑娘原则”（即中庸之道）解决方案。他们开发了一种新的算法，其作用就像是一次**“魔法交换”**。

以下是他们的“核心交换”（Core-swap）算法用通俗易懂的语言是如何运作的：

准备阶段： 大厨准备好了一个“备选方案”。当炖菜完成时，大厨不仅准备了主锅，还准备了一个“安全网”版本——这个版本看起来像是没有那特定胡萝卜的炖菜，但大厨将其隐藏在一个稍大的、模糊的可能性云团之中。
请求阶段： 当顾客说“移除我的胡萝卜”时，大厨并不会扔掉所有东西。相反，他进行了一个巧妙的技巧：
- 他拿取包含胡萝卜的美味主炖菜。
- 他将“模糊云团”部分的配方进行交换，使其与不含胡萝卜的版本相匹配。
- 至关重要的是，他进行这一切的方式，使得从统计学上讲，外人无法分辨大厨是真的移除了胡萝卜，还是仅仅交换了配方。

“隐私预算”（ $\epsilon$ 因子）

论文引入了一个变量 $\epsilon$ （epsilon）。你可以把它理解为你的**“隐私预算”或“置信水平”**。

低预算（ $\epsilon$ 很小）： 如果你要求必须绝对确保胡萝卜已经消失（极高的隐私要求），那么“魔法交换”就帮不上什么忙。在这种情况下，你能做的最好的办法就是从头开始重新训练。论文证明，如果你的隐私需求如此之高，你就无法通过作弊来规避系统；你必须支付重新开始的全部代价。
高预算（ $\epsilon$ 很大）： 如果你愿意接受一种几乎察觉不到的、胡萝卜可能在“技术层面”仍然存在的微小可能性（但在统计上被隐藏了），那么“魔法交换”就会大放异彩。
- 结果： 论文表明，当你拥有较高的隐私预算时，他们的算法比从头开始重新训练要呈指数级地更好。这就像是得到了一锅口感新鲜的炖菜，却节省了 99% 的精力。与“从头开始”的方法相比，误差（味道的差异）降到了极低，几乎可以忽略不计。

“维度”因子

论文还提到了 $d$ （维度）。在我们的类比中，想象这锅炖菜有很多种不同的风味特征（咸、甜、酸、辣等）。

如果风味数量（ $d$ ）相对于你的隐私预算（ $\epsilon$ ）较小，那么“魔法交换”会发挥奇效。
如果风味数量相对于你的预算非常庞大，那么“魔法交换”会显得力不从心，此时你最好还是直接从头开始。

核心结论

作者们证明了他们已经找到了遗忘数据的理论极限。

如果你想要完美的隐私： 你必须从头开始重新训练。没有捷径。
如果你有一个灵活的隐私预算： 你可以使用他们全新的“核心交换”（Core-swap）方法，获得一个比重新训练在准确度上呈指数级更高的结果，同时仍满足法律规定的“遗忘”数据要求。

他们不仅仅发明了一个新技巧；他们还从数学上证明了，除了他们的这种方法之外，你无法做得更好（在与问题“曲率”相关的微小因子范围内）。他们破解了这个谜题：即为了移除数据的一部分，你究竟需要支付多少“统计学上的痛苦”。

技术摘要：平滑强凸损失下的近优纯粹机器遗忘（Machine Unlearning）

问题陈述

本文研究了在**平滑强凸随机凸优化（SCO）**框架下，机器遗忘的基本统计代价。目标是设计一种算法，给定数据集 $Z$ 和删除子集 $U$ 的请求（其中 $|U| \le m$ ），输出一个更新后的模型，该模型在统计上与在保留数据 $Z \setminus U$ 上从头开始训练的模型不可区分。

解的质量由**超额总体风险（excess population risk）**衡量，定义为 $\Delta_{F_P}(w) = F_P(w) - F^*_P$ ，其中 $F_P$ 是总体损失。核心问题在于：在平滑强凸 SCO 中，针对最多 $m$ 个样本的 $\epsilon$ -遗忘，其极小极大最优（minimax optimal）的超额总体风险是多少？

本文考虑的是近似 $\epsilon$ -遗忘，即遗忘算法在 $(Z, U)$ 上的输出分布必须与在保留数据集 $Z \setminus U$ 上运行学习算法（且无删除请求）时的输出分布在最大散度（max-divergence）意义下 $\epsilon$ -不可区分。

方法论

1. 上界：核心交换（Core-Swap） $\epsilon$ -遗忘算法

作者提出了一种新颖的算法（算法 1），它在两种极端策略之间进行插值：

从头重训（RFS）： 返回在 $Z \setminus U$ 上的经验风险最小化（ERM）解。这满足精确的 0-遗忘，但由于丢弃了数据，会产生较高的统计误差。
忽略请求： 返回在全量数据集 $Z$ 上的 ERM。这很准确，但无法满足遗忘保证。

机制：
该算法利用了解空间的几何特性。它构建了一个用于输出的混合分布：

高概率部分： 从以全量数据 ERM 解 $\hat{w}_Z$ 为中心的微小球体内均匀采样。这确保了高准确性。
低概率部分： 从以减量数据 ERM 解 $\hat{w}_{Z \setminus U}$ 为中心的较大球体内均匀采样。该球体的大小足以覆盖在有效删除后，可能产生的任何全量数据 ERM 解。

通过仔细校准这些球体的半径和混合概率 $\eta$ ，算法可以确保“空运行”（无删除）与“真实运行”（执行删除）之间的似然比保持在 $e^\epsilon$ 以内。该算法需要两次调用 ERM Oracle 和一次凸投影，运行时间为 $O(d)$ 。

2. 下界：打包论证（Packing Argument）

为了建立最优性，作者使用了一种不同于标准差分隐私（DP）论证的打包技术来推导下界。

构造： 他们构造了一组“困难”的均值估计实例，这些均值指向单位球内许多分离的方向。
删除策略： 对于每个实例，定义了一个特定的删除请求，该请求会以高概率移除“信号”样本（非零项）。
坍缩： 删除后，所有这些不同实例的保留数据集都坍缩为一个共同的参考数据集（全零）。
不可区分性： $\epsilon$ -遗忘约束强制要求所有这些不同的初始实例的输出分布，都必须接近由该共同参考数据集产生的分布。
打包限制： 打包的大小（分离方向的数量）限制了算法恢复真实均值的准确度，从而导致了误差的下界。

核心贡献与结果

1. 极小极大最优速率

本文为平滑强凸 SCO 建立了近乎紧致（tight）的上下界。最优速率表征为：
$\text{Risk} \approx \frac{1}{n} + \left(\frac{m}{n}\right)^2 e^{-2\epsilon/(d+2)}$
其中：

$\frac{1}{n}$ 是标准的统计误差项。
$\left(\frac{m}{n}\right)^2$ 是从头重训的惩罚项。
$e^{-2\epsilon/(d+2)}$ 是通过所提遗忘算法可实现的指数级改进因子。

这些界限在条件数因子 $\kappa = \beta/\mu$ （其中 $\beta$ 为平滑度， $\mu$ 为强凸度）的意义下是紧致的。

2. 均值估计的精确特征化

对于单位球 $\mathbb{R}^d$ 上的均值估计这一特定情况，作者提供了在常数因子意义下匹配的上下界。这为这一典型设置下的遗忘统计代价提供了本质上精确的特征化。

3. 基线分析与前人工作

从头重训（RFS）： 本文提供了精确分析，表明 RFS 实现的超额风险为 $O(1/n + (m/n)^2)$ 。证明了当 $\epsilon \lesssim d$ 时，它是最优的。
差分隐私（DP）： 文中指出，标准 DP 基线（组 DP）产生的风险为 $O(1/n + d^2 m^2 / (\epsilon^2 n^2))$ ，在 $\epsilon \gg d$ 时，相比于本文提出的方法是次优的。
前序算法： 作者细化了 [SAKS21] 中牛顿步算法的分析，在遗忘误差项上实现了二次改进，并指出了 [AKGK25] 中效用分析的一个错误，并提供了修正后的保证。

4. 机制分析（Regime Analysis）

结果划分为两个截然不同的机制，基于隐私预算 $\epsilon$ 与维度 $d$ 的比例：

低预算机制 ( $\epsilon \lesssim d$ )： 从头重训在统计上是最优的。遗忘惩罚无法通过改进 $(m/n)^2$ 项来进一步降低。
高预算机制 ( $\epsilon \gg d$ )： 所提算法在准确度上相对于从头重训和基于 DP 的基线实现了指数级改进。遗忘惩罚通过 $\exp(-2\epsilon/(d+2))$ 因子得以降低。

重要性与主张

本文声称几乎解决了关于平滑强凸 SCO 中 $\epsilon$ -遗忘的极小极大最优超额风险这一开放性问题。

基本极限： 它确立了遗忘的统计代价并非固定惩罚，而是取决于遗忘预算与模型维度的指数关系。
效率： 所提算法证明，只要隐私预算相对于维度足够大，就可以在满足严格遗忘约束的同时，实现极高的准确度（接近全量数据 ERM）。
效用与隐私的权衡： 该工作澄清了“被遗忘权”与模型效用之间的权衡，表明对于高维模型，只要有足够的隐私预算，遗忘并不一定需要以丢弃大量统计信息为代价（如从头重训那样）。

作者指出，其针对一般 SCO 的界限与条件数因子存在差异，这为超越均值估计实现完全精确的特征化留下了空间。他们还指出，将这些结果扩展到非凸优化以及处理显式的存储/计算约束是未来的研究方向。