Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The paper provides an algorithm for online data deletion. They consider unlearning with convex / strongly convex loss functions (with additional assumptions standard in the literature). The key improvement in the algorithm over prior works in [15, 29] is to provide an update step that does not require to recompute a new hessian inverse for every new deletion request (which they call infinitesimal Jacknife (IJ). Thus, they improve the running time from O(md^3) to O(md^2) where \(m\) is the number of deletions that can be handled. The authors provide extensions of this update step when the underlying regularization is not smooth (but the objective function is still smooth). This is obtained using a proximal update. Finally, the authors show an interesting limitation of unlearning for ERM based learning procedures. 
strengths_and_weaknesses: Strength: The topic of machine unlearning is new and upcoming. The paper addresses computational side of the problem in the online deletion setting which is an important problem. The paper is well written! 

Weaknesses: 
1. I feel the key technical improvement from prior works is to come up with update in 5a in which H_l^{-1} does not need to be updated after every deletion request. While being interesting, I feel jacknife, proximal updates, etc are all well established theoretical tools and there is not much that fundamentally new, which is why I am not giving this paper a strong accept. 


2.  I am a bit confused by the rationale to choose Definition 1 from [15] (instead of the smilar definition from [29]). In order for this definition to hold, one needs to randomize the out of the learning algorithm (which would decrease performance). In the corresponding definition in [29], one does not need the learning algorithm to be randomized. Furthermore, in your experiments where you report RT is this ERM + noise or just ERM ? (I feel there is a mismatch between the two sections). 

3. Suppose we restrict outselves to generalized linear models ? In this case, the hessian is the sum of rank-1 matrices (one corresponding to each data point), and online updating the hessian as in [15, 29] is easy to do. What are the benefits of your algorithm in that case? 

4. Do you have any suggessions from mitigating the reported issue in Section 5 for hyperparameter-tuned models ? 

questions: Refer to above comments
limitations: I do not see any negative societal consequences. In fact, the paper is trying to develop solutions for the important issues of right to be forgotten.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: The paper proposes an online approximate unlearning algorithm that is efficient in computation and memory. To begin with, the paper uses the infinitesimal jackknife to enable the proposed algorithm to delete data from models trained which is non-smooth regularized. Furthermore, the paper theoretically proves the generalization and deletion capacity of the proposed method. Finally, extensive experimental results demonstrate that the proposed method can exceed in retraining the model and the second-order Taylor Approximation[1]. 
From my point of view, this paper falls into several significant drawbacks and might be improved by addressing the following issues:
1. It’s not clear how can the proposed method be effective in non-smooth regularized models. 
2. The proposed method only inverts the Hessian for one time, but how can it ensure the total error is tolerable. 
3. The supplementary lacks the comparison of runtime in different hyperparameter settings. 
4. The candidates of the hyperparameter \lambda may be {10^{-3}, 10^{-4}, 10^{-5}, 10^{-6}} rather than {1^{-3}, 1^{-4}, 1^{-5}, 1^{-6}}. 

[1] Ayush Sekhari, Jayadev Acharya, Gautam Kamath, and Ananda Theertha Suresh. Remember what you want to forget: Algorithms for machine unlearning. Advances in Neural Information Processing Systems, 34, 2021.

strengths_and_weaknesses: Strengths: 
1. The paper provides sufficient theoretical proof of the proposed method. 
2. According to the experimental results, the proposed method outperforms much better than the previously proposed unlearning algorithms. 
Weaknesses: 
1. The paper mainly enables the unlearning algorithm to be applied in non-smooth regularized models, but does not explain it specifically. 
2. Lacking the comparison of runtime in different hyperparameter settings.

questions: 1. How can the proposed method be effective in non-smooth regularized models?
limitations: The paper has not addressed the limitations of their work. It states that the proposed method fails to run with hyperparameter tuning, which is a common issue existing in unlearning algorithms.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: In this paper, the authors study the data deletion problem under the online setting. For linear models, the authors propose a second order online data deletion algorithm that enjoy better theoretical guarantees than existing methods. The algorithm can also be extended to non-smooth regularization objectives through a proximal gradient variant. Empirical studies have also shown the proposed algorithm to significantly improve over the time complexity of existing baselines while sacrificing some test accuracy. In the end, the authors propose a simple cross validation setting where all existing algorithms fail to have any theoretical guarantees.
strengths_and_weaknesses: Overall, I find the paper to exhibit reasonable improvement over existing work. I also find the discussion in the end of the paper regarding model tuning to be valuable and a highlight of the paper.

On the other hand, I find the setting motivation to be relatively unsupported:
1. The authors use data regulations for industrial sized models as motivation of the paper. However, most industrial models of the scale are deep neural networks. The study of only linear models seem ill-suited.
2. The authors argue that the online setting is more practical. However, taking GDPR for example, the companies are obligated to delete user data only within a month instead of immediately. As a result, I find the batched setting to be more realistic where retraining could also be competitive.
3. As a result of the above comment, is it fair to compare IJ against RT and TA in the online setting? I believe it is more reasonable compare against the methods for removing an entire batch.
4. The proposed Algorithm 1 would benefit from more detailed description and intuition.
questions: 1. Could you give a concrete example where online data deletion is necessary?
2. Is there motivating examples of linear models of scale significant enough that retraining underperforms the proposed data deletion algorithm? Or alternatively, do the authors find the algorithm easily generalizable to neural networks?

limitations: I think the limitation of hyper-parameter tuning is very interesting.

On the other hand, please see the above questions regarding limitations of use cases of the proposed algorithm.
review_title: null

Meta-review: metareview: Most of the reviewers agree that this paper is well written and provides a notable improvement over prior works on algorithms for data deletion. Some initial concerns regarding the proper motivation for the problem setting have been largely addressed.
confidence: Less certain
Decision: Accept