Langevin Unlearning: A New Perspective of Noisy Gradient Descent for Machine Unlearning
Authors: Eli Chien
Haoyu Peter Wang
Ziang Chen
Pan Li
Venue: NeurIPS 2024 spotlight (2024)
Keywords: Machine unlearning
privacy
Langevin Monte Carlo
Langevin dynamic
gradient descent
differential privacy
Primary area: privacy
TL;DR: We propose Langevin unlearning which not only connect DP with unlearning, but also provides unlearning privacy guarantees for PNGD with Langevin dynamic analysis.

Abstract: Machine unlearning has raised significant interest with the adoption of laws ensuring the ``right to be forgotten''. Researchers have provided a probabilistic notion of approximate unlearning under a similar definition of Differential Privacy (DP), where privacy is defined as statistical indistinguishability to retraining from scratch. We propose Langevin unlearning, an unlearning framework based on noisy gradient descent with privacy guarantees for approximate unlearning problems. Langevin unlearning unifies the DP learning process and the privacy-certified unlearning process with many algorithmic benefits. These include approximate certified unlearning for non-convex problems, complexity saving compared to retraining, sequential and batch unlearning for multiple unlearning requests.

Langevin Unlearning: A New Perspective of Noisy
Gradient Descent for Machine Unlearning
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 zianggmtt.. langmmit.edu edu
Georgia, U.S.A.
haoyu. haoyu. wangogatchh. edu
Pan Li
Department of Electrical and Computer Engineering Georgia Institute of Technology Georgia, U.S.A. panli@gatech. edu
Abstract
Machine unlearning has raised significant interest with the adoption of laws ensur- ing the "right be forgotten". Researchers have provided probabilistic notion of approximate unlearning under a similar definition of Differential Privacy (DP), where privacy defined as statistical indistinguishabiiiy to retraining from scratch. We propose Langevin unlearning, unlearning framework based noisy gradient descent with privacy guarantees for approximate unlearning problems. Langevin unlearning unifies the DP learning process and the privacy-certifet unlearning process with many algorithmic benefits. These include approximate certified unlcarning for non-convex problems, complexity saving compared retraining. sequential and batch unlearning for multiple unlcarning requests.
Introduction
With recent demands for increased data privacy, owners of these machine learning models respon- sible for fulfilling data removal requests from users. Certain laws are already in place guaranteeing the users' "Right be Forgotten", including the European Union's General Data Protection Regula- tion (GDPR), the California Consumer Privacy Act (CCPA), and the Canadian Consumer Privacy Protection Act (CPPA) M.. Merely removing user data from the training data set insufficient, as machine learning models are known to memorize training data information (2). It is critical to also remove the information of user data subject to removal requests from the machine learning models. This consideration gave rise to an important research direction, referred to as machine unlearning (3].
Naively, may retrain the model from scratch after every data removal request ensure "perfect" privacy guarantee. However, it is prohibitively expensive practice when accommodating frequent removal requests. To avoid complete retraining, various machine unlearning methods have been
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

=
-/// + v2no'W
Unlemtng
4
(a, (G.2))-RDP
PR
x
stationary y/2
(ir, c
Bg
f +
/2
V/'
k-x
stronge privacy for learning
Learning process M
Unlearning process II Privacy recuperation: k /", better privacy.
Privacy erosion: / worse privacy.
Figure 1:
The geometric interpretation of relations between learning and unlearning. (Left) RDP guarantee of the learning process induces a regular polyhedron. Smaller Sp implies an "easier" unlearning problem. (Right) Learning and unlearning processes on adjacent datasets. It illustrates main idea and results. More learning iteration gives worse privacy (privacy erosion [12) while more unlearning iteration gives better privacy, which we termed this phenomenon privacy recuperation.
proposed, including exact 6 as well approximate approaches ( Exact approaches ensure that the unlearned model would be identical to the retraining one distribution. Approximate approaches, on the other hand, allow for slight misalignment between the unlearned model and the retraining one distribution under a similar definition to Differential Privacy (DP) [1].
1.1 Our Contributions
Learning with noisy gradient methods, such as DP-SGD (13), is widely adopted for privatizing machine learning models with DP guarantee. Intuitively, learning process with stronger DP guarantee implies an "easier" unlearning problem as depicted in Figure However, it is unclear if fine-tuning with it on the updated dataset subject to the unlearning request provides an approximate unlearning guarantee, how the DP learning guarantee affects unlearning, and computational benefit compared to retraining. In this work, we provide an affirmative answer for the empirical risk minimization problems with smooth objectives. We propose Langevin unlearning, an approximate unlearning framework based on projected noisy gradient descent (PNGD). Our core idea can be interpreted via novel unified geometric view of the learning and unlearning processes in Figure [ which naturally bridges DP and unlearning. Given sufficient learning iterations via the learning process M, we first show that PNGD converges to unique stationary distribution VD for any dataset D (Theorem 3.1). Comparing I'D with the stationary distribution P'r for any of its adjacent dataset D'. the learning process shows Rényi DP with privacy los: Given particular unlearning request D D', the unlearning process 14 can be interpreted as moving from V/D to Vpr from cloclose to E-close. In practice, due the unlearning process, the unlearning privacy loss smaller than Eo. while on the other hand, a stronger initial RDP guarantee, i.e., smaller Eo, allows for less unlearning iterations achieve the desired s. Besides the above DP-unlearning bridge, this framework also brings many benefits including (1) a capability of dealing with non-convex problems in theory, which to the best of our knowledge, can tackle, (2) better privacy-utility trade-off in practice compared to state-of-thh-aar approximate unlearning approach (8) in strongly convex settings, (3) provably computational benefit compared with model retraining, and (4) a friendly extension to sequential and batch settings with multiple unlearning requests.
be set much
previous approximate unlearning framework
We prove the intuition in Fig. formally in Theorem 3.2 We show that K unlearning iterations
lead to an exponentially fast privacy loss decay < exp( > K-1 Ry)sa. where is the order of
Rényi divergence and R2 is the strict privacy improving rate depends on the problem settings with an iteration independent strictly positive lower bound R > 0. Our result is based on convergence analysis of Langevin dynamics [15]. The sampling essence of PNGD allows for a provable unlearning guarantee for non non-convex problems [7] Our characterization of Eu allows an extension of the recent results that PNGD learning satisfies Rényi DP for convex problems [2
19
non-convex
We refer privacy loss as two-sided Rényi divergence of two distributions, which defined as Rényi difference in Detinition (.22 Note that it standard to define privacy loss for unlearning as the two-sided Rényi divergence between the weight distribution of the unlearned model and the retrained model. Such a definition directly relates the power of the strongest possible adversary for distinguishing these cases [14]

---

problems as summarized in Theorem 3.3
Our key technique is to carefully track the constant of log-Sobolev inequality [20] (LSI) along the learning and unlearning processes and leverage the boundedness property of the projection step via results of (11.
Regarding the computational benefit compared to model retraining, we show iteration complexity saving by comparing two Rényi differences, the one between initialization Pi and PDr, which is at least (2) in the worst case versus the other one between the learning convergent distribution VD and PDr, i.e., Eo which is shown to be O(1/n²) for a dataset of size n. Such a gap demonstrates that Langevin unlearning is more efficient than retraining, especially for the dataset with large n.
For sequential unlearning with multiple unlearning requests, we composite the privacy loss bound for single-step requests via the weak triangle inequality of Rényi divergence (22], which yields sequential unlearning procedure that achieves privacy loss e for each request (Corollary 3.4). For
batch unlearning, En changed to incorporate the batch size (Theorem 3.3
Beyond theoretical contributions, we also conduct empirical evaluation. Despite the provable order- wise improvement in n compared to re-training, our current theory has limitation by relying on some constants that are undetermined or can be only loosely determined in the non-convex setting. Therefore, we focus on logistic regression tasks for empirical evaluation. Compared with the state-of- the-art gradient-basee certified approximate unlearning solution (8) that requires strong convexity, we achieve superior privacy-utille
trade-off. Although success in the convex case may not directly imply success in non-convex settings, we leave tightening these constants as a future study. For this, we discuss potential alleviation and future direction in Appendix A and 5 respectively.
1.2 Related Works
Unlearning with privacy guarantees. Prior approximate unlearming works require (strong) convexity of the objective function [1778]. Their analysis is based on the sensitivity analysis of the optimal parameter. Since the optimal parameter is not even unique in the non-convex setting, it is unclear how their analysis can be generalized beyond convexity. In contrast, we show that the law of our PNGD learning process admits unique stationary distribution even for non-convex cooblems.Authon of leverage a second-orde -odder update which requires computing Hessian inverse and thus is not scalable for high-dimensional problems. While they only require one unlearning iteration, we show in our experiment that one PNGD unlearning iteration is sufficient for strongly convex loss to achieve satisfied privacy with comparable utility retraining as well. Neel al. [8] leverage PGD for learning and unlearning, and achieve the privacy guarantee via publishing the final parameters with additive Gaussian noise. We show in our experiment that our Langevin unlcarning strategy provides a better privacy-utiligy silcy--ulitt-ccopleiiyyy tradc-off compared to this approach. Ullah et al. (5) focus on exact unlearning by leveraging variants of noisy GS) Their analysis based on total variation stability which is different from our analysis based on Rényi divergence. Also, their analysis does not directly generalize to approximate unlearning. Several works focus on extending the unlearning problems for adaptive unlearning requests [ 23). While we focus on the non-adaptive setting, it is possible to show that Langevin unlearning is also capable of adaptive unlearning requests as we do not keep any non-private internal state. We left rigorous discussion on this as future work. Chourasia et al. (23) also leverage Langevin dynamic analysis in their work. However, their unlearning definition is different from the standard literature as F
Differential privacy of noisy gradient methods. A pioneer work 24 studied the DP properties of Langevin Monte Carlo methods. Yet, they do not propose using noisy GD for general machine learning problems. A recent line of work [12 25 shows that projected noisy (S)GD training exhibits DP guarantees based on the analysis of Langevin dynamics [15 26 under the strong convexity assumption. In the meanwhile, Altschuler et al. [19] also provided the DP guarantees for projected noisy SGD training but with analysis based on Privacy Amplification by Iteration (27) under the convexity assumption. None of these works study how PNGD can be leveraged for machine unlearning or DP guarantees for non-convex problems.
Sampling literature. Non-asymptotic convergence analysis for Langevin Monte Carlo has a long history [2829]
29 The seminal works [15] 24 proved -on-asympootic convergence analysis in Rényi
'Their unlearning privacy definition does not compare with retraining and they only discuss one-side Rényi divergence. As a result, their unlearning guarantee is less compatible with DP and cannot control both type I and II errors simultaneously against the best possible adversary (14]
3

---

divergence under strong convexity. Many works improve upon them by either working with weaker isoperimetric inequalities or different notions of convergence (30 See (26) for a more thorough review along this direction. While these works mainly focus on convergence to the unbiased limit (i.e., the limiting distribution for an infinitesimal step size), we have biased limits (i.e., the limiting distribution for a constant step size, such as our I'D) in machine unlearning problems. Recently Altschuler et al. [32] initiated the question of studying the properties and convergence to the biased limit. Our work provides new important application, machine unlearning, for these astonishing theoretical results in the sampling literature.
The rest of the paper is organized as follows. In Section 2 we provide preliminaries and problem setup. The theoretical results of Langevin unlearning are in Section We conclude with experiments in Section 4 Due to the space limit, all proofs and future directions are deferred to Appendices.
2 Preliminaries and Problem Setup
We consider the empirical risk minimization (ERM) problem. Let D [d:)²= be training dataset with n data points d, taken from the universe X. Let fo(x) 1 function. We aim to minimize with learnable parameter x E CR. where CR = {a Rd ||>||| S R} closed ball of radius R. We denote II, Rd + Cn to be an orthogonal projection to Cn- The norm || is standard Euclidean l2 norm if not specified. P(C)) is denoted as the set of all probability measures over a closed convex set C. Standard definitions such as convexity can be found in Appendix [ Finally, we use ~ V to denote that random variable follows the probability distribution v. To control the convergence behavior (P)NGD, it is standard to check an isoperimetric condition known as Sobolevee inequality (20), described as follows.
n -i= f(z; d,) be the objective
Definition 2.1 (Log-Sobolev Inequality (Sts)-LSI)). A probability measure v E P(RRd) is said to
satisfy Logarithmic Sobolev Inequality with constant CLSI if
v p E P(RR), (olle) S
CLSI 2
CLStEa<D
Exep
V log p(z)
(xx)
where (p(plv) is the Kullback-Leibler divergence.
2.1 Privacy Definition for Learning and Unlearning
We say two datasets D = [d. and D' [d are adjacent if they "differ" only in one index in E [n]] so that d, = d' for all * in unless otherwise specified. Furthermore, we say two datasets D and 'D' are adjacent with group size of 5 2 if they differ in at most S indices. We next introduce a useful idea termed Rényi difference.
Definition 2.2 (Rényi difference). Let 1. For a pair of probability measures u, with the same support, the a Rényi difference da v') is defined as (v, max (Da(lll'),Dad (v(vll)) where (rile') is the a Rényi divergence Da (vllp") defined
pla) [(xx)
(a(ll//) a
log
B
We are ready to introduce the formal definition of differential privacy and unlearning.
Definition 2.3 (Rényi Differential Privacy (RDP) (22). Let a > 1. A randomized algorithm
M : X + Rd satisfies R)DD if for any adjacent dataset pair D,D' E X²,, the Rényi difference (2, I E, where MDD ~ v and M(D') ~/.
It is known to the literature that (a, RDP guarantee can be converted to the popular (c, 8)-DP guarantee [T] relatively tight [22]. As a result, we will focus on establishing results with respect to Rényi difference (and equivalently Rényi divergence). Next, we introduce our formal privacy definition of unlearning.
Definition 2.4 (Rényi Unlearning (RU)). Consider a randomized learning algorithm M : : + Bd and a randomized unlearning algorithm V Rd x X x X + Rd. We say (M,U) achieves Ru if for any a >> and any adjacent datasets DD D', the a Rényi difference da (,, v') S E, where (MM()), D, D') ~ p and M(D') ~.

---

Notably, our Definition 2.4 can be converted to the standard (c, Junlearrnn definition [1 7
similar to RDP-DP conversion [22]. Since we work with the replacement definition of dataset adjacency, to "erase" data point d, we can simply replace it with any data point d' E X for the updated dataset 'D' in practice.
3 Langevin Unlearning: Main Results
We propose to leverage projected noisy gradient descent for our learning and unlearning algorithm M and U. For M, we propose to optimize the objective fz(z) with PNGD:
1t+1 IIca x2 -VV + V2no2W.).
(1)
where W. uid (O Ia) and 17, o² are hyperparameters of step size and noise variance respectively, The initialization Zo can be chosen arbitrarily in CR unless specified. We assume the learning procedure will train the model until convergence i MM(D) for simplicity, where we prove in Theorem 3.1 that the law of this learning process (T) indeed converges to unique stationary distribution when V is continuous. A similar "waleetrained" assumption has been also used in prior unlearning literature [17 and we will discuss the case of insufficient training later. After we obtain a learned parameter M(D), an unlearning request arrives so that the training dataset changes from D to D'. For the unlearning algorithm Ut we propose to fine-tune the model parameters on the new objective fo (y) with K iterations of the same PNGD.
y = IccR (w (D)( + 2n
where Wr id (O Ia) procedure. Throughout our work, we assume f(z; d) is M-Lipschitz and L-mooohh in x for any d E X. Nevertheless, one
La) and Yo Too, which starts from the convergent point of the learning
apply per-sample gradient clipping in (T) and (2) so that the M- Lipschitz assumption can be dropped. In this case, our learning and unlearning processes admit the popular DP-SGD [13] without mini-batching. For the rest of the paper, we denote Vt, Pk as the laws of the processes It, Uh respectively. Recall that we also denote the limiting distribution of the learning process (T) as uD for training dataset D.
3.1 Limiting Distribution and General Idea
A key component of the Langevin unlearning is the existence, uniqueness, and stationarity of the limiting distribution uD of the training process. We start with proving that V'D exists, unique, and is a stationary distribution. Our proof is relegated to Appendix F which is based on showing the ergodicity of the process I by leveraging results in [33].
Theorem 3.1. Suppose that the closed convex set CR Rdd is bounded with CR having positive Lebesgue measure and that VDD CR + IRd is continuous. The Markov chain {ær} in ( admits unique invariant probability measure VD on the Borel o-algebra of CR. Furthermore, for any Cr. the distribution of I, conditioned on Ty converges weakly to VD as t + 00.
If M is known to be (a, RDD for a a > 1, by definition we know that for all adjacent dataset D, D', da (VD, )D') S Ep. In the space of P(CR), this RDP guarantee gives a "regular polyhedron", where vertices are LD, UD' and all adjacent vertices are of "lengths" en at most Rényi difference. We caveat that Rényi difference is not metric but the idea of the regular polyhedron is useful conceptually. As a result, the RDP guarantee of the learning process controls the "distance" between distribution induced from adjacent dataset D and D'. Once we finish the learning process, receive an unlearning request so that our dataset changes from D to an adjacent dataset D', We need to move from V'D to Pay at least close for a (a, E)-U guarantee. Intuitively, if the initial RDP guarantee is stronger (i.e., Eu is smaller), unlearning becomes "easier" at the cost of larger noise. When Eg = E. automatically achieve (). without any unlearning update. One of our main contributions is to characterize how many PNGD unlearning iteration is needed to reduce d, (Pr. VDy) from En to E, where Po VD.
For the unlearning process, note that the initial Rényi difference between Po, ''D is provided by the RDP guarantees of the learning process. As a result, are left to characterize the convergence of
5

---

the process y& to its stationary distribution Ppy in Rényi difference (Theorem 3.2 Since the privacy loss E gradually decays with respect to unlearning iterations, we refer this phenomenon as privacy recuperation. This is in contrast to the learning process, where prior work [12) has shown the worse privacy loss Eg with respect to learning iterations and refers to that phenomenon as privacy erosion.
3.2 Unlearning Guarantees
Our first Theorem shows that (M,4) achieves (a, e)-RU, where E decays monotonically in K unlearning iterations starting from Eo, condition M being (a, -DDP. We provide the proof sketch in Appendix G.I]and and formal proofs are deferred to Appendix G.2
Theorem 3.2 (RU guarantee of PNGD unlearning). Assume for all DD E X",, fD is L-smooth, M-Lipschitz and PD satisfies Cisr-LSI. Let the learning process follow the PNGD update ① Given M is (ar, (RD and yoo Ixx. MMD), for a 1, the output of the Kth unlearning ileration
K- Rx) Eo and Rs depends on along 2 (i.e., yK) achieves (a. E), where E S cxp (-3 2k=
the problem settings specified as follows:
1) For general non-convex fDD we have Rs ((I+L))00) (1+01)00 ( +2 CR+1 S min((1 + n2))C2 + 2no .). Č 6(4(R nMy + 2nj0²) expl diRttdd) 2no
where
where
Co CIsI and R is the radius of the projected set Cn-
2) Suppose JD is convex. By choosing 1 S Z. we have Rs = (1obx (C2+2n0zys where
CR+1 S minnC' + 2no2 Ö).
3) Suppose So is m-strongly convex. Les a² m
o² mC ) f) Then, CIsI and choosing 1) S min(
2 CLu
Rg
Note that Rs can be interpreted the striet privacy improving rate at step k: and Ck is the LSI constant upper bound of distribution of yk. The above theorem states that fine-tuning with PNGD decrease the privacy loss d, (PK, VDD) exponentially fast with the unlearning iteration K. This is because R& is lower bounded away from 0 by constant, thanks to the iteration independent upper bound on C2. Stronger assumptions on the objective function I'D lead to better rate, which implies fewer unlearning iterations are needed to achieve the same RU guarantee. There are several remarks for our Theorem 3.2] First, note that the result is dimension-frre,, which favorable for problems with many parameters to be learned. Second, note that the M -isiisschitzness assumption can be dropped by clipping the gradient to norm M in the PNGD update (T) and (2) instead. As a result, our Theorem 3.2 applies to neural networks with smooth activation functions in theory. Finally, our result gives an upper bound on the LSII constants along the unlearning process (i.e., Ck) which may be improved with more advanced analysis. We note that the exponential dependence in R for the bound of C& can be loose. It possible to have a better constant with either more structural assumptions or working with different isoperimetric inequalities such as (weak) Poicaré inequality (31] A more detailed discussion is in Appendix 5
Initial RDP guarantees and LSI constant. Since Theorem 3.2 on M being (a, (o, and the PD satisfies LSI, the theorem below provides such results for the learning process, where the
formal proof is relegated to Appendix H
Theorem 3.3 (RDP guarantee of PNGD learning). Assume f(: d) be L-smooth and M Lipschiitz for all d E X. Also assume that the initialization of PNGD ① satisfies Co-LSI. Then the learning
process 1 (a, (9) J-DP of group size S Th iteration with
Sa M
EI[ n1²
T t-1
(S)
--
22
Cv.1
where Co.1 I min ((1 + n2 + mp2 C), ő 6(4(R + n2)² + no²) exp( MB++ Ce+1 S min (Cr, + no² C). Furthermore, ii satisfies Ct-ISI.
and
na²
When we additionally assume d(: is convex, by choosing n S Ct,1 I min (C. + no²2,)
2 the same result hold with L.

---

When we additionally assume f(;:d) is m-strongly convex, by choosing 0 < 17 S min 2 (1 40 M²
mc,), ; tt) with a constant Co > e m. we have E
mo (1 exp(-mr[T)). Furthermore, Vt
satisfies Co-LSI for all t 2 0.
Note that any initialization an Cn can be viewed sampling from M eTa) with c c- which corresponds to Co-LSI for any Co > O. By taking T' - xc. Theorem 3.3 provides the initial (a, eo)- RDP guarantee and the LSI constant needed in Theorem 3.2 Since there is an iteration indeenddenn
upper bound for Ct,1, one can show that Eo v 2em M for some 7-independent constant e E (0, 1) o'n²c
due to the finiteness of geometric series. Similar to our discussion for Theorem 3.2 the bound of C may be loose and it is possible to further improve the LSI constant analysis. The goal of our results is demonstrate that it is possible derive (finite) RDP and (arbitrarily small) RU guarantees even for general non-convex problems.
Nevertheless, for the m-strongly convex case we have e/ < 10 mo²""² for all T > 0. including T cc. It shows that indeed the current learned distribution VD is close to the retraining distribution PD' for n sufficiently large. This also leads to the computational benefit of Langevin unlearning compared to retraining from scratch, which we discuss below. On the other hand, we show by experiments in Section 4 that our results provide superior privacy-utiligy utility-complexity trade-off for the strongly convex case compared to existing approximate unlearning approaches.
The computational benefit compared to retraining. While our Theorems [.2 and 3.3 together provide the privacy guarantee of Langevin unlearning, is critical to check if our approach provides computational benefit compared to retraining from scratch as well. Let un be the (data-independent) initialization distribution of the learning process. Intuitively, starting with up instead of un (i.e., retraining) should converge faster to I/D', since (VD, PDD) S Eo is likely to be much smaller than da (vo, VDD) ). Thus, our Langevin unlearning needs less iterations than retraining for most cases, except for corner case when 1o is already close to PD. From Theorem 3.2 we know that the number of PNGD iterations we need to approach E-close in da to the target distribution Vpr is roughly (log( EI )), where ε is the Rényi difference between the initial distribution and the target distribution Vpr From Theorem we know that the initial Rényi difference of Langevin unlearning is at most En (1/n²) for any datasets D, D' and any smooth Lipchitz loss. In contrast, both the target distribution UD' and the initialization of retraining "n are Gaussian distributions with the same variance but mean difference ((1), their Rényi difference is 22(1) (22). As result, computational saving offered by Langevin unlearning is significant for sufficiently large n. A more thorough discussion is in Appendix B
3.3 Empirical Aspects of Langevin Unlearning
Insufficient training. While our theorem assumes the learning process runs until con- vergence, this assumption can be relaxed by the geometric view of Langevin unlearning. Assume the learning process M(D) ~ Pr terminate with finite step T instead and we only have da (ur, MD) < (a)(a)) for all possi- ble D X". One can still apply the weak triangle inequality of Rényi divergence (22) twice to bound d,, (pk: v'r)) with dan (PE, "D') (2())). and (4(a) with additional factors (a-0.5)/(a-D 1) and (25))/2((2a 1). In practice, it is reasonable to require the model parameters to be sufficiently trained so that ey is negligible and a tighter weak triangle inequality can be employed.
[b]
xCy
MFD
Figure Illustration of (a) sequential unlearning and (b) batch unlearning. For sequential unlearn- ing, we can leverage the weak triangle inequality of Rényi divergence to connect all the error terms. For batch unlcarning, only the initial RDP guarantee changes with general group size. Notably, unlearn- ing more samples at once implies Eo being larger (Theorem 3.3), and thus need more unlearning iteration to recuperate the privacy loss to a desired E.
Sequential and batch unlearning. Langevin unlearning naturally supports sequential and batch unlearning for unlearning multiple data points thanks to our geometric view of the unlearning problem, see Figure 2 for pictorial example. For sequential unlearning, we show that fine-tuning the current model parameters on the updated datasets for sequential 2 unlearning requests can achieve E)-U simultancously. The formal proof is deferred to Appendix [
7

---

04
20000
89
1999
00
unlaerning iteratiin
Accura
Larger LI Lraedg
1000
1011
08
-66
Accuracy
07
Unerry
88
04
Accumulated.um
16"
Accuracy
09
04
83
02
gusit
01
Number of unleamed data
Noise standard deviation
(a) Unlearning one point
(b) Unlearning 100 points
(c) Langevin unlearning tradeoff
Figure 3: Main experiments, where the top and bottom rows are for MNIST and CIFARIO 10 respectively, (a) Compare D2D for unlearning one point using limited unlearning iteration. This demonstrates the privacy-utiiity (e-accuracy) tradeoff under the fixed unlearning complexity (K). For Langevin unlearning. we use only K unlearning iterations. For D2D, we allow it not only to use K 2, unlcarning iterations but also to keep the non non- private internal state information. (b) Compare to D2D for unlearning 100 points, where all methods achieve (c, 1 (nn)/n/)uaaan -uneeannn guarantee with For Langevin unlearning, we vary different unlearning batch sizes S and combine them with the sequential unlearning result. For D2D, we do not allow information in this experiment that there is an inherent lower bound the unlearning iterations per unlearning request. (c) A detailed investigation of the utility compleyyo trade-off of Langevin unlearning with unlearning S 100 points at once under the fixed privacy constraint = 1. For each a, we report the corresponding 6g (black dash line) for the initial (eo, 1/n)-DP guarantee and utility after unlearning
keep the non-private internal state
Corollary 3.4 (Sequential unlearning). Assume the unlearning requests arrive sequentially such (s) that our dataset changes from Dn - Di ....- Ds, where D., Dz41 are adjacent. Let ys be the unlearned parameters for the 5th unlearning request with i. unlearning update following (2) on D and yo (a+1) Vk. ~ VDD, where (2) Io and Kg is the unlearning steps for the thh unlearning request. Suppose have achieved (a, (a))) for the 8th unlearning request, the learning process (I) is (ax, so(a)) and DD, satisfies Cısr-LSI, we achieve (ax, c(,,(())) RRU for the (s + 1)th unlearning request as well, where
K Ket1-1
a- 1/2 (so(2a) + e e())(22))
(a)+ exp(-
Σ
R&)
a-
(00) = Va and Rs are defined in Theorem
3.2
As result, leverage Corollary 3.4 to recursively determine needed unlearning iterations for each sequential unlearning request. For the batch unlearning setting, it only affects the initial Rényi difference in Theorem 3.2] We simply adopt Theorem 3.3 with group size of S 2 1 for the (S)
RDP guarantees the learning process $
Utility seitty--rrvvcc-fffiinnne trade-off. An interesting aspect of the Langevin unlearning is its strong connection to the initial RDP guarantee. From Theorem 3.3 we know that increasing a leads to smaller Rényi difference and thus better unlearning efficiency. However, this intuitively is at the cost of the utility of L'D see for example the discussion Section of [12) under the strong convexity assumption. To achieve the same (a, R)-RU guarantee, one can either ensure smaller at the cost of worst utility or run more unlearning iterations at the cost of unlearning efficiency. We investigate how utility trade-off with privacy and unlearning complexity empirically in Section 4

---

4 Experiments
Benchmark datasets. We consider logistic regression with &g regularization. We focus on this strongly convex setting since the non-convex unlearning bound in Theorem 3.2jentln is not tight enough to be applied in practice due to its exponential dependence on various hyperparameters. However, we
emphasize its significant theoretical implication due to the lack of certified non-convex approximate
unlearning framework in previous studies. Mcanwhile, the existing baseline approach [8] also only applies to strongly convex problems. We conduct experiments on MNIST (34) and CIFAR10 10 (35). which contain 1 11.982 and 50,000 training instances respectively. We follow the setting of [7] to distinguish digits 3 and 8 for MNIST so that the problem is binary classification. For the CIFARIO
dataset, we use all classes and leverage the last layer of the public ResNet18 (36) embedding as the data features, which follows the public feature extractor setting of (7). Experiments on additional datasets (37] are deferred to Appendix M and our code is publicly available
Baseline methods. Our baseline methods include Delete-to-Descent (D2D) (8), the state-of-the-ard gradient-based approximate unlearning method, and retraining from scratch using PNGD. For D2D, we leverage Theorem 9 and 28 in [8] for privacy accounting depending on whether we allow D2D to have an internal non con-private state. Note that allowing an internal non non-private state provides a weaker notion of privacy guarantee [8] and our Langevin unlearning by default does not require it. We include those theorems for D2D and a detailed explanation of its possible non- non-privacy internal state in Appendix N for completeness. All experimental details can be found in Appendix M including how to convert [a, e)-RU to the standard (c, unnleannng guarantee. Throughout this section, we choose 5 = 1/n for each dataset and require all tested unlearning approaches to achieve (c, -unllearnig with different e. We report test accuracy for all experiments as the utility metric. For the initialization, we sample from Gaussian distribution with mean 1000. This simulates the case that the initial distribution is in a reasonable distance away from the convergent distribution vp. We set the learning iteration T 10, 000 ensure all approaches converge. For Langevin unlearning, we leverage Theorems 3.2 3.3 and Corollay [.4]for privacy accounting under different settings. All results are averaged over 100 independent trials with standard deviation reported as shades in all figures.
Unlearning one data point with K = iteration. We first consider the setting of unlearning one data point using only K = 1 unlearning iteration for both Langevin unlearning and D2D (Figure Baj. Since D2D cannot achieve privacy guarantee with only 1 unlearning iteration without a non-private internal state, we allow D2D have it in this experiment. Even in this case, our Langevin unlearning significantly outperforms D2D in utility for e from 0.1 to 5 under the same unlearning complexity (K = 1), but also achieves similar accuracy to retraining from scratch. Since retraining requires T = 10, 000 PNGD iterations, Langevin unlearning is indeed much more efficient. We also show that D2D can achieve better utility at the cost of a larger unlearning iteration K 2, 5. Our Langevin unlearning exhibits both smaller unlearning complexity and better utility compared to D2D.
Unlearning multiple data points. We now consider the sce- nario of unlearning 100 data points, where the results are in Figure 3b We let all methods achieve the same (1, 1/n)- unlearning guarantee for a fair comparison. Since D2D only supports sequential unlearning, we directly apply its sequential unlearning results [8). Also, we do not allow D2D to have an in- ternal non-private state in this experiment for a fair comparison. On the other hand, since Langevin unlearning supports both sequential and batch unlearning, we vary the number of points per unlcarning request S = 5, 10, 20 and report the accumu- lated unlearning iterations for a 0.03. All methods achieve similar utility. with an accuracy of roughly 0.9 and 0.98 for MNIST and CIFARIO respectively. Langevine unlearning can achieve significantly better unlearning complexity compared to D2D if one allows for larger unlearning batch size. For instance, when we are allowed to unlearn S = 20 points at once, Langevine unlearning saves 40% unlearning iteration compared to D2D. Nevertheless, we note that due to the use of weak triangle inequality of Rényi divergence in our analysis, Langevin unlcarning can be more
1, a.ch0 .69
3000
S 50, ace
100 ascm0.899
2000
1000
0
Figure 4: Trade-off between privacy (e), unlcarning complexity (K), and the number of points be unlearned (S) in the batch unlearning setting for MNIST. We fix a 0.03 so that K can be determined given S).

---

expensive in complexity compared to D2D when one only allows for unlearning a small batch of points (i.e, S 5). We leave the improvement in this direction as the future work.
trade-off. We further examine the inherent trade-off provided by our Langevin unlearning with two experiments. In the first experiment, aim to achieve (e, Junlearinn guarantee with = 1 for batch unlcarning of 100 points. We vary the choice of a from 0.01 to 1.0. A smaller o leads unlearning iteration K to recuperate it to = 1. It is interesting to see that even if we choose a small so that the initial (cu, 1/n)-DP guarantee is extremely weak (i.e, cy R 100 for = 0.05), our unlearning iteration can recuperate 6o to c = 1.0 efficiently. On the other hand, a larger o leads to worse utility which is the inherent privacy-utility citt--uttiitt--plliiittt trade-off of Langevin unlearning. The results are illustrated in Figure Compared to retraining until convergence (T 10, 000), we achieve a similar utility but with much lower unlearning complexity with K roughly up to 2500.
worse initial eo and thus requires more
In the second experiment, we investigate the effect of the number of points to be unlearned S in the batch unlearning setting. In Figure 4 we can see that both larger S and smaller will require more unlearning iterations K. It is worth noting that the resulting utility does not change significantly, whereas Langevin unlearning always archives similar utility compared to retraining (see Figure Sa in Appendix M). Retraining requires T = 10, 000 PNGD iterations which is significantly larger than the required unlearning iteration K even for e 0.5. We have shown that Langevin unlearning is a promising unlearning solution.
5 Conclusions and Future Directions
We propose Langevin unlearning based on noisy gradient descent with privacy guarantees for approximate unlearning problems. It unifies the DP learning process and the privacy-certffied unlearning process with many algorithmic benefits such as applicability non-convex problems and multiple unlearning requests. Below we discuss several future directions for Langevin unlearning.
Extension to projected noisy stochastic gradient descent. It is straightforward to extend analysis to the projected noisy SGD case. There are two possibilities for the SGD setting: 1) randomly partition the indices [n] into sequence of mini batiheb then fix this sequence for all the
learning and unlearning process [8]; 2) randomly draw mini-batch for each update [19 25 The
analysis of [18 can be combined with our LSI constant analysis for RU guarantees, similar the proof of our Theorem 3.2 Unfortunately, the analysis
(25) may lead to an extra large LSI constant in the intermediate step even if R is small. We refer interested readers to Appendix C of [88 for a detailed discussion. The technical difficulty here is to provide tight analysis of the LSI constant for mixture of distributions, where each of them corresponds to a possible choice of mini-batch. The analysis of (19] is based on privacy amplification by iteration, which does not directly generalize to the non-convex cases. In our companion work (38), we exploit it not only to establish better unlearning result but also to enable the mini- batch setting under the convexity assumption. It is currently an open problem whether matching result can be established via Langevin dynamic analysis as well.
Better convergence rate. While it is already exciting that Langevin dynamic analysis leads to formal unlearning algorithms and guarantees even for general non-convex problems in theory, the potential of this direction for a practical plug-and-play unlearning solution even more interesting. Several promising future directions can significantly improve the convergence rate and the unlearning efficiency. Developing better LSI constant bound under additional structural assumptions for the non-convex problems is the most straightforward one. Another direction is to work with (weak) Poincaré inequality instead. While weaker tail assumption leads slower convergence (3T), the corresponding (weak) Poincaré constant may be more tightly tracked. Finally, while we only discuss the noisy GD which corresponds to Langevin Monte Carlo, some other advanced samplers are off-the-shelf including the Metropoliis-Hattnng filter (39) and Hamiltonian Monte Carlo [40]. We hope our work motivates further collaborations among the sampling and privacy communities and pushes the boundaries of learning and unlearning with privacy guarantees.
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] A. Sekhari, J. Acharya, G. Kamath, and A. T. Suresh, "Remember what you want to forget: Algorithms for machine unlearning." Advances in Neural Information Processing Systems, vol. 34, pp. 1075-180866 2021.
[2] N. Carlini, C. Liu, U. Erlingsson, J. Kos, and D. Song. "The secret sharer: Evaluating and testing unintended memorization in neural networks," in 28th USENIX Security Symposium (USENIX Security 19). pp. 267-284, 2019.
[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-Choo, 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 Machine Learning. pp. 34642-34661 PMLR, 2023.
[7] C. Guo, T. Goldstein, A. Hanmun, and L. Van Der Maaten, "Certified data removal from machine learning models," in International Conference on Machine Learning, pp. 3832-3842, PMLR. 2020.
[8] S. Neel, A. Roth, and S. Sharifi- Malvai--aalajjrddi,, "Descent-to-delete Gradient-bart methods for machine unlearning," in Algorithmic Learning Theory, pp. 931-962122 PMLR, 2021.
[9] V. Gupta, C. Jung, S. Neel, A. Roth, S. Sharifi-Malvajerdd and C. Waites, "Adaptive machine unlearning," Advances in Neural Information Processing Systems, vol. 34, pp. 16319-16330, 2021.
[10] E. Chien, C. Pan, and O. Milenkovic, "Efficient model updates for approximate unlearning of graph-structured data," in The Eleventh International Conference on Learning Representations, 2022.
[11] 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.
Springer, 2006.
[12] 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.
[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] P. Kairouz, S. Oh, and P. Viswanath, "The composition theorem for differential privacy," in International conference on machine learning, pp. 1376-1385, PMLR, 2015.
[15] S. Vempala and A. Wibisono, "Rapid convergence of the unadjusted langevin algorithm: Isoperimetry suffices," Advances in neural information processing systems, vol. 32, 2019.
[16] Y.-A. Ma, Y. Chen, C. Jin, Flammarion, and Jordan, "Sampling can be faster than optimization." Proceedings of the National Academy of Sciences, vol. 1 116, no. 42, pp. 20881- 20885, 2019.
[17] A. Lamperski, "Projected stochastic gradient langevin algorithms for constrained sampling and non-convex learning." in Conference on Learning Theory, pp. 2891-29377, PMLR, 2021.
[18] Ye and Shokri, "Differentially private learning needs hidden state (or much faster conver- gence)," Advances in Neural Information Processing Systems, vol. 35, pp. 703-715, 2022.
11

---

[19] J. Altschuler and K. Talwar, "Privacy of noisy stochastic gradient descent: More iterations without more privacy loss," Advances in Neural Information Processing Systems, vol. 35, pp. 3788-8800, 2022.
[20] L. Gross, "Logarithmic sobolev inequalities." American Journal of Mathematics, vol. 97, no. 4, pp. 1061-1083, 1975.
[21] H.-B. Chen, S. Chewi, and J. Weed,, "Dimension-free log-sobolev inequalities for mixture distributions," Journal of Functional Analysis, vol. 281, no. 11, p. 109236, 2021.
[22] I. Mironov, "Rényi differential privacy." in 2017 IEEE 30th computer security foundations symposium (CSF), pp. 263-275, IEEE, 2017.
[23] R. Chourasia and N. Shah, "Forget unlearning: Towards true data-deletion in machine learning," in International Conference on Machine Learning, pp. 6028-6073, PMLR, 2023.
[24] 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.
[25] Ryffel, Bach, and D. Pointcheval, "Differential privacy guarantees for stochastic gradient langevin dynamics," arXiv preprint arXiv:2201.//98) 2022.
[26] Chewi, Sinho, "Log-Concave Sampling." htttps://chewisinhh github. github.io/maing ww/imoon........... pdf
2023. Online; accessed September 29, 2023.
[27] 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.
[28] A. S. Dalalyan and A. B. Tsybakov, "Sparse regression learning by aggregation and langevin monte-carlo," Journal of Computer and System Sciences, vol. 78, no. 5, pp. 1423-1443, 2012.
[29] A. Durmus and E. Moulines, "Nonasymptotic convergence analysis for the unadjusted langevin algorithm." 2017.
[30] M. A. Erdogdu, R. Hosseinzadeh, and S. Zhang, "Convergence of langevin monte carlo in chi-squared and rényi divergence," in International Conference on Artificial Intelligence and Statistics, pp. 8151-8175, PMLR, 2022.
[31] A. Mousavi-Hosseine T. Farghly, Y. He, K. Balasubramanian, and M. A. Erdogdu, "Towards a complete analysis of langevin monte carlo: Beyond poincar' inequality," arXiv preprint arXiv:2303.0358% 2023.
[32] J. M. Altschuler and K. Talwar, "Resolving the mixing time of the langevin algorithm to its stationary distribution for log-concave sampling," arXiv preprint arXiv:2210.084M. 2022.
[33] S. P. Meyn and R. L. Tweedie, Markov chains and stochastic stability. Springer Science & Business Media, 2012.
[34] L. Deng, "The mnist database of handwritten digit images for machine learning research," JEEE Signal Processing Magazine, vol. 29, no. 6, pp. 141-142, 2012.
[35] A. Krizhevsky et al., "Learning multiple layers of features from tiny images," 2009.
[36] 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.
[37] B. Becker and R. Kohavi, "Adult." UCI Machine Learning Repository, 1996. DOI: http://bbb.rr/11024443///3
[38] E. Chien, H. Wang, Z. Chen, and P. Li, "Stochastic gradient langevin unlearning"" Advances in Neural Information Processing Systems, 2024.
[39] W. K. Hastings, "Monte carlo sampling methods using markov chains and their applications," 1970.
[40] R. M. Neal al., "Meme using hamiltonian dynamics," Handbook of markov chain monte carlo, vol. 2, no. 11, p. 2, 2011.
[41] M. Aerni, Zhang, and F. Tramèr, "Evaluations of machine learning privacy defenses are misleading." arXiv preprint arXiv:2404.13399, 2024.
12

---

[42] Q. P. Nguyen, B. K. H. Low, and P. Jaillet, "Variational bayesian unlearning." Advances in Neural Information Processing Systems, vol. 33, pp. 16025-16036, 2020.
[43] Q Nguyen, R. Oikawa, D. M. Divakaran, M. C. Chan, and B. K. H. Low, "Markov chain monte carlo-based machine unlearning: Unlearning what needs to be forgotten," in Proceedings of the 2022 ACM Asia Conference on Computer and Communications Security, pp. 351-363, 2022.
[44] A. Rawat, J. Requeima, W. Bruinsma, and R. Turner, "Challenges and pitfalls of bayesian unlearning," arXiv preprint arXhv:2207.032227, 2022.
[45] S. Fu, F. He, Y. Xu, and D. Tao, "Bayesian inference forgetting," arXiv preprint 2021.
arXiv:2101.064
[46] T. H. Gronwall, "Note the derivatives with respect a parameter of the solutions of system of differential equations." Annals of Mathematics, pp. 292-296, 1919.
[47] M. Hardt, B. Recht, and Y. Singer, "Train faster, generalize better: Stability of stochastic gradient descent," in International conference machine learning, pp. 1225-1234, PMLR, 2016.
[48]
maintainers and contributors, "Torchvision: Pytorch's computer vision library." https 77 thub. wwt.:ccccpppppppp http:/yyttrcvvviiiioo 2016.
[49] A. Paszke, S. Gross, F. Massa, A. Lerer, J. Bradbury, G. Chanan, T. Killeen, Z. Lin, N. Gimelshein, L. Antiga, Desmaison, Kopf, Yang. Vito, M. Raison, A. Tejani,
S. Chilamkurthy, B. Steiner, L. Fang, J. Bai, and S. Chintala, "Pytorch: An imperative style, high-performance deep learning library," in Advances Neural Information Processing Systems 32, pp. 8024 8035, Curran Associates, Inc., 2019.
[50] A. Paszke, S. Gross, S. Chintala, G. Chanan, E. Yang, Z. Vito, Z. Lin, A. Desmaison,
L. Antiga, and A. Lerer, "Automatic differentiation in pytorch," 2017.
[51] 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, R. Kern, M. Picus, Hoyer, M. H. van Kerkwijk, M. Brett, A. Haldane, F. del Río, M. Wiebe, P. Peterson, P. Gérard-Marchane K. Sheppard,
T. Reddy, W. Weckesser, H. Abbasi, C. Gohlke, and T. E. Oliphant, "Array programming with NumPy," 2020.
[52] 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.
13

---

A Limitations
While Langevin unlearning provides the first approximate unlearning solution for non-convex problems, it is still not practical enough as we have stated in the main text. One limitation of our unlearning guarantees (Theorem 3.2) is that the privacy bound for non-convex problems not tight and can potentially improved via advanced analysis, where some possible directions are discussed in the future directions below. Currently, it is still only applicable in practice for strongly convex problems as we have demonstrated in our experiment section if privacy guarantee is required. Nevertheless, recent studies have shown that (c. 6)-DP model provides strong empirical privacy against popular attacks such as membership inference attacks even if e = 10th (41). We conjecture similar phenomenon exists for Langevin unlearning, which allows Langevin unlearning to defend against membership inference attacks for non-convex models well in practice with a similar scale. We leave this empirical study as our important future work.
B Broader Impact
Our work study the theoretical unlearning guarantees of projected noisy gradient descent algorithm for convex problems. We believe our work foundational research and does not have direct path to any negative applications.
C Standard Definitions
Let f Rd + E be a mapping. We define smoothness, Lipschitzsness, and strong convexity as follows:
L-smooth V v. Rd, [V - V s L||> yll
(3)
m-strongly convex: V V E Rd (x y. fz(=) vf(()) ml|x v/1
(4)
M-Lipschitzs: V z. Rd ([ -
- M - y/l-
(5)
Furthermore, we say f convex means it is O-strongly convex.
D Additional Related Works
Bayesian Unlearning. Due the relation between Langevin Monte Carlo and Bayes learning approaches, our Langevin unlearning also loosely related to Bayesian unlearning literature. See [4 for series of empirical results. Along this line of work, 45) is the only one that provides a certain unlearning guarantee in terms of KL divergence. However, they only provide a bound for one direction of KL (similar to (pkl (/))) which makes it fail to be directly connected
to the differential privacy. Note that it is crucial to ensure the bidirectional bound for KL or Rényi divergence for the purpose of privacy. Otherwise, we cannot ensure the sufficiently large type and type II errors of the best possible attacker in membership inference attack (14). Also, it is essential to have (relatively) tight conversion to DP, where the general order in Rényi divergence is crucial.
E Detailed Discussion on Computational Benefit Against Retraining
In this section, we provide a more detailed discussion of the computational benefit of Langevin unlearning against retraining from scratch. We start our discussion under strongly convex assumption and then explain the non-convex case. Let us consider the case f(r; is m-strongly convex, L--
smooth and M M-Lipschitz in for all d X. Also, assume the initialization distribution Vo
2n Ta) for some ão E Cr. this case, from Theorem 3.2 N m learning iteration (I), we have
we know that running PNGD
da da VDD) S exp(- 20T aCisi
(da vD:).
(6)
Note that by Theorem 3.3 we know that CLsI
20 m
by our choice of uo for an appropriate step size
77 min(2 1 1). As result, in order to be close uDr, we need myj
log( d. (Po.Pp)) retraining
14

---

iteration. On the other hand, for Langevin unlearning need my log( = where en S 4a result, Langevin unlearning the computational saving for Langevin unlearning against retraining is
mo"n As
da (Vo, vD.)
Eo log(
da (vo, vD')
mo²n² x da dalus, vD.)
log( my
log(
log
mi E
ED
4aM²
Clearly, this saving depends on PDr. In some rare cases, might accidentally be close to Por that retraining is more efficient. However, even if vp (D'x 2 Ia), we have do ("o, PDD)
com am [m That is, even if we know the target distribution is Gaussian and 4a choose the initialization to have the same variance, the corresponding Rényi difference 2(1) for -.0 x- (D') || (()). As result, if we uniformly at random sample T. from CR. have [00 - (D') 2 1 with probability at least - Rd- Plug this into the lower bound above we obtain a data-independent lower bound on the computational savings with probability at least 1 - 7 as follows
da (vo, VD.)
a
60
m n² x do (vo, vD!)
log(
log(
log
(8)
mn
my x= (D'II
mn
4a.2
a log(
m 2 1300
m n
log
(9)
1709
16M
m
16M2
Here we can see that for larger problem size n, our computational benefit more significant.
For the non-convex case, note that the convergence rate R3 in Theorem 3.2 will vary and depend
on the LSI constant of i4 and up in general. This makes hard to have direct characterization of
the computational benefit against retraining. To simplify the situation, we assume the convergence
rate Rg is constant R > 0 that is independent of n, In this case, the computational saving can be characterized as
da (v, VTD)
log(
(10)
E0
In this case, one can still leverage Theorem 3.3 to provide an upper bound on Eg. yet the obtained bound can be weak due the inaccurate estimate of LSI constants for the non-convex case. Instead, we propose to use unbiased limits Vp to approximate the biased limit vp for a rough estimate instead,
since Da (vD (D)) - as r + 0 [26). From standard sampling literature (15), we know that DD x exp(- ( provide the following result for bounding da (DD, DD:).
Proposition E.1. Let iD exp(-fp). Assume If d) f(x; d')l $ F for all E Rd and d, d' E X. Then do (DD, uD)) s 2F for any adjacent dataset D DD' and > 1.
As result, we know that Eg is roughly at most gån when the step size 1) is sufficiently small. Thus when da (Po, VD-) R(1), we Langevin unlearning save ((log(n) PNGD iterations.
F Proof of Theorem 3.1 Convergence of PNGD
Theorem. Suppose that the closed convex set CR C Rd is bounded with Leb(CR) > 0 where Leb denotes the Lebesgue measure and that V CR - TRd continuous. The Markov chain {x²) in ① admits unique invariant probability measure VD on B(CR) that is the Borel o-algebra of Cr. Furthermore, for any x E CR. the distribution of o4 conditioned on zo = x converges weakly to vD as 3C.
In this section, prove that the learning process I with general closed convex set C' that is restated as follows for the reader's 's convenience,
1t Nc [ 1/ SD(x)) ( 22no2..)
(11)
will converge to an invariant probability measure. One observation is that a Markov chain and some ergodicity results can be applied.
15

---

Proposition F.1. Suppose that the closed convex set C C R is bounded with Leb(C) > O where Leb denotes the Lebesgue measure and that VsD : C - TRd is continuous. Then the Markov chain {x1} defined by (11) admits a unique invariant measure (up to constant multiples) on B(C) that is the Borel a-algebra of
Proof. This proposition is direct application of results from 33 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 Wi, { is Leb-ineeducible i.e. it holds for any x E and any E B(C) with Leb(A) > that
[(x, A) == P(TA +o0 =x) =>>> >
where TA = in 2 0 22 E A} is the stopping time. Therefore, there exists a Borel probability measure & such that that {ar} is e-irreducible and & is maximal in the sense Proposition 4.2.2 in [33 Consider any A E B(C) with (AA) > O. Since { is (f-ireeuucibe, one has [ A) P(TA too Zg x) 0 for all E C. This
implies that there exists 2 0, 8 O, and E B(C) with Leb(B) > 0, such that
PxT E A zo x) 2 6, x E B. Therefore, one can conclude for any that
U(x, A) = Σ
P(x. E A Ty = x)
Σ
P(I+T A 21 E B, 2) P(ae E B zo z)
8
inf Pr: B Iz-1 = v)
t=1
= 00,
where we used the fact that infyec P(x, E B 2111 = P(z) B y) 0 that is implies by Leb( B) > 0 and the boundedness of C and ff((C). Let us remark that we actually have compact V fC) since compact and fD continuous. The arguments above verify that {xa} } is recurrent (see Section 8.2.3 in 33 for definition).
2. Strong aperiodicity. Since C and V (C))) are bounded and the density of W, has uniform positive lower bound on any bounded domain, there exists non-zero multiple of the Lebesgue measure, say satisfying that
P(#1 E Zo x) 2 (A). VzEC, A B(C).
Then {xt} is strongly aperiodic by the equation above and (C) > 0 (see Section 5.4.3 in 33 for definition).
The proof is hence completed.
Theorem F.2. Under the same assumptions as in Proposition F.1 unique invariant probability measure VD on B(C). Furthermore, for any C, the distribution of x generated by conditioned on zo x converges weakly to vp as 1 co.
the Markov chain {xr} admits
Proof. It has been proved in Proposition F.1 that {a²} is strongly aperiodic and recurrent with an invariant measure. Consider any E B(C) with (AA > and use the same settings and notations as in the proof of Proposition F. There exists 7 > 0, 8 > 0, and B E B(C) with Leb(B) > 0, such that Pxxr E Fo x) 2 o, V E B. This implies that for any 2 0 and any x E
P(14T4+1 E A It x) = P( A
x) 2 P( E A æ E B,z0 x)-P(a B 2o = x) 2 6,
where
8 inf Px(1 E B y) 0,
yEC
which then leads to
Q(z, A) = P(x: A. infinitely often) +
16

---

This verifies that the chain } is Harris recurrent (see Section 9 in 33 for definition). It can be further derived that for any 2 E C,
E(TA ro x)
P(TA 2 2
= x0-
(T+1)
P(TA> (T+ x)
S (T + 1)
Σ (1 k=1
c) toc
The bound above is uniform for all E C and this implics that is a regular set of {Ø²} (see Section 11 in (33] for definition). Finally, one can apply Theorem 13.0.1 1 in [33 to conclude that there exists a unique invariant probability measure Vp on B(C) and that the distribution of xy converges weakly to uD conditioned on 2a x for any C.
G Proof of Theorem 3.2
G.1 Proof Sketch of Theorem 3.2
Given M is (a,, ( we aim to show the upper bound of da (pk; UDi) decays in l starting from Eo at k = 0. As a warm-up, we start with the strongly convex case. The analysis is inspired by [15] and [24] and formal proof can be found in Appendix G.2 Roughly speaking,
characterize how both a Rényi divergence (pu ('D)) and (~ l(pk) decay, given VD' and pa satisfy LSI condition for some constants. Standard sampling literature only focuses on the part (P=lllpD)) (i.e., Lemma 8 in [5)). where VDr satisfies LSI implies exponential decay in Rényi divergence. The other direction is necessary for meaningful privacy guarantee but more challenging
one to carefully track the LSI constant of ps for all 2 O. We prove the following lemma for such LSI constant characterization along the unlearning process, which specializes results of (26) to the PNGD update.
Lemma G.1 (LSI constant characterization). Consider the following PNGD update for a closed convex set C:
T l((ak), T2.2 = FK.1 WWk Tk+1 (c(
where h is any M-Lipschitz map Rd + Rd, We ~ (0, Ta) independent of anything before step k. and Hle is the projection onto a closed convex set C. Let [k.,1, Pk.2 and pa be the distribution of Nk.1-
I&2 and Fy respectively. Then we have the following LSI constant characterization of this process.
1) If μı satisfies c-LSI, μk.1 satisfies M cfLL- 2) If p4,1 satisfies L-LS Pk.2 satisfies (c + o2+ 3) If pk.2 satisfies c-LSI, 1941 satisfies c-LSI.
By leveraging Lemma G.I we can characterize the LSI constant for all Pk. One key step is to characterize the Lipschitz constant of the gradient update h(xx) x V/ [xx). From Lemma 2.2 in 32) we know if / is m-strongly convex, L-smooth and 1) S Z. then h is (1 -pm)--ipschitz. Let
Pk satisfy C+-LSI, Lemma G.1 leads to the recursion expression Ck+1 S - (C o² mCasi +) and the assumption a² m non-increasing and thus Ps LSI for all O. As result, the decay of both (P&llluDD)) can be shown.
Co =
CisI- By choosing 1) satisfying
v S min( 2 (1
< CisI, Ck
m
and Da (PDd llpk)
Beyond strong convexity. To extend beyond strong convexity, one may naively apply Lemma G. for convex and non-convex settings. Unfortunately, both cases lead to monotonically increasing LST constant Cg. As result, given an 6o. proving achieve an arbitrarily small is challenging even with K + 00 since the I.SI constant may be unbounded. More specifically, if f is convex and 1) S 2. then
Applying Lemma G leads to the recursions on Cg. For the convex case, we have Ck+1 S. C2 + 2np For the non-convex case, we have C++1 < (1 + =L)² + 2no².
h(()) = x n V fxr) is L-Lipschitz. If f is L-smooth only, the map is +
One of our contributions to demonstrate that C₁ has a universal upper bound which is independent of the number of iterations. Hence, the exponential decay in Rényi difference still holds. The key is to leverage the geometry of CR to establish an LSI upper bound that is independent of l using the result of (21), which has not been explored in the prior privacy literature (12 25
Lemma G.2 (Corollary in (2I). Let be a probability measure supported on for some R 2 0.
Then, for each 0, μ (0, {la) satisfy C-LSI with constant C S 6(AR2 + + exp( 1R² )R2).
17

---

[19] also leverage the geometry of CR for the DP guarantee of learning with projected noisy (S)GD, but their analysis follows privacy amplification by iteration (27] and still require convexity. Our result demonstrates the potential of Langevin dynamic analysis for unlearning guarantees of non-convex problems.
G.2
Formal Proof
We will start with the proof for the strongly convex case and then extend it for convex and non-convex cases. As indicated in our sketch of proof, there are main parts of our proof. The first is to characterize the decay in Rényi divergence between two processes yk, V under LSI conditions. The second to track the LSI constant yk y/ throughout the unlearning process. The analysis is modification of the proof of Lemma 8 in [15]
We first define some useful quantities and list all technical lemmas that need proof. For and any two probability distribution p. with the same support, define
Fa(pz) = (0) = v x) dx.
(12)
Ga(p:v) = E 1/ ) V log 1/ - -
a E. G)00/13
(13)
Note that (p(pll)) = - log Fa (p: 2/) by definition and (p: is known as the Rényi Informa- tion, where the limit technical lemmas need. The first is data-processing inequality for Rényi divergence, which is the
recovers the relative Fisher information [15]. Now we introduce all the
Lemma 2.6 in (32]. The second and third lemmas are based on results in [15]. We note again that we use the definition of LSI in [26], where the LSI constant is reciprocal to those defined in [15]
Lemma G.3 (Data-processing inequality for Rényi divergence 32 For any 2 1, any function h: _2d I& and any distribution p., with support on Ik!
Do (e(kvulllgg)) < Dalullu)
(14)
Lemma G.4 (Lemmaa 18 in [5 with customized variance). For any probability distribution po. Vo
and for any t 2 0, let Pb * N0, 2to² and v = vo * N Lto² Then all a > 0 we have
Da(p:lla)) -ao² Galprie)
(15)
dt
(p
Lemma G.5 (Low bound of G-F ratio, Lemma 15] all probability distribution p have
Suppose v satisfy CisI-ISI. Let a 2 1. For
Galpiv) Pa(p:))
2
2
2 (olplv).
(16)
a
Now are ready to prove Theorem 3.2 under strong convexity assumption.
Proof. For brevity and to make our proof succinct, we will only prove the harder direction (v l|pk). The proof of the other direction is not only simpler (due to upy being the stationary distribution), but also the same analysis applies.
First, let consider two processes:
V/++ = 11 (U (yk(k) + 22 where yo ~ Po = VDD
(17)
V641 = ITc (vá - (VD + 2 where vo ~ VD
(18)
Note that yy is the process we would have during the unlearning process and y an auxiliary process. Let Pk. Pk.2, Pv be the probability distribution of 1k, 2h. Mss respectively, where
Vk.1 = yk 7) V Uk.2 yk.1 + 2 yk- Hle (Jl..)
(19)
Similarly, let Pk... 1. p/22. P be the probability distribution of Bh.1 Vk.2 V4 respectively. By definition Ppr is the stationary distribution of this process (in fact, both), we know that p uD for all & 2 0.
18

---

Also, without loss of generality, we assume Pk: satisfies C&-LSD for some value C₁ to be determined. Notably by assumption we have C. CLSI-
Observe that the gradient update k(y) = 1/ LD (v) is 1pm))- -Lisschitz map for D being
T-smooth and m-strongly convex due to Lemma 2.2 in 32) when rj S -. By Lemma G.1 know
that Pk, satisfies ((1 7m))* Next, by Lemma G.3 we have
Da (a( = Da(h+ (1ppps))) - Da Ipx)) = Da (a(x-)llxx))
(20)
Next, consider Pk.1, = Pk.1 * (0, Ia) and Pk,11 = Pk.1 * (0, Ia) for t E [0, Clearly, Pk.1.n = Pk.2 and Plc,1.1 Pk.2- By Lemma G.4 we have
d Dr (.....llll...... -02 Ga(P(1.1PP...)) di
(21)
Fa (k.1,,)
By Lemma G.1
we know that 1k, satisfies ((1-rmm) - -2n0 -LSI for all t S 7, By the choice
17 S
2
mC we know that
m
(1 - m-mmm) 21j0² S Ck.
(22)
Clearly, this would require e < Cp for 0. Then by Lemma G.5
we have
2 a²Ch
2
Do pllllt.)))
(23)
(a(
This would imply
20²
Da (1h, s DalpkiallPaa..)
(24)
dt
aC2
By Gronwall's incquality
[46). integrating over E [0 gives
20 Da Ilppaa)
Da Da(Pkallpkzz) S exp(-
(25)
aC₁
Apply Lemma G.3 for the mapping Ie,, we have
(o S Da Da(dh2lllpa))
(26)
Note that by Lemma G.I we have also shown that Pk+1 is C&-LSI. This implies Pa is Co-LSI, where Co CLsi by assumption. Combining all results and the fact that up is the stationary distribution, we have
20
Da (VD=llpx+1) S exp(p Da aCisi
(27)
Iterating this over is complete the proof.
The proof beyond strong convexity is similar, except the characterization C₁ is different. As we mentioned in the main text, without strong convexity constant that grows monotonically with respect to the iterations. To prevent a diverging LSI constant, leverage the boundedness of the projected set Cn establish iteration-indepeneent bound for the I.SI constant. Below we give the proof of Theorem 3.2 without the strong convexity assumption.
only prove upper bound of the LSI
Proof. As before, we will only prove the decay of the direction Do (MD [px), since it is more challenging. We again assume is CL-LSI, where Co = C1.sI by our assumption. First, due to (47) know that the map h(y) = y - V fo (v) is (1 1/L--sisehhitz for for being L-smooth. By Lemma G.1 we know that Pk. satisfies ((1 + + LLSS. Next, by Lemma G.3 we have
D. Da 11px.1) S Da (xllle)) Da (D'(())))
(28)
Next, by Lemma G.4 we have
d
- (e.Pll....sPP....)
Da (o(ee.LalPP...)
(29)
dt
Fa Pa P,,1,))
19

---

Note that by Lemma G.1
P satisfies (11+nL)&3 + 2to )-LS. Then by Lemma G.5 we have
20²
Do (P...)))
a((1 +nL 2to²) Da 1a(
(30)
dt
By Gronwall's inequality
[46]. integrating over E [0, gives
["
20²
Da Da(e22llnn.) S exp((
1= ae((1 + 2 + 2to2) di) dt) Ma)Daalle (a)aale.l)l)
(31)
Note the calculation
2x²
d(2o²t)
dt
(32)
a((1 + +n) + 2to
1= a((1 + n1)00 + 2to2)
1
1
(33)
2a ((1 ((1+nb)) C2)
((1 nL) + 2no2)3
By applying Lemma G.3 for the projection operator and combining all results we have
1
((0=11))
& exp(- 2a ((1++D)3C&) ((1+ nL) + 2n02)3 )a((ollle))
(34)
Iterate this over K steps, we have
K-1
Da(vD-llex) s exp(
)D, (VD (vD
20
2a
((1+nL)CCa)
((1 + nL))Cr + 2noo13
k=U
(35)
K
=exp(-
(()))))) ((1 + nT)C 2n ). (UDrllPo).
(36)
20
2xx
k=0
To complete the proof, establish the recursion relation of Cs. If is convex and 1j S 2 then hxx) = x - Vf(x) is 1-Lipscchizz. If is L-smooth only, the map is (1 Liiss-iiithttt Applying
Lemma G.I leads the following recursions on C₁
Convex: Ca+1 S Cx + 21jo² Non-convex: CK+1 S (1 + + + 2no
(37)
On the other hand, the Corollary 1 in (21) states the following result.
Lemma G.6 (Corollary in 21) Let μ be probability measure on Rd supported on CR for some R 2 O. Then, for each μ (0, tla) satisfy C-LSI with constant
4R
C S 6(4R² 1) exp(
(38)
Now, consider the following PNGD process similar to Lemma G.I
I h((x), F2.2 Fk.1 2njo Fa+1 IIc (Ix.2),
where h(x) - fz) and Wi ~ (0, Ia) as before. Clearly, due to the projection IIc, we know that μı supported on CR. By assumption that fo M M-Lipschitz, we know that [x) < M and thus M4.1 is supported on CR+gM. By applying Lemma G.6 we know that N4,2 satisfies LSI with constant upper bounded by
4(R n2M
6(4(R 72 + 2n00) exp(
(39)
2n
Finally, by Lemma G.I we know that the projection Ic., does not increase the LSI constant so that the same LSI constant upper bound holds for all 14g- Combining with previous recursive result we complete the proof.
If we further have that /D being convex, then by Lemma 3.7 in 47 we know that when 1) S the gradient map is 1-Lipchitz. As result, the factor (1 mL) can be reduced to 1.
D
20

---

H Proof of Theorem 3.3
The proof is mainly modified from the analysis of (18) with our LSI constant analysis. First, we list the all needed notations and technical lemmas adopted from [8] Let us start with the PNGD process with training dataset D and D' as before
Ii+1 Ieen (xe fDDx)) + 2nno2W:)
(40)
1/41 Ilc (z/- -
W. W, ind (O Ia),
(41)
For each iteration, the above update is equivalent to the following two steps:
3t - //D()) + Vi J++1 = Ilcc (ne.1 + Vijo2W.)
(42)
That is, it can be decomposed into another noisy GD update followed by a small additive noise with projection. Let vt; Mt,1, 14, L/11 be the law of Zt, 1,,1, Tyg 24, respectively. Finally, we introduce the following technical lemma from (18) specialized to PNGD case.
Lemma H.1 (Simplification of Lemma 3.2 in 18 then we have
For any Et E P(Rd) that both satisfy Ct,1-
Dale N(00, no² 1a)lE N m
Do (Eills)
no² a'
)-1
a- + 1. (43)
a²
Ct,1
1 1
no
Ct,
The proof is an application of Lemma G.5 but with the integral involving time-dependent LSI constant. Now we are ready to prove our Theorem 3.3
Proof. We first provide a full characterization of the LSI constant of V1,1 for all & 2 0, assuming Vy is Co-LSI to chosen later. Let us denote the LSI constant of 24, V1,1 to be C., Ct,1 respectively.
By Lemma
G.1 when S'D is L-smooth we have that
C² S (1 + nL) no? C411 S Ct,1 + no²
(44)
Similarly, by leveraging the same analysis in the proof of Theorem 3.2 using Lemma G.6 with the assumption that fo is M-Lipschitz gives the following h independent bound
4(R + m) )
C₂ S 6(4(R nM)² + n7²) exp(
(45)
1122
4(R + n2
C.+1 S
+ 7)M) 2 21j0²) exp(
(46)
2nj0²
Now establish the iteration bound on the Rényi divergence. By composition theorem for RDP (and equivalently Rényi divergence) [22] and the assumption that fD, for are M-Lipschitz, we have
Do (vr, Da(uilb))
2n52M²
(47)
02n²
This is because the sensitivity of ||V fz(z) fz < R x (2n for group size S 2 1. More specifically, there are at most S different pairs of [ d.) - ff(;; d(), and for each pair we have [z; d., - f d < 2 by triangle inequality and M M--Lisschtznesss By triangle inequality again, we have V fz(z) f [2) < (2n y On the other hand, the variance of the added Gaussian noise in this step (from x, x4,1) is nj22. Leveraging the standard result of
-
a
Gaussian mechanism [22 gives the a-Rényi divergence 4ng 22 2a Dividing it by gives the second term
2(0²11)
Then by applying Lemma H.I we have
(a 11/41) <
Dar (v. (1
no2 Ct,1
-1 a' a
no 1. Ce.1
(48)
a'
1
21

---

Combining these two bounds we have
Da(vetalleet) 2 < 22)
(Da(vslle)) a'
no²
+
(1+
)-1 a
+ 1.
(49)
02n²
na? Ct.1
+
Now, iterate this bound for all & and note that (vovllle)) = 0 for any a > 1 due to the same initialization, have
Da(urll44)
2
T EII+ _
no?
(50)
a
22n2
t=/== Cr,1
The same analysis applies to the other direction Da(1/_111a441) convex and non-convex cases. For the m-strongly convex case, it is direct result of Theorem D.6 in [18), where the LSI constant analysis of C, is exactly the same to those of Theorem 3.2 Together
Together we complete the proof for
we complete the proof.
I Proof of Corollary 3.4
Corollary 1.1 (Sequential unlearning). Assume the unlearning requests arrive sequentially such that
our dataset changes from D Do Di ... - Dss where D., Ds41 are adjacent. Let yı be the unlearned parameters for the th unlearning request with is unlearming update following (2)
(9)
on D and yo [o+1) ИkK VD, where (2) x' and K is the unleurning steps for the th unlearning request. Suppose have achieved (a, (a)))- for the 8th unlearning request, the learning process ( is (ex, so(a)) and DD, satisfies CısI-LSI, we achieve ((x,e( RRU for the (s + 1)th unlearning request as well, where
K-p2-1
(()+))(a) exp(-=
Σ k=0
Rg) a a- 1/2
(co(2a) + (2a))
a --
(a)) = 0 Va and Rg are defined in Theorem
3.2
While our main theorems only discuss one unlearning request, we can generalize it to address multiple unlearning requests. Consider the case where our learning process is trained with dataset D. At the unlearning phase, we receive a sequence of unlearning requests so that our dataset becomes D1, D Ds. where each consecutive dataset D., D.+1 are adjacent (i.e., each unlearning request ask for unlearning one data point). Let us denote 1',, the output probability distribution (MD.) for 2 0, where set Do D. Sequential unlearning VD, + I/D, ... VDg, where for each request we will stop when we are "z" away from the target distribution in terms of Rényi difference. As a result, for some sequence of distribution (V', ) such that the a Rényi difference da (VD,, (D,) ) & See Figure 2 for pictorial example of the case S = 2. While convergence along PD, > TD.E. directly, we can leverage the weak triangle inequality of Rényi divergence provide upper bound of it.
be viewed as transferring along
actual path is VD, - DD, + DD,
unable characterize the
Proposition 1.2 (Weak Triangle Inequality Rényi divergence, Corollary 4 in (22). For any a > 1, P,q > satisfying 1/p + 1/q and distributions P, Q, R with the same support:
a 1 1 P PD (PI1Q) D/
Da R)
a
22

---

Note that by choosing difference d, as follows
= 2, we can also establish the weak triangle inequality for Rényi
S a D2a (PI1Q) + -2a-1
Da(PI
(51)
IV W 1
(P,(P, + d2a 1Q,
(52)
Q
(P,(P + d2 (Q: R) 2
(53)
(d2a(P,)) + d2 ( R))
(54)
(55)
where (a) is due to the definition of Rényi difference, (b) is due to the monotonicity of Rényi divergence in and (c) is due to the fact that for all a > e= P) and combine with the bound above, one can show that
a-1 2 1. Repeat the same analysis for
S a 2 (d2a(P,Q) d2a (Q,
da (P, R)
(56)
a
The main idea illustrated in Figure 2 (a). We first leverage Theorem 3.2 to upper bound the Rényi difference da (PD.,, PDD,) ) in terms of the Rényi difference between da ( VD,) (dash line) with decaying factor. Then by weak triangle inequality of Rényi difference we derived above, we can further bound it with e(1) (2x) (black line) and Eo (2a) (red line).
Proof. The proof is a direct combination of Theorem 3.2 and Proposition I.2 To achieve
(a, (a))- for the (s + 1)th unlearning request, we need to bound da (iD..., IDD...) Assume run K341 unlearning iteration, from Theorem 3.2 we have
Ko41-1
da
) S exp(
Σ
R& VD.41),
(57)
k=
where Rg is defined in Theorem difference, we have
3.2 On the other hand, by weak triangle inequality of Rényi
1/2 Cx -
(DD,,, VD..1)
S
(d2. VD.) + d2a (UD. VD..)))
(58)
By the initial RDP condition, know that dza (VD,, VD. co(2a). On the other hand, by the RU guarantee of the 4t unlearning request, have
d2a(iD,, s e
(59)
Together we have
d, (Dp,, DD 1 a a-112 (5o(2a) + (2)) -
(60)
Hence we complete the proof.
Proof of Lemma G.1
Lemma (LSI constant characterization), Consider the following PNGD update for a closed convex set C:
I h(xx), F6.2 = FK,1 +oWk, Tk+1 (1
where h is any M-Lipschitz map Rd + Rd, WE NN Ia) independent of anything before step k. and He is the projection onto C. Let fKK,1, 11s.1,15, 2Kk22 and μ4 be the probability distribution of 2x,1, F4.2 and respectively. Then we have the following LSI constant characterization of this process. 1) If p& satisfies c-ISI, μa, satisfies 2 2) If pa, satisfies c-LSI, pkg2 satisfies (c+ o2)- 3) 4k.2 satisfies c-LSI, pk+1 satisfies c-LSI.
23

---

Proof. The first statement is the direct result of Proposition 2.3.3. in [26]. See also Lemma 16 in [15] but additionally require h being differentiable. The second statement is the direct result of Lemma I7 in [5]. The third statement is because ITc is 1-Lipchitz map. Together we complete the proof. 17
K Proof of Lemma G.4
Lemma (Lemma 18 in [5]. with customized variance). For any probability distribution po, Vo and for any &. 2 O, let Pt = Po * NNO. 2102 Ia) and us. vi * (0, 21o² Then for all a > 0 we have
dt Dalpllles = -aa² Ga (p(iv)
(61)
Fa vp(i
Proof. The proof is nearly identical to that in 15 Let Xt Pt. then we have the following stochastic differential equation.
dx, = 2odW
(62)
Thus Pr evolves following the Fokker- Plankkk equation:
0p: 0² Ap:-
(63)
Øt
Same for and just plug this into the first step in the proof of Lemma 18 in [15] which gives the result.
L Proof of Proposition E.1
The proof is a direct manipulation of the Rényi divergence, Due to symmetry, we will only show that 2
(d iD)) S [a-1)n as the proof for the bound of Da(iD, (D) is identical.
Define Zd = exp( (oo(ffo(pp) (rr be the normalizing constant. Then we have
1
(D(x))
vD(x)) Vi (x)
a-1
Da(in,ū a
log Eawip
log Enwis
(64)
exp((ff(xx) (T)(1))
a
1
((22)
LDD')
a-1
log
Exnino
(65)
a 1
Zp
Zp
exp(-fo(z)) exp(-fd:(x))
loog
log( EpvDD
(66)
ZD
Recall that D and D' are adjacent, thus they only differ in one index. Without loss of generality, assume the index is n so that d, = d' for all n. By definition,
(x)
Σ [(;; d + n
(67)
f(x; d + fz; dn) + f(z; dz)) f(r;f( dn))
(68)
1 (f(x; d' - d,)). n
f)(x) +
(69)
As result, the ratio the normalizing constant can be bounded as
Zd
(x)(-//(x))dd J eeep(- fD (x))
fcxp(- + )d
Zp
ZeD
Zp
Zo
(70)
(exp(-fo(x)) + If(xzd()) ((x:d))))) )d
(71)
ZD
Texp(- + F)dr
expl (b) f exeppp- (D()))d
exp(F)70
F exp(
(72)
ZD
Z
Zp
11
24

---

On the other hand, for the second term we have
(xp(=fo(x)) exp(-/p((x))
a-1
ExpiD
Ea exp(- -o))(aaao)(((()-aaaa)))a
(73)
F
S BRniD exp((a
1)((-)) exp((a-
(74)
As result, we can further simplify (64 as follows
ZDD'
(exp(-fb(x)) a-1
Da (VD, PD.) = log(
+
a - log (og
(75)
Z
exp((-f>(x))
F (a 1)F
2F
(76)
π1
(a n
n
Together complete the proof.
M Experiment Details
M.1
(Q, to (e, -Unlearnng Conversion
Let us first state the definition of (c, uunneemingg from prior literature 17
Definition M.1. Consider a randomized learning algorithm M A + RRd and a randomized
unlearning algorithm 4 IR x X X Rd We say (M,u) achieves (c, -nnleermng if for
any adjacent datasets D, D' and any event E, we have
P (U( S F) S exp(e) PMM(D') S F) S
C F. + 6, S F.) + 8.
(77)
(78)
Following the same proof of RDP-DP conversion (Proposition 3 in 22 we have the following s) to (e, -u-uneaann conversion as well.
Proposition M.2. If (M, achieves (a, ERU it satisfies (e, -nmllearnnng well, where
log(1/8)
E E
(79)
a a-1
M.2 Datasets
contains the grey-scale image of number 0 number each with 28 28 pixels. We follow 8 to take the images with the label 3 and 8 as the two classes for logistic regression. The training data contains 11982 instances in total and the testing data contains 1984 samples. We spread the image into an E IR d = 724 feature as the input of logistic regression.
MNIST
CIFAR-10 355 contains the RGB-scale image of ten classes for image classification, each with 32 x 32 pixels. For CIFAR-10-binary. we also select class #3 (cat) and class #8 (ship) as the two classes for logistic regression. The training data contains 10000 instances and the testing data contains 2000 samples. As to TTTAR-10-muliin
we include all the classes for multi-class logistic regression. The training data contains 50000 instances and the testing data contains 10000 samples. We apply data pre-processing on CIFAR-10 by extracting the compact feature encoding from the last layer before pooling of an off-the-shelf pre-trained ResNet18 model (36) from Torch- vision library [48] 49 as the input of our logistic regression. The compact feature encoding is 12d 512.
All the inputs from the datasets are normalized with the l norm of 1.
M.3 Experiment Settings
Hardware and Frameworks All the experiments run with PyTorch=2.1.2 [50] and numpy=1.24.3 (5T). The codes run on a server with single NVIDIA RTX 6000 GPU with AMD EPYC 7763 64-Corc Processor.
25

---

Problem Formulation Given a binary classification task D = {x; RR U/s E +11 our goal is to obtain set of parameters w that optimizes the objective below:
C(:; D)
72 Σ
l(w x, vi)
1w1l2.
(80)
where the objective consists of standard logistic regression loss 1(w T Fy 34) log lo x,), where (t) I+-xp(-t) is the sigmoid function; and a l2 regularization term where À is a hyper- parameter control the regularization, and we À 10-6 across all the experiments. By simple algebra one can show that
VI(w x;; vc) (ou: xx) 1)yxx + Aw; 22((w' x;, 1/1 = ouow x;) - aly x))xxx?? Ald-
(81)
(82)
Due to (Uew") x,) [0, 1], it is not hard that have smoothness L 1/4 + X and strong convexity X.
The per-sample gradient with clipping w.r.t the weights of the logistic regression loss function is given as:
Vetip( (w" X; y1) Ucx ((o x,) 1)y;x,) Aw,
(83)
where Tcc, denotes the gradient clipping projection into the Huelidean ball with the radius of M, satisfy the Lipschitz constant bound. According to Proposition 5.2 of (18). the per-sampling clipping operation still results in a L-smooth, m-strongly convex objective. The resulting Langevin leamnin/unlearning update the full dataset as follows:
V eetipl (w" X4, W));
(84)
Finally, we remark that in our specific case since have normalized the features of all data points (i.e., || = 1), by the explicit gradient formula we know that (I( w x;) 1)y.x,1| S 1.
As to multi-class classification task D {x; E Rdd yi +11071 the loss function denoted as follows [8]]
C(w; D) =
l(w Nis vk) + 2 1
(85)
1=1
where
e u xt
z
I(w x;, 91) = -y² log( " di
yf log( "
(86)
e
After similar derivations, the aforementioned objective function can also yield an explicit expression for the gradient, well as bounds for the constants.
The constant meta-data of the loss function in equation in the table below:
and 85 above for the datasets is shown
Table 1: The constants for the loss function and other calculation on MNIST and CIFAR-10.
expression
MNIST
CIFARIO-binar
CIFAR 10-multi-class
smoothness constant L strongly convex constant Lipschitz constant M
1 +
I + 0.0119
1 +
++1 A
X
0.0100
0.0499
gradient clip
2
RDP constant Cisi
1/n
8.3458e-5
0.0001
2c-5
2a²
m
Learning from scratch set-up For the baselines and our Langevin unlearning framework, we all sample the initial weight randomly sampled from i.i.d Gaussian distribution N(po CLsi), where
26

---

Ao is hyper-yarameee parameter denoting the initialization mean and we set as 1000 to simulate the situation where the initial has long distance towards the optimum alike most situations in real-world applications. For the learning methods M, we set 7 = 10, 000 for all the methods to converge.
Unlearning request implementation. In experiment, for unlearning request of removing data point i, we replace its feature with random features drawn from (O0, 1a) and its label with random label drawn uniformly at random drawn from all possible classes. This similar the DP replacement definition defined in [2) where they replace point with special null point I.
General implementation of baseline D2D (8]
Across all of our experiments involved with D2D, we follow the original paper to set the step size as 2/(L. + m).
For the experiments in Fig. 3a calculate the noise add after gradient descent with the private bound as illustrated in Theorem. [..]Jrre 9 in [8];; For experiments with sequential
unlearning requests in Fig. 3b calculate the least step number and corresponding noise with the
bound in Theorem. N.2 Theorem 28 in (8).
The implementation of D2D follows the pseudo code shown in Algorithm 1,2 in follows:
Algorithm 1 D2D: learning from scratch
1: Input: dataset D
2: Initialize Wo
3: for = 1, 2, 1, 10000 do
4: W, Wr-1 I.
2 1 I (Voin((W(
5: end for
6: Output: W WT
Algorithm 2 D2D: unlearning
1: Input: dataset D;-1, update u,; model w;
2: Update dataset D; D;-1 c 24
3: Initialize w/=
4: for 1,..., do
5: w W Itm
2
E \ vx))))))
6: end for
7: Calculate 7 L+M
8: Draw 7 NN1, 010,0211)
9: Output w; W/, 7
The settings and the calculation of I, a Algorithm. are discussed in the later part of this section and could be found in Section. N
27

---

General Implementation of Langevin Unlearning
We set the step size 7) for Langevin unlearning framework across all the experiments T/T.
The pseudo code for Langevin unlearning framework follows:
Algorithm 3 Langevin unlearning framework, learning unlearning
Input: dataset D
2: if Learn from scratch then
3: Initialize Wo E N (No, CisIla)
4: else
5: Initialize Wo with the pre-trained parameters
6: end if
7: for t = 1,2,.. ...., K do
8: Draw W ind NO La)
9: W. Wt-1 1 E (Venl((((W + +
24 W
10: end for
Output: w WK
M.4 Implementation Details for Fig.
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 test the accuracy on the testing set.
set the target è with different values |0.05, 0.1, 0.5, 1,. For each target è:
For D2D, we set three different unlearning gradient descent step budgets as = 1, 5, and calculate the corresponding noise to be added to the weight after gradient descent on D according to Theorem, N.T. where the detailed noise information is shown in the table below:
Table 2: Baseline a details in Fig. 3a
0.05
0.1
0.5
2
5
1
59.5184
29.7994
6.0233
3.0504
1.5626
0.6663
CIFAR-IO-binary
2
28. 1340
14.0859
2.8472
1.4419
0.7386
0.3149
9,4523 5
4.7325
0.9565
0.4844
0.2481
0.1058
I
5.9612
2.9840
0.6022
0.3044
0.1554
0.0657
CIFAR-IO-multi-llas
2
2.8386
1.4209
0.2867
0.1449
0.0740
0.0313
0.9764 5
0.4887
0.0986
0.0498
0.0254
0.0107
1
36.8573
18.4620
3.7310
1.8890
0.9673
0.4120
MNIST
2
17.3030
8.6229
1.7507
0.8864
0.4538
0.1933
5
5.6774
2.8424
0.5744
0.2908
0.1489
0.0634
For the Langevin unlearning framework, we set the unlearning fine-tune step budget as = 1 only, and calculate the smallest a that could satisfy the fine-tune step budget and target the same time. The calculation follows the binary search algorithm as follows:
28

---

Algorithm 4 Langevin Unlearning: binary search a that satisfy R and target budget
1: Input:target unlearn step budget K, lower bound Flow upper bound hhih
2: while Flow -iihh do
3: mmid = (oew + Thight/ /2
4: call Alg. to find the least K that satisfies é with mid
5: if K K then
6:
Return K
7:
else if' K - K then
8:
Thigh mid
9: else
10:
end if
12:
end while
Algorithm 5 Langevin Unlearning: find the least unlearn step K that satisfies the target
1: Input:target
log( 2: Initialize K K= ==1,e, =,,
3: while do
4: <= c= =-mina>1 [exp( 2Ko das2
aC1si mainn a-1
5: = +1
6: end while
7: Return K
The found is reported in the table below:
Table 3: The found with different target é
0.05
0.1
0.5
1
CIFAR-1O-binand
0.2431
0.1220
0.0250
0.0125
0,0064
0.0028
CIFAR- mo-iiii-uutiss
0.0473
0.0238
0.0049
0.0025
0.0012
0.0005
MNIST
0.1872
0.094
0.0190
0.0096
0.0049
0.0021
M.5 Implementation Details for Fig. 3b
set the total number 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 get the initial weight Wo. and sequentially remove data step by step until all the data points are removed. We count the accumulated unlearning steps K needed in the process.
In this experiment, we fix the target
For D2D, According to the original paper, only data point could be removed time. We calculate the least required steps and the noise to added according to Theorem. N2.2
For Langevin unlearning, we fix the thanks to our theory. We obtain the least required unlearning steps for each removal operation Kis following corollary. 3.4 The pscudo code is shown in Algorithm. 6
0.03, and we let the model unleam [5, 10, 20] per time

---

Algorithm 6 Langevin Unlearning: find the least unlearn step K' in sequential settings
1: Input:target é, a, total removal S, removal batch size b per time
2: Küst =
3: for i in range( S/b) do
4: Initialize Kis{ - 1,
5: while e > do
6: c= c=mina>1(E(0) 0, b, Kins + log(1/6)/(a 1)]
7: Kiuli - = Kin +
8: end while
9:
end for
10: Return Kiist
Algorithm 7 E(C,, b, Küs))
1: Input:target a, a, removal batch size per time, i-th removal in the sequence
2: if i==1 then
3: Return exp(-
En(a, b)
a
4: else
5: Return exp( gmnKgli--)
x
ك-اي a-1
(Eo(2a, (2a b, Kist))
6: end if
Algorithm 8 co S,
Return
4c.5 M²
mo'n?
M.6
Implementation Details for Fig.
In this study, we set the of the Langevin unlearning framework as [0.05, 0.1, 0.2, 0.5, 1]. For each a, we calculate the corresponding eg- We train the Langevin unlearning framework from scratch to get the initial weight Wo. Then we remove 100 data points from the dataset and unlearn the model. We here also call Algorithm. 5 to obtain the least required unlearning steps K.
M.7 Implementation Details for Fig.
In this study, set different target è as [0.5, 1,2, and set different number of data to remove S [1, 50, 100). We train the Langevin 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 again calling Algorithm. 5
M.8 Additional experiments
N
Unlearning Guarantee of Delete-to-Descent
8
Theorem N.1 (Theorem 9 in [8). with internal non-private state). Assume for all d E X, f(a; d)
L-m m-strongly convex, M- -LLischiitz and L-smooth in z. Define = L+m and = I+m Let the learning iteration T
2
log( RRmn / log(1/>) for PGD (Algorithm I in (8)) and the unlearning
algorithm (Algorithm 2 in (8), PCD fine-tuning on learned parameters before adding Gaussian noise) run with I iterations. Assume gaussian noise a to be
((log(1/0)), let the standard deviation of the output perturbation
4/2M-
(87)
mn(1->")(/oon (1)( + Vlog(1/8)
Then it achieves (e, 8) uulearnnng for add/remove dataset adjacency.
30

---

0.91
Accuracy
0.7
Langevin Unkerning
Accuracy
0.90
Langevin Retraining
Retraining Optinum
D2D,
0.89
Untearning 0-5
Retraining,
0.5
D20, R
D2D, 5
Retraining,
Untearning
0.88
Unlearnig, -1
Retraning,
10"
10"
S
(a) S v.S. Accuracy
(b) Unlearn one point on the Adult dataset
Figure 5: (a) The utility results that correspond Figure 4 Since a is fixed the utility is roughly the same. (b) The privacy-utility tradeoff for unlearning point restricting one (or K) unlearning update on the Adult dataset.
Theorem N.2 (Theorem 28 in (8. without internal non-private state). Assume for all d X, I (a;; d) m-strongly convex, M- M-Lipschitz and L-smooth in Define ? L+m and 1j L+m Let the learning iteration T 2 + log( 2 / 1og(1//)) for PGD (Algorithm 1 in (81) and the unlearning algorithm (Algorithm 2 in [8], PGD fine-tuning learned parameters after adding Gaussian noise) run with I + log(log(4di) (o//(//o((///)///////// log(l//)///0/ (1/7)) iterations for the ith sequential unlearning request, where
satisfies
/2d(1-
log
(2g//)2/ (2g(2/8)
(88)
log(1/7)
Assume e (log(1/))), let the standard deviation of the output perturbation gaussian noise o to be
8M
(89)
mm(1->')(V2logg22) 3c / (og((22/ + 2c)
Then it achieves (e, (0llaa)aanningggg.. for add/remove dataset adjacency.
Note that the privacy guarantee D2D 8 is with respect to add/remove dataset adjacency and ours the replacement dataset adjacency. However, by slight modification of the proof of Theorem N. and N.2 one can show that a similar (but slightly worse) bound of the theorem above also holds for directly use the bound Theorem N.] and N.2 in our experiment. Note that [52] also compares a 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 8 For simplicity and fair comparison,
The non-private internal state of D2D. There are two different versions of the D2D algorithm and leverage the model parameter
depending whether allows the server (model holder) before adding Gaussian noise. The main difference between Theorem N. and N.2 is whether their unlearning process starts with the "clean" model parameter (Theorem N.I I or the noisy model parameter (Theorem N.2). Clearly, allowing the server to keep and leverage the non-private internal state provides weaker notion of privacy [8]. In contrast, our Langevin unlearning approach by default only keeps the noisy parameter so that we do not save any non-private internal state. As
result, one should compare Langevin unlearning D2D with Theorem N.2 for fair comparison.
31

---

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 claims are provided with corresponding theorems (i.e., Theorem 3.2 for unlearning guarantees) and we demonstrate superior experiments in Section 4
tradeoff via
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made 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
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 of the work performed by the authors?
Answer: [Yes]
Justification:
We provide a detailed discussion on the limitation of our work in Section
Guidelines:
The answer NA means that the paper has 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 in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model sell-speciiiatiinn asymptotic approximations only holding locally). The authors should reflect on 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 low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to provide closed captions for online lectures because it fails 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 faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
32

---

Answer: [Yes]
Justification: All assumptions are clearly stated in our theorems, see Theorem 3.2 and 3.3 for instance. The proofs for every theoretical statements are provided in 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 they appear in the supplemental material, the authors are encouraged provide short proof sketch to 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 the paper to the extent that 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: We provide the experiment code in our supplementary materials and details about our settings in Section|M
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 to 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 to 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 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, other means that appropriate to the research performed.
also be provided via detailed
While NeurIPS 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) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reprodueibility may be tricky in some cases, in which authors are welcome to describe 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 be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
33

---

reproducible, they Question: 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?
Answer: [Yes]
Justification: We provide the experiment code our supplementary materials and data used in our experiments are cited with public access.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.cm cc/
for more details.
While we encourage the release of code and data, we understand that this might be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/
Coaee//dddeSebmmmcma ssi onPolicy) for more details.
The authors should provide instructions data access and preparation, including how to 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 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 is permitted.
6. Experimental Setting/Details
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 to understand the results?
Answer: [Yes]
Justification: All experimental details are included in Appendix M
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: All results are provided with standard deviation error bar, which gathered over 100 independent trials.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
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 with given experimental conditions).
34

---

The method for calculating the error bars should be explained (closed form formula, call 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 enror 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 range (e.g. negative enror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification:
The compute resources used for our experiments are detailed in Appendix M.3
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute worker CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
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 NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is special consid- eration due to laws or regulations 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 impacts in
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
35

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess 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 not 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 as 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 a 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 no 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 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 is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
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?
Question:
Answer: [Yes]
Justification: All datasets used in experiments are properly cited with proper open access license, see Section
Guidelines:
The answer NA means that the paper does not use 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 is used and, if possible, include 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.
36

---

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 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 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.
37

---

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.
38


Reviews:
[{"review_id": "wDsgSNRrvB", "reviewer": "Reviewer_1Nom", "summary": "The paper proposes Langevin unlearning, a new perspective of noisy gradient descent for approximate machine unlearning, which unifies the differential privacy learning process and privacy-certified unlearning process with many algorithmic benefits. The key technique of the proposed method is to carefully track the constant of log-Sobolev inequality. The authors validate the practicality of Langevin unlearning through experiments on MNIST and CIFAR10, and demonstrate its superiority against gradient-descent-plus-output-perturbation based approximate unlearning.", "questions": "1. Is it possible to provide experiments on (toy) non-convex problems?", "limitations": "1. Most experiments are binary classification problems, with multiclass classification experiments on CIFAR-10-multi-class deferred to the appendix.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "1. The authors innovatively interpret the relations between learning and unlearning via a geometric view.\n\n2. The authors provide a rigorous theoretical analysis of privacy guarantees and a framework for certified non-convex approximate unlearning. \n\n3. The theorems and proofs are well-presented.\n\n4. The proposed method supports insufficient training as well as sequential and batch unlearning, aligning well with practical scenarios.\n\n5. The paper is well-organized and the writing is clear overall.", "weaknesses": "1. The experiments are not extensive enough and do not consider non-convex problems.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank reviewer 1Nom for their praise and positive feedback. We address their sole question below.\n\n**Q1: “Is it possible to provide experiments on (toy) non-convex problems?”**\n\nIndeed, as mentioned in Section 1.1, the current theoretical bound might not be sufficiently tight for non-convex problems. However, it is possible to conduct experiments on toy non-convex problems such as logistic regression with non-convex regularization, including the minimax concave penalty (MCP) or the smoothly clipped absolute deviation (SCAD) penalty. A canonical toy example of a non-convex function is provided in [31]: $f(x) = \\frac{1}{2}\\log(1+\\|x\\|^2) + \\frac{1}{20}\\|x\\|^2$, which is related to Student’s t-regression with a Gaussian prior.\n\nLiterature indicates that the distribution $\\nu(x) \\propto \\exp(-f(x))$ satisfies the Log-Sobolev Inequality (LSI) with a constant roughly around $176$ [31]. Also, it is known that the Langevin diffusion process with $f(x)$ as its potential function and noise variance $1$ has a stationary distribution $\\nu(x)$, also known as the Gibbs measure. Furthermore, $f(x)$ is known to be $1.1$-Lipschitz and $1.6$-smooth within the $\\ell_2$ ball of radius $R=1$.\n\nWhen the step size $\\eta = 1$ and $\\sigma = 1$, the iteration-independent LSI constant bound in Theorem 3.2 approximately evaluates to $8 \\times 10^5$, which is a significant overestimation and results in impractical privacy bounds. This highlights the reasons we did not conduct non-convex experiments.\n\nImproving the unlearning analysis for non-convex problems, particularly a better estimate of the LSI constant, remains an interesting and significant future direction, as already mentioned in our outlined future work.", "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": "7IuP0DtvZD", "reviewer": "Reviewer_tZ8F", "summary": "This paper proposes a novel framework for machine unlearning through noisy gradient descent with Langevin dynamic analysis. This framework has privacy guarantees for approximate unlearning problems and it unifies differential privacy and machine unlearning process, giving benefits including approximate certified unlearning for non-convex problems, complexity saving compared to retraining, sequential and batch unlearning for multiple unlearning requests.", "questions": "How does the unlearning process ensure other learned data are not affected? Are there any empirical results or theoretical guarantees?", "limitations": "While the paper claims to theoretically handle non-convex problems, the practical applicability of the framework for such problems might be limited due to the reliance on certain constants that are either undetermined or can only be loosely determined. The applications may still limited to strong convex problem.", "rating": 5, "confidence": 1, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. The authors propose a novel unlearning framework called Langevin unlearning, which is based on noisy gradient descent. This framework provides a new approach to approximate machine unlearning with privacy guarantees.\n2. The paper presents a theory that unifies the differential privacy (DP) learning process with the privacy-certified unlearning process, offering algorithmic benefits such as approximate certified unlearning for non-convex problems.\n3. This paper provides empirical results showing the practical effectiveness of the proposed framework compared to existing methods.", "weaknesses": "1. The writing is not easy for readers unfamiliar with differential privacy to follow. I think including more details and intuitive explanations in the preliminary would help. \n2. Although the paper discusses the computational benefits over retraining, the empirical results are limited to toy datasets such as MNIST and CIFAR10. Actual scalability and computational complexity of the Langevin unlearning approach for large-scale machine learning models and datasets need further investigation.\n3. The effect of the method is sensitive to hyperparameters such as the standard deviation of the noise.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank reviewer tZ8F for their helpful comments and positive evaluation. We address the weaknesses and questions below.\n\n**W1: “The writing is not easy for readers unfamiliar with differential privacy to follow.”**\n\nWe appreciate reviewer tZ8F's insight on making our manuscript more accessible to a broader audience, including those outside the differential privacy (DP) community. To address this concern, we will incorporate more intuitive explanations into Figure 1, Sections 2.1, and 3.1 to make the concepts more approachable. This will help readers unfamiliar with DP better understand our work.\n\n**W2: “The effect of the method is sensitive to hyperparameters such as the standard deviation of the noise.”**\n\nIt is important to note that the noise scale (standard deviation $\\sigma$) is not a hyperparameter to be tuned arbitrarily. In both DP and theoretical unlearning literature, a privacy constraint $(\\epsilon,\\delta)$ is specified either by regulatory policies or user agreements. We use our theoretical results (specifically, Theorem 3.2) to determine the smallest possible $\\sigma$ that satisfies the given privacy constraint while maintaining the model's utility as much as possible. Therefore, there is no “sensitivity issue” regarding the noise scale, as our theoretical framework provides a privacy-utility trade-off for any given privacy constraint under Definition 2.4.\n\n**Q1: “How does the unlearning process ensure other learned data are not affected? Are there any empirical results or theoretical guarantees?”**\n\nOur Theorem 3.2 provides a theoretical guarantee that the model weight distribution after the unlearning process will be approximately the same as that obtained from retraining the model from scratch without the data that needs to be removed. This essentially means that the other learned data are approximately unaffected by the unlearning process. The gold standard in machine unlearning is retraining from scratch, and our approach closely aligns with this standard by ensuring minimal impact on the remaining data.", "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": "JEN2Vhak8F", "reviewer": "Reviewer_GDGF", "summary": "This paper focuses on approximate unlearning under a similar definition of Differential privacy (DP), where privacy is defined as statistical indistinguishability to retraining from scratch. To be specific, they propose Langevin unlearning, which is a new framework based on the noisy gradient descent with privacy guarantees for approximate unlearning. The proposed framework has demonstrated many benefits like approximate certified unlearning for non-convex problems, and sequential and batch unlearning for multiple unlearning requests.", "questions": "Minor comments and specific questions:\n1. It seems there is no conclusion part, it would be better if the author could summarize the main claims and add it.", "limitations": "This work has adequately discussed the limitations and there is no significant negative societal impact of this work.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. This work studies the theoretical unlearning guarantees of projected noisy gradient descent algorithms for convex problems, which provide fruitful theoretical basics for unlearning with several important algorithmic benefits, like approximate certified unlearning for the non-convex problems, and complexity saving, as well as enabling the sequential and batch unlearning.\n2. The proposed Langevin unlearning based on the projected noisy gradient descent provides a unified geometric view of learning and unlearning processes, which is good for the understanding of the main idea.\n3. Both theoretical results and empirical evaluation of the logistic regression task are provided to make the work comprehensive and insightful.", "weaknesses": "Overall, the reviewer appreciates the idea of Langevin unlearning with the rigorous theoretical analysis for privacy guarantees, below are some comments from the weakness part which are hoped to be constructive for consideration.\n\n1. The current presentation of this work can be further improved by considering clearly stating all the notations at the corresponding position and reorganizing the theoretical results with some intuitive explanation and connection with the empirical evaluation or justifications.\n2. Before introducing the Langevin unlearning with the main results, it could be better to explain the motivation for the proposed framework.\n3. For the geometric interpretation of the relations between learning and unlearning, what is the connection between this and the later illustration of the sequential unlearning and batch unlearning scenarios, and could the authors also explain the gap between the illustration and the practical learning dynamics for the corresponding problems?\n4. For the empirical aspects of Langevin unlearning, how can we understand the corollary 3.4 more intuitively for the benefit obtained by the framework?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank reviewer GDGF for their constructive suggestions and positive assessment. We address the weaknesses and questions below.\n\n**W1: “Suggestions for improving the presentation.”**\n\nWe appreciate the helpful suggestions for improving the presentation of our manuscript. Following the suggestion of reviewer GDGF, we plan to add a more intuitive explanation and motivation in Section 3.1, add connections to empirical justification in Sections 3.2-3.3, and improve the clarity of notations. \n\n**W2: “Question about the geometric interpretation for the sequential unlearning and batch unlearning scenarios, and practical learning dynamics.”**\n\nAs mentioned in Section 3.1, the learning process can be conceptualized as inducing a regular polyhedron in the space of model weight distribution $\\nu_{\\mathcal{D}}$. Each vertex represents a model weight distribution $\\nu_{\\mathcal{D}}$, and adjacent vertices correspond to distributions arising from adjacent datasets $\\mathcal{D}$ and $\\mathcal{D}^\\prime$. The edge length between vertices is indicated by the initial privacy loss $\\varepsilon_0$. The unlearning process effectively involves moving from one vertex $\\nu_{\\mathcal{D}}$ to its adjacent vertex $\\nu_{\\mathcal{D}^\\prime}$ until we are $\\varepsilon$-close to the desired distribution.\n\nWithin this framework, sequential unlearning is interpreted as moving towards different neighboring vertices in sequence (i.e., $\\nu\\_{\\mathcal{D}} \\rightarrow \\nu\\_{\\mathcal{D}\\_1} \\rightarrow \\nu\\_{\\mathcal{D}\\_2}...$), as depicted in Figure 2. It is important to highlight that the unlearning process halts once we are $\\varepsilon$-close to the current target distribution. Consequently, the \"initial distance\" for the subsequent unlearning request is not merely $\\varepsilon_0$. Utilizing our geometric interpretation, we apply the weak triangle inequality to provide an upper bound for this initial distance in terms of $\\varepsilon_0$ and $\\varepsilon$. This allows us to employ Theorem 3.2 to ensure the desired unlearning guarantee.\n\nIn the context of batch unlearning, the notion of data adjacency is altered so that datasets $\\mathcal{D}$ and $\\mathcal{D}^\\prime$ are considered adjacent if they differ in $S$ points. This modifies the underlying regular polyhedron, where the edge length (initial distance) now becomes $\\varepsilon_0^{(S)}$. Once $\\varepsilon_0^{(S)}$ is determined, Theorem 3.2 can again be applied to guarantee successful unlearning.\n\nIt is also essential to note that the aforementioned discussion pertains to the worst-case scenario. In practical situations, adjacent (un)learning processes are typically closer in terms of distribution. Recent evidence supporting this claim includes a study [38] demonstrating that models trained using DP-SGD with $\\varepsilon \\approx 10^{8}$ perform optimally against empirical adversarial attacks, such as membership inference attacks, compared to other popular heuristic defenses. We expect similar behavior to persist for Langevin unlearning, highlighting the practical potential of our approach.\n\n**W3: “Understand the benefit of Corollary 3.4 more intuitively.”**\n\nThe primary benefit of Corollary 3.4 is that it facilitates Langevin unlearning for sequential unlearning requests. Sequential unlearning holds significant practical value, particularly in light of regulations like the GDPR that explicitly state, “the data has to be erased without undue delay.” While we do not assert that sequential unlearning is superior to batch unlearning, it is crucial to recognize that these two approaches are orthogonal and can be effectively combined. For instance, one could sequentially unlearn $S\\times T$ points by removing $S$ points in each iteration of the process.\n\n**Q1: “No conclusion part”**\n\nWe acknowledge reviewer GDGF's suggestion and appreciate the feedback. We will incorporate a conclusion section in the manuscript to summarize our key results and contributions.", "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": "hHP5kRsNDu", "reviewer": "Reviewer_Akdu", "summary": "This paper proposes an unlearning framework based on Langevin dynamics with two key components:\n- The initially trained model satisfies some differential privacy guarantee\n- Unlearning relies on DP fine-tuning the model on the rest of the dataset (which quickly reduces the privacy loss on the example to be forgotten).\n\nThis framework is formalized using the theory of convergence of Langevin dynamics. Specifically, assuming the Log-Sobolev inequality holds for the stationary distribution, the paper establishes a linear rate of convergence of the unlearning step. Notably, these bounds apply for the nonconvex setting as well; however, the constants are quite pessimistic in this case. The explicit constants are given for the convex and strongly convex settings, leading to implementable algorithms.\n\nThe paper also gives extensions to multiple deletions (sequential and simultaneous). Advantages relative the D2D baseline and retraining from scratch are established as well.", "questions": "- What are the various degrees of freedom in the privacy-utility-compute tradeoff? I assume that if we fix $\\epsilon$ (privacy) and $K$ (compute), then we can tune $\\sigma$ to get the desired privacy bound. Are there other degrees of freedom? If there is an extra degree of freedom, what are some rules of thumb for setting the parameters?\n\n- Continuiung from the above, it would be nice to see some more plots exploring this tradeoff. Examples:\n     - Fix $K$, plot accuracy vs $\\epsilon$ (or vs. $\\sigma$) (I believe Fig 3c varies $K$ between the various points)\n     - Fix $\\sigma$, plot accuracy vs. $\\epsilon$ (or vs. $K$)\n     - Fix $\\epsilon$, plot accuracy vs. $K$\n\n-  How do $C_k$ and $R_k$ scale with $k$ in the various settings of Theorem 3.2? While the authors acknowledge that the rates in the nonconvex case are pessimistic, it would be nice to discuss exactly how the iteration independent lower-bound scales with various problem parameters. Specifically, the dependence on which parameters do you think can be improved?\n\n- Figure 3b: do all of the points have the same utility?\n\n- Theorem 3.2(c): The strongly convex case needs $\\sigma^2$ small enough. I wonder about the implications of this requirement. Does it mean that unlearning is not possible using the given framework for certain parameter values? Does it mean that a certain minimum amount of compute is necessary to make unlearning possible? It would be great to explore these quantitatively from the established bounds. \n\n- Can the established unlearning guarantees be compared analytically to existing ones?", "limitations": "Yes, limitations have been adequately addressed.", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "This is a very strong paper and generally high quality work.\n- While it is grounded in RDP, the theoretical advances are original. I love that the paper also explores 2nd order effects of the proposed framework, such as batch/parallel unlearning, etc. \n- This framework gives the first provable approximate unlearning guarantees in the nonconvex setting and improves upon other approaches in the (strongly) convex setting. I believe these results are very significant and can inspire future work in the area.\n- The paper is generally well-organized and well-written (although it is not perfect; specific suggestions for improvements are given below).", "weaknesses": "- **Clarity**: The paper tackles some advanced technical tools, which may only be known to a niche audience. It would greatly help the broader appeal of the paper to explain the key intuition behind the LSI and why it can be expected to hold. Similarly, it would be nice to consider simple examples in the unlearning setting and give explicit values of the LSI constant. Also, what is its right scaling with respect to other problem parameters such as smoothness, strong convexity, etc.?\n\n- The improvements from Langevin unlearning over training from scratch are purely logarithmic. How significant is this factor in the experiments? \n\n- The paper uses full gradient steps. How do things change with stochastic gradient steps? What would be the computational complexity of the resulting algorithm?\n\n- No experiments in the nonconvex case. Since these are the only provable guarantees in the literature so far, future work in the area would greatly benefit from setting up a benchmark with the results of this work.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are glad that Reviewer Akdu recognizes our work as a very strong and high-quality paper. We also appreciate the thoughtful comments and suggestions. We address the weaknesses and questions below.\n\n**W1: “Question about LSI constant.”**\n\nThank you for your valuable suggestion. We will add some intuition about the Log-Sobolev Inequality (LSI) in our revision. Roughly speaking, LSI characterizes the tail density as “well-behaved.” For instance, the density of the form $\\nu \\propto \\exp(-V(x))$ satisfies LSI when the tail behaves as $V(x) \\approx \\|x\\|^2$. If the tail exponent is smaller, say $\\|x\\|^\\alpha$ with $\\alpha \\in (0,2)$, it corresponds to different isoperimetric inequalities. For a more detailed discussion, please refer to our Appendix B, as well as references [31] and the comprehensive book [26]. See also the section 3 and 4.2 of [31] for some LSI constant example of non-convex distrubiton. \n\n**W2: “How significant is the benefit compared to retraining in the experiments?”**\n\nThe significance of the benefit compared to retraining can be observed from Figure 3(a) in the experiment section. In our experiments, Langevin unlearning uses only **one** unlearning update per removed data point, achieving a strong privacy guarantee (i.e., $\\epsilon=1$) while maintaining similar accuracy (utility) to retraining from scratch, even when retraining is performed without noise (Retraining Optimum). In contrast, retraining would require **at least** tens of iterations even with a good initialization, and more iterations when the initialization is far from the optimum. This clearly demonstrates that the benefit of our approach compared to retraining is significant in terms of both efficiency and computational cost.\n\n**W3: “Extension to mini-batch setting”**\n\nThis is a great question! We have discussed how to correctly extend Langevin unlearning to a mini-batch setting in Appendix A. A more thorough study of this extension is left for future work. The extension to mini-batch settings offers potential improvements in both computational efficiency and adaptability to larger datasets, making it a promising area for further investigation.\n\n\n**Q1: “The privacy-utility-computation trade-off.”**\n\nThis is an excellent question! Indeed, for a given $\\varepsilon$ (privacy), by fixing $K$ (unlearning steps), we can compute the smallest possible $\\sigma$ (noise) to achieve the best possible model utility. Alternatively, another trade-off can be considered: fixing $\\sigma$ based on the model utility that one is satisfied with, and then computing the required $K$ that needs to be executed. These approaches allow for a flexible adjustment of parameters based on the desired balance between privacy, utility, and computational cost.\nExperiments to examine the privacy-utility-computation trade-off are indeed crucial, and this is the main focus of Section 4 in our manuscript. Our Figure 3(a) illustrates the trade-off between $\\epsilon$ (privacy) and model utility (accuracy) for all tested methods, with $K=1$ fixed unless otherwise specified. Figure 4 further demonstrates the trade-off between $K$ and $\\epsilon$ for a fixed $\\sigma$. Additionally, Figure 3(c) can be interpreted as a trade-off between accuracy (y-axis on the right, inversely related to $\\sigma$) and $K$ for a fixed $\\epsilon$. We will provide more explicit explanations and highlight these trade-offs in our revision to ensure clarity for readers.\n\n\n**Q2: “Questions about $C_k$ and $R_k$.”**\n\nTo elaborate, $C_k$ scales linearly with $k$ (for the convex case) until it reaches an iteration-independent upper bound $\\tilde{C}$, and $R_k$ is roughly the difference $1/C_k^2 - 1/C_{k+1}^2$. For the non-convex case, the dependency on $k$ is worse due to the multiplicative factor $(1+\\eta L) > 1$ for $L$-smooth functions and when the step size $\\eta > 0$. We believe that the dependencies on all parameters ($L, \\eta, k, R$, etc.) can be improved.\n\nConsider a special case where our target distribution is exactly Gaussian $N(0, C I_d)$ with variance $C$. In this scenario, the corresponding LSI constant is $C$, but our bound provides a relatively poor estimate when $C$ is moderate. Intuitively, for sufficiently large $k$, the underlying distribution $\\rho_k$ or $\\nu_t$ will be close to $N(0, C I_d)$, and the tight bound should be roughly $C$, which is not adequately captured by our Theorem 3.2.\n\nCombined with the discussion in W1, we conjecture that for losses that grow sufficiently fast as the norm of the weight goes to infinity, it may be possible to derive a much tighter estimate of the LSI constant along the (un)learning process.\n\n**Q3: “Do all points in Figure 3(b) have similar utility?”**\n\nYes. As stated in lines 359-361, all points have similar utility (accuracy) of approximately 0.9 for MNIST and 0.98 for CIFAR-10, respectively.\n\n**Q4: “Question about the strongly convex case of Theorem 3.2.”**\n\nThere might be some confusion here. As explained in the simple example provided in W1, it is not necessary to enforce $\\sigma$ to be particularly small. Our statement in line 243 pertains purely to the initialization. Note that if a distribution satisfies $C$-LSI, it also satisfies $C^\\prime$-LSI for all $C^\\prime \\geq C$. As a result, given $\\sigma^2,m$, we can always choose $C_{LSI}$ to be larger than $\\sigma^2/m$, given that the initialization is (roughly) a constant (delta measure) which satisfies $C$-LSI for any $C>0$.\n\n**Q5: “Can the established unlearning guarantees be compared analytically to existing ones?”**\n\nThis is a great question. While we can compare our unlearning bounds to existing results in the literature numerically, it is challenging to make an analytical comparison due to the RDP-to-DP conversion process [21]. This complexity is similar in the differential privacy (DP) literature, where researchers typically compare Rényi Differential Privacy (RDP) bounds with DP bounds numerically via such conversions.", "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, which has gained interest in recent years. It proposes a new algorithm, where the initial model is trained with a DP algorithm and then unlearning relies on fine tuning the model on the rest of the dataset, again with differential privacy. Theoretical guarantees are provided for convex, strongly convex, and non-convex settings, and the algorithm is empirically demonstrated on a few small datasets.

While the reviewers are generally positive, they do raise a few concerns: lack of experiments on non-convex problems, theoretical guarantees require full-gradient steps at each iteration, and certain parts of the paper are difficult to follow.  While I agree with the reviewers, I do believe the paper provides a new algorithm and theoretical results that would be of interest to many in the community. I recommend acceptance. I strongly encourage authors to address reviewer concerns in the final version of the paper.
Decision: Accept (spotlight)