Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: 1. Summary

The paper proposes a novel method for knowledge removal in a MCMC context. The contribution is four-fold: First, a theoretical analysis relates the MCMC unlearning problem to an optimiziation problem introduced. Second, the conversed problem is related to a MCMC influence function. Third an abduction of theoretical results is done. Finally real world data experiments are performed showing that the proposed approach can indeed tackle the problem introduced.
main_review: 2. Rationale for the score

The problem is very nicely introduced and well justified with recent (GDPR!) developments in application of IT / AI System.

The contribution is well structured into four main parts, each part being then outlined in the paper.

The supplementary material is complete and provides a nice benefit. 

The Choice of BNNs and GMMs as use cases for MCMC learned distributions is well made, both algorithms being widely used and rather important scenarios for such MCMC distributions.

The choice of real world dateets (FMNIST and CIFAR-10 ) is taking well known but complex enough datasets into account.

The paper is well structured, graphical contributions in the main part as well as in the appendix serve to enable a good understanding of the approach done.

Weaknesses: None

summary_of_the_review: A very nice paper, both well justified and nicely outlined. I can't see any weaknesses.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper approaches the problem of how to make a machine learning model forgets some data samples it was trained on. This is of high relevance in the context of “the right to be forgotten” legislation. In this case, this work approaches this problem for machine learning models represented as Markov Chain Monte Carlo, which is of relevance in the context of Bayesian learning. The presented approach is based on the formalization of the problem as an optimization problem. Authors also provide theoretical guarantees that the presented approach really makes the Markov Chain Monte Carlo forgets a given set of samples. 
main_review: Strong Points

- This work addresses a relevant problem that has not been addressed before in the literature. The  “the right to be forgotten” is part of the legislation of many countries. AI-Industry needs tools to implement this right. Previous literature do not cover the case where the machine learning model is represented as a sequence of samples (i.e. Markov Chain Monte Carlo)

- The proposed method is sound and provides theoretical guarantees about the capacity of the presented approach to implement this task. This is something that is really needed in this context. 

- A well-performed experimental evaluation shows the effectiveness of the presented method. 


Weak Points

- The theoretical guarantees provided in this work are based on several technical assumptions which are hard to verify in real contexts. The question is: Is this proposed method an acceptable solution in a legal context? Your approach provides theoretical guarantees that it will erase this information from the model (with an epsilon error), but this guarantee only applies if a set of assumptions are met. But it is almost impossible to verify that theses assumptions are met in a real context. In consequence, will the legislator be willing to accept this method as a solution to implement “the right to be forgotten”? This is not discussed in the paper. 

summary_of_the_review: I lean to accept this paper. I think they present a solid contribution to a relevant problem. Even though, there are some limitations that should be discussed by the authors.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This paper proposes the first method in MCMC for the problem of knowledge removal (meaning that the sampled posterior must be modified so that some subset of the training data is "forgotten"). The paper introduces the concept of epsilon-knowledge removal to measure how closely the modified posterior corresponds to the exact posterior that would have been obtained based on only the remaining data.
main_review: Strengths:

- the problem of knowledge removal seems like it may see a lot of application, and introducing the first algorithm for MCMC is an important  step

- the theoretical development of the method looks solid

Concerns / questions:

- The proposed algorithm works by translating the posterior without otherwise changing its shape. This would imply that many aspects of the data are not forgotten. (In fact, I would say that in applications where MCMC is being used to describe the shape of the posterior, then aspects of the posterior other than its location are apparently important in that application. If only the location of the posterior was important, simpler methods would have sufficed.) I think the empirical results largely hide any potential shortcomings in this area: For the simulated data, only the cluster centers are shown (Figure 1(a)), so all other aspects of the posterior remain hidden. For the BNN experiments (Table 1), none of the columns give information addressing this issue. (The column with the knowledge removal estimator has large numbers for all methods, suggesting that all result in similarly poor approximations of $\hat{p}_{S-S'}$, with the proposed method consistently marginally best. But since these are estimated upper bounds to KL-divergences, it is unclear what this implies about the actual KL-divergences of any of the methods.)

I think the inability to adjust anything about the posterior other than its location is a serious drawback. As epsilon becomes large, the concept of epsilon-knowledge removal becomes meaningless: at some point, even the original posterior (which didn't forget anything) satisfies it. The paper should be more forthcoming about these issues. Do you have a way of better quantifying how large the deviations are in both experiments?

- In section 5.2, it's unclear to me from the description what the difference is between the baseline method and just retraining.

Small remarks:

- In Table 1, for the results about CIFAR-10+SGHMC, 3000 examples, error on S_test, the score for "Ours" is bolded, but the score for IS is actually highest.

- Figure 1(b), y-axis: why does it say (/s), shouldn't that be (s)?

- Appendix C.2: "phrases" should be "phases"
summary_of_the_review: This paper introduces an interesting problem, studies it well and comes up with a first algorithm. However, I have main concern about the usability of this algorithm, which only adjusts the location of the posterior while leaving its shape untouched. I am worried that under this restriction, it may be impossible to achieve the intended goal, namely forgetting part of the data. Furthermore, I think the paper should have discussed these issues with the proposed approach.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper demonstrates an algorithm to remove the effect of some training examples, S', on a learned model. In particular, it estimates the shift on the model parameters when the examples S' are removed, where the shift models the information contribution from the removed dataset. The shift is estimated by solving an optimization problem to minimize the KL divergence between the approximated parameter distribution using the shift and the estimating ground truth parameter distribution. Author demonstrates that the shift can be efficiently estimated using only the learning experiences that are collected with the entire dataset with theoretical approximation guarantees. Hence, one can estimate the model parameters without the knowledge of the removed the dataset and do not need to retrain the model at the same time.
main_review: Strength: 
1) The demonstrated algorithm is very simple. From the evaluation, the quality of the method also seems to be effective.
2) The proposed epsilon-knowledge removal terminology also seems to be clean. In addition, this new definition helps to evaluate the quality of the unlearning algorithm.

Weakness:
1) The paper seems to very dense on mathematical and technical details. It would be nice if authors could introduce some intuitive examples to explain how the shift is estimated.  For example, from Definition 3, the calculation of the shift requires the expectation computation under the distribution p_S. Is this estimated through samples from the p_S? 
2) The evaluation of the method seems too numerical. Although I really like the metrics from the epsilon-knowledge removal terminology, some case study would make the evaluation more convincing as the problem of removing training examples is a real world problem. For example, the evaluation can be more entertaining if author can demonstrate the change on a model's prediction (both the label and confidence) on some images when similar images are removed from the training set. 

Question:
Is there difficulty of extending a shift on theta to a linear transformation on theta? There seems to have some benefits of modifying each sampled modeled parameter using some scalar multiplier, as it also helps to adjust the geometry of the distribution, i.e. variance, which should be changed with the number of training examples? 
summary_of_the_review: The problem of removing the effect of some training examples on a trained model is well motivated by the paper.  In addition, the simplicity and the effectiveness of the proposed method should be contributory to the community.

At the same time, the reviewer is not able to verify the proofs of the theorems in 4.3 and 4.4.
review_title: null

Meta-review: The article proposes an approach to alter the approximate posterior distribution in order to remove some of the information (unlearning). The approach is applicable when the approximate posterior is obtained via (stochastic gradient) MCMC methods. Unlearning is done by shifting the approximate true posterior by some value delta, which is found via optimisation with an influence function.

The approach is novel, tackles an important problem and is mathematically sound. Reviewers have highlighted some of its limitations. In particular, the modified posterior is obtained by translating the original posterior, without changing its shape; many aspects of the data may therefore not be forgotten. The authors have partially addressed this concern in their response and provided additional experiments. Although there is still disagreement amongst reviewers, I recommend acceptance. 

A Minor comment:
I would not present MCMC merely as a "machine learning algorithm" (p.1), nor as a "sampling based Bayesian inference method" (p.1 and p.2). MCMC is a generic approach to approximate high-dimensional integrals and obtain samples approximately sampled from some target distribution, dating back from the work of Metropolis (1953) and Hastings (1970). Its application to Bayesian inference/machine learning problems came much later, see e.g. the excellent review of C. Robert and R. Casella: A short History of MCMC: Subjective recollections from incomplete data. Statistical Science, 2011.
Decision: Accept (Poster)