Certified Machine Unlearning via Noisy Stochastic Gradient Descent
Authors: Eli Chien
Haoyu Peter Wang
Ziang Chen
Pan Li
Venue: NeurIPS 2024 poster (2024)
Keywords: Machine unlearning
privacy
stochastic gradient descent
Primary area: privacy
TL;DR: We propose to leverage stochastic noisy gradient descent for unlearning and establish its first approximate unlearning guarantee under the convexity assumption.

Abstract: ``The right to be forgotten'' ensured by laws for user data privacy becomes increasingly important. Machine unlearning aims to efficiently remove the effect of certain data points on the trained model parameters so that it can be approximately the same as if one retrains the model from scratch. We propose to leverage projected noisy stochastic gradient descent for unlearning and establish its first approximate unlearning guarantee under the convexity assumption. Our approach exhibits several benefits, including provable complexity saving compared to retraining, and supporting sequential and batch unlearning. Both of these benefits are closely related to our new results on the infinite Wasserstein distance tracking of the adjacent (un)learning processes. Extensive experiments show that our approach achieves a similar utility under the same privacy constraint while using $2\%$ and $10\%$ of the gradient computations compared with the state-of-the-art gradient-based approximate unlearning methods for mini-batch and full-batch settings, respectively.

Certified Machine Unlearning via Noisy Stochastic Gradient Descent
Eli Chien
Department of Electrical and Computer Engineering Georgia Institute of Technology
Georgia, U.S.A. i rchien6@@atech.coo
Haoyu Wang
Ziang Chen
Department of Electrical and Computer Engineering Georgia Institute Technology
Department of Mathematics Massachusetts Institute of Technology Massachusetts, U.S.A. zi zinngmitt.. langgmit.edu edu
Georgia, U.S.A.
haoyu. haoyu. wangoggategg..cccccoooo edu
Pan Li
Department of Electrical and Computer Engineering Georgia Institute of Technology Georgia, U.S.A. panli@gatech. edu
Abstract
"The right to forgotten" ensured by laws for user data privacy becomes increas- ingly important. Machine unlearning aims to efficiently remove the effect of certain data points on the trained model parameters so that can be approximately the same as if one retrains the model from scratch. We propose to leverage projected noisy stochastic gradient descent for unlearning and establish its first approximate unlearning guarantee under the convexity assumption. Our approach exhibits sev- eral benefits, including provable complexity saving compared to retraining, and supporting sequential and batch unlearning. Both of these benefits are closely lated to our new results on the infinite Wasserstein distance tracking of the adjacent (un)learning processes. Extensive experiments show that our approach achieves similar utility under the same privacy constraint while using 2% and 10% of the gra- dient computations compared with the state-of-the-art gradient-basee approximate unlearning methods for mini-batch and full-batch settings, respectively.
1 Introduction
Machine learning models usually learn from user data where data privacy has to be respected. Certain laws, such as European Union's General Data Protection Regulation (GDPR), are in place to ensure "the right to be forgotten", which requires corporations to erase all information pertaining to user if they request to remove their data. It is insufficient comply with such privacy regulation by only removing user data from the dataset, as machine learning models can memorize training data information and risk information leakage (12). A naive approach adhere to this privacy regulation is to retrain the model from scratch after every data removal request. Apparently, this approach prohibitively expensive in practice for frequent data removal requests and the goal of machine unlearning is to perform efficient model updates so that the resulting model is (approximately)
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

the same as retraining statistically. Various machine unlearning strategies have been proposed, including exact (3)6) and approximate approaches [7. The later approaches allow a slight misalignment between the unlearned model and the retraining one in distribution under notion similar to Differential Privacy (DP) [12].
The most popular approach for privatizing machine learning models with DP guarantee is arguably noisy stochastic gradient methods including the celebrated DP-SGD [13). Mini-batch training is one of its critical components, which not only benefits privacy through the effect of privacy amplification by subsampling (14) but also provides improved convergence of the underlying optimization process. Several recent works [1] based on full-batch (noisy) gradient methods may achieve certified approximate unlearning. Unfortunately, their analysis is restricted to the full-batch setting and is non-trivial to extend these works to the mini- batch setting with tight approximate unlearning guarantees. The main challenge is to incorporate the randomness in the mini-batch sampling into the sensitivity-
analysis (9] or the
analysis.
We aim to study mini-batch noisy gradient methods for certified approximate unlearning. The high- level idea of our unlearning framework is illustrated in Figure [ Given a training dataset D and a fixed mini-batch sequence B, the model first learns and then unlearns given unlearning requests, both via the projected noisy stochastic gradient descent (PNSGD). For sufficient learning epochs, we prove that the law of the PNSGD learning process converges to unique stationary distribution PD)S (Theorem 3.1). When an unlearning request arrives, we update 'D to adjacent dataset D' so that the data point subject to such request is removed. The approximate unlearning problem can then be viewed as moving from the current distribution VDDS the target distribution VD' I until s-close in Rényi divergence for the desired privacy loss +
Our key observation is that the results of Altschuler and Talwar 15 16 which study the conver- gence of PNSGD under the (strong) convexity assumption, can be leveraged after formulate the approximate unlearning as above. They show that the Rényi divergence of two PNSGD processes with the same dataset but different initial distributions decays at a geometric rate, starting from the infinite Wasserstein distance (Woc) of initial distributions (Figure I, step 3). As result, if the initial Wx distance can be properly characterized, we achieve the corresponding approximate unlearning guarantee by further taking the randomness of the mini-batches B into account (Figure 1, step 4). Therefore, the key step to establish the PNSGD-based unlearning guarantee is characterize the initial W distance of the unlearning process tightly.
The projection set diameter 2R for this W> distance adopted in 15 for DP analysis, unfortunately, leads to a vacuous unlearning guarantee, which cannot illustrate the computational advantage over the retraining from scratch. To alleviate this issue, we perform careful W distance tracking analysis along the adjacent PNSGD learning processes (Lemma 3.3), which leads to a much better bound (PD)S, PD'18) S ZB &. O(1M/b) (Figure I, step 2) for bounded gradient norm M, mini-batch size b and step size 13. This ultimately leads to our unlearning guarantee e = OZZ for K unlearning epochs and some rate < 1. The computational benefit. compared to the retraining from scratch naturally emerges by comparing two Wo distances, O(R) for the retraining from scratch and (B) for our unlearning framework.
Our approach also naturally extends to multiple unlearning requests, including sequential and batch unlearning settings (Theorem 3. Corollary J.1. by extending the W Wo-tracking analysis (Lemma (.4). Here, we may use the triangle inequality of W 20 distance, which leads to a tigher privacy loss bound (growing linearly to the number of unlearning requests) than that in the Langevin-dynamie based analysis [TT] via weak triangle inequality of Rényi divergence (growing exponentially).
Our results highlight the insights into privacy-utility culplety trade-off regarding the mini-batch size b for approximate unlearning. smaller batch size b leads to a better privacy loss decaying rate Oc22n/bb) However, an extremely small may degrade the model utility and incur instability. It also leads to worse bound Zg x On,M/b) which degrades the computational benefits compared to retraining. We demonstrate such trade-off of our PNSGD unlearning results via experiments against the state-of-the-an full-batch (b- = n) gradient- based approximate unlearning solutions (9] 11]. Our analysis provides a significantly better watplyy--littycommppp
trade-off even when we restrict ourselves to b- n, and further improves the results by adopting mini-batches. Under the same
'e refer privacy loss as two-sided Rényi divergence of two distributions, which we defined as Rényi difference in Definition 2.1
2

---

(x [I, x x ; leel
f(x:)) + +2
xt+1 (xx:B.2)
Kojs
PNSGD update d:: contractive nolsy iteration
2
( D) (;; D) . (c: 8 D) (.: Bu/b-1
Xi+1 (x²: B .D')
Ma'ps
Step 1: per-epach update converge unique stationary distribution Vpl
Learning process M
Vajs
Po
Step Initial distance: Wi (Voje. Vo'ja) Zg
Ye+1 = (b2:
Unlearning
Step 3: Privacy loss given B:c < 1,
Pkt8
du (oeiss "o'ia) s 0 (Z)
Zn
Me+1
d
Yelp
Step 4: Final privacy loss:
du (px, v log(E s
Vo'is
0 Unlearning process
Figure I: The overview of PNSGD unlearning. (Left) Proof sketch for PNSGD unlearning guarantees. (Right) PNSGD (un)learning processes on adjacent datasets. Given a mini-batch sequence B, the learning process M induces regular polyhedron where each vertex corresponds to a stationary distribution VDiS for each dataset D. VDj and "DDS"' are adjacent if D D' differ one data point. We provide an upper bound Zg for the infinite Wasserstein distance W no (VDjs: "DDS"): ), which is crucial for non-vacuous unlearning guarantees. Results of (16) allow us to convert the initial W oc bound to Rényi difference bound da and apply joint convexity of KL divergence to obtain the final privacy loss which also take the randomness of B into account.
privacy constraint, our approach achieves similar utility while merely requiring 10%, 2% of gradient computations compared to baselines for full and mini-batch settings respectively.
1.1 Related Works
Machine unlearning with privacy guarantees. The concept of approximate unlearning uses probabilistic definition of (e, 6)-unerrnn motivated by differential privacy (12), which is studied by [7.8 [0]. Notably, the unlearning approach of these works involved Hessian inverse computation which can be computationally prohibitive in practice for high dimensional problems. Ullah et al. [5] focus on exact unlearning via a sophisticated version of noisy SGD. Their analysis is based on total variation stability which is not directly applicable to approximate unlearning settings and different from our analysis focusing on Rényi divergence. Neel et al. (9] leverage full-batch PGD for (unnnnggning and achieve approximate unlearning by publishing the final parameters with additive noise. Chien et al. (T1) utilize full-batch PNGD for approximate unlearning with the analysis of Langevin dynamics. The adaptive unlearning requests setting is studied in 66 [8], where the unlearning request may depend on the previous (un)learning results. It is possible to show that our framework is also capable of this adaptive setting since we do not keep any non-private internal states, though we only focus on non-adaptive settings in this work. We left a rigorous discussion for this as future work.
2 Preliminaries
We consider the empirical risk minimization (ERM) problem. Let D) [d,} be training dataset with n data point d; taken from the universe X. Let fD(x) = 1 b. f(x; d,) be the objective function that we aim to minimize with learnable parameter x E CR. where CR = {a E Rd ||>||| s R} is a closed ball of radius R. We denote 11c₂ : Rd + CR to be an orthogonal projection to CR- The norm || is standard Euclidean & norm. P(C) is denoted as the set of all probability measures over a closed convex set C. Standard definitions such as convexity are in Appendix [D] We use x ~ v to denote that random variable follows the probability distribution We say two datasets D and D' are adjacent if they "differ" in only one data point. More specifically, we can obtain D' from D by replacing one data point. We next introduce useful idea which term as Rényi difference.
Definition 2.1 (Rényi difference). Let 1. For a pair of probability measures v, v' with the same support, the a Rényi difference d,, (v, v') is defined as (u, v') max (Da(elle),, Da(v'(l)) where (ulle)) is the a Rényi divergence defined as (ulvll/) = - log (Eaey P(x) ya
((()))
3

---

Algorithm 1 (Un)learning with PNSGD
1: Parameters: stepsize 1). noise standard deviation o, dataset size n, mini-batch size
2: Minibatch Generation: randomly partition indices [nx] into n/b mini-batches of size b:
B" BB.....,B,,8.
3: Learning process M(D); given a dataset D = {d; H= E X", sample initial parameter 26
from given initialization distribution Vn supported on Cn. The output the last iterate x/
4: for epoch t = O...., T
do
5: for iteration j = =0, .................... n//b do
H+1 =Ilea (o) - -nngggl B¹) + 22n02W?), where B') Eies v/(a/;d))
6:
24
and W ind AO La).
7: end for
8: 2++1 = 2///
9: end for
Unlearning process (D), D'): given an updated dataset DD' {d] X and current parameter V the output is the last iterate vkg
11: for epoch & = 0, ................
do
12:
for iteration j = 0, n//b do
j+l = CC y n B) + v 22 where s = EieD VS(r(:d))
13:
and W 14 (O, Ia).
end for
15: vh+1 Vi n/b
16: end for
We are ready to introduce the formal definition of differential privacy and unlearning.
Definition 2.2 (Rényi Differential Privacy (RDP) (19). Let a > 1. A randomized algorithm M X Rd satisfies (a, s)D if for any adjacent dataset pair D,D' D' X2, the Rényi difference (u, v') S where M(D) ~ v and M(D') ~v.
It is known to the literature that (a, R)-RDP guarantee can be converted to the popular (e, 8)-DP guarantee [12 relatively tight [9). As a result, we will focus on establishing results with respect to Rényi difference (and equivalently a Rényi difference). Next, we introduce our formal definition of unlearning based on Rényi difference as well.
Definition 2.3 (Rényi Unlearning (RU)). Consider a randomized learning algorithm M :. + Rd and a randomized unlearning algorithm U Rd x X x Xm + Rd. We say (M,U) achieves (a,e)-RU if for any a > and any adjacent datasets D, D', the a Rényi difference dalp, SE, where (MM()), D') p and M(D') ~ v'.
Our Definition 2.3 can be converted to the standard (e, uunlearnigg definition defined in 7 similar to RDP to DP conversion (see Appendix NJ. Since we work with the replacement definition of dataset adjacency, to unleam a data point d, we can simply replace it with any data point d' e X' for the updated dataset D' in practice. One may also repeat the entire analysis with the objective function being the summation of individual loss for the standard add/remove notion of dataset adjacency. Finally, we will also leverage the infinite Wasserstein distance in analysis.
Definition 2.4 (W og distance). The co- Wasserstein distance between distributions μ and y on a Banach space (R2 ||I []) is defined as Woo(u,))
inf inf,er(a.)) ess (x.))) ||x yll, where (x, y) means that the essential supremum is taken relative to measure over R2d xRd parametrized by (x. y). I(H4 v) is the collection of couplings of μ and v.
2.1 Converting Initial W Distance to Final Rényi Divergence Bound
An important component of our analysis is to leverage the result of [16], which is based on the celebrated privacy amplification by iteration analysis originally proposed in (20) and also utilized for DP guarantees of PNSGD in [15]. The goal of (16) is to analyze the mixing time of the PNSGD process, which can be viewed as the contractive noisy iterations due to the contractiveness of the gradient update under strong convexity assumption.

---

Definition 2.5 (Contractive Noisy Iteration (c-CNI)). Given an initial distribution E P(R*), a sequence of (random) c-contractive (equivalently, c-I.ipschitz) functions t/a .Rd + Rd, and a sequence of noise distributions Çu. we define the c-Contractive Noisy Iteration (c-CNI) by the update rule Xx+1 1 = ( + W&+1. where WK+1 ~ Çk independently and Xo ~ No. We denote the law of the final iterate X by CN. (..)){(a)))
Lemma 2.6 (Metric-aware privacy amplification by iteration bound (20), simplified by (16) in Proposition 2.10). Suppose Xx ~ (No, { {(x}) and Xxk ~ CNlo (1x)), (ca)) where the initial distribution satisfy W (Ho 14)) I Z, the update function the are c-contractive, and the noise distributions ÇR = =N(0, of Ia). Then we have
ifc Da(XxlIXk) S 20 11/K ifc=
a7 J
Roughly speaking, Lemma shows that if we have the W~ distance of initial distributions of two PNSGD processes on the same dataset, we have the corresponding Rényi difference bound after K iterations. The projection set diameter 2R is default upper bound for Wo distance if we do not care about the initial distributions as the case studied in (16) for mixing time analysis. In the unlearning scenario, the initial distributions of the unlearning processes, denoted by PD|B, PD are much more relevant. We can show much tighter bound by analyzing W (VDjs. (Dr)s) along the adjacent PNSGD learning processes.
3 Certified Unlearning Guaranatee for PNSGD
We start with introducing the (un)learning process with PNSGD with a cyclic mini-batch strategy (Algorithm D.. Note that this mini-batch strategy is not only commonly used for practical DP-SGD implementations in privacy libraries (21). but also in theoretical analysis for DP guarantees (22)
For the learning mechanism M. we optimize the objective function with PNSGD on dataset D (line 3-8 in Algorithm! []. 17, o² > are hyperparameters of step size and noise variance respectively. The initialization PD is an arbitrary distribution supported on CR if not specified. For the unlcarning mechanism U, we fine-tune the current parameter with PNSGD on the updated dataset D' subject to the unlearning request (line 10-15 in Algorithm I with d4 = =t M(D). For the rest of the paper, we denote vn. p as the probability density of x v respectively. Furthermore, we denote the minibatch sequence described in Algorithm where b is the step size and we assume is divided by b throughout the paper for simplicity? distribution of v.. given B.
B = (B²) j==0
) m//b1
We use v.js to denote the conditional
3.1 Certified Unlearning Guarantees
Now we introduce the certified unlearning guarantees for PNSGD and the corresponding analysis illustrated in F We first prove that for any fixed mini-bated sequence B, the limiting distribution VD' g of the learning process exists, is unique, and stationery. The proof is deferred to Appendix E
and is based applying the results in [23] to establish the ergodicity of the learning process xf.
Theorem 3.1. Suppose that the closed convex set C C Rd is bounded with C having positive Lebesgue measure and that ff C - Rd is continuous for all i E [n]. The Markov chain {I: := xf} } in Algorithm [ for any fixed mini-batch sequence B admits unique invariant probability measure PD on the Borel o-algebra of Furthermore, for any x E C, the distribution
of xi conditioned on Hog converges weakly VDDB as oc, where VDIS is the conditional distribution of VD given B.
Suppose the training epoch T' is large enough that the model is well-trained for now, which means M(D ~ VDJB = Po and our target "retraining distribution" " is VDDIB- Our goal is then to upper bound the Rényi difference d,, (P% B, "D(1)) after K unlearning epochs. In the case of insufficient 0. training, the privacy loss is da (P ( BT)B where M(D') rris for T training epochs. It can be upper bounded in terms of da (P% | 1D) and da (v VD' (B) via weak triangle inequality of
0,1
Whee n is not divided by b. we simply drop the last [n/b]bb points.
5

---

Rényi divergence, which is provided in Theorem 3.2 below. We later provide a better bound by considering the randomness of B.
Theorem 3.2 (RU guarantee of PNSGD unlearning, fixed B). Assume Vd E X, f(x; d) is L-smooth,
M-Lipchitz and m--strongly convex in x. Let the learning and unlearning processes follow Algorithm|] 7 with y x MMD). Given any fixed mini-batch sequence B, for any a 1. let n S E. the output of the W unlearning iteration satisfies (a,, EUU for any adjacent dataset DD DD' where
follow
a - 1/2 8 Σ
(E1 (2a) + =z((2)) = a(2R)
aZ3 22Kn/b
2n/b,, =2(aa
--1 1
21j0²
2n10²
1 - Tn/b 2
ZB W (PKIB. S 2Rd TT/b min
22
cn/b
b
and c 1ym..
As we explained earlier, we need non-trivial Wx bounds for adjacent PNSGD processes to obtain better unlearning guarantees when applying Lemma 2.6 We provide such results below and the proof' are deferred to Appendix D and M respectively.
Lemma 3.3 (Woe oc between adjacent PNSGD learning processes). Consider the learning process in Algorithm| 7 on adjacent datasets D and D' and a fixed mini-batch sequence B. Assume Vd E X, f(; d) is L-smohth, M -Lpischhitz and m-strongly convex in z. Let the index of different data point between D, D' belongs to mini-batch B Then for 1) S I. and let e -rmm). we have
W Wo
0, (T(B)) S min
(
cT//b (L-CTn/b
jo- I-/b/b cn/b c0/b-j0-1
L
2nA1
2R
b
Lemma 3.4 (Woo between PNSGD learning process to its stationary distribution). Following the same setting as in Theorem 3.2 and denote the initial distribution of the unlearning process as vg- Then we have
Wo ( PD|B) S (1-rmm)T///W (vo, VD1s).
Remark 3.5. In [15). the authors used the default projection set diameter 2R as the Woo distance upper bound for their DP results, see equations (3.5) and (5.2) therein. However, it yields vacuous bound as an unlearning guarantee compared retraining from scratch. Note that our tighter bound for Woo distance is also useful for deriving later sequential unlearning guarantees compared to the prior work based on the analysis of Langevein dynamics
(TT] Interestingly, this improved result can also be utilized for tightening the DP guarantee in [15) and make it more practically useful, as 2R can be very large practice, which may be of independent interest.
We are ready to provide the sketch of proof for Theorem 3.2
Sketch of proof. First note that the PNSGD update leads to a (1 rym)-CNI process when 1 S 1/L for any mini-batch sequence. Recall that v is the unlearning process at epoch & at iteration j. starting from 30 29 M(D). Consider the "adjacent" process vi starting from y0" 0,1 20 M(D') but still fine-tume tune on D' so that y yd only differ in their initialization. Now, consider three distributions: DD 18 PK] are the stationary distribution for the learning processes, learning process at epoch T and unlearning process at epoch K respectively. Similarly, consider the "adjacent" processes that learn on D' and still unlearn on D' (see Figure I for the illustration).
01 0, Denote distributions VD' B, BBB PK|8 for these processes similarly. Note that our goal is to bound da (P (T(() for the RU guarantee. By weak triangle inequality [19] we can upper bound it in terms of d2a [ PD41)) and d2a (PD 7T((), which are the E2 and E terms in Theorem 3.2 respectively. For (vD)) 20/3), we leverage the naive 2R bound for the Woe distance between 0,1 and applying Lemma 2.6 leads to the desired result. For de [P& (D(1B), 1). by triangle
PD's..oj
inequality of Wx and Lemma 3.3 3.4 one can show that the Wxc between 18 "D'I is bounded by Zg in Theorem 3.2. Further applying Lemma 2.6 again completes the proof.
Remark 3.6. Our proof only relies on the bounded gradient difference d) d')ll < 2M Yo E IRdd and Vd, d' E X' hence M-Liiphitz assumption can be replaced. In practice, we can leverage the gradient clipping along with &2 regularization for the convex objective function [22

---

The convergent case, In practice, one often requires the model to be "well-trained", where a similar assumption is made in the prior unlearning literature 8 Under this assumption, we can further simplify Theorem 3.2 into the following corollary.
Corollary 3.7. Under the same setting as of Theorem 3.2 When we additionally assume T is sufficiently large so that yd = M (D) ~ VDIB. Then.for any a > 1 and 1j S T. the output of the K
unlearning iteration satisfies (a, E-- with e = 1 - 17m, where
a78 2kn/b E 2ny0
M ZB min (1 11 cm/b b 22
1
For simplicity, the rest of the discussion on our PNSGD unlearning will based on the well-trained assumption. From Corollary 3.7 one can observe that a smaller b leads to better decaying rate (c2Kn/1) but also a potentially worse initial distance ZB O )b)) In general, choosing a smaller still leads to less epoch for achieving the desired privacy loss. In practice, choosing b too small (e.g.. b 1) can not only degrade the utility but also incur instability (i.e., large variance) of the convergent distribution VDjS, as VDD B depends on the design of mini-batcher B. One should choose a moderate to balance between privacy and utility, which is the unique privacy-uillty--oopeeixy trade-off with respect to b revealed by our analysis.
Computational benefit compared to retraining. In the view of Corollary 3.7 or Lemma 2.6 is not hard to see that a smaller initial Woo distance leads to fewer PNSGD (un (un)learning epochs for being e-close target distribution VDI in terms of Rényi difference d, For PNSGI unlearning. we have provided a uniform upper bound ZB = (npM/(( (11 - yb)) of such initial Woo distance in Lemma 3.3 On the other hand, even if both No; PD are both Gaussian with identical various and mean difference norm of S2(1). we have Woc (Vo, (D
(11) for retraining from scratch. Our results show that larger mini-batch size 6 leads to more significant complexity savings compared to retraining. As we discussed above, one should choose a moderate size to balance between privacy and utility. In our experiment, we show that for commonly used mini-batch sizes (i.c., b 2 32), our PNSGD unlearning is still much more efficient in complexity compared to retraining.
Improved bound with randomized B. So far our results are based on a fixed (worst-case) mini- batch sequence B. One can improve the privacy bound in Corollary[3.7] account under non-adaptive unlearning setting. That is, the unlearning request is independent of the mini-batch sequence B. See also our discussion the related work. By taking the average of the bound in Corollary 3.7 in conjunction with an application of joint convexity of KL divergence (22). we can derive an improved guarantee beyond the worst-case of B.
taking the randomness of B into
Corollary 3.8. Under the same setting of Theorem 3.2 but with random mini-batch sequences described in Algorithm 7 Then for any a >> 1, and 1) S T the output of the Kth unlearning iteration
(ala-11) 1722 2 ( and ZB is
satisfies (a, RR- with c= 1- - 1m, where E I o- log ER exp
2nd
the bound described in Lemma 3.3
Different mini-batch sampling strategies. We remark that our analysis can be extended to other mini-batch sampling strategies, such as sampling without replacement for each iteration. However, this strategy leads to a worse ZB in our analysis of Lemma 3.3, which may seem counter-intuitive at first glance. This is due to the nature of the essential supremum taken in W... Although sampling without replacement leads to a smaller probability of sampling the index that gets modified due to the unlearning request, it is still non-zero for each iteration. Thus the worst-case difference 2n /b between two adjacent learning processes in the mini-batel gradient update occurs at each iteration, which degrades the factor 1/(1 - cm/b) to 1/(1- - c) in Lemma 3.3 As result, we choose to adopt the cyclic mini-batch strategy so that such a difference is guaranteed to occur only once per epoch and thus a better bound on Woo-
Discussion on utility bound. One can leverage the utility analysis in section 5 of (24 to derive the utility guarantee for the full batch setting b n. We relegate the proof to Appendix K
Proposition 3.9. Under the same setting as Corollary 3.7 with b = n, 17 S 27 and assume the minimizer of any I' is in the relative interior Cn C R2 for any given adjacent dataset pair D D' the output of the kh unlearning iteration y satisfies
ElfDr inf for (x)) S Mc min( 1 M 1-c
2R) + 2Tdo²
=ECR
7

---

Note that a similar analysis applies to both the mini-batch (i.e., b n) and covvernvt case (i.e., Theorem (.2) but the result is more complicated. We leave the rigorous analysis as future work. An important remark is that the second term 2Lda" is the excess risk of up', which is controlled by the noise scale a. This presents the privacy-utiligg trade-off as demonstrated in the DP scenario in (24).
Without strong convexity. Since Lemma 2.6 also applies to the convex-only case (i.e., m = 0 so that 1), repeating the same analysis leads to the following extension.
Corollary 3.10. Under the same setting of Theorem 3.2 but without strong convexity (i.e., 0).
When we udditionally assume sufficiently large so that yo (D) ~ UDIB- Then for any a > 1,
and 1j I t. the ousput of the Wthh unlearning iteration satisfies (a, E)- where
aZg 2nj Kn.
22MTT 2R
8 S
ZB min
There are several remarks for Corollary 3.10 First, the privacy loss now only decays linearly instead of exponentially as opposed to the strongly convex case. Second, Zg now can grow linearly in training epoch T. As result, the computational benefit of our approach compared to retraining may vanish for large T such that 29MT 2
b 2 2R. Nevertheless, the computational benefit against retraining persists for moderate T such that 2nMT < 2R. This condition can be met the model learns reasonably well with moderate T and the projection diameter 2R is not be extremely small. For example, with 2R- = 10, = 128, 17 = 1 and M = 1, any training epoch T < 640 will lead to 2rMT < 2R. Still, we conjecture better analysis is needed beyond strong convexity.
b
3.2 Unlearning Multiple Data Points
So far we have focused on one unlearning request and unlcarning one point. In practice, multiple unlearning requests arrive sequentially (sequential unlearning) and each unlearning request may require unlearning multiple points (batch unlearning). Below we demonstrate that our PNSGD unlearning naturally supports sequential and batch unlearning as well.
Sequential unlearning, As long as we can characterize the initial Wxc distance for any mini-bater sequences, we have the corresponding (a, guarantee due to Corollary 3.7 Thanks to our geometric view of the unlearning problem (Figure 2 and Wo is indeed a metric, applying triangle inequality naturally leads to an upper bound on the initial Wx distance. By combining Lemma 3.3
and Lemma 3.4. we have the following sequential unlcarning guarantee.
Theorem 3.11 (Woo bound for sequential unlearning). Under the same assumptions as in Corol- lary 3.7 Assume the unlearning requests arrive sequentially such that our dataset changes from
D Do +1, + ... > Ds. where D,,D,- are adjacent. Let yk (((s) be the unlearned pa- rameters for the 5th unlearning request at hth unlearning epoch and jth iteration following Al- 0.(++1) 0.(+) УK, ~ DD.IB. where Yo = Ioa and Ka is the unlearning steps for the thh unlearning request. For any s E [S], we have Woo(D, 1|8; VD,11)) S Z(() where z(o+1) min(e z(0) + ZB, 2R),
gorithm ① on Dz and yo
0.(00
2
z(I1 ZR, Zi and e are described in Corollary 3.7
By combining Corollary 3.7 and Theo-
(a)
Yoys
200
(b)
Vays
rem 3. we can establish the least un-
learning iterations of each unlearning quest [,)5_ ==1 to achieve (a,&)-RU si- multancously. Notably, our sequential un- learning bound is much better than the one in [TT), especially when the num- ber of unlearning requests is large. The key difference is that (IT] have to lever- age weak triangle inequality for Rényi divergence, which double the Rényi di- vergence order for each sequential un- learning request. In contrast, since our analysis only requires tracking the initial
Vis
Zg
Voyl
Figure 2: Illustration of (a) sequential unlearning and (b) batch unlearning. The key idea is to establish an upper bound on the initial Wao distance. (a) For sequential un- learning, the initial Woc distance bound ((a) for each thh unlearning request can be derived with triangle inequality. (b) For batch unlearning, we analyze the case that two learning processes can differ in S > 1 points.
8

---

Acsumuu suldd Lanlaanding apo-che
20
6:
44
Numbar unisamadd
devistion
(a) Unlearning one point (b) Unlearning 100 points
(c) Noise V.s. accuracy
Noise v.s. complexity
Figure 3: Main experiments, where the top and bottom rows are for MNIST and CIFARIO respectively. (a) Compare to baseline for unlearning one point using limited K unlearning epoch. For PNSGD, we use only K = unlearning epoch. For D2D, we allow it to use K = 1,5 unlearning epochs. (b) Unlearning 100 points sequentially versus baseline. For LU, since their unlearning complexity only stays in reasonable range when combined with batch unlearning of size S sufficiently large, report such a result only. (c,d) Noise- accuracy-comppa points sequentially with various mini-batch sizes b, where all methods achieve (c, 1/n) -unlearrnnnn guarantee with e = 0.01. We also report the required accumulated epochs for retraining for each b.
trade-off of PNSGD for unlearning 100
Wx distance, where the standard triangle inequality can be applied. As result, our analysis can better handle the sequential unlearning case. We also demonstrate in Section that the benefit offered by our results is significant in practice.
Batch unlearning. We can extend Lemma 3.3 the case that adjacent dataset DD D' can differ in S 1 points, which further leads to batch unlearning guarantee. We relegate the result in Appendix
4 Experiments
Benchmark datasets. We consider binary logistic regression with l2 regularization. We conduct experiments on MNIST (25) and CIFARIO 10 [26). which contain 11,982 and 10,000 training instances respectively. We follow the setting of [7 to distinguish digits 3 and 8 for MNIST so that the problem is a binary classification. For the CIFARIO dataset, we distinguish labels 3 (cat) and 8 (ship) and leverage the last layer of the public ResNet18 [27] embedding as the data features, which follows the setting of (7) with public feature extractor.
Baseline methods. Our baseline methods include Delete-to-Descent (D2D) (9) and Langevin Un- learning (I.U) (TT), which are the state-of-the-art full-batch gradient- based approximate unlearning methods. Note that when our PNSGD unlearning chooses b = (i.e., full batch), the learning and unlearning iterations become PNGD which is identical to LU. Nevertheless, the corresponding privacy bound is still different as we leverage the analysis different from those based on Langevin dynamics in [TT]. Hence, we still treat these two methods differently in our experiment. For D2D, we leverage Theorem 9 and 28 in for privacy accounting depending to have an internal non-private state. Note that allowing an internal non- non-private state provides a weaker notion of privacy guarantee [9] and both PNSGD and LU by default do not require it. We include those theorems for D2D and a detailed explanation of its possible non con-privacy internal state in Appendix O For LU, we leverage their Theorem 3.2, and 3.3 for privacy accounting (II, which are included in Appendix PP
whether allow D2D
All experimental details can be found in Appendix N including how to convert E) to the standard (e, -unneerani guarantee. Our code is publicly available We choose ô = 1/n for each dataset and require all tested unlearning approaches to achieve (e, -unllearng with different e. We report test accuracy for all experiments as the utility metric. We set the learning iteration T 10, 20, 50, 1000 to ensure PNSGD converges for mini-batch size b = 32, 128, 512, respectively. All results are averaged over 100 independent trials with standard deviation reported as shades in figures.
httpp:///githuu.cco//rrre https//pDD_eeeeeninnggm

---

Unlearning one data point with K = epoch. We first consider the setting of unlearning one data point using only one unlearning epoch (Figure Baj. For both LU and PNSGD, we use only K = 1 unlearning epoch. Since D2D cannot achieve a privacy guarantee with only limited (i.e., less than 10) unlearning epoch without a non-private internal state, we allow D2D to have it and set K = 1,5 5 in this experiment. Even in this case, PNSGD still outperforms D2D in both utility and unlearning complexity. Compared to LU, our mini-batch setting either outperforms or is on par with it. Interestingly, we find that LU gives a better privacy bound compared to full-batch PNSGD (b n) and thus achieves better utility under the same privacy constraint, see Appendix P for the detailed comparisons. Nevertheless, due the use of weak triangle inequality in LU analysis, will see that our PNSGD can outperform LU significantly for multiple unlearning requests.
Unlearning multiple data points. Let us consider the case of multiple (100) unlearming requests (Figure 3bp. We all methods achieve the same (1, 1//n)-unnbnnee -unlearnnn guarantee for a fair comparison. We do not allow D2D) to have an internal non-private state anymore in this experiment for fair comparison. Since the privacy bound of LU only gives reasonable unlearning complexity with a limited number of sequential unlearning updates [1I], we allow it to unlearn S = 10 points at once. We observe that PNSGD requires roughly 10% and 2% of unlearning epochs compared to D2D and LU for for MNIST and CIFAR 10 respectively). It shows that PNSGD is much more efficient compared to D2D and LU. Notably, while both PNSGD with 6 n and LU (un)learn with PNGD iterations, the resulting privacy bound based on our PABI-based analysis is superior to the one pertaining to Langevin-dynnn
and b 128 respectively, where all methods exhibit similar utility (0.9 and 0.98
analysis in I See our discussion in Section 3.2 for the full details.
Privacy-utilite uuillty-ccopllexiiii trade-off. We now investigate the inherent utility-ompplxxtt trade-off regarding noise standard deviation and mini-batch size b for PNSGD under the same privacy con- straint, where we require all methods to achieve (0.01, 1/n) -unleerrnnnn guarantee for 100 sequential unlearning requests (Figure 3c and 3db. We can see that smaller leads to a better utility, yet more unlearning epochs are needed for PNSGD to achieve e = 0.01. On the other hand, smaller mini-batch size b requires fewer unlearning epochs K as shown in Figure 3d since more unlearning iterations are performed per epoch. Nevertheless, we remark that choosing b too small may lead to degradation of model utility instability. Decreasing the mini-bated size b from 32 to 1 reduces the average accuracy of training from scratch from 0.87 to 0.64 and 0.97 to 0.81 on MNIST and CIFAR respectively for 0.03. In practice, one should choose moderate mini-batch size b to ensure both good model utility and unlearning complexity. Finally, we also note that PNSGD achieves a similar utility while much better complexity compared to retraining from scratch, where PNSGD requires most 1, 5 unlearning epochs per unlearning request for b = 32, 512 respectively.
5 Limitations and Conclusion
we share the same limitation that the (strong) convexity assumption required. It is an open problem on how extend such analysis beyond convexity assumption as stated in [6). While we resolve this open problem for establishing DP properties of PNSGD our recent work (28), it is still unclear whether the same success can be generalized to the unlearning problem. One interesting direction is to leverage the Langevin dynamic analysis (29] instead as in [IT), which can deal with non-convex problems in theory yet we conjecture the resulting bounds can be loose, and more complicated.
Limitation. Since our analysis is built on the works of [15 16
16].
Conclusion. We propose to leverage projected noisy stochastic gradient descent (PNSGD) for machine unlearning problem. We provide its unlearning guarantees as well as many other algorithmic benefits of PNSGD for unlearning under the convexity assumption. Our results are closely related to our new results on infinite Wasserstein distance tracking of the adjacent (un) (un)learning processes, which is also leveraged in our concurrent work for studying DP-PageRank algorithms (30]. Extensive experiments show that our approach achieves a similar utility under the same privacy constraint while using 2% and 10% of the gradient computations compared with the state-of-the-an gradient-bases approximate unlearning methods for mini-batch and full-batch settings, respectively.
10

---

Acknowledgments and Disclosure of Funding
The authors thank Sinho Chewi, Wei-Ning Chen, and Ayush Sekhari for the helpful discussions. Chien, H. Wang and P. Li are supported by NSF awards OAC-2117997 and JPMC faculty award.
References
[1] N. Carlini, C. Liu, U. Erlingsson, J. Kos, and D. Song, "The secret sharer: Evaluating and testing unintended memorization in neural networks," 28th USENIX Security Symposium (USENIX Security 19), pp. 267-284, 2019.
[2] C. Guo, F. Bordes, P. Vincent, and K. Chaudhuri, "Do ssl models have d', 'eja vu? case of unintended memorization in self-supervised learning," arXiv preprint arXiv:2304. 13850, 2023.
[3] Y. Cao and J. Yang. "Towards making systems forget with machine unlearning," in 2015 IEEE symposium on security and privacy, pp. 463 480, IEEE, 2015.
[4] L. Bourtoule, V. Chandrasekaran, C. A. Choquette-Chon H. Jia, A. Travers, B. Zhang, D. Lie, and N. Papernot, "Machine unlearning," in 2021 IEEE Symposium on Security and Privacy
(SP), pp. 141-159, IEEE, 2021.
[5] E. Ullah, T. Mai, A. Rao, R. A. Rossi, and R. Arora, "Machine unlearning via algorithmic stability," in Conference on Learning Theory, pp. 4126-4142, PMLR, 2021.
[6] E. Ullah and R. Arora, "From adaptive query release to machine unlearning," in International Conference on Machine Learning, pp. 14642-34667, PMLR, 2023.
[7] C. Guo, T. Goldstein, Hannun, and L. Van Der Maaten, "Certified data removal from machine learning models," in International Conference on Machine Learning, pp. 3832-3842, PMLR, 2020.
[8] A. Sekhari, Acharya, G. Kamath, and A. Suresh, "Remember what you want to forget: Algorithms for machine unlearning," Advances in Neural Information Processing Systems, vol. 34, pp. 18075- 18086, 2021.
[9] Neel, A. Roth, and Malvjei-Malvjjerdi,, "Descent-to-delete: Gradient-based methods for machine unlearning." in Algorithmic Learning Theory, pp. 931-962, PMLR, 2021.
[10] E. Chien, C. Pan, and O. Milenkovic, "Efficient model updates for approximate unlearning of graph-structured data," The Eleventh International Conference on Learning Representations, 2022.
[11] E. Chien, H. Wang, Z. Chen, and P. Li, "Langevin unlearning: A new perspective of noisy gradient descent for machine unlearning"" Advances in neural information processing systems, 2024.
[12] C. Dwork, F. McSherry, K. Nissim, and A. Smith, "Calibrating noise to sensitivity in private data analysis," in Theory of Cryptography: Third Theory of Cryptography Conference, TCC 2006, New York, NY, USA, March 4-7, 2006. Proceedings 3, pp. 265-284, Springer, 2006.
[13] M. Abadi, A. Chu, I. Goodfellow, H. B. McMahan, I. Mironov, K. Talwar, and L.. Zhang, "Deep learning with differential privacy." in Proceedings of the 2016 ACM SIGSAC conference on computer and communications security, pp. 308-318, 2016.
[14] B. Balle, G. Barthe, and M. Gaboardi, "Privacy amplification by subsampling: Tight analyses via couplings and divergences," Advances in neural information processing systems, vol. 31, 2018.
[15] Altschuler and Talwar, "Privacy of noisy stochastic gradient descent: More iterations without more privacy loss," Advances in Neural Information Processing Systems, vol. 35, pp. 3788-3800, 2022.
[16] M. Altschuler and K. Talwar, "Resolving the mixing time of the langevin algorithm to its stationary distribution for log-concave sampling." arXiv preprint arXiv:22 20.0::200008444,, 2022.
[17] V. Gupta, C. Jung, S. Neel, A. Roth, S. Sharif--Malvjerddi and C. Waites, "Adaptive machine unlearning," Advances in Neural Information Processing Systems, vol. 34, pp. 16319-16330, 2021.
11

---

[18] R. Chourasia and N. Shah, "Forget unlearning: Towards true data-deletion in machine learning." in International Conference on Machine Learning, Pp. 5028-6073, PMLR, 2023.
[19] I. Mironov, "Rényi differential privacy," in 2017 IEEE 30th computer security foundations symposium (CSF), pp. 263-275, IEEE, 2017.
[20] V. Feldman, I. Mironov, K. Talwar, and A. Thakurta, "Privacy amplification by iteration," " in 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pp. 521-532, IEEE, 2018.
[21] A. Yousefpour; Shilov, A. Sablayrolles, D. Testuggine, K. Prasad, M. Malek, Nguyen, S. Ghosh, A. Bharadwaj, J. Zhao, et al., "Opacus: User-friendly differential privacy library in pytorch," arXiv preprint arXiv:2 12298, 2021.
[22] J. Ye and R. Shokri, "Differentially private learning needs hidden state (or much faster conver- gence)," Advances in Neural Information Processing Systems, vol. 35, pp. 703-715, 2022.
[23] S. P. Meyn and R. L. Tweedie, Markov chains and stochastic stability. Springer Science & Business Media, 2012.
[24] R. Chourasia, J. Ye, and R. Shokri, "Differential privacy dynamics of langevin diffusion and noisy gradient descent," Advances in Neural Information Processing Systems, vol. 34, pp. 14771- 14781, 2021.
[25] L. Deng, "The mnist database of handwritten digit images for machine learning research," " IEEE Signal Processing Magazine, vol. 29, no. 6, pp. 141-142, 2012.
[26] A. Krizhevsky et al., "Learning multiple layers of features from tiny images." 2009.
[27] K. He, X. Zhang, S. Ren, and J. Sun, "Deep residual learning for image recognition," in Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 770-778, 2016.
[28] E. Chien and P. Li, "Convergent privacy loss of noisy-sgd without convexity and smoothness," 2024.
[29] Chewi, Sinho, "Log-CCocavve Sampling." htttps://chevisintte www.:/iiiiinin...uu... ww/main..mii..... pdf
2023. Online; accessed September 29, 2023.
[30] R. Wei, F. Chien, and P. Li, "Differentially private graph diffusion with applications in person- alized pageranks," Advances in neural information processing systems, 2024.
[31] A. Ganesh and K. Talwar, "Faster differentially private samplers via rényi divergence analysis of discretized langevin meme." Advances in Neural Information Processing Systems, vol. 33, pp. 7222-7233, 2020.
[32] T. Ryffel, F. Bach, and D. Pointcheval, "Differential privacy guarantees for stochastic gradient langevin dynamics," arXiv preprint arXiv:2201./1980 2022.
[33] S. Vempala and A. Wibisono, "Rapid convergence of the unadjusted langevin algorithm: Isoperimetry suffices," Advances in neural information processing systems, vol. 32, 2019.
[34] T. maintainers and contributors, "Torchvision: Pytorch's computer vision library." https
7/g haaubb.com/yytorcc//viiiioo 2016.
[35] A. Paszke, S. Gross, F. Massa, A. Lerer, J. Bradbury, G. Chanan, T. Killeen, Z. Lin, N. Gimelshein, I. Antiga, A. Desmaison, A. Kopf, E. Yang, Z. DeVito, M. Raison, A. Tejani,
S. Chilamkurthy, B. Steiner, I.. Fang. J. Bai, and S. Chintala, "Pytorch: An imperative style, high-performance deep learning library," in Advances in Neural Information Processing Systems 32, pp. 8024-8035, Curran Associates, Inc., 2019.
[36] A. Paszke, S. Gross, S. Chintala, G. Chanan, E. Yang, Z. DeVito, Z. Lin, A. Desmaison,
L. Antiga, and A. Lerer, "Automatic differentiation in pytorch," 2017.
[37] C. R. Harris, K. J. Millman, S. J. Van Der Walt, R. Gommers, P. Virtanen, D. Cournapeau,
E. Wieser, J. Taylor, S. Berg, N. J. Smith, et al., "Array programming with numpy." Nature,
vol. 585, no. 7825, pp. 357-362, 2020.
[38] P. Kairouz, B. McMahan, S. Song, O. Thakkar, A. Thakurta, and Z. Xu, "Practical and pri- vate (deep) learning without sampling or shuffling," " in International Conference on Machine Learning, pp. 5213-5225, PMLR, 2021.
12

---

A Additional related works
arguably the most popular method for ensuring a DP guarantee for machine learning models. Since it leverages the DP composition theorem and thus the privacy loss will diverge for infinite training epochs. Recently, researchers have found that if we only release the last step of the trained model, then we can do much better than applying the composition theorem. pioneer work (3T] studied the DP properties of Langevin Monte Carlo methods. Yet, they do not propose to use noisy GD for general machine learning problems. recent line of work [22 32] shows that PNSGD training can not only provide DP guarantees, but also the privacy loss is at most a finite value even if we train with infinite number of iterations. The main analysis therein is based on the analysis of Langevin Monte Carlo [29]33). In the meanwhile, [15) also provided the DP guarantees for PNSGD training but with analysis based on privacy amplification by iteration 20 None of these works study how PNSGD can also be leveraged for machine unlearning.
Differential privacy of noisy gradient methods. DP-SGD 13
B Limitations
Since our analysis is built on the works of [5|16] we share the same limitation that the (strong) convexity assumption is required. It is open problem how extend such analysis beyond
convexity assumption as stated 15 16]. While we resolve this open problem for the DP properties
of PNSGD in our recent work (28). is still unclear whether the same success be generalized to the unlearning problem. One interesting direction is to leverage the Langevin dynamic analysis [29] instead in (TT), which can deal with non-convex problems in theory yet conjecture the resulting bounds can be loose, and more complicated.
C Broader Impact
Our work study the theoretical unlearning guarantees of projected stochastic noisy gradient descent algorithm for convex problems. We believe our work is a foundational research and does not have direct path to any negative applications.
D Standard definitions
Let f Rd + R be mapping. We define smoothness, Lipschitzness, and strong convexity as follows:
L-smooth: Vx, R., [V - v((i)] < L||T yll
(3)
m-strongly convex: VE E Rd (x v. Vf(x) vʃ(v)) 2 ml| - 211²
(4)
M-Lipschitzs: V Vz E ER, [[((x) f()il s M| 1 y/l-
(5)
Furthermore, we say f is convex means it is O-strongly convex.
E Existence of limiting distribution
Theorem. Suppose that the closed convex set C C Rd is bounded with C having a positive Lebesgue measure and that ff(:; d.) C + Ed is continuous for all i [n]. The Markov chain {z, xf } in Algorithm for any fixed mini-batch sequence B= (Bi) // admits a unique invariant probability measure B on the Borel r-algebra of C. Furthermore, for any x E C, the distribution of at conditioned on 4t = x converges weakly to UDDB as f
The proof is almost identical to the proof of Theorem 3.1 in and we include it for completeness. We start by proving that the process {a, == 2 admits unique invariant measure (Proposition E.I and then show that the process converges to such measure which is in fact probability measure (Theorem F.2 Combining these two results completes the proof of Theorem 3.11
Proposition E.1. Suppose that the closed convex set C C Rd is bounded with Leb(C) 0 where Leb
denotes the Lebesgue measure and that V ff(:d) C I is continuous for all i [n). Then the
13

---

Markov chain {=:== =it defined in Algorithm 7 for any fixed mini-batch sequence B = (8) (83)
admits unique invariant measure (up to constant multiples) on B(C) that is the Borel a-algebra of C.
Proof. This proposition is direct application of results from 23 According to Proposition 10.4.2
in [33 it suffices to verify that { is recurrent and strongly aperiodic.
1. Recurrency. Thanks to the Gaussian noise W,, {2t} is Leb-irreducible, i.e., it holds for any x E Cadd any E B(C) with Leb(A) > that
[(x, A) == P(TA < +oo zo = z) > 0.
where TA = in 2 0 2 E A} is the stopping time. Therefore, there exists Borel
probability measure 1/ such that that { is w/-irreducible and 1 is maximal in the sense
of Proposition 4.2.2 in [23]. Consider any A E B(C) with (A) > 0. Since { is qf-ireducible, one has Lıx, A) = P(TA < too Zg x) > 0 for all x E C. This implies that there exists
0. 8 O, and E B(C) with Leb(B) > O. such that
P(IT E A xo x) 2 8, Vx E B. Therefore, one can conclude for any C that
Ul, = Σ
P( E A No 22)
P(I4T EAI 2e E B,00 2) P(xe E B zo x)
[=1
2 8
inf Px, E B 12-1=1) NEC
t=1
=+0,
where used the fact that inf P(zz E B x1-1 3) inf P(zi E B Io y) O that is implies by Leb(B)=
y)
and the boundedness of C and Ulegars Vf(C; d,). Let us
remark that we actually have compact Usegm/n VS(C; d.) since compact and V [ d,)
is continuous. The arguments above verify that { recurrent (see Section 8.2.3 in 23 for definition).
2. Strong aperiodicity. Since C and Uieg V de) are bounded and the density of We has uniform positive lower bound on any bounded domain, there exists non-zero multiple of the Lebesgue measure, say V1, satisfying that
P( E xo x) 2 (A), YzEC, A E B(C).
Then } is strongly aperiodic by the equation above and (C) > 0 (see Section 5.4.3 in 23 for definition).
The proof is hence completed.
Theorem E.2. Under the same assumptions as in Proposition E.1 unique invariant probability measure VDDB on B(C). Furthermore, for any I E C, the distribution of I xf generated by the learning process in Algorithm conditioned on Zo = I converges weakly to VaIS as + 30.
the Markov chain {x²} admits
Proof. It has been proved in Proposition E. that {are} is strongly aperiodic and recurrent with an invariant measure. Consider any A E B(C) with (((A) >> O and use the same settings and notations as in the proof of Proposition E.1 There exists 2 0, 8 > 0, and B E BCC) with Leb(B) (B) > such
that P(rr E A Hо x) 2 o, v E B. This implies that for any 2 0 and any E C,
P(14T++1
Øx x) P(TT+1 E xo = =x)
> P(IT+1 E A æ E B, = r) P(æ1 E B TD = x) 2
where
= 8. inf ((t E B
20 = v) > 0,
yEC
14

---

which then leads to
Q(x, := P(z, A. infinitely often) +000
This verifies that the chain { is Harris recurrent (see Section 9 in 23 for definition). It can be further derived that for any x E C.
E(TA ro = x)
P(TA 2 t 2o x) (T+
P(TA> (T' 1)k 2 = x)
S
+
Σ (1 e) < +oc
Jmn
The bound above is uniform for all C and this implies that C is regular set of {2,, (see Section 11 in (23) for definition). Finally, one can apply Theorem 13.0.1 in [23) to conclude that there exists unique invariant probability measure uD on (CC) and that the distribution of x2 converges weakly to UDjB conditioned on xo x for any x E C.
F Proof of Theorem 3.2
Theorem (RU guarantee of PNSGD unlearning, fixed B). Assume AA X, f(:; d) is L-smooth, M- Lipchitz and m-strongly convex in æ. Let the learning and unlearning processes follow Algorithm[]] with v = M(D). Given any fixed mini-batel sequence B, for any 1, let 1j S t, the output of the Wth unlearning iteration satisfies (a, RU with c 1 1m, where
8 a- 1/2 a-1
(E) (2xx) + +2((2)))
a(2R)²
aZ c 2kn/b
(a))
6 2T/h E2((x)
2no
2n
1- In/b M
Z8 Tn/b min
22
c-/bbb cm/b
We first introduce an additional definition and a lemma needed for the our analysis. Definition F1 (Shifted Rényi divergence). Let μ and be distributions defined on a Banach space (Rd || []). For parameters 2 0 and a 2 1, the z-shifted Rényi divergence between μ and v is defined as
D(2 (mll))
inf Da(p'llv).
(6)
Lemma F.2 (Data-processing inequality for Rényi divergence, Lemma 2.6 (16).. For any a 2 any (random) map h Rd + IRd and any distribution μt, with support R
1,
Do ( S Dalullu),
where hig fI denotes the pushforward operation for a function h and distribution μ.
Proposition F.3 (Weak Triangle Inequality of Rényí divergence, Corollary 4 in [19). For any a > p. 9 > satisfying 1 1/p- + 1/9 and distributions P, Q. R with the same support:
1 P. D (PI12) 1/(a-11p)
(a(PIR))
Proof. Recall that from the sketch of proof of Theorem 3.2 we have defined the six distributions: UDjB, BB 1 are the stationary distribution the learning process, distribution at epoch T the learning process and distribution at epoch of the unlearning process. Note that we learn on dataset D and fine-tune D'. On the other hand, the corresponding distributions of "adjacent" processes that learn on D' and still unlearn D' are denoted as I'D VTis PK| similarly. Note that v is 0.f
U., 0.1
the distribution of retraining from scratch on D', and we aim to bound da (P' ( 1/((s) for all possible D, D' pairs. By Proposition
E3 we know that for any a > 1, by choosing = = 2, we have
do (p (16))
a 1/2
(dza (VD1 27/)) + d2a (UD Po pk
(8)
-
15

---

Recall the Definition 2.1 that (P.Q) = max( Da (Q] P)) for distributions P. Q. The
above inqquality correct since consider any distributions P. Q, R. by Proposition F3 we have
Da
a D20 (PIIQ) -2a-
(9)
a
(0) a
d2a (P.Q) + 12a
(10)
w
d2a (P, + d2a (Q.
(11)
SVS
+ d2 (2. R))
(12)
(13)
where (a) is due to the definition of Rényi difference, (b) is due to the monotonicity of Rényi divergence in a, and (c) is due to the fact that for all a 1. a= 21. 1. Similarly, we have
D. (R a
+ (Q, R)).
(14)
Combining these two bounds leads the weak triangle inequality for Rényi difference.
Now establish the upper bound of da (PDr [B, ( which we denoted {I(() in Theorem 3.2
We first note that due to the projection operator Ie.,, we trivially have Wo v0) S 2R. On the other hand, note that TTis is the distribution of the learning process at epoch T with respect to dataset D', where VD'I8 is the corresponding stationary distribution. Let us "unroll" iterations so that v 1 j. We apply Lemma 2.6 for these two processes, where the initial distribution are μr0 1 and 1ó VD*IS. The updates (x) [c(()) - N Eien (f([(())) are with respect the dataset D', and S. = [(, Ia). First, note that we have no² instead of o² as in the Lemma[2.6 hence we need to apply change of variable. The only thing we are left to prove is that
2.6
th is c-contractive for = rym and any 1. This because for any mini-batch B and any data point d' E X, E B' of size b, we have
(1))(z) vi - 7
Σ Vf(lc(())d)) -1ec01 + ! Σ v[(Uc(()):d)))
IE
IBB
(15)
IA
(Iec()) -
|I
(16)
iEBS
(1 - [1-mm)|[[a [T - (x('l)
(17)
< (1 - 7m) æ - 1|
(18)
Finally, due to data- Sata-processing inequality for Rényi divergence (Lemma F22 applying the final
projection step does not increase the corresponding Rényi divergence. As a result, by Lemma 2.6 we have
D1 2 WWo
TTB
(2R) 2n
Da(PDiBBll71)) <
2T//
2Tn/b
(19)
2n0²
where the last inequality is due our naive bound W (UDys ( One can repeat the same anal- ysis for the direction (r 0. (I)))s)) which leads to the same bound by symmetry of Lemma 2.6 Together we have shown that
a(2R)²
da (UDisllu
(20)
2no2
16

---

Now we focus on bounding the term (v Pk(s). We once again note that jorjs is the stationary distribution of the process P since we fine-tune with respect the dataset 'D' for the unlearning process. As a result, the same analysis above can be applied, where the only difference is the initial Wo distance between VD [B, Pojs
aW (VD1 PoIB) 2Kn/b.
da (B PkIB) (KII))
(21)
2no²
We are left with establish an upper bound of W (VDr B. p Note that since Woc is indeed metric, we can apply triangle inequality which leads to the following upper bound.
W (VDi PojB) S Wo (VDr "D1B) + Woo (uD)o PojB)
(22)
From Lemma 3.3 we have that
5o0 (TiB) I min ( Tn/b ca/b c 1o Mn
(1-
2 .2R I min cn/b b
.2R
(23)
b
where the last inequality is simply due to the fact that < Since the upper bound is independent of T. by letting T oo, and the definition that PDjs, 1a are the limiting distribution of 1s T respectively, we have
21 Woc (VD)B S min 1- cm/b b 2R
(24)
On the other hand, note that by definition we know that PQ.s = 1/1.8 Thus by Lemma 3.4 we have (recall that c = vpm)
W (VD Pois) Woo (1 PDDB) S W vDIB) S 2R x 20/b
(25)
where the last inequality is again due to the naive bound induced by the projection to CR for Woo (18. PDJB). Together we have that
2nM 2R Zg.
WocUp B. PojB) 2R x Tofb + min c²/b b
(26)
Combining things we complete the proof.
G Proof of Theorem 3.11
Theorem. Under the same assumptions in Corollary 3.7 Assume the unlearning requests arrive
sequentially such that our dataset changes from D Do Di + ... + Dss where D., D,+1 are adjacent. Let (+(0) be the unlearned parameters for the th unlearning request at kth unlearning epoch 0,(e) 0,(s+1) УK, ~ DD, |s. where Yo
and jth iteration following Algorithm ( on D, and Vo and K2 is the unlearning steps for the th unlearning request. For any [S]. we have
0.(0) Foe
W (UD (DD..I1,, VD,18) v 7(0)
where 2L z(a+1)_ = Kin/b 2 + ZB, 2R), n..
z ZI.. ZB is described in Corollary 3.7 and
The proof is direct application of triangle inequality, Lemma and induction. For the base case & = it trivial since ūp, = VD, as we choose Yo 0.(0) _ Thus by our definition that ZB is the upper bound of W (Vo (DDB)) for any adjacent dataset D, D' D'. Apparently, we also have
We will prove by
W (VDo (D) = W (VDo vD,18) s Zg Z
(27)
17

---

For the induction step, suppose our hypothesis is true until step. Then for the + step we have
(a) I
W (DD. DD++
W
+ Woo (UD, [8: IB)+
(28)
(6)
Wa (VD, DDD118) + Zs
(29)
(c) K, 1n.-nn/11 W (VD.-.18: VD, (8) 7s
(30)
(4) ck_ + ZB
(31)
where (a) is due to triangle inequality as W0 is a metric. (b) is due to Corollary 3.7 where Zø is
an upper bound of Wx distance between any two adjacent stationary distributions. (c) is due
Lemma 3.4 3.4 and (d) is due to our hypothesis. Finally, note that 2/t is a natural universal upper bound
due projection CR, which has diameter 2R. Together complete the proof.
H Proof of Corollary 3.7
Note that under the training convergent assumption, the target retraining distribution is directly VDrj8 so that do not need the weak triangle inequality for Rényi difference. Similarly, do not need
the triangle inequality for the term Zg. Directly using E2(a) with ZB min I- from Theorem 3.2 leads the result.
2yM 2R
I Improved bound with randomized B
Corollary, Under the same setting as of Theorem 3.2 with random mini-batch sequences described in Algorithm Then for any 1, and v7 7, the output of the Wth unlearning iteration satisfies (a, c)-RU with e = 1 17m, where
1
a(a aaaa-11 1)28 22kn/hh 21j0²
a log Eg exp
where ZB is the bound described in Lemma 3.3
We first restate the lemma in [22). which is an application of the joint convexity of KL divergence.
Lemma L.1 (Lemma 4.1 in 22 ). Let U1," ",,... Um and v/ V'm be distributions over Rdd, For any
and any coefficients pl, Pm such that Σ Li=1 Ps 1, the following inequality holds.
172
m
exp((a-1)1) 1)D
Piv Σ P(()))
(32)
p exp((a (vill())
(33)
The proof of Corollary 3.8 directly follows by repeating the proof of Lemma 3.7 but with the B
dependent Zg described in Lemma 3.3 Then leverage Lemma leads to the result.
Woo bound for batch unlearning
Corollary J.1 (Woc bound for batch unlearning). Consider the learning process in Algorithm on adjacent dataset D and D' that differ in 1 S. S points and fixed mini-batch sequence B. Assume vd X. f(r; d) L-smooth, M M-Lipschitz and m-strongly convex in I. Let the index of different data point between D. D' belongs to mini-batches Bio BBh ..... BiG-1, each of which contains 1 < Sj, < b such that EG-1 Sj, S. Then for I. and (1 1pm), we have
(1 11-2" G-1
(1-
a/b- 2 2R
0, W (2 (T)))) < min
Σ
b
18

---

Proof. The proof is a direct generalization of Lemma 3.3 Recall that for the per-iteration bound within an epoch, there are two possible cases: 1) we encounter the mini-batch B that contains indices of replaced points or not. This is equivalently 1) j { or 2) $ (ig)a=0
Let us assume that 1) happens and j jy for g {o..... G 1). Also, let denote the set of those indices as Sj, with a slight abuse of notation. By the same analysis, we know that
1 (a
(34)
-
Σ
||l| 23 -
-
(35)
1EBB
Σ SES,a
|
-
+ -
(36)
b
For the first term, note that the gradient mapping (with respect to the same data point) is contractive with constant (1 vpm) for 7) S L. thus have
| - 2² (Vf(=]d - Vs(al' d.)) s (1-mm)][a -
(37)
For the second term, by triangle inequality and the M-Lipschitznesss of f we have
|ل - - + (V :f(=
(38)
= || - - + (V d.) - V/
+ ( d.) - Vs(af';
(39)
< (1 m - + - d.) +|
f [ d()l
(40)
S (1 - 2r
(41)
Note that there are S3 terms above. Combining things together, we have
(x/ - (+4''l s (1 (1-rm)]laf 2f''l || + Mr,
(42)
Iterate this bound over all n/b iterations within this epoch, we have
2n 11, (4241) - 25 & (1 - mym))/////1 (eb3(()))) (a + Σ (1- mmmmm/0-s--11
G-1
b
5=0
(43)
The rest analysis is the same those in Lemma 3.3 where iterate over T epochs, infimum over all possible coupling, and then simplify the expression using geometric series. Thus we complete the proof.
K Proof of Proposition 3.9
Proposition. Under the same setting Corollary 3.7 with b = n, S m
222 and assume the minimizer
of any fn is in the relative interior of CR S IR for any given adjacent dataset pair D, D' the output of the th unlearning iteration b satisfies
1 2
2Tdo²
E (xk)
inf (x)) S M min( 1-c 2R) #CCR
+ m
(44)
The proof is based on the following key lemma from 24
Lemma K.1. For M M-Liscchitz m-strongly convex and L-smooth loss function fo(x) over the closed bounded convex set Cn S. Rd with radius R. step size n S m and initial parameter Du Vo, the 212
excess empirical risk of the learning process of Algorithm [or T epoch is bounded by
L 2 exp(-mqTT)B 11 x= [1
2Ldo2
(f( - fo(x")]
(45)
m
where x² is the minimizer of fo(z) in the relative interior of CR and d is the dimension of parameter.
19

---

Clearly, we can see that under the convergent assumption of Corollary 3.7
the excess risk of v6 = 2ccc
2Ldo²
[[ - [D(='){))))))))))')>"}})))
(46)
m
This is true since ||00 - x=1| S 2R is finite by the boundedness of CR.
Now we are ready to prove Proposition 3,9
Proof. Start by observing that
E| (vk) [ = B----E/D/-- (vk) fD (D (yf fD (v=("")) }},
(47)
where we recall that VK is the "adjacent process" of 5 that running noisy gradient descent D for both learning and unlearning processes. As a result, we have 0. IT for T learning epoch. By taking T + oo under the convergent assumption and utilizing Lemma have
2Ldo²
El/D - (b')) S
(48)
Hence left with analyzing the first term. We will bound it in terms of 11y 2 Note 0.1 that we choose a particular coupling between v VK as in Lemma 3.3 where the Gaussian noise in vk. UK are identical almost surely. Also for simplicity, we drop 0 in the superscript since we are analyzing the full batch case. By M-Lipschitzness of fD,, we have
Il-
lIfo(uk) for (1x)) s Mlyy UK v
(49)
For 11yb Vx V/'l. we have
lyy Vkll
(50)
||I_c_lk-II- - v/ (VVDD-uu--i 2 w- 1ookk-1n///<(kk--- + v 2n
WK- -1]]
(51)
< 11yk-1- (/N (2 // (VK-1))
(52)
$ (1 - 1pm) (/)m)llx==1 1
(53)
where the first inequality is due to the fact that Ic, is contraction map and noise cancels out due to our coupling of v UK 0.1 The second inequality is due to the fact that gradient update is
(1 - (1-mm))-ontraction map when for is L-smooth, m-strongly convex and n S L. By iterating this bound, we have
[fD()))) fo( S M(1 M(1--n) 1 2n
11v0 b6ll
(54)
I K min(
22).
(55)
1 1 n
where c 1- myy and the last inequality is due to Lemma 3.3 for the case b = n and taking the limit T + oc. Combining all results together, we have
El.D (vk) - (u")
(56)
< LElD - (or 2Ldo²
(57)
m
2Ldo²
< EEllfor - f 0,1 I1
(58)
1 M
2L
$ K min(
.2R)
(59)
n
m
Together complete the proof.
20

---

L Proof of Lemma 3.3
Lemma (Wec between adjacent PNSGD learning processes). Consider the learning process in Algorithm on adjacent dataset 'D and D' and a fixed mini-batch sequence B. Assume vd E X, f(æ; d) is s-ooohth, M-Lipschitz and m-strongly convex in æ. Let the index of different data point between D, D' belongs to mini-batch B Then for S T. and let c = (1 - rjm), we have
1 Tw/b
20/b- 10-1 2n
co TTi)) & min
1 - ca/b 1-
b ,,2
Proof. We prove the bound of one iteration and iterate over that result under specific coupling of the adjacent PNSGD learning processes, which is by definition an upper bound for taking infimum over all possible coupling. Given mini-batch sequence B, assume the adjacent dataset D. DD' differ index in E [n] and in belongs to 1 mini-batch (i.e., in E B For simplicity, we drop the condition on I for all quantities in the proof as long as it is clear that we always condition fixed B. Let us denote t),(2)) = r 1 Eien V Vf(x; d() and similar for vij on D'. Note that for some coupling of vl on! denoted as .
esssup (zt - ) ||
x 111
(60)
=esssup ((2) w Cod w m |/ (1:t) -0/((04)) + 2no 2
(61)
S &esssup ((x) wi) (f w ) (x?) - 1//3 (1f ||| + 2n W/ W/
(62)
Now, note that by definition the noise W is independent of x/. we can simply choose the coupling so that w wa for all j and z To 0.' due to the same initialization distribution. So the last term is For the first term, there are two possible cases: 1) j = jo and 2) j # jo- For case 1), we have
(63)
1 Σ
| - + +VV+VVV(( v
(64)
1 ||ا| - ot (VScd; v (
(65)
For the first term, note that the gradient mapping (with respect the same data point) is contractive with constant (1 77m) for 1) S i. thus we have
|| - =t + (V [x];; - v s <11 - mpm) - -
(66)
For the second term, by triangle inequality and the M-Lipschiteness of we have
| xt² + 1 (VV[((/ vf(="';d
(67)
= || - 2 + [V<
- ( + -
(68)
< (1 , - - + [<> d: [
(69)
S (1 - - - -
M.
(70)
Combining things together, we have
M
(1/)((/)) (ft < (1- mm)] 2
(71)
On the other hand, for case 2) can simply use the contrativity of the gradient update for all terms, which leads to
(3/)) (xf")) S -mm))/l - 21'11
(72)
Combining these cases, we have
esssup, esssup,|la?*** - x.(+ < esssup,, m)m)llaa - 2 || + MnM
1 jo]
(73)
b
(74)
21

---

where 1 jol is the indicator function of the event j = jo- Now we iterate this bound within the epoch t, which leads to an epoch-wiss bound
csssup,llaa441 - =241ll I esssup, - 1mm) - 2 + (1-mm))m0-oo--- 2n
(75)
b
(76)
We can further iterate this bound over all iterations T, which leads to
esssup, esssup,,124. 24'1l I esssup, (1 7mm) // 20 1 Σ (1 nm) (t)) 2
T-1
(77)
(m))((+)n/// Mn
(78)
(79)
where the last equality follows by our choice of coupling y such that = og due the same initialization distribution. Now by taking the infimum overall possible coupling y and simply the expression, we have
1 - Ta/o
1 ca/b co/b- 1o/b--o-11 Mn
W (17 (TiB)
(80)
Finally, note that there is also a naive bound W Wo 4T1B) S 2R due to the projection UT. Combine these two we complete the proof.
0,1
M Proof of Lemma 3.4
Lemma (W between PNSGD learning process to its stationary distribution). Following the same setting as in Theorem 3.2 and denote the initial distribution of the unlearning process as vg- Then have
Woo PD|B) < (1-1mm) Tn/ (vo PD1B).
Proof. We follow similar analysis as in Lemma 3.3 but with two key differences: 1) our initial Wo distance is not zero and 2) we are applying the same c-CNI. Let us slightly abuse the notation to denote the process xt ~ ugah be the process of learning on D as well but starting with of = VDJB- As before, we first establish one iteration bound with epoch f, then iterate over n/b iterations, and then iterate over T to complete the proof. Consider the two CNI processes a/ x²" with the same update (2) = x - o Eieg ff(x; d,), where x ~ of and z0 ~ VDISS We will use the similar coupling construction in the proof of Lemma 3.3 (i.e., W W However, note that will not restrict the coupling between the two initial distributions v8 PojB and r0d VDjss Let denote the coupling for W as "/ and the coupling for the initial distributions vg = Pojs and vo VDiS as 7/- We denote the overall coupling as 7 = (",, nw). For our specific choice of coupling ww. we have
(b) (a) & (x/))())) - (xf(" 2n (W? w S (10)( (5 xz 1111
(c) (1 (81)
||as i+
mm))l x2'1l.
where (a) is due to the fact that projection Te is 1-contractive, (b) is due to our coupling choice on the noise distribution, and (c) is due to the fact that v/ is (1 rmm) contractive and the coupling choice the mini-batch.
Now we iterate the bound above within the epoch and then over T' epoch similar as before, which leads to the per epoch bound follows
esssup,, 1|2 0. < esssup, (1 -
- 2011 esssup,, (1 mmm) T2/b 2 0/1 1.
(82)
22

---

Note that this holds for all coupling "r for initial distributions. Let us now choose specific (tie break arbitrary) "is so that the W (VoIB: "DDB) esssup,, || T coupling Yr we have
0,7 is attained. For this specific
esssup ||,9 27 S (1 mmmmmm////)
Tw/h Th/" (Pops, VD B)-
(83)
Finally, by the definition infimum and observe that य. VDiS due to the stationary property of PDjB (which is independent of our choice of coupling), we have
oo (vy B (DBB) I esssup (w) || 21'1 s mm)) mpm)mm////n Tw/ (Vo) By VDD B)-
(84)
Hence we complete the proof.
N Experiment Details
N.1 R)U to (c, d)-Unlearning Conversion
Let us first state the definition of (c, -unnlermin from prior literature (7-9)
Definition N.1. Consider randomized learning algorithm M x + æº and a randomized unlearning algorithm 21 IR x X x X + R. We say (M,U) achieves (e, 6) -unlearnnn if for
any adjacent datasets D, D' and any event E, we have
P P(U(M(D), D,D" C E) S exp(()) C E) +
(85)
(MM(D)) S E) S exp(c)P (U(M(D), S E) +
(86)
Following the same proof of RDP-DP conversion (Proposition 3 in 19 we have the following EQ to (c, 5)-unleamnnng conversion as well.
Proposition N.2. If (), achieves (a, R)R it satisfies (e, --nllaannnn as well, where
log(1/6)
é == + 1-1
(87)
N.2 Datasets
MNIST (25 contains the grey-scale image of number number 9, each with 28 x 28 pixels. We follow [9] to take the images with the label 3 and 8 as the two classes for logistic regression. The training data contains 11264 instances in total and the testing data contains 1984 samples. We spread the image into
Rd d 724 feature as the input of logistic regression.
CIFAR-10 [26] contains the RGB-scale image of ten classes for image classification, each with 32 x 32 pixels. We also select class #3 (cat) and class #8 (ship) as the two classes for logistic regression. The training data contains 9728 instances and the testing data contains 2000 samples. We apply data pre-processing on CIFAR- by extracting the compact feature encoding from the last layer before pooling of an off-the-shelf pre-trained ResNet18 model [27) from Torch-vision library (34 as the input of our logistic regression. The compact feature encoding is IR d 512.
All the inputs from the datasets are normalized with the & norm 1. Note that We drop some date points compared with (IT) to make the number of training data an integer multiple of the maximum batch size our experiment, which is 512.
N.3 Experiment Settings
Hardware and Frameworks All the experiments run with PyTorch=2.1.2 1.2 (36 and numpy=1.24.3 (37]. The codes run server with single NVIDIA RTX 6000 GPU with AMD EPYC 7763 64-C Processor.
Problem Formulation Given binary classification task D = (x, E Rd, M E (-1,+11),, our goal is to obtain set of parameters w that optimizes the objective below:
L(w; D)
1(w x; vii + w/
(88)
72
23

---

where the objective consists of standard logistic regression loss 1(w I,, Mr) = log (uow" "wwwx,) x.).
where (t) I+exp[-7] is the sigmoid function; and &g regularization term where a hyperpa- rameter to control the regularization, and we set X as 10-6 across all the experiments. By simple
algebra one can show that
Vl(w Xs. vk) = (a(ww x:) - 1)M1 + Aw, oyyw' xx))x,x Ald.
(89)
Vi((w' Xz, v/) oluww x;) x
(90)
Due to (yewTx) E [0, 1], it not hard to see that we have smoothness 1/4 + À and strong convexity A. The constant meta-data of the loss function in equation (88) above for the two datasets shown in the table below:
Table I: The constants for the loss function and other calculation on MNIST and CIFAR-10.
expression
MNIST
CIFARIO
smoothness constant strongly convex constant m Lipschitz constant M RDP constant 8
$ +
1 +
+
0.0112
0.0097
gradient clip
1 8.8778e-5
1/n
0.0001
The per-sample gradient with clipping w.r.t. the weights of the logistic regression loss function is given as:
Vetip((w x,, B/)) = Ikrr (lo(y, x; - 1));x.) + Aw,
(91)
where Ie denotes the gradient clipping projection into the Euclidean ball with the radius of M, to satisfy the Lipschitz constant bound. According Proposition 5.2 of (22). the per-sampling clipping operation still results in a L-smooth, m-strongly convex objective. The resulting stochastic gradient update on the full dataset as follows:
Veiipl(w' Xi, Wi),
(92)
Finally, we remark that in our specific case since have normalized the features of all data points (i.c., ||ж||| = 1), by the explicit gradient formula we know that (I( xx) 1)y,x, S
Learning from scratch set-up For the baselines and our PNSGD unlearning framework, we all sample the initial weight randomly sampled from i.i.d Gaussian distribution N(ro, 20 where μo is a hyper-parameter denoting the initialization mean and we set as O. For the PNSGD unlearning method, the burn-in steps T w.r.t. different batch sizes are listed in Table. 2 we follow T' = 10, 000 for the baselines (D2D and Langevin unlearning) to converge.
111 and set
Table The Burn-in step for different batch sizes for the PNSGD unlearning framework
batch size
32
128
512
full-batch
burn-in steps
10
20
50
1000
Unlearning request implementation. In experiment, for unlearning request of removing data point i, we replace its feature with random features drawn from (0, (a) and its label with random label drawn uniformly at random drawn from all possible classes. This is similar to the DP replacement definition defined in 38) where they replace point with a special null point
General implementation of baselines D2D 19:
Across all of our experiments involved with D2D, we follow the original paper to set the step size 2/(L m).
24

---

For the experiments in Fig. 3a we calculate the noise to add after gradient descent with the non- private bound as illustrated heorem. (Theoree in [9]; For experiments with sequential
unlearning requests in Fig. 3b we calculate the least step number and corresponding noise with the
bound Theorem. 0.2 Thoremm 28
(9).
The implementation of D2D follows the pseudo code shown in Algorithm 1,2 in 9 as follows:
Algorithm 2 D2D: learning from scratch
Input: dataset D
2: Initialize Wo
3: for = 1, 2....... 10000 do
4: W, WW-1
2
x E (V (Vdip((w(
I.
5: end for
6: Output: W WT
Algorithm 3 D2D: unlearning
1: Input: dataset D,-1, update u,; model w;
2: Update dataset D; D;-1 u
3: Initialize W/=
4: for 1...., do
5: w = w I+m
2
x Ex 3
6: end for
7: Calculate 7 L-m
8: Draw Z N/0, 0² Ia)
9: Output w; WT.
The settings and the calculation of I, Algorithm. are discussed in the later part of this section and could be found in Section. O
Langevin unlcarning [1]
We follow exactly the experiment details described in
General Implementation of PNSGD Unlearning (ours)
We set the step size 7) for the PNSGD unlearning framework across all the experiments L/L.
The pseudo-code for PNSGD unlearning framework is shown Algorithm.
N.4 Implementation Details for Fig. 3a
In this experiment, we first train the methods on the original dataset D from scratch to obtain the
initial weights Wo- Then we randomly remove a single data point (S = 1) from the dataset to get the new dataset D', and unlearn the methods from the initial weights and the accuracy on the testing set. We follow 11 and set the target è with 6 different values as [0.05, 0.1, 0.5, 1, 2, 5). For each target
For D2D, we set two different unlearning gradient descent step budgets as / = 1, 5, and calculate the corresponding noise to be added to the weight after gradient descent D according Theorem. O.1
For the Langevin unlcarning framework [1]. we the unlearning fine-tune step budget K 1 only, and calculate the smallest a that could satisfy the fine-tune step budget and target at the same time. The calculation follows the binary search algorithm described in the original paper.
For the stochastic gradient descent langevin unlearning framework, we also the unlearning fine-tune step budget as K 1, and calculate the smallest a that could satisfy the fine-tune step budget and target& é at the same time. The calculation follows the binary search algorithm as follows:
25

---

Algorithm 4 PNSGD Unlearning: binary search that satisfy I and target budget
1: Input:target unlearn step budget K, lower bound Flow upper bound hnigh
2: while Ohigh Flow le
do
3: mmid = (Oew + hhigh) /2
4: call Alg. to find the least K that satisfies é with mid
5: if K K then
6:
Thggh mid
7: else
8:
New = mid
9:
end if
10: end while
return K
Algorithm 5 PNSGD Unlearning [non-convergent]: find the least K satisfying
I: Input:target burn-in I', projection radius R
2: Initialize K = 1,, >
3: while do
4: c= 1pm
5: E1 (a) a(2R)² 2Tnb
2n0 2
6:
Z
T- b
(a) at2 2kn/b Tn/b
7:
2n
8:
( a-1/2
a-1 (0n (2a) E2(2)))
9:
= minmiinm-- ((a) log (1/8))/(((a-
10:
K =++
end while
12: Return K
We set the projection radius as R = 100, and the a found is listed in Table.
Table 3: a of PNSGD unlearning.
0.05
0.1
0.5
5
b=128
0.2165
0.1084
0.0220
0.0112
0.0058
0.0025
CIFAR-10
full batch
1.2592
0.6308
0. 0.1282
0.0653
0.0338
0.0148
b=128
0.0790
0.0396
0.0080
0.0041
0.0021
0.0009
MNIST
full batch
0.9438
0.4728
0.0960
0.0489
0.0253
0.0111
26

---

(1/(1/)) N.5 Implementation Details for Fig. 3b
In this experiment, we fix the target 1, we set the total number of data removal as 100. We show the accumulated unlearning steps w.r.t. the number of data removed. We first train the methods from scratch to get the initial weight wo, and sequentially remove data step by step until the data points are removed. We count the accumulated unlearning steps K needed in the process.
For D2D, According the original paper, only one data point could be removed time. We calculate the least required steps and the noise to be added according to Theorem, 0.2
For Langevin unlearning, we fix the 0.03, and we let the model unlearn [5, 10, 20) per time. The least required unlearning steps are obtained following [11].
For Stochastic gradient descent langevin unlearning, we replace single point per request and unlearn for 100 requests. We obtain least required unlearning step K following Corollary 3.7 The pseudo-code is shown in Algorithm. 6
Algorithm 6 PNSGD Unlearning: find the least unlearn step K in sequential settings
1: Inputstarget total removal S
2: Kisa- =
3: for i in range(S) do
4: Initialize Kis - 1| = 1
5: while E do
6: = mimm m o, b, Ki - 1]) +
7: Kisd - 1] = Kigli + a-1
8: end while
9: end for
Return Kist
Algorithm 7 c(a, o, k)
1: Input:target a, a, removal batch size per time, i-th removal in the sequence
2: c c= nm7
3: Return aZalh)² 2Kn/b 2np
Algorithm 8 (b)
1: c= -1- 2nM
2: return I-
N.6
Implementation Details for Fig. 3c and 3d
In this study, we fix S 100 to remove, set different a = [0.05, 0.1, 0.2, 0.5, 1] and set batch size as b = [32, 128, 512, full batch]. We train the PNSGD unlearning framework from scratch to get the initial weight, then remove some data, unlearn the model, and report the accuracy. We calculate the least required unlearning steps K by calling Algorithm.
Unlearning Guarantee of Delete-to-Descent
The discussion is similar to those in [1I we include them for completeness.
Theorem 0.1 (Theorem in 19). with internal non-private state). Assume for all d X. f(x; d) is m-strongly convex, M-Lipschitz and L-smooth in x. Define = L+m and I+m Let the learning iteration T + logg Rumm / log(1 //x) for PGD (Algorithm in (9)) and the unlearning algorithm (Algorithm 2 in (9, PGD funitu learned parameters before adding Gaussian noise)
2
(
27

---

run with I iterations. Assume (llg((1/)), let the standard deviation of the output perturbation gaussian noise a be
4/2M-
(93)
mn(1- - 7000-~"((/// (1/6) (1g(//))1))))) - Vlog(1/6)
Then achieves (e, 8) unlearning for add/remove dataset adjacency.
Theorem O.2 (Theorem 28 in (9), without internal non-private state). Assume for all d X, I (a;; L-m m-strongly convex, M- M-Lipschitz and L-smooth in Define ?, T+m and 1] I+tmm Let the learning iteration T 2 + log( 2 1og(1// ) for PGD (Algorithm in 191) and the unlearning algorithm (Algorithm 2 in (9]. PGD fine-tuning learned parameters after adding Gaussian noise) run with I + (ad//)///))) /6)) /t////g(///)////// (1/7) iterations for the ith sequential unlearning request, where
satisfies
v2d(1
log
(2g//)2/6)
(2g()
(94)
log(1/7)
Assume e (loo(1//)), let the standard deviation of the output perturbation gaussian noise o to be
8M
(95)
mn(1 2mm(1=")(/2loo(22 3c /2 12g(2/6) + 2c)
Then achieves -an unlearning for add/remove dataset adjacency.
Note that the privacy guarantee of D2D 99 is with respect to add/remove dataset adjacency and ours the replacement dataset adjacency. However, by a slight modification of the proof of Theorem O.] and O.2 one can show that a similar (but slightly worse) bound of the theorem above also holds for directly use the bound in Theorem O. O.I O.2 in our experiment. Note that (38] also compares special replacement DP with standard add/remove DP, where a data point can only be replaced with null element in their definition. In contrast, our replacement data adjacency allows arbitrary replacement which intuitively provides stronger privacy notion.
D2D For simplicity and fair comparison,
The non-private internal state of D2D. There are two different versions of the D2D algorithm depending on whether one allows the server (model holder) save and leverage the model parameter before adding Gaussian noise. The main difference between Theorem 0. and O.2 is whether their unlearning process starts with the "clean" model parameter (Theorem O.I or the noisy model parameter (Theorem O.2). Clearly, allowing the server to keep and leverage the non-private internal state provides weaker notion of privacy [9]. contrast, our PNSGD unlearning approach by default only keeps the noisy parameter so that we do not save any non- con-private internal state. As result, one should compare the PNSGD unlearning D2D with Theorem 0.2 for fair comparison.
P Unlearning Guarantees of Langevin Unlearning
In this section, restate the main results of Langevin unlearning and provide detailed comparison and discussion for the case of strongly convex objective functions.
Theorem P.1 (RU guarantee of PNGD unlearning, strong convexity). Assume for all D X", fo L-smooth, M M-Lisschitz, m-strongly convex and VD satisfies Cisr-ISS.. Let the learning process follow 2(1 merr)) ), 1). Given M is (o,,e)-RDD
m CLsI and min( m and yo = Txc = =M(D), for a > 1, the output of the Kth PNGD unlearning iteration achieves (ar,e (RU, where
the PNGD update and choose o²
1 20 CLSI
6 S exp
Eg-
(96)
Theorem P.2 (RDP guarantee PNGD learning, strong convexity). Assume f(:: be T-smooth. M- Lipschitz and m-strongly convex for all d E X. Also, assume that the initialization of PNGD
28

---

satisfiey 20" -LSI. Then by choosing 0 < S I with constant, the PNGD learning process is (a,50 (5) J-RDP of group size S 2 1 at thh iteration with
(8) 4
eq 10222 (1 exp(-mnn())
(97)
Furthermore, the law of the PNGD learning process is 2at -LSI for any time step.
Combining these two results, the (a,, E)-U guarantee for Langevin unlearning is
mnk
4a.5
S exp
(98)
m0212
On the other hand, combining our Theorem 3.2 with some simplification, we have
3.3 and using the worst case bound on Zg along
E S 2knbb a
2 (2
)
2
= =(1 mm))2k//
/
2M 2
= (1 -1-17m)2kkn 2k
2a
2nj
2njo²
mb
1)m
(99)
To make an easier comparison, we further simplify the above bound with b = n and x < exp( which holds for all x > 0:
8 S s7m) 2/n/ 22m)2Kn/6
1022 < exp( 2K nom
2a
4a
1 2mm
exp(-2K
4a
mo 222
mo²n2
2mmrj
(100)
Now we compare the bound (98) obtained by Langevin dynamic in [T] and our bound (100) based on PABI analysis. First notice that the "initial distance" in (TO0) has an additional factor 1/ (2mr). When we choose the largest possible step size 7 f. then this factor is d which is most likely greater than in a real-world scenario unless the objective function is very close to a quadratic function. As result, when K is sufficiently small (i.e., K 1), possible that the bound (98) results in better privacy guarantee when unlearning one data point. This is observed in our experiment, Figure [a Nevertheless, note that the decaying rate of (100) is independent of the Rényi divergence order a, which actually leads to a much better rate in practice. More specifically, for the case n = 10 (which is roughly our experiment setting). To achieve (1.1/n)-unlaan
guarantee the corresponding a is roughly at scale a R 10, since Tog(n)/(a= - 1) needs to be less than 1 in the (a,, &R-U to (e, 6) unleearnnn conversion (Proposition N.2p. As a result, the decaying rate of (TOO) obtained by PABI analysis is superior by a factor of 2a, which implies a roughly 20x saving in complexity for K large enough.
Comparing sequential unlearning. Notably, another important benefit of our bound obtained by PABI analysis is that it is significantly better in the scenario of sequential unlearning. Since only need standard triangle inequality for the upper bound 2 = min x Knn/b 2/1) + ZB, 21) of the (s + 1)th unlearning request, only the "initial distance" is affected and grows at most linearly in (i.e., for the convex only case). In contrast, since Langevin dynamic analysis in [II] requires the use of weak triangle inequality of Rényi divergence, the a in their bound will roughly grow at scale 2 which not only affects the initial distance but also the decaying rate. As pointed out in experiment and by the author [TT] themselves, their result does not support many sequential unlcarning requests. This is yet another important benefit of our analysis based PABI for unlearning.
29

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: All claimed theoretical results provided in Section and empirical studies are provided in
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
We discuss the limitation in section B
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
30

---

Justification:
All assumptions are stated for each theorem and proof for every theoretical statement is provided in the Appendix to
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification:
The code is provided in the supplementary material and experimental details
are stated in Appendix N
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
31

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification: All data used in the experiments publicly available with open-access licenses. The code is provided in the supplementary material and all experimental details stated in Appendix
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.co cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
y /nips. /nips.cc//ppppp httpss/ccccclcgguiueeeee///////e hwwbbiiicguiddes/oeeeuubiiii
for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/ettails
Question:
Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Answer: [Yes]
Justification:
All experimental details are stated in Appendix N
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented the core the paper to level detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: All experimental results are reported with one standard deviation gathered from 100 independent trials, which is stated Section
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emoor bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
32

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative еπτог rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
The compute resources used for our experiments are detailed in Appendix N.3
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported the paper (e.g., preliminary or failed experiments that didn't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics httpp::/neeurips..... httpp/pp.w..p..bbleeciciiiiiiiia
Answer: [Yes]
Justification: The authors have read the NeurIPS Code of Ethics and affirm that this work conforms with it in every respect.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: We briefly discuss why our work does not have any negative societal impact in Section
Guidelines:
The answer NA means that there is no societal impact of the work performed.
33

---

If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), faimess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but encourage authors to take this into account and make best. faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: All used datasets provided with citations to the original authors and works, where all of them have proper open access license.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include a URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
34

---

If assets are released, the license, copyright information, and terms of use in the thcode has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
package should be provided. For popular datasets, paperswi
latasets.paperssit
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
[NA]
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moode as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper doess not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
35

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
36


Reviews:
[{"review_id": "DNsGA2OaV7", "reviewer": "Reviewer_SMx2", "summary": "The paper presents a simple scheme for machine unlearning. The algorithm has two parts: in the learning part, the models learns using the original dataset D, and in the second part it unlearns using a neighboring dataset D’. The algorithm uses 1) same batches at every epoch, and same batches for both learning and unlearning, 2) Gaussian noise for both learning and unlearning. Based on Renyi differential privacy and the relation between Renyi unlearning and (ε, δ)-unlearning, the paper shows that the privacy parameter ε drops exponentially with every epoch.", "questions": "The assumptions in Theorem 3.2 are rather strong. You assume bounded domain + smoothness + Lipschitzness + strong convexity. Please justify these assumptions.\n\nThe notation is sometimes confusing. For example, there is notation \\nu_{T | B} and there is notation \\nu_{D | B}. Line 177: \\nu_{D | B}^{0, ‘} is undefined. In Lemma F.2, notation # is undefined.\n\nMinor issues:\n-- Is line 173 the definition of \\nu_{D | B}? Please make it clear. The wording sounds like this is already defined, and I spent quite some time trying to find the definition.\n\n-- Algorithm 1: please list algorithm’s parameters, such as η and σ \n\n-- Line 146: PABI was not defined\n\n-- Theorem 3.2: Z_B: you don’t actually use B\n\n-- Appendix D: Lipschitzness (no s after z)\n\n-- Line 548: “Proof” -> ”Proof of Theorem 3.2”\n\n-- I think the presentation could be simplified by focusing on some specific value of α\n\n-- C_R: Line 97 doesn’t match Line 169\n\n-- Theorem 3.2: relationship between D’ and D is not mentioned.", "limitations": "None", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Novel set of results", "weaknesses": "My main concern is the lack of utility bounds. It’s not hard to design an algorithm which guarantees privacy: just don’t use the dataset at all. What is the utility your algorithm achieves after K iterations of unlearning?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank reviewer SMx2 for their careful reading, positive assessment, and thoughtful comments. We address the weaknesses and questions below.\n\n**W1: ``No utility bound.``**\n\nWe thank reviewer SMx2 for the thoughtful comments. We agree that utility is an important aspect of the unlearning problem, but we do not think a utility bound is always necessary for a literature on machine unlearning. While a privacy bound is crucial to prevent the worst-case scenario, it is common practice in the machine learning literature to empirically measure utility in an average or data-dependent manner by conducting extensive experiments (as seen in the seminal DP-SGD paper [13]). This is also true in previous unlearning literature [7,11].\n\nHowever, we acknowledge that there are situations where a formal utility guarantee for the worst-case scenario is important. In such cases, the utility bound for noisy gradient descent is established in the differential privacy literature under strong convexity assumptions; see, for instance, Section 5 of [ref 1]. We will mention this point in our revision to provide clarity on when and how utility bounds can be applied.\n\n### Reference\n\n[ref 1] Differential privacy dynamics of langevin diffusion and noisy gradient descent, Chourasia et al., NeurIPS 2021.\n\n**Q1: ``Justifying the assumption``**\n\nWhile it is true that our set of assumptions—covering strong convexity, Lipschitz continuity or bounded gradient norm, and smoothness—appears restrictive, these assumptions hold significant practical relevance. They cannot be directly applied to the modern neural networks but they still encompass critical learning problems, including logistic regression, as empirically demonstrated in our experiments.\n\nIt is important to underscore that these assumptions are not unique to our work. They are foundational within the existing literature on machine unlearning [7-10] and are similarly necessary for studies related to the differential privacy (DP) guarantees and convergence of hidden-state PNSGD [15, 16, 22]. Specifically, the leading analytical approach for hidden-state PNSGD in privacy contexts—namely, the privacy amplification by iteration (or shifted divergence) analysis—relies on these assumptions.\nWe acknowledge that relaxing these constraints represents a meaningful direction for future research. Indeed, prior works [15, 16, 22] identify this as an open problem, and we are actively conducting research to address these limitations. \n\n**Q2:``Clarity of notations and typos``**\n\nWe thank reviewer SMx2 for their careful reading and suggestion. We will make sure all notations are defined and typos are corrected in our revision. \n\n**Q3:``Questions about Theorem 3.2``**\n\nThanks for pointing out the issue regarding $\\mathcal{Z}_{\\mathcal{B}}$. Originally we derived a $\\mathcal{B}$ dependent bound $\\mathcal{Z}\\_{\\mathcal{B}}$ by Lemma 3.3. There we have $j_0$ that depends on when the differing index between $\\mathcal{D},\\mathcal{D}^\\prime$ we encounter for a given mini-batch sequence $\\mathcal{B}$. In the current Theorem 3.2, we directly choose the worst case $\\mathcal{B}$, for which the bound is still valid (but loose). We will correct it in our revision and thank you again for spotting this issue.", "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": "", "extra_scores": {}}, {"review_id": "YMXwrue1OB", "reviewer": "Reviewer_DXXZ", "summary": "The paper proposes an effective and efficient machine unlearning algorithm based on projected noisy gradient descent (PSGD). The proposed methods can be extended to handle multiple unlearning requests.   The theoretical unlearning guarantee is established when the loss is assumed to be convex and smooth. Experiments verify the effectiveness of the proposed method.", "questions": "1. In algorithm, mini-batch sequence B is fixed. Is it reasonable in practice or analysis? \n\n2. The paper states that \"A smaller batch size b leads to a better privacy loss decaying rate\". This seems counterintuitive. Could authors give some explanation?", "limitations": "NA", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "1. A simple unlearning algorithm is established by PSGD, whose effectiveness and efficiency is verified by experiments. Especially, the experiments show that the proposed algorithm outperforms the baseline with less gradient complexity.  \n\n2. Theoretical analysis of unlearning guarantee for the proposed algorithm is established for convex smooth losses,  privacy-utility-complexity trade-off regarding the mini-batch size b for approximate unlearning is highlighted. \n\n3, The paper is well-written and easy to follow.", "weaknesses": "1. The smoothness of the loss is required, which might limit the algorithm's applicability.\n\n2. In experiments, a logistic loss with $\\ell_2$ regularization is considered. It would be better to provides some results on convex loss since the corresponding theory is given.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank reviewer DXXZ for their positive and thoughtful comments. We address the weaknesses and questions below.\n\n**W1:``Smoothness of the loss is required``**\n\nWe agree with reviewer DXXZ that smoothness assumptions can restrict the applicability of our approach, for which will also list it as a limitation in Appendix B in our revision. We are currently working on relaxing these assumptions in the follow-up works.\n\n**Q1: ``Is mini-batch sequence B to be fixed in Algorithm 1 necessary?``**\n\nIt is currently for analysis purposes, where similar limitations persist in the DP research of PNSGD [22]. We conjecture that one can randomly sample the mini-batch sequence at the beginning of each epoch. Our intuition is that instead of taking expectation with respect to $\\mathcal{B}$ at the end of the (un)learning process, we can take the expectation for each epoch where the stationary property of the distribution remains. Nevertheless, the rigorous analysis in this direction is left as an interesting future work.\n\n**Q2: ``Question about a smaller batch size $b$ leading to a better privacy loss decaying rate.``**\n\nThere appears to be a misunderstanding here. We are not saying that a smaller batch size $b$ will lead to better ***privacy loss***; instead, it will lead to a better ***privacy decaying rate***. To clarify, let's examine the bounds presented in Corollary 3.7, where the privacy loss is determined by the initial distance $Z_{\\mathcal{B}}$ and the privacy decaying factor $c^{2Kn/b} = (c^{2n/b})^K$ for $K$ unlearning epochs. Notably, a smaller $b$ will lead to a better privacy decaying rate $c^{2n/b}$ ($c < 1$), since we are running more contractive updates (see Figure 1, green part) per epoch.\n\nHowever, as discussed in lines 234-243, an excessively small $b$ can increase the initial distance $Z_{\\mathcal{B}}$. This is because $Z_{\\mathcal{B}} = O(((1 - c^{n/b})b)^{-1})$, which is not monotonically decreasing with respect to $b$. Consequently, setting $b$ to its minimum value, such as $b = 1$, does not necessarily yield the optimal privacy guarantee. While smaller batch sizes improve the decaying rate, they can also adversely affect the initial privacy loss, necessitating a balanced choice of $b$, let alone its effect on the utility as discussed in line 230 and demonstrated in experiment section line 362.", "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": "", "extra_scores": {}}, {"review_id": "61gpquwqUD", "reviewer": "Reviewer_MVBT", "summary": "The paper studies a practically important problem of machine unlearning and provides rigorous statistical guarantees for unlearning using the tools from the differential privacy. More specifically, it is shown that, for strongly convex losses, running Projected SGD on the new (adjacent) dataset guarantees that the removed data point will be forgotten, that is the output of \"unlearning\" algorithm will be close to the output of the Projected SGD if data point on a new dataset.", "questions": "n/a", "limitations": "The results are limited to strongly convex objectives. To make the problem not trivial, it is crucial to consider convex or PL losses.", "rating": 4, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The algorithm is simple and easy to understand. The presentation is good with nice illustrations of the concepts. All necessary background is provided. The theoretical claims look sound to the best of my knowledge, apart from some technical remarks mentioned below.", "weaknesses": "(Major)\n\nMy main concern is very conceptual. Isn't it trivial that running SGD (unlearning part) on a strongly convex loss with updated dataset will eventually converge to the same unique optimum of the new loss as if we have started training from scratch. I want to highlight that in the strongly convex case, the optimum is unique. Moreover, the initial distance to the optimum is forgotten exponentially fast for constant step-size SGD. Therefore, I cannot understand why the derived result in this paper is not trivial. In my view, as expected, the authors face a difficulty in the convex case (getting only vacuous result Corollary 3.9). \n\n(Minor)\n\n1. Why the same batches are used in the unlearning process, shouldn't batches be from the updated dataset? This is perhaphs just a notational issue. \n2. It is unclear to me what is the output of Algorithm 1.\n3. It is unclear what it means to satisfy $(\\alpha, \\varepsilon)$-RU **with $c = 1-\\eta m$** in Theorem 3.2. There is no parameter $c$ in definition 2.3. \n4. The quantity $h_{\\#}\\mu$ in Lemma F.2. is not defined. This lemma is used in Proposition F.3., which is one of the key tools in analysis. \n5. $\\mathcal Z_{\\mathcal B}$ appearing first in Theorem 3.2 is not defined in the main part. I had to go to Appendix to understand what it is. \n6. Figure 3 (c) is not informative. All lines and confidence intervals overlap. \n7. Why the method is called \"contractive noisy iteration\"? A more conventional name like Projected SGD would be more appropriate. \n8. It would be helpful to explain the role of the projection in the algorithm. Is it possible to employ it without projection? \n9. In the abstract, \"convexity assumption\" should be changed to \"strong convexity assumption\" because the guarantees in the convex case are vacuous in this paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank reviewer MVBT for their insightful comments and suggestions. We address the weaknesses and questions below.\n\n**W1: ``Is the unlearning privacy bound for strongly convex settings trivial? Are our results for convex settings vacuous?``**\n\n*Compare to retraining:* We agree with reviewer MVBT that under strong convexity, the optimum is unique and SGD can approach that optimum exponentially fast. However, as we have discussed theoretically in lines 234-243 and demonstrated in experiments, our unlearning strategy does offer computational benefits compared to retraining when the initialization is not very close to the optimal solution. In Figure 3(a), we have shown that even unlearning with ***one*** epoch is sufficient to achieve good accuracy (utility) and a strong privacy guarantee ($\\epsilon \\approx 1$). In contrast, for a mini-batch size $b=128$, we need $20$ epochs to ensure the result converges reasonably well.\n\n*Convex only:* There seems to be a misunderstanding regarding our convex result in Corollary 3.9. The bound is ***not*** vacuous when the training epoch $T$ is not too large so that $\\frac{2\\eta MT}{b} < 2R$. This condition can be met if the model learns reasonably well with moderate $T$ and the projection diameter $2R$ is not set to be extremely small. For example, with $2R = 10$, $b = 128$, $\\eta = 1$, and $M = 1$, we can train for at most $639$ ***epochs*** while still holding $\\frac{2\\eta MT}{b} < 2R$. A smaller step size $\\eta$ would allow for even more epochs. Under this scenario, our approach still provides computational benefits compared to retraining from scratch when the initialization is not close to ***every*** (each corresponding to an adjacent dataset) optimum solution (set). We will clarify this further in our revision.\n\n*Compare to noiseless fine-tuning:* Instead of retraining from scratch to ensure exact unlearning, another potential approach would be running ***noiseless*** SGD and then applying output perturbation (i.e., publishing weights with additive noise) to mitigate privacy leakage, as done in prior work [9]. Note that such methods also require strong convexity for their privacy guarantees. However, there are several downsides to this strategy compared to unlearning with PNSGD (i.e., adding noise at every iteration, our approach). These include an inferior privacy-utility-complexity trade-off, as demonstrated by our experiments, and the issue of non-private hidden states discussed in Appendix N.\n\n**Q1: ``Question about mini-batch``**\n\nNote that the mini-batches only contain indices, and the underlying dataset is different with adjacent datasets $\\mathcal{D},\\mathcal{D}^\\prime$. Since we denote the replacement notion of dataset adjacency, the size of all considered datasets is always $n$ so that the mini-batch sequences can be the same. The main reason to keep it the same is for the analysis purpose, see also our response to DXXZ, Q1. \n\n**Q2: ``The output of Algorithm 1``**\n\nWe apologize for the confusion. The output is the last iterates of learning and unlearning processes, which are $x^0_T, y^0_K$ respectively. We will make it clear in our revision.\n\n**Q3: ``Meaning of Theorem 3.2``**\n\nWe apologize for the confusion. Theorem 3.2 indicates that the value $c$ is determined by the step size $\\eta$ and the strong convexity parameter $\\mu$, and it is used solely to determine the bound of $\\varepsilon$. This has no bearing on the definition of $(\\alpha,\\varepsilon)$-RU. We will clarify this point in our revised manuscript to avoid any ambiguity.\n\n**Q4: $h_{\\sharp} \\mu$`` is undefined.``**\n\nWe apologize for this oversight. For a function $h$ and a distribution $\\mu$, $h_{\\sharp} \\mu$ denotes the pushforward operation. Essentially, it represents the distribution of $h(X)$, where the random variable/vector $X \\sim \\mu$. We will ensure this concept is properly defined and explained in the revision.\n\n**Q5: ``Question about ``$Z_{\\mathcal{B}}$**\n\nWe apologize for the confusion. The meaning of $Z_{\\mathcal{B}}$ is explained in line 59, Figure 1, and its caption; it represents the upper bound of the $W_\\infty$ distance between two adjacent learning processes. In Theorem 3.2, we provide an explicit formulation of $Z_{\\mathcal{B}}$. We will ensure the meaning of $Z_{\\mathcal{B}}$ is clear throughout our revised manuscript.\n\n**Q6: ``Why the name 'contractive noisy iteration'?``**\n\nWe followed the terminology used in prior work [15, 16, 20], where the authors introduced the key technical tool (Lemma 2.6) that we employ in our analysis. To give due credit to their contribution, we decided to retain the same name.\n\n**Q7: ``The role of projection and is it necessary?``**\n\nWe leverage the projection operation in multiple aspects of our analysis. Firstly, it is used to prove Theorem 3.1, which shows that the limiting distribution of the PNSGD learning process exists, is unique, and stationary. Secondly, we use it to bound the $W_\\infty$ distance between the initial distribution and the target stationary distribution $\\nu_{\\mathcal{D}|\\mathcal{B}}$. This bounding is crucial when applying our results without assuming that the learning process has attained its stationary distribution. This is precisely the aim of Theorem 3.2. If such an assumption is made, we can simplify the bound in Theorem 3.2, leading to Corollary 3.7. Note that the $Z_{\\mathcal{B}}$ bound in Corollary 3.7 can always use the former term as an upper bound, rendering everything independent of $2R$, the projection diameter.\n\nIn summary, if we directly assume the existence of the stationary distribution of the PNSGD learning process and that it is attained after learning, the projection operation can be omitted. However, in the general case, the projection is essential for the rigor and completeness of our analysis.", "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": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The paper considers the problem of machine unlearning and proposes to use a projected noisy stochastic gradient descent algorithm (PNSGD). This algorithm is shown to achieve unlearning for convex and strongly convex functions. While the results are mainly theoretical in nature, the authors complement their theoretical results with a small set of proof of concept experiments. The topic is interesting and relevant, however reviewers raise a few concerns. These concerns include the strong convexity assumption and authors rebut that many prior theoretical papers do make this assumption. Another big concern is the lack of utility bound. The authors argue that the utility bounds can largely be derived from the work of Chourasia et al. (2021), a point I concur with.

I strongly encourage authors to address reviewer comments in the final version of the paper. In particular, kindly add the utility bound and compare it with some of the prior works with the same set of assumptions e.g., Sekhari et al., 2021.
Decision: Accept (poster)