分布内与分布外机器遗忘的效用与复杂度分析

研究分析了近似机器遗忘在效用、时间与空间复杂度上的权衡，并给出类似差分隐私的严格认证。对于分布内遗忘数据，带输出扰动的经验风险最小化即可实现紧致的遗忘-效用-复杂度权衡；而分布外遗忘数据即使只删一个样本，遗忘时间也可能超过重新训练，为此作者提出一种带噪梯度下降变体，在不损失效用的情况下摊薄遗忘时间。