Knowledge Removal in Sampling-based Bayesian Inference
Authors: Shaopeng Fu
Fengxiang He
Dacheng Tao
Venue: ICLR 2022 Poster (2022)
Keywords: Bayesian inference
Markov chain Monte Carlo
machine unlearning

Abstract: The right to be forgotten has been legislated in many countries, but its enforcement in the AI industry would cause unbearable costs. When single data deletion requests come, companies may need to delete the whole models learned with massive resources. Existing works propose methods to remove knowledge learned from data for explicitly parameterized models, which however are not appliable to the sampling-based Bayesian inference, {\it i.e.}, Markov chain Monte Carlo (MCMC), as MCMC can only infer implicit distributions. In this paper, we propose the first machine unlearning algorithm for MCMC. We first convert the MCMC unlearning problem into an explicit optimization problem. Based on this problem conversion, an {\it MCMC influence function} is designed to provably characterize the learned knowledge from data, which then delivers the MCMC unlearning algorithm. Theoretical analysis shows that MCMC unlearning would not compromise the generalizability of the MCMC models. Experiments on Gaussian mixture models and Bayesian neural networks confirm the effectiveness of the proposed algorithm. The code is available at \url{https://github.com/fshp971/mcmc-unlearning}.

Published as a conference paper at ICLR 2022
KNOWLEDGE REMOVAL IN SAMPLING-BASED BAYESIAN INFERENCE
Shaopeng Fu' "u'", Fengxiang He & Dacheng Tao'
'The University of Sydney, Australia, ²JD Explore Academy, China shfu70088 uni sydney, edu. au, fengxiang. f. hw@.he@mmm....m 1 com, dacheng. taolsydney edu.ar au
ABSTRACT
The right be forgotten has been legislated in many countries, but its enforce- ment in the AI industry would cause unbearable costs. When single data dele- tion requests come, companies may need delete the whole models learned with massive resources. Existing works propose methods to remove knowledge learned from data for explicitly parameterized models, which however are not appliable to the sampling- based Bayesian inference, i.e., Markov chain Monte Carlo (MCMC), as MCMC can only infer implicit distributions. In this pa- per, we propose the first machine unlearning algorithm for MCMC. We first convert the MCMC unlearning problem into an explicit optimization problem. Based on this problem conversion, MCMC influence function is designed to provably characterize the learned knowledge from data, which then delivers the MCMC unlearning algorithm. Theoretical analysis shows that MCMC learning would not compromise the generalizability of the MCMC models. Ex- periments Gaussian mixture models and Bayesian neural networks confirm the effectiveness of the proposed algorithm. The code is available at https: //ggthhub.com/Esppp// www.emmmnnneeaainnnnn
INTRODUCTION
"The right to be forgotten" refers to the right of individuals to request data controllers such as tech giants delete the data collected from them. It has been recognized in many countries through legislation, including the European Union's General Data Protection Regulation (2016) and the Cal- ifornia Consumer Privacy Act (2018). In the field of machine learning, legal experts suggest that companies may need to delete and re-train the machine learning models to meet the legal require- ments of the right to be forgotten (Li al. 2018, Garg al., 2020). However, training a machine learning model would usually cost massive amounts of resources, including data, energy, and time. Thus, the enforcement of the right be forgotten in the Al industry may result in unbearable costs.
Toward this end, recent works (Cao & Yang 2015 Guo et al. 2020) propose machine unlearning algorithms to efficiently characterize and remove the knowledge learned from specific data. To enable knowledge removal analysis. existing unlearning approaches usually require the machine learning models to be explicitly parameterized, which however do not cover an important family of machine learning algorithm, the Markov chain Monte Carlo (MCMC). MCMC is sampling- -based Bayesian inference method that aims to draw samples along a Markov chain to approximate a target posterior distribution (Hastings 1970 Geman & Geman 1984 Welling & Teh 2011). Distributions inferred by MCMC are usually implicitly parameterized, which makes it difficult to directly apply existing unlearning algorithms to the MCMC unlearning problem.
In this paper, we propose an MCMC unlearning algorithm to realize the right to be forgotten in the baseling-based Bayesian inference for the first time. The key of tackling the MCMC unlearning problem is to design methods to directly analyze the implicit parameter of the learned distribution. To this end, we propose to employ the learned implicit distribution approximate the target poste- rior under the measure of KL-divergence, which then converts the MCMC unlearning problem to an
"The authors contributed equally.

---

Published as a conference paper at ICLR 2022
optimization problem with an explicit distribution parameter for knowledge removal analysis. Based on this conversion, an MCMC inftuence function is designed (Huber 2004| Koh & Liang 2017) to characterize the knowledge learned from single data samples. The new influence function then de- livers the MCMC unlearning algorithm, which removes data knowledge by directly subtracting the corresponding influence from the learned distribution.
Theoretical analyses are conducted for the proposed MCMC unlearning algorithm. For the knowl- edge removal analysis, we prove that the proposed algorithm can provably realize a s-knowledge removal, which is a new notation defined for evaluating the machine unlearning performance in Bayesian inference. For the generalization analysis, a PAC-Bayesian generalization upper bound (McAllester 1998 1999; 2003; He et al.) (2019) is established for the distribution processed by the MCMC unlearning algorithm. The upper bound shows that the difference introduced by MCMC unlearning in the generalization upper bound no larger than the order of O ((V(N))))) This result demonstrates that the proposed algorithm would not compromise the generalization ability of the learned distribution.
In summary, our work has four main contributions: (1) We enable the knowledge removal analysis in MCMC by converting the MCMC unlcarning problem to an optimization problem. (2) Based on this problem conversion, from data, which then delivers the MCMC unlearning algorithm. (3) We conduct theoretical analyses and prove that the MCMC unlearning can realize e-knowiedge removal and has little impact on the generalization ability of the learned distribution. (4) We conduct comprehensive experiments verify the effectiveness of the proposed algorithm, which include Gaussian mixture models for clustering on synthetic data, and Bayesian neural networks for classification on real-world dataset. The results suggest that the MCMC unlearning can effectively remove the knowledge learned from the requested data while retaining the information learned from other data intact.
design an MCMC influence function to characterize the knowledge learned
2 RELATED WORKS
Markoy chain Monte Carlo. MCMC is a Bayesian inference method that would draw samples along a Markov chain, in which the drawn samples are proved to converge to that from a targeted distribution (Hastings 1970). Although many improvements have been made such as Hamiltonian
Monte Carlo (HMC) (Duane al. 1987: Neal et al.) (011). Gibbs sampling (Geman & Geman 1984 George & McCulloch] 1993) and slice sampling (Neal 2003 Walker (007). MCMC still suffers from huge computational cost when inferring on large-scale dataset, e.g. computer vision
and image processing tasks (Zhang et al.) 2020b; Wang et al. 2020), since each sampling step in MCMC requires computation over the whole dataset.
To tackle this issue, WWlling & Teh (201)) introduce a scalable MCMC sampler named stochastic gradient Langevin dynamics (SGLD) that by adding a proper noise to a standard stochastic gradient optimization algorithm (Robbins & Monro 1951), which can help the update iterations converge to samples from the true posterior distribution. Since that, a variety of stochastic gradient MCMC samplers (SG-MCMC) have been proposed, including stochastic gradient HMC (SGHMC) (Chen) et al. 2014), Patterson & Tch (2013), Ahn et al. (2012), Ding et al. (2014), and Zhang et al. (2020a). Ma et al. (2015) further design complete framework for constructing SG-MCMC.
Machine unlearning. Machine unlearning aims to remove the knowledge learned from specific data in efficient manners (Cao & Yang 2013). Existing approaches can be roughly divided into exact methods and approximate methods. Exact methods aim to recover the model trained without the removed data exactly and are usually realized via reducing the retraining cost. For example, Ginart et al. (2019) design an efficient unlearning method for k-means clustering via model quantization. Bourtoule et al. (02T) propose a SISA framework that would only retrain the affected part of the model during data deletion. Other advances include Ullah al. (2021) and Brophy & Lowd 202
On the other hand, approximate methods aim to modify the trained model to approximate that trained only on the remaining data. A series of works (Guo al. 2020 Golatkar al. 2020 2021) are de- signed via characterizing the influence of data on the trained model with influence functions (Cook) & Weisberg 1982, Huber 2004 Koh & Liang 2017). Other approaches include Baumhauer et al.
(2020) and lzzo et al. (2021). Some works have studied machine unlearning in Bayesian infer-
ence (Nguyen et al." 2020 Gong et al. 2021). However, these works only focus on variational
2

---

Published as a conference paper at ICLR 2022
inference, optimization-basee Bayesian inference method, and could not be applied to sampling- based Bayesian inference, MCMC. In contrast, our approach is the first machine unlearning method for MCMC, with theoretical knowledge removal guarantee.
3 PRELIMINARIES
Suppose p(=10) is a parameterized distribution over the sample space 2, where E θ C IR is the parameter with prior distribution p(0). Suppose S {21, 22, ... =NN is dataset consists of samples, where each sample E 2 is drawn from the parameterized distribution p(=]0), i.e. 24 (0) Bayesian inference aims to infer the posterior distribution p(0)S) () of the parameter 0,
p(0) 1 p(z.()
p(0 () J p(O) p(z)))d0
For simplicity, for the given dataset S, we let ps denotes the true posterior distribution p(0)S), and Ps denotes the posterior distribution that inferred by Bayesian inference.
Usually, the denominator of the posterior ps has no closed-form solution, which barriers directly cal- culating the posterior distribution. Thereby, researchers have designed methods to approximate the target posterior. canonical approach is the sampling based Bayesian inference method, Markov chain Monte Carlo (MCMC) (Hastings) 1970).
MCMC infers posterior distribution via first constructs a Markov chain and then draws samples according to the state of the chain. When the target posterior is the stationary distribution of the Markov chain, is proved that the drawn samples will converge to that from the target posterior. However, MCMC methods usually suffer from scalable issues on large-scale datasets.
To this end, stochastic gradient MCMC (SG-MCMC) (Ma al. 2015) leverage mini-batch estima- tion (Robbins & Monro 1951) to enable scalable sampling. In SG-MCMC. the posterior distribution S) can be rewritten as () x (xp(-U(()) where U (0) is the potential function defined as (0) Ex,s log p(2,) ()) p(0). In each sampling step, drawing samples with SG-MCMC
requires one to estimate the potential function U()) with mini-batch data C S as follows,
S S
(())
Σ
logp(z, log
Typical SG-MCMC methods include SGLD and SGHMC. Stochastic gradient Langevin dynamics (SGLD) (Welling & Teh 2011) inserts Gaussian noise to stochastic gradients. In each sampling step, SGLD updates the posterior sample 0, as follows,
0++1 0, (o.(())) + 2
where Win drawn from the standard Gaussian distribution (/ 7) and r/. > is the step size.
To improve the sampling efficiency of SGLD, stochastic gradient Hamiltonian Monte Carlo (SGHMC) (Chen et al., 2014) inserts momentum iz into the posterior sample update as below,
0.+1 = 0 + Ut:
0t+1 = -
n (O.) 22m W,
where W is also drawn from the Gaussian distribution (00, T), q > 0 is the step size, and a E (0, 1) is the momentum factor. The initial momentum term Go is drawn from the Gaussian distribution N (0, no!).
To ensure the drawn samples converge to the targeted posterior, the step size т for both SGLD and SGHMC needs satisfy (Welling & Teh 2011): (1) E 7h oc; and (2) E ni A typical step size schedule is 7): a(b+#) where a, b > O and r e (0.5, 1].
MCMC UNLEARNING ALGORITHM
This section presents the main results of this paper. We first define notion, e-nnwwlegee removal, to assess the machine unlearning performance in Bayesian inference. Then, an MCMC unlearning algorithm is designed with knowledge removal and generalizability guarantees.
3

---

Published as a conference paper at ICLR 2022
4.1 E- C-KNOWLEDGE REMOVAL FOR BAYESIAN INFERENCE
Suppose a client requests to remove her/his data S' C S from the whole training dataset S. An unlearning algorithm A for Bayesian inference aims remove the knowledge learned from the requested data S' from the inferred distribution ps as follows,
Ps = A(ps, S'),
where PS" is named as the processed distribution.
In order meet the regulation requirements, the following notion is defined to quantify the machine unlearning performance in Bayesian inference.
Definition (e-knowledge removal). For the distribution Ps that inferred on dataset S via Bayesian inference and any subset S' C. S, we call algorithu A performs e-knowledge removal, if
KL (lãs-s:) S E,
where PS 5" A(ps.S') 5 is the processed distribution.
Remark 1. Intuitively, smaller indicates the algorithm A has better unlearning performance.
In practice, one usually can only obtain an inferred distribution Ps(-lw), subjects to random seed w. In this case, the overall inferred distribution fs = f (>s(-()p((())))) which suggests that the KL-divergence in Definition can then be upper-bounded as below,
KL llās = KL (-( (.w D (-(1w) = EuPs (0(w) log EnPs (0(w) Enps s (0 (0w
$ f Ew Ps S (0lw) (f)w) log Ps 5 (0 db = (p ((ps-s(lw). s
Motivated by the above inequality, the following knowledge removal estimator is further defined to efficiently estimate the knowledge removal performance in practice.
Definition 2 (knowledge removal estimator). Suppose w1,'.. ..M is M i.id random seed in Bayesian inference. Then, the knowledge removal estimator ê is defined as below,
M S' [Pssss(um))
Σ KL m==1
M
is the processed distribution for the m-th random seed Wm- Remark 2. Our experiments have employed this knowledge removal estimator êM to estimate the E value the E-knowledge removal guarantee. See Section S..2ion(5.2)for details.
where P5 S¹ (+(wm)
Remark 3. This estimator is similar the "Local Forgetting Bound" defined in Golatkar et al. 22200. The difference is that the bound in Golatkar et al. (2020) aims to estimate the random- ness introduced by some "readout functions", while Eas aims quantify the s-knowledge removal guarantee by estimating the difference between the original and processed distributions.
4.2 METHODOLOGY
This section presents the MCMC unlearning algorithm. To make the analysis easier, we assume that one can obtain the exact targeted posterior distribution via MCMC. In other words, for posterior ús that inferred by MCMC, we assume that pss = Ps-
Developing unlearning algorithm for MCMC is challenging, since there is no explicitly parame- terized distribution for knowledge removal analysis. tackle this challenge, we re-formulate the MCMC unlearning problem minimizing the following KL-divergence,
min KL(ps(- - 5) (ps-s:);
where ps is the distribution already learned via MCMC, 8 is the distribution shifting scale, S' the dataset that requested be deleted, and ps- is the targeted posterior that aims obtain. The
4

---

Published as a conference paper at ICLR 2022
idea behinds Eq. I is to approximate the targeted posterior Ps-s- via directly shifting the currently learned distribution ps. In this case, one no longer needs to know the exact implicit distribution parameter to perform machine unlearning, but only the explicit shifting scale 8 is enough.
So far, the MCMC unlearning problem has been converted to an optimization problem defined as Eq. I We then design MCMC unlearning algorithm based on this problem conversion. Let 6g" S denotes any local minimizer Eq. ① and the goal of MCMC unlearning is to calculate the optimal shifting scale 0g" To achieve that goal, we first expand the KL-divergence in Eq. as follows,
(ps( 6) pl s') kL (tppsllpss-- ps- s (-+ +))
Egapps [log p [|S]] log 5') + Be-ps [- log
log p( 6]] (2)
Through Eq. 2 one can find that when removing dataset 5" via optimizing Eq. I1. an additional
term Eg-ps log Sggg((.3 (S + 5) is introduced to force the distribution ps(- 6) approaching the target
posterior S*- This motivate us to follow existing works (Koh & Liang 2017 Guo et al. 2020)
to conduct influence analysis on Eq. I based on the introduced term Eg-ps (
Specifically, we define new function F-s (,, where [].,0]. Suppose there exists a function 8(7) with domain [-1, 0] such that 8(0) O, and (() is a local minimizer of (=, Then, one can let the target shifting scale 0g 5-5" be 8(-1), and approximate it by the first-order approximation: 8(-1) 8(0) 06(0) /r, which means 55 08(0)/OT the following defined MCMC influence function I(S'). Thus, the optimal 05 5" is then approximated as 55 I(S).. For the detailed influence analysis, see Appendix A.1
10, -- (S 8)},
(8((0)/TT. Following standard derivation, one can calculate the first derivative
Definition 3 (MCMC influence function). The MCMC inftuence function of dataset S' C S is defined to be
I(S") (Eo-ps (ologp(0,S))
Σ SES"
(Eoups Vo log ((g((()))))
The MCMC influence function is defined to estimate the influence of data S' on the learned distri- bution Ps. as 85 2 -I(S". The computational cost of the MCMC influence function would be high. An efficient calculation method is given in Appendix B
Finally, based on Definition 3 the MCMC unlearning algorithm is designed as follows.
Algorithm (MCMC unlearning). Suppose one have drawn series of samples {fI.... 00 from the posterior ps via MCMC. Then, MCMC unlearning algorithm removes the learned knowledge of datuset S' from euch drawn sample 0, as follows,
8 + 0 - I(S'), where I(S') is the MCMC influence function for dataset S' C.
Remark 4. Algorithm is equivalent to the the following unlearning process,
P5 (-) Alps, ps(- + I(S)) = ps( (5(--655').
Remark 5. Due to the inherent geometric difference between the distribution functions and Ps-s', it is impossible for Algorithum to directly shift ps exactly recover ps-s- However, the experiments (see Section 5) show that the designed algorithm is good enough for removing learned knowledge from MCMC distributions.
4.3 KNOWLEDGE REMOVAL ANALYSIS
This section studies the e-knowledge removal for the proposed MCMC unlcarning algorithm. We first introduces several assumptions (Assumptions 1-4) for the knowledge removal analysis. Assumption 1. Function - -Ea-pg log + 6) and -aapps logp(z/0 + 8) are Li-isschitz con- tinuous on the support set (8)
The Lipschitzness of -Ep EEa-s log p + 5) can be realized by choosing appropriate prior dis- tribution for 8, for example, let p(0) be Laplace distribution. Besides, the Lipschitzness of -Ep-ps log p(2 + 5) can usually be achieved by setting p(z)0 6) to be a neural network with bounded domain in practice.
5

---

Published as a conference paper at ICLR 2022
There exists neighborhood V2 supp(o) of the origin point such that for any dataset and any sample point 2 E Z, the followings hold:
Assumption 2.
(Smoothness). Vol- Tal-Be-pg log + 6]] and Vol Ea-ps log logp(=10 8)] are Lz-Lipschitz continuous on the space 2/2
(Lipschitz Hessian). Vo log p(6 + 8)1 and 3l--Bo p + 6)] are Ly- Lipschitz continuous on the space V22
Assumption 2 assumes the local smoothness and Hessian Lipschitzness for the involved functions, which are common in literature for analyzing Newton methods (Nesterov & Polyak 2006 Carmon et al. 2018 Zhou et al. 2018).
Assumption 3 (strong convexity). There exists a neighborhood V3 C supp(o) of the origin point such that for any dataset S and any sample point 2 E 2, -Egpps log + 8) and -En-ps log p(z|6 +8) are p-strongly convex on V3.
The influence analysis and the defined MCMC influence function require the Hessian matrices of - -Baups log p(0 + 6) and -Eg-ps log p(=(0 6) to be invertible. Assumption 3 ensures the invert- ibilities of these Hessian matrices.
Assumption
Suppose Assumptions 1-3 hold. Then there exists a sub-neighborhood V V/2 n V/3 of the origin point such that for any dataset S and any real T E [-1.0], the function -Ep-ps p(g + 8|5) T Eaaps p(S + 8) has least one local minimizer falls in V.
(.
Assumption assumes the target optimal solution 0g of Eq. ① exists in the subspace that we interested in, which would make the influence analysis being meaningful.
Under Assumptions 1-4, we prove that the MCMC influence function defined in Definition 3 can rigorously estimate the influence of data on the shifting scale 8.
Theorem 1. Under Assumptions 1-4, have that
S/ N2
85 S'
-II(S'+ +
The proof Theorem
1 presented in Appendix A.I
Based on Theorem
I a knowledge removal guarantee is proved for the MCMC unlearning algorithm.
Theorem 2. Suppose Assumptions 1-4 hold. Then, the MCMC unlearning algorithm A(ps, S') = ps(: + I(S')) performs Eg" -nowledge removal, where
-s'
|S'1
S' Eg" = KL(pss-- -85 -555 "lps' + O
N3
and 8g a local minimizer of the KI-divergence KT(ps(- -)llss-ss)
Proof sketch. We expand KL(ps(- + I(S') (ps-s))) s:) into Taylor series up to 2-th order around the point = 85 S' By applying the first-order optimality condition, the first-order term in the Taylor series becomes O. By leveraging the approximation error given in Theorem [ the second-order term proved to be no larger than the order ([[SS((/N))) The proof is presented in Appendix A.2
Remark 6. As explained in the previous section, Algorithm 7 could learned knowledge from the inferred distribution due to the inherent geometric difference between the distribution ps and ps-s Nevertheless, Theorem Theorem demonstrates that the Algorithm [ean help the KL-divergence in Eq. 7 approach its local minimum.
completely remove the
4.4 GENERALIZATION ANALYSTS
This section studies the impact of the proposed MCMC unlearning algorithm on the generaliza- tion ability of the inferred distribution. The analysis is conducted based on the PAC-Bayes theory (McAllester) 1999, 2003) He et al., 2019), a framework for analyzing the generalization ability of stochastic machine learning models (Mohri et al. 2012 He & Tao 2020).

---

Published as a conference paper at ICLR 2022
Original Data
SOLO
SOHMC
Timo Coel
Razan
SOLD
2G/MC
Visualized results of the GMMs experiments. There four groups of points in the synthetic dataset, where different groups are in different colors. The samples that were generated from the original, processed, and target model via MCMC sampling are colored in black, blue, and red, respectively.
(b) Time costs for pro- cessing single deletion requests via retraining and MCMC unlearning.
Figure I: Experiment results for GMMs.
Specifically, suppose Q is the parameter distribution of a stochastic model. Suppose S is the training dataset. Then, the expected risk R(Q)) and empirical risk (Q) of Q are defined to be
N
1
R(Q) E)(0,=),
(2)
E 0~Q
((0,2s))
0~Q
N
==1
where 0 is the model parameter drawn from the distribution Q and é is loss function ranging in [0, 1]. The difference the expected risk and the empirical risk is the generalization error. Its magnitude characterizes the generalization ability of the stochastic model.
Then, a generalization bound for the distribution processed by Algorithm i proved as below.
Theorem 3.
Suppose Assumptions 1-4 hold. Le 5 denotes the distribution processed by Algo-
rithm Then, for any E (0, 1), with probability at least - 6, the following inequality holds,
Ee-ps [lgg (0) |1]]]]] [I(S")
log 2 + log log N +
R(ps" ) Rs(Ps' 8
2NV -
where [I(S')| S INN)..
The proof is given in Appendix
Corollary 1. Algorithm 7 increases the generalization upper bound in Theorem no larger than the order of O( ((STNN))
Proof. According to Theorem
3 the difference of the generalization upper bound introduced by (OIS//N) 2N-1 0 / This completes the proof. L. =
Algorithm is O(V
|Z(S')|| 2N-1
2N
Remark 7. Corollary 7 indicates that the proposed MCMC unlearning algorithu would not com- promise the generalization ability of the inferred distribution.
EXPERIMENTS
In this section, we empirically verify the effectiveness and efficiency of the proposed MCMC un- learning algorithm on the Gaussian mixture models and Bayesian neural networks.
5.1 EXPERIMENTS FOR GAUSSIAN MIXTURE MODELS
We first visualize the effect of the MCMC unlearning algorithm on a synthetic clustering dataset that consists of 2, 000 examples, where each examples is two-dimensional and is possibly from clusters. The Gaussian mixture models (GMMs) are employed to infer the cluster centers. For the details of the GMMs used in experiments, Appendix C.1
Experiment design. We employ SGLD and SGHMC to infer the GMMs on the clustering dataset. Then, 400 points removed from each of the grey parts and yellow parts, around 40% of the whole

---

Published as a conference paper at ICLR 2022
Table 1:
Experiment results on CIFAR-IO. Different metries are used to evaluate the machine unlearning performance, including the classification errors on the remaining set S,. removed set Sy. and test set Stest, the knowledge removal estimators EM, and the membership inference attack (MIA) accuracy on Sy. Every experiment is repeated 5 times. The results show that the proposed MCMC unlearning algorithm beats baseline methods in almost every experiments settings.
Remove
Method
Em: S, (9)
Frr. Sy
Fr:: Stest
(x 10
MIA Acc. (%)
Retrain
20.45:10.95
46.69.1 1.05
31.80:1..71
0.00:10.00
51 51.85:11.39
3,000
Origin
21.71=0.94
1..91=1.11
31.22:+0.53
4079. 4079.511=2.07
80.1 1:3.87
Examples
IS
20.80
28.71:1:1000
31.77.1.088
4228. 1228.11::11 11::1 .60
72.29:1:2.07
CIFAR- SGLD
Ours
21.56=00.6
11.14::..75
31.76:20.66
4070.59::11.99
69.21
Retrain
18.61=0.90
100.00::0.00
36.25::0.63
0.00::00000
0.00=+0.00
Origin
21.82:20991
19.07 1.26
31,23::0,53
4173.233t 90
80.62:4-.55
Examples
IS
21.17=0.87
54.05=+1.86
03.25=0077
4342,044::166
46,49:1-4.90
Ours
2..73::0.86
73.96:1:4.25
34.11 0.3.1
4151.34::194
26.64:1:7.68
Retrain
20.24=0.37
45.83=11.61
01.80
0.00=00.00
55.34
3,000 Examples
Origin
21.50:10:40
18.83:1:1.46
31.47:0.554
0,00:10.000
82.85:1:1:44
IS
21.61=0.40
28.64+t: 1.23
31.90:00.53
4296.82::222
70.79
CIFAR-10
21.31::0.37
3..75
69.83:1-2.78
SGHMC
18.56:10.38
100.00110.00
36.21110.3
0.00.10.00
0.00:10.00
5,000
Origin
21.61:1:.39
18.91:11.13
31.47:10.52
1233,95:::.73
82.70:1:133
Examples
IS
21.03:10.44
54.20.L 1.48
30,35
4408.05:11.22
44,20.1:.66
Ours
20.54:0.36
69.56:1:4.45
34.67:10.78
4212.63:11.72
29.12:13.94
dataset at all. by our forgetting algorithms. We also trained models on only the remaining set with the same MCMC inference settings to show the targets of the forgetting tasks. For the details of the experiments, see Appendix C
Results analysis. The visualization results presented in Fig. Ta which show that after unlearn- ing, the processed models are close to the target models. Besides, the time costs for processing single data deletion requests are presented in Fig. lb. which shows that the proposed MCMC unlearning algorithm is significantly faster than retraining the whole model. These results demonstrates that the proposed algorithm can effectively and efficiently remove the learned knowledge of specified data.
5.2 EXPERIMENTS FOR BAYESIAN NEURAL NETWORKS
We then apply the MCMC unlearning algorithm to the Bayesian neural networks on the CIFAR-10 (Krizheskyy et al.
CIFAR-10
Retzin
2009) dataset for classification. Analogous experiments also conducted on the Fashion-MNIST (Xiao et al.) 2017) dataset, please see Appendix D for more details.
18
Unteamiig
Dataset & BNN. We divide the training set S of CIFAR-10 into two parts, the removed part Sy and the remained part S,. A certain number of examples are randomly chosen from a single class in the dataset to form the removed training set Sy. The test set is denoted by Sjeat A BNN consists of two con- volutional layers and two fully-connected layers is adopted in the experiments. For more details about the dataset and model architecture, see Appendix D
Figure Time costs for process- ing single data deletion requests on BNNs. smaller time cost implies higher efficiency of the unlearn- ing method.
Baseline method. We compare the proposed MCMC unlearning algorithm with the importance sampling method (IS). Specifically, when data deletion request comes, the importance sampling method will process the request via performing MCMC sampling on the remaining data.
Evaluation metrics. Four kinds of metrics are used to evaluate the performance of machine un- learning: (1) Classification errors. We calculate classification errors the remaining set S,, removed set Sy. and test set Stest for different models. Ideally, after removing data, the three errors of the processed model would approach that of the retrained model. (2) (2))-k e-Knowledge removal guaran- tee. We use the knowledge removal estimator Ê defined Definition 2 to estimate the value in the e-knowledge removal guarantee. A smaller estimation result would imply a better knowl-
8

---

Published as a conference paper at ICLR 2022
(a) The prediction confidences changes for "plane" image. "Plane" also the removed class.
(b) The prediction confidences changes for "plane" image. "Plane" is also the removed class.
Serced peoserple
Reteedd 244 crgge
"perpems
(c) The prediction confidences changes for a "cat" image. "Cat" is not the removed class.
(d) The prediction confidences changes for "ship"
image. "Ship" is not the removed class.
Figure 3: The changes of the prediction confidences for the test set examples of CIFAR-10 along with data removing. The BNN is trained with SGLD and the knowledge removal is conducted with the proposed MCMC unlearning algorithm. The predictions for the true labels are colored in red.
edge removal performance. Calculating éas requires to fix a series of random seeds W1,... ....... WM- series of pre-trained models the random seeds. See Appendix [D.3 for the
To this end, detailed calculation procedures. (3) Membership inference attack (MIA) accuracy. We employ a white-box MIA (Yeom al., 2018) infer whether the examples from the removed subset Sy come from the training set of the model. Intuitively, the attack accuracy would decline after unlearning. Thereby, small attack accuracy implies a strong knowledge removal performance. See Appendix f.r]for more details about the MIA and its calculation procedures. (4) Time costs for unlearning. For different unlearning methods, we estimate the average time usages for processing single data deletion requests. A smaller time cost corresponds to high unlearning efficiency.
Experiment designs. We first train the BNN on the complete training set with SGLD and SGHMC, respectively. Then, the subset Sy is removed iteratively, where a fixed number of data points are removed in each iteration. We also trained models on only the remaining set S, to show the targets of the machine unlearning task. For the details of the experiments, see Appendix D.5]
Results analysis. The experiment results are presented in Table | In all experiments, we observe that the proposed MCMC unlearning algorithm can significantly increase the model error sample set S while making the error on sample sets S, and Stest close to that of the retrained one, Besides, algorithm can also reduce the value in the knowledge removal guarantee and the MIA accuracy on Sy, which further indicates it can indeed remove specified knowledge from the MCMC models. In contrast, the importance sampling method could neither effectively make the classification erros approach the targets, nor achieve stronger e-knowledge removal. We also present the time costs for different unlearning methods in Fig. [ One can found that the MCMC unlearning algorithm is significantly faster than other methods. All these experiment results demonstrate the effectiveness and efficiency of the proposed algorithm.
Finally, we give a case study about the prediction changes on the test set examples to illustrate the effect of the proposed MCMC unlearming algorithm. The results are presented in Fig. where one can observe that as the data removing continues, the prediction confidence of the model on the removed class significantly decreases, while those on other classes remain the same or increase.
CONCLUSION
The right be forgotten imposes considerable compliance burden on AI companies. A company may need to delete the whole model Iearned from massive resources due to request to delete a single sample point. Existing works only appliable to explicit parameterized optimization problem, which however not work for sampling- based Bayesian inference method, i.e., MCMC. In this work, we convert the MCMC unlearning problem to an optimization problem. Then, an MCMC influence function is designed to characterize the influence of data the distribution inferred by MCMC. It then delivers the first MCMC unlearning algorithm. Theoretical analyses show that the proposed algorithm can indeed reduce the learned knowledge, and would not compromise the generalization ability of the inferred distribution. Experiments show that the proposed algorithm can remove the influence of specified samples without compromising the knowledge learned on the remained data.

---

Published as a conference paper at ICLR 2022
ACKNOWLEDGMENTS
FH is supported in part by the Major Science and Technology Innovation 2030 "New Generation SF and DT are supported by Australian Artificial Intelligence" key project (No. IH-180100002, IC- 1901000003,, and LE-200100049, The Research Council Projects FL-177100117,
authors sincerely appreciate Yue Xu and the anonymous ICLR reviewers for their helpful comments.
REFERENCES
Martín Abadi, Ashish Agarwal, Paul Barham, Eugene Brevdo, Zhifeng Chen, Craig Citro, Greg S. Corrado, Andy Davis,Jeffrey Dean, Matthieu Devin, Sanjay Ghemawat, Ian Goodfellow, Andrew Harp, Geoffrey Irving, Michael Isard, Yangqing Jia, Rafal Jozefowicz, Lukasz Kaiser, Manjunath Kudlur, Josh Levenberg, Dandelion Mané, Rajat Monga, Sherry Moore, Derek Murray, Chris Olah, Mike Schuster, Jonathon Shlens, Benoit Steiner, llya Sutskever, Kunal Talwar, Paul Tucker, Vincent Vanhoucke, Vijay Vasudevan, Fernanda Viégas, Oriol Vinyals, Pete Warden, Martin Wat- tenberg. Martin Wicke, Yuan Yu, and Xiaoqiang Zheng. TensorFlow: Large-scale machine learn- ing on heterogeneous systems, 2015.
Martin Abadi, Andy Chu, Ian Goodfellow, Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC conference on computer and communications security, pp. 308-318, 2016.
Naman Agarwal, Brian Bullins, and Elad Hazan. Second-order stochastic optimization for machine learning in linear time. The Journal of Machine Learning Research, (8(1):41484444 2017.
Sungjin Ahn, Anoop Korattikara, and Max Welling. Bayesian posterior sampling via stochastic gradient Fisher scoring. In International Conference on Machine Learning, pp. 1771-1778, 2012.
Thomas Baumhauer, Pascal Schöttle, and Matthias Zeppelzauer. Machine unlcarning: Linear filtra- tion for logit-based classifiers. arXiv preprint arXiv:2002.027:30 2020.
Lucas Bourtoule, Varun Chandrasekaran, Christopher A Choquette-Choo, Hengrui Jia, Adelin Travers, Baiwu Zhang, David Lie, and Nicolas Papernot. Machine unlearning. In 2021 IEEE Symposium on Security and Privacy (SP), pp. 141-159. IEEE, 2021.
Jonathan Brophy and Daniel Lowd. Machine unlearning for random forests. In International Con- ference on Machine Learning, pp. 1092-1104 PMLR, 2021.
Yinzhi Cao and Junfeng Yang. Towards making systems forget with machine unlearning. 2015 IEEE Symposiun Security and Privacy, pp. 463-480. IEEE, 2015.
Yair Carmon, John Duchi, Oliver Hinder, and Aaron Sidford. Accelerated methods for nonconvex optimization. SIAM Journal Optimization, 28(2):151-1172, 2018.
Tianqi Chen, Emily Fox, and Carlos Guestrin. Stochastic gradient Hamiltonian Monte Carlo. In International Conference Machine Learning, volume 32 of Proceedings of Machine Learning Research, pp. 1683-1691, PMLR, 2014.
Dennis Cook and Sanford Weisberg, Residuals and Influence Regression. New York: Chapman and Hall, 1982.
Nan Ding, Youhan Fang, Ryan Babbush, Changyou Chen, Robert D Skeel, and Hartmut Neven. Bayesian sampling using stochastic gradient Thermostats. In Advances in Neural Information Processing Systems, volume 27. Curran Associates, Inc., 2014.
Simon Duane, Anthony D Kennedy, Brian J Pendleton, and Duncan Roweth. Hybrid Monte Carlo. Physics letters B, 195(2):21-22)) 222, 1987.
Sanjam Garg. Shafi Goldwasser, and Prashant Nalini Vasudevan. Formalizing data deletion in the context of the right to forgotten. Advances in Eoypology-EUROCHE 2020, 12106:373, 2020.
10

---

Published as a conference paper at ICLR 2022
Stuart Geman and Donald Geman. Stochastic relaxation, Gibbs distributions, and the Bayesian restoration of images. IEEE Transactions on Pattern Analysis and Machine Intelligence, (6): 721-741, 1984.
Edward George and Robert E McCulloch. Variable selection via Gibbs sampling. Journal of the American Statistical Association, 88(423):881-88) 1-889, 1993.
Antonio Ginart, Melody Guan, Gregory Valiant, and James Y Zou. Making Al forget you: Data deletion in machine learning. In Advances in Neural Information Processing Systems, volume 32.
Curran Associates, Inc., 2019.
Aditya Golatkar, Alessandro Achille, and Stefano Soatto. Eternal sunshine of the spotless net: Selective forgetting deep networks. Proceedings the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 9304-9312, 2020.
Aditya Golatkar, Alessandro Achille, Avinash Ravichandran, Marzia Polito, and Stefano Soatto. Mixed-privacy forgetting in deep networks. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 192-801,24 2021.
Jinu Gong, Osvaldo Simeone, and Joonhyuk Kang. Bayesian variational federated learning and unlearning in decentralized networks. arXiv preprint arXiv:210.003844 2021.
Chuan Guo, Tom Goldstein, Awni Hannun, and Laurens Van Der Maaten. Certified data removal from machine learning models. In International Conference Machine Learning, pp. 3832- 3842. PMLR, 2020.
W Keith Hastings. Monte Carlo Sampling Methods Using Markov Chains and Their Applications. 1970.
Fengxiang He and Dacheng Tao. Recent advances in deep learning theory. arXiv preprint arXiv:2012.10931, 2020.
Fengxiang He, Tongliang Liu, and Dacheng Tao. Control batch size and learning rate to generalize well: Theoretical and empirical evidence. In Advances in Neural Information Processing Systems, pp. 1143-1152 2019.
Peter Huber. Robust Statistics, volume 523. John Wiley & Sons, 2004.
Zachary Izzo, Mary Anne Smart, Kamalika Chaudhuri, and James Zou. Approximate data dele- tion from machine learning models. In International Conference on Artificial Intelligence and Statistics, pp. 2008-2016. PMLR, 2021.
Pang Wei Koh and Percy Liang. Understanding black-box predictions via influence functions. In International Conference on Machine Learning, pp. 1885-1894, 2017.
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-basse learning applied to document recognition. Proceedings of the IEEE, 86(11):2278-2322 1998.
Tiffany Li, Eduard Fosch Villaronga, and Peter Kieseherg. Humans forget, machines remember: Artificial intelligence and the right to be forgotten. Computer Law & Security Review, 34(2):304, 2018.
Yi-An Ma, Tianqi Chen, and Emily Fox. A complete recipe for stochastic gradient MCMC. In Advances in Neural Information Processing Systems, volume 28. Curran Associates, Inc., 2015.
David A McAllester, Some PAC-Bayesian theorems. In Proceedings of the Annual Conference on Computational Learning Theory, pp. 230-234, 1998.
David A McAllester. PAC-Bayesian model averaging. In Proceedings of the Annual Conference on Computational Learning Theory, pp. 164-170, 1999.

---

Published as a conference paper at ICLR 2022
David A McAllester. PAC-Bayesian stochastic model selection. Machine Learning, 51(1):5-21, 2003.
Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of machine learning- MIT press, 2012.
Radford M Neal. Slice sampling. The Annals of Statistics, 31(3):75--76,, 2003.
Radford M Neal et al. MCMC using Hamiltonian dynamics. Handbook of Markov Chain Monte Carlo, 2(11):2, 2011.
Yurii Nesterov and Boris T Polyak. Cubic regularization of Newton method and its global perfor- mance. Mathematical Programming, (08(1):177-200) 2006.
Quoc Phong Nguyen, Bryan Kian Hsiang Low, and Patrick Jaillet. Variational Bayesian unlearning. Advances in Neural Information Processing Systems, 33, 2020.
Adam Paszke, Sam Gross, Soumith Chintala, Gregory Chanan, Edward Yang, Zachary DeVito, Zeming Lin, Alban Desmaison, Luca Antiga, and Adam Lerer. Automatic differentiation in PyTorch. In NIPS-W W 2017.
Sam Patterson and Yee Whye Tch. Stochastic gradient Riemannian Langevin Dynamics on the probability simplex. In Advances in Neural Information Processing Systems, volume 26. Curran Associates, Inc., 2013.
Herbert Robbins and Sutton Monro. A stochastic approximation method. The Annals of Mathemat- ical Statistics, pp. 400-407, 1951.
Reza Shokri, Marco Stronati, Congzheng Song, and Vitaly Shmatikov. Membership inference tacks against machine learning models. In 2017 IEEE Symposium on Security and Privacy (SP), pp. 3-18. IEEE, 2017.
Enayat Ullah, Tung Mai, Anup Rao, Ryan A. Rossi, and Raman Arora. Machine unlearning via algorithmic stability. In Proceedings of Thirty Fourth Conference on Learning Theory, volume 134 of Proceedings of Machine Learning Research, pp. 4126-4142 PMLR, 2021.
Stephen G Walker. Sampling the dirichlet mixture model with slices. Communications in Statis- fics fics-Simllation and Computation&o, 36(1):45-555 54, 2007.
Chaoyue Wang, Chang Xu, and Dacheng Tao. Self-supervised pose adaptation for cross-domain image animation. IEEE Transactions on Artificial Intelligence, 1(1):34-46, 2020. doi: 10.1109/
TAI2200.3031581.
Qing Wang, Sanjeev R Kulkarni, and Sergio Verdú. Divergence estimation for multidimensional densities via k-nearest-neighhor distances. IEEE Transactions Information Theory, 55(5): 2392-2405, 2009.
Max Welling and Yee W Teh. Bayesian learning via stochastic gradient Langevin dynamics. In International Conference on Machine Learning, pp. 681-688, 2011.
Han Xiao, Kashif Rasul, and Roland Vollgraf. marking machine learning algorithms, 2017.
novel image dataset for bench-
Samuel Yeom, Irene Giacomelli, Matt Fredrikson, and Somesh Jha. Privacy risk in machine learn- ing: Analyzing the connection to overfitting. In 2018 IEEE 31st Computer Security Foundations Symposium (CSF), pp. 268-282. IEEE, 2018.
Ruqi Zhang, Chunyuan Li, Jianyi Zhang, Changyou Chen, and Andrew Gordon Wilson. Cyclical stochastic gradient MCMC for Bayesian deep learning. In International Conference on Learning Representations, 2020a.
Youjian Zhang, Chaoyue Wang, and Dacheng Tao. Video frame interpolation without temporal priors. Advances Neural Information Processing Systems, volume 33, pp. 13308-13318, 2020b.
Dongruo Zhou, Pan Xu, and Quanquan Gu. Stochastic variance-reduced cubic regularized newton methods. In International Conference on Machine Learning, pp. 5990-5999, PMLR, 2018
12

---

Published as a conference paper at ICLR 2022
A PROOFS
This section collects all the proofs in this paper. To avoid technicalities, we assume that all functions are differentiable throughout this paper. Furthermore, the order of differentiation and integration is assumed to be interchangeable.
For simplicity, we denote that
h(6, 2) Eamps logp(= 6),
[(6) Egrus log 6),
F)),S) = Eees h(6,2) + f(0) = Exes Bewps logp(z|0 + 8) Eg-us log p( + 6).
A.1 PROOF OF THEOREM
To prove Theorem I we first define the following function,
= + h(6, 2).
Σ
=ES
where = E [-1,0].
Under Assumption it can be shown that F-s (=, is strongly convex the space V3 defined in Assumption 3
Lemma 1. Suppose 3 Then, for any T E [-1,0], (-, is strongly comve on the space V3.
Proof of Lemmal 7
We rearrange the function F-st.r as follows,
= F:(.(( - +1) (1+T) Σ h(6,2).
ZES"
S') is strongly convex V3. Since [-1, 0j. we have that 1+r 2 0. Thus, (1 + r) > h(6, z) either strongly convex on V3 or equal to zero. Therefore, F- (8) is strongly convex on Vg3
Apparently, F(,, S')
The proof is completed.
We then prove that when Assumption holdds there exists continuous mapping that "connects" the origin point O Rd and the target shifting scale 5-55.
Lemma 2. Suppose Assumption 4 holds. Then, there exists a continuous function å [-1,0] + V such that for any [),,0). 8(T) is the global minimizer the function F-s (ō, space V.
Proof of Lemma By applying Lemma and Assumption 4 we have that the global minimizer of function F F-s (7, S) uniquely exists in V. Therefore, one can define the mapping below,
8(T) arg min (-5,, seV
where E [-1,0].
We then prove the continuity of 8. Notice that 8(T) is the solution of the following equation,
V&F(5,S) Σ Vah(6,)) 0.
Since (-S),-(5,S) is strongly convex, thus its Hessian matrix (3==)),((()) is invertible. Combining with the implicit function theorem, we have that is continuous on the interval [-1,0].
The proof is completed.
13

---

Published as a conference paper at ICLR 2022
When takes and 11, the function 5(T) becomes 0 R and 65% respectively. Therefore, 65" can be expanded into Taylor series as follows,
08(0) 1 88(()) 855 8{-1) = Ôr 2 0T
(4)
where { E [-1, 1 (2 is the Lagrange form of the remainder. 8r
We prove that the Lagrange remainder term becomes negligible as the training set size N goes to infinity. To do this, we first prove the following Lemma.
Lemma 3. Suppose Assumptions 1 hold. The mapping å is as defined Lemma Then, we have that
0б(T) -VFFF((())
Σ Vah((()),
Ür
#ES'
for any T [-1,0]. p
1l2 - O(IS
aB(r) based on Eq. (3) the proof of Lemma &
Proof. We first calculate
Calculate the derivatives
of the both sides of Eq.
3
with respect we have that
0δ(T)
05(T)
V)
Vsh(((r), + =ES
Σ (8h(((T),
= 0.
(5)
dT
ZES'
According to Lemma
F-st, (6, 5) strongly convex on V. Thus, the following Hessian matrix
F V3F-s, = (( + vgn(((T),
sES!
is positive definite, hence invertible. Combining with Eq. 5 we have that
0б(T)
() +T Σ V)
[o)(((r))
(6)
FES'
ZES
We then upper bound the norm of an(r) Ör
Based on Eq.
6). we have that
(ō(T)) Ør 2
< (
Vgh(6(T),2)
Σ Vob(6(T).
N
BES
BES
We first consider the first term of the right-hand side of Eq. 7 By Assumption both f(0) and 10 z) are y-strongly convex the space V supp(o). Thus, we have that
(5r((()) N
V)h(((7),))
N
VM(((T), m)) + N
V))(((T)) T Σ Vzh(((7), N
N
ZES'
Σ
Σ
N
=ES-8'
N S' 4 I.
Let Amin denotes the smallest eigenvalue of the following matrix
S)= T Σ
N V31(6(T),2)) #ES
N
14

---

Published as a conference paper at ICLR 2022
Then, the Eq. (8 implies that Amin
N-18 μ.. Hence, have the following.
1( (2r(0
)
N
E Vgh(0(T).2) N
0(1).
(9)
Amin
(N 1'
We then upper bound the second term of the right-hand hand side of Eq. we have that
7 By applying Assumption
!
Ia 18
(18))
Voh(6(T).2)
2)
(10)
N
N
RES'
2
Finally, inserting eqs.
10
into Eq.
we eventually have that
(δ(TT)
|
SS
- 0(1)
O
= O
θr
N
N
The proof is completed.
Then, the following Lemma is obtained based on Lemma] which demonstrates the strictness the approximation in Eq. 4
Lemma 4. Suppose Assumptions 1-4 hold. The induced mapping 8 is as defined in Lemma Then, for any T E [-1,0], we have that 828(()
Gr2 1 < ((
Proof. We first calculate 88(() based Eq. 3 Similar to the proof of Lemma calculate the D-2
second-order derivatives of the both sides of Eq.
with respect to T and have that
028(7)
V2h(((T),2) + v3r(0(1))
B(), + A(7) +
072
06(T)
②²((T) 0,
+2. Σ V)h(6(T),))
Σ
B(T,2) + Σ Vjh(((T),2)
Ør
Or2
BES'
ZES'
which means
028(7)
N
V)F(((T),
V Σ ((((T),)
0r2
N
N
1=1
2ES
B(T, 2;) + T
2 B(T A(T)
Σ Vjh(B(T), 2)
08(T)
N
N
N
Or
ZE5
(11)
in which the invertibility of ΣN V3F(((T), + ExES V)h(6(T),))) is guaranteed by Eq. A(r), B(T, E x x1 and for = 1,... K, we have the following,
A(T), = 08(T)
(f(((T))
08(T)
V
(12)
dr
06;
Or
08(7) T
(ah(6(T),))
06(T)
B(T,2);
v
(13)
0t
06,
15

---

Published as a conference paper at ICLR 2022
(br) d+
We then upper bound the norm
Based on Eq. 11
we have that
(P)(T)
Ör
2
N
$
VjF((((),
+ T Σ Vgh(5(T),2)
N
ZES"
85(T)
[B(T 24) + Σ
[B(T, + [|A(T)]l2 +
Vgh(((T),
N
Or
ZES"
(14)
08(T)
B(T, 22 + Σ
+ + V2h(((T),2)
N
δr
zeSt
ZES!
(15)
where Eq. (15) is obtained by inserting Eq. (9) (in the proof of Lemma] 3 into Eq. (4 Thus, the remaining task is upper bound the norms of A(r), B(T, 2) and V Eves h(5(T)) 2) aa(r)
We first upper bound [| Applying Lemma we have that || 06(r)
1|2 S O(IS") Applying
8r
the Lipschitz Hessian condition Assumption we have that V @f( a real constant. Therefore, we have that
2 is also bounded by
06.
(8((((T)) 06,
08(T) θT
2
|S'
|S
||A())]l2 - Σ v3
$ Σ 0(1)
O
(16)
N2
N2
2
For B(T,2), we similarly have that
[1112)
[ 2)112 50
(17)
N²
To upper bound the norm of Exes' Vzh(((T),,) have that
08(7) 0r
we apply Lemma
Assumption
2 and
08(T)
( Ør
|S/
Σ xE
v2h(0(T),2)
V)h(6(T), 2)
o
(18)
δr
N
=ES'
Inserting eqs. (6)..
[1 and 18 into Eq.
15
eventually have that
028(7)
S
SS'
S 2
(187P
)
||S'1
0
o
+
O
+
+ 2
O
=0
N2
N2
N2
N22
The proof is completed.
Finally, combining all the results, we prove Theorem
Proof of Theorem 7 The proof is completed by applying Lemmas and 4 into Eq.
44
16

---

Published as a conference paper at ICLR 2022
A.2 PROOF OF THEOREM 2
This section presents the proof of Theorem 2
Proof of Theorem 2
By expanding the KL-divergence ((((ssss++(()))lsssss== into Taylor series
around the local region of 5 = 6g" we have
KL(ps(- + [(s
= KL(ps(- - 53 llps + (I(S") + 0g V- - E)lps--s)) (I((') + +5z")
= KL(ps(- - 55 s') - (I(S") + 63 V F(5.S) - - ((E (I((S) + 65 5))
2ES!
(19)
where the first-order term equals according the first-order optimal condition. we further have
By applying
Theorem and Assumption
(I(S") + 55 ST V F(C,S)- SES"
ME, 2) (I(S") + +55
|||
< V/ F(E, 8) - Σ h(s, 2)
||-(5') + +0g" 5555
ZES
|15113 N2
SS'1
0 ((N | + 1)L2 diam
$ O
(20)
N3
By combining eqs. and 20 the proof is completed.
A.3 PROOF OF THEOREM
This section presents the proof of Theorem
We derive generalization bound for the proposed algorithm under the PAC-Bayesian framework [McAllester] 1998 1999: 2003). The framework can provide guarantees for randomized predictors (e.g,, the Bayesian predictors).
Specifically, let Q distribution the parameter space θ P denotes the prior distribution over the parameter space θ Then, the expected risks R(Q) bounded in terms of the empirical risk S) and KL-divergence (L]( by the following result from PAC-Bayes. Lemma 5 (cf. McAllester (2003), Theorem 1). For any real ō E (0, 1), with probability at least - 8, we have the following inequality for all distributions Q:
[L[Q|] P) + log 1/ + log N +
R(Q) < R(Q,S) +
(21)
2N
Based on Lemma we prove the generalization bounds in Theorem 3
Let the prior distribution P be Laplace distribution lap(0, 15 p I(S')) be the distribution processed by the MCMC unlearning algorithm. Then, one can calculate the KL-divergence KL(P3" (IP) (PP) as follows (where we assume that θ = IRd),
proof of Theorem 3
KL [PP)
log
Ps
(0)
Ps
(0)dd
p(0)
ps (0)
log
p(0 - -I(("))) (s())d
[log (0) + 110 I(S') [I, + log 2) ps (0)d0
Eg-ps log ps (0) + Eg-ps |0|| |[((S)) | log 2.
(22)
17

---

Published as a conference paper at ICLR 2022
bound. into Eq.
Inserting Eq.
22
(1 in Lemma 5
then obtain the PAC-Bayesian generalization
Eventually, by applying Lemma have that 5
The proof is completed.
B EFFICIENT CALCULATION OF MCMC INFLUENCE FUNCTION
major computing burden in the MCMC unlearning algorithm is calculating the product H where H is the Hessian matrix of some vector- vector-valued function f(z) and is constant vector. When the function (() of high dimension, the calculation would have a considerably high computa- tional cost. We follow Agarwal al. (2017) Koh & Liang (2017) apply divide-and-conquer strategy to address the issuc. This strategy relies on calculating the Hessian-vector product Hu.
Hessian-vector product (HVP). We first discuss how to efficiently calculate Hv. The calculation of Hv can be decomposed into two steps: (1) calculate af(z) and then (2) calculate 0
(ff(z) )
dz
de
dx
worth noting that (f(x)) [f(()) On -V) is a scalar value. Calculating its gradient 8
Ox E 1xd and v E Rdx1, where > 0 is the dimension of data. Thus, [f(()) Ur - has a very low computational
cost on platform PyTorch (Paszke et 2017) or TensorFlow (Abadi et al. 2015).
Calculating H When the norm ||||| & 1. the matrix H-1 can be expanded by the Taylor's series as H -i Hy. Define that H Ei H)' Then, we have the following recursive equation,
- (1 1|M
Agarwal al. (2117) prove that when j oo, have B|H + 1 H Therefore, employ H to approximate H H-'c.
Moreover, to secure the condition || < stands, we scale H to cHl by scale c E Rt, such that ||cH|| Then, approximate (c/1)-1, Eventually, have that H-1 c(cH)- We can plug it to the applicable equations above.
C EXPERIMENTS DETAILS FOR GAUSSIAN MIXTURE MODELS
This section provides the additional experiments details for the Gaussian mixture models.
C.I GAUSSIAN MIXTURE MODELS
We employ Gaussian mixture models (GMMs) to infer the cluster centers on the synthetic dataset. A GMM assumes that each example is drawn from K Gaussian distributions centered at Mi; PAK. respectively. Then, the hierarchical structure of GMM is as follows: (1) draw a clustering center from the uniform distribution over ( Pex Ji and (2) sample 2; from Gaussian distribution centering at Pe. That is,
14 _N.00
1 K K'
1 (K
C categorical
7: ~ N(Hae T),
where 1 < K. pa Rd, c; {1.... .K) Zj e Rdd and the hyperparameter o e IR is the prior standard deviation. In our experiments, the factor K is set as 4, and the prior standard deviation a is set 1.
C.2 EXPERIMENTS DETAILS
The experiments for GMM have main phases:
18

---

Published as a conference paper at ICLR 2022
Training phase. Every GMM is trained for 4, 000 iterations. The batch size is set as 64. For both SGLD and SGHMC, the learning rate schedule is set as 4- -.5000 /N, where is the training iteration step and N is the number of the training set size. Besides, the momentum factor of SGHMC is set as 0.9.
Unlearning phase. We remove batch of 4 datums each time. When calculating the inversed- Hessian-vector product H in the influence functions (see Section B). the recursive calculation number j as 32, and the scaling factor is set 1/N', where N the number of the current remained training examples. Notice that N' will gradually decrease as the forgetting process con- tinues. Moreover, we employ the Monte Carlo method to calculate the expectations the MCMC influence function. Specifically, we repeatedly draw sample 0 for 5 times, calculate the matrix or vector the MCMC influence function, and average the results to approach the expectations.
D EXPERIMENTS DETAILS FOR BAYESIAN NEURAL NETWORKS
This section provides the additional experiments details for Bayesian neural networks.
D.1 DATASETS
We employ two image datasets, Fashion-MNIST (Xiao et al. 2017) and CIFAR-10 (Krizhevsky al. 2009), our experiments. Fashion-MNIST consists of grey-scale images from 10 classes, where each class contains 6, 000 training examples and 1, 000 test examples. Besides, CIFAR-10 consists of color images from 10 classes, where each class contains 5, 000 training examples and 1, 000 test examples. No data augmentation is used in the experiments.
Furthermore, worth noting that the models used for MNNIST and CIFAR-10 are first pretrained on MNIST (LeCun et al. 1998) and CIFAR-100 (Krizhevsky et al. 2009), respectively. Please see Appendices
D.3 and D.5 for more details.
D.2 BAYESIAN NEURAL NETWORKS
This section introduces the model architectures used in our experiments and the implementation details for training BNNs.
D.2.1 MODEL ARCHITECTURES
LeNet (LeCun et al. 1998) architecture that consists of two convo- lutional layers followed by three fully-connected layers. The convolutional layers use x 5 convo- lutions, each followed by 2 x 2 max-pooling layer and ReLU activation function. The channel numbers of the two convolutional layers are and 16, respectively. Besides, each fully-connected layer is also followed by ReLU activation function, while the hidden layer channels are 120 and 84, respectively.
For Fashion-MNIST.
network architecture that consists of two convolutional layers followed by two fully-connected layers. Each convolutional layer uses 5 x convolution, with channel number of 64, followed by 2 max-pooling layer and ReLU acti- vation function. Besides, each fully-connected layer is also followed by ReLU activation function, while the hidden layer channels are 384.
for CIFAR-10, we follow Abadi al. 2016)
D.2.2 MODEL TRAINING
In all the experiments, use isotropic Gaussian distribution (O o as the prior of the BNNs, in which the hyperparameter do is set as 0.
Traditional SG-MCMC methods would inject random noise to BNNs during training. However, it is found that the noise injection in the early training iterations hurts the convergence of BNNs (hhang et al. 2020ah. To alleviate such problem, follow Zhang al. (2020a) to first avoid the noise injection in the early training iterations and then resume SG-MCMC as usual in the rest of the training.
19

---

Published as a conference paper at ICLR 2022
D.3 ESTIMATING THE E- KNOWLEDGE REMOVAL GUARANTEE
We use the knowledge removal estimator As defined in Definition 2 to estimate the value in the e- knowledge removal guarantee. According the definition of éM. calculating it requires first fixing a series of random seeds, and then calculating the KI-divergence between two MCMC distributions.
For the random seeds, we employ the pretraining technique (Golatkar al. 2020 to fix them. Specifically, for the experiments on Fashion-MNISS all the models used are first pre-trained on MNIST; for the experiments on CIFAR-IO, all the models used first pre-trained on CIFAR-I00.
Besides, for the KL-divergence calculation, we follow WWan et al. (2009) to estimate the KL- divergence in a k-NN manner. in which 100 samples are drawn from each of the processed and retrained distributions for the estimation.
D.4 MEMBERSHIP INFERENCE ATTACK
Membership inference attack (MIA) (Shokri et al. 2017 Yeom et al. 2018) is a privacy attack that aims infer whether given example in the training set based the output of the model. In our experiments, we adopt a white-box threshold- based MIA (Yoom et al.] 2018) to assess the unlearning performance. The calculation consists of two steps: (1) learn optimal MIA threshold on the remained training set S, and the test set Stest: and (2) calculate MIA accuracy with the learned threshold on the removed training set Sy.
Learn the optimal threshold. Suppose the "to-be-inferred" example (x, y) comes from S, and Stest with equal probabilities. Then, the attack accuracy of MIA with threshold p E [0, 1] on the model fe is calculated as follows.
Eie.nEE.. 1[fo(T), 2 p.
Ex.)es 1[fo()) < pl
=
Acc(p, Sr, Stest) = 0.5 x
|S,1
|Steal
where fo(r) the output confidence for label y and 1|-] is the indicator function. Then, the optimal threshold Poptim is obtained via calculating the maximizer of the above attack accuracy, i.e.,
Poptim = arg max Acc(p, S,, Stest).
Calculate MIA accuracy on Sy. With the optimal threshold poptim that learned on S, and Stests the MIA accuracy on the removed set S is calculated as follows,
Poo(pop 8z) E(a,)es, [[fo(T) 2 Poptiml
SSy
Intuitively, after removing the knowledge learned from the removed subset Sy, the MIA accuracy Aco(poptim: Sy) would decline. As a result, a low MIA accuracy on the removed subset Sy would imply strong knowledge removal performance.
D.5 EXPERIMENTS DETAILS
This section provides the omitted experiment details, including the settings of the hyperparameters and the procedures of the experiments.
D.5.1 EXPERIMENTS ON FASHION-MNIST
Pretraining phase. In every experiment, we pretrain a non-Bayesian model on MNIST via SGD for 2, 000 iterations, with a batch size of 128, a learning rate of 0.1/N, where N is the training set size, and a momentum factor of 0.9.
Training phase. Every BNN is trained for 10, 000 iterations. The batch size is set 128. For both SGLD and SGHMC, we first train the model without noise injection the first 1, 000 iterations. In this stage, the learning rate is fixed to 0.01/N. Then, we resume the traditional SGLD and SGHMC in the rest of the training. In this stage, the learning rate schedule is set as 0.01 .t -oe.-tt0.0000 005500 /N, where t is the training iteration step. Besides, the momentum factor of SGHMC is set as 0.9.
20

---

Published as a conference paper at ICLR 2022
Unlearning phase. We remove batch of 64 datums each time.
product H ''y in the MCMC influence function (sec Appendix (B), the recursive calculation number is set 64, the scaling factor с set as 0.05/N', in which N' is the number of the current remained training examples. Notice that N' will gradually decrease as the forgetting process continues. Besides, employ the Monte Carlo method to calculate the expectations in the MCMC influence function. Specifically, each time we draw a sample 0 via the MCMC sampler and calculate the matrix and vector in the MCMC influence function based on 0 to estimate the desired expectation.
For the MCMC unlcarning algorithm. when calculating the inverse--Hessian-
Besides, for the importance sampling method, process each data deletion request by performing MCMC sampling for 1, 000 times on the remaining data.
D.5.2 EXPERIMENTS ON CIFAR-10
Pretraining phase. In every experiment, we pretrain a non-Bayesian model on CIFAR-100 via SGD for 10, 000 iterations, with a batch size of 128, learning rate of 0.1/N, where N is the training set size, and momentum factor of 0.9.
Training phase. Every BNN is trained for 20, 000 iterations. The batch size is set 128. For both SGLD and SGHMC, we first train the model without noise injection in the first 5, 000 iterations. In this stage, the learning rate is fixed to 0.01/N. Then, we resumee the traditional SGLD and SGHMC in the rest of the training. In this stage, the learning rate schedule is set as 0.01 t -00.000 /N, where t the training iteration step. Besides, the momentum factor of SGHMC is set as 0.9.
Unlearning phase. We remove batch of 64 datums each time.
For the MCMC unlearning algorithm, When calculating the unversed-Hessian- Hessian- vectoor product H H in the MCMC influence functions (see Appendix B). the recursive calculation number j is set as 64, the scaling factors is set as 0.08/N', where N is the number of the current remained training examples. Notice that N' will gradually decrease as the forgetting process continues. Besides, employ the Monte Carlo method to calculate the expectations in the MCMC influence function. Specifically, each time draw sample & via the MCMC sampler and calculate the matrix and vector the MCMC influence function based on 8 to estimate the desired expectation.
Besides. for the importance sampling method, process each data deletion request by performing MCMC sampling for 1, 000 times on the remaining data.
D.6 EXPERIMENT RESULTS ON FASHION-MEN MNIST
This section presents all the experiment results BNNs on the Pashion-MNIST dataset. The evalu- ations of unlearning performance are shown as Table while the time costs for unlearning is shown in Fig. The results further justify the effectiveness of the proposed algorithm.
Fashion-MNIST
Untearning Time (8)
Retrain
IS
40
Ours
20
SGLD
SGHMC
Figure 4: Time costs for processing single data deletion requests on BNNs.
D.7 EVALUATION ON PREDICTION DIFFERENCES
In this section, adopt the metric named prediction differences to better quantify the difference between the retrained and processed models. For two BNNs p1(.) and pz(.) learned by MCMC, their prediction difference given dataset S is defined as Ee, rpp. E0s-p2 p2 E(ryyes ll,e, (I.)
21

---

Published as a conference paper at ICLR 2022
Table Experiment results on Fashion-MNIST. Different metrics are used evaluate the machine unlearning performance, including the classification errors on the remaining set Sr. removed set Sy, and test set Stest, the knowledge removal estimators EM, and the membership inference attack (MIA) accuracy Sy. Every experiment is repeated 5 times.
Remove
Method
Err. on S. (%)
Err. on Sy (%)
Frr. on Steet (%)
EM (x 10")
MIA Acc. (%)
Retrain
12.81:10::9
37.62:10.76
15.63-10.59
0.00
16.12:15579
4,000 Examples
Origin
13.49:#0.81
17.39:20.41
14.73:10.80
351 15:0-0444998
10.86:28.00
Fashion MNIST
12.67::0.70
34.93-22.16
15.30=00.7
365.97:3:.04
13.97=11.37
Ours
12.93:10.72
35.84:1:.88
15.57
350.30
10.36.1
Retrain
11.21:0.57
100.00=00.00
21.05=0.449
0.00:00.00
0.00=10.00
SGLD
6,000 Examples
Origin
13.38:10.85
17,08 10,,1
14.73:10.80
364.63:1
1.29
IS
11.10:10.66
57.30
19.90:10.87
378.11:: 4.5
4.52.42.31
Ours
11.39:10.88
98.13:1..61
20.59:10.99
362.55:1:247
1.25:10.67
Retrain
14.57:11.11
38.
38.90#3:42
17.34#1111
0.00#00.00
5.58
4,000 Examples
Origin
15.21::1.30
17.58 1.68
16.40::1.17
362,60.18.24
12.03-1
Fashion MNITT
IS
14.27:11.22
36.54
16.97-11.16
375.62.1
13.12
Oars
14.56:t:1.24
2..4
17.29:11.08
361.72:+7.87
11,28 13.25
Retrain
12.99:1:094
100.00-10.00
22.61
0.00
0.00:10.00
SGHMC
6,000
Origin
15.16t11.31
17.27 1.80
16.40=1.17 1.
366 366.98:6.24
1..07
Examples
12.52:::1.04
87.48=7.22
20.94:11444
382.34:4:448
4.20=11884
Ours
12193::1.116
9.02
22.39-10.85
364.99::6.00
1.59
Table 3: The results of prediction differences on CIFAR-10 and Fashion-MNIST. The prediction differences between the retrained model and the processed model are calculated on the remaining set S,,, removed set Sj, and test set Stest, respectively.
Pred. S,
diff. on S
Pred. diff. Stea
Origin IS Ours
0.50:10.02
3,000 Examples
0.18=00.00
0,37=00.01
0,20=00.01
CIFAR-10
0.17-:0.0
0.35:t0.02
0.19:1:0.01
SGLD
5,000
Origin
0.23++0.00
142::0.02
0,37::0.01
0.21-20.00
0.92::0.03
0.29:10.01
Examples
Ours
0.19:10.00
0.67-1:0.05
0.25:10.01
Origin
0.19:20.00
0,50+t0.01
0,22+t0.00
0.19:10.00
0.38100.01
0.21110.00
Examples
CIFAR-ID
Ours
0.18:10.00
0.35
0.20110.01
SGHMC
5,000
Origin
0.23:10.00
1.44:00002
0.37.10.000
Examples
IS
0.22-1:0000
0,94:10.02
0.31-1.0.00
Ours
0.20-10.00
0.73-10.05
Origin
0.13-20.02
0.37-40.02
0.15:40.02
4,000
IS
0.11=20.02
0,22+:0.01
0.12:+-002
Fashion MNIST
Examples
Ours
0.11:10.02
0.21:10.02
0.12:1:0002
Origin
0.17:0001
145::0.02
0,30+:0.01
SGLD
6,000
0.13:10.01
0.56:1:000
0.18:10001
Examples
Ours
0.13:10.01
0.33
0.15
Origin
0.15::0003
0,43:10003
0.18+F-003
4,000
0.14:10.03
0.26
0.15
Fashion MNIST
Examples
Ours
0.14:10.03
0.26:1.0.05
0.15:10.03
Origin
0.18100.02
1.44
0.30.10.02
SGHMC
Examples
6,000
IS
0.14-10.02
0.55+10007
0.18::0.02
Ours
0.13-20.02
0.35+00.05
0.16:::002
for (1;))l where fx; and fay (xx) are two prediction confidence vectors for the example z;- Intuitively, smaller prediction difference indicates smaller deviation between the retrained and processed models.
We calculate the prediction difference between the retrained model and the processed model on three different datasets, S,, Sy, and Steat The experiment results on CIFAR-10 10 and Fashion-MNISY are shown in Table The results show that the proposed MCMC unlearning algorithm effectively reduce the prediction difference, which further justify the effectiveness of the proposed method.
22


Reviews:
[{"review_id": "m9x3IkY7QZ1", "reviewer": "Reviewer_b83d", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strength: \n1) The demonstrated algorithm is very simple. From the evaluation, the quality of the method also seems to be effective.\n2) 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.\n\nWeakness:\n1) 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? \n2) 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. \n\nQuestion:\nIs 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_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.", "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.\n\nAt the same time, the reviewer is not able to verify the proofs of the theorems in 4.3 and 4.4. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "jNu2uKF-DA", "reviewer": "Reviewer_uE21", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "2. Rationale for the score\n\nThe problem is very nicely introduced and well justified with recent (GDPR!) developments in application of IT / AI System.\n\nThe contribution is well structured into four main parts, each part being then outlined in the paper.\n\nThe supplementary material is complete and provides a nice benefit. \n\nThe 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.\n\nThe choice of real world dateets (FMNIST and CIFAR-10 ) is taking well known but complex enough datasets into account.\n\nThe 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.\n\nWeaknesses: None\n", "summary_of_the_paper": "1. Summary\n\nThe 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.", "summary_of_the_review": "A very nice paper, both well justified and nicely outlined. I can't see any weaknesses.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "B8s49H9H_r", "reviewer": "Reviewer_VQTF", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strong Points\n\n- 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)\n\n- 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. \n\n- A well-performed experimental evaluation shows the effectiveness of the presented method. \n\n\nWeak Points\n\n- 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. \n", "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. ", "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. \n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "ABRH4nedshr", "reviewer": "Reviewer_2pj7", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n\n- 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\n\n- the theoretical development of the method looks solid\n\nConcerns / questions:\n\n- 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.)\n\nI 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?\n\n- In section 5.2, it's unclear to me from the description what the difference is between the baseline method and just retraining.\n\nSmall remarks:\n\n- 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.\n\n- Figure 1(b), y-axis: why does it say (/s), shouldn't that be (s)?\n\n- Appendix C.2: \"phrases\" should be \"phases\"", "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.", "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.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

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)