Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: Machine unlearning is new and hot topic. This paper makes several interesting contributions. The idea that the unlearning operation can only access a summary of the entire dataset is a great conceptual innovation since many deployment environments are memory-constrained compared to the training environment. The main contributions of this paper lean theoretical. I did not closely check all the details in the math, but it seems correct at a high-level. I consider the theoretical contributions interesting and strong.
main_review: Contributions:
 - Study trade-off between generalization loss and unlearning with memory constraints
 - Propose an unlearning technique and show it results in asymptotic improvements over DP-based unlearning methods

Overall, I am enthusiastic about this paper. I am tentatively voting a 7.

Suggestions/Concerns:

- One of the key, interesting findings of this paper is the strict separation between DP and removal in the setting of choice. I suggest the authors add more intuition and description so that the readers can easily digest this finding. 

- The deletion notion in Ginart 2019 does not require randomness, contrary to the claims in this paper. In that work, the learning algorithm could just deterministically output the database in the clear and the unlearning operation need just remove the target row from the database. Even simpler, all learning algorithms could just deterministically output "0" and the unlearning operation doesn't need to do anything. The only differences I can see with respect to the definition in Ginart 2019 are that: (1) this definition explicitly supports batch deletions, (2) this definition is two-sided, meaning that unlearned models must be indistinguishable from models trained on the subset  & (3) this definition limits access to the dataset via the summary structure T.

- Consider letting the magic constant (0.01) be an arbitrary gamma. For some applications 0.01 is too small and for others it might be too large. This is a stylistic recommendation and does not need to be addressed in rebuttal.

- While this paper clearly leans towards the theoretical, it would be good to include simple experiments to illustrate the points made in the paper. For example, a simple linear or logistic regression setting should satisfy the theoretical criteria and is not a hard implementation. It is nice to actually compute and tell the reader what the actual improvement in deletion capacity ends up being, especially if non-vacuous metrics can be achieved in practice.

- At the end of Section 4, the subsection titled "Algorithms for convex loss functions" is elementary and should be moved to the appendix. It is standard knowledge that adding regularization to the loss function yields strong convexity and this does not need an entire subsection to explain (it can be stated in 1 or 2 sentences as above, if mentioned at all).

limitations_and_societal_impact: Yes, they address social impact.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper considers the problem of machine unlearning: after a model is trained on a dataset, there is a request to delete a point from the dataset. The goal is to design an *efficient* method to update the trained model such that is nearly indistinguishable from what we would have obtained had we trained on the dataset without the point. The authors use differential privacy as the unlearning criteria and look at unlearning in convex learning problems. The give a method which can *unlearn more points* that DP-training with small runtime and storage complexity.
main_review: The paper contributes novel definitions and terminology to the budding unlearning literature. To give an example: the viewpoint of deletion capacity is interesting.
The paper is well-written, the proofs are natural and well-presented.

**Confusion with the subtlety in the definition of unlearning**: The authors claim that their definition of $(\epsilon, \delta)$ unlearning is more general than previous work because it allows the learning algorithms to be deterministic. But I feel that this is an dubious claim from a practical viewpoint basically because any deterministic output is useless to begin with. The promise of unlearning is that the updated model is indistinguishable from what is obtained from training on the dataset with the deleted points. If the model in use is the deterministic one, then the company/service is not compliant  with the unlearning promise to begin with, and hence the deterministic output serves no purpose. The only situation where the deterministic output is thus useful is, when we know there are no unlearning requests to address  -- no reason to believe why we know this a-priori.

**Separation between DP and unlearning**:
A key contribution in the paper is a separation of DP and unlearning. It should be noted though that unlearning algorithms operate under more information than DP (they have knowledge of the deletion requests), therefore a smaller accuracy is reasonable to expect -- showing this formally is a good contribution. However, upon thinking about it a little more, it semms to me that it is possible to show much stronger results (see later half of "population risk minimization and non i.i.d. points" paragraph).

**Population risk minimization and non i.i.d. points**:
This paper, in contrast to most previous work, considers excess population risk (rather than excess empirical risk) as the measure of performance. The authors motivate this via an example of mean estimation where it is straightforward to unlearn with best empirical risk performance. However, the authors show that there exists a sequence of deletions such that the corresponding population risk deteriorates. Interestingly, the deletion sequence is "adversarial", in the sense that the data points are no longer i.i.d., and thus (at a high-level) the empirical minimizer fails. My first impression upon reading this was that this is a challenging problem, since if we allow such "adversarial" updates, then we need to devise learning algorithms for datasets which are not i.i.d. anymore. But (if my understanding is correct) initial i.i.d. points and stability properties of ERM allows them to tackle it. My understanding is as follows: the initial dataset is i.i.d. and we have a model (empirical minimizer) $w_1$ which has small population risk. After deletions, we have to output $w_2$, the new empirical minimizer. It can be shown that $\Vert w_1-w_2 \Vert \leq \alpha$, so with the DP-like unlearning guarantee, we can add noise $\propto \alpha$, but this leads to worse accuracy. Instead, is there a point $w_3$, which is *closer* to $w_2$ but still has good population risk performance (guaranteed if it is close to $w_1$) -- the proposed unlearning algorithm gives such a point *efficiently*. 
The two factors described above gives the two terms in the accuracy guarantee.
Now, ignoring the computational cost of unlearning, I think that there are *even better* models, ones which optimize the aforementioned trade-off optimally. Consider a model $w_4$: let $a:=\Vert w_1 - w_4\Vert $ and $b:=\Vert w_2 - w_4\Vert $.  Let $c:=\Vert w_1 - w_2\Vert \leq \frac{m}{\lambda n}$. If $w_1, w_2$ and $w_4$ are co-linear, then $a+b=c$. Adding noise of variance (roughly) $b^2/\epsilon$ suffices for the unlearning guarantee. Plugging this in the proof of Lemma $9$, this gives an excess risk of $a + \sqrt{d}b/\epsilon + \frac{1}{\lambda n}$, the trade-off between the first two is optimized when $a = \frac{\sqrt{d}}{\epsilon+\sqrt{d}}c \leq c$. This gives an excess risk of $\frac{m}{\lambda n}$.
Note that this is as good (in terms of upper bounds) as using $w_2$ with no noise.
It is unclear if we can find this $w_4$ efficiently, but the above argument (if correct) is sufficient to establish a much stronger separation between unlearning and DP. Please correct if I made any mistake in the above reasoning.

**Population risk vs ERM**: While the authors make a big deal about the fact that unlike prior work, they consider the population risk problem, in their problem (strongly convex learning), simply outputting (approximate) ERM gives smaller or (at worst) equal excess population risk than than authors'. Importantly, this is the method and proof technique used by the authors.

**Some confusion on storage**:
A key criteria in the paper is to also minimize storage complexity.
The authors want that storage complexity be independent of $n$, and moreover, the dataset is not stored/accessible. My confusion is, when getting a point $z$ to deleted, do we get (a). an id of the point or (b). full description of the point. If it is (a), then we indeed need to store the whole dataset, since we don't know the incoming requests. If it is (b), then the storage is indeed independent of $n$, but then what are we even "remembering" (which motivates the paper title). In general, the phrase "remember what you want to forget" is confusing to me -- why is it fine to assume we know what we want to forget a-priori?

**Unlearning runtime**:
The authors say that their unlearning runtime is $O(d^\omega)$, however, they should also consider the time it takes to compute the hessian and gradient on the deleted data points -- the sum of Hessians overl all data-points can be be pre-computed, but not the individual terms: this gives additional runtime of $\Omega(md^2)$.

**Comparison with retraining**:
A natural baseline in unlearning papers is comparison with retraining.
With the constraints put on storage, the authors specifically removed retraining as a valid method.
However, I find this limiting since in such a new and unexplored problem as unlearning, having multiple criteria of performance (unlearning runtime, storage..)  inhibits a deep understanding of any of the aspects. Furthermore, if we remove the only known (and trivial) method, then how to do we if the guarantees are indeed *interesting* (perhaps the trivial method retraining takes space but has much *smaller* runtime?). 
Thus, due to personal curiosity, I tried to (roughly) calculate how it performs against retraining.
Due to the population risk minimization criteria and non-i.i.d. points, I first thought that this does not apply.
However, due to the stability properties of ERM (the approach via which this paper gave risk bounds), the ERM output after $m$ deletions can be shown to have excess risk $\frac{m}{\lambda n}$ -- the authors' upper bound is, at best, this term. Similarly, an $\alpha$ approximate ERM can be shown to have excess population risk of $\sqrt{\frac{\alpha}{\lambda}} + \frac{m}{\lambda n}$.
The authors achieve excess population risk of $\frac{\sqrt{d}m^2}{\lambda^3 n^2 \epsilon}$ (disregarding other terms) with run-time $md^2 + d^\omega$. To achieve the same error on $n-m = \Omega(n)$ points, the total gradient complexity (using SGD) is $\frac{\lambda^4 n^4 \epsilon^2}{d m^4}$. Hence, the prposed method is more efficient than retraining if (roughly) $\max(md^2, d^{\omega}) < \frac{\lambda^4 n^4 \epsilon^2}{d m^4} \iff \epsilon > \frac{m^2}{\lambda^2n^2}  \max \left( \sqrt{m}d^{3/2}, d^{(1+\omega)/2}\right)$. For reasonable unlearning guarantee, we want $\epsilon$ to be a small constant, say $1$. This would give (reasonable?) upper bounds on $m$ and/or $d$ in terms of number of data points $n$ and $\lambda$. 
Again, I think such an exercise as above is required to assess if the guarantees are indeed non-trivial.

**Incorrect description of previous work:** The authors mention "Ullah et al. 2021, Machine Unlearning via Algorithmic Stability" in context of methods which use an approximate unlearning criteria (i.e. differential privacy). However, this is incorrect: Ullah et al. 2021 give methods which guarantee **exact** unlearning.

limitations_and_societal_impact: No direct societal impact.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper proposes a new unlearning algorithm that is provably memory and sample efficient in some cases. The paper provides sample complexity upper and lower bounds for test error given access to second order information of loss function.

main_review: Strength: - Nicely written, with detailed related work section. Theorems and definitions are well motivated and each of them is intuitively explained for readers not so familiar with the problem of machine unlearning and the general area. The paper adopts standard Mathematical notations which is nice, and they are consistently followed throughout the paper as well. 
- Application of ideas from DP for unlearning is intuitive and interesting. The main idea is that if the future delete requests are manageable, then a deterministic procedure like the one proposed maybe sufficient under some technical conditions on the loss function of the learning algorithm. The separation result in terms of sample complexity between DP and unlearning is technically interesting.

Weakness:- For a paper that presents a machine (un)learning _algorithm_ as its main contribution, it does not contain any experiments, not even simulation. It seems like the algorithm could be implemented for reasonable size datasets since it only requires hessian-vector product -- this package comes to mind https://github.com/amirgholami/pyhessian 
- Again, for a theory paper like this, I consider it a lost opportunity to give no intuition at all about the proofs. I believe readers would be able to appreciate the paper even more if some proof sketches are provided. The examples are nice but they are almost trivial, and they don't necessarily convey the challenge . The proofs contain some minor typos and quantities (D^*) undefined. The proofs appear to be technically correct and utilize tools from convex optimization and results from differential privacy literature. 

Justification: The paper seems to have some interesting ideas that are not fully formed i.e., pieces of the paper sometimes felt disjoint without one full coherent story. For example, the introduction section is only slightly related to the rest of the paper -- discussion about regulations is totally forgotten. A similar statement could be made for the related work section, wherein it seems none of the ideas are used in this paper. Incorporating some elements of the proofs in the main paper might make it more readable from the technical perspective.

limitations_and_societal_impact: Have addressed appropriately.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper studies the problem of unlearning: given a model M trained on a set of examples S, and a subset T of S, the goal is to generate a model M’ that does not rely on any of the samples in T. The authors in particular aim to minimize the test error (rather than the training errors is done in previous approaches), while keeping speed and space constraints low. Their main contributions are a comparison with differential privacy (DP) algorithms, and showing theoretically that unlearning and DP are two separate problems, as well as presenting an unlearning algorithm which can unlearn asymptotically more examples the DP.
I will say upfront that I am not an expert on this topic, but to the best of my judgement the paper seems interesting and solid.

main_review: The paper provides a thorough background and is generally clear. The contributions seem novel, though I am not intimately familiar with the topic.

Questions:
1. The authors attribute some of the limitations of previous approaches to their usage of randomness (#176), and later say explicitly that “(their) definition does not require the learning algorithm to be randomized”. However, as stated in #301 and Algorithm 1, their model in fact does add noise to w. 
2. The authors discuss one of the benefits of their approach in not needing to save the entire training set. However, a reasonable assumption is that you don’t know in advance which samples are going to be deleted, so it seems like one would need to save the entire training set anyhow, plus a mapping from each author to their samples, which makes this constraint not a particularly useful one.

Minor: 
#189: grown -> grow

limitations_and_societal_impact: The paper tries to make models adhere to privacy requirements such as deletion of personal data, which makes it seem like it could have a positive societal impact.
review_title: null

Meta-review: The paper considers the problem of machine unlearning: after a model is trained on a dataset, there is a request to delete a point from the dataset. The goal is to design an efficient method to update the trained model s.t. is nearly indistinguishable from what we would have obtained had we trained on the dataset without the point. One baseline from prior work is to use DP. The authors give a method that can efficiently unlearn more points that DP-training in the context of in convex learning problems. The reviewers agree that this is an interesting paper with solid contribution, and all of them support acceptance.
Decision: Accept (Poster)