Year: 2021

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, 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 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 source code package has been submitted and will be released publicly.

heading: 1 INTRODUCTION
text: “The right to be forgotten” refers to the right of individuals to request data controllers such as tech giants to 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 California 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 requirements of the right to be forgotten (Li et al., 2018; Garg et 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 to be forgotten in the AI 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 a 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 sampling-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 to approximate the target posterior under the measure of KL-divergence, which then converts the MCMC unlearning problem to an optimization problem with an explicit distribution parameter for knowledge removal analysis. Based on this conversion, an MCMC influence function is designed (Huber, 2004; Koh & Liang, 2017) to characterize the knowledge learned from single data samples. The new influence function then delivers 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 knowledge removal analysis, we prove that the proposed MCMC unlearning algorithm can provably realize a ε-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) 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 is no larger than the order of O(1/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 unlearning problem to an optimization problem. (2) Based on this problem conversion, we design an MCMC influence function to characterize the knowledge learned from data, which then delivers the MCMC unlearning algorithm. (3) We conduct theoretical analyses for the proposed algorithm. We prove that the MCMC unlearning can realize an εknowledge removal and has little impact on the generalization ability of the learned distribution. (4) We conduct comprehensive experiments to 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 algorithm can effectively remove the knowledge learned from the requested data while retaining the information learned from other data intact. The code has been submitted and will be released publicly.

heading: 2 RELATED WORKS
text: Markov 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 et al., 1987; Neal et al., 2011), Gibbs sampling (Geman & Geman, 1984; George & McCulloch, 1993) and slice sampling (Neal, 2003; Walker, 2007), MCMC still suffers from huge computational cost when inferring on large-scale dataset since each sampling step in MCMC requires computation over the whole dataset.
To tackle this issue, Welling & Teh (2011) 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), stochastic gradient Riemannian Langevin dynamics (SGRLD) (Patterson & Teh, 2013), Ahn et al. (2012), Ding et al. (2014), and Zhang et al. (2020). Ma et al. (2015) further design a complete framework for constructing SG-MCMC.
Machine unlearning. Machine unlearning aims to remove the knowledge learned from specific data in efficient manners (Cao & Yang, 2015). Existing unlearning methods can be roughly divided into two categories, exact methods and approximate methods. Exact methods aim to recover the model that trained without the removed data exactly, which therefore are usually realized by reducing the retraining cost as much as possible. For example, Ginart et al. (2019) propose an efficient unlearning method for k-means clustering via model parameter quantization. Bourtoule et al. (2021) propose a SISA framework that would only retraining the affected part of the model during data deletion. Other advances of exact machine unlearning include Ullah et al. (2021) and Brophy & Lowd (2021).
On the other hand, the approximate method aims to modify the trained model to approximate that trained only on the remaining data. A series of works are designed via characterizing the influence of data on the trained model with influence functions (Cook & Weisberg, 1982; Huber, 2004; Koh & Liang, 2017), including Guo et al. (2020), Golatkar et al. (2020), and Golatkar et al. (2021). Other approaches include Baumhauer et al. (2020) and Izzo et al. (2021). Some works have also studied machine unlearning in Bayesian inference (Nguyen et al., 2020; Gong et al., 2021). However, these works only focus on variational inference, an optimization-based 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 a theoretical knowledge removal guarantee.

heading: 3 PRELIMINARIES
text: Suppose p(z|θ) is a parameterized distribution over the sample space Z , where θ ∈ Θ ⊂ Rd is the parameter with a prior distribution p(θ). Suppose S = {z1, z2, · · · , zN} is a dataset consists of N samples, where each sample zi ∈ Z is drawn from the parameterized distribution p(z|θ), i.e., zi ∼ p(z|θ). Bayesian inference aims to infer the posterior distribution p(θ|S) of the parameter θ,
p(θ|S) = p(θ) ∏N i=1 p(zi|θ)∫
p(θ) ∏N i=1 p(zi|θ)dθ .
For simplicity, for the given dataset S, we let pS denotes the true posterior distribution p(θ|S), and p̂S denotes the posterior distribution that inferred by Bayesian inference.
Usually, the denominator of the posterior pS has no closed-form solution, which barriers directly calculating the posterior distribution. Thereby, researchers have designed methods to approximate the target posterior. A canonical approach is the sampling-based Bayesian inference method, Markov chain Monte Carlo (MCMC) (Hastings, 1970).
MCMC infers a 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, it 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 et al., 2015) leverage mini-batch estimation (Robbins & Monro, 1951) to enable scalable sampling. In SG-MCMC, the posterior distribution p(θ|S) can be rewritten as p(θ|S) ∝ exp(−U(θ)), where U(θ) is the potential function defined as U(θ) = − ∑ zi∈S log p(zi|θ)− log p(θ). In each sampling step, drawing samples with SG-MCMC requires one to estimate the potential function U(θ) with mini-batch data S̃ ⊂ S as follows,
Ũ(θ) = −|S| |S̃| ∑ zi∈S̃ log p(zi|θ)− log p(θ).
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 θt as follows,
θt+1 = θt − ηt∇θŨ(θt) + 2 √ ηtW,
where W is drawn from the standard Gaussian distribution N (0, I) and ηt > 0 is the step size. To improve the sampling efficiency of SGLD, stochastic gradient Hamiltonian Monte Carlo (SGHMC) (Chen et al., 2014) inserts a momentum vt into the posterior sample update as below,
θt+1 = θt + vt, vt+1 = (1− α)vt − ηt∇θŨ(θt) + √ 2αηtW,
where W is also drawn from the Gaussian distribution N (0, I), ηt > 0 is the step size, and α ∈ (0, 1) is the momentum factor. The initial momentum term v0 is drawn from the Gaussian distribution N (0, η0I). To ensure the drawn samples converge to the targeted posterior, the step size ηt for both SGLD and SGHMC needs to satisfy (Welling & Teh, 2011): (1) ∑∞ t=1 ηt = ∞; and (2) ∑∞ t=1 η 2 t < ∞. A typical step size schedule is ηt = a(b+ t)−r, where a, b > 0 and r ∈ (0.5, 1].

heading: 4 MCMC UNLEARNING ALGORITHM
text: This section presents the main results of this paper. We first define a new notion, ε-knowledge removal, to assess the machine unlearning performance in Bayesian inference. Then, an MCMC unlearning algorithm is designed with knowledge removal and generalizability guarantees.
4.1 ε-KNOWLEDGE REMOVAL FOR BAYESIAN INFERENCE
Suppose a client requests to remove her/his data S′ ⊂ S from the whole training dataset S. An unlearning algorithm A for Bayesian inference aims to remove the knowledge learned from the requested data S′ from the inferred distribution p̂S as follows,
p̂−S ′ S = A(p̂S , S ′),
where p̂−S ′
S is named as the processed distribution.
In order to meet the regulation requirements, the following notion is defined to quantify the machine unlearning performance in Bayesian inference. Definition 1 (ε-knowledge removal). For the distribution p̂S that inferred on dataset S via Bayesian inference and any subset S′ ⊂ S, we call algorithm A performs ε-knowledge removal, if
KL(p̂−S ′
S ‖p̂S−S′) ≤ ε,
where p̂−S ′
S = A(p̂S , S′) is the processed distribution. Remark 1. Intuitively, a smaller ε indicates the algorithm A has better unlearning performance.
In practice, one usually can only obtain an inferred distribution p̂S(·|ω), subjects to a random seed ω. In this case, the overall inferred distribution is p̂S = ∫ p̂S(·|ω)p(ω)dω, which suggests that the KL-divergence in Definition 1 can then be upper-bounded as below,
KL(p̂−S ′ S ‖p̂S−S′) = KL(Eωp̂ −S′ S (·|ω)‖Eωp̂S−S′(·|ω)) = ∫ θ Eωp̂−S ′ S (θ|ω) log Eωp̂−S ′ S (θ|ω) Eωp̂S−S′(θ|ω) dθ
≤ ∫ Eω [ p̂−S ′ S (θ|ω) log p̂−S ′
S (θ|ω) p̂S−S′(θ|ω)
] dθ = EωKL(p̂−S ′ S ‖p̂S−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 ω1, · · · , ωM is M i.i.d. random seed in Bayesian inference. Then, the knowledge removal estimator ε̂M is defined as below,
ε̂M = 1
M M∑ m=1 KL(p̂−S ′ S ‖p̂S−S′ |ωm),
where p̂−S ′
S (·|ωm) = A(p̂S(·|ωm), S′) is the processed distribution for the m-th random seed ωm. Remark 2. Our experiments have employed this knowledge removal estimator ε̂M to estimate the ε value in the ε-knowledge removal guarantee. See Section 5.2 for details. Remark 3. This estimator is similar to the “Local Forgetting Bound” defined in Golatkar et al. (2020). The difference is that the bound in Golatkar et al. (2020) aims to estimate the randomness introduced by some “readout functions”, while ε̂M aims to quantify the ε-knowledge removal guarantee by estimating the difference between the original and processed distributions.

heading: 4.2 METHODOLOGY
text: 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 a posterior p̂S that is inferred by MCMC, we assume that p̂S = pS .
Developing unlearning algorithm for MCMC is challenging, since there is no explicitly parameterized distribution for knowledge removal analysis. To tackle this challenge, we re-formulate the MCMC unlearning problem as minimizing the following KL-divergence,
min δ
KL(pS(· − δ)‖pS−S′), (1)
where pS is the distribution already learned via MCMC, δ is the distribution shifting scale, S′ is the dataset that is requested to be deleted, and pS−S′ is the targeted posterior that one aims to obtain. The
idea behinds Eq. (1) 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 δ is enough.
So far, the MCMC unlearning problem has been converted to an optimization problem defined as Eq. (1). We then design MCMC unlearning algorithm based on this problem conversion. Let δ−S ′ S denotes any local minimizer of Eq. (1), and the goal of MCMC unlearning is to calculate the optimal shifting scale δ−S ′
S . To achieve that goal, we first expand the KL-divergence in Eq. (1) as follows, KL(pS(· − δ)‖pS−S′) = KL(pS‖pS−S′(·+ δ))
= Eθ∼pS [log p(θ|S)] + log p(S − S′) + Eθ∼pS [− log p(S, θ + δ) + log p(S′|θ + δ)] . (2) Through Eq. (2), one can find that when removing dataset S′ via optimizing Eq. (1), an additional term Eθ∼pS log p(S′|θ + δ) is introduced to force the distribution pS(· − δ) approaching the target posterior pS−S′ . This motivate us to follow existing works (Koh & Liang, 2017; Guo et al., 2020) to conduct influence analysis on Eq. (1) based on the introduced term Eθ∼pS log p(S′|θ + δ). Specifically, we define a new function F−S′,τ (δ, S) = Eθ∼pS [− log p(S, θ+δ)−τ · log p(S′|θ+δ)], where τ ∈ [−1, 0]. Suppose there exists a function δ̂(τ) with domain [−1, 0] such that δ̂(0) = 0, and δ̂(τ) is a local minimizer of F−S′,τ (δ, S). Then, one can let the target shifting scale δ−S ′
S be δ̂(−1), and approximate it by the first-order approximation: δ̂(−1) ≈ δ̂(0) − ∂δ̂(0)/∂τ , which means δ−S ′
S ≈ −∂δ̂(0)/∂τ . Following a standard derivation, one can calculate the first derivative ∂δ̂(0)/∂τ as the following defined MCMC influence function I(S′). Thus, the optimal δ−S ′
S is then approximated as δ−S ′
S ≈ −I(S′). For the detailed influence analysis, see Appendix A.1. Definition 3 (MCMC influence function). The MCMC influence function of dataset S′ ⊂ S is defined to be
I(S′) = − ( Eθ∼pS∇2θ log p(θ, S) )−1 ∑ z∈S′ (Eθ∼pS∇θ log p(z|θ)) T .
The MCMC influence function is defined to estimate the influence of data S′ on the learned distribution pS , as δ−S ′
S ≈ −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 1 (MCMC unlearning). Suppose one have drawn a series of samples {θ1, · · · , θT } from the posterior pS via MCMC. Then, MCMC unlearning algorithm removes the learned knowledge of dataset S′ from each drawn sample θi as follows, θ′i ← θi − I(S′), where I(S′) is the MCMC influence function for dataset S′ ⊂ S. Remark 4. Algorithm 1 is equivalent to the following unlearning process,
p−S ′ S (·) = A(pS , S ′) = pS(·+ I(S′)) ≈ pS(· − δ−S ′ S ).
Remark 5. Due to the inherent geometric difference between the distribution functions pS and pS−S′ , it is impossible for Algorithm 1 to directly shift pS to 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.

heading: 4.3 KNOWLEDGE REMOVAL ANALYSIS
text: This section studies the ε-knowledge removal for the proposed MCMC unlearning algorithm. We first introduces several assumptions (Assumptions 1-4) for the knowledge removal analysis. Assumption 1. Function −Eθ∼pS log p(θ + δ) and −Eθ∼pS log p(z|θ + δ) are L1-Lipschitz continuous on the support set supp(δ).
The Lipschitzness of −Eθ∼pS log p(θ + δ) can be realized by choosing appropriate prior distribution for θ, for example, let p(θ) be a Laplace distribution. Besides, the Lipschitzness of −Eθ∼pS log p(z|θ + δ) can usually be achieved by setting p(z|θ + δ) to be a neural network with bounded domain in practice.
Assumption 2. There exists a neighborhood V2 ⊂ supp(δ) of the origin point such that for any dataset S and any sample point z ∈ Z , the followings hold:
• (Smoothness). ∇δ[−Eθ∼pS log p(θ+ δ)] and∇δ[−Eθ∼pS log p(z|θ+ δ)] are L2-Lipschitz continuous on the space V2.
• (Lipschitz Hessian). ∇2δ [−Eθ∼pS log p(θ + δ)] and ∇2δ [−Eθ∼pS log p(z|θ + δ)] are L3Lipschitz continuous on the space V2.
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 ⊂ supp(δ) of the origin point such that for any dataset S and any sample point z ∈ Z , −Eθ∼pS log p(θ + δ) and −Eθ∼pS log p(z|θ + δ) are µ-strongly convex on V3.
The influence analysis and the defined MCMC influence function require the Hessian matrices of −Eθ∼pS log p(θ + δ) and −Eθ∼pS log p(z|θ + δ) to be invertible. Assumption 3 ensures the invertibilities of these Hessian matrices. Assumption 4. Suppose Assumptions 1-3 hold. Then there exists a sub-neighborhood V ∈ V2 ∩ V3 of the origin point such that for any dataset S and any real τ ∈ [−1, 0], the function −Eθ∼pS log p(θ + δ|S)− τ · Eθ∼pS log p(S′|θ + δ) has at least one local minimizer falls in V .
Assumption 4 assumes the target optimal solution δ−S ′
S of Eq. (1) exists in the subspace that we are 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 δ. Theorem 1. Under Assumptions 1-4, we have that
δ−S ′ S = −I(S ′) +O
( |S′|2
N2
) .
The proof of Theorem 1 is presented in Appendix A.1.
Based on Theorem 1, 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 ε−S ′ S -knowledge removal, where
ε−S ′ S = KL(pS(· − δ −S′ S )‖pS−S′) +O
( |S′|4
N3
) ,
and δ−S ′
S is a local minimizer of the KL-divergence KL(pS(· − δ)‖pS−S′).
Proof sketch. We expand KL(pS(·+ I(S′))‖pS−S′) into Taylor series up to 2-th order around the point δ = δ−S ′
S . By applying the first-order optimality condition, the first-order term in the Taylor series becomes 0. By leveraging the approximation error given in Theorem 1, the second-order term is proved to be no larger than the order of O(|S′|4/N3). The proof is presented in Appendix A.2. Remark 6. As explained in the previous section, Algorithm 1 could not completely remove the learned knowledge from the inferred distribution due to the inherent geometric difference between the distribution pS and pS−S′ . Nevertheless, Theorem 2 demonstrates that the Algorithm 1 can help the KL-divergence in Eq. (1) approach its local minimum.

heading: 4.4 GENERALIZATION ANALYSIS
text: This section studies the impact of the proposed MCMC unlearning algorithm on the generalization ability of the inferred distribution. The analysis is conducted based on the PAC-Bayes theory (McAllester, 1999; 2003), a framework for analyzing the generalization ability of stochastic machine learning models.
Specifically, supposeQ is the parameter distribution of a stochastic model. Suppose S is the training dataset. Then, the expected riskR(Q) and empirical risk R̂S(Q) of Q are defined to be
R(Q) = E θ∼Q E z `(θ, z), R̂S(Q) = E θ∼Q
1
N N∑ i=1 `(θ, zi),
where θ is the model parameter drawn from the distribution Q and ` is a loss function ranging in [0, 1]. The difference of 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 1 is proved as below.
Theorem 3. Suppose Assumptions 1-4 hold. Let p−S ′
S denotes the distribution processed by Algorithm 1. Then, for any δ ∈ (0, 1), with probability at least 1− δ, the following inequality holds,
R(p−S ′ S ) ≤ R̂S(p −S′ S ) +
√ Eθ∼pS [log pS(θ) + ‖θ‖1] + ‖I(S′)‖1 + log 2 + log 1δ + logN + 2
2N − 1 ,
where ‖I(S′)‖1 ≤ O(|S′|/N).
The proof is given in Appendix A.3.
Corollary 1. Algorithm 1 increases the generalization upper bound in Theorem 3 no larger than the order of O( √ |S′|/N).
Proof. According to Theorem 3, the difference of the generalization upper bound introduced by Algorithm 1 is O( √ ‖I(S′)‖1 2N−1 ) ≤ O( √ O(|S′|/N) 2N−1 ) = O( √ |S′| N ). This completes the proof.
Remark 7. Corollary 1 indicates that the proposed MCMC unlearning algorithm would not compromise the generalization ability of the inferred distribution.

heading: 5 EXPERIMENTS
text: In this section, we empirically verify the effectiveness and efficiency of the proposed MCMC unlearning algorithm on the Gaussian mixture models and Bayesian neural networks.

heading: 5.1 EXPERIMENTS FOR GAUSSIAN MIXTURE MODELS
text: 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 4 clusters. The Gaussian mixture models (GMMs) are employed to infer the cluster centers. For the details of the GMMs used in our experiments, see Appendix C.1.
Experiment design. We employ SGLD and SGHMC to infer the GMMs on the clustering dataset. Then, 400 points are removed from each of the grey parts and yellow parts, around 40% of the whole
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 are presented in Fig. 1a, which show that after unlearning, the processed models are close to the target models. Besides, the time costs for processing single data deletion requests are presented in Fig. 1b, 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.

heading: 5.2 EXPERIMENTS FOR BAYESIAN NEURAL NETWORKS
text: We then apply the MCMC unlearning algorithm to the Bayesian neural networks on the CIFAR-10 (Krizhevsky et al., 2009) dataset for classification. Analogous experiments are also conducted on the Fashion-MNIST (Xiao et al., 2017) dataset, please see Appendix D for more details.
Dataset & BNN. We divide the training set S of CIFAR-10 into two parts, the removed part Sf and the remained part Sr. A certain number of examples are randomly chosen from a single class in the dataset to form the removed training set Sf . The test set is denoted by Stest. A BNN consists of two convolutional layers and two fully-connected layers is adopted in the experiments. For more details about the dataset and model architecture, see Appendix D.
Baseline method. We compare the proposed MCMC unlearning algorithm with the importance sampling method (IS). Specifically, when a 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 unlearning: (1) Classification errors. We calculate classification errors the remaining set Sr, removed set Sf , 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) ε-Knowledge removal guarantee. We use the knowledge removal estimator ε̂M defined in Definition 2 to estimate the ε value in the ε-knowledge removal guarantee. A smaller estimation result would imply a better knowl-
edge removal performance. Calculating ε̂M requires to fix a series of random seeds ω1, · · · , ωM . To this end, we use a series of pre-trained models as the random seeds. See Appendix D.3 for the detailed calculation procedures. (3) Membership inference attack (MIA) accuracy. We employ a white-box MIA (Yeom et al., 2018) to infer whether the examples from the removed subset Sf come from the training set of the model. Intuitively, the attack accuracy would decline after unlearning. Thereby, a small attack accuracy implies a strong knowledge removal performance. See Appendix D.4 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 S with SGLD and SGHMC, respectively. Then, the subset Sf is removed iteratively, where a fixed number of data points are removed in each iteration. We also trained models on only the remaining set Sr 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 1. In all experiments, we observe that the proposed MCMC unlearning algorithm can significantly increase the model error on sample set Sf while making the error on sample sets Sr and Stest close to that of the retrained one. Besides, our algorithm can also reduce the ε value in the knowledge removal guarantee and the MIA accuracy on Sf , 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 errors approach the targets, nor achieve stronger ε-knowledge removal. We also present the time costs for different unlearning methods in Fig. 2. 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 unlearning algorithm. The results are presented in Fig. 3, 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.

heading: 6 CONCLUSION
text: The right to be forgotten imposes a considerable compliance burden on AI companies. A company may need to delete the whole model learned from massive resources due to a 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 on 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.

heading: A PROOFS
text: 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(δ, z) := −Eθ∼pS log p(z|θ + δ), • f(δ) := −Eθ∼pS log p(θ + δ), • F (δ, S) := ∑ z∈S h(δ, z) + f(δ) = ∑ z∈S −Eθ∼pS log p(z|θ + δ)− Eθ∼pS log p(θ + δ).

heading: A.1 PROOF OF THEOREM 1
text: To prove Theorem 1, we first define the following function, F−S′,τ (δ, S) = F (δ, S) + τ ∑ z∈S′ h(δ, z),
where τ ∈ [−1, 0]. Under Assumption 3, it can be shown that F−S′,τ (δ, S) is strongly convex on the space V3 defined in Assumption 3.
Lemma 1. Suppose Assumption 3 holds. Then, for any τ ∈ [−1, 0], F−S′,τ (δ, S) is strongly convex on the space V3.
Proof of Lemma 1. We rearrange the function F−S′,τ as follows, F−S′,τ (δ, S) = F (δ, S − S′) + (1 + τ) ∑ z∈S′ h(δ, z).
Apparently, F (δ, S−S′) is strongly convex on V3. Since τ ∈ [−1, 0], we have that 1+τ ≥ 0. Thus, (1 + τ) ∑ z∈S′ h(δ, z) is either strongly convex on V3 or equal to zero. Therefore, F−S′,τ (δ, S) is strongly convex on V3.
The proof is completed.
We then prove that when Assumption 4 holds, there exists a continuous mapping that “connects” the origin point 0 ∈ Rd and the target shifting scale δ−S ′
S .
Lemma 2. Suppose Assumption 4 holds. Then, there exists a continuous function δ̂ : [−1, 0] → V such that for any τ ∈ [−1, 0], δ̂(τ) is the global minimizer of the function F−S′,τ (δ, S) on space V .
Proof of Lemma 2. By applying Lemma 1 and Assumption 4, we have that the global minimizer of the function F−S′,τ (γ, S) uniquely exists in V . Therefore, one can define the mapping δ̂ as below,
δ̂(τ) = arg min δ∈V F−S′,τ (δ, S),
where τ ∈ [−1, 0].
We then prove the continuity of δ̂. Notice that δ̂(τ) is the solution of the following equation, ∇δF (δ, S) + τ ∑ z∈S′ ∇δh(δ, z) = 0. (3)
Since F−S′,τ (δ, S) is strongly convex, thus its Hessian matrix ∇2δF−S′,τ (δ̂(τ), S) is invertible. Combining with the implicit function theorem, we have that δ̂ is continuous on the interval [−1, 0]. The proof is completed.
When τ takes 0 and −1, the function δ̂(τ) becomes 0 ∈ Rd and δ−S ′ S , respectively. Therefore, δ −S′ S can be expanded into Taylor series as follows,
δ−S ′ S = δ̂(−1) = − ∂δ̂(0)
∂τ +
1 2 · ∂
2δ̂(ξ) ∂τ2 , (4)
where ξ ∈ [−1, 0], 12 ∂2δ̂(ξ) ∂τ2 is the Lagrange form of the remainder.
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-4 hold. The mapping δ̂ is as defined in Lemma 2. Then, we have that
∂δ̂(τ)
∂τ = −∇−2δ F (δ̂(τ), S) ∑ z∈S′ ∇δh(δ̂(τ), z)T ,
and for any τ ∈ [−1, 0], ‖∂δ̂(τ)∂τ ‖2 ≤ O(|S ′|/N).
Proof. We first calculate ∂δ̂(τ)∂τ based on Eq. (3) in the proof of Lemma 2. Calculate the derivatives of the both sides of Eq. (3) with respect to τ , we have that
∇2δF (δ̂(τ), S) · ∂δ̂(τ) ∂τ + ∑ z∈S′ ∇δh(δ̂(τ), z)T + τ · ∑ z∈S′ ∇2δh(δ̂(τ), z) · ∂δ̂(τ) ∂τ = 0. (5)
According to Lemma 1, F−S′,τ (δ, S) is strongly convex on V . Thus, the following Hessian matrix ∇2δF−S′,τ (δ̂(τ), S) = ∇2δF (δ̂(τ), S) + τ ∑ z∈S′ ∇2δh(δ̂(τ), z)
is positive definite, hence invertible. Combining with Eq. (5), we have that
∂δ̂(τ)
∂τ =−
( ∇2δF (δ̂(τ), S) + τ ∑ z∈S′ ∇2δh(δ̂(τ), z) )−1 · ∑ z∈S′ ∇δh(δ̂(τ), z)T . (6)
We then upper bound the norm of ∂δ̂(τ)∂τ . Based on Eq. (6), we have that∥∥∥∥∥∂δ̂(τ)∂τ ∥∥∥∥∥
2
≤ ∥∥∥∥∥∥ ( 1 N ∇2δF (δ̂(τ), S) + τ N ∑ z∈S′ ∇2δh(δ̂(τ), z) )−1∥∥∥∥∥∥ 2 · ∥∥∥∥∥ 1N ∑ z∈S′ ∇δh(δ̂(τ), z) ∥∥∥∥∥ 2 .
(7)
We first consider the first term of the right-hand side of Eq. (7). By Assumption 3, both f(δ) and h(δ, z) are µ-strongly convex on the space V ⊂ supp(δ). Thus, we have that
1
N ∇2δF (δ̂(τ), S) +
τ
N ∑ z∈S′ ∇2δh(δ̂(τ), z)
= 1
N N∑ i=1 ∇2δh(δ̂(τ), zi) + 1 N ∇2δf(δ̂(τ)) + τ N ∑ z∈S′ ∇2δh(δ̂(τ), z)
( 1
N ∑ z∈S−S′ µ+ µ N + 1 + τ N ∑ z∈S′ µ
) I
N − |S ′|
N µ · I. (8)
Let λmin denotes the smallest eigenvalue of the following matrix( 1
N ∇2δF (δ̂(τ), S) +
τ
N ∑ z∈S′ ∇2δh(δ̂(τ), z)
) .
Then, the Eq. (8) implies that λmin ≥ N−|S ′|
N µ. Hence, we have the following,∥∥∥∥∥∥ ( 1 N ∇2δF (δ̂(τ), S) + τ N ∑ z∈S′ ∇2δh(δ̂(τ), z) )−1∥∥∥∥∥∥ 2 = 1 λmin ≤ N (N − |S′|)µ = O(1). (9)
We then upper bound the second term of the right-hand side of Eq. (7). By applying Assumption 1, we have that ∥∥∥∥∥ 1N ∑
z∈S′ ∇δh(δ̂(τ), z) ∥∥∥∥∥ 2 ≤ L1 · |S ′| N = O ( |S′| N ) (10)
Finally, inserting eqs. (9) (10) into Eq. (7), we eventually have that∥∥∥∥∥∂δ̂(τ)∂τ ∥∥∥∥∥
2
≤ O(1) · O ( |S′| N ) = O ( |S′| N ) .
The proof is completed.
Then, the following Lemma is obtained based on Lemma 3, which demonstrates the strictness of the approximation in Eq. (4).
Lemma 4. Suppose Assumptions 1-4 hold. The induced mapping δ̂ is as defined in Lemma 2. Then, for any τ ∈ [−1, 0], we have that ‖∂
2δ̂(τ) ∂τ2 ‖2 ≤ O(|S ′|2/N2).
Proof. We first calculate ∂ 2δ(τ) ∂τ2 based on Eq. (3). Similar to the proof of Lemma 3, we calculate the second-order derivatives of the both sides of Eq. (3) with respect to τ and have that
N∑ i=1 B(τ, zi) +A(τ) + ( N∑ i=1 ∇2δh(δ̂(τ), zi) +∇2δf(δ̂(τ)) ) · ∂ 2δ̂(τ) ∂τ2
+ 2 · ∑ z∈S′ ∇2δh(δ̂(τ), z) · ∂δ̂(τ) ∂τ + τ ∑ z∈S′ B(τ, z) + τ ∑ z∈S′ ∇2δh(δ̂(τ), z) · ∂2δ̂(τ) ∂τ2 = 0,
which means
∂2δ̂(τ)
∂τ2 =−
( 1
N N∑ i=1 ∇2δF (δ̂(τ), S) + τ N ∇2δ ∑ z∈S′ h(δ̂(τ), z)
)−1
·
( 1
N N∑ i=1 B(τ, zi) + τ N ∑ z∈S′ B(τ, z) + 1 N A(τ) + 2 N ∑ z∈S′ ∇2δh(δ̂(τ), z) · ∂δ̂(τ) ∂τ
) ,
(11)
in which the invertibility of (
1 N ∑N i=1∇2δF (δ̂(τ), S) + τ N ∑ z∈S′ ∇2δh(δ̂(τ), z) ) is guaranteed by
Eq. (8), A(τ), B(τ, z) ∈ RK×1, and for i = 1, · · · ,K, we have the following,
A(τ)i = ∂δ̂(τ)
∂τ
T
· ∇2δ
( ∂f(δ̂(τ))
∂δi
) · ∂δ̂(τ) ∂τ , (12)
B(τ, z)i = ∂δ̂(τ)
∂τ
T
· ∇2δ
( ∂h(δ̂(τ), z)
∂δi
) · ∂δ̂(τ) ∂τ . (13)
We then upper bound the norm of ∂ 2δ̂(τ) ∂τ2 . Based on Eq. (11), we have that∥∥∥∥∥∂2δ̂(τ)∂τ2 ∥∥∥∥∥ 2
≤ ∥∥∥∥∥∥ ( 1 N N∑ i=1 ∇2δF (γ̂(τ), S) + τ N ∑ z∈S′ ∇2δh(δ̂(τ), z) )−1∥∥∥∥∥∥ 2
· 1 N ( N∑ i=1 ‖B(τ, zi)‖2 + τ ∑ z∈S′ ‖B(τ, z)‖2 + ‖A(τ)‖2 + 2 ∥∥∥∥∥∑ z∈S′ ∇2δh(δ̂(τ), z) · ∂δ̂(τ) ∂τ ∥∥∥∥∥ 2 ) (14)
≤ O
( 1
N ( N∑ i=1 ‖B(τ, zi)‖2 + τ ∑ z∈S′ ‖B(τ, z)‖2 + ‖A(τ)‖2 + 2 ∥∥∥∥∥∑ z∈S′ ∇2δh(δ̂(τ), z) · ∂δ̂(τ) ∂τ ∥∥∥∥∥ 2 )) ,
(15)
where Eq. (15) is obtained by inserting Eq. (9) (in the proof of Lemma 3) into Eq. (14). Thus, the remaining task is to upper bound the norms of A(τ), B(τ, z) and ∇2δ ∑ z∈S′ h(δ̂(τ), z) · ∂δ̂(τ) ∂τ .
We first upper bound ‖A(τ)‖2. Applying Lemma 3, we have that ‖∂δ̂(τ)∂τ ‖2 ≤ O(|S ′|/N). Applying the Lipschitz Hessian condition in Assumption 2, we have that ‖∇2δ( ∂f(δ̂(τ)) ∂δi
‖2 is also bounded by a real constant. Therefore, we have that
‖A(τ)‖2 ≤ K∑ i=1 ∥∥∥∥∥∇2δ ( ∂f(δ̂(τ)) ∂δi )∥∥∥∥∥ 2 · ∥∥∥∥∥∂δ̂(τ)∂τ ∥∥∥∥∥ 2 2 ≤ K∑ i=1 O(1) · O ( |S′|2 N2 ) = O ( |S′|2 N2 ) . (16)
For B(τ, z), we similarly have that ‖B(τ, z)‖2 ≤ O ( |S′|2
N2
) . (17)
To upper bound the norm of ∑ z∈S′ ∇2δh(δ̂(τ), z) · ∂δ̂(τ) ∂τ , we apply Lemma 3, Assumption 2, and have that∥∥∥∥∥∑ z∈S′ ∇2δh(δ̂(τ), z) · ∂δ̂(τ) ∂τ ∥∥∥∥∥ 2 ≤ ∑ z∈S′ ∥∥∥∇2δh(δ̂(τ), z)∥∥∥ 2 ∥∥∥∥∥∂δ̂(τ)∂τ ∥∥∥∥∥ 2 ≤ O ( |S′|2 N ) . (18)
Inserting eqs. (16), (17) and (18), into Eq. (15), we eventually have that∥∥∥∥∥∂2δ̂(τ)∂τ2 ∥∥∥∥∥
2
≤ O
( 1
N ( N∑ i=1 O ( |S′|2 N2 ) + τ · O ( |S′|3 N2 ) +O ( |S′|2 N2 ) + 2 · O ( |S′|2 N ))) = O ( |S′|2 N2 ) .
The proof is completed.
Finally, combining all the results, we prove Theorem 1.
Proof of Theorem 1. The proof is completed by applying Lemmas 3 and 4 into Eq. (4).

heading: A.2 PROOF OF THEOREM 2
text: This section presents the proof of Theorem 2.
Proof of Theorem 2. By expanding the KL-divergence KL(pS(·+I(S′))‖pS−S′) into Taylor series around the local region of δ = δ−S ′
S , we have KL(pS(·+ I(S′))‖pS−S′)
= KL(pS(· − δ−S ′ S ‖pS−S′) + (I(S ′) + δ−S ′ S ) T · ∇2δKL(pS(· − ξ)‖pS−S′) · (I(S′) + δ−S ′ S )
= KL(pS(· − δ−S ′ S ‖pS−S′)− (I(S ′) + δ−S ′ S ) T · ∇2δ
[ F (ξ, S)−
∑ z∈S′ h(ξ, z)
] · (I(S′) + δ−S ′
S ),
(19) where the first-order term equals 0 according to the first-order optimal condition. By applying Theorem 1 and Assumption 2, we further have∥∥∥∥∥(I(S′) + δ−S′S )T · ∇2δ [ F (ξ, S)− ∑ z∈S′ h(ξ, z) ] · (I(S′) + δ−S ′ S ) ∥∥∥∥∥ 2
≤ ∥∥∥∥∥∇2δ [ F (ξ, S)− ∑ z∈S′ h(ξ, z) ]∥∥∥∥∥ 2 · ∥∥∥I(S′) + δ−S′S ∥∥∥2 2
≤ (N − |S′|+ 1)L2 · diam(V ) · O ( |S′|2
N2
)2 ≤ O ( |S′|4
N3
) . (20)
By combining eqs. (19) and (20), the proof is completed.

heading: A.3 PROOF OF THEOREM 3
text: This section presents the proof of Theorem 3.
We derive generalization bounds for BIF 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 a distribution on the parameter space Θ, P denotes the prior distribution over the parameter space Θ. Then, the expected risks R(Q) is bounded in terms of the empirical risk R̂(Q,S) and KL-divergence KL(Q‖P ) by the following result from PAC-Bayes. Lemma 5 (cf. McAllester (2003), Theorem 1). For any real δ ∈ (0, 1), with probability at least 1− δ, we have the following inequality for all distributions Q:
R(Q) ≤ R̂(Q,S) +
√ KL(Q‖P ) + log 1δ + logN + 2
2N − 1 . (21)
Based on Lemma 5, we prove the generalization bounds in Theorem 3.
proof of Theorem 3. Let the prior distribution P be a Laplace distribution lap(0, 1), p−S ′
S = pS(·+ I(S′)) be the distribution processed by the MCMC unlearning algorithm. Then, one can calculate the KL-divergence KL(p−S ′
S ‖P ) as follows (where we assume that Θ = Rd),
KL(p−S ′ S ‖P ) = ∫
Θ
log
( p−S ′
S (θ)
p(θ)
) p−S ′
S (θ)dθ
= ∫ Θ log ( pS(θ) p(θ − I(S′)) ) pS(θ)dθ
= ∫ Θ [log pS(θ) + ‖θ − I(S′)‖1 + log 2] pS(θ)dθ ≤ Eθ∼pS log pS(θ) + Eθ∼pS‖θ‖1 + ‖I(S′)‖1 + log 2. (22)
Inserting Eq. (22) into Eq. (21) in Lemma 5, we then obtain the PAC-Bayesian generalization bound.
Eventually, by applying Lemma 3, we have that ‖I(S′)‖1 ≤ O(|S′|/N). The proof is completed.

heading: B EFFICIENT CALCULATION OF MCMC INFLUENCE FUNCTION
text: A major computing burden in the MCMC unlearning algorithm is calculating the product of H−1v, whereH is the Hessian matrix of some vector-valued function f(x) and v is a constant vector. When the function f(x) is of high dimension, the calculation would have a considerably high computational cost. We follow Agarwal et al. (2017) and Koh & Liang (2017) to apply a divide-and-conquer strategy to address the issue. This strategy relies on calculating the Hessian-vector product Hv.
Hessian-vector product (HVP). We first discuss how to efficiently calculate Hv. The calculation of Hv can be decomposed into two steps: (1) calculate ∂f(x)∂x and then (2) calculate ∂ ∂x ( ∂f(x) ∂x · v ) . It is worth noting that ∂f(x)∂x ∈ R 1×d and v ∈ Rd×1, where d > 0 is the dimension of data. Thus,(
∂f(x) ∂x · v ) is a scalar value. Calculating its gradient ∂∂x ( ∂f(x) ∂x · v ) has a very low computational
cost on platform PyTorch (Paszke et al., 2017) or TensorFlow (Abadi et al., 2015).
Calculating H−1v. When the norm ‖H‖ ≤ 1, the matrix H−1 can be expanded by the Taylor’s series as H−1 = ∑∞ i=0(I −H)i. Define that H −1 j = ∑j i=0(I −H)i. Then, we have the following recursive equation, H−1j v = v + (I −H)H −1 j−1v.
Agarwal et al. (2017) prove that when j → ∞, we have E[H−1j ] → H−1. Therefore, we employ H−1j v to approximate H −1v.
Moreover, to secure the condition ‖H‖ ≤ 1 stands, we scale H to cH by a scale c ∈ R+, such that ‖cH‖ ≤ 1. Then, we approximate (cH)−1. Eventually, we have that H−1 = c(cH)−1. We can plug it to the applicable equations above.

heading: C EXPERIMENTS DETAILS FOR GAUSSIAN MIXTURE MODELS
text: This section provides the additional experiments details for the Gaussian mixture models.

heading: C.1 GAUSSIAN MIXTURE MODELS
text: 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 µ1, · · · , µK , respectively. Then, the hierarchical structure of GMM is as follows: (1) draw a clustering center from the uniform distribution over {µc1 , . . . , µcK}; and (2) sample zi from a Gaussian distribution centering at µci . That is,
µk ∼ N (0, σ2I), ci ∼ categorical ( 1
K , · · · , 1 K
) ,
Zi ∼ N (µci , I),
where 1 ≤ k ≤ K, 1 ≤ i ≤ n, µk ∈ Rd, ci ∈ {1, · · · ,K}, Zi ∈ Rd, and the hyperparameter σ ∈ R is the prior standard deviation. In our experiments, the factor K is set as 4, and the prior standard deviation σ is set as 1.

heading: C.2 EXPERIMENTS DETAILS
text: The experiments for GMM have two main phases:
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 · t−0.5005/N , where t 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 a batch of 4 datums each time. When calculating the inversedHessian-vector product H−1v in the influence functions (see Section B), the recursive calculation number j is set as 32, and the scaling factor c is set as 1/N ′, where N ′ is the number of the current remained training examples. Notice that N ′ will gradually decrease as the forgetting process continues. Moreover, we employ the Monte Carlo method to calculate the expectations in the MCMC influence function. Specifically, we repeatedly draw sample θ for 5 times, calculate the matrix or vector in the MCMC influence function, and average the results to approach the expectations.

heading: D EXPERIMENTS DETAILS FOR BAYESIAN NEURAL NETWORKS
text: This section provides the additional experiments details for Bayesian neural networks.

heading: D.1 DATASETS
text: We employ two image datasets, Fashion-MNIST (Xiao et al., 2017) and CIFAR-10 (Krizhevsky et al., 2009), in 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, it is worth noting that the models used for Fashion-MNIST 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.

heading: D.2 BAYESIAN NEURAL NETWORKS
text: This section introduces the model architectures used in our experiments and the implementation details for training BNNs.

heading: D.2.1 MODEL ARCHITECTURES
text: For Fashion-MNIST, we use a LeNet (LeCun et al., 1998) architecture that consists of two convolutional layers followed by three fully-connected layers. The convolutional layers use 5× 5 convolutions, each followed by a 2 × 2 max-pooling layer and a ReLU activation function. The channel numbers of the two convolutional layers are 6 and 16, respectively. Besides, each fully-connected layer is also followed by a ReLU activation function, while the hidden layer channels are 120 and 84, respectively.
for CIFAR-10, we follow Abadi et al. (2016) to use a network architecture that consists of two convolutional layers followed by two fully-connected layers. Each convolutional layer uses 5 × 5 convolution, with a channel number of 64, followed by a 2× 2 max-pooling layer and a ReLU activation function. Besides, each fully-connected layer is also followed by a ReLU activation function, while the hidden layer channels are 384.

heading: D.2.2 MODEL TRAINING
text: In all the experiments, we use an isotropic Gaussian distributionN (0, σ20I) as the prior of the BNNs, in which the hyperparameter σ0 is set as 0.1.
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 (Zhang et al., 2020). To alleviate such a problem, we follow Zhang et al. (2020) to first avoid the noise injection in the early training iterations and then resume SG-MCMC as usual in the rest of the training.
D.3 ESTIMATING THE ε-KNOWLEDGE REMOVAL GUARANTEE
We use the knowledge removal estimator ε̂M defined in Definition 2 to estimate the ε value in the εknowledge removal guarantee. According to the definition of ε̂M , calculating it requires first fixing a series of random seeds, and then calculating the KL-divergence between two MCMC distributions.
For the random seeds, we employ the pretraining technique (Golatkar et al., 2020) to fix them. Specifically, for the experiments on Fashion-MNIST, all the models used are first pre-trained on MNIST; for the experiments on CIFAR-10, all the models used are first pre-trained on CIFAR-100.
Besides, for the KL-divergence calculation, we follow Wang et al. (2009) to estimate the KLdivergence in a k-NN manner, in which 100 samples are drawn from each of the processed and retrained distributions for the estimation.

heading: D.4 MEMBERSHIP INFERENCE ATTACK
text: Membership inference attack (MIA) (Shokri et al., 2017; Yeom et al., 2018) is a privacy attack that aims to infer whether a given example is in the training set based on the output of the model. In our experiments, we adopt a white-box threshold-based MIA (Yeom et al., 2018) to assess the unlearning performance. The calculation consists of two steps: (1) learn an optimal MIA threshold on the remained training set Sr and the test set Stest, and (2) calculate MIA accuracy with the learned threshold on the removed training set Sf .
Learn the optimal threshold. Suppose the “to-be-inferred” example (x, y) comes from Sr and Stest with equal probabilities. Then, the attack accuracy of MIA with a threshold ρ ∈ [0, 1] on the model fθ is calculated as follows,
Acc(ρ, Sr, Stest) = 0.5×
(∑ (x,y)∈Sr 1[fθ(x)y ≥ ρ]
|Sr| +
∑ (x,y)∈Stest 1[fθ(x)y < ρ]
|Stest|
) ,
where fθ(x)y is the output confidence for label y and 1[·] is the indicator function. Then, the optimal threshold ρoptim is obtained via calculating the maximizer of the above attack accuracy, i.e.,
ρoptim = arg max ρ Acc(ρ, Sr, Stest).
Calculate MIA accuracy on Sf . With the optimal threshold ρoptim that learned on Sr and Stest, the MIA accuracy on the removed set Sf is calculated as follows,
Acc(ρoptim, Sf ) =
∑ (x,y)∈Sf 1[fθ(x)y ≥ ρoptim]
|Sf | .
Intuitively, after removing the knowledge learned from the removed subset Sf , the MIA accuracy Acc(ρoptim, Sf ) would decline. As a result, a low MIA accuracy on the removed subset Sf would imply a strong knowledge removal performance.

heading: D.5 EXPERIMENTS DETAILS
text: This section provides the omitted experiment details, including the settings of the hyperparameters and the procedures of the experiments.

heading: D.5.1 EXPERIMENTS ON FASHION-MNIST
text: Pretraining phase. In every experiment, we pretrain a non-Bayesian model with 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 as 128. For both SGLD and SGHMC, we first train the model without noise injection in 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−0.5005/N , where t is the training iteration step. Besides, the momentum factor α of SGHMC is set as 0.9.
Unlearning phase. We remove a batch of 64 datums each time.
For the MCMC unlearning algorithm, when calculating the inversed-Hessian-vector product H−1v in the MCMC influence function (see Appendix B), the recursive calculation number j is set as 64, the scaling factor c is 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, we employ the Monte Carlo method to calculate the expectations in the MCMC influence function. Specifically, each time we draw a sample θ via the MCMC sampler and calculate the matrix and vector in the MCMC influence function based on θ to estimate the desired expectation.
Besides, for the importance sampling method, we process each data deletion request by performing MCMC sampling for 1, 000 times on the remaining data.

heading: D.5.2 EXPERIMENTS ON CIFAR-10
text: Pretraining phase. In every experiment, we pretrain a non-Bayesian model on CIFAR-100 via SGD for 10, 000, 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 20, 000 iterations. The batch size is set as 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 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−0.5005/N , where t is the training iteration step. Besides, the momentum factor α of SGHMC is set as 0.9.
Unlearning phase. We remove a batch of 64 datums each time.
For the MCMC unlearning algorithm, When calculating the inversed-Hessian-vector product H−1v in the MCMC influence functions (see Appendix B), the recursive calculation number j is set as 64, the scaling factors c 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, we employ the Monte Carlo method to calculate the expectations in the MCMC influence function. Specifically, each time we draw a sample θ via the MCMC sampler and calculate the matrix and vector in the MCMC influence function based on θ to estimate the desired expectation.
Besides, for the importance sampling method, we process each data deletion request by performing MCMC sampling for 1, 000 times on the remaining data.

heading: D.6 EXPERIMENT RESULTS ON FASHION-MNIST
text: This section presents all the experiment results of BNNs on the Fashion-MNIST dataset. The evaluations of unlearning performance are shown as Table 2, while the time costs for unlearning is shown in Fig. 4 The results further justify the effectiveness of the proposed algorithm.

heading: D.7 EVALUATION ON PREDICTION DIFFERENCES
text: In this section, we adopt the metric named prediction differences to better quantify the difference between the retrained and processed models.
For two BNNs p1(·) and p2(·) learned by MCMC, their prediction difference on a given dataset S is defined below,
Eθ1∼p1Eθ2∼p2 1 |S| ∑
(xi,yi)∈S
‖fθ1(xi)− fθ2(xi)‖1,
where fθ1(xi) and fθ2(xi) are two prediction confidence vectors for the example xi. Intuitively, a smaller prediction difference indicates a 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, Sr, Sf , and Stest. The experiment results on CIFAR-10 and Fashion-MNIST are shown in Table 3. The results show that the proposed MCMC unlearning algorithm can effectively reduce the prediction difference, which further justifies the effectiveness of the proposed method.

Review summaries:
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.

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. 

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.