Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 3: Reject: For instance, a paper with technical flaws, weak evaluation, inadequate reproducibility and incompletely addressed ethical considerations.
review_content: summary: This papers tackles the problem of machine unlearning, that is, removing training data upon request from a model, as if the model is trained only with the retained data. The proposed approach, PCMU, trains a model with randomly smoothed quantized gradient. Analogous to certified robustness, the paper presents some certified radius of the proposed method, against to pertubation of the gradient. Unlike previous machine unlearning approaches, PCMU directly trains a model that is robust to data removal, so it does not require an additional unlearning stage. Experimental results show that PCMU can achieve a more similar error rate with retraining than competitive models. 
strengths_and_weaknesses: Strength
- some theoretical results are provided
- the proposed method is faster than previous methods, and it can matches the accuracy better with the retraining approach

Weaknesses
- I'm not an expert on machine unlearning. But from my perspective, rather than a machine unlearning method, the proposed approach looks more like a differential privacy work, which trains a model without utilizing too specific features from individual users, so the trained model automatically satisfies removal requirements. I wonder whether it counts as machine unlearning.
- The writing is somewhat vague: there is not a description or pseudocode of how the training and unlearning are performed, making the paper difficult to follow.
questions: 1. Does the proposed approach work for non-uniform data removal? For example, a "group" or class of samples are removed completely. 
2. In Eq. (21), I suppose \bar G is a gradient, and \epsilon ~ \mathcal D is a datum. What does it mean by adding a data and a gradient?
3. What does "prompt" in the title mean?

Typos:
L33: "certified" should be capatalized. 
L53: two consecutive periods. 
limitations: There are not apparent further limitations or potential  negative societal impacts other than those I raised for weaknesses and questions.
review_title: null

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper presents a novel certified machine unlearning framework that targets the issue in the expensive computational cost of training and unlearning. The authors analogize certified robustness on classification against adversarial attacks to certified machine unlearning on gradient quantization against data removals. The randomized gradient smoothing and quantization techniques are developed to guarantee that the learnt model shares the same gradients (and parameters) and has the same performance with the naive unlearning model retrained on only the remembered data, with only the cost of simultaneous training and unlearning. The theoretical analyses validate the effectiveness of certified machine unlearning in terms of the certified radius and the certified budget of data removals. Overall, the studied problem is interesting and practically important. The experimental results look promising.

strengths_and_weaknesses: Strengths:

1. Existing machine unlearning methods separate the unlearning process into two sequential operations of training and unlearning, which leads to non-trivial computation cost when training complex models over large datasets. In addition, these methods often sequentially address multiple unlearning requests one by one. To improve the unlearning efficiency, this work trains and unlearns the model simultaneously.

2. The authors propose a randomized gradient smoothing and quantization technique to directly train an unlearning model in advance with fast convergence and certified unlearning guarantees. The framework is able to resolve the requests of data removal in a timely and cost-efficient manner. 

3. The proposed method provides a general machine unlearning framework. The proposed framework is important for privacy-critical applications that usually require near-zero tolerance of data leaking, such as financial and health data analyses.

4. This work theoretically analyzes and understands the certified radius regarding the data change before and after data removals and the certified budget of data removals in machine unlearning. Extensive experimental results on different benchmark datasets have been conducted to validate the efficacy of the developed prompt certified machine unlearning algorithms.

Weaknesses:

1. The paper provides descriptions of the benchmark image classification datasets and learning models in the paper and appendix. It would be nice to include the description of the data removals for how to separate the datasets into the forgotten data and the remembered data for each benchmark dataset.

2. It would be interesting to see the results about different smoothing strategies exploited in certified machine unlearning problems, such as Laplacian and uniform smoothing.
questions: Data removal description and other smoothing strategies.
limitations: It is unclear of the potential negative societal impacts of the results, such as security, privacy, and fairness issues, etc.
review_title: null

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: The authors propose a novel certified machine unlearning algorithm to improve the unlearning efficiency for complex models on large-scale data. First, the authors present an analytic framework to connect  randomized smoothing for certified robustness on classification to randomized smoothing for certified machine unlearning on gradient quantization. Second, the paper develops a prompt certified machine unlearning model for producing the effective certificates of data removals based on randomized data smoothing and gradient quantization. Finally, the authors propose a practical framework of randomized gradient smoothing and quantization for producing the high confidence certificates in an efficient manner.

The proposed PCMU method brings three significant benefits: simultaneously conduct the training and unlearning for improving the unlearning efficiency, one-time training for responding multiple machine unlearning requests at a time, and no need to know the forgotten data before the unlearning.

strengths_and_weaknesses: Strengths:

+ The authors study an important research problem, i.e., prompt machine unlearning, which is important to improve the unlearning efficiency for complex models on large-scale data and to provide the timely response to a series of machine unlearning requests. There are few prior works to conduct this problem. 

+ The motivation for proposing randomized gradient smoothing and quantization techniques is clearly explained. The method and the claim are correct and sound. The authors provide enough methodology description and theoretical analysis to explain their proposed PCMU model.

+ The paper conducts the theoretical analysis to derive the certified radius regarding the data change, the certified budget of data removals, and the correlation between two types of certified radii in two frameworks. This work integrates the certifying and training of machine unlearning into a uniﬁed framework for further enhancing the unlearning performance. The convergence analysis is conducted to demonstrate the effectiveness and efficiency of the prompt certified machine unlearning algorithm.

+ The paper provides comprehensive extensive evaluation on three real datasets to demonstrate the superior performance of the proposed techniques against a number of SOTA baselines. The experiment results look promising.

Weaknesses:
- There are several typos and the paper would beneﬁt of a careful proofread. For example, "which are used to derive the certified budget B about R'" in P2 -> "B'", "the certified budget of data removal" in P5 -> "removals", and "Notice that the accuracy and error on test data by our PCMU keeps unchanged" in P8 -> "keep".

- It would be nice to move the related work section to the paper for readers to better understand and appreciate the technical contributions of this paper compared with existing studies, instead of the appendix.

- In the experiments, Tables 1-2 and relevant texts lie in different pages, which decreases the paper’s readability. I suggest the authors to update the paper layout to get more clear presentation.

questions: See the above weaknesses.

limitations: None
review_title: null

Meta-review: metareview: This paper proposes an algorithm for simultaneous learning and unlearning without the knowledge of the datapoints that will be forgotten. This reduces the computational cost associated with unlearning in a unified fashion. Both experimental and theoretical results are interesting and the paper would be a great addition to NeurIPS. 
confidence: Certain
Decision: Accept