Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper considers the problem of adaptive data deletion in model unlearning. Using the tools of differential privacy and its connection to max information, a general reduction from deletion guarantees against adaptive sequences to deletion guarantees against non-adaptive sequences is provided in Theorem 3.1. Combined with the ideas from prior work which give guarantees for non-adaptive deletion sequences, Theorem 3.1 leads to flexible algorithms, and gives strong provable deletion guarantees for adaptive deletion sequences. It is further shown in theory how prior work for non-convex models fails against adaptive deletion sequences, and a practical attack against the SISA algorithm of Bourtoule et al is prosed and tested on CIFAR-10, MNIST, Fashion-MNIST.
main_review: 
This paper tries to resolve the adaptive unlearning problem defined in Definition 2.2. Based on my knowledge, the setting of such a problem is novel, but it is not clear to me how practical the main result (Theorem 3.1) is when we try to construct an adaptive unlearning algorithm with theoretical guarantee. 

Theorem 3.1 states that if we have a “good” unlearning algorithm in the oblivious setting, and the publishing function is differential private with respect to the internal randomness r, then the same unlearning algorithm is also “good” in the adaptive setting. To my understanding, such a result only provides the sufficient conditions for the same algorithm to work in the adaptive setting. I feel like the differential private assumption might be: 1) too strong, so that the same algorithm works for both oblivious and adaptive setting; 2) impractical, since in general we want the publishing function to be DP with respect to the training dataset. I was expecting a stronger result which tells us how to modify the existing algorithm with weaker assumptions. The authors should provide more discussions on why we should be satisfied with the current Theorem 3.1, and how we can use it to resolve the problem.

The organization of the paper can be improved. I did not fully understand the adaptive setting studied in the paper until I read section 5.1. I feel like this section should appear earlier in the paper, since it serves as a motivation of the adaptive unlearning problem. Moreover, I feel like the result in section 5.2 is not directly related to the analysis in the paper, it only shows the significance of the problem, but does not demonstrate how resolve the problem. Maybe some applications of the results in section 3 or 4 beyond the SISA framework are more informative and useful. 

Minor comments:
1.	In line 112, The notation $\mathcal{Z}^*$ and $\Theta^*$ is used without definition.
2.	In line 181, notation $m$ is used before definition, why m is important here?


After rebuttal:
The response resolves some of my questions, and I would like to raise my score to 6, as the problem studied in the paper is quite novel and could lead to more discussion in the future.
limitations_and_societal_impact: I think the authors addressed the limitations and potential negative societal impact of their work.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper considers the problem of machine unlearning. A general setting is explored, where initially a model is learned on some dataset, and some function of the model is published. Then in following rounds, either a data deletion or a data addition request is received, and its required to update the model in a way that the data request is respected. The authors formalize this in their proposed definition of (alpha, beta, gamma)-unlearning. 

Contributions.
1. A formalization of machine unlearning. The paper proposes Definition 2.3 to formally define what it means to do machine unlearning. The definition is fairly general, and bears some similarity to the definition of differential privacy. Though, here, there are two algorithms involved, a learning algorithm, and an unlearning or update algorithm.

2. (Theorem 3.1) Showing that machine unlearning with adaptive data deletion requests (when the requests depend on what was previously published) can be reduced to machine unlearning with oblivious data deletion requests, provided that the publishing functions are differentially private with respect to the random bits used by the learning algorithm. 

3. (Theorem 4.1) The authors show how their generic reduction can be applied to obtain machine unlearning guarantees in a distributed learning setting. They compare this with a previously published mechanism (Bourtoule et al. 2021). Though, it's important to note that Algorithm 3 does retrain models from scratch. 

4. (Theorem 4.3) The authors instantiate the result in Theorem 4.1 when the publishing functions are private aggregations of predictions. 

5. Experiments suggesting that differential privacy can help provide data deletion guarantees on adaptively chosen sequences.

main_review:  Establishing a connection between differential privacy and machine unlearning is novel in this work to the best of my knowledge. To obtain machine unlearning guarantees against adaptive deletion requests, the authors rely on differential privacy guarantees. While this shows sufficiency of differential privacy, is differentially privacy necessary to obtain such guarantees? This could further motivate the importance of machine unlearning if, for example, it turns out to be an “easier” problem than differential privacy.

In other words, is Definition 2.3 of (alpha, beta,gamma)-unlearning equivalent in some way to differential privacy? It would be good if the authors could further motivate why this is an appropriate notion of machine unlearning?

In the framework suggested, if what is being published is differentially private, then why are we looking for data deletion guarantees?

The paper is clear and easy to follow.

limitations_and_societal_impact: In my opinion, the authors have adequately addressed the limitations of their work and negative societal impacts of their work.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper has showed an interesting solution to the data deletion problem. The method is novel. The authors have identified an important blindspot in the data deletion literature.  However, the experimental validation is weak. 
main_review: In this paper, the authors addressed the data deletion problem, which has become important in business scenarios. Existing methods rely on the implicit assumption that the deleted data points are independent of the randomness used to train the models. However, this assumption is too strong and is not practical in some scenarios. Indeed, the authors  proposed a more generalized scenario, which shows the blindspot in data deletion. Also, they provided a general method to reduce adaptive deletion guarantees. Comparing with the existing methods, the proposed model allows for the deletion of arbitrary sequences of adaptively chosen points while providing rigorous guarantees. While the paper has innovative ideas, it also has some limitations. First, the model is not clearly described. Second, the experimental results are not fully convincing. In the experiments, the authors showed that the deletion guarantees of algorithms in the SISA framework fail for adaptive deletion sequences, however  the effectiveness of the proposed model cannot be fully explained. Finally, the baselines are weak. The authors should compare their methods with the prior studies which do have deletion guarantees.
limitations_and_societal_impact: 1.	The model description is not clear.
2.	The experimental results are not convincing.
3.	This paper focuses on the data deletion algorithms and it gives 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.
review_title: null

Meta-review: The paper revisits the problem of machine unlearning in a setting wherein the (training) data deletion requests can depend on the trained model. Authors give guarantees for this adaptive data deletion problem using a general reduction from the non-adaptive settings studied in prior work. A good paper, overall. 
Decision: Accept (Poster)