Remember What You Want to Forget: Algorithms for Machine Unlearning
Remember What You Want to Forget: Algorithms for Machine Unlearning
复制标题
DOI：
--
复制
发表时间：
2021-03
期刊：
影响因子：
--
通讯作者：
Ayush Sekhari;Jayadev Acharya;Gautam Kamath;A. Suresh
中科院分区：
文献类型：
--
作者：
Ayush Sekhari;Jayadev Acharya;Gautam Kamath;A. Suresh
我们研究了从学习模型中去除数据点的问题。学习器首先接收一个用i.i.d.绘制的数据集S。从未知的分布，并输出一个模型$\widehat{w}$，该模型在来自相同分布的未知样本上表现良好。然而，在未来的某个时候，S$中的任何训练数据点$z \都可以请求取消学习，从而促使学习器修改其输出模型，同时仍然确保相同的精度保证。我们开始了对机器非学习泛化的严格研究，目标是在以前看不见的数据点上表现良好。我们的重点是计算和存储的复杂性。对于凸损失的设置，我们提供了一个unlearning算法，可以unlearn到$O（n/d^{1/4}）$样本，其中$d$是问题的维度。相比之下，一般来说，差分私有学习（这意味着不学习）只保证删除$O（n/d^{1/2}）$样本。这证明了差分隐私和机器学习之间的新分离。
We study the problem of unlearning datapoints from a learnt model. The learner first receives a dataset $S$ drawn i.i.d. from an unknown distribution, and outputs a model $\widehat{w}$ that performs well on unseen samples from the same distribution. However, at some point in the future, any training datapoint $z \in S$ can request to be unlearned, thus prompting the learner to modify its output model while still ensuring the same accuracy guarantees. We initiate a rigorous study of generalization in machine unlearning, where the goal is to perform well on previously unseen datapoints. Our focus is on both computational and storage complexity. For the setting of convex losses, we provide an unlearning algorithm that can unlearn up to $O(n/d^{1/4})$ samples, where $d$ is the problem dimension. In comparison, in general, differentially private learning (which implies unlearning) only guarantees deletion of $O(n/d^{1/2})$ samples. This demonstrates a novel separation between differential privacy and machine unlearning.