Prompt Certified Machine Unlearning with Randomized Gradient Smoothing and Quantization
Authors: Zijie Zhang
Yang Zhou
Xin Zhao
Tianshi Che
Lingjuan Lyu
Venue: NeurIPS 2022 Accept (2022)
Keywords: Certified machine unlearning
randomized gradient smoothing
gradient quantization
theoretical guarantee
prompt unlearning

Abstract: The right to be forgotten calls for efficient machine unlearning techniques that make trained machine learning models forget a cohort of data. The combination of training and unlearning operations in traditional machine unlearning methods often leads to the expensive computational cost on large-scale data. This paper presents a prompt certified machine unlearning algorithm, PCMU, which executes one-time operation of simultaneous training and unlearning in advance for a series of machine unlearning requests, without the knowledge of the removed/forgotten data. First, we establish a connection between randomized smoothing for certified robustness on classification and randomized smoothing for certified machine unlearning on gradient quantization. Second, we propose a prompt certified machine unlearning model based on randomized data smoothing and gradient quantization. We theoretically derive the certified radius R regarding the data change before and after data removals and the certified budget of data removals about R. Last but not least, we present another practical framework of randomized gradient smoothing and quantization, due to the dilemma of producing high confidence certificates in the first framework. We theoretically demonstrate the certified radius R' regarding the gradient change, the correlation between two types of certified radii, and the certified budget of data removals about R'. 

Prompt Certified Machine Unlearning with Randomized Gradient Smoothing and Quantization
Zijie Zhang
Yang Zhou
Xin Zhao' Tiansi Che Lingjuan Lyu²*
Auburn University, 'Sony AI
zzz00920auburn.c edu,, yangzhou@auuurn edu, cmkk6847350gmail. com,
tzc0029@auburn.co edu, lingjuan. lv@sony com
Abstract
The right to be forgotten calls for efficient machine unlearning techniques that make trained machine learning models forget a cohort of data. The combination of training and unlearning operations in traditional machine unlearning methods often leads the expensive computational cost on large-scale data. This paper presents a Prompt Certified Machine Unlearning algorithm, PCMU, which executes one-time operation of simultaneous training and unlearning advance for a series of machine unlearning requests, without the knowledge of the removed/forgotten data. First, we establish a connection between randomized smoothing for certified robustness on classification and randomized smoothing for certified machine un- learning on gradient quantization. Second, we propose prompt certified machine unlearning model based on randomized data smoothing and gradient quantization. We theoretically derive the certified radius It regarding the data change before and after data removals and the certified budget of data removals about R. Last but not least, we present another practical framework of randomized gradient smoothing and quantization, due to the dilemma of producing high confidence certificates in the first framework. We theoretically demonstrate the certified radius R' regarding the gradient change, the correlation between two types of certified radii, and the certified budget of data removals about R'.
1 Introduction
In order to respect the privacy, machine unlearning techniques aim enable data owners to proac- tively remove their data and eliminate its influence from already trained machine learning model upon requests 10
50 134 97]. straightforward solution is to retrain new models from scratch on the eemmininn/remmemeeree data, without the knowledge of the removed/forgotten data, as if the retrained model has never seen forgotten data. However, the naive method impractical since it often encounters expensive cost over complex models (e.g., DNN) on large data.
This has motivated the recent study of resolving the inefficiency issue of the naive machine unlearning. Existing techniques can be broadly classified into two categories: (1) Exact unlearning algorithms aim learn an unlearning model with the same performance the above naive ones retraining from scratch by completely excluding the forgotten data from the training data [107] 12 62 [7] 78
15 [4] and (2) Approximate unlearning methods try bring the parameters of the trained model closer to the naive ones through the relaxation of exact unlearning
83
g [08 42 10
124
requirements 4 45
122
336
64
40
94 110
4
49 96
46
81
Certified removal is sertifiedrremoval mechanism that applies Newton step on the model parameters that largely remove the influence of the deleted data points [49]. GKT is zero-shot machine unlearning algorithm that imposes the constraint that zero training data
83
126
133
143
82
*Corresponding authors
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

is available to the unlearning algorithms 20 Two recent studies propose online machine unlearning methods for linear regression models [78] and linear support vector machine models [77. for further improving the efficiency of machine unlearning. The former adapts users' requests to delete their data before a specific time bar. The latter conducts only the task of variable support vector machine.
Despite achieving remarkable success, most of the above machine unlearning methods consist of two sequential operations: (1) Training: train model on the complete training data and (2) Unlearning: generate an unlearning model from the former. The combination of two operations is computationally expensive when training complex models over large datasets. In addition, they often sequentially redo the unlearning operations one by one, when addressing series of machine unlearning requests.
Randomized smoothing has achieved the offte--o-theearr certified robustness guarantees against
worst-case attacks by smoothing with isotropic Gaussian distribution 669 23 70 76
104 72 144
58 6
53 (6). Specially, it takes base classifier f(x) as an input, and outputs a smooth classifier g (3) argmax TP (f(x + E) = c) by averaging its prediction
38
141
92 88 3
13
142
119
16
CEY' END
over isotropic Gaussian noise D = N (0, r) of the input data x. within its neighborhood e. It provides a tight certified robustness guarantee: g(r) can always return the most probable class C.A. i.e., g(x + 5) = ca for all ||1|| < R, as long as the perturbation 5 within the certified radius R.
This motivates us to establish a connection between randomized smoothing for certified robustness on classification and randomized smoothing for certified machine unlearning on gradient quantization. We analogize the data removals on the entire training data (i.e., the perturbations on the entire data) in the machine unlearning the adversarial attacks (i.e., the perturbations on the data samples) in the certified robustness and liken the output quantized gradients in the former to the output discrete class labels in the latter. Since the output class labels in the latter through randomized smoothing are able to keep unchanged and correct against adversarial attacks within the certified radius, it is highly possible that the output quantized gradients in the former through randomized smoothing can keep unchanged against data removals within the certified budget, which implies that the learnt model shares the same gradients (and parameters) with the naive one retrained on only the remembered data.
Instead of performing two sequential operations of training and unlearning, this work directly trains an unlearning model in advance, without the knowledge of the forgotten data, based on randomized data smoothing and gradient quantization. We propose to execute the randomized smoothing on the average T of data samples. When there are data removal requests in the training data, will be updated with a new average F', which can be treated as a perturbed version of Z. As the class labels lie in (countable) small discrete space but the gradients lic in large continuous space, we propose a gradient quantization technique to produce discrete gradients in three-class space (-1, 1). The randomized smoothing method needs to sample a large number of points surrounding the input data for producing high confidence certificates, e.g., 10 samples for 99.9% confidence [23). In our context, the outputs of randomized smoothing are high sigh-dimensional gradients. We propose to utilize the Taylor expansion to approximate the output gradients of the sampled points for avoiding expensive gradient computation. We theoretically derive the error introduced by the Taylor expansion, the certified radius R regarding the perturbation surrounding J and the certified budget B of data removals (i.c., the maximally allowed amount of escaped data samples).
Notice that the response to the data removals is to crase the data samples and their associated labels together. It is necessary to smooth on both of them. However, for a given dataset, the relationship between the samples and labels is a multi-valued non-continuous mapping, which is non- non- -nteegggea function. This results in the dilemma of producing high confidence certificates, even with sampling and estimation techniques. Therefore, we propose feasible solution based on randomized gradient smoothing and gradient quantization. We theoretically demonstrate the certified radius R' regarding the gradient perturbations. Most importantly, we recognize the correlations between two types of radii R and R' and between B and R, which are used to derive the certified budget B' about R'. We further integrate the model training, randomized gradient smoothing, and gradient quantization into unified framework for directly training a machine unlcarning model with the data removal certificates as guidance, for guaranteeing that the model parameters and gradients keep unchanged against the data removals within the certified budget.
In comparison with existing machine unlearning techniques, our randomized gradient smoothing and gradient quantization method exhibits three compelling advantages: (1) It simultaneously executes the training and unlearning operations, which is able to dramatically improve the unlearning efficiency
2

---

for complex models on large-scale data; (2) The one- timetime operation of simultaneous training and unlearning can provide the timely response series of machine unlearning requests, long as the actual data removals are below the certified budget of data removals; and (3) It is agnostic to the removed/forgotten data before performing the unlearning operation.
Empirical evaluation on real datasets demonstrates the superior performance of our PCMU model against several state-of-the-art machine unlearning methods on image classification. More experi- ments, implementation details, and hyperparameter setting are presented in Appendices A.5
2 Background
2.1 Randomized Smoothing for Certified Robustness
Randomized smoothing aims to build a smoothed classifier 9 from a base classifier f that maps inputs C.
Rd to classes
g(x) argmax P (e( cEY oND
(1)
where D -N is Gaussian probability distribution in IRd for randomized smoothing, returns whichever class f is most likely to return when r is perturbed by noise E.
Let Po(x) be the output probability of f over class i... Po(x)= = _Pe - (f c). c). Without loss of generality, assume that (x)) and (a) are the probabilities on the most probable class and the runner-up class cp respectively. If (f(z + CA) 2 PA 2 PB 2 maxeşca (Pf((x + = c). where PA (x) is lower bound of (I:) and pa (x is upper bound of (z)),, then g(x + 5) CA for V5 E R ||8||2 I R. In this case, the smoothed classifier can always output the correct prediction long the perturbation ō ís within certified -orm radius of R.
Theorem 1. Let Rd y be any deterministic random function, and let N (0, Let g be defined as in (1). Suppose E and PA PB E [0, 1] satisfy (23)
Pff = CA) PA 2 PB max
(2)
ofea
Then g(x 5) ca for all ||ō|| < R, where
R
(pa) x -1 (pn)
(3)
where Φ-1 is the inverse of the standard Gaussian CDF
2.2 Machine Unlearning
Machine unlearning aims to enable the trained models to forget what has been learned from the data to be removed. Specifically, given a training dataset of N samples
{æ,, y: Each sample I; Fd is associated with a label y E y {1,2, 2, ..., Y). where is the number of classes. classification model M (D) is trained on the complete training dataset D.
The users submit data removal request at any time. Thus, the complete training data D is partitioned into two subsets: D, C D denoting the data which we wish the classification model to forget and D, D specifying the data which
the model to remember (D) Dy U D,). The goal of machine unlearning is to unlearn the forgotten data Dy, i.e., eliminate the influence of Dy from M (D). straightforward solution is to use the remembered data D, as the training data to retrain a new classification model M, (D,) from scratch. However, this naive method is often time-consuming over large-scale datasets. An efficient algorithm is to directly generate sanitized model (D, Dy. .M) from the deployed model M MD) that approximates M, MD,)),, i.e.,
MD M) ~ M,(D,)
(4)
3

---

Randomized Data Smoothing and Gradient Quantization
The idea of this work is establish connection between randomized smoothing for certified robustness on classification and randomized smoothing for certified machine unlearning gradient quantization. By leveraging the theory of randomized smoothing and gradient quantization, we theoretically derive the certified radius R regarding the perturbation surrounding the data average B and the certified budget B of data removals.
The gradient G(v, v) E R of a machine learning model is given as follows.
G(x,y) v) aC(z, y:
(5)
Ow
where C is the loss function, e.g., cross-entropy for image classification. w is the model parameter.
We propose to quantize each dimension (t 1, T) of the continuous gradient G(z, E IR" over a discrete three-class space {-1, 0, 1}, for mimicking the classification in the randomized smoothing for certified robustness.
Q(t) So -1,,
(6)
where ((t) maps gradient dimension to a dinee-iimenional vector 1- - + I
where each component denotes the similarity score between = 0, 0². the standard deviation of the Gaussian probability distribution in the randomized smoothing and also serves a quantization threshold in our method. The details of the selection of quantization threshold are presented in Appendix A.2 Therefore, all T gradient dimensions are partitioned into three intervals: (-20- -02 /2] that comes near to -a? 1-a² /2, o²/2) that is closer and [a²/2, oo) that approaches o². Each component in Qt) with the Softmax function also represents the probability of the gradient dimension belonging to classes -1, O, 1. The most probable class сд E (-1,0, 1} in (t) is assigned to dimension & as final quantized gradient dimension.
We represent the composition F(z y) of gradient computation and quantization follows.
F(x,y) = Q(G(2, v))
We use F* y) to denote the output three-dimensional quantization vector of the ( (1 = 1,... dimension of the gradient G y) and use (2, y) to represent the et (c 1- 1}) component of Ft (x. y).
As the data removal treated as the noise on the entire training data, we use the average 7 of all data samples to represent the entire training data.
1 N
Σ 3z y
1
Σ
I
where ÿ the average of the class labels of all data samples. The randomized data smoothing for certified unlearning on gradient quantization is defined below.
(* = argmax cEf -60-100))
(F Ex, Ex, +Ey = cc
(9)
where = -V (1) is a Gaussian distribution. St is a smoothed version of a base gradient quantizatier Fr that maps the tth gradient dimension about inputs (z, g) to gradient classes e E 1,. St returns whichever class Ftt is most likely to return when (z, ū) is perturbed by Ey))
=N(00021
The randomized smoothing method needs to sample a large number of points surrounding the input data for producing high confidence certificates, e.g., 10 samples for 99.9% confidence (23 In our context, computing the gradients for massive samples extremely inefficient. We utilize the Taylor expansion to approximate the output gradients of sampled points, based the outputs from

---

the original sample (z. g). For each quantization component (2, ÿ) for sample in Gaussian
distribution surrounding (z, g). where å Ez, 1 y + Eg. Exi Ey D, we take the Taylor
expansion of Fx (2, û) at (z. D) as follows.
OF
OF (z, ( g)+
(2) -F +
(z, () 3) +
dr
1
8 (T, 1)
8 F (5 =) 5)
F 1)
+ 2
( x)² 2
(i)
5))
dr
Erdy
Oy²
+ (,
(10)
where (, 1 1Σ E
F By
x)* g)-t1++,,...) (0.
3. .. 00, and k = 1,2.3.
The following theorem derives the error introduced by the Taylor expansion.
Theorem 2. The evvor introduced by the Taylor expansion of (.. D) (a.0) is
20 Lj+1
Σ
(11)
G+1)1
j=0
where Lj maxk 1.
8
and M is the number of sampled points.
Dy
Please refer to Appendix A.4 for detailed proof of Theorem
Notice that
(( = (()) / ((
diddd
( 9) c-(01,0,1)
max
(12)
Thus, derive the probabilities PA and pg the most probable class сд and the runner-up class en in the randomized smoothing for certified machine unlearning (Ca,CB E {-1, 1}), based on the error introduced by the Taylor expansion.
e)dådj, == CA ( (
PA max (f) -c) -))
(13)
3E -.(-1,0.1)
( + / ((F)(E + eddddj c Ca
PB = maxP
(14)
cgea
Notice that the correlation between the data 7 and its classes is fixed for given dataset. We denote this correlation as ÿ = (i) where H [Rd + C. Thus, the randomized smoothing for certified machine unlearning in Eq. ( is rewritten an equivalent one follows.
51(Z) argmax P (F cE( cE(-1,01)E-D
(15)
where (())) =
-
Based the computed PA PE. and (z), can obtain the certified radius R regarding the perturbation surrounding z and the certified budget of data removal.
Theorem 3. Let D N (0, 02)) and (*)) = argmax P (F* + = c). Suppose that cE(-1.0.1]50D
for a specific & E Rd, there exist eΛ (-1,0, 1} and Pn E [0, 1] such that:
(F ( = cA) 2PA 2
PB > max P( F ( =
(16)
SfA
5

---

Then (1 + = for all ||0|| < R. where
R= (0-1 (Pa) -- (pn) 2
(17)
where Φ- is the inverse of the standard Gaussian CDF.
Theorem Let R the certified radius of & I2d based on (t) argmax (F = c).
cE(-1.0.]END)
then the certified budget of data removals is
9do²
BSN-
(18)
R
Please refer to Appendix A.4 for detailed proof of Theorems
anddd
The above method is effective for certified machine unlearning, but it is computationally expensive to calculate high-dimensional double integrals in PA and Pg. We can reduce the double integrals to the single integrals through ij (T). However, H is essentially multi-valued non-continuous mapping, which is not an integrable function and makes the above method impractical.
PA | P(FA(G c)d = - P(F H()) c)dă, c = Ca
(19)
4 Randomized Gradient Smoothing and Quantization
In order to avoid the dilemma of computing practical PA: PB and R, we propose feasible solution based on randomized gradient smoothing and gradient quantization. We theoretically demonstrate the certified radius R' regarding the gradient perturbations. We recognize the correlations between R and Ht' and between and R, which are used to derive the certified budget about H'.
We first calculate the gradient G(x,, yi) in terms of each sample (I,, and the gradient average G.
G =
Σ
G(I,, 8s)
(20)
(D.D))ED
The randomized gradient smoothing for certified unlearning on gradient quantization is defined below.
(t) argmax cE(-1.01jEND
(Q) =
(21)
where D - (0, is Gaussian distribution. Str is smoothed version of base gradient quantizatier Q' that maps each dimension of the gradient G to gradient classes c {-1, 1). S returns whichever gradient class Q' is most likely to return when G is perturbed by noise E.
We compute the probabilities over three intervals of (-oc, o /2], o- /2, 02 /2], and o /2, o0).
-
P= /
P= c
2m e 20 dz,
0/22 c 2o
dz,
e 2o dz
(22)
2
- àà
Now, we can directly generate the corresponding probabilities p'a and p'z.
P'A max P. P/ max (P- (p'Aa)
(23)

---

By following the similar strategy in Theorem 3 we can derive the corresponding certified radius R'. Namely, G 6) = сд for all |8|12 < R', where
R'
④
PBB
(24)
However, it is difficult to obtain the corresponding certified budget of data removal from R', since R' related the perturbations over the gradient G, instead of the data E. The following theorem demonstrates the correlation between two types of radii R and R'.
Theorem 5. Let R and R' be the certified radii the above algorithms respectively and I. be the Lipschitz constant of gradient G( y) E R², then
VT R2 L
(25)
By combining Theorems 4 and together, we derive the certified budget B' of data removal from R'.
36dL2
S T($-I(pA)) 4 "
(26)
In addition, conduct the convergence analysis of our prompt certified machine unlearning algorithm based on randomized gradient smoothing and quantization.
Theorem 6. Let St be the randomized gradient smoothing for certified machine unlearning gradient quantization, L. L1. and L2 be the Lipschitz constants of G. Q', and S respectively, i.e.,
(b))
-
& L2L, - bll2 for any a, b
(77)
we run gradient descent for i iterations with fixed step size inght to it will yield solution gu(() which satisfies
(h) 5" (0) 1
(28)
2sk
where (0) is the initial solution and (g)))) ) is the local optimal solution.
This means that gradient descent is guaranteed converge and that it converges with rate (1/k))
Please refer to Appendix A.4for for detailed proof of T'Therrems 5and
Finally, integrate the model training for specific learning task (c.g.. image classification) randomized gradient smoothing, and gradient quantization into a unified framework for directly training machine unlearning model with the data removal certificates that the model parameters and gradients keep unchanged against the data removals within the certified budget. The corresponding parameter update is given below.
guidance, for guaranteeing
m) (G)
(29)
where w is the model parameter and is a learning rate.
Experimental Evaluation
In this section, we have evaluated the effectiveness of our PCMU model and other comparison methods for machine unlearning over three popular image classification datasets: Fashion-MNIST [138] (50]
377, CIFAR-10 [66 44 121 50 37 and SVHN 955 49 7 train the classifiers on the training
set and test them on the test set for three datasets. We train convolutional neural network (CNN) on
Fashion-MNIST for clothing classification. We train LeNet over CIFAR-10 for image classification. We apply the ResNet-18 18 architecture on SVHN for street view house number identification. We
7

---

Table I: Performance with 10% data removal and CNN Fashion-MNISTT
Performance Prror,
Runtime (s)
Metric
Accuracy
Error,
Prror,
Training
Unlearning
Total
Retrain
88.50
11.50
8,92
11.41
687
629
1,316
Fisher
86.23
13.77
12.61
13.33
671
2,015
2,686
certified removal
77.70
22.30
90.11
89.87
181
900
DeltaGrad
84.22
15.78
14.36
15.27
553
141
694
NTK
86.02
13.98
12.81
13.25
671
1,879
2,550
Unrolling SGD
83.44
16.56
41.13
41.00
356
63
419
SISA
84.46
15.54
14.59
14.52
1,419
1,387
2,806
Adaptive Unlcarning
86.02
13.98
12.80
13.25
1,537
1,481
3,018
FedEraser
69.86
30.14
29.88
28.14
677
608
1,285
MCMC unlearning
85.29
14.71
6.62
58.73
621
803
1,424
PCMU
88.34
11.66
10.68
10.71
802
802
Table 2: Performance with 20% data removal and CNN on Pashion-MNIST
Performance
Runtime (s)
Metric
Accuracy
Error, Error,
Error,
Training
Unlearning
Total
Retrain
88.21
11.79
9.75
11.76
687
561
1,248
Fisher
86.02
13.98
12.80
13.25
1,939
2,766
certified removal
76.69
23.31
90.29
89.82
711
347
1,058
DeltaGrad
84.11
15.89
14.73
13.21
570
140
710
NTK
86.03
13.97
12.81
13.25
827
1,807
2,634
Unrolling SGD
85.56
14.44
38.27
37.50
371
65
436
SISA
83.90
16.10
14.64
14.71
1,419
1,351
2,770
Adaptive Unlcarning
75.13
24.87
25.37
25.19
1,537
1,419
2,956
FedEraser
71.93
28.07
27.07
27.13
654
586
1,240
MCMC unlearning
84.52
15.48
6.95
63.02
995
778
1.773
PCMU
88.34
11.66
10.25
11.47
802
802
evaluate the performance of various machine unlearning methods on three datasets with the ratio of data removal between 5% and 20%. In this work, by following several representative machine unlearning methods 7 50 [4 where each learning request is modeled
random draw from the training data terms of a uniform distribution. Given a ratio data removal, the forgotten data D, are sampled uniformly from the complete training data D with this ratio. The remaining dataset D, D, U D,.) will be considered as the remembered data. This sampling approach is more realistic since removal request may be applied to any data examples with the same probability.
(i.e.. =
Baselines. We compare the PCMU model with nine state-of- thrt--rrt machine unlearning models. Fisher is scrubbing procedure that removes information from the trained weights, without the need access the original training data, nor retrain the entire network (43. certified removal provides a strong theoretical guarantee that model from which data is removed cannot be distinguished from a model that never observed the data to begin with 49 DeltaGrad is a rapid retraining machine learning model based information cached during the training phase [136]. NTK removes dependency on cohort of training data from trained deep network that improves upon and generalizes previous methods to different readout functions 44 Unrolling SGD is taxonomy of approximate unlearning which concludes with verification error as metric to study as it subsumes a large class of unlearning criteria [12]]. SISA is practical approach for unlearning that relies data sharding and slicing to reduce the computational overhead unlearning 77] Adaptive Unlearning gives general reduction from deletion guarantees against adaptive sequences to deletion guarantees against non-ade hon-adaptive sequences. [50]. FedEraser a federated unlearning methodology that can eliminate the influences of federated client's s data the global model while significantly reducing the time consumption [79]. MCMC unlearning designs an MCMC influence function to characterize the knowledge learned from data, which then delivers the MCMC unlearning algorithm 37 To best knowledge, this work is the first to execute one-time operation of simultaneous training and unlearning advance for a series of machine unlearning requests.
Variants of PCMU model. We evaluate two versions of PCMU to show the strengths of different techniques. PCMU-N uses the basic model with only the gradient quantization. PCMU operates with the full support of both the randomized gradient smoothing and the gradient quantization techniques. Notice that the gradient quantization is necessary operation to convert continuous gradients to discrete gradient classes for the randomized gradient smoothing in our PCMU model. Thus, we cannot validate the version with only the randomized gradient smoothing.
Evaluation metrics. By following the same settings several representative machine unlearn- ing models 43 44 121 37), we use four popular measures in machine unlearning to verify the

---

Table 3: Performance with 10% data removal and LeNet on CIFAR-10
Performance
Runtime (s)
Metric
Accuracy
Error,
Error,
Error,
Training
Unlearning
Total
Retrain
64.31
35.69
27.44
36.16
846
745
1.591
Fisher
62.39
37.61
33.76
33.78
693
2189
2,882
certified removal
36.91
63.09
90.02
89.66
749
174
923
DeltaGrad
61.46
38.54
23.12
23.92
493
1,352
NTK
62.36
37.64
33.76
35.44
693
2,047
2,740
Unrolling SGD
59.69
40.31
41.69
49.80
511
168
679
SISA
58.01
41.99
34.01
34.40
1,594
1,533
3,127
Adaptive Unlearning
43.35
56.65
55.80
55.21
1,176
293
1,469
FedEraser
51.63
48.37
43.57
48.62
1,190
984
2,174
MCMC unlearning
60.70
39.30
4.53
26.98
1,322
718
2,040
PCMU
64.33
35.67
24.21
37.68
903
0
903
Table 4: Performance with 20% data removal and LeNet on CIFAR-10
Performance
Runtime (s)
Metric
Accuracy Error, Error, Error
Training Unlcarning
Total
Retrain
63.29
36.71
24.59
36.89
846
673
1,519
Fisher
Failed due to out of memory
Failed due to out of memory
certified removal
36.03
63.97
90.14
89.84
749
430
1,179
DeltaGrad
61.55
38.45
22.61
22.20
864
499
1,363
NTK
Failed due to out memory
Failed due to out memory
Unrolling SGD
60.39
39.61
40.17
47.00
511
327
838
SISA
57.17
42.83
35.75
35.74
1,594
1,465
3,059
Adaptive Unlearning
41.23
58.77
57.52
59.22
1,176
321
1,497
FedEraser
51.66
48.34
48.53
50.14
1,190
980
2,170
MCMC unlcarning
61.33
38.67
5.29
30.42
1,322
714
2,766
PCMU
64.33
35.67
25.18
35.32
903
0
903
performance of different methods: Accuracy, Errory (classification errors on the forgortten data Dj), Error, (errors on the remembered data D,), and Error, (errors on the test data). Since the model (D,),) (Retrain) that uses only the remembered data D, the training data retrained from scratch has never seen the forgotten data D,, it is usually used as the gold standard for evaluating the performance of machine unlearning algorithms
43 37). Ideally, the accuracy and three errors the unlearning models should match that of the retrained model (D,)).
Machine unlearning accuracy with varying ratios of data removal. Tables 1 exhibit the accu- racy obtained by eleven machine unlearning approaches by varying the ratio of unlearning request / data removal between 10% and 20%. Retrain represents the model retrained only the remembered data D, from scratch, without the knowledge of the forgotten data D,. A machine unlearning algorithm with more similar performance to the Retrain model achieves a better unlearning result. is observed that among ten approaches except the Retrain model, no matter how large the ratios of data removal are, the PCMU method achieves the closest accuracy the Retrain model in all tests, showing the effectiveness of PCMU to the machine unlearning. Compared to the absolute performance difference between other baselines and the Retrain model, PCMU, on average, achieves at least 5.56% and 15.17% improvement of absolute accuracy difference on Fashion-MNIST and CIFAR-10 respectively. Notice that the accuracy and error on test data by our PCMU keep unchanged since it performs one-time operation of simultaneous training and unlearning for addressing multiple unlearning requests. addition, the promising performance of PCMU over Mushion-MNISS and CIFAR-10 10 implies that PCMU has great potential as general machine unlearning solution to other image datasets, which desirable in practice.
Machine unlearning error with varying ratios of data removal. Tables also show the clas- sification errors on the deleted data Dy (Errory), errors on the remembered data D, (Error,), and errors on the test data (Error,) by eleven machine unlearning methods respectively. We have observed that the performance of our PCMU method behaves similarly and achieves at least 13.73% and 16.01% % boost of absolute error difference on two datasets respectively. PCMU substantially outperforms the performance of other baselines in most experiments, especially on the CIFAR-11 10 dataset. In addition, the errors by our PCMU are not sensitive to the ratio of data removals. This is because that our PCMU method performs one-time operation of simultaneous training and unlearning when addressing a series of machine unlearning requests, long the ratio of actual data removals below the certified budget of data removals our PCMU. However, other baselines need to sequentially handle these machine unlearning requests by one.

---

Farran POMU-X
POWL-M PONU
PCNU
PONU
2014
Datssot
Dataset
Datooet
Star Deviiioe
Doa
(a) Accuracy
(b) Error,
(c) Errory
(a) Standard (eviation(b) Data Removal (%)
Figure 1: Performance of PCMU variants with 20% data
Figure 2: Performance with varying pa-
removal on two datasets
rameters
Ablation study. Figure I exhibits the unlearning performance with the Retrain model and two variants of the PCMU model over two datasets of Fashion-MNIST and CIFAR-10 respectively. We have observed the exact PCMU achieves the closest accuracy and errors the Retrain model over two datasets, which are obviously better than PCMU-N. A reasonable explanation is that our PCMU method utilizes the randomized gradient smoothing and gradient quantization techniques for supporting certified machine unlearning. It further uses the certificates guidance to train the machine unlearning model, for guaranteeing that model parameters and gradients keep unchanged against the data removals within the certified budget.
Running time. Tables report the running time achieved by all comparison methods over two dataset to produce machine unlearning results respectively. We observe that PCMU scales well with deep neural network architectures over different image datasets and shows good efficiency for machine unlearning. Our PCMU method achieves better efficiency than most baseline methods, except DeltaGrad and Unrolling SGD, As discussed above, our PCMU method performs one-time operation of simultaneous training and unlearning when addressing series of machine unlearning requests. However, DeltaGrad and Unrolling SGD need to sequentially handle these machine unlearning requests one by one. This is clearly computationally expensive process when the number of machine unlearning requests is huge.
Impact of standard deviation. Figure 2 measures the performance effect of standard deviation of the Gaussian distribution in the randomized smoothing for machine unlearning by varying from 0.025 to 0.3. Notice that the Retrain and PCMU-N models do not contain the module of randomized smoothing. Thus, their accuracy scores keep unchanged with varying a. We have witnessed the performance curves by PCMU initially increase quickly and then become stable or even slight drop when a continuously increases. Initially, a large a can help utilize the strength randomized gradient smoothing and quantization for directly training machine unlearning model in advance. Later on, when a continues to increase and goes beyond some thresholds, the performance curves become stable. A rational guess is that after the data removals have been already certified a certain threshold and considered in the training of machine unlearning models, our PCMU model is able to generate a good machine unlearning result. When continuously increases, this does not affect the performance of machine unlcarning any more.
Impact of data removal ratio. Figure 2 (b) evaluates the accuracy impact of data removal ratios varying from 5% to 20% on three datasets of Dishion-MNIST. CIFAR-10, 10, and SVHN. It is observed that when changing data removal ratios, the accuracy by our PCMU model matchs well with that of the retrained model from scratch. The performance by our PCMU model keeps relatively stable, since our method directly trains unlearning model based the certified budget of data removals in advance and performs one-time operation of simultaneous training and unlcarning, as long as the ratio of actual data removals is below the certified budget of data removals.
6 Conclusions
In this work, we have proposed prompt certified machine unlearning algorithm that executes one- time operation of simultaneous training and unlcarning in advance. First, we establish a connection between randomized smoothing for certified robustness classification and randomized smoothing for certified machine unlearning on gradient quantization. Second, we propose a certified machine unlearning model based on randomized data smoothing and gradient quantization. Finally, present another practical framework of randomized gradient smoothing and quantization, due to the dilemma of producing high confidence certificates in the first framework.
10

---

References
[1] M. Alfarra, Bibi, Khan, P. H. S. Torr, and B. Ghanem. Deformrs: Certifying input deformations with randomized smoothing. In Proceedings of the 36th AAAI Conference on Artificial Intelligence, (AAAI 22), February 22-March 1, 2022, Vancouver, Canada, 2022.
[2] C. Anil, J. Lucas, and R. B. Grosse. Sorting out lipschitz function approximation. In Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA, pages 291-301, 2019.
[3] X. Bao, L. Liu, N. Xiao, Y. Zhou, and Q. Zhang. Policy-driven autonomic configuration management for nosql. In Proceedings of the 2015 IEEE International Conference on Cloud Computing (CLOUD' 15), pages 245, New York, NY, June 27-July 2015.
[4] T. Baumhauer, P. Schöttle, and M. Zeppelzauer. Machine unlcarning; Linear filtration for logit-based classifiers. CoRR, abs/2002.02730, 2020.
[5] A. Blum, T. Dick, N. Manoj, and H. Zhang. Random smoothing might be unable to certify loo robustness for high-dimensional images. J. Mach. Learn. Res., 21:211:1-211:: 2020.
[6] Bojchevski, J. Klicpera, and S. Günnemann. Efficient robustness certificates for discrete data: Sparsity-aware randomized smoothing for graphs, images and more. In Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 12-18 July 2020, 2020.
[7] L. Bourtoule, V. Chandrasekaran, C. Choquette-Choo,, H. Jia, A. Travers, B. Zhang, D. Lie, and N. Papernot. Machine unlearning. In Proceedings of the 42nd IEEE Symposium on Security and Privacy, 2021.
[8] J. Brophy and D. Lowd. Machine unlearning for random forests. In M. Meila and T. Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event, volume 139 of Proceedings of Machine Learning Research, pages 1 199--1044. PMLR, 2021.
[9] Bunel, I. Turkaslan, P. H. S. Torr, P. Kohli, and P. K. Mudigonda. A unified view of piecewise linear neural network verification. In Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurIPS 2018, 3-8 December 2018, Montréal, Canada, pages 4795-4804, 2018
[10] Y. Cao and J. Yang. Towards making systems forget with machine unlearning, In 2015 IEEE Symposium on Security and Privacy, SP 2015, San Jose, CA, USA, May 17-21, 2015, pages 463-480. IEEE Computer Society, 2015.
[11] N. Carlini and D. A. Wagner. Adversarial examples are not easily detected: Bypassing ten detection methods. In Proceedings of the 10th ACM Workshop Artificial Intelligence and Security, AlSec @ CCS 2017, Dallas, TX, USA, November 3, 2017, pages 3-14, 2017.
[12] G. Cauwenberghs and T. A. Poggio. Incremental and decremental support vector machine learning. In T. K. Leen, T. G. Dietterich, and V. Tresp, editors, Advances in Neural Information Processing Systems 13, Pupers from Neural Information Processing Systems (NIPS) 2000, Denver, CO, USA, pages 409-415. MIT Press, 2000.
[13] C. Chen, B. Kailkhura, R. A. Goldhahn, and Y. Zhou. Certifiably-robus federated adversarial learning via randomized smoothing. In IEEE 18th International Conference on Mobile Ad Hoc and Smart Systems, MASS 2021, Denver, CO, USA, October 4-7, 2021, pages 173-179. IEEE, 2021.
[14] C. Chen, F. Sun, M. Zhang, and B. Ding. Recommendation unlearning. In F. Laforest, R. Troncy, E. Simperl, D. Agarwal, A. Gionis, Herman, and L. Médini, editors, WWW '22: The ACM Web Conference 2022, Virtual Event, Lyon, France, April 25 29, 2022, pages 2768-2777. ACM, 2022.
[15] M. Chen, Zhang, T. Wang, M. Backes, M. Humbert, and Y. Zhang. When machine unlearning jeopardizes privacy. In Y. Kim, J. Kim, G. Vigna, and E. Shi, editors, CCS '21: 2021 ACM SIGSAC Conference on Computer and Communications Security, Virtual Event, Republic of Korea, November 15 19, 2021, pages 896-911. ACM, 2021.
11

---

[16] R. Chen, J. J. Yan, P. Li, and B. Sheng. Input-specific robustness certification for randomized smoothing. In Proceedings of the 36th AAAI Conference on Artificial Intelligence, (2)) February 22-March 1, 2022, Vancouver, Canada, 2022.
[17] Y. Chen, J. Xiong, W. Xu, and J. Zuo. A novel online incremental and decremental learning algorithm based on variable support vector machine. Clust. Comput., 22(Supplement)7433 7445, 2019.
[18] C. Cheng, G. Nührenberg, and H. Ruess. Maximum resilience of artificial neural networks. In Automated Technology for Verification and Analysis 15th International Symposium, ATVA 2017, Pune, India, October 3-6, 2017, Proceedings, pages 251-268, 2017.
[19] P. Chiang, R. Ni, A. Abdelkader, C. Zhu, C. Studer, and T. Goldstein. Certified defenses for adversarial patches. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020, 2020.
[20] V. S. Chundawat, A. K. Tarun, M. Mandal, and M. S. Kankanhalli. Zero-shot machine 2022.
unlearning. CoRR,
[21] M. Cissé, P. Bojanowski, E. Grave, Y. N. Dauphin, and N. Usunier. Parseval networks: Improving robustness to adversarial examples. In Proceedings of the 34th International Conference Machine Learning, ICML 2017, Sydney, NSW, Australia, 6-11 August 2017, pages 854-863, 2017.
[22] E. J. Cohen, T. Huster, and R. Cohen. Universal lipschitz approximation in bounded depth neural networks. CoRR,
2019.
[23] J. M. Cohen, E. Rosenfeld, and J. Z. Kolter. Certified adversarial robustness via randomized smoothing. In Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA, pages 1310-1320, 2019.
[24] F. Croce, M. Andriushchenko, and M. Hein. Provable robustness of relu networks via maxi- mization of linear regions. In The 22nd International Conference on Artificial Intelligence and April 2019, Naha, Okinawa, Japan, pages 2057-2066, 2019
Statistics, AISTATS 2019, 16- 18
[25] S. Dutta, S. Jha, S. Sankaranarayanan and A. Tiwari. Output range analysis for deep feedfor- ward neural networks. In NASA Formal Methods 10th International Symposium, NFM 2018, Newport News, VA, USA, April 17-19, 2018, Proceedings, pages 121-138, 2018.
[26] K. Dvijotham, S. Gowal, R. Stanforth, R. Arandjelovic, B. O' O'Donoguue, J. Uesato, and P. Kohli. Training verified learners with learned verifiers. CoRR, abs/ 805.8005.... 2018
[27] K. Dvijotham, R. Stanforth, S. Gowal, T. A. Mann, and P. Kohli. A dual approach to scalable verification of deep networks. In Proceedings of the Thirty-Fourth Conference on Uncertainty in Artificial Intelligence, UAI 2018, Monterey, California, USA, August 6-10, 2018, pages 550 100-559,770 2018
[28]
K. D. Dvijotham, J. Hayes, B. Balle, J. 7. Kolter, C. Qin, A. György, K. Xiao, S. Gowal, and P. Kohli. A framework for robustness certification of smoothed classifiers using f-divergences. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020, 2020.
[29] R. Ehlers. Formal verification of piece-wise linear feed-forward neural networks. In Automated Technology for Verification and Analysis 15th International Symposium, ATVA 2017, Pune, India, October 3-6, 2017, Proceedings, pages 269-286, 2017.
[30] M. Fazlyab, A. Robey, H. Hassani, M. Morari, and G. J. Pappas. Efficient and accurate estimation of lipschitz constants for deep neural networks. In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, 8-14 December 2019, Vancouver, BC, Canada, pages 11423-11434, 2019.
12

---

[31] H. Feng, C. Wu, G. Chen, W. Zhang, and Y. Ning, Regularized training and tight certification for randomized smoothed classifier with provable robustness. In The Thirty-Forr Fourth AAAI Conference on Artificial Intelligence, AAAI 2020, The Thirty-Second Innovative Applications of Artificial Intelligence Conference, IAAI 2020, The Tenth AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2020, New York, NY, USA, February 7-12, 2020, pages 3858-3865, 2020.
[32] M. Fischer, M. Baader, and M. T. Vechev. Certified defense image transformations via randomized smoothing. In Advances in Newral Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurlPS 2020, December 6-12 6-1 2020, virtual, 2020.
[33] M. Fischer, M. Baader, and M. Vechev. Scaleable certified segmentation via randomized smoothing. In Proceedings of the 38th International Conference on Machine Learming, ICML 2021, 18-24 July 2021, Virtual Event, 2021.
[34] M. Fischetti and Jo. Deep neural networks and mixed integer linear optimization. Constraints An Int. J., 23(3):296-309, 2018.
[35] M. Fredrikson, S. Jha, and T. Ristenpart. Model inversion attacks that exploit confidence information and basic countermeasures. In I. Ray, N. Li, and C. Kruegel, editors, Proceedings of the 22nd ACM SIGSAC Conference Computer and Communications Security, Denver, CO, USA, October 12-16, 2015, pages 1322-1333. ACM, 2015.
[36] A. Fromherz, K. Leino, M. Fredrikson, B. Parno, and C. Pasareanu. Fast geometric projections for local robustness certification. In 9th International Conference on Learning Representations, ICLR 2021, Online, May 4-7, 2021, Conference Track Proceedings. 2021.
[37] S. Fu, F. He, and D. Tao. Knowledge removal in sampling- based bayesian inference. In 10th International Conference on Learning Representations, ICLR 2022, Online, April 25-29, 2022, Conference Track Proceedings, 2022.
[38] Z. Gao, R. Hu, and Y. Gong. Certified robustness of graph classification against topology attack with randomized smoothing. In 2020 IEEE Global Communications Conference, GLOBECOM 2020, Taipei, Taiwan, December 8-10, 2020, 2020.
[39] S. Garg, S. Goldwasser, and P. N. Vasudevan. Formalizing data deletion in the context of the right to be forgotten. In A. Canteaut and Y. Ishai, editors, Advances in Cryptology EUROCRYPT 2020- 39th Annual International Conference on the Theory and Applications of Cryptographic Techmiques, Zugreb, Croatia, May 10-14, 2020, Proceedings, Part II, volume 12106 of Lecture Notes in Computer Science, pages 373-402. Springer, 2020.
[40] T. Gehr, M. Mirman, D. Drachsler-Cohen, P. Tsankov, S. Chaudhuri, and M. T. Vechev. A12: safety and robustness certification of neural networks with abstract interpretation. 2018 IEEE Symposium on Security and Privacy, SP 2018, Proceedings, 21-23 May 2018, San Francisco, California, USA, pages 3-18, 2018
[41] A. Ghiasi, A. Shafahi, and T. Goldstein. Breaking certified defenses: Semantic adversarial examples with spoofed robustness certificates. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020, 2020.
[42] A. Ginart, M. Y. Guan, G. Valiant, and J. Zou. Making AI forget you: Data deletion in machine learning. In H. M. Wallach, H. Larochelle, A. Beygelzimer, F. d' Alché-Buc, B. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, December 8- 14, 2019, Vancouver, BC, Canada, pages 3513-3526 2019.
[43] A. Golatkar, A. Achille, and Soatto. Eternal sunshine of the spotless net: Selective forgetting in deep networks. In 2020 IEEE/CVF Conference Computer Vision and Pattern Recognition, CVPR 2020, Seattle, WA, USA, June 13-19, 2020, pages 9301-9309. Computer Vision Foundation/ / IEEE, 2020.
13

---

[44] A. Golatkar, A. Achille, and S. Soatto. Forgetting outside the box: Scrubbing deep networks of information accessible from imput-output observations. A. Vedaldi. H. Bischof, T. Brox, and J. Frahm, editors, Computer Vision ECCV 2020 16th European Conference, Glasgow, UK, August 23-28, 2020, Proceedings, Part XXIX, volume 12374 of Lecture Notes in Computer Science, pages 383-398. Springer, 2020.
[45] A. Golatkar, A. Achille, A. Ravichandran, M. Polito, and S. Soatto. Mixed-privaas forgetting in deep networks. In IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2021, virtual, June 19-25, 2021, pages 792-801. Computer Vision Foundation / IEEE, 2021.
[46] J. Gong, O. Simeone, and J. Kang. Bayesian variational federated learning and unlearning in decentralized networks. In 22nd IEEE International Workshop Signal Processing Advances in Wireless Communications, SPAWC 2021, Lucca, Italy, September 27-30, 2021, pages 216-220. IEEE, 2021.
[47] S. Gowal, K. Dvijotham, R. Stanforth, R. Bunel, C. Qin, J. Uesato, R. Arandjelovic, T. A. Mann, and P. Kohli. On the effectiiveness of interval bound propagation for training verifiably robust models. CoRR, abs/1810. 12715, 2018.
[48] L. Graves, V. Nagisetty, and V. Ganesh. Amnesiac machine learning. In Thirty-Fifth AAAI Conference on Artificial Intelligence, AAAI 2021, Thirty-Third Conference on Innovative Applications of Artificial Intelligence, IAAI 2021, The Eleventh Symposium on Educational Advances in Artificial Intelligence, EAAI 2021, Virtual Event, February 2-9, 2021, pages 11516-11524. AAAI Press, 2021.
[49] C. Guo, T. Goldstein, A. Y. Hannun, and L. van der Maaten. Certified data removal from machine learning models. In Proceedings of the 37th International Conference on Machine Learning. ICML 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pages 1832-3842 PMLR, 2020.
[50] V. Gupta, C. Jung, S. Neel, A. Roth, S. Sharifi- Sharifi- Malvajerdi, and C. Waites. Adaptive machine unlearning. In M. Ranzato, A. Beygelzimer, Y. N. Dauphin, P. Liang, and J. W. Vaughan, editors, Advances in Neural Information Processing Systems 34; Annual Conference on Neural Information Processing Systems 2021, NeurlPS 2021, December 6-14, 2021, virtual, pages 16319-16330, 2021.
[51] J. Hayes. Extensions and limitations of randomized smoothing for robustness guarantees. In 2020 IEEE/CVF Conference on Computer Vision and Pattern Recognition. CVPR Workshops 2020, Seattle, WA, USA, June 14-19, 2020, pages 3-3311,11111 2020.
[52] K. He, X. Zhang, S. Ren, and J. Sun. Delving deep into rectifiers: Surpassing human-level performance on imagenet classification. In 2015 IEEE International Conference on Computer Vision, ICCV 2015, Santiago, Chile, December 7-13, 2015, pages 1026-1034, 2015.
[53] M. Z. Horváth, M. N. Müller, M. Fischer, and M. T. Vechev. Robust and accurate- composi- tional architectures for randomized smoothing. In 10th International Conference on Learning Representations, ICLR 2022, Online, April 25-29, 2022, Conference Track Proceedings, 2022.
[54] P. Huang, R. Stanforth, J. Welbl, C. Dyer, D. Yogatama, S. Gowal, K. Dvijotham, and P. Kohli. Achieving verified robustness to symbol substitutions via interval bound propagation. In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing, EMNIPP-JCNIPP 2019, Hong Kong, China, November 3-7, 2019, pages 4081-4091, 2019.
[55] X. Huang, M. Kwiatkowska, S. Wang. and M. Wu. Safety verification of deep neural networks. In Computer Aided Verification 29th International Conference, CAV 2017, Heidelberg, Germany, July 24-28, 2017, Proceedings. Part I, pages 3-29, 2017.
[56] Z. Izzo, M. A. Smart, K. Chaudhuri, and Zou. Approximate data deletion from machine learning models. In A. Banerjee and K. Fukumizu, editors, The 24th International Conference on Artificial Intelligence and Statistics, AISTATS 2021, April 13-15, 2021, Virtual Event, volume 130 of Proceedings of Machine Learning Research, pages 2008-2016 PMLR, 2021.
14

---

[57] J. Jeong and J. Shin. Consistency regularization for certified robustness of smoothed classifiers. In Advances Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurlPS 2020, December 12, 2020, virtual, 2020.
[58] J. Jia, X. Cao, B. Wang, and N. Z. Gong. Certified robustness for top-k predictions against adversarial perturbations via randomized smoothing. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020, 2020.
[59] J. Jia, X. Cao, and N. Z. Gong. Intrinsic certified robustness of bagging against data poisoning attacks. In Proceedings of the Thirty-Fifth AAAI Conference on Artificial Intelligence, AAAI 2021, 2021.
[60] J. Jin, J. Ren, Y. Zhou, L. Lv, J. Liu, and D. Dou, Accelerated federated learning with decoupled adaptive optimization. In Proceedings of the 39th International Conference on Machine Learning (ICML' (2)), pages
Baltimore, MD, July 17-23 2022.
[61] J. Jin, 7. Zhang, Y. Zhou, and I.. Wu. Input-agnostic certified group fairesss via gaussian parameter smoothing. In Proceedings of the 39th International Conference on Machine Learning (ICML'22) (2,, pages 10340-10361, Baltimore, MD, July 17-23 2022.
[62] M. Karasuyama and I. Takeuchi. Multiple incremental decremental learning of support vector machines. In Y. Bengio, D. Schuurmans, J. D. Lafferty, C. K. I. Williams, and A. Culotta, editors, Advances in Neural Information Processing Systems 22: 23rd Annual Conference on Neural Information Processing Systems 2009. Proceedings of meeting held 7-10 December 2009, Vancouver, British Columbia, Canada, pages 907-915. Curran Associates, Inc., 2009.
[63] G. Katz, C. W. Barrett, D. L. Dill, K. Julian, and M. J. Kochenderfer. Reluplex: An efficient SMT solver for verifying deep neural networks. In Computer Aided Verification 29th International Conference, CAV 2017, Heidelberg, Germany, July 24-28, 2017, Proceedings, Part I, pages 97-117, 2017.
[64] M. E. Khan and S. Swaroop. Knowledge-adaptation priors. In M. Ranzato, A. Beygelzimer, Y. N. Dauphin, P. Liang, and J. W. Vaughan, editors, Advances in Neural Information Process- ing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurlPS 2021, December 6-14, 2021, viriual, pages 19757-19770, 2021.
[65] V. Krishman, A. A. A. Makdah, and F. Pasqualetti. Lipschitz bounds and provably robust training by laplacian smoothing. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurlPS 2020, December 6-12, 2020, virtual, 2020.
[66] A. Krizhevsky. Learning multiple layers of features from tiny images. Technical Report, 2009.
[67] A. Kumar, A. Levine, S. Feizi, and T. Goldstein. Certifying confidence via randomized smoothing. In Advances in Neural Information Processing Systems 33: Anmual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020.
[68] A. Kumnr, A. Levine. T. Goldstein, and S. Feizi. Curse of dimensionality randomized smoothing for certifiable robustness. Proceedings of the 37th International Conference on Machine Learning. ICML 2020. 13-18 July 2020, Virtual Event, pages 5458-5461 2020.
[69] M. Lécuyer. V. Atlidakis, R. Geambasu, D. Hsu, and S. Jana. Certified robustness to adversarial examples with differential privacy. In 2019 IEEE Symposium on Security and Privacy, SP 2019, San Francisco, CA, USA, May 19-23, 2019, pages 656-672, 2019.
[70] G. Lee, Y. Yuan, S. Chang, and T. S. Jaakkola. Tight certificates of adversarial robustness for randomly smoothed classifiers. In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurlPS 2019, 8-14 December 2019, Vancouver, BC, Canada, pages
2019.
[71] C. S. Legislature. California consumer privacy act of 2018. cal. civ. code $1798. 100, 2018.
15

---

[72] A. Levine and S. Feizi. Robustness certificates for sparse adversarial attacks by randomized ablation. In The Thirty-Fourth AAAI Conference on Artificial Intelligence, AAAI 2020, The Thirty-Second Innovative Applications of Artificial Intelligence Conference, IAAI 2020, The Tenth AAAI Symposium on Educational Advances Artificial Intelligence, EAAI 2020, New York, NY, USA, February 7-12, 2020, pages 5585-4595 2020.
[73] A. Levine and S. Feizi. Deep partition aggregation: Provable defenses against general poisoning attacks. In 9th International Conference on Learning Representations, ICLR 2021, Online, May 4-7, 2021, Conference Truck Proceedings, 2021.
[74] A. Levine, A. Kumar, T. Goldstein, and S. Feizi. Tight second-order certificates for randomized smoothing. CoRR, abs/2010. 105299 2020.
[75] B. Li, C. Chen, W. Wang, and L. Carin. Second-order adversarial attack and certifiable robustness. CoRR, abs/1809) 031 13, 2018.
[76] B. Li. C. Chen, W. Wang, and L. Carin. Certified adversarial robustness with additive noise. In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurlPS 2019, 8-14 December 2019, Vancouver, BC, Canada, pages 9459-9469, 2019.
[77] Q. Li, S. Haque, C. Anil, J. Lucas, R. B. Grosse, and J. Jacobsen. Preventing gradient attenuation in lipschitz constrained convolutional networks. In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurlPS 2019, 8-14 December 2019, Vancouver, BC, Canada, pages 15364-15376 2019.
[78] Y. Li, C. Wang, and G. Cheng. Online forgetting process for linear regression models. In A. Banerjee and K. Fukumizu, editors, The 24th International Conference on Artificial Intelligence and Statistics, AISTATS 2021, April 13-15, 2021, Virtual Event, volume 130 of Proceedings of Machine Learning Research, pages 217-225. PMLR, 2021.
[79] G. Liu, X. Ma, Y. Yang, C. Wang, and J. Liu. Federaser: Enabling efficient client-level data removal from federated learning models. In 29th IEEF/ACM International Symposium on Quality of Service /WQOS 2021, Tokyo, Japan, June 25-28, 2021, pages 1-10. IEEE, 2021.
[80] J. Liu, J. Huang, Y. Zhou, X. Li, S. Ji, H. Xiong, and D. Dou. From distributed machine learning federated learning: A survey. Knowledge and Information Systems (KAIS), 64(4); 885-917, 2022.
[81] Y. Liu, Z. Ma, Y. Yang, X. Liu, Ma, and K. Ren. Revfrf: Enabling cross-domain random forest training with revocable federated learning. IEEE Transactions on Dependable and Secure Computing, 2021.
[82] Y. Liu, M. Fan, C. Chen, X. Liu, Z. Ma. L. Wang, and J. Ma. Backdoor defense with machine unlearning. In 41st IEEE Conference on Computer Communications, INFOCOM 2022, Virtual, May 2-5, 2022. IEEE, 2022.
[83] Y. Liu, L. Xu, X. Yuan, C. Wang, and B. Li. The right to be forgotten in federated learn- ing: An efficient realization with rapid retraining. In 41st IEEE Conference on Computer Communications, INFOCOM 2022, Virtual, May 2-5, 2022. IEEF, 2022.
[84] A. Lomuscio and L. Maganti. An approach to reachability analysis for feed-forwer forwwfd relu neural networks. CoRR, ftls//706.0735/ 2017.
[85] Mahadevan and M. Mathioudakis. Certifiable machine unlearning for linear models. CoRR, 0bs/2106.15093 2021.
[86] T. Maho, T. Furon, and F. L. Merrer. Randomized smoothing under attack: How good is it in pratice? In IEEE International Conference on Acoustics, Speech and Signal Processing, ICASSP 2022, Singapore, May 22-27, 2022, 2022.
[87] N. G. Marchant, B. I. P. Rubinstein, and S. Alfeld. Hard to forget: Poisoning attacks on certified machine unlearning. In Proceedings of the 36th AAAI Conference on Artificial Intelligence, (AAAI'22), February 22 22-March 1, 2022, Vancouver, Canada, 2022.
16

---

[88] A. Mehra, B. Kailkhura, P. Chen, and J. Hamm. How robust are randomized smoothing based defenses to data poisoning? In IEEE Conference on Computer Vision and Pattern Recognition. CVPR 2021, virtual, June 19-25, 2021, pages 11244-13253 Computer Vision Foundation / IEFE, 2021.
[89] J. H. Metzen and M. Yatsura. Efficient certified defenses against patch attacks on image classifiers. In 9th International Conference on Learning Representations, ICLR 2021, Online, May 4-7, 2021, Conference Track Proceedings, 2021.
[90] M. Mirman, T. Gehr, and M. T. Vechev. Differentiable abstract interpretation for provably robust neural networks. In Proceedings of the 35th International Conference on Machine Learning. ICML 2018, Stockholmsmsssan, Stockholm, Sweden, July 10-15, 2018, pages 3575-3583, 2018.
[91] J. Mohapatra, C. Ko, T. Weng, P. Chen, S. Liu, and L. Daniel. Higher-order certification for randomized smoothing. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020.
[92] J. Mohapatra, C. Ko, L. Weng, Chen, S. Liu, and L. Daniel. Hidden cost of randomized smoothing. In A. Banerjee and K. Fukumizu, editors, The 24th International Conference on Artificial Infelligence and Statistics, AISTATS 2021, April 13-15, 2021, Virtual Event, volume 130 of Proceedings of Machine Learning Research, pages 4033 4041. PMLR, 2021.
[93] M. N. Mueller, M. Balunovic, and M. Vechev. Certify or predict: Boosting certified robustness with compositional architectures. In 9th International Conference Learning Representations, ICLR 2021, Online, May 4-7, 2021, Conference Track Proceedings, 2021.
[94] S. Neel, A. Roth, and S. Sharif-MMalvajerdi Descent-to-dellte: Gradient- based methods for machine unlearning. In V. Feldman, K. Ligett, and S. Sabato, editors, Algorüthmic Learning Theory, 16-19 March 2021, Virtual Conference, Worldwide, volume 132 of Proceedings of Machine Learning Research, pages 931-962. PMLR, 2021.
[95] Y. Netzer, T. Wang, A. Coates, A. Bissacco, B. Wu, and A. Y. N. Reading digits in natu- ral images with unsupervised feature learning. In NIPS Workshop on Deep Learning and Unsupervised Feature Learning, 2011, 2011.
[96] Q P. Nguyen, B. K. H. Low, and P. Jaillet. Variational bayesian unlearning. In H. Larochelle, M. Ranzato, R. Hadsell, M. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems 33: Annual Conference Neural Information Processing Systems 2020, NeurlPS 2020, December 6- 6-12, 2020, virtual, 2020.
[97] Q. P. Nguyen, R. Oikawa, D. M. Divakaran, M. C. Chan, and B. K. H. Low. Markov chain monte varlo-based machine unlearning: Unlearning what needs be forgotten. In Proceedings of the 2022 ACM Asia Conference on Computer and Communications Security (ASIA CCS '22), May 30-June 3, 2022, Nagasaki, Japan. 2022.
[98] C. of the EU. Regulation (eu) 2016/679 of the european parliament and of the council of 27 april 2016 on the protection of natural persons with regard to the processing of personal data and on the free movement of such data, and repealing directive 95/46/ec (general data protection regulation), 2016.
[99] B. Palanisamy, L. Liu, Y. Zhou, and Q. Wang. Privacy-preservee publishing of multilevel utility-controlled graph datasets. ACM Transactions on Internet Technology (TOIT), 18(2): 24:1 24:1-24:21, 2018
[100] A. Raghunathan, J. Steinhardt, and P. Liang. Semidefinite relaxations for certifying robustness to adversarial examples. In Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurIPS 2018, December 3-8, 2018, Montréal. Canada, pages 10900-10910, 2018
17

---

[101] J. Ren, Z. Zhang, J. Jin, X. Zhao, S. Wu, Y. Zhou, Y. Shen, T. Che, R. Jin, and D. Dou. Integrated defense for resilient graph matching. In Proceedings of the 38th International Conference Machine Learning (ICMI'21), pages 8982-8997, Virtual Event, July 18-24 2021.
[102] E. Rosenfeld, E. Winston, P. Ravikumar, and J. Z. Kolter. Certified robustness to label-flippigg attacks via randomized smoothing. In Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event, pages 8230-82444 2020.
[103] A. Ruoss, M. Baader, M. Balunovic, and M. Vechev. Efficient certification of spatial robustness. In Proceedings of the Thirty-Fifth AAAI Conference on Artificial Intelligence, AAAI 2021, 2021.
[104] H. Salman, Li, I. P. Razenshteyn, P. Zhang, H. Zhang, Bubeck, and G. Yang. Provably robust deep learning via adversarially trained smoothed classifiers. In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurlPS 2019, 8- 14 December 2019, Vancouver, BC, Canada, pages 1 11289- 11300, 2019.
[105] H. Salman, G. Yang, H. Zhang, C. Hsieh, and P. Zhang. A convex relaxation barrier tight robustness verification of neural networks. In Advances in Neural Information Processing Systems 32: Annual Conference Neural Information Processing Systems 2019, NeurIPS 2019, December 14, 2019, Vancouver, BC, Canada, pages 9832-9842, 2019.
[106) S. Saralajew, L.. Holdijk, and T. Villmann. Fast adversarial robustness certification of nearest prototype classifiers for arbitrary seminorms. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020.
[107] S. Schelter. "amnesia" machine learning models that can forget user data very fast. 10th Conference on Innovative Data Systems Research, CIDR 2020, Amsterdam, The Netherlands, January 12-15, 2020, Online Proceedings. www.cidrdb.org. 2020.
[108] S. Schelter, S. Grafberger, and T. Dunning. Hedgecut: Maintaining randomised trees for low- latency machine unlearning. In G. Li, Z. Li, S. Idreos, and D. Srivastava, editors, SIGMOD '21: International Conference Management of Data, Virtual Event, China, June 20-25, 2021, pages 1545 1555-157. ACM, 2021.
[109] J. Schuchardt, A. Bojchevski, J. Klicpera, and S. Günnemann. Collective robustness certificates. In 9th International Conference on Learning Representations, ICLR 2021, Online, May 4-7, 2021, Conference Track Proceedings. 2021.
[110] A. Sekhari, J. Acharya, G. Kamath, and A. T. Suresh. Remember what you want to forget: Algorithms for machine unlearning. In M. Ranzato, A. Beygelzimer, Y. Dauphin, Liang, and J. W. Vaughan, editors, Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurIPS 2021, December 6-14 64, 2021, virtual, pages 18075-18088 2021.
[111] T. Shibata, G. Irie, D. Ikami, and Y. Mitsuzumi. Learning with selective forgetting. In Z. Zhou, editor, Proceedings the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI 2021, Virtual Event / Montreal, Canada, 19-27 August 2021, pages 989-996. ijeai.org, 2021.
[112] R. Shokri, M. Stronati, C. Song, and V. Shmatikov. Membership inference attacks against machine learning models. In 2017 IEEE Symposium on Security and Privacy, SP 2017, San Jose, CA, USA, May 22-26, 2017, pages 3-18. IEEE Computer Society, 2017.
[113] G. Singh, T. Gehr, M. Mirman, M. Püschel, and M. T. Vechev. Fast and effective robustness certification. In Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurIPS 2018, 3-8 December 2018, Montréal, Canada, pages (0825-10836, 2018
18

---

[114] G. Singh, T. Gehr, M. Püschel, and M. T. Vechev. An abstract domain for certifying neural networks. Proc. ACM Program. Lang., 3(POPL):41:144:33) 2019.
[115] S. Singla and S. Feizi. Robustness certificates against adversarial examples for relu networks. CoRR, abs/1902.01235, 2019.
[116] S. Singla and S. Feizi. Sedend-order provable defenses against adversarial attacks. In Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event, pages 8981-8991, 2020.
[117] Z. Su, L. Liu, M. Li, X. Fan, and Y. Zhou. Servicetrust: Trust management in service provision networks. In Proceedings of the 10th IEEE International Conference on Services Computing (SCC'13), pages 272 279, Santa Clara, CA, June 27-July 2 2013.
[118] Z. Su, L. Liu, M. Li, X. Fan, and Y. Zhou. Reliable and resilient trust management in distributed service provision networks, ACM Transactions on the Web (TWEB), 9(3):1-37, 2015.
[119] P. Súkeník, A. Kuvshinov, and S. Günnemann. Intriguing properties of input-dependent randomized smoothing. CoRR, abs/21 2021.
[120] J. Teng, G.-H. Lee, and Y. Yuan. I adversarial robustness certificates: a randomized smoothing approach. OpenReview, 2019.
[121] A. Thudi, G. Deza, Chandrasekaran, and N. Papernot. Unrolling SGD: understanding factors inftuencing machine unlearning. CoRR, abs/2109. 13398, 2021.
[122] A. Thudi, H. Jia, I. Shumailov, and N. Papernot. On the necessity of auditable algorithmic definitions for machine unlearning. CoRR, abs/2110.11 1891, 2021.
[123] Y. Tsuzuku, I. Sato, and M. Sugiyama. Lipschitz-marge margin training: Scalable certification of perturbation invariance for deep neural networks. Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurIPS 2018 3-8 December 2018, Montréal, Canada, pages 65511, 2018
[124] E. Ullah, T. Mai, A. Rao, R. A. Rossi, and R. Arora. Machine unlearning via algorithmic stability. In M. Belkin and S. Kpotufe, editors, Conference on Learning Theory, COLT 2021, 15-19 August 2021, Boulder, Colorado, USA, volume 134 of Proceedings of Machine Learning Research, pages 4126-4142. PMLR, 2021.
[125] M. Veale, Binns, and Edwards. Algorithms that remember: Model inversion attacks and data protection law. CoRR, abs/l /tt///00704444 2018.
[126] J. Wang. S. Guo, X. Xie, and H. Qi. Federated unlearning via dlass-discriminatiee pruning. In F. Laforest, R. Troncy, F. Simperl, D. Agarwal, A. Gionis, I. Herman, and L. Médini, editors, www '2: The ACM Web Conference 2022, Virtual Event, Lyon, France, April 25 29, 2022, pages 622-632. ACM, 2022.
[127] S. Wang, K. Jei, Whitehouse, J. Yang, and S. Jana. Efficient formal safety analysis of neural networks. In Advances Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurIPS 2018, December 3-8, 2018, Montréal, Canada, pages 6369-6379, 2018
[128] S. Wang, K. Pei, J. Whitehouse, J. Yang, and S. Jana. Efficient formal safety analysis of neural networks. In Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurIPS 2018, 3-8 December 2018, Montréal, Canada, pages 6369-6379, 2018
[129] T. Weng, H. Zhang, H. Chen, Z. Song, C. Hsieh, L. Daniel, D. S. Boning, and I. S. Dhillon. Towards fast computation of certified robustness for relu networks. In Proceedings of the 35th International Conference on Machine Learning, ICMI. 2018, Stockholmsmässon, Stockholm. Sweden, July 10-15, 2018, pages 5273-5282, 2018
19

---

[130] T. Weng. P. Zhao, S. Liu, P. Chen, X. Lin, and L. Daniel. Towards certificated model robustness against weight perturbations. In The Thirty-Forr Fourth AAAI Conference on Artificial Intelligence. AAAI 2020, The Thirty-Second Innovative Applications of Artificial Intelligence Conference, IAAI 2020, The Tenth AAAI Symposium on Educatiinal Advances in Artificial Intelligence. EAAI 2020, New York, NY, USA, February 7-12, 2020, pages 6356-6363, 2020.
[131] E. Wong and J. Z. Kolter. Provable defenses against adversarial examples via the convex outer adversarial polytope. In Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsmüssan, Stockholm, Sweden, July 10-15, 2018, pages 5283-5299 2018.
[132] E. Wong, F. R. Schmidt, J. H. Metzen, and J. Z. Kolter. Scaling provable adversarial defenses. In Advances Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurlPS 2018, 3-8 December 2018, Montréal, Canada, pages 1410-8419 2018
[133] C. Wu, S. Zhu, and P. Mitra. Federated unlearning with knowledge distillation. CoRR, abs/2201.09441, 2022.
[134] G. Wu, M. Hashemi, and C. Srinivasa. PUMA: performance unchanged model augmentation for training data removal. In Proceedings of the 36th AAAI Conference on Artificial Intelligence, (AAAI'22), February 22-March 1, 2022, Vancouver, Canada, 2022.
[135] S. Wu, Y. Li, D. Zhang, Y. Zhou, and Z. Wu. Topicka: Generating commonsense knowledge- aware dialogue responses towards the recommended topic fact. In Proceedings of the Twenty- Ninth International Joint Conference on Artificial Intelligence (IJCAI'20, pages 3766-3772, Online, January 7-15 2021.
[136] Y. Wu, E. Dobriban, and S. B. Davidson. Deltagrad: Rapid retraining of machine learning models. In Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pages 10355-10366. PMLR, 2020.
[137] Y. Wu, A. Bojchevski, A. Kuvshinov, and S. Günnemann. Completing the picture: Random- ized smoothing suffers from the curse of dimensionality for large family of distributions. In A. Banerjee and K. Fukumizu, editors, The 24th International Conference on Artificial Intelligence and Statistics, AISTATS 2021, April 13-15, 2021, Virtual Event, volume 130 of Proceedings of Machine Learning Research, pages 3763-3771. PMI.R, 2021.
[138] H. Xiao, K. Rasul, and R. Vollgraf. Fashion-mnist: a novel image dataset for benchmarking machine learning algorithms. CoRR, hatp/10080777,, 2017.
[139] K. Xu, Z. Shi, H. Zhang, Y. Wang, K. Chang, M. Huang, B. Kailkhura, X. Lin, and C. Hsieh. Automatic perturbation analysis for scalable certified robustness and beyond. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020.
[140] G. Yang, Duan, J. Hu, H. Salman, P. Razenshteyn, and J. Li. Randomizee smoothing of all shapes and sizes. In Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event, pages 10693-10705, 2020.
[141] M. Ye, C. Gong, and Q. Liu. SAFER: A structure-free free approach for certified robustness to adversarial word substitutions. In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, ACL 2020. Online, July 5-10, 2020, pages 3465-3665 3475, 2020.
[142] H. Zeng, J. Su, and F. Huang. Certified defense via latent space randomized smoothing with orthogonal encoders. CoRR, (ass2108..0099) 2021.
[143] Y. Zeng. S. Chen, W. Park, Z. Mao, M. Jin, and R. Jia. Adversarial unlearning of backdoors via implicit hypergradient. In 10th International Conference on Learning Representations, ICLR 2022, Online, April 25-29, 2022, Conference Track Proceedings, 2022.
20

---

[144] R. Zhai, C. Dan, D. He, H. Zhang, B. Gong, P. Ravikumar. C. Hsieh, and L. Wang. MACER: attack-free and scalable robust training via maximizing certified radius. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020, 2020.
[145] D. Zhang, M. Ye, C. Gong, Z. Zhu, and Q. Liu. Black-bo box certification with randomized smoothing: A functional optimization based framework. In Advances in Neural Information Processing Systems 33: Anmual Conference on Neural Information Processing Systems 2020, NeurlPS 2020, December 6- 2020, virtual, 2020.
[146] G. Zhang, Y. Zhou, S. Wu, Z. Zhang, and D. Dou. Cross-lingual entity alignment with adversarial kemel embedding and adversarial knowledge translation. CoRR, abs/2 104,2104.7787,, 2021.
[147] H. Zhang. Weng, P. Chen, C. Hsieh, and L. Daniel. Efficient neural network robustness certification with general activation functions. In Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurIPS 2018, 3-8 December 2018, Montréal, Canada, pages 4944-4953, 4953, 2018.
[148] R. Y. Zhang, On the tightness of semidefinite relaxations for certifying robustness to adversarial examples. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurlPS 2020, December 6-12, 2020, virtual, 2020.
[149] Z. Zhang. J. Jin, Z. Zhang, Y. Zhou, X. Zhao, J. Ren, J. Liu, L. Wu, R. Jin, and D. Dou. Validating the lottery ticket hypothesis with inertial manifold theory. In Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021 (NeurlPS'2 211), Virtual.
[150] Z. Zhang, Z. Zhang, Y. Zhou, Y. Shen, Jin, and D. Dou. Adversarial attacks on deep graph matching. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020 (NeurIPS'2O) 20). Virtual, December 6-12 2020.
[151] X. Zhao, Z. Zhang. Z. Zhang, L. Wu, J. Jin, Y. Zhou, R. Jin, D. Dou, and D. Yan. Expressive 1-lipschitz neural networks for robust multiple graph learning against adversarial attacks. In Proceedings of the 38th International Conference on Machine Learning (ICML 21), pages 22719-12735, Virtual Event, July 18-24 2021.
[152] Y. Zhou. Innovative Mining, Processing, and Application of Big Graphs. PhD thesis, Georgia Institute of Technology, Atlanta, GA, USA, 2017.
[153] Y. Zhou and L. Liu. Social influence based clustering of heterogeneous information networks. In Proceedings of the 19th ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD' 13), pages 338 346, Chicago, IL. August 11-14 2013.
[154] Y. 7hou and I.. Liu. Approximate deep network embedding for mining large-scale graphs. In Proceedings of the 2019 IEFE International Conference on Cognitive Machine Intelligence (CogMI'19), pages 53-60, Los Angeles, CA, December 12- 14 2019.
[155] Y. Zhou, L. Liu, K. Lee, C. Pu, and Q. Zhang. Fast iterative graph computation with resource aware graph parallel abstractions. In Proceedings of the 24th ACM Symposium on High- Performance Parallel and Distributed Computing (HPDC' 15), pages 179-190, Portland, OR, June 15-19 2015.
[156) Y. Zhou, A. Amimeur, C. Jiang, D. Dou, R. Jin, and P. Wang. Density-aware local siamese autoencoder network embedding with autoencoder graph clustering. In Proceedings of the 2018 IEEE International Conference on Big Data (BigData' 18), pages 1162-1167, Seattle, WA, December 10-13 2018
[157] Y. Zhou, S. Wu, C. Jiang, Z. Zhang, D. Dou, R. Jin, and P. Wang. Density-adaptive local edge representation learning with generative adversarial network multi-label edge classification. In Proceedings of the 18th IEFE International Conference on Data Mining (ICDM' 18), pages 1464-1469, Singapore, November 17-20 2018
21

---

[158] Y. Zhou, J. Ren, D. Dou, R. Jin, J. Zheng, and K. Lee. Robust meta network embedding against adversarial attacks. In Proceedings of the 20th IEEE International Conference on Data Mining (CCDM220) pages 1448-1453 Sorrento, Italy, November 17-20 2020.
[159] Zhou, Z. Zhang, S. Wu, Sheng, Han, Z. Zhang, and R. Jin. Robust network alignment via attack signal scaling and adversarial perturbation elimination. In Proceedings of the 30th Web Conference (WWW'2/), pages 3884-3895, Virtual Event Ljubljana, Slovenia, April 19-23 2021.
[160] Y. Zhou, Ren, R. Jin, Z. Zhang. J. Zheng, Z. Jiang, D. Yan, and D. Dou. Unsupervised adversarie network alignment with reinforcement learning, ACM Transactions Knowledge Discovery from Data (TKDD), 16(3):50:1-50:29, 2022.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes] See Sections 3 and 4
(b) Did you describe the limitations of your work? [Yes] See Section A.8
(c) Did you discuss any potential negative societal impacts of your work? [Yes] See
Section[A.8]
(d) Have you read the ethies review guidelines and ensured that your paper conforms them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] See Section A.4
(b) Did you include complete proofs of all theoretical results? [Yes] See Section A.4
3. If you experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main exper- imental results (either in the supplemental material or as a URL)? [No] We include the citations and URLs of all datasets used in this work and all codes of third-party baselines in Sections and A.7 Since the datasets used are all public datasets and our methodologies and the hyperparameter settings are explicitly described in Section 3
5 and A.7 our codes and experiments can be casily reproduced on top of a GPU server.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] See Section A.7
(c) Did you report error bars (e.g., with respect the random seed after running experi-
ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] See Section A.7]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes] See Sections 5 and
A.7
(b) Did you mention the license of the assets? [Yes] See Section A.7
(c) Did you include any new assets either in the supplemental material or as URL? [No] Since the datasets used are all public datasets and our methodologies and the hyperparameter settings are explicitly described in Section 5 and A.7 our codes and experiments can be easily reproduced on top GPU server.
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
22

---

(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review
Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
23


Reviews:
[{"review_id": "rkoT44_QMZH", "reviewer": "Reviewer_JFbC", "summary": "This paper presents a novel certified machine unlearning framework that targets the issue in the expensive computational cost of training and unlearning. The authors analogize certified robustness on classification against adversarial attacks to certified machine unlearning on gradient quantization against data removals. The randomized gradient smoothing and quantization techniques are developed to guarantee that the learnt model shares the same gradients (and parameters) and has the same performance with the naive unlearning model retrained on only the remembered data, with only the cost of simultaneous training and unlearning. The theoretical analyses validate the effectiveness of certified machine unlearning in terms of the certified radius and the certified budget of data removals. Overall, the studied problem is interesting and practically important. The experimental results look promising.\n", "questions": "Data removal description and other smoothing strategies.", "limitations": "It is unclear of the potential negative societal impacts of the results, such as security, privacy, and fairness issues, etc.", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n1. Existing machine unlearning methods separate the unlearning process into two sequential operations of training and unlearning, which leads to non-trivial computation cost when training complex models over large datasets. In addition, these methods often sequentially address multiple unlearning requests one by one. To improve the unlearning efficiency, this work trains and unlearns the model simultaneously.\n\n2. The authors propose a randomized gradient smoothing and quantization technique to directly train an unlearning model in advance with fast convergence and certified unlearning guarantees. The framework is able to resolve the requests of data removal in a timely and cost-efficient manner. \n\n3. The proposed method provides a general machine unlearning framework. The proposed framework is important for privacy-critical applications that usually require near-zero tolerance of data leaking, such as financial and health data analyses.\n\n4. This work theoretically analyzes and understands the certified radius regarding the data change before and after data removals and the certified budget of data removals in machine unlearning. Extensive experimental results on different benchmark datasets have been conducted to validate the efficacy of the developed prompt certified machine unlearning algorithms.\n\nWeaknesses:\n\n1. The paper provides descriptions of the benchmark image classification datasets and learning models in the paper and appendix. It would be nice to include the description of the data removals for how to separate the datasets into the forgotten data and the remembered data for each benchmark dataset.\n\n2. It would be interesting to see the results about different smoothing strategies exploited in certified machine unlearning problems, such as Laplacian and uniform smoothing.", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}, {"review_id": "cx4nOLQ-3AP", "reviewer": "Reviewer_xTHV", "summary": "This papers tackles the problem of machine unlearning, that is, removing training data upon request from a model, as if the model is trained only with the retained data. The proposed approach, PCMU, trains a model with randomly smoothed quantized gradient. Analogous to certified robustness, the paper presents some certified radius of the proposed method, against to pertubation of the gradient. Unlike previous machine unlearning approaches, PCMU directly trains a model that is robust to data removal, so it does not require an additional unlearning stage. Experimental results show that PCMU can achieve a more similar error rate with retraining than competitive models. ", "questions": "1. Does the proposed approach work for non-uniform data removal? For example, a \"group\" or class of samples are removed completely. \n2. In Eq. (21), I suppose \\bar G is a gradient, and \\epsilon ~ \\mathcal D is a datum. What does it mean by adding a data and a gradient?\n3. What does \"prompt\" in the title mean?\n\nTypos:\nL33: \"certified\" should be capatalized. \nL53: two consecutive periods. ", "limitations": "There are not apparent further limitations or potential  negative societal impacts other than those I raised for weaknesses and questions. ", "rating": 3, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength\n- some theoretical results are provided\n- the proposed method is faster than previous methods, and it can matches the accuracy better with the retraining approach\n\nWeaknesses\n- I'm not an expert on machine unlearning. But from my perspective, rather than a machine unlearning method, the proposed approach looks more like a differential privacy work, which trains a model without utilizing too specific features from individual users, so the trained model automatically satisfies removal requirements. I wonder whether it counts as machine unlearning.\n- The writing is somewhat vague: there is not a description or pseudocode of how the training and unlearning are performed, making the paper difficult to follow.", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "Hzvg9fTR9G6", "reviewer": "Reviewer_VAAx", "summary": "The authors propose a novel certified machine unlearning algorithm to improve the unlearning efficiency for complex models on large-scale data. First, the authors present an analytic framework to connect  randomized smoothing for certified robustness on classification to randomized smoothing for certified machine unlearning on gradient quantization. Second, the paper develops a prompt certified machine unlearning model for producing the effective certificates of data removals based on randomized data smoothing and gradient quantization. Finally, the authors propose a practical framework of randomized gradient smoothing and quantization for producing the high confidence certificates in an efficient manner.\n\nThe proposed PCMU method brings three significant benefits: simultaneously conduct the training and unlearning for improving the unlearning efficiency, one-time training for responding multiple machine unlearning requests at a time, and no need to know the forgotten data before the unlearning.\n", "questions": "See the above weaknesses.\n", "limitations": "None", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n+ The authors study an important research problem, i.e., prompt machine unlearning, which is important to improve the unlearning efficiency for complex models on large-scale data and to provide the timely response to a series of machine unlearning requests. There are few prior works to conduct this problem. \n\n+ The motivation for proposing randomized gradient smoothing and quantization techniques is clearly explained. The method and the claim are correct and sound. The authors provide enough methodology description and theoretical analysis to explain their proposed PCMU model.\n\n+ The paper conducts the theoretical analysis to derive the certified radius regarding the data change, the certified budget of data removals, and the correlation between two types of certified radii in two frameworks. This work integrates the certifying and training of machine unlearning into a uniﬁed framework for further enhancing the unlearning performance. The convergence analysis is conducted to demonstrate the effectiveness and efficiency of the prompt certified machine unlearning algorithm.\n\n+ The paper provides comprehensive extensive evaluation on three real datasets to demonstrate the superior performance of the proposed techniques against a number of SOTA baselines. The experiment results look promising.\n\nWeaknesses:\n- There are several typos and the paper would beneﬁt of a careful proofread. For example, \"which are used to derive the certified budget B about R'\" in P2 -> \"B'\", \"the certified budget of data removal\" in P5 -> \"removals\", and \"Notice that the accuracy and error on test data by our PCMU keeps unchanged\" in P8 -> \"keep\".\n\n- It would be nice to move the related work section to the paper for readers to better understand and appreciate the technical contributions of this paper compared with existing studies, instead of the appendix.\n\n- In the experiments, Tables 1-2 and relevant texts lie in different pages, which decreases the paper’s readability. I suggest the authors to update the paper layout to get more clear presentation.\n", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept