Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper investigates whether the existing definitions for machine unlearning are ‘complete’. Prior works on machine unlearning defined ‘certified unlearning’ (at a high level) as indistinguishability from retrained models. This paper argues that this is incomplete, and demonstrate two vulnerabilities (Theorems 3 and 4) such  that a majority of existing unlearning guarantees suffer from one of them. Then, the paper proposes a stronger definition of unlearning, and uses it to propose objectives for data deletion. Finally, the paper analyzes convex and non-convex loss functions to that DP-GD (noisy GD) satisfies the proposed objectives. 
strength_and_weaknesses: **Strengths:**
1. The problem of machine unlearning (data deletion) is practically relevant and technically challenging. It is important to analyze current methods and develop new definitions of data deletion in ML.

**Weaknesses:**
1. The paper does not provide sufficient details on how the compute savings are calculated. Data deletion method proposed in Def. 5.1 is essentially retraining the model using noisy-GD (DP-GD). Since it also performs retraining (but with noisy-GD, it is not clear how the compute savings in Table 1 are calculated. It is important to add more details on this.

2. The paper does not discuss how the reduction result in Theorem 5 relates to the reduction result in [Gupta et al. 2021]. It would be helpful to give more details. 

3. The paper does not present any empirical results to support the theory. In contrast, many prior works including [Gupta et al. 2021] present some empirical results to corroborate the theory.

clarity,_quality,_novelty_and_reproducibility: * The presentation is a bit dense, which makes it tedious to follow the paper. It seems like the introduction is written in a somewhat flashy manner. It is not clear how some points in the Introduction are related to technical contents. (See suggestions and questions below.)

* The claims seem to be correct, even though I did not go through the detailed proofs. 

* The contributions are fairly novel, but the presentation can be improved. 

**Suggestions and questions:**

1. The paper says that “We emphasize that we are not advocating for doing data deletion through differentially-private mechanisms that cap the information content of all records equally, deleted or otherwise, which is known to be inefficient (Sekhari et al., 2021). Instead, data-deletion mechanisms should provide two differing information reattainment bounds; one for records currently in the database in the form of a differential privacy guarantee and the other for records previously deleted in the form of a data-deletion guarantee.”

* The method proposed in the paper relies on retraining with DP-GD. So, the above statement is a bit confusing. It would be good to provide more details.

2. It would be important to give more details about how computational savings over retraining are calculated.

3. Notation $\mathcal{O}$ is used several times before it is defined (on page 4). 

4. It is not clear why Theorems 1 and 2 need to be included with details in the main text. That space may be better used to give some high level details about the proofs of Theorems 3 and 4. 

5. Edit request is considered as a replacement operation, and it is argued that adversary can duplicate a target record before its deletion. Considering edit requests in machine unlearning seems a bit stronger adversary model. Also, the service provider can employ simple defenses such as examine the edit request to check for duplication with any existing training sample, and discard any request that attempts to insert a duplicate item. It would be helpful to discuss these points. 

summary_of_the_review: The paper asks important questions about machine unlearning, and shows some interesting results. However, the presentation can be significantly improved, and some details need to be added.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The paper looks at the problem of ensuring the right-to-be-forgotten (RTBF), under multiple adaptive edit requests to the dataset. The paper has three main contributions (a) they show that the machine unlearning definitions used in the prior works are not sufficient to ensure RTBF, especially when the edit requests are adaptive (they show that it is neither sound nor complete), (b) They provide a new definition for data deletion, (c) They provide an analysis of noisy-SGD algorithm under this new definition. This is a completely theoretical paper and there are no experiments. 


strength_and_weaknesses: Strengths: The paper considers the important question of properly defining data deletion and gives algorithms for data deletion, in the adaptive and online unlearning setting. The paper provides a rigorous theoretical exploration of issues of a prior definition, and a fix to it. 

Weaknesses: 
1. I think the paper creates a misleading impression of the prior works, as:  
  - They only consider the setting of iterative unlearning (multiple {adaptive or non-adaptive} unlearning requests) which, in my opinion, does not comprise the fundamental deletion setting. In particular, the two-stage setting that consists of a single learning state, and a single unlearning stage (to unlearn K many points) has been completely ignored in the paper. All their constructions to invalidate the soundness of machine unlearning definition completely breaks down in this setting. 

 
  - They only consider the indistinguishability definition of Neel et. al. 2021, Gupta et. al. 2021, and extrapolate the failure of these definitions under adaptive queries to argue that all prior machine unlearning works are wrong/incomplete. Contrary to how they pose the prior works, there already exist definitions in the literature that are both sound and complete. Consider the definition of Sekhari et. al. 2021 - It is sound as there is no f_publish and only two stages of interaction, and complete since it only compares the output after the unlearning state (on both original and updated datasets) and hence, an unlearning algorithm that outputs a fixed untrained model is a valid unlearning algorithm. 




2. Following up on the above comment, Theorem 3 only holds when there is a separate f_publish, but not all unlearning definitions distinguish f_publish and algorithms output (e.g. Sekhari et. al. 2021, Ginart et. al. 2019). 

3. The authors claim in the abstract, and in various places in the paper, that it is necessary to satisfy DP to ensure true data deletion. I do not see any formal claim anywhere arguing that DP is necessary. From the definitions and results, it seems to be a sufficient condition rather than a necessary one. Please elaborate. 

4. What are the DP guarantees for the noisy SGD algorithm in Algorithm 1. Is it the exact same noise as DP-SGD? Are the authors essentially running a pure DP algorithm, and then just arguing in hindsight that it is also unlearning? 

5. In the analysis for noisy SGD, the authors only consider empirical risk guarantees. Do the benefits over retraining (reported in Table 1) also hold when we care about test loss performance? 

6. Do the authors have any proof that their definition of data deletion is sound or complete? 

7. The risk of adaptive unlearning requests was also previously explored by Gupta et. al.

8. Minor issues and typos:
   - Definition 2.5, eqn 8 is not clear. I feel it will help to elaborate a bit more on what it means. 
   - Definition 4.1 has a typo “all edit requests u = … \in U^{i}” instead of U^1. 
   - Independence is defined for two random variables (and not two distributions).  Please fix the paper to not use phrases like “there exists a distribution \pi_i^u that is independent of the record being deleted” (e.g. in defn 4.1). This is not mathematically consistent. 
   - Change the notation R to denote the unlearning algorithm (it is confusing as R should ideally be used to denote the retraining algorithm). 

I would be happy to engage further with the authors on any of the above comments. 
clarity,_quality,_novelty_and_reproducibility: All proofs are included, and except for a few minor typos the paper seems to be well-written. Please refer to other sections for more details about clarity. 
summary_of_the_review: As the paper stands, I recommend rejecting it. I feel that the authors are trying to create a wrong impression of the current machine-unlearning literature, which is my primary reason for rejection.  I also feel that the paper is incomplete (as discussed more in the weaknesses). In particular, it is not clear whether DP is actually necessary for deletion in the adaptive setting (as claimed by the authors), and whether their new definition is sound or complete.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The authors consider the definition of unlearning developed in previous work. The paper claims that these definitions do not satisfy the true meaning of unlearning as data could be added back in at later points in time. To this end, the propose that the new definition should be stateless and algorithms for deletion and training should satisfy DP-like guarantees.
strength_and_weaknesses: Strengths:
- the problem of unlearning is important
- observation that the data maybe added later on is an important one

Weaknesses:
- missing threat model
- the definition requiring an algorithm to be stateless does not seem to be intuitive (see below)
- the adaptive vs non-adaptive aspect is confusing
- summary of where and which previous definitions fail is missing


Observation: this paper provides a theoretical result.
clarity,_quality,_novelty_and_reproducibility: Threat model: The paper is missing a clear threat model: who is the attacker, what can they do, what information they have. As a result it is difficult to evaluate claims that other papers do not satisfy the proper definition of deletion.

State: please consider expanding this discussion. How can a server not having any information about original data "delete" a point that it forgot was there? how would it know that the request is legitimate and retrieve data is needs to delete?

Adaptivity: the results presented in the paper seem to be in a non-adaptive case, however arguments showing that previous work does not satisfy the definition seem to be adaptive. It would be great if the authors could clarify this aspect.

Algorithm: as this work presents a way to unlearn data, an algorithm showing the steps for learning and unlearning would facilitate the presentation.

Please consider summarising the properties that previous works fail to achieve in your definition. Counter-example of executing previous algorithms and showing where they would fail help.

Please consider how re-training from scratch would or would not satisfy your definition. It would be good to be clear from the beginning that not all definitions fail (if it is the case).
summary_of_the_review: The paper makes an observation that some of the existing unlearning definitions may not capture all properties one needs from unlearning. This is an important observation. It suggests a new definition. However, without clear threat model and attack capabilities it is difficult to evaluate whether it is the definition that fails or the assumptions on the attacker that fail. The method and the paper could also be presented in a clearer way (e.g., with counter-examples that follow previous definitions an show how they fail).
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper challenges the unlearning criterion used in prior works, indistinguishibility to retraining, for ensuring the right to be forgotten guideline. They argue that this criterion itself is neither complete nor sound. The authors then propose a new unlearning criterion and design learning and unlearning algorithms for the problem of optimizing smooth convex and non-convex losses.
strength_and_weaknesses: Strengths

1. The problem and the message of the paper is definitely interesting and important especially since the area of machine unlearning is up and coming. It rightly distinguishes between the unlearning criterion used in prior works (indistinguishibility to retraining) and the informal goal of implementing the right to be forgotten guideline.

2. The paper is well-written and presents a systematic investigation of deficiencies in prior abstraction of the problem. Furthermore, it contributes new and compelling language to capture various important entities and their interaction in unlearning properties and to imbibe desirable properties towards a definition. 

Weaknesses and questions:

Admittedly, some of the weaknesses I list below may stem from my potentially incorrect understanding, so I would be grateful if the authors can correct me if I am missing something.

**Proposed definition**: The authors show that the prior definition of unlearning is neither complete nor sound. To remedy this, the authors propose a new definition. However, it seems that the authors do not show that this new definition satisfies (some degree of) soundness and completeness, apart from informal justifications. Is there a rigorous argument here? If yes, please point me to it in case I missed it.

**Problem with internal data strucutres**: One of the key requirements that the authors posit in desirable unlearning algorithms is that they don't maintain any internal data-structure. Their key argument towards this are Thms 3 and 4 wherein they construct problems and a valid learning/unlearning pair with internal state such that after some updates, an adversary can infer a deleted record. However, it seems to me that this is possible even with no internal state. Consider the problem of mean (or sum, for simplicity) estimation and the perfect learning/unlearning pair for it. For all 1-non-adaptive requester, an adversary can completely recover its data record by subtracting the updated estimate from the original estimate, right? 
If the above reasoning is correct, then there is something missing in the deduction of the stateless requirements from Thm3/4.
What am I missing here?

Relatedly, I don't understand what *unsafe* means in the context of internal data-structures? For example, in Table 1, the authors correctly list that the prior work of Ullah et al. maintain internal data-structure, but therin, the unlearning being indistinguishable to retraining criterion is applied not just to the model output but the internal data structure as well. In that case, is this still considered unsafe? If yes, then can the authors provide a rigorous definition of safety here?


**Reduction from adaptive to non-adaptive updates**: The recent work of Gupta et al. 2021 also studied machine unlearning against adaptive updates and similarly proved  reductions (as the authors do) using differential privacy. However, a key difference is that Gupta et al. required DP to hold with with regard to a change of description of internal randomness as opposed to standard data item replacement. I understand that the notion of unlearning is different in both papers, but I wonder if there is something more which allows the authors to use standard DP?
In any case, the authors should provide a discussion on differences with the result in the aforementioned work, which is currently missing.

**New definition but similar algorithmic techniques**:
As an example, authors study the design of learning and unlearning algorithms for smooth convex empirical risk minimization under their proposed unlearning criterion.
 The authors' proposed method is based on Noisy gradient descent from the differential privacy literature. This (or its variants) is the method used in many prior works on unlearning (albeit some are stateful, which the authors discard owing "safety" issues). I wonder therefore if it is possible to a-posteriori reason about their unlearning properties (with possibly worse parameters) in the language proposed by the authors. Or is there something fundamental in the algorithmic differences of the authors proposed method?

**Computational savings in Noisy GD**:
 The authors argue that their unlearning method based on Noisy GD demonstrates non-trivial savings of computation compared to retraining with their learning algorithm (Noisy GD).
However, noisy "full" gradient descent is an inefficient (in the sense of gradient complexity) method for the problem of (privately) optimizing smooth convex losses -- it seems that the gradient complexity is $O(\kappa n)$ whereas there exists private methods based on SVRG with $O(n+\kappa)$ gradient complexity or even better.
Now, if retraining were a viable unlearning method, the this computational savings of retraining over a slow learning method may be problematic. 
In any case, ideally, we would want unlearning methods for fast learning methods for the problem.
So, it would be good if the authors can expand on if there is something important about the structure of Noisy GD updates, or is it possible to obtain the same results via a faster but (a somewhat) black-box DP optimization routine.


**Elaboration of proof techniques**:
The authors mention that "...techniques we develop for analyzing data deletion differ tremendously from those used to argue differential privacy". It would have been useful if the authors could include some more details on this claim (maybe some key lemmas) in the main text itself.

Minor:

In the conclusion, the authors state that "we showed that differential privacy is necessary for data deletion when requests are adaptive". I did not see such a strong claim formally in the paper.

Typo? -- In page 2, the authors say "B) generates models that are indistinguishable from any distribution independent of the deleted records". Based on their definition 4, shouldn't it be "from some distribution independent of the deleted record"? 

clarity,_quality,_novelty_and_reproducibility: I think the paper is well-written and coherent. Overall, I found the flow of ideas natural. There are some places where it gets a little heavy on notation but it is perhaps unavoidable. The problem studied as well the ideas presented are indeed novel, interesting and of high quality. For detailed concerns/questions regarding some of the claims and how they tie together in the overall story, please see the preceding question.
Reproducibility: Does not apply.
summary_of_the_review: Overall, I think that this paper rigorously challenges the existing formulation of a problem which has been used in multiple prior works and thus is important. The paper is well-written and I enjoyed reading the paper. I have some concerns and suggestions about some technical details of their claims (see above), and I hope that the authors response would help towards addressing these.

-----
Update: Score changed from 8 to 6 owing to potentially significant update to the paper post release of first set of reviews.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: This paper saw enormous amounts of reviewer comments and responses from the authors. It appears that the original submitted paper had a number of lacking aspects, including, e.g., a limited perspective on previous works, claiming DP is necessary for data deletion, etc. The authors did a heroic effort in revising the paper, addressing many of these issues, and I believe the paper has improved dramatically since the original submission. However, I, and the reviewers, feel uncomfortable accepting the paper in its current state, without careful scrutiny afforded to the large number of new claims and proofs. While reviewers should be expected to investigate small, few, and well-scoped changes, multiple reviewers requested significant changes, which modifies the content of the paper from the original submission in a stark fashion. This is not a journal submission, so I do not expect reviewers to scrutinize such a changed manuscript for ICLR. The manuscript, however, appears at a glance to be far improved from the original submission and will likely see acceptance at a future conference. 
justification_for_why_not_higher_score: Significant changes from the original submitted version
Decision: Reject