Data deletion algorithms aim to remove the influence of deleted data points from trained models at a cheaper computational cost than fully retraining those models. However, for sequences of deletions, most prior work in the non-convex setting gives valid guarantees only for sequences that are chosen independently of the models that are published. If people choose to delete their data as a function of the published models (because they don't like what the models reveal about them, for example), then the update sequence is adaptive. In this paper, we give a general reduction from deletion guarantees against adaptive sequences to deletion guarantees against non-adaptive sequences, using differential privacy and its connection to max information. Combined with ideas from prior work which give guarantees for non-adaptive deletion sequences, this leads to extremely flexible algorithms able to handle arbitrary model classes and training methodologies, giving strong provable deletion guarantees for adaptive deletion sequences. We show in theory how prior work for non-convex models fails against adaptive deletion sequences, and use this intuition to design a practical attack against the SISA algorithm of Bourtoule et al. [2021] on CIFAR-10, MNIST, Fashion-MNIST.

本文从差分隐私入手，使用最大信息原理和以往相关工作中对于非自适应删除序列的保证，将针对自适应序列的删除保证推导为针对非自适应删除序列的删除保证，从而为数据删除算法提供了极大的灵活性。实验分析指出该算法能够针对各种模型和训练方法给出强有力的删除保证，并应用在CIFAR-10、MNIST、Fashion-MNIST等数据集上的SISA算法攻击中。

自适应机器遗忘