Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The authors consider the problem of unlearning. The aim is to do more efficiently than retraining from scratch. The authors propose to construct a prefix-sum-like tree during learning/training to keep intermediate results. These results can then be queried to construct a model that will look like the one without a certain data point (i.e., the one that was requested to be deleted).
strength_and_weaknesses: Strengths:
- the problem of unlearning is really interesting and important
- the authors aim to propose a method that is more efficient than training from scratch
- the idea of decomposing into prefix-sum-like learning is nice

Weaknesses:
- the definition of exact unlearning used by authors is not common
- the paper is extremely dense in notation and content
- the method seems to work only for unlearning one point though the authors allude it may be extended
- the method is expensive in terms of space as it seems one need store a model for every data point
- no experimental results
clarity,_quality,_novelty_and_reproducibility: Clarity: The paper is difficult to read as it is heavy on content and notation. I was not sure why noise needed to be added. It seems it is not for DP purposes. Is it to make learning fall into distribution that would be close to unlearning? Though I appreciate the tree and the figure, it did not make things much clearer. It would be best to define all parameters and use fonts that fit.

Quality: The authors use unlearning definition which is not quite what one would call exact unlearning: exact unlearning is the model one obtains if the data point is deleted and retraining happens. It seems definition 1 is a probabilistic guarantee. That is learning process is made probabilistic so that unlearning of probabilistic nature would be an appropriate counterpart. Please consider definitions in Thudi et al. USENIX Security 2022.

Novelty: The idea of decomposing some training algorithms into prefix-sum is nice. It would be good to compare with Bourtoule et al as sharding seem to also isolate points and recompute those shards where the deleted point was used. Though authors say this work does not provide theoretical guarantees it seems to not use a data point at all hence, may provide exact unlearning as well.

Reproducibility: N/A as this is a theoretical paper.
summary_of_the_review: I believe the paper is not ready to be published due to its presentation (the method description) and how it positions itself (i.e., is this exact unlearning, how it compares to retraining from scratch, how it compares to sharding approach by Bourtoule et al. It may be that in considers inly certain training tasks but it would be best to be clear about it.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The authors propose a general framework for machine unlearning via (structured) adaptive algorithms. In machine unlearning, given a model trained via dataset S, one attempts to build algorithms which can efficiently remove any point z from the dataset post-training in such a way that the altered model is indistinguishable from training on $S \setminus \{z\}$. The main goal is to build algorithms where the cost of unlearning is significantly less than the cost of simply retraining the model. The study of machine unlearning is practically motivated by data privacy laws and `the right to be forgotten,’ in particular the General Data Protection Regulation (GDPR), and California Consumer Privacy Act (CCPA), which require (in limited circumstances) that a company must delete stored personal data on request.

In this work, the authors generalize the prior techniques of Ullah et al. (COLT 2021) for machine unlearning via (noisy) SGD via total variation stability to hold for a general class of adaptive algorithms built on either "linear" or "prefix-sum" queries, two well-studied classes of algorithms within optimization and privacy. In particular, they show how to modify any such algorithm into one in which unlearning costs only a $\rho$-fraction as many queries as retraining (for arbitrary $\rho > 0$). The main contribution is the algorithm and analysis for prefix queries, which is roughly based on combining Ullah et al.’s TV-stability techniques with the binary tree mechanism of Dwork, Naor, Pitassi, and Rothblum (STOC 2010). The authors also study an extension of these methods to the streaming setting, where multiple insertions and deletions in such a manner in an online fashion.

Finally, authors give a number of applications of this general framework based on known algorithms in the literature, namely for stochastic convex optimization (SCO) via Frank-Wolfe and Dual Averaging, and dimension-independent bounds for GLMs via the above and Johnson-Lindenstrauss (as in Arora et al. 2022). These techniques provide the best known unlearning algorithms for SCO, improving the known convergence rate from $\frac{1}{\sqrt{n}} + (\frac{\sqrt{d}}{n\rho})^{2/3}$ to $\frac{1}{\sqrt{n}} + (\frac{\sqrt{d}}{n\rho})$, thus showing unlearning has no asymptotic cost up to relative complexity $\sqrt{d/n}$. The authors also give applications of the linear query method to federated learning and k-means.
strength_and_weaknesses: Strengths:

1. The authors introduce the first general framework for (exact) machine unlearning for adaptive algorithms using linear and prefix query algorithms
2. They give improved minimax rates for unlearning in stochastic convex optimization, a ubiquitous paradigm.
3. They give many applications (federated learning, k-means, various SCO settings…), and generalize to streaming setting
4. The paper is generally well written (with some exceptions detailed below)


Weaknesses

1. While machine unlearning is motivated by data privacy/rights as a general concept, the exact model studied in this paper is not clearly well motivated. Approximate machine unlearning (or any say computationally indistinguishable method) seems substantially more useful. Furthermore, while the authors claim that GDPR and CCPA require companies to fully retrain models in this sense, as far as I can tell these laws say nothing of the sort, and only include vague instructions that personal data should be removed upon request. I find the introductory paragraph to be very misleading in this sense. This said, there is legal precedence for requiring model re-training in a 2021 Federal Trade Commission decision, but this is a specific instance and should be cited as such. It seems very plausible that approximate unlearning would be accepted in general.
2. Many of the results seem to be straightforward generalizations or combinations of prior work and techniques, though proving the prefix query theorem does require some involved technical calculations. Furthermore, since no lower bounds are given in the paper it is hard to tell how substantial the rate improvements are.
3. A more minor complaint is that the notion of relative unlearning complexity needs better motivation. Of course the idea of algorithms whose unlearning time is faster than retraining is natural, but it seems like the denominator comparison should maybe be to the best possible rate. For instance, one could have a very poor unlearning algorithm with very good relative complexity, where it would be better to just run a different method from scratch.
4. No accuracy guarantee is given for the general framework, and has to be shown on a by-algorithm basis. The authors state informally that accuracy should be preserved for noise-tolerant algorithms, but if one is giving a general framework for application this should be formalized.
5. While the level of detail given in the main body is ok for the short version, there needs to be additional background and exposition somewhere in the paper. It should not be necessary to be familiar with any specific prior work to understand the paper. I'd also recommend defining even very basic terms (at least briefly) such as query release, for non-familiar readers.

Typos: 

Page 5: In 2. Efficient Unlearning Model should “does” be “doesn’t”?

Page 7: Line 11 does not seem to be rejection sampling. Perhaps line 13?
clarity,_quality,_novelty_and_reproducibility: The work is fairly well-written (with exceptions observed above), and has reasonable quality applications. The framework introduced for adaptive query algorithms is original, though it draws heavily on analysis techniques and algorithms from prior work.
summary_of_the_review: This is a nice follow up work to Ullah et al. 2021, the idea of building a general framework of machine unlearning for adaptive query algorithms is a good idea, and the authors give a number of applications. On the other hand, it is not clear that the model of unlearning (and complexity measure) the authors study is interesting or well-motivated, and at a technical level it is also not clear much additional insight is given over prior works. As it stands, I am not sure this work is quite above the bar of ICLR.

Edits: See rebuttal and response, raising to above bar.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper provides a framework for efficient machine unlearning for stochastic convex optimization. In particular, the work builds upon the prior paper by Ullah et al. (2021) and generalize it to handle prefix sum queries. As for concrete applications, this enables machine unlearning for variance-reduced  stochastic convex optimization (SCO) methods and dual averaging schemes. 
strength_and_weaknesses: The paper claims a set of efficient algorithms for exact machine unlearning of SCO methods that are widely used in ML practice.  I believe this is a well-motivated question and the technical contributions here are novel and non-trivial. 

However, I am concerned about the technical clarity of the presentation. Overall, I find the paper lack of some conceptual exposition to be accessible to non-experts of the area. In fact, much of the materials rely upon using the prior work Ullah et al. (2021). I believe for those who are not familiar with Ullah et al. (2021), the technical sections of the paper would be hard to parse. 

Most importantly, the main algorithm from Section 4 (on prefix sum queries) is mostly described by the pseudocode. I find it hard to understand it at a conceptual level. Why and how does it perform unlearning? What does the noise-adding mechanisms do here? I think the issue stems from not having sufficient exposition on the coupling nature of the problem and the technique of reflection coupling.  (It appears that the techniques are borrowed from Ullah et al. (2021), which I have not read.)  I suggest the author(s) add a technical overview section earlier in the paper. 

The paper does not give empirical validation of their methods, though I do not consider it a major weakness, as this work is theoretical in nature. 

Some other minor comments: 
---- 
In what sense is “linear queries” (Definition 8) is “linear in the data-points”, as claimed in the introduction? In Definition 8, the function p_j can be non-linear in z_j. In fact, if p_j is the gradient of the loss function, it can easily be non-linear in z_j (for many ML models and choices of the loss function). 

After Definition 6 it should be mentioned that the bounded sensitivity condition is satisfied in variety of applications. 

I think Appendix B requires more exposition. What does Algorithm 6 do at an intuitive level?  What is the LearnLinearQueries function? In fact, I suggest the author(s) expand this section and put it into the main paper as a warm up before delving into the prefix sum queries. 

The paper should also discuss related work in more detail. In addition to Ullah et al. (2021) that this work builds upon, there’s been a flurry of recent work on machine unlearning. This includes, for example, Descent-to-Delete: Gradient-Based Methods for Machine Unlearning by Seth Neel, Aaron Roth, Saeed Sharifi-Malvajerdi (ALT 21)

Mechanical suggestions
---
1. In the additional prelim section, I suggest the author(s) to elaborate on reflection coupling, especially its formal guarantees. (The original paper claims the result in the setting of Brownian motion, which seems different from what’s going on here.)
2. End of page 2: Frank Wolfe -> “Frank-Wolfe”
3. Section 5: “[...], and thus fits into the framework”
4. Algorithm 6, the Load() function is undefined?

clarity,_quality,_novelty_and_reproducibility: The main technical contribution of the work is novel and original. In terms of clairty, I believe the paper requires more polishing to be readable. 
summary_of_the_review: Given the quality of the presentation, I cannot recommend accept. However, I can see that the paper could be improved a lot if the author(s) put some efforts on writing during the rebuttal period.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper studies the problem of machine unlearning and improves oracle complexity for stochastic convex optimization (SCO) under both smooth and non-smooth setting. The key idea is a new prefix-sum unlearning sub-routine that enables one to use Variance reduction Frank-wolfe and dual averaging algorithm for SCO.

Result. For smooth SCO, the paper gives an $O(\frac{1}{\sqrt{n}} + \frac{\sqrt{d}}{n\rho})$ accuracy answer with expected runtime $O(\rho n)$ per update using variance reduced Frank Wolfe. For non-smooth SCO, it gives $O(\frac{1}{\sqrt{n}}) + \frac{d^{1/4}}{\sqrt{n\rho}})$ accurate answer with $O(\rho n)$ per update, using dual averaging. Dimension independent results have also been obtained for the special case of generalized linear model.
strength_and_weaknesses: Strength. The paper provide improved oracle complexity for stochastic convex optimization (SCO) of the machine unlearning task. The prefix-sum idea seems simple, but it is good enough for one to use powerful tool from SCO. Meanwhile, I expect the prefix-sum subroutine could be useful for other applications of machine unlearning


Weakness. There is no major weakness. 
clarity,_quality,_novelty_and_reproducibility: The prefix-sum idea seems to be new in the area of machine unlearning.
summary_of_the_review: The paper gives improved rate for stochastic convex optimization of machine unlearning with some interesting ideas. I would vote for acceptance.

Question for authors. Are there any lower bounds known for SCO of machine unlearning?


-----------

Post rebuttal

I have read the rebuttal and my evaluation remains.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The paper studies the problem of machine unlearning where the goal is to update a model without retraining from scratch in response to deletions of training datapoints. The paper considers exact unlearning where the updated model is indistinguishable from the model obtained by retraining from scratch. The paper designs unlearning algorithms that improve the excess population risk for linear and prefix-sum queries, and they apply to several settings of interest, including unlearning in the context of both smooth and non-smooth stochastic optimization and generalized linear models.

The reviewers appreciated the theoretical contributions of the paper. In particular, the algorithm and analysis for prefix sum queries introduces novel ideas and techniques that were appreciated by the reviewers. The reviewers were concerned about the paper's writing and its technical clarity and accessibility to a broad audience. The authors revised the exposition based on the reviewers' feedback. During the subsequent discussion, the reviewers noted that the revision improved the exposition but the paper could further benefit from a more substantial revision that will make it more accessible to the broader ICLR community. Some specific suggestions are the following:

- Provide an overview of the pseudocode in the main body.
- Explaining in the main body the algorithm and results on a concrete application will facilitate understanding. One of the applications discussed in the appendix, the kmeans or federated learning, could be brought forward and used for this purpose.
- Illustrate how the guarantees translate to specific examples of interest.
- Consider some experiments on synthetic data as a proof of concept for the algorithms.
- Add an analysis of both space and time, discuss that the entire model needs to be stored.

We encourage the authors to further revise the paper to make it more accessible to a broader machine learning audience. 
justification_for_why_not_higher_score: The exposition could be improved to make it more accessible to the broader ICLR community.
Decision: Reject