arXiv：cs.LG· Youssef Allouah, Joshua Kazdan, Rachid Guerraoui, Sanmi Koyejo·· 4 小时前AI 评分41
分布内与分布外机器遗忘的效用与复杂度分析
The Utility and Complexity of in- and out-of-Distribution Machine Unlearning
AI 导读
该论文分析了近似机器遗忘在效用、时间和空间复杂度上的根本权衡，并给出类似差分隐私的严格认证。对于分布内遗忘数据，带输出扰动的经验风险最小化即可实现紧致的遗忘-效用-复杂度权衡；但面对分布外遗忘数据，即使只删一个样本，遗忘时间也可能超过重新训练，作者为此提出一种带噪声的鲁棒梯度下降变体来摊销遗忘时间。
正文
Abstract:Machine unlearning, the process of selectively removing data from trained models, is increasingly crucial for addressing privacy concerns and knowledge gaps post-deployment. Despite this importance, existing approaches are often heuristic and lack formal guarantees. In this paper, we analyze the fundamental utility, time, and space complexity trade-offs of approximate unlearning, providing rigorous certification analogous to differential privacy. For in-distribution forget data -- data similar to the retain set -- we show that a surprisingly simple and general procedure, empirical risk minimization with output perturbation, achieves tight unlearning-utility-complexity trade-offs, addressing a previous theoretical gap on the separation from unlearning "for free" via differential privacy, which inherently facilitates the removal of such data. However, such techniques fail with out-of-distribution forget data -- data significantly different from the retain set -- where unlearning time complexity can exceed that of retraining, even for a single sample. To address this, we propose a new robust and noisy gradient descent variant that provably amortizes unlearning time complexity without compromising utility.
| Subjects: | Machine Learning (cs.LG); Cryptography and Security (cs.CR); Optimization and Control (math.OC) |
| Cite as: | arXiv:2412.09119 [cs.LG] |
| (or arXiv:2412.09119v4 [cs.LG] for this version) | |
| https://doi.org/10.48550/arXiv.2412.09119 arXiv-issued DOI via DataCite |
Submission history
From: Youssef Allouah [view email]
[v1]
Thu, 12 Dec 2024 09:54:38 UTC (548 KB)
[v2]
Wed, 12 Feb 2025 09:38:31 UTC (913 KB)
[v3]
Fri, 5 Jun 2026 00:11:44 UTC (550 KB)
[v4]
Tue, 6 Oct 2026 21:47:16 UTC (550 KB)
来源：arXiv：cs.LG · arxiv.org