Rewind-to-Delete: Certified Machine Unlearning for Nonconvex Functions
Authors: Siqiao Mu
Diego Klabjan
Venue: NeurIPS 2025 poster ()
Keywords: machine unlearning
privacy
nonconvex
nonconvex optimization
differential privacy
first-order methods
gradient descent
deep neural networks
Primary area: social_and_economic_aspects_of_machine_learning

Abstract: Machine unlearning algorithms aim to efficiently remove data from a model without retraining it from scratch, in order to remove corrupted or outdated data or respect a user's "right to be forgotten." Certified machine unlearning is a strong theoretical guarantee based on differential privacy that quantifies the extent to which an algorithm erases data from the model weights. In contrast to existing works in certified unlearning for convex or strongly convex loss functions, or nonconvex objectives with limiting assumptions, we propose the first, first-order, black-box (i.e., can be applied to models pretrained with vanilla gradient descent)  algorithm for unlearning on general nonconvex loss functions, which unlearns by ``rewinding" to an earlier step during the learning process before performing gradient descent on the loss function of the retained data points. We prove $(\epsilon, \delta)$ certified unlearning and performance guarantees that establish the privacy-utility-complexity tradeoff of our algorithm, and we prove generalization guarantees for nonconvex functions that satisfy the Polyak-Lojasiewicz inequality. Finally, we demonstrate the superior performance of our algorithm compared to existing methods, within a new experimental framework that more accurately reflects unlearning user data in practice.

Rewind-to-Delete Certified Machine Unlearning for Nonconvex Functions
Siqiao Mu
Department of Engineering Sciences and Applied Mathematics Northwestern University Evanston, II. 60208
Diego Klabjan
Department of Industrial Engineering and Management Sciences
Northwestern University
Evanston, IL 60208
d.k.abbaanehoortwesstem..mm edu
Abstract
Machine unlearning algorithms aim to efficiently remove data from a model with- out retraining it from scratch, in order to remove corrupted outdated data respect user's "right to be forgotten." Certified machine unlearning is a strong the- oretical guarantee based differential privacy that quantifies the extent to which an algorithm erases data from the model weights. In contrast to existing works certified unlearning for convex strongly convex loss functions, nonconvex objectives with limiting assumptions, we propose the first, first-order, black-box (i.e., can be applied models pretrained with vanilla gradient descent) algorithm for unlearning on general nonconvex loss functions, which unlearns by "rewinding" earlier step during the learning process before performing gradient descent on the loss function of the retained data points. We prove (c, 8) certified unlearning and performance guarantees that establish the privacy-utility-oo complexxty tradeoff of our algorithm, and we prove generalization guarantees for functions that satisfy the Loyaak-ojjsiewiez inequality. Finally, we demonstrate the superior perfor- mance of our algorithm compared to existing methods, within new experimental framework that more accurately reflects unlearning user data in practice.
Introduction
Machine unlearning, or data deletion from models, refers to the problem of removing the influence of some data from trained model without the computational expenses completely retraining from scratch [6]. This research direction has become highly relevant in the last few years, due to increasing concern about user privacy and data security as well as the growing cost of retraining massive deep learning models on constantly updated datasets. For example, recent legislation that protects user's s "Right be Forgotten," " including the European Union's 's General Data Protection Regulation (GDPR), the California Consumer Privacy Act (CCPA), and the Canadian Consumer Privacy Protection Act (CPPA), mandate that users be allowed to request removal their personal data, which may stored in databases or memorized by models [38]. In addition, machine unlearning has practical implications for removing the influence of corrupted, outdated, or mislabeled data [28. 35].
The typical goal of machine unlearning algorithms is to yield a model that resembles the model obtained from full retrain on the updated dataset after data removed. This requirement is
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Table Comparison of certified unlearning algorithms for convex and nonconvex functions, where d is the dimension of the model parameters and n is the size of the training dataset.
Algorithm
Loss Function
Method
Storage
Black-box?
Newton Step[23]
Strongly convex
Second-order
(
Rescent-to-Delett [34]
Strongly convex
First-order
O(d)
Langevin Unlearning [12]
Nonconvex
First-order
O(d)
Constrained Newton Step [48]
Nonconvex
Second-order
(
Hessian-Free Unlearning [37]
Nonconvex
Quasi-sccond-order
((nd)
Our Work (R2D)
Nonconvex
First-order
((d)
formalized in the concept of "certified unlearning," a strong theoretical guarantee motivated by differential privacy that probabilistically bounds the difference between the model weights returned by the unlearning and retraining algorithms [23]. However, algorithms satisfying certified unlcarning need also be practical. For example, retraining the model from scratch on the retained dataset is trivial unlearning algorithm that provides no efficiency gain. On the other hand, unlearning is also provably satisfied if the learning and unlearning algorithm both output weights randomly sampled from the same Gaussian distribution, but this would yield poorly performing model. Therefore, an ideal algorithm optimally balances data deletion, model accuracy, and computation, also known the tradeoff [32]. Moreover, because training from scratch is computationally expensive in the machine unlearning setting, we desire black-box unlearning algorithms, which can be applied to pretrained models and do not require training with the intention of unlearning later.
siriaacy-uility-fffiieeeee
Most certified unlearning algorithms are designed for convex or strongly convex functions [23, 34, 38). Relaxing the convexity requirement is challenging since nonconvex functions do not have unique global minima. Recently, there have been several works that provide certified unlearning guarantees for nonconvex functions. For example, [48] proposes a single-step Newton update algorithm with convex regularization followed by Gaussian perturbation, inspired by existing second-order unlearning methods such as [23, 38]. Similarly, [37] proposes quasi-second-one
method that exploits Hessian vector products avoid directly computing the Hessian. Finally, [12] proposes first-order method in the form of projected noisy gradient descent with Gaussian noise added at every step.
Prior work has focused on achieving theoretical unlearning guarantees in the nonconvex setting; however, practical unlcarning algorithms should also be computationally efficient and convenient to use. First, [48] and [37] are both (quasi) second-order methods, but first-order methods that only require computing the gradient are more computationally efficient and require less storage. Second, [12, 37] are not black-box, since during the training process, [12] requires injecting Gaussian noise at every step and [37] requires storing a statistical vector for each data sample at each time step. These "whiteeboxx" algorithms require significant changes to standard learning algorithms, which hinders easy implementation. See Table I and Appendix E for an in-depth comparison with prior work.
In this work, we introduce 'rewind-to-delete (R2D), first-order, black-box, certified unlearning algorithm for general nonconvex functions. Our lcarning algorithm consists of vanilla gradient descent steps the loss function of the dataset followed by Gaussian perturbation to the model weights. To remove data from the model, our unlearning algorithm "rewinds" to a model checkpoint from earlier in the original training trajectory, followed by additional gradient descent steps on the new loss function and Gaussian perturbation. The checkpoint can be saved during the training period (which is standard practice), proximal point method. We prove (c, 8) certified unlearning for our algorithm and provide theoretical guarantees that explicitly address the "privacy-utility -ufliity-fffciency"" tradeoff of our unlearning algorithm. Our algorithm is simple, easy to implement, and black-box, as it can be applied to pretrained model as long as the model was trained with vanilla gradient descent.
it can be computed post hoc from pretrained model via the
We also analyze the case of nonconvex functions that satisfy the The PL inequality is weak condition that guarantees the existence of connected basin of global minima, to which gradient descent converges at a linear rate [27]. This property allows us to derive empirical risk convergence and generalization guarantees, despite nonconvexity. PL functions are highly relevant to deep learning because overparameterized neural networks locally satisfy the PL condition in neighborhoods around initialization [30].
(PL) inequality.
Finally, we empirically demonstrate the privacy-utilit--e -fffciiyyeffccceney tradeoff of our unlearning algorithm and its superior performance compared to other algorithms for nonconvex functions, within chal-

---

lenging new framework in which the unlearned data is not independently and identically distributed (i.i.d.) to the training or test set. Most experiments select the unlearned samples either uniformly at random [48, 37] or all from one class [23, 20, 28], neither of which reflects unlearning in practice. For example, if we train 10-class classifier and lose access to data from one class, we would not continue to use the same model on a 9-class dataset. In our approach, we instead train model to learn some global characteristics about a real-world dataset derived from a collection of users. Upon unlearning, we remove data associated with subset of the users, thereby simulating realistic unlearning requests and their impact on model utility. To assess the extent of unlearning, we adapt membership inference attack (MIA) methods [41, 9] discriminate between the unlearned dataset and an -fff-ii-iittiitttonn dataset, constructed separately from users not present in the training data. Our results demonstrate that R2D outperforms other certified and non-certified methods, showing greater decrease in performance on the unlearned data samples and defending successfully against both types of membership inference attacks (Tables 2 and 3). In particular, compared to the white-box algorithm [37], R2D is up to 88 times faster during training, highlighting the advantage of our black- box approach (Tables 6 and 7). Ultimately, our first-order method enjoys the benefits of minimal computational requirements, easy off-the-shelf implementation, and competitive performance. While this work primarily addresses certified unlearning, our theoretical and empirical insights suggest that "rewinding" is a more appropriate baseline for comparison with new unlearning algorithms for deep neural networks, as opposed to to standard baselines like finetuning or gradient ascent.
Our contributions are as follows.
We develop the first (c, 5) certified unlearning algorithm for nonconvex loss functions that is first-order and black-box.
We prove theoretical unlearning guarantees that demonstrate the privacy-utility-efficien tradeoff of our algorithm, allowing for controllable noise at the expense of privacy or computation. For the special case of PL loss functions, obtain linear convergence and generalization guarantees.
We empirically demonstrate the superior performance of our algorithm compared to both certified and non-certified unlearning algorithms, within a novel experimental framework that better reflects real-world scenarios for unlearning user data.
1.1 Related Work
Differential privacy (DP) [15] a well-established framework designed to protect individual privacy by ensuring that the inclusion or exclusion of any single data point in a dataset does not significantly affect the output of data analysis or modeling. limiting information leakage about any individual within the dataset. Specifically, a DP learning algorithm yields a model trained on some dataset that is probabilistically indistinguishable from a model trained on the same dataset with data sample removed or replaced. The concept of (e, 6) --privacyy quantifies the strength of this privacy guarantee in terms of the privacy loss, e. and the probability of a privacy breach, [14]. This privacy can be applied during after training by injecting controlled noise to the data, model weights [46, 49], gradients [1, 49], or objective function [8], in order to mask information about any one sample in the dataset. However, greater noise typically corresponds to worse model performance, leading to a trade-off between utility and privacy. The theory and techniques of differential privacy provide a natural starting point for the rigorous analysis of unlearning algorithms.
Differential privacy.
As observed in [46], "white-box" DP algorithms, which require code changes to inject noise at every training step, require additional development and runtime overhead and are challenging to deploy in the real world. Rather than adding noise at each iteration, [46] and [49] propose DP algorithms that only perturb the output after training, which is easier to integrate into standard development pipelines. In similar fashion, our proposed black-box box unlcarning algorithm can be implemented without any special steps during learning with gradient descent. We also do not inject noise at each iteration, and we only perturb at the end of training. The difference between our approach and [46, 491, however, is that our approach can accommodate the nonconvex case, leveraging model checkpointing to control the distance from the retraining trajectory.
Certified unlearning. The term "machine unlearning" was first coined by [6] to describe a determin- istic data deletion algorithm, which has limited application to general optimization problems. In the following years, techniques have been developed for "exact unlearning," which exactly removes the
3

---

influence of data, and "approximate unlearning." which yields a model that is approximately close to the retrained model with some determined precision [47]. Our work focuses on the latter. Both [18] and [23] introduce a probabilistic notion of approximate unlearning. where the unlearning and retraining outputs must be close in distribution, Inspired by differential privacy, [23] introduces the definition of certified (e, 8) unlearning used in this work. Like DP algorithms, certified unlearning algorithms typically involve a combination of empirical risk minimization and noise injection to the weights or objective function, which can degrade model performance. Moreover, unlearning algorithms are also designed to reduce computation, leading to a three-way trade-off between privacy, utility, and complexity.
Certified unlearning has been studied for a variety of settings, including linear and logistic models [23, 25], graph neural networks [10]. minimax models [31]. and the federated learning setting [17], as well as convex models [38, 34, 42, 11] and nonconvex models [12, 37,4..8.. These algorithms can be categorized as first-order methods that only require access to the function gradients [34, 11] or second-order methods that leverage information from the Hessian to approximate the model weights that would result from retraining [38. 42, 48, 37j. Our work is inspired by the
(D2D) algorithm [34], a first-order unlearning algorithm for strongly convex functions that unlearns by fine-tuning with gradient descent iterates the loss function of the retained samples.
Nonconvex unlearning. There are also many approximate unlearning algorithms for nonconvex functions that rely on heuristics or weaker theoretical guarantees. For example, [4] proposes a "weak unlearning" algorithm, which considers indistiguuisaability with respect to model output space instead of model parameter space. Another popular algorithm for neural networks is SCRUB [28]. a gradient- based algorithm that balances maximizing error on the unlearned data and maintaining performance on the retained data. An extension of SCRUB, SCRUB+Rewind, "rewinds" the algorithm to point where the error on the unlearned data is "just high enough," " so as to impede membership inference attacks. Furthermore, [20, 21] propose unlearning algorithms for deep neural networks, but they only provide a general upper bound on the amount of information retained in the weights rather than a strict certified unlearning guarantee. Additional approaches include subtracting out the impact of the unlearned data in each batch of gradient descent [22]. gradient ascent on the loss function of the unlearned data [26]. and retraining the last layers of the neural network on the retained data [19]. Ultimately, while the ideas of checkpointing, gradient ascent, and 'rewinding" have been considered in other machine unlearning works, our algorithm combines these elements in novel manner to obtain strong theoretical guarantees that prior algorithms lack.
Notably, virtually all unlearning papers implement noiseless "finetuning" baseline method which is based on the D2D framework. This is usually because finetuning is first-order and easy to implement, even though D2D only has theoretical guarantees on strongly convex functions (which are impossible to extend to nonconvex settings) and finetuning does not perform well empirically on deep neural networks. In contrast, R2D is equally easy to implement, has theoretical guarantees nonconvex functions, and empirically outperforms certified and non-certified methods. Therefore, our work provides strong support that rewinding instead of "descending" is a more appropriate baseline method for comparison.
2 Algorithm
Let D = [.,,,.., ) be training dataset of data points drawn independently and identically distributed from the sample space 2, and let θ be the (potentially infinite) model parameter space. Let A: : 2" + θ be a (randomized) learning algorithm that trains on D and outputs a model with weight parameters& 0 O where θ is the (potentially infinite) space of model weights. Typically, the goal of learning algorithm is to minimize (0), the empirical loss on D, defined as fD( where f=. (0) represents the loss on the sample 2;-
n fa, (0),
Let us "unlearn" or remove the influence of subset of data Z C DD from the output of the learning algorithm A(D). Let D' = D' Z, and we denote by U(AD), D, Z) the output of an unlearn- ing algorithm U. The goal of the unlearning algorithm is to output a model parameter that is probabilistically indistinguishable from the output of A(D'). This is formalized in the concept of (e, 8) mondistinnuisability. which is used in the DP literature to characterize the influence of data point on the model output [14].

---

Definition 2.1. [14, 34] Let X and Y be random variables over some domain Q. We say X and Y are (e, -iiiistiinguuihhall if for all S f2.
P[X E S] S E $]+0 à, P|Y S) Sc E 51 +
In the context of differential privacy, X and Y are the learning algorithm outputs on neighboring datasets that differ in single sample. e is the privacy loss or budget, which can be interpreted as limit on the amount of information about an individual that can be extracted from the model, whereas 5 accounts for the probability that these privacy guarantees might be violated. Definition 2.1 extends naturally to Definition 2.2, the definition of (c, certified unlearning.
Definition 2.2. Let Z C D denote the data samples we would like to unlearn. Then U is an (e, 6) certified unlearning algorithm for A if for all such Z, U(A(D), 2) and A(D)Z) are (e, 0)- indistinguishable.
Next, describe our algorithm A (Algorithm 1) performs gradient descent updates on fo for iterations, and the iterate at the T - K time step saved checkpoint computed post hoc via the proximal point algorithm (Algorithm 3). Then Gaussian noise is added to the final parameter 0y, and the perturbed parameter is used for model inference. When request is received remove the data subset Z, the checkpointed model parameter Oy- K is loaded as the initial point of the unlearning algorithm U (Algorithm 2). Then we perform K gradient descent steps the new loss function fD and add Gaussian noise again to the final parameter, using the perturbed weights for future model inference.
(R2D) algorithms for machine unlearning. The learning
Algorithm 1 A: R2D Learning Algorithm
Algorithm 2 U: R2D Unlearning Algorithm
Require: dataset D, initial point On E θ for t = 1, 2, T do
Require: dataset D', model checkpoint Or-K 0% = 0r-K K
8, - 0:11 V (D(0-11)
for ... K do
end for Save checkpoint 0r- compute 0y-K via Algorithm
0 = 0-1 - 1/ (0%_)
end for
Sample ~ *=(00, 0"= 0*k + Use 8" for model inference
Sample { &~ ~N,00, II))
0= Or + g
Use i for model inference
Upon receiving an unlearning request, call Al-
Algorithm 3 Compute Checkpoint via Proximal Point Method
gorithm
When a model is trained without a checkpoint saved, can still obtain black-box unleam- ing algorithm by carefully undoing the gradi- descent training steps via the proximal point method, outlined in Algorithm 3. We can solve for previous gradient descent iterates through the following implicit equation (2):
Require: datasets D, model checkpoint 0r We 0T for t=
do W0 arg min (-fo(x)+ || Wt 112)
end for return WK
01+1 O2 (..
+
The backward Fuler update in (2) is distinct from a standard gradient ascent step, which is a forward Fuler method. Instead, compute O, from 0,+1 by taking advantage of the connection between backward Euler for gradient flow and the proximal point method, an iterative algorithm for minimizing convex function [33]. Let g(0) denote convex function. The proximal point method minimizes g(0) by taking the proximal operator with parameter of the previous iterate, defined as follows
0 proz (0%) arg min(g( + 1 || 1
27
Although for our problem, / is nonconvex, adding sufficient regularization produces a convex and globally tractable proximal point subproblem, stated in Lemma A. Therefore, by computing the proximal operator with respect to (0), we can solve the implicit gradient ascent step.
5

---

Lemma 2.1. Suppose f(0) is continuously differentiable, Bg is defined as in (2), and let < L. Then proz pr, (8,41))
If 7 < t. then due to strong convexity, we can solve the proximal point subproblem casily via gradient descent Newton's 's method. Computationally, when K < T. the algorithm is comparable to other second-order unlcarning methods that require a single Newton step. In addition, we only need compute the model checkpoint once prior to unlearning requests, this computation considered "offline" [25, 37]. In Appendix B.3, we test the ability of Algorithm to reconstruct prior training steps in practice (Table 8), and measure the additional computation time required (Tables 9 and 10). We measure the Euclidean distance between the original checkpoint and the reconstructed checkpoint, observing that
be
quite faithfully reconstruct checkpoints for K < T/2, but beyond this point we encounter instability issues due to compounding approximation errors.
In general, our work shares similarities with Sosceenttt-Delette (D2D), which "descends" from the trained model Qr instead of from an earlier checkpoint 0r-K. However, extending the D2D analysis beyond the strongly convex setting is impossible since it relies the existence of a unique global minimum, which (i) attracts training trajectories and (ii) remains in a small neighborhood when the underlying loss function is changed. Neither (i) nor (ii) hold for the general nonconvex setting, where we may only converge to a local minima or saddle point. Our novel insight is we leverage rewinding instead of "descending" to bring the unlearned model closer to the retrained model by reversing the divergence in training trajectories caused by the unlearning bias.
3 Analyses
The proof's of all theoretical results can be found in Appendix A. In the following theorem, we establish the unlearning and performance guarantees for our algorithm on nonconvex functions. For nonconvex functions, gradient descent might converge to local minima or saddle points, so we measure the performance by the average of the gradient norm over iterates, common DP performance metric for algorithms on nonconvex functions.
Theorem 3.1. Let ê be fixed such that 0 < E < and é > O. Suppose for all E Z, the loss function f& L-Lipschitz smooth and the gradient is uniformly bounded by some constant G so that ||V (0)] < G for all 0 E Q Let 'D denote the original dataset of size let Z C D denote the unlearned dataset of size m, and let D' Z denote the retained dataset. Let the learning algorithm A be initialized at 0o and rumfor T iterations with step size r S minn + Xn-m)] Let the standard deviation o of the Gaussian noise be defined as
2mG +(() 2 log(1.255)) (1.25/0)
(3)
Lan.
where ((K) is function that monotonically decreases to zero K increases from to T defined by
nLn - 1)(1 n/..KK
M(K) ((1
n m
Then U is an (c, 80-ullarnnn algorithm for A with noise a. In addition,
T T-K-1
K-1
|o (0.)1
Σ
V (12) + V (0")
(T K 1)m
<0
(4)
T(n ((n-m) m)
T(n m)
where the expectation laken with respect to the Gaussian noise added the end of U, and where O()) hides dependencies on q, G, and L..
Corollary 3.2. For fixed a and 8, the dependence of K on in (3), denoted as K(e), is bounded as follows:
K(e)= 5 (log(1 + Tn )) log((1 + nLn ) m
L
(5)
2mG (...2///

---

Equation (4) states that the average of the gradient norm squared of the initial T K learning iterates, the K - unlearning iterates after, and the last perturbed iterate 6" decreases with increasing T and n, indicating that the algorithm converges a stationary point with small gradient norm. Corollary 3.2 provides an upper bound on ((c), such that in practice we can choose K equal to this bound to ensure the privacy guarantee is achieved.
The analysis relies on carefully tracking the distance between the unlearning iterates and gradient descent iterates on /pr. Like prior work in certified unlearning, our analysis relies on the Gaussian mechanism for differential privacy [14], which implies that as long as the distance between the trajectories is bounded, we can add a sufficient amount of Gaussian noise make the algorithm outputs (e, D>-indistinguihable. We therefore can compute the noise level ø required to achieve unlearning. For the utility guarantees, we leverage the fact that gradient descent steps on fo also make progress on for to obtain bounds that only depend on problem parameters and fg-
Theorem 3.1 underscores the watpaccy--iilitccoomoee
tradeoff between measure of unlearning. noise, a. and the number of unlearning iterations, K. By construction, K < T, so our algorithm more efficient than retraining. We can pick larger K such that the noise required is arbitrarily small at the expense of computation, and when = T our algorithm becomes a noiseless full retrain. Moreover, the standard deviation o inversely scales with the size of the dataset n, implying that unlearning on larger datasets require less noise. In contrast. [48] and [37] do not feature such data-dependent guarantees. In practice, following the guidelines in [48], that preserves model utility (in our work, we choose budget, such as 10% T. From there, one can compute the level of privacy achieved. Our experiments for various including = O, (Table 13 and 15) suggest that small amount of rewinding or noise performs well empirically.
suggest first choosing 0.01) and K within the computational
Theorem 3.1 applies to unlearning a batch of m data samples, but our algorithm also accommodates sequential unlearning requests. If, after unlearning m points, additional & unlearning requests arrive, we simply call the unlearning algorithm M on the new retained dataset of size m k. Notably, if the total number of unlearned data increases while and K stay constant, our unlearning guarantee worsens, which aligns with other results [23, 48, 12].
We can obtain faster convergence for Lojsik--ooasiewiizz (PL) functions, which are functions that satisfy the PL. inequality (6). Although PL. functions can be nonconvex, they have a continuous basin of global minima, enabling both empirical and population risk bounds.
Definition 3.3. [27] For some function f, suppose attains global minimum value f". Then f satisfies the PL inequality if for some μ > and all x.
[f(=)] ((f(())f')
(6)
Although practical algorithms typically minimize the empirical risk, the ultimate goal of learning is to minimize the population risk F, in order to determine how well the model will generalize on unseen test data. We leverage results from [29] that relate the on-average stability bounds of algorithms on PL. functions to their excess population risk.
Corollary 3.3. Suppose the conditions of Theorem 3.1 hold and in addition, for satisfies the PL condition (6) with parameter p.. Let F' represent the population risk, defined F()) 2f and let F represent its global optimal value. Then we have
2G²
B[F(0") F SLVdo +
(n - (n-m)
mu(n m) m))r L - - 11- " [(1- 2p
(fD (T-TT-K(f - -f:) + Gm(G + LT) u(n m))
+
n
where a is defined (3) and the expectation taken with respect to i.i.d. sampling of and the Gaussian noise added at the end of U.
Our performance guarantees demonstrate that more learning iterates T correspond to better perfor- mance upon unlearning for fixed a. For PI. functions, the utility converges faster with increasing T than for the general nonconvex case.
7

---

4 Experiments
See Appendix B for an in-depth review of experimental details, including hyperparameters and hardware (B.1), implementation details of MIAs (B. and baseline methods (B.1.2), computation time experiments (B.2), proximal point method (Algorithm 3) experiments (B.3), additional numerical results (B.5), and the GitHub repository.
4.1 Sctup
Experimental Framework. We test Algorithms I and 2 in novel setting where the unlearned dataset is not iid. to the training or test dataset. For all experiments, we train a binary classifier with the cross-entropy loss function over dataset that is naturally split among many different users. To test unlearning, we remove the data associated with a subset of the users (1%-2% of the data) and observe the impact the original classification task. Our framework better reflects unlearning in practice, where users may request the removal of their data but they do not each represent a class in the model. This stands in contrast to current experimental approaches that unlearn data from selected class [23, 20, 28). or randomly select samples uniformly from the dataset to unlearn [48, 37].
Datasets and Models. We consider two real- world datasets and neural network models with highly nonconvex loss functions. For small-scale experiments, we train multilayer perceptron (MLP) with 3 hidden layers to perform classification
the eICU dataset, a large multi-center intensive care unit (ICU) database consisting of tabular data on ICU admissions [36]. Each patient is linked with 1-24 hospital stays. We predict if the length of hospital stay of patient is longer or shorter than week using the intake variables of the Acute Physiology Age Chronic Health Evaluation (APACHE) predictive framework, including blood pressure, body temperature, and age. For unlearning, remove a random subset of patients and their corresponding data. For large-scale experiments, we consider a subset of the VGGFace2 dataset, which composed of approximately 9, 000 celebrities and their face images from the internet [5]. We apply the MAAD-Face annotations from [44] to label each celebrity as male female, and sample a class balanced dataset of 100 celebrities to form the Lacuna- 100 dataset as described in [20]. We train a ResNet-18 18 model to perform binary gender classification. For unlcarning, we remove random subset of the celebrities and their face images.
During the learning process, we train the model and save checkpoints every 10 epochs. Upon unlearning, each version of R2D, we compute the "rewind percent" as T x 100%, or the number of unlearning steps K as fraction of the number of original training steps T. Due to the computational demands of full-batch gradient descent, we implement our algorithms using mini-batch gradient descent with utilize
Implementation.
revert earlier checkpoints and train the new loss function. For
very large batch size (2048 for eICU and 512 for Lacuna- 100). For (e, -)nuneaagn, the bound derived in [3] to calibrate the noise for > 1, and we estimate the values L and G using sampling approaches outlined in Appendix B.1.
To empirically evaluate the unlcarned model, we apply membership inference attacks (MIA) to attempt to distinguish between unlearned data and data that has never been in the training dataset. A lower Area Under the Receiver Operating Characteristic Curve (AUC) of the membership attack model corresponds to less information retained in the model and more successful unlearning. We employ both the classic MIA [41], that only considers the output of the model after unlearning, and advanced attack tailored to the unlearning setting (MIA-U) [9], that compares the output of the original model and the unlearned model. These attacks are typically performed on i.i.d. datasets, but adapt them our setting by constructing an out-of-distribution (OOD) dataset representing data from users absent from the training data. For Lacuna- we construct an OOD dataset using an additional 100 users from the VGGFace2 database. For eICU, we construct the OOD dataset from data samples in the test set belonging to users not present in the training set.
Unlearning Metrics.
We also consider the performance (AUC) the retain set, unlearned set, and test set (denoted as Dretain. Dunlearns Drest) of both the original trained model and the model after unlearning (Table 2). A decrease in performance on Duntearn suggests the model is losing information about the data.
Baseline Methods. We compare against two other certified unlearning algorithms for nonconvex functions: Constrained Newton Step (CNS) [48], a black-box algorithm which involves a single Newton step within a constrained parameter set, and Hessian-Free Unlearning (HF) [37], a white- box algorithm which involves demanding pre-computation and storage of data influence vectors
8

---

o] Model Performannss on Phut
Classic MIA V5.
Madial Performazee on Padan
1300
50300
1.000
18
sis
Model Fecfommatee on Phat
0:00
1.4
Likermiennki Oepeu
2450
0.5
1.00
1.0
27%
Figure I: Privacy-tdlity-coplleeii tradeoff of R2D compared to other certified unlearning methods (Constrained Newton Step and Hessian-Free method) on the eICU dataset. In Figures 1a, If, and ig, we plot against the rewind percent, computed as 7 x 100%.
during training, allowing unlearning via simple vector addition later. Both methods also involve single Gaussian perturbation at the end to achieve (e, dunllerrnn, We do not implement the white- box algorithm from [12] because, as stated in their work, "the non-convex unlearning bound... is not tight enough to be applied in practice due its exponential dependence on various hyperparameters. For all baselines methods, we use the hyperparameters reported in the original papers that align with our settings. However, we note that certified unlearning algorithms can be highly sensitive to hyperparameter choices, so for a fair comparison we also consider flat noise amount of a = 0.01, following the precedent established [37, 48, 23]. Moreover, this allows us to compare against several state-of-the-arr baseline methods which do not have theoretical unlearning guarantees but can be evaluated empirically: Finetune, where the model is fine-tuned on the retained dataset, Fisher Forgetting [20], which selectively perturbs weights via the Fisher information matrix, and SCRUB [28]. Unlike the certified unlearning methods, these algorithms do not require any specific training procedure, apply them to the same original trained model used for R2D.
4.2 Results
In Figure compare R2D with varying and K to other certified unlearning algorithms on the eICU dataset. Figures la and 1b demonstrate that model performance (AUC) on Drest improves with more rewinding and larger e, which correspond to smaller as shown from the result derived in (3). Figure lb shows that R2D has a superior privacy-utility tradeoff, with better performance on Preat due a smaller noise requirement that scales more advantagcously with e, as shown in Figure le. In addition, for most values of e, R2D is able to defend more successfully against the membership attacks, demonstrated by lower MIA scores in Figure Ic and 1d. Finally, Figure Ig displays the performance of the model before and after unlearning on Duntearn. with the decrease in performance after unleariin indicating that the model is losing information about the samples.
We further compare R2D to certified and non-certified algorithms in Tables and 3, with the full numerical results available in Tables 12 and 14 in Appendix B.5. Table 2 displays the model AUC on Dretains D Dunlearn. and Dreet before and after unlearning, and Figure 2 plots these values over rewind percent. We note that there are different "original models" because the certified baseline methods (HF, CNS) require different training procedures. On both datasets, R2D displays a significantly greater performance drop on Panlearn compared to non-certified methods, while outperforming CNS on eICU and both HF and CNS on Lacuna- 1000. We observe that as expected, more rewinding decreases the utility on Duntearn (Figure 2) and reduces the success of the MIA (Figure 4 in the Appendix). Finally, Table 3 displays the results of both MIA methods. On the eICU dataset, R2D outperforms all other methods under the classic MIA and outperforms other certified methods under the MIA-U, and on the Llcuna-100 dataset, R2D is competitive under the classic MIA while outperforming all other methods under the MIA-U. Our results suggest that even with a small amount of perturbation, certified unlearning methods tend to defend against MIAs more successfully than non-certified

---

Table 2: Model performance (AUC) before and after unlearning. "Original Models" refers the trained models before unlearning, and all other rows are unlearned models, We consider the relative decrease of the AUC on Duntearn as an unlearning metric. The non-certified methods are applied to the R2D original model. We bold the two best results for each dataset.
eICU
Lacuna- 100
Algorithm
D Peetaia
D Punicarn
Dieat
Dretain
D unllearn
Diest
Original Models (no noise)
Hessian-Free
0.7490
0.7614
0.7472
0.9851
0.9746
0.9737
Constrained Newton Step
0.7628
0.7860
0.7602
0.9983
0.9956
0.9856
R2D
0.7337
0.7451
0.7322
0.9989
0.9993
0,9844
Certified Methods
Pessian-Freee Constrained Newton Step
0.7476
0.7587 (480027)
0.7465
0.9757
0.9555 (-0.1191)
0.9652
0.7622
0.7848 (-00012)
0.7601
0.9977
0.9949 (-0.0007)
0.9847
R2D 7-10%
0.7335
0.7444
(-00007)
0.7327
0.9606
0.9238 (-0.7755)
0.9478
R2D 36-37%
0.7334
0.7441
(000010)
0.7327
0,9683
0.9269 (0.0724)
0,9525
R2D 74%
0.7333
0.7439
(-0.0012)
0.7326
0.9712
0.8998 (-0.9995)
0,9534
Noiseless Retrain (R2D 100%)
0.7335
0.7447 (-0.0004)
0.7321
1.0000
0.9460 (-0.0533)
0.9840
Non-certified Methods
Finetune
0.7352
0.7463 (40.0012)
0.7337
0.9997
0.9975
(-0.0018)
0,9854
Fisher Forgetting
0.7310
0.7482 (40.0031)
0.7302
0.9982
0.9986 (-0:0077)
0.9831
SCRUB
0.7336
0.7450
(-00000))
0.7322
0.9989
0.9999 (+0.006)
0.9845
methods. Finally, Tables and in Appendix B.2 demonstrate that R2D is more computationally efficient than HF and CNS.
Conclusion
We propose R2D, the first black-box, first-order certified-unlearning algorithm for nonconvex func- tions, addressing theoretical and practical limitations of prior work. Our algorithm outperforms existing certified and non-certified methods in storage, computation, accuracy, and unlearning.
Table 3: Membership inference attack success (AUC). We bold the two best results for each dataset and attack method.
Model Performance eICU
eICU
Lacuna-100 100
0778
0m/5
AlI
Algorithm
Classic MIA
MIA-U
Classic MIA
MIA-U
Certified
(n 0.01)
Reaiind Fercver
HF CNS
0.5078
0.5108
0.4950
0.8460
Miodel Performance Lacuna-10h 1001
0.5145
0.5144
0.6020
0,8480
R2D 7-10%
0.5047
0.5001
0.5625
0.7721
R2D 36-37%
0.5046
0.5001
0.5197
0.6779
1455
R2D 74%
0.5044
0.4997
0.5333
0.7206
Tha ALC Pia.
Noiseless Retrain
0.5060
0.5064
0.4974
0.8101
Votus AGA
Non-certified
27%
45%
107%
Finetune
0.5063
0.5066
0.6013
0.8497
Fisher Forgetting
0.5114
0.5102
0.5814
0.8735
Figure 2: Model performance rewinding for 0.01.
SCRUB
0.5060
0.5056
0.6179
0.8586
10

---

References
[1] Martin Abadi et al. "Deep Learning with Differential Privacy". In: Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security. CCS '16. Vienna, Austria, 2016, pp. 308-318.
[2] Mistral AI and Daniel Furman, Mistrul-7B-IInttrutt-0.... https: / htt////gggnggga...eem/ co/ dfurman/Mistral. 7B- IBB-InsrructtO Instruction-tuned 7B model (Apache 2.0 license). 2024.
[3] Borja Balle and Yu-Xiang Wang. "Improving the Gaussian Mechanism for Differential Privacy: Analytical Calibration and Optimal Denoising". In: Proceedings of the 35th International Con- ference on Machine Learning. Ed. by Jennifer Dy and Andreas Krause. Vol. 80. Proceedings of Machine Learning Research. PMLR, July 2018, pp. 394-403.
[4] Nhung Bui et al. On Newton's 's Method to Unlearn Neural Networks. 2024. arXiv: 2406, 14507
[cs.LG] LG]
[5] Qiong Cao et al. "VGGFace2: A dataset for recognising faces across pose and age". In: International Conference on Automatic Face and Gesture Recognition. 2018.
[6] Yinzhi Cao and Junfeng Yang. "Towards Making Systems Forget with Machine Unlearning".
In: 2015 IEEE Symposium on Security and Privacy. 2015, pp. 463-480.
[7] Zachary Charles and Dimitris Papailiopoulos. "Stability and Generalization of Learning Algo- rithms that Converge to Global Optima". In: Proceedings of the 35th International Conference Machine Learning. Ed. by Jennifer Dy and Andreas Krause. Vol. 80. Proceedings of Machine Learning Research. PMLR, July 2018, pp. 745-754.
[8] Kamalika Chaudhuri, Claire Monteleoni, and Anand D. Sarwate. "Differentially Private Empirical Risk Minimization".
In: Journal of Machine Learning Research 12.29 (2011),
pp. 1069-1109
[9] Min Chen et al. "When Machine Unlearning Jeopardizes Privacy".. In: Proceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security. CCS '21. Virtual Event, Republic of Korea: Association for Computing Machinery, 2021, pp. 896-911. ISBN: 9781 7781450384544.
[10] Eli Chien, Chao Pan, and Olgica Milenkovie. "Certified Graph Unlearning". In: NeurlPS 2022 Workshop: New Frontiers in Graph Learning. 2022.
[11] Eli Chien et al. "Certified Machine Unlearning via Noisy Stochastic Gradient Descent". In: The Tiirty-eighth Annual Conference on Neural Information Processing Systems. 2024.
[12] Eli Chien et al. "Langevin Unlearning.. In: Privacy Regulation and Protection in Machine
Learning. 2024.
[13] Dmitriy Drusvyatskiy. "The proximal point method revisited". In: arXiv: arXiv,
Dec. 2017.
[14] Cynthia Dwork and Aaron Roth. "The Algorithmic Foundations of Differential Privacy". In: Found. Trends Theor. Comput. Sci. 9.3-4 (Aug. 2014), pp. 211-407. ISSN: 1551-305X.
[15] Cynthia Dwork et "Calibrating Noise Sensitivity Private Data Analysis". In: Theory of Cryptography. Ed. by Shai Halevi and Tal Rabin. Berlin, Heidelberg: Springer Berlin Heidelberg, 2006, pp. 265-284. ISBN: 978-3-540-32732-55.
[16] Andre Elisseeff, Theodoros Evgeniou, and Massimiliano Pontil. "Stability Randomized Learning Algorithms". In: Journal of Machine Learning Research 6.3 (2005), pp. 55-79,
[17] Yann Fraboni et al. "SIFU: Sequential Informed Federated Unlearning for Efficient and Prov- able Client Unlearning in Federated Optimization", " In: Proceedings of The 27th International Conference on Artificial Intelligence and Statistics. Ed. by Sanjoy Dasgupta, Stephan Mandt, and Yingzhen Li. Vol. 238. Proceedings of Machine Learning Research. PMLR, May 2024,
pp. 3457-3465.
[18) Antonio Ginart et al. "Making Al Forget You: Data Deletion in Machine Learning". In: Advances in Neural Information Processing Systems. Ed. by H. Wallach et al. Vol. 32. Curran Associates, Inc., 2019.
[19] Shashwat Goel, Ameya Prabhu, and Ponnurangam Kumaraguru. "Evaluating Inexact Unlearn- ing Requires Revisiting Forgetting". In: CoRR abs/2201 .06640 (2022). arXiv: 2201 06640.
[20] Aditya Golatkar, Alessandro Achille, and Stefano Soatto. "Eternal Sunshine of the Spotless Net: Selective Forgetting in Deep Networks". In: IEEF/CVE Conference on Computer Vision
and Pattern Recognition (CVPR). June 2020.

---

[21] Aditya Golatkar, Alessandro Achille, and Stefano Soatto. "Forgetting Outside the Box: Scrub- bing Deep Networks of Information Accessible from Input-Output Observations". In: CoRR abs/2003.02990 .02960 (2020). arXiv: 2003. 2003.02960.
[22] Laura Graves, Vineel Nagisetty, and Vijay Ganesh. "Amnesiac Machine Learning". en. In: Proceedings of the AAAI Conference on Artificial Intelligence 35.13 (May 2021), pp. 11516-
11524. ISSN: 2374-3468.
[23] Chuan Guo et al. "Certified Data Removal from Machine Learning Models". In: Proceedings of the 37th International Conference on Machine Learning. Ed. by Hal Daumé III and Aarti Singh. Vol. 119. Proceedings of Machine Learning Research. PMLR, Aug. 2020, pp. 3832-3842.
[24] Edward J. Hu et al. "LoRA: Low-Rank Adaptation of Large Language Models". In: CoRR abs/2106. 006.99655 (2021). arXiv: 2106.09685. URL: https: /wwpvv.xivvv...////////a.//..av. org/abs/ /2g/0 09685. [25] Zachary Izzo al. "Approximate Data Deletion from Machine Learning Models". In: Pro- ceedings of The 24th International Conference on Artificial Intelligence and Statistics. Ed. by Arindam Banerjee and Kenji Fukumizu. Vol. 130. Proceedings of Machine Learning Research. PMLR, 2021, pp. 2008-2016.
[26] Joel Jang et al. "Knowledge Unlearning for Mitigating Privacy Risks in Language Models". In: Proceedings of the 61 Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Pupers). Ed. by Anna Rogers, Jordan Boyd-Graber, and Naoaki Okazaki. Toronto, Canada: Association for Computational Linguistics, July 2023, pp. 14389-14408.
[27] Hamed Karimi, Julie Nutini, and Mark Schmidt. "Linear Convergence of Gradient and Proximal-Gradiiet Methods Under the Polyak-E.ojasievice Condition". In: Machine Learn- ing and Knowledge Discovery in Databases. Ed. by Paolo Frasconi et al. Cham: Springer International Publishing, 2016. pp. 795-811.
[28] Meghdad Kurmanji et al. "Towards Unbounded Machine Unlearning". In: Thirty-seventh Conference on Neural Information Processing Systems. 2023.
[29]
Yunwen Lei and Yiming Ying. "Sharper Generalization Bounds for Learning with Gradient- dominated Objective Functions". In: International Conference on Learning Representations.
2021.
[30] Chaoyue Liu, Libin Zhu, and Mikhail Belkin. "Loss landscapes and optimization in over- parameterized non-linear systems and neural networks". In: Applied and Computational Harmonic Analysis 59 (2022). Special Issue on Harmonic Analysis and Machine Learning.
pp. 85-116. ISSN: 1063-5203.
[31] Jiaqi Liu et al. "Certified Minimax Unlearning with Generalization Rates and Deletion Capac- ity". In: Thirty-seventh Conference on Neural Information Processing Systems. 2023. [32] Zheyuan Liu et al. "Breaking the Trilemma of Privacy, Utility, and Efficiency via Controllable Machine Unlearning". In: Proceedings of the ACM on Web Conference 2024. WWW '24. Singapore, Singapore: Association for Computing Machinery, 2024, pp. 1260-1271.
[33] B. Martinet. "Brève communication. Régularisation d' d'iééuuations variationnelles par approxi- mations successives". fr. In: Revue françuise d' informatique et de recherche opérationnelle. Série rouge 4.R3 (1970), pp. 154-158. ISSN: 0373-8000, 2777-3515.
[34] Seth Neel, Aaron Roth, and Saeed Sharifi-Malvajendd "Desceentto-Deeetee Gradient-Based Methods for Machine Unlearning". In: Proceedings of the 32nd International Conference on Algorithmic Learning Theory. Ed. by Vitaly Feldman, Katrina Ligett, and Sivan Sabato. Vol. 132. Proceedings of Machine Learning Research. PMLR, 2021, pp. 931-962.
[35] Thanh Tam Nguyen et al. "A survey of machine unlearning". In: atXiv:2209.02299, arXiv,
Sept. 2024.
[36] Tom J. Pollard et al. "The eICU Collaborative Research Database, a freely available multi- center database for critical care research". en. In: Scientific Data 5.1 (Sept. 2018), p. 180178. ISSN: 2052-4463.
[37] Xinbao Qiao et al. "Hessian-Free Online Certified Unlearning". In: The Thirteenth Interna- tional Conference on Learning Representations. 2025.
[38] Ayush Sekhari et al. "Remember what you want to forget: algorithms for machine unlearning".
In: Proceedings of the 35th International Conference on Neural Information Processing Systems. NIPS 211 2021.
[39] Shai Shalev-Shward et al. "Stochastic Convex Optimization". In: Annual Conference Compu- tational Learning Theory. 2009.
12

---

[40] Gil I. Shamir, Dong Lin, and Lorenzo Coviello. "Smooth activations and reproducibility in deep networks". In: CoRR abs/2010.09931 (2020). arXiv: 2010. 09931.
[41] Reza Shokri et al. "Membership Inference Attacks Against Machine Learning Models". In:
2017 IEEE Symposium on Security and Privacy (SP). 2017, pp. 3-18.
[42] Vinith Menon Suriyakumar and Ashia Camage Wilson. "Algorithms that Approximate Data Removal: New Results and Limitations". In: Advances in Neural Information Processing
Systems. Ed. by Alice H. Oh al. 2022.
[43] Rohan Taori et al. Stanford Alpuca: An fowiown LLaMA Model. https / github. com watmm/tttsslaaassaeeeee stabfortaaoordd_.o alpaca. Stanford Center for Research on Foundation Models (CRFM). 2023.
[44] Philipp Terhörst et al. "MAAD-Face: Massively Annotated Attribute Dataset for Face Images". In: CoRR abs/2012.01030 (2020). arXiv: 01000..
[45] Enayat Ullah al. "Machine Unlearning via Algorithmic Stability", In: CoRR abs/2102.13179 (2021). arXiv: 13179.
[46] Xi Wu et al. "Bolt-on Differential Privacy for Scalable Stochastic Gradient Descent-base Analytics". In: Proceedings of the 2017 ACM International Conference on Management of Data. SIGMOD '17 Chicago, Illinois, USA, 2017, pp. 1307-1322.
[47] Heng Xu et al. "Machine Unlearning: A Survey". In: ACM Comput. Surv. 56.1 (Aug. 2023).
ISSN: 0360-0300.
[48] Binchi Zhang et al. "Towards Certified Unlearning for Deep Neural Networks". In: Forty-first International Conference on Machine Learning. 2024.
[49] Jiaqi Zhang et al. "Efficient Private ERM for Smooth Objectives". In: Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence, IJCAI-17. 2017,
pp. 3922-3928.
13

---

A Proofs
The proof of Theorem 3.1 is provided in Appendix A.2. The proof of Corollary 3.2 is in Appendix A.2.2.
A.1 Proof of Lemma 2.1
Proof. We have the following lemma from [13].
Lemma A.1. [13] If f(0) is continuously difserentiable with I--Liscchttz gradient, -5(0) 1 is convex.
Now we define 0 as the solution to the proximal problem follows
proz -,,00-110(0+1111 arg min( f(z) - || 0t+1 [|
1
2nj
which is well-defined due Lemma A. and the fact that r < t. leading to strong convexity. Then the gradient of the objective function is zero at 0 and thus
vf(0") (0" 0c+1) 0,
0" = 0c11 + + ((0).
A.2 Proof of Theorem 3.1
Like prior work in differential privacy and machine unlearning, our work hinges on the Gaussian mechanism for differential privacy, which ensures (c, (c.-)=indistinuuishalllty for normal random variables with the same variance.
Theorem A.2. [14] Let X N(H, LaIaa and ~ NN', o Suppose || plllas A. Then for any 8 O, X and Y are (e, oy..iiddssiingusshabll if
A
V 22/22oggi 2log(1.25/8).
Therefore, to prove Theorem 3.1, we need to bound the distance between the output of the unlearning algorithm and the learning algorithm. We can then add sufficient amount of noise, scaled by this distance, to achieve (e, unlearning.
Proof. Let Z be dataset of data points we would like unlearn, where n. Let represent the original full dataset and D' D, Without loss of generality, define
(D(0)
(0),
n
1 n-m m
JD (0)
(2,
n
m
1=1
such that we have
fo
fD (8)
+
Σ (0),
n
n
i=n-m++
n fD
(Jb(0)
Σ
(0)
Let {0.]T represent the gradient descent iterates of the learning algorithm on fo. starting from do-
and let (0)) be the iterates of the learning algorithm on for starting from the same fg. Then we have
0g = 0,:
0, 0,-1- 1--1-1V/0((0111
(8)
8, 0
(9)
14

---

Let {
It=o represent the gradient descent iterates of the unlearning algorithm starting at 06 = -K- K. Finally, let 0 = 0% + denote the iterate with Gaussian noise added.
We first bound the distance between Og and 0f as follows.
Lemma A.3. Let {0.]7 {0 be defined as in (7). Then
2Gm
[[1 + ILn
|0: - 0P.-6111- -
n )0 1).
Ln
Proof. We have
V (0) = n
(V
1 (0))
m
i= m+1
8% 0 n m
v fz (o
Σ
(f,
n m
So we have for A, 02 0/,
A - A VDD((0 + (VID(0,))
Σ
(o,((0)))),
t=n
1
= --1 (V
VDD(O(-1)
V fz, (0,-
i=n- m+1
=A VV/((0111) ' m
(SD(O(-1) (V (/D(0,-1))
m
1
1] 11 17
f ff,,((/111) (0%-1),
=A +
(0 + n (ViD(((_1) vfD(0(-1)) -1
V (0%-1).
n n- m
n m
i=n-m+1
After taking the absolute value of each side, we obtain by the triangle inequality
n /V/((t-i)llt n m (VD(@(-)-V55(0 ||A,|| < || m
Σ
V 11-1
n m
i=n-m+1
Since the gradient on each data sample is bounded by G, we have
1
|a/|| $ ||A-- + G 17
[VD(((]1)) (f
G,
m
n m
mmn-m++1
21,mm
||l||| S ||A,-1l| n [Vo((')1) V.
n1 m
By Lipschitz smoothness of the gradient, we have
||| < || +
1110 - 02-111 n n
27/mm
n
nLn n m m Since we have ||oo|| 0, evaluating this recursive relationship yields for >
2nGm
| < ||A,1
2m
t-1
(1+ nLn 72
|| < n m
m
1=0
2mGm (1 + aLn )
1
||//| S n- m
nLa
n mm
15

---

(1 +
n-m nIa )
||t|| 2Gm
Ln
This bound takes advantage of the difference between JDD and JDD as it decreases with large n, but also grows exponentially with the number of iterates.
Lemma A.. Let (0 It=0 represent the gradient descent iterates on for starting at 8 Or-K such that
0 = - -
Then
110- 0 1 1 K 0x1(x nT)k
Proof. Let A UT-K+t 0¹¹ such that A 1104- 8''l and we bound it as follows
A = -r- - 0g = 07 K K+H-1 - //V. (0T-Kkttt - 0' 1 + v, ID 10
= - NV
|لإ/|| S || || //IV (00- - 100--V//100 (0""")))
By Lipschitz smoothness
|A S +
0ل-111
|| S (1+ 11+14)144<111 S 116611(1 [1 +
Returning to the algorithm, suppose the learning algorithm has T iterations and we backtrack for K iterations. Then the difference between the output of the learning algorithm (without noise) fo and the unlearning algorithm would be
2mG 10/ 0% < | + nT.**
nLn yr- y 1)(1 + T,T.)
((1
Ln
n m
where the bound on the right hand side decreases monotonically as K increases from 0 to T' as shown by the following. Let
M(K) ((1 nLn TT- 1)((1 mL)*
n1
Then the derivative is
W(K) = (1 ( [((1 + Tm -T-K log(1 + tn)) - (1 + nn -r-
log(1 + nLn }},
m7
n m
n m
observe that (KK < 0 for K [0. T]. Therefore h(K) is decreasing. Therefore by Theorem A.2, to achieve e, 6-unlearning, we need to set the value of as follows
|10 0% 11 2og (1.25/5) 2mG I(K)))()))))))))) 2l..log1..2//// o
Lne
Now we prove the utility guarantee. For nonconvex smooth functions, we know by standard analysis that for the gradient descent iterates 0", we have
K
K
?
V (8") <
for (6)) fD.(0"))) = for (6%) - (ork))
2
Now we consider the progress the iterates 0, on for (0). By Lipschitz smoothness, we have
10.4))) s (0.) (Vfo (f 4 II
16

---

We have
n
VfD(0,)= = n m
Vf (01) +
Σ (0,
n
m+1
f0+(0)+1) (0)()))) - 7 (VVf (0)) n - m (f)) + (0))
i--m++
Lnp n - m fD +
1 Σ
+ 2
(0)(1
n i=
(0))
n - m
V V (0))
VV (o.
1 Σ
n
i=--++
+
Lnp
n m
V (ti) + 1 Σ
(f)(
2
i=n-
n m
V f (0:)1 V (0.),
Σ (la(
n
i=--m+1
+
+Ln21
n m
V frr (0:)1 + Ln7'1 1
(0.1
-=---+1
(0D((0))
n - m
Ln(n= m)
(1/ (0.), _ Σ
(0))
n
i=n-m+1
+ Lnj² 1
Σ i=n-m-+
(0)1l
Ln(n- m | for (0,)11 + 1)
G'm
mG Lnj"
1 n
(1
n
n
n1
Let the step size 1) be bounded such that 17 2(n then we have
7(1 m)
G Lm
fD+(0)+)) S (0))
2n
n
n
Rearrange the terms to get
nnnn m)
( (0+41))) + G2mm Lm
2n
n
n
Sum from t 0 T K 1
711 - m)
T- K-
G Lni
/V/ < (0o)
K 1)(
2n
n
n
T-K-1
2n
K- 1){ -1)(" n03mm
LnpGm
IV (0.)11 v in - m)
(Ox) - (0r- + -T- -
-
n
n
T-K-1
Σ
fI (0.)1 < (n m)
2n
(80) fo (0r-k)) +T K - 1)( 2G2m m
2LnGm
m
n m
t=
From standard analysis of gradient descent on nonconvex functions, we know
V (ox) < for -
K
/ (01))1 v 1 - (0%) - (0(00)))
1)
17

---

Summing the equations yields
V (0,)112 Σ
V for (0
1=0
2n
(fD:(16) - (0) -0r-K)) +T (T K --11 -1]( 2G²m 2LrGmm
$
+ (Srr (fDx(0%) (60)
SD (0%)
11( - m)
m
m
2n
2G 2LmGm
17(n m) (frr (fDr(00) - ffx (0%) (T K 1){
n2 m
π m
We can expand B[Il V fD (0") as follows
\ (12 = / /D/ (0
= f (6") |1² +0²
So we have
K-1
sa² + 2n(ff: - fr.
[ +
|| [00
Tıj(n m)
T K 222
2LmGmm
T
n m
n m
A.2.1 Proof of Corollary 3.3
To prove Corollary 3.3, we first need to obtain empirical risk bounds for PL. functions. Corollary A.5 states that the empirical risk converges linearly with both T and K.
Corollary A.S. Suppose the conditions of Theorem 3.1 hold and in addition, fD satisfies the PL condition with parameter p. Let f represent the global optimal value of JD. Then
BISD (0")) S LVdo+(1-np)) Pm + LajGm
1--KK111 (1-m1)* K (0o)-OO +(1 mu(n - m) TT
-m)
p(n mm) m)
where a is defined in (3) and the expectation is taken with respect to the Gaussian noise added at the end of U.
Proof. As before, we first consider the gradient descent iterates on SD. For ptPPI and smooth functions, we know that for the iterates 0", we have [27]
fo (ox) fo. s (1 mH) (fo: f5.).
Now we track the progress of the iterates Og on fD. By Lipschitz smoothness and the above analysis, we have
(0 - fo.(()) S (V (n.0)).nVVoool (..())) + I (
ID (0)())))) (0. -1 (1 Ln(nn m) || ID (0.) +1 G2m Let the step size 17 be bounded such that 1) S 2(n 2(n-m)r. then we have
Lyj" MG
n
n
(0++)))) - -'D (0.) 1nn m)
G Lm
2n
n
n
By the PL inequality, we have
fT - Jo (0t) s nu(n (m) m)
(fo) - -(b-) G Lm
n
mu(n m)
(fD fb.) mFFm
+ L
(0 - fft- S (1
7
n
n
18

---

We evaluate this recursive relationship to obtain
fD:(00+1)- - (1 nu(n m) y (fx((0)) (nG" Gm)
mu(n m)
1=0
[D-(0++1)-55 S (1 nu(n - m) ye+ y (J0) n 1
Mu(( m)
may Gm)
n
n
1=0
$ (11 nu(n n mm) yet ( (06) - ) + [n m + Tap
-
Y1
n
n
n/ m))
(0++1) - -for S (1 mu(nn m) p+| (On) - -bb:) + G2m + LnGmm
1
1(n - -m)
(o--k kk) - -fb- S (1 nu(n m) yT (fD (06) -fo) G2m + LaGmm
f0'()%) fir fo for--kK
pln m)
(0k) - -r < (1 mji(n 10mmm m) yT- K (1 - mnl1 K (fr - 1 + (1 - nu)) k G + LN/Gm
n
u m) (10)
By Lipschitz smoothness, we have
mu(n m) (1-K(1-11--0 (ff:(0)) - -
for fo") - ft (fD - fo (0k) + (1
n
+ (1 - n1)) G2m + LInGm plnn -m)
<1100" - 8% + (1 quin m) T- k<( (for(()))))) - )
n + (1 - ) G + LnGmm
(11)
1ln m)
-|lE||| + (1 mu(n - m) , 1-(((-1 (1-1-1)) n1)* K (fox(fo) f
+ (1 nu) K G2m + LIGmm
p(n m)
If we take the expectation on both sides with respect to the noise added at the end of the algorithm U, we have
Elʃo (0") S IVVdo+(1 mi(n - m) m (1 (1-11)* ( (fDx (00)- +1 - ))) Gmm + LaGmm
u(n m)
Now can prove Corollary 3.3. Bounds on generalization can be derived using seminal results in algorithmic stability [16]. Prior work on the generalization ability of unlearning algorithms focus on the strongly convex case [38, 37, 31, 45], which feature excess risk bounds for the empirical risk minimizer when the loss is strongly convex [39]. By considering PL functions, we are, to the best of our knowledge, the first to consider unlearning generalization algorithms on PL objective functions can at best satisfy pointwise [7] or on-average [29] stability. The following result derives from Theorem of [29]. We utilize the fact that for w" E arg minsge F(0). we have [ < Effo (w=)] F F(w") = F*. and we also slightly modify the result to include the stronger bounded gradient assumption used our work.
nonconvex setting. In contrast,
Lemma A.6. [29] For F defined F(0)= (f-2((2(0))
and 0 as the output of an algorithm dependent on D', we have
2G2
((F FF] < (n m)u
Elf ffr].
2μ
19

---

We obtain the result by substituting in (10). The population risk can be decomposed to three terms: an O(1/n) term representing the difference with empirical risk, an O(vio) term representing the Gaussian noise, and term representing the convergence of the underlying optimization framework. The first two terms are roughly equivalent across most works because they follow from fundamental principles.
A.2.2 Proof of Corollary 3.2
We want to determine the value of K required to maintain a privacy level e for chosen level of noise a. From (3) we have
h(K)2mG /2lg)mmm/llog(222////
oLn
Although this does not have an exact explicit solution for K K()), we can bound (K()) as follows
h(K) S ((1 + nLn ) 1)(1+
nLn K (1 + nLn )
(1+ pn K
m
n2
Then we have
2mG v 221og(1.25/0)
((1 nLn )T (1 + nLn )K)
c
oLn
(1 + nLn )k S (1+ + nLn
Lnc
2mG / (o.2(1)2//))
log (1 + nLn yr
Lnc
n-m
2mG 2 (og(1.25/8))
log(1
g/a
We therefore obtain close upper bound on (e) for fixed o. practice we can choose K equal to this bound to ensure the privacy guarantee is achieved. We show in Figure 3 that this bound is close tight for 0 < S and real-world parameters.
Comparison of Kic) and Bound on the eICU Dataset
Murrencally computed inverss fashyriccal bound
M40.446
3018.904
3618.992
0.2
0.6
1.0
Figure 3: Comparison of ((4) and analytically derived bound using real-world parameters from the
eICU dataset.
B Experiments
In Appendix B.1, we review the details of our experimental implementations, including the member- ship inference attacks (Appendix I.I, and baseline methods (Appendix 1.2).. In Appendix B.2, we provide computation time experiments. In Appendix B.5, we present the full versions of Tables 2 and 3, including I-sigma error bars for the MIA results, and tables for the noiseless version of the certified unlearning algorithms. We review the impact of rewinding the attack success in Figure 4.
20

---

B.1 Implementation Details
Code is open- open-sourced at the following GitHub link: https://github. com/ com/siqiaom///2.
Datasets, We consider two datasets: the eICU Collaborative Database, large multi-center ICU database [36], and the Lacuna- 100 dataset, subset of the VGGFace2 [5] dataset, which construct using the MAAD-Face annotations [44) and following the procedure in [20].
The eICU dataset can be obtained after following the instructions at https://eicus crd. mit. http/ggtttingstatte//aaasos access/. We combine the patient, apacheApsVar, apachePredVar, and apachePatientReaule tables to form our dataset, predicting whether the hospital length of stay is longer or shorter than a week with the following predictive variables: ["age", "intubated", "vent", "dialysis", "eyes", "motor", "verbal", "meds", "urine", "wbc", "temperature", "respiratoryrate,, "sodium", "heartrate", "meanbp", "ph", "hematocrit", "creatinine", "albumin", "pao2", "pco2", "bun", "glucose", "bilirubin", "fio2", "gender", "admitsource" "admitdiagnosis", "thrombolytics" "aids", "hepaticfailure" "lymphoma", "metastaticcancer"" "leukemia", "Immunosuppression"" "cirrhosis", "diabetes"]
Code for preprocessing the Lacuna- 100 dataset is available at the GitHub repository linked above. The MAAD-Face anmotations are available at https: http:////gihht..oooopprrrrr///// wwt//pterhoorr//MMD--- the VGG-Face dataset is available at https wwwtt//wwwwww...oooo//ooooo..... ox ac. w./.k/////vvgve dttp///ta//v.aee////
and
Model architecture. We perform experiments on multilayer perceptron with three hidden layers and ResNet- 18 deep neural network. Because our analysis requires smooth functions, we replace all ReLU activations with SmeLU activations [40]. We also do not use Batch Normalization layers since we want to train with constant step size. These steps may affect model performance but improve the soundness of our experiments by allowing estimation of the smoothness constant T..
Gradient bound estimation. To estimate the gradient bound G, we compute the norm of each mini-batch gradient each step of the training process, and take the maximum of these values the estimate.
Lipschitz constant estimation. To estimate the Lipschitz constant L, perturb the model weights after training by Gaussian noise with o = 0.01, and we estimate the Lipschitz constant by computing
|00 02ll [V)()) v ((2))
We sample 100 perturbed weight samples and take the maximum of all the estimates i to be our Lipschitz constant.
Table 4: R2D Experiment parameters for the eICU and Lacuna- 100 datasets.
Experiment Parameter
eICU and MLP
Lacuna- 100 and ResNet-18
Size of training dataset
94449
32000
Number of users
119282
100
Percent data unlearned
1%
2%
Number of model parameters d
136386
11160258
Batch size
2048
512
L
0,2065
0.5946
7)
0.01
0.01
Number of training epochs
78
270
Model selection. To simulate real-world practices, we perform model selection during the initial training on the full dataset by training until the validation loss converges, and then selecting the model parameters with the lowest validation loss. We treat the selected iteration as the final training iterate.
Unlearning metrics. Many prior works solely use the error on the unlearned dataset as an unlearning metric, theorizing that the model should perform poorly data it has never seen before. However, this is questionable in our context. For example, for Lacuna- 1000 unlearning a user's facial data does not preclude the model from correctly classifying their gender later, especially if the user's 's photos
21

---

are clear and easily identifiable. Moreover, since the unlearned data contains small subset of the users in the training data, is also likely to have lower variance. As a result, the unlearned model may even perform better on the unlearned data than on the training data, which is shown to be true for the eICU dataset. We therefore consider the performance on the unlearned data before and after unlearning (as shown in Figure Ig).
Hardware. All experiments were run using PyTorch 2.5.1 and CUDA 12.4, either on an Intel(R) Xeon(R) Silver 4214 CPU (2.20GHz) with an NVIDIA GeForce RTX 2080 (12 GB) or on an Intel(R) Xeo Silver 4208 CPU (2.10GHz) with an NVIDIA RTX A6000 GPU (48 GB). Almost all experiments require less than 8 GB of GPU VRAM, except for running the HF algorithm on the Lacuna- 100 dataset, which requires at least 29 GB of GPU VRAM to implement the scaled-down version.
Additional details. We use the same Gaussian noise vector for unlearned R2D under the same seed, rescaled to different standard deviations. We found that using unique noise for every hyperparam- eter combination resulted in similar but noisier trends. When initialized with the same seed, the torch. randn method outputs the same noise vector rescaled by the standard deviation. We use a different seed for the original model perturbations.
B.1.1 Membership Inference Attacks
Implementation. We conduct MIAs to assess if information about the unlearned data is retained in the model weights and reflected in the model outputs. Prior works typically perform the attack comparing the unlearned dataset and the test dataset, the latter of which represents data previously unseen by the model. However, in our setting, the model may perform well on users present in both the training data and the test data, while performing poorly on the users that are unlearned. It is therefore more appropriate to conduct the membership inference attack on out- out-of-distribution (OOD) data that contains data from users absent from the training data. For the Lacuna- 100 dataset, which has fewer users and many samples per user, we construct OOD dataset using an additional 100 users from the VGGFace2 database. For the eICU dataset, which has many users and a few samples per user, we construct the OOD dataset from data from the test set belonging to users not present in the training set.
We perform two different types of MIAs: the classic MIA approach based on [41], and an advanced attack tailored to the unlearning setting based on [9] (MIA-U). For both problem settings, we combine a subsample of the constructed OOD set with the unlearned set to form a 50-50 balanced training set for the attack model. We train a logistic regression model to perform binary classification, and we measure the success of the MIA by the attack model AUC on the data samples, computed via k-fold cross-validation (A: = 5) repeated 10 times. For the classic MIA, we also repeat undersampling 100 times to stabilize the performance. We provide error bars for the MIA results in Appendix B.S.
The classic MIA considers the output of the unlearned model on the data. For the eICU setting, we consider the loss on the data, and for Lacuna- 100, we consider the loss and logits on the data. The MIA-U leverages both the outputs of the unlearned and the original model, computing either a difference or concatenation of the two posteriors to pass to the attack model. We found that using the Euclidean distance was most effective at preventing overfitting and improving the performance of the attack, which aligns with the observations of [9]. To study the effects of the MIA-U for certified unlearning, we add noise to both the original model and unlearned model before performing the attack. Both [48] and [37] address a weaker yet technically equivalent definition of certified unlearning, introduced in [38], that only considers indistinguishability with respect to the output of the unlearning algorithms, with or without certain data samples, as opposed to the definition used in our work, which considers indistinguisaabiity with respect to the learning algorithm and the unlcarning algorithm. As result, neither [48] nor [37] require adding noise during the initial learning process, which may lead to a more successful MIA. However, their theoretical results naturally extend to the strong definition used in our paper, so for a fair comparison, we add noise to the original models of the other certified unlearning algorithms. Despite this, our algorithm still outperforms other certified unlearning algorithms in defending against the attacks.
Additional Discussion of MIAs. Although MIAs are a standard tool for testing user privacy and unlearning, we observe that they are an imperfect metric. MIAs are highly sensitive to distributional differences due to the non-uniform sampling of the unlearned data, and this sensitivity is stronger when the model performs well. This may explain why the MIA performs well even for the fully
22

---

retrained model, but is less successful on any of the certified methods that require adding uniform noise. It also explains why the attacks are weaker on the eICU dataset than on the Lacuna-100 100 dataset, since the model on the former dataset achieves a lower accuracy than on the latter.
On the flip side, MIAs can also react to distributional differences with deceptively good performance. For example, for very large a, the perturbed model may perform poorly by classifying all data in a single class. If the class distribution in the unlearned dataset different from the class distribution in the non-training dataset, the MIA may succeed by simply identifying the majority class in the unlearned dataset. To counter this effect, we ensure that the OOD dataset used for MIA and the unlearned dataset have the same class distribution. This nonlinear relationship is captured in the Classic MIA plot in Figure Ic, which shows that the Attack AUC is highest for very large or very small Ø.
Ultimately, results suggest that some caution is required when using MIAs evaluate unlearning, especially in the real world where models may not be extremely well-performing or data may not be ii.d. We find that the MIAs are generally less successful in our non-i.idd setting compared the standard settings of other papers. A future direction of this research is developing a specialized MIA for the OOD setting presented in this paper.
B.1.2 Baseline Methods
To implement the certified baseline methods, we estimated values of L and G when applicable, and we choose the step size and batch size so that the learning algorithms are sufficiently converged for our problems. For other parameters, such minimum Hessian eigenvalue or Hessian Lipschitz constant, we use the values in the original works. We trained each unique learning algorithm on each dataset until convergence before adding noise. Tables 13 and 15 report the AUC of the noiseless trained models of the certified algorithms, showing that they achieve comparable performance prior unlearning. Since HF requires O(nd) storage (and (nddI)) storage during training to compute the unlearning vectors), which is impractically large for our datasets and models, we follow their precedent and employ a scaled-dows (md) version that only computes the vectors for the samples we plan to unlearn.
Table 5: Experiment parameters of HF and CNS for the eICU and Lacuna- 100 datasets.
Experiment Parameter
cCCU
Lacuna-100
Hessian-Free Unlearning
Batch size
512
256
170
0.1
0.1
Step size decay Gradient norm clipping
0.995
0.995
5
S
Number training epochs Optimizer
15
SGD
SGD
Constrained Newton Step
Batch size
128
128
7)
0.001
0.001
Weight decay
0,0005
0.0005
Parameter norm constraint R
10
21
Number of training epochs
30
30
Convex constant
200
2,000
Hessian scale
50,000
50,000
Optimizer
Adam
Adam
Table 5 shows the parameters used for implementing the certified unlearning baselines. Ad-
ditional information can be found in the GitHub repository. The implementation of [48] based on code from petps://githa
com/ http//hangincciccrritttttt seerrfiiedddeep---e unlearning. and the implementation of [37] is based code from https: htt///gttttuuu com com/XinbaoQiiao/ Hessian- Freaaan-Feee-ertteee ied Unlearning.
The implementations of the non- non-certified baseline methods are also available in the GitHub repository. The hyperparameters for these methods are as follows:
Finetune: 10 epochs
23

---

Fisher Forgetting: alpha=le-6 for eICU, alpha=le-8
SCRUB:
See the following notebooks the GitHub repository for full SCRUB hyperparameters, including lacuma_baseline. aamaellin__mmplementtiionn ipynb and hta.baaelline_immmmmmetttaa
ipynb.
B.2 Computation Time Experiments
Because we desire machine unlearning algorithms that achieve computational advantage over training from scratch, is useful to compare the amount of time required for learning and unlearning for different algorithms. The results in Table 6 and 7 demonstrate that R2D unlearning is significantly more computationally efficient than HF and is competitive compared to CNS. These results were achieved on an NVIDIA RTX A6000 GPU (48 GB). As expected based on its straightforward algorithmic structure, the unlearning time of R2D is proportional to the number rewind iterations.
Although these results depend on our implementation of the learning algorithms of HF and CNS, we observe that as shown in Table 5, we use fewer training iterations for HF compared R2D. Despite this, HF requires 22-88 times more compute time during learning, highlighting the benefits of black-box algorithms that dovetail with standard training practices and do require complicated data-saving procedures. Similarly, CNS also requires fewer training iterations than R2D because it allows the use of advanced optimization techniques like momentum and regularization. However, because CNS unlearning requires an expensive second-order operation independent of the training process, it only displays moderate computational advantage on the Lacuna- 100 dataset and no advantage on the eICU dataset. In contrast, by construction R2D unlearning will always require less computation than learning, demonstrating the benefits of a cheap first-order approach.
Table 6: Comparison of computation time on the eICU dataset, with 23% or 49% of training iterations for R2D.
Algorithm
Learning Time
Unlearning Time
Rewind-to- Sowind-to-Deleess (R2D), 23%
230.76 sec
58.48 sec
Rewind-to-Deds to-eeltt (R2D), 49%
230.76 sec
113.69 sec
Hessian-Free (HF)
5.65 hours
0.01 sec
Constrained Newton Step (CNS)
266.0 sec
293.6 sec
Table 7: Comparison of computation time on the Lacuna-100 dataset, with 19% or 44% of training iterations for R2D.
Algorithm
Learning Time
Unlearning Time
Rewind-to-Deie (R2D), 19%
4.57 hours
0.91 hours
Rewind-to-Die -Deete (R2D), 44%
4.57 hours
2.06 hours
Hessian-Free (HF)
4.23 days
0.00 hours
Constrained Newton Step (CNS)
0.58 hours
0.32 hours
As for storage, note that even with the stripped-down version of HF, it still requires 1.5 GB of storage for the eICU dataset and 136GB for the Lacuna- 100 dataset during training, whereas R2D only needs to store the model weights at checkpoint and the final iterate (2 x 8) MB for eICU and (2 x 45 MB for Lacuna-100),
B.3 Proximal Point Experiments
We implement the proximal point method (Algorithm 3) and evaluate its ability to reconstruct prior checkpoints. Our results are shown in Table 8. We measure the success by the Euclidean distance between the original checkpoint and the reconstructed checkpoint, observing that they are close for small K but grow apart as we rewind past half the original training trajectory, due compounding approximation errors that ultimately leads to instability in convergence. Taking into account the model dimension, our results show that we can quite faithfully reconstruct checkpoints for moderate K.
24

---

We also evaluated the computational cost of Algorithm 3 and found that in most cases, reconstructing the checkpoint has a minor impact on the overall runtime. In Tables 9 and 10. we include the time takes to reconstruct the checkpoint into the learning time. For eICU, we see that small amounts of rewinding require minimal additional computation, while more rewinding takes slightly longer due to instability slowing down convergence. For Lacuna- 100, the cost of Algorithm 3 is small compared to the cost learning and unlearning, due to a difference in batch size.
We note that the precomputation learning time of R2D is still vastly superior to that of the Hessian- Free method, the state-of-the of-the--rrt art second-order certified unlearning method. Moreover, by design, R2D (with checkpointing) will always cost less than retraining from scratch. This stands in contrast CNS, which has a fixed computation cost that not necessarily more efficient than retraining.
Table 8: Checkpoint reconstruction for eICU and Lacuna- 100 datasets.
eICU (136k parameters)
Lacuna-100 (11 million parameters)
Rewind Percent Euclidean Distance
Rewind Percent
Euclidean Distance
10.26%
0.0650
7.41%
1.174
23.08%
0.2921
18.51%
2.737
35. 35.90%
0.9977
25.92%
3.187
48.71%
2.924
44.44%
4.464
Table 9: Learning times with checkpoint reconstruction (Algorithm 3) on the eICU dataset.
Algorithm
Learning Time
R2D with checkpoint reconstruction, 23 %
231.33 sec
R2D with checkpoint reconstruction, 49 %
337.18 see
Table 10: Learning times with checkpoint reconstruction (Algorithm 3) on the Lacuna- 100 dataset.
Algorithm
Learning Time
R2D with checkpoint reconstruction, 19 % 4.57 hours +123.62 sec
R2D with checkpoint reconstruction, 44 %
4.57 hours +280 sec
B.4 LLM Experiments
We note that LLM unlearning is a rich subfield with its own specific experiment designs, evaluation metrics, and membership attacks. In this section, provide a preliminary experiment to demonstrate the potential benefits of rewinding as opposed to "descending," i.e. continuing directly from the final model parameters, for LLMs. The code is available in the GitHub repository.
We finetune an open-source LLM dataset [43]. We treat the math-related tasks in Alpaca the unleamed set D Dunlearn- We generate the following sets model parameters:
[2]) using LoRA [24] on the Alpaca
1. Learned Model: We fine-tune the off-the-shelf model for three epochs on the whole Alpaca dataset.
2. "Retraining" " Baseline: We fine-tune the off-the-shelf model for three epochs on only the non-math tasks. This simulates the "retrain from scratch" unlearning baseline.
3. "Finetuning" " Baseline: We fine-tune for one more epoch starting from the Learned Model the non-math tasks. This simulates the "finetuning" D2D unlearning baseline. We note there is some overlap in terminology; in unlearning literature, "finetuning" refers to starting from the trained model and performing more steps the loss function of the retained data.
4. R2D: We rewind to the first or second checkpoints from the Learned Model fine-tuning process, and proceed for two one more epochs the non-math tasks.
25

---

Classic MIA
MIA-U
0.10
120
0.00
Atrak
03000
eAm
0.40
2.mm
Rewtnd Tomeent
Towind Peroett
Classic
MIA-U
W
Atook AUCC
420
Figure 4: MIA scores for the eICU dataset (top) and the Lacuna- 100 dataset (bottom).
In Table 11, we compare the performance (BLEU) these models on D Dunicarn and the computation cost of unlearning. We observe that both R2D methods outperform Finetuning, and in particular R2D 33% performs better while using the same amount of computation. This further supports our claim that rewinding is better than direct finetuning for unlearning on nonconvex functions.
Algorithm
BLEU
Unlearning Epochs
Learned Model
0.1576
N/A
"Retraining" Baseline
0,0935
3
"Finetuning" Baseline
0.1035
1
R2D 33% 0.1009
1
R2D 67%
0.1020
2
Table II: Experiments with LoRA finetuning on an LLM.
B.5 Additional Results
In this section, we provide additional experimental results, including full version Tables and in Tables 12 and 14. For additional comparison purposes, also provide metrics computed on the noiseless version of the certified unlearning methods in Tables 13 and 15. We include the standard deviation (1-sigma error) of the MIA scores all k-fold cross-validation trials.
Figure shows the MIA scores decreasing as the rewind percent increases, demonstrating that the attacks become less successful with more unlearning steps. This suggests that the rewinding step is important for erasing information about the data even without noise disguising the output of the unlearning algorithm. Nonetheless, Figure also shows that small perturbation consistently reduces the effectiveness of the membership attack. Finally, we observe that the MIA are generally more successful on the Lacuna- 100 dataset than the eICU dataset. This may be because the eICU dataset noisier and the models are trained to lower level of accuracy, leading to errors in classification that that passed to the attack model.
Finally, we plot t-SNE feature representations of the model outputs Figure before and after unlearning, observing that the unlearned samples are indeed more dispersed after unlearning.
26

---

Table 12: Comparison of Unlearning Algorithms on the eICU Dataset
Model AUC
MIA AUC
Algorithm
Dood
D Detain
Duntearn
Deast
Classic MIA
MIA-U
Original Models
HF
0.7365
0.7490
0,7614
0.7472
CNS
0.7519
0.7628
0.7860
0.7602
R2D (with noise)
0.7207
0.7329
0.7458
0.7316
Certified Methods (o 0.01)
HF
0.7361
0.7476
0.7587
0.7465
0.5078 #000260
0.5 108 +000202
CNS
0.7517
0.7622
0,7848
0.7601
0.5145 +0.0288
0.5 4.51042
R2D 10%
0.7220
0.7335
0.7444
0.7327
0.5047 #000285
0.500 +=0.0255
R2D 23%
0.7220
0.7334
0.7442
0.7327
0.5046200.065
0.5000
R2D 36%
0.7220
0.7334
0.7441
0.7327
0.5046::0.2285
0,5001 =1000255
R2D 49%
0.7219
0.7334
0,7441
0.7326
0,5045 0.00283
0,4998 1000255
R2D 74%
0.7219
0.7333
0,7439
0.7326
0.5044 0.0283
0.0228
0.0297
R2D 87%
0.7218
0.7333
0.7438
0.7325
0.5044 0.0028
0.4996
R2D 100%
0.7217
0.7331
0.7437
0.7323
0.5044
0.5000
Noiseless Retrain (R2D 100%)
0.7210
0.7335
0.7447
0.7321
0.5060
0.5064
Non-certified Methods
Finetune
0.7225
0.7352
0.7463
0.7337
0.5063
0.5066==00248
Fisher Forgetting
0.7201
0.7310
0.7482
0,7302
0.5114
0.5102
SCRUB
0.7211
0.7336
0,7450
0,7322
0.5060
0.5056+0.0247
Table 13: Certified Unlearning Algorithms without Noise (c = oo) on the eICU Dataset
Model AUC
MIA AUC
Algorithm
Dood
Dretain
Duntearn
Drest
Classic MIA
MIA-U
Original Models
HI
0.7365
0.7490
0.7614
0.7472
CNS
0.7519
0.7628
0.7860
0.7602
R2D
0.7211
0.7337
0,7451
0.7322
Certified Methods (a 0)
HF
0.7365
0.7490
0.7612
0.7472
0.5078=20026
0.5135 0..0199
CNS
0.7521
0.7630
0.7862
0.7604
0.5143
0.51 0.51138
R2D 10%
0.7214
0.7339
0.7452
0.7325
0.5062
0.506.5=0.024
R2D 23%
0.7213
0.7338
0.7450
0.7324
0.506
1: 1:0.02
0.5064
R2D 36%
0.7213
0.7338
0,7450
0.7324
0.506 +000286
0.5064-10.024
R2D 49%
0.7212
0.7338
0.7449
0.7324
0.5060
0.0028
0.5063 2.00244
R2D 74%
0.7212
0.7337
0.7449
0.7323
0.5059
0.50632200244
R2D 87%
0.7212
0.7337
0.7448
0.7323
0.5059
0.5062-20024
Noiseless Retrain (R2D 100%)
0.7210
0.7335
0,7447
0.7321
0.5060=000285
0.5064-20.0241
Figure 5: Left: t-SNE representations on D Dretain- Right: t-SNE representations on D unlleamn
27

---

Table 14: Comparison of Unlearning Algorithms on the Lacuna-100 100 Dataset
Model AUC
MIA AUC
Algorithm
Dood
D retain
D Danlearn
Deest
Classic MIA
MIA-U
Original Models
HF
0,9392
0.9851
0,9746
0,9737
CNS
0.9497
0.9983
0,9956
0,9856
R2D (with noise)
0.9106
0,9719
0,9742
0.9591
Certified Methods (a = 0.01)
HI
0.9327
0.9757
0,9555
0,9652
0.4949
0.846 +000179
CNS
0.9475
0.9977
0,9949
0,9847
4..023
0.84
R2D 7%
0,9090
0,9606
0.9238
0,9478
0,5625
1:.0221
R2D 19%
0.9120
0.9728
0,9407
0.9559
0.5735
0. 0.7446:10.027
R2D 26%
0.8889
0,9313
0,8580
0.9266
0.5672:10.08
0.7089910.00
R2D 37%
0.9055
0.9683
0,9269
0.9525
0.5197
0.6779
R2D 44%
0.9151
0.9752
0,9290
0.9621
0.5
0.7481
R2D 56%
0.8897
0.9634
0.9215
0,9440
0.541 20.0322
0.7504
R2D 63%
0.9018
0.9594
0,8411
0.9426
0.5519 #0.035
0.7092:#0.022
R2D 74%
0,9082
0.9712
0,8998
0.9534
0.5333 0.0034
0.7206
R2D 81%
0.8955
0.9648
0,9059
0.9463
0.5284
+0.0443
0.7043
R2D 85%
0.9010
0.9672
0.9072
0.9509
0.5529 20.0336
0.7613
R2D 93%
0,9136
0.9701
0.8814
0.9528
0.541 8.000339
0.7322:200216
R2D 100%
0.8932
0.9589
0.8868
0.9407
0.5164
0.7586
Noiseless Retrain (R2D 100%)
0.9406
1.0000
0,9460
0,9840
0.4974
0.8101 +0,0262
Non-certified Methods
Finetune Fisher Forgetting
0.9403
0.9997
0,9975
0.9854
0.601 3.0.0335
0,8497:100233
0.9398
0.9982
0,9986
0.9831
0.58 35814=0.000
0.8735
SCRUB
0.9391
0.9989
0.9999
0.9845
0.6179=00331
0.8586=0.0239
Table 15: Certified Unlearning Algorithms without Noise (e = 2c) on the Lacuna- 100 Dataset
Model AUC
MIA AUC
Algorithm
Dood
D Dretain
Dantearn
Dtext
Classic MIA
MIA-U
Original Models
HF
0.9392
0.9851
0,9746
0,9737
CNS
0.9497
0.9983
0.9956
0.9856
R2D
0.9391
0.9989
0.9993
0.9844
Certified Methods (ar
HF
0.9393
0.9852
0,9744
0,9738
0.4949+4.008
0.8360++0.018s
CNS
0.9497
0.9984
0,9957
0.9857
0.5896=00039
0.9674-20.00
R2D 7%
0.9307
0.9903
0,9677
0.9741
0.5727
0.81 1 02.30.029
R2D 19%
0,9379
0.9992
0,9732
0.9828
0.6305=00033
0.8475-20.025
R2D 26%
0.9179
0.9582
0.8833
0.9506
0.5318 00.099
0
R2D 37%
0.9317
0.9959
0,9598
0.9777
0.51 79 0.0354
0.7961 ++00200
R2D 44%
0.9368
0.9980
0,9518
0.9815
0.6024 0.0035
0.8374
R2D 56%
0.9406
1.0000
0.9567
0.9860
0.554 0.0038
0.8096-+0.0245
R2D 63%
0,9260
0.9917
0.8870
0,9720
0,5442 0.0035
0..3385-100226
R2D 74%
0.9387
1.0000
0,9381
0.9856
0.4948
0..0352
0.8 +0.0262
R2D 81%
0.9391
0,9999
0,9486
0.9843
0.526
100034
0,8137 1.002622
R2D 85%
0.9337
0.9987
0.9475
0.9827
0.5309 200061
0.81 1 20003
R2D 93%
0,9389
0.9968
0.9385
0.9801
0.5177
0.8246=10:0144
Noiseless Retrain (R2D 100%)
0.9406
1.0000
0.9460
0.9840
0.4974=2.034
0.8101 2200262
28

---

C Limitations
In this section, we discuss some limitations of our work. First, we observe that while theoretically we can achieve any level of noise and privacy by controlling K, the number of unlearning steps, the value of decreases very slowly with more rewinding, as shown in Figure If. This stands in contrast to results in convex unlearning, where the noise may decay exponentially with K. See Appendix E for more discussion.
Second, since in practice full-batch gradient descent is too computationally demanding for all but the smallest datasets, we closely approximate this setting using mini-batch gradient descent with very large batch size. This approximation and others (like estimation of and G) introduce some imprecision into the level of certification, although the general principle of achieving probabilistic indistinguishabiityy via Gaussian perturbation still holds. In addition, the large batch size slows down training, as the optimizer takes a long time escape saddle points and converge to well-generalizing minima. Moreover, because we require constant step size, we also lose the benefits of advanced optimization techniques such as Adam, momentum, or batch normalization, all of which improve convergence speed and model performance. Developing certified unlearning algorithms for stochastic gradient descent and adaptive learning rates future direction of our work.
Third, we note that in the experimental settings we consider, we only achieve reasonable model utility very high levels of c, which may not be used in practice. This is true for all certified unlearning algorithms considered in this paper, as shown in Figure 1b and le. Therefore in this regime, 6 just represents a relative calibration of privacy rather than specific theoretical meaning.
Finally, we note that while certified unlearning methods do leverage Gaussian perturbation to defend against membership inference attacks successfully, this comes at cost to model performance. The non-certified algorithms tend have higher MIA scores but also better model performance.
D Broader Impacts
This paper expands existing work in machine unlearning, which has the potential to improve user privacy and remove the influence of corrupted, biased, or mislabeled data from machine learning models. However, additional investigation may be necessary to determine the effectiveness of these algorithms in the real world.
E
Additional Discussion of Related Work
To review, our algorithm is first-order, black-box algorithm that provides (e,8) unlearning while also maintaining performance and computational efficiency. In this section, we provide an in-depth comparison our algorithmic differences with existing convex and nonconvex certified unlearning algorithms (Table 16). These algorithms all involve injecting some (Gaussian) noise to render the algorithm outputs probabilisticall indistinguishable, whether is added the objective function, to the final model weights, or at each step of the training process.
We are interested in comparing the noise- unlearning tradeoff of each of these algorithms. The second column of Table 16 lists the standard deviation a in terms of c, 6, and other problem parameters for the other certified unlearning algorithms. Our result is analogous to that of [34], due algorithmic similarities such as weight perturbation at the end of training. However, the required noise in (34] decays exponentially with unlearning iterations, while our noise decreases more slowly with increasing K for our algorithm. This difference is because [34] considers strongly convex functions, where trajectories are attracted to a global minimum.
The third column of Table 16 highlights an additional advantage our algorithm has over existing approaches. Our theoretical guarantees do not require a uniform bound on the model weights ||0|| < R. nor does a depend on R, in contrast to [12] and [48]. Both [48, 12] require a bounded feasible parameter set, which they leverage provide loose bound the distance between the retraining and unlearning outputs dependent on the parameter set radius R. However, this yields excessive noise requirements, with the standard deviation scaling linearly or polynomially with R.
Our work shares similarities with [12], a first-order white-box algorithm that uses noisy projected gradient descent to achieve certified unlearning, leveraging the existence and uniqueness of the
29

---

Bounded
Algorithm
Standard Deviation of Injected Gaussian Noise
|0]| < R??
Newton Step [23]
4LG v (log
No
(a-11 1/c
Descent-to- delete (D2D) [34]
4/2M (.71)
No
An(1 - (V + Vlog(1/6))
Langevin Unlearning [12]
No closed-form solution for terms of e,
Yes
Constrained Newton Step (CNS) [48]
2R(PR+A)
/2/log(d/p) X+Amin
+
IR 2 log(1 (lgg(112///) 25/6)
A-Amin
Yes
Elessian-Free unlearning (HF) [37]
21/G V 2 log (1.25/0)
CT
No
Our Work (R2D)
2mG I(K)) V (0og(1.25/1)
No
Lnc
Table 16: Comparison of certified unlearning algorithms and their noise guarantees. We denote K as the number of unlearning iterates, as the regularization constant or strongly convex parameter, M as the Lipschitz continuity parameter, and d as the model parameter dimension. In addition, R is the parameter norm constraint. For [48], represents the Lipschitz constant of the Hcssian, Amin represents the minimum eigenvalue of the Hessian, and p represents probability less than 1. For [37], ST is constant dependent the upper and lower bounds of the Hessian spectrum that grows with the number of learning iterates T for nonconvex objective functions.
limiting distribution of the training process as well as the boundedness of the projection set. Their guarantee shows that the privacy loss decays exponentially with the number of unlearning iterates. However, a, the noise added at each step, defined implicitly with no closed-form solution. We only assert that for fixed number of iterations K, must be at least O(R) to obtain O(1). Because a cannot be defined explicitly, is difficult to implement this algorithm for a desired e. For example, when performing experiments for the strongly convex setting, which is simpler mathematical expression, they require an additional subroutine to find the smallest a that satisfies the target As for the nonconvex setting, they state that "the non-convex unlearning bound... currently is not tight enough to be applied in practice due to its exponential dependence on various hyperparameters.
30

---

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]
The abstract and introduction highlight the context of our work and the essential contribution, which developing first-order, black-hox certified unlearning algorithm with theoretical guarantees on nonconvex functions. We also review the experimental design, explain why is novel, and correctly summarize the results.
Justification:
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as is clear that these goals attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
We discuss the limitations of our work in Appendix C.
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 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 (e.g., independence assumptions, noiseless settings, model well-specification, 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 the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend implicit assumptions, which should be articulated.
The authors should reflect 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-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and prool's
Question: For each theoretical result, does the paper provide the full of assumptions and complete (and correct) proof?
31

---

Answer: [Yes]
Justification: We provide the assumptions in the statement of each theoretical result, and we provide proofs for all results in Appendix A.
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 in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversell, 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 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 anonymous GitHub repository of all code required to implement the superiments,includine the baseline methods, model architecture, default hyperparame- ters, and dataset preprocessing. We also provide extensive details about the experimental implementations in Appendix B.I.
Guidelines:
The answer NA means that the paper does not include experiments. If the paper includes experiments, 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 is a specific model and empirical evaluation, it may be necessary to either make 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 to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) 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) the contribution is a new model (e.g., a large language model), then there should either be way 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 reproducibility may be tricky in some cases, in which case authors are welcome 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 (c.g., to registered users), but it should be possible for other researchers to have some path to reproducing verifying the results.
32

---

5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Answer: [Yes]
Justification: In Appendix B.I, provide links for downloading the datasets, instructions for dataset preprocessing, and the GitHub repository containing code for reproducing the results. While the eICU database requires taking a short online course ethics before providing access, it is available to all researchers who submit a request.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips. cc/
Siades//oodSuubmise
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" 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 NeurlPS code and data submission guidelines (https:
/nips. /twps.cc/ppuiiiii wttp:cccpppppc.cciccceoooocppcpa gwwii///gge////eeeeoeooie (CodeSubiissionPolll
for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code 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: We provide all experimental details in Appendix B.1 and the anonymous GitHub repository linked in the paper.
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 be provided either with the code, appendix, or as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer:
[Yes]
Justification; In Tables 12, 13, 14, and 15, we provide 1-sigma error bars for the MIA results.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by enror bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
33

---

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

---

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

---

If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com datasttssss has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors encouraged to reach out the asset's s creators.
13. New assets
Question: Are assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: The new assets in the paper well documented and licensed under the MIT license, provided in the GitHub repository.
Guidelines:
The answer NA means that the paper does not release assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in 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 the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, 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 an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor 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.
36

---

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.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: The core method development in this research does involve LLMs as any important, original, or non-standard components.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to our LLM policy for what should or should not be described.
37


Reviews:
[{"review_id": "Bv6jqtXx68", "reviewer": "Reviewer_PXQd", "summary": "This paper proposes a black-box, first-order machine unlearning algorithm for non-convex, Lipschitz, and smooth loss functions. The (randomized) unlearning algorithm takes as input the original model parameters, the full training dataset, and a subset of the training data to be unlearned. The goal is to return model parameters that are indistinguishable from those that would have been obtained had the subset never been part of the training set.\nEffectively, this means the influence of the removed data on the model is significantly reduced.\n\nThe proposed algorithm uses only first-order information and analyzes the privacy-utility trade-off. Furthermore, when the non-convex loss satisfies the Polyak-Łojasiewicz (PL) inequality, a well-known condition in nonconvex optimization, a generalization guarantee is provided.", "questions": "See the above.", "limitations": "Limitations are addressed.", "rating": 3, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths:\n\nThe problem of certified machine unlearning for non-convex loss functions is important and underexplored.\nThis paper appears to make meaningful progress in this direction.\n\nWeaknesses and Questions:\n\nAs someone familiar with the general concept of machine unlearning but not deeply familiar with previous algorithms:\nHow do the proposed privacy-utility and generalization guarantees compare to prior work?\nThis comparison is unclear from the current presentation.\n\nThe algorithm appears relatively simple. What are the novel contributions or insights compared to existing methods?\n\nWhy is the method described as a \"black-box\" algorithm?\nSpecifically: What is the initial point $\\theta_0$? Is it the model trained on the full dataset, or some arbitrary initialization? If  $\\theta_0$ is just an arbitrary initialization, in what sense is the method \"black-box\"? \n\nWhat is the role of the parameter $K$ in the algorithm?\n\nI think some clarifications are missing in the paper, which are necessary to assess the significance of the results.", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review and considerate comments. In the following, we respond to your concerns.\n\n**As someone familiar with the general concept of machine unlearning but not deeply familiar with previous algorithms: How do the proposed privacy-utility and generalization guarantees compare to prior work? This comparison is unclear from the current presentation.**\n\nWe provide a list and detailed comparison of the theoretical guarantees of prior work in Table 12 in Appendix E. Our algorithm inherits the same basic $\\sigma = O(\\frac{1}{\\epsilon})$ relationship as other differentially private (and certified unlearning) algorithms, since it follows directly from the Gaussian mechanism. However, computational efficiency is also a central concern for unlearning, which is why we also have a tradeoff with complexity, represented by the number of unlearning iterates $K$. Our algorithm and theoretical analysis allows flexible selection between the variables $\\epsilon, \\sigma$, and $K$, such that one can be chosen to be arbitrarily small compared to the other two. In particular, when we rewind to the initial iterate ($K = T$), we recover *perfect* privacy-utility, corresponding to full retraining and zero noise, at the expense of computation. \n\nOur privacy-utility-complexity guarantee (3) has several advantages over prior work in nonconvex certified unlearning, which we highlight in Section 3 and discuss further in Appendix E. First, (Zhang et al., 2024) and (Qiao et al., 2025) have *no complexity tradeoff*, both require a fixed amount of computation that is not guaranteed to be more efficient than retraining. In fact, we found in our experiments (Table 6) that the Newton step in (Zhang et al., 2024) may be *more* costly than retraining. Second, our noise bound scales inversely with the size of the dataset $n$, implying that unlearning a fixed number of samples for large datasets has less impact than for small datasets. In contrast, the noise in (Zhang et al., 2024) and (Qiao et al., 2025) is fixed for all dataset sizes. Finally, (Zhang et al., 2024) and (Chien et al., 2024) require projection onto a bounded parameter set, with fixed radius $R$, in order to control the training trajectory and thereby bound the distance between unlearning and retraining. As a result, their noise guarantees scale as $O(R)$, which is impractical and not necessarily better than randomly sampling weights from the feasible set. \n\nAs for the generalization guarantee, we note that we can only obtain such guarantees for algorithms that converge to global minima. By considering PL functions, we are, to the best of our knowledge, the first to consider unlearning generalization in a nonconvex setting. However, we can compare our result to existing results for strongly convex functions, which are a subset of PL functions (Qiao et al., 2025; Liu et al., 2023; Suriyakumar et al., 2022). We observe that the population risk can be decomposed to three terms: an $O(\\frac{1}{n})$ term representing the difference with empirical risk, an $O(\\sqrt{d} \\sigma)$ term representing the Gaussian noise, and a term representing the convergence of the underlying optimization framework. The first two terms are roughly equivalent across most works because they follow from fundamental principles. As for the last term, in our work it decays exponentially with increasing iterations, whereas (Liu et al., 2023) and (Suriyakumar et al., 2022) feature fixed bounds that cannot be reduced. Our result is roughly equivalent to Equation (14) of (Qiao et al., 2025) (since $T =  \\frac{n E}{|B|}$). However, PL is a significantly weaker condition than strong convexity that cannot take advantage of a *unique* global minimum; instead, we show convergence by noting that gradient descent steps on the original loss function $f_{\\mathcal{D}}$ represent biased gradient descent steps on the updated loss function $f_{\\mathcal{D}'}$ (Corollary A.5). We will expand our discussion of the generalization guarantee in our camera-ready version.\n\n**The algorithm appears relatively simple. What are the novel contributions or insights compared to existing methods?**\n\nBeyond the main contributions of our work (first-order, black-box, nonconvex), **our algorithm addresses an important gap in machine unlearning.** There are two well-known algorithms in machine unlearning: Descent-to-Delete (D2D), a certified unlearning algorithm for strongly convex functions, and Finetuning, the non-certified analog to D2D. In particular, Finetuning is an extremely common baseline method implemented in almost every machine unlearning paper, including both theory and application papers. These algorithms are similar-- for both, the model is trained with (stochastic) gradient descent steps during the learning stage, and for unlearning, additional steps are performed starting from the trained model, on the retained dataset. However, neither have theoretical guarantees for nonconvex functions. In fact, it is likely *impossible* to extend the D2D analysis to the nonconvex setting, since it relies on the existence of a unique global minimum, which (i) attracts training trajectories and (ii) remains in a small neighborhood when the underlying loss function is changed. Neither (i) nor (ii) hold for the general nonconvex setting, where we may only converge to a local minima or saddle point. \n\nIn our work, we argue that instead of performing steps starting from the trained model, one should \"rewind\" to an earlier checkpoint and perform steps starting from there. Our novel insight is we leverage rewinding instead of \"descending\" to bring the unlearned model closer to the retrained model by reversing the divergence in training trajectories caused by the unlearning bias. This is a brand new algorithmic idea and an important contribution of our work. We provide a clean theoretical analysis analyzing the privacy, utility, and complexity of this approach, showing that it is provably more efficient than retraining. Our work provides a theoretical basis for first-order methods in unlearning, but suggests that rewinding instead of fine-tuning is a better choice on nonconvex functions. We feel that the simplicity is not a flaw of our algorithm, rather it is part of its appeal, making it easier to understand and implement. \n\n**Why is the method described as a \"black-box\" algorithm? Specifically: What is the initial point $\\theta_0$?**\n\nOur *unlearning* algorithm $U$ is black-box, which we define to be an unlearning algorithm that can be applied to a model pretrained with gradient descent, without any special procedures during learning. This stands in contrast to white-box algorithms, such as (Qiao et al., 2025), which requires expensive storage of information during training, and (Chien et al., 2024), which requires noise added at every training iteration. $\\theta_0$ is the model initialization for the *learning* algorithm. We show that our *unlearning* algorithm is $\\epsilon, \\delta$-indistinguishable to the output of the learning algorithm $A$, if $A$ initialized at the same point $\\theta_0$ and performed on $\\mathcal{D}'$. \n\n**What is the role of the parameter $K$ in the algorithm?**\n\n$K$ is the number of unlearning iterates, where $T$ is the number of training iterates and we start the unlearning process from the $T - K$th training checkpoint. Informally, it is \"the number of steps to go back,\" starting from the trained model $\\theta_T$. We can \"go back\" or rewind either by directly loading an earlier checkpoint or reconstructing one via Algorithm 3.\n\nWe will improve the manuscript by making the above points clearer in the camera-ready version. Thank you again for your thoughtful review, and please let us know if you have any further concerns about the paper."}, {"review_id": "D4r3JdlnhZ", "reviewer": "Reviewer_RBM5", "summary": "This paper introduces a novel certified unlearning framework that operates in a first-order, black-box manner. The authors provide a rigorous theoretical analysis of the trade-off between privacy, utility, and efficiency, and further explore the special case of Polyak–Łojasiewicz (PL) loss functions. Comprehensive empirical experiments demonstrate that the proposed algorithm outperforms existing methods in terms of convergence speed and unlearning guarantees.", "questions": "1. The authors focus on a first-order method, yet second-order approaches often offer faster convergence and stronger guarantees. Could you provide both theoretical discussion and empirical comparisons against a suitable second-order baseline to clarify the pros and cons?\n\n2. How does the proposed algorithm scale to very large datasets or large language models? Including at least a preliminary experiment (e.g., fine-tuning a small Transformer) would help demonstrate practical feasibility.\n\n3. Gaussian noise injection is central to your method. Please explain intuitively and formally why certified guarantees fail without this noise, and add ablation studies comparing performance with and without noise to highlight its impact on privacy and utility.", "limitations": "N/A", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths\n\n1. The paper delivers solid proofs for the privacy-utility-efficiency trade-off, offering clear bounds and insights.\n2. A wide range of benchmarks, datasets, and baselines are evaluated, showcasing the method’s superior performance.\n3. The treatment of PL loss functions provides additional depth and highlights practical scenarios where the algorithm excels.\n\nWeaknesses\n\n1. The paper does not compare against second-order unlearning methods, leaving unclear whether the proposed first-order approach truly balances effectiveness and efficiency.\n\n2. Scalability to very large datasets or modern large language models is not demonstrated.\n\n3. The necessity and impact of Gaussian noise are stated but not empirically isolated.", "was_revised": true, "final_justification": "I would like to keep my score:\n\n1. This paper needs more explanations for the noise added in the method, because it is the key contribution of the method \n\n2. The experiments need to improve the presentation. And results in Table 2 are incremental.\n\n3. This method is a novel unlearning method with guarantees based on first order. However, the novelty is not enough, it would be better to extend to second order version.", "rebuttal": "Thank you for your insightful review and considerate comments. In the following, we respond to your concerns.\n\n**The paper does not compare against second-order unlearning methods, leaving unclear whether the proposed first-order approach truly balances effectiveness and efficiency.**\n\n**(Q1) The authors focus on a first-order method, yet second-order approaches often offer faster convergence and stronger guarantees. Could you provide both theoretical discussion and empirical comparisons against a suitable second-order baseline to clarify the pros and cons?**\n\nWe do compare against both existing second-order certified unlearning methods for nonconvex functions: Hessian-Free method (Qiao et al., 2025) and Constrained Newton Step (Zhang et al., 2024). Theoretically, we compare against both methods in Table 1, with additional discussion in Section 3 and Appendix E, including a more detailed review of the noise guarantees in Table 12. Beyond the main benefits of first-order algorithms, our guarantee has several theoretical advantages. We note that both second-order methods involve a single step and have *no complexity tradeoff*, requiring a fixed amount of computation that is not guaranteed to be more efficient than retraining and may not be converged to a stationary point or local minima. In contrast, both our unlearning and our utility guarantees can be improved by increasing the number of iterations. In addition, our noise bound scales inversely with the size of the dataset $n$, implying that unlearning a fixed number of samples for large datasets has less impact than for small datasets. In contrast, the noise in (Zhang et al., 2024) and (Qiao et al., 2025) is fixed for all dataset sizes. \n\nEmpirically, we implement both methods as baselines in all experiments. We find that R2D outperforms both second-order methods in unlearning metrics (Table 2), is computationally efficient (Table 6 and 7), and exhibits a better privacy-utility tradeoff in practice (Figure 1). In particular, we found that the HF method requires expensive precomputation before unlearning, and the unlearning Newton step in (Zhang et al., 2024) may be *more* costly than retraining (Table 6). \n\n**Scalability to very large datasets or modern large language models is not demonstrated.**\n\n**(Q2) How does the proposed algorithm scale to very large datasets or large language models? Including at least a preliminary experiment (e.g., fine-tuning a small Transformer) would help demonstrate practical feasibility.**\n\nWe note that LLM unlearning is a very rich subfield with its own specific experiment designs, evaluation metrics, and membership attacks, and as such extensive experiments may be outside the scope of our work, which focuses on theoretical unlearning guarantees. We now provide an experiment to demonstrate the potential benefits of rewinding as opposed to continuing directly from the current model parameters, for LLMs. The details and findings are as follows.\n\nWe consider fine-tuning an open-source LLM (Mistral-7B-Instruct-v0.2) using LoRA on the Alpaca dataset. We treat the math tasks in Alpaca as the unlearned set $\\mathcal{D} _{unlearn}$. We generate the following models:\n\n1. Learned Model: We fine-tune the off-the-shelf model for three epochs on the whole Alpaca dataset.\n2. \"Retraining\" Baseline: We fine-tune the off-the-shelf model for three epochs on only the non-math tasks. This simulates the \"retrain from scratch\" unlearning baseline.\n3. \"Finetuning\" Baseline: We fine-tune for one more epoch starting from the Learned Model on the non-math tasks. This simulates the \"finetuning\" unlearning baseline. We note there is some overlap in terminology; in unlearning literature, \"finetuning\" refers to starting from the trained model and performing more steps on the loss function of the retained data.\n4. R2D: We rewind to the first or second checkpoints from the Learned Model fine-tuning process, and proceed for two or one more epochs on the non-math tasks.\n\nIn the following table, we compare the performance (BLEU) of these models on $\\mathcal{D} _{unlearn}$ and the computation cost of unlearning. We observe that both R2D methods outperform Finetuning, and in particular R2D 33% performs better while using the same amount of computation. This further supports our claim that rewinding is better than direct finetuning for unlearning on nonconvex functions.\n\n| Algorithm             | BLEU       | Unlearning Epochs |\n|-----------------------|------------|-------------------|\n| Learned Model        | 0.1576     | N/A               |\n| \"Retraining\" Baseline | 0.0935     | 3                 |\n| \"Finetuning\" Baseline |0.1035 | 1                 |\n| R2D 33%               | 0.1009| 1                 |\n| R2D 67%               | 0.1020 | 2                 |\n\n**The necessity and impact of Gaussian noise are stated but not empirically isolated.**\n\n**(Q3) Gaussian noise injection is central to your method. Please explain intuitively and formally why certified guarantees fail without this noise, and add ablation studies comparing performance with and without noise to highlight its impact on privacy and utility.**\n\nWe do perform ablation studies to empirically isolate the impact of Gaussian noise, but due to space constraints they are located in the Appendix. Tables 8 and 10 provide the full numerical results with noise, and Tables 9 and 11 provide the same results without noise. Figure 4 shows the MIA results for noiseless and noised R2D. As expected, the noiseless results exhibit higher model utility but the noised results exhibit better unlearning, indicated by lower MIA scores. At the same time, we note that for both versions, increased rewinding improves unlearning and reduces the MIA success, showing that this is a critical component of our approach. \n\nUnlearning may fail without noise because, as first addressed in (Guo et al., 2020), small differences in parameter space can leak information about data that was in the training set, even if the unlearned model parameters are approximately close to retraining. We require noise to achieve probabilistic indistinguishability and disguise the potential effects of the unlearned data, leveraging the properties of the Gaussian mechanism to quantify the privacy guarantee in terms of $\\epsilon$ and $\\delta$.\n\nThank you again for your thoughtful review, and please let us know if you have any further concerns about the paper."}, {"review_id": "Kt1HV3fAlo", "reviewer": "Reviewer_7iuP", "summary": "In this paper, the authors propose a first-order black-box unlearning algorithm. The key contributions of the paper are (i) a certified unlearning algorithm for non-convex loss functions. (ii) Theoretical unlearning guarantees; linear convergence and generalization guarantees for PL inequality satisfying loss functions. (iii) better performance than existing methods within a novel experimental framework.", "questions": "1. How does the accuracy of the proximal point method vary with the choice of K or η? Are there failure modes where it cannot approximate a valid earlier iterate?\n2. For large neural networks, does the \"offline\" computation of recovering earlier checkpoints scale efficiently? Is there any empirical or theoretical justification for its tractability?\n3. Since σ depends on L and G (which are estimated), how robust are the unlearning guarantees to inaccurate estimates? Is there a safe fallback?\n4. Unlearning in Continual or Online Learning: Can R2D be applied to continually updated models, or does it assume static datasets during training and unlearning?", "limitations": "Not many limitations. The only thing I notice is that there is no novelty in methods. The authors themselves acknowledge that they just combine well established ideas together in a different fashion to get R2D. That is the only limitation that I could see.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 1, "originality": 2, "strengths_and_weaknesses": "Strengths:\n+ First certified unlearning algorithm for general nonconvex functions that is both first-order and black-box, addressing a key gap in the current literature.\n+ The major strength of the paper comes from the analysis (specifically the unlearning guarantees, generalization guarantees) for nonconvex loss functions. This seems to be the major contribution.\n+ The method performs better than other baseline methods chosen\n\n\nWeaknesses:\n- While the authors propose a proximal point method for black-box checkpoint reconstruction, the computational cost and convergence behavior of this approach are briefly addressed and may not be practical for large-scale deployments without further assumptions. A clearer breakdown of when this reconstruction becomes prohibitive would help support real-world adoption.\n- The paper does an excellent job of analyzing trade-offs among ε, σ, and rewind steps K, but it doesn't offer practical guidance on selecting these parameters. This might hinder adoption in real-world pipelines that prioritize usability over theoretical bounds.\n- The experiments are well-crafted, especially in the user-centric setting, but are focused on classification with binary labels. While not required, the paper would be stronger if it discussed generalizability of R2D beyond this setup, especially since the claim is a general first-order method for nonconvex functions.", "was_revised": true, "final_justification": "The authors provided sufficient justification in terms of results to help improve the paper and also address many concerns that were raised. They also addressed the concerns about novelty and after keen look into the analysis and the proofs, I am willing to increase my score.", "rebuttal": "Thank you for your insightful review and considerate comments. In the following, we respond to your concerns.\n\n**While the authors propose a proximal point method for black-box checkpoint reconstruction, the computational cost and convergence behavior of this approach are briefly addressed and may not be practical for large-scale deployments without further assumptions. A clearer breakdown of when this reconstruction becomes prohibitive would help support real-world adoption.**\n\nThank you for this suggestion. Based on your feedback, we implemented the proximal point method (Algorithm 3) and evaluated its ability to reconstruct prior checkpoints. We will include these numerical results and their plots in the camera-ready version of the paper. \n\nWe measured the success by the Euclidean distance between the original checkpoint and the reconstructed checkpoint, observing that they are close for small $K$ but grow apart as we rewind past half the original training trajectory, due to compounding approximation errors that ultimately leads to instability in convergence. Taking into account the model dimension, our results show that we can quite faithfully reconstruct checkpoints for moderate $K$.\n\n| eICU (136k parameters)| | | Lacuna-100 (11 million parameters) | |\n|----------------|----------|---|----------------|----------|\n| Rewind Percent | Euclidean Distance |   | Rewind Percent | Euclidean Distance |\n| 10.26% | 0.0650 | | 7.41%| 1.174  |\n| 23.08%| 0.2921 | | 18.51%| 2.737 |\n| 35.90%| 0.9977 | | 25.92%| 3.187 |\n| 48.71%   | 2.924 | | 44.44%| 4.464 |\n\n**(Q1) How does the accuracy of the proximal point method vary with the choice of $K$ or $\\eta$? Are there failure modes where it cannot approximate a valid earlier iterate?**\n\nIn the above, we address how performance degrades as $K$ increases. The $\\eta$ parameter is fixed, as it is the learning rate of the *training* algorithm (Algorithm 1). A small $\\eta$ corresponds to more regularization, allowing the subproblem to remain computationally tractable.\n\n**(Q2) For large neural networks, does the \"offline\" computation of recovering earlier checkpoints scale efficiently? Is there any empirical or theoretical justification for its tractability?**\n\nWe also evaluated the computational cost of Algorithm 3 and found that in most cases, reconstructing the checkpoint has a minor impact on the overall runtime. In the following, we reproduce Table 6 and 7 from the paper, now including the time it takes to reconstruct the given checkpoint into the learning time. For eICU, we see that small amounts of rewinding require minimal additional computation, while more rewinding takes slightly longer due to instability slowing down convergence. For Lacuna-100, the cost of Algorithm 3 is small compared to the cost of learning and unlearning, due to a difference in batch size.\n\nWe note that the precomputation learning time of R2D is still vastly superior to that of the Hessian-Free method, the state-of-the-art second-order certified unlearning method. Moreover, by design, R2D (with checkpointing) will *always* cost less than retraining from scratch. This stands in contrast to CNS, which has a fixed computation cost that is not necessarily more efficient than retraining.\n\nOur results are also theoretically supported since $\\eta \\leq \\frac{1}{L}$ implies that the subproblem becomes a tractable convex problem (Lemma A.1). Moreover, because we solve the subproblem with SGD, our algorithm is still a pure first-order method that beats second-order methods in memory storage.\n\n**Table 6: eICU dataset**\n| Algorithm  | Learning Time | Unlearning Time |\n| ----------------------------- | ------------- | --------------- |\n| R2D, 23 % | 230.76 sec | 58.48 sec |\n| R2D, 49 %  | 230.76 sec | 113.69 sec |\n| R2D with checkpoint reconstruction, 23 % |231.33 sec|  58.48 sec |\n|R2D with checkpoint reconstruction, 49 %|337.18 sec|113.69 sec |\n| Hessian-Free (HF) | 5.5 hours | 0.01 sec |\n| Constrained Newton Step (CNS) | 266.0 sec | 293.6 sec |\n\n**Table 7: Lacuna-100 dataset**\n| Algorithm | Learning Time | Unlearning Time|\n| ----------------------------- | ------------- | --------------- |\n| R2D, 19 %  | 4.57 hours | 0.91 hours |\n| R2D, 44 %  | 4.57 hours | 2.06 hours |\n|  R2D with checkpoint reconstruction, 19 % | 4.57 hours +123.62 sec |0.91 hours|\n| R2D with checkpoint reconstruction, 44 %  | 4.57 hours +280 sec |2.06 hours|\n| Hessian-Free (HF) | 4.23 days | 0.00 hours |\n| Constrained Newton Step (CNS) | 0.58 hours | 0.32 hours |\n\n**The paper does an excellent job of analyzing trade-offs among $\\epsilon$, $\\sigma$, and rewind steps $K$, but it doesn't offer practical guidance on selecting these parameters.**\n\nFollowing the guidelines in (Zhang et al., 2024), we suggest first choosing a $\\sigma$ that preserves model utility (in our work, we use $\\sigma = 0.01$), and a $K$ within the computational budget, such as $10$% of the training iterates. From there one can compute the level of privacy $\\epsilon$ achieved. Our experiments for various $\\sigma$, including $\\sigma = 0$, (Table 9 and 11) suggest that a small amount of rewinding and/or noise performs well empirically. We will include this text in our paper.\n\n**The experiments are well-crafted, especially in the user-centric setting, but are focused on classification with binary labels. While not required, the paper would be stronger if it discussed generalizability of R2D beyond this setup, especially since the claim is a general first-order method for nonconvex functions.**\n\nR2D does generalize to any empirical risk minimization problem, and the number of classes does not meaningfully change the method or theoretical guarantees. Even though some other papers consider a multiclass setting, they uniformly sample i.i.d. data from the dataset to form the unlearning set, which is essentially equivalent to i.i.d. unlearning in a binary setting.\n\nWe sought to develop a more realistic experiment framework for unlearning, with more complex dataset considerations. For example, we chose the Lacuna-100/VGG-Face2 dataset because it is a standard unlearning benchmark dataset consisting of individual \"user data\" that can be classified by global characteristics, using the MAAD-Face labels. We considered a multiclass problem (i.e. hair color or age) but found that the MAAD-Face labels were much less accurate and the classes were highly imbalanced. Designing a multiclass benchmark dataset that is compatible with our novel framework is a potential future direction of our research.\n\n**(Q3) Since $\\sigma$ depends on $L$ and $G$ (which are estimated), how robust are the unlearning guarantees to inaccurate estimates? Is there a safe fallback?**\n\nInaccurate estimates indeed introduce some imprecision in the theoretical guarantee. However, the benefit of certified unlearning is that the basic principle of ensuring differential privacy via Gaussian perturbation, which scales with the strength of the privacy guarantee $\\epsilon$, still holds. Empirically, we observe that certified unlearning methods with even a small amount of Gaussian noise tend to outperform non-certified algorithms that do not use noise (Table 2).\n\n**(Q4) Unlearning in Continual or Online Learning: Can R2D be applied to continually updated models, or does it assume static datasets during training and unlearning?**\n\nR2D, and certified unlearning in general, applies to static datasets during training and unlearning. While we can perform sequential unlearning, and *adding* a fixed number of samples would yield a symmetric analysis, the existing theory is not equipped for a constant stream of new samples or any shifts in the underlying data distribution. Developing a certified unlearning framework for handling sequential tasks would be an interesting new direction of research.\n\n**Limitation: The only thing I notice is that there is no novelty in methods. The authors themselves acknowledge that they just combine well established ideas together in a different fashion to get R2D.**\n\nWe feel that our work is sufficiently novel in both method and analysis, and that its strength lies in its simple and intuitive structure. Many unlearning algorithms utilize various forms of gradient descent and/or checkpointing, but developing the underlying theory to support them, for nonconvex functions, is highly nontrivial. For example, our work is inspired by Descent-to-Delete (D2D), a first-order certified unlearning algorithm for strongly convex functions. However, directly extending the D2D analysis to the nonconvex setting is *impossible*, since it relies on the existence of a unique global minimum, which (i) attracts training trajectories and (ii) remains in a small neighborhood when the underlying loss function is changed. Neither (i) nor (ii) hold for the general nonconvex setting, where we may only converge to a local minima or saddle point. Our novel insight is we leverage rewinding instead of \"descending\" to bring the unlearned model closer to the retrained model by reversing the divergence in training trajectories caused by the unlearning bias. This is a brand new algorithmic idea and an important contribution of our work.\n\nIn our Prior Work section, we discuss existing algorithms that use some form of checkpointing and \"rewinding\" (Kurmanji et al., 2023), or gradient ascent (Jang et al., 2023). However, these works **do not have any theoretical guarantees** and rely solely on empirical unlearning metrics. For example, (Kurmanji et al., 2023) rewinds to a checkpoint of the unlearning process where the error on the forget set is \"just right,\" so as to defend against MIAs, which is completely different from our usage and rationale. Moreover, although Algorithm 3 does involve gradient steps \"up\" the loss function, it is not gradient ascent but an implicit Euler step, which is theoretically supported (Section 2).\n\nThank you again for your thoughtful review, and please let us know if you have any further concerns about the paper."}, {"review_id": "xye9I9jYyL", "reviewer": "Reviewer_xkYS", "summary": "The paper proposes R2D (Rewind-to-Delete), a certified machine unlearning algorithm designed for the black-box setting, where model retraining is infeasible. The method operates by rewinding the model to an earlier checkpoint  $\\theta _{T-K}$, re-optimizing only on the retained data $\\mathcal{D}'$ , and injecting calibrated Gaussian noise to satisfy $\\left( {\\varepsilon ,\\delta } \\right)$-certified unlearning guarantees. When the checkpoint $\\theta _{T-K}$ is unavailable, a proximal point method is used to reconstruct it from the final model state $\\theta _{T-K}$.", "questions": "Please answer the questions in the Weaknesses. All questions need to be answered.", "limitations": "yes", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n1. The method does not require access to internal training dynamics or full gradient history, making it deployable in practical, real-world scenarios.\n2. The use of differential privacy allows the algorithm to offer $\\left( {\\varepsilon ,\\delta } \\right)$-certified unlearning guarantees, enhancing interpretability and accountability.\n3. Algorithm 3 introduces a proximal fixed-point iteration to approximate historical checkpoints, enabling backward recovery without explicit training logs.\n\nWeaknesses:\n1. The paper should visualize feature representations (e.g., via t-SNE or PCA) to show how samples enjoy different levels of privacy and unlearning guarantees. \n2. As Out-of-Distribution (OOD) samples are typically less sensitive to the presence or absence of specific training data, they may not be a reliable probe for evaluating unlearning success. The current experimental setup does not convincingly demonstrate the advantage of the proposed method.\n3. The paper should include comparisons with more (e.g., DP-based) machine unlearning methods.\n4. The proposed method finetunes from a checkpoint at step $T-K$, and empirical results suggest that performance improves when $K$ is large (i.e., closer to full retraining). However, the cost savings over retraining from scratch on $\\mathcal{D}'$ are not clearly demonstrated. The paper should provide a concrete runtime and resource comparison in tasks where the model has converged, to justify practical efficiency.", "was_revised": true, "final_justification": "The rebuttal has address some of my main concerns. I have increased my rating, but without more visualization results, the effectiveness of the proposed method still may not be very clear. So I only increase the rating to 4.", "rebuttal": "Thank you for your insightful review and considerate comments. In the following, we respond to your concerns.\n\n**The paper should visualize feature representations (e.g., via t-SNE or PCA) to show how samples enjoy different levels of privacy and unlearning guarantees.**\n\nWe thank you for this suggestion. Due to NeurIPS rebuttal guidelines, we cannot provide any new plots. However, we have performed this visualization of the features, observing that the unlearned samples are indeed more dispersed after unlearning. We will include the results in our camera-ready version. \n\n**As Out-of-Distribution (OOD) samples are typically less sensitive to the presence or absence of specific training data, they may not be a reliable probe for evaluating unlearning success. The current experimental setup does not convincingly demonstrate the advantage of the proposed method.**\n\nWe only use the OOD dataset for the membership inference attack (MIA), not for direct evaluation of model performance. We agree that unlearning should have little effect on the model performance on the OOD set, and this is supported by experimental data in Tables 8, 9, 10, and 11. In fact, **we leverage this low sensitivity to make our MIA more robust**. The MIA compares the output of the model on two datasets: the unlearned data, and \"unseen\" data not present in the training set. The attack is more successful if it determines that the first dataset is more sensitive to unlearning than the second. Typically, the standard practice is to use the test set as the second dataset. However, in our framework the test set may still contain data from *users* in the training data, and will still be affected by unlearning even if the specific test samples were not used during training. Therefore, we determined that the OOD dataset, constructed specifically from *users* not present in the training data, provides a more appropriate comparison. We note that while we refer to these samples as \"OOD,\" they do not fall outside of the *classes* considered by the model and can still be reliably and accurately classified. \n\nOur other unlearning metric is performance on the unlearned dataset $\\mathcal{D} _{unlearn}$ before and after unlearning. A decrease in performance  suggests the model is losing information about the data. For additional information about our unlearning metrics and membership attacks, see Section 4.1 and B.1.1.\n\n**The paper should include comparisons with more (e.g., DP-based) machine unlearning methods.**\n\nOur work already compares against all existing DP/certified methods for **nonconvex** unlearning. Theoretically, we compare against the Constrained Newton Step (Zhang et al., 2024), the Hessian-Free method (Qiao et al., 2025), and Langevin Unlearning (Chien et al., 2024), and we also review several convex methods, as highlighted in Table 1 and Appendix E. Experimentally, we compare against CNS (Zhang et al., 2024) and HF (Qiao et al., 2025). We do not compare against convex DP/certified unlearning methods because they are not designed for nonconvex functions like deep neural networks, and we do not compare against (Chien et al., 2024) because, as stated in their paper, their result is mostly of theoretical interest and is currently too loose to be implemented in practice.\n\n**The proposed method finetunes from a checkpoint at step $T-K$, and empirical results suggest that performance improves when $K$ is large (i.e., closer to full retraining). However, the cost savings over retraining from scratch on $\\mathcal{D}'$ are not clearly demonstrated. The paper should provide a concrete runtime and resource comparison in tasks where the model has converged, to justify practical efficiency.**\n\nBy construction, R2D with checkpointing will always be more efficient than retraining from scratch, because $K \\leq T$. We provide a runtime comparison in Tables 6 and 7 in the Appendix. As expected, the runtime of R2D unlearning is directly proportional to the amount of rewinding steps, such that 20% rewinding takes 20% of the original training time to run, translating to 80% in computational savings. Our results in Table 2 suggest that even a small $K$ yields competitive performance. \n\nTables 6 and 7 also show that R2D is more practical and efficient compared to HF and CNS. In particular, although HF unlearns quickly, it requires 22-88 times more compute time during learning, highlighting the benefits of black-box algorithms that do not require complicated data-saving procedures during training. As for memory requirements, our algorithm requires $O(d)$ storage, which beats the $O(d^2)$ and $O(nd)$ requirements of CNS and HF respectively (Table 1). We note that in practice, HF actually requires $O(ndT)$ storage during training to ultimately compute the unlearning matrix, where $T$ is the number of learning iterates. This is completely intractable for moderately sized neural networks and datasets, so instead we follow their lead and implemented a scaled-down version of their algorithm that only stores the vectors of the samples we are planning to unlearn, a small fraction of the whole dataset. Even with this concession, HF requires 1.5 GB of storage for the eICU dataset and 136GB for the Lacuna-100 dataset solely during training, whereas R2D only needs to store the model weights at a checkpoint and the final iterate ($2 \\times 8$ MB for eICU and $2 \\times 45$ MB for Lacuna-100). We will update our manuscript to include these concrete comparisons.\n\n**Figure 1 is difficult to interpret. In particular, it is unclear why the classification performance on $\\mathcal{D} _{unlearn}$ in Figure 1(g) increases as the rewind depth $K$ grows.**\n\nFigure 1(a) and 1(g) show the utility tradeoff for various fixed $\\epsilon$ and rewind depth $K$, based on equation (3). More rewinding $K$ means less noise is required to achieve the same unlearning guarantee $\\epsilon$, improving the overall performance of the model, including the performance on $\\mathcal{D} _{unlearn}$. This is why 1(a) and 1(g) are similar. Figure 1(g) specifically shows that for all these varying levels of utility, the performance on $\\mathcal{D} _{unlearn}$ is lower after unlearning. We will improve the contrast on this figure to make the point clearer.\n\nIn contrast, Figure 2 plots the performance for *constant* noise (Table 2), thereby isolating the impact of rewinding. We see that rewinding *decreases* the performance on $\\mathcal{D} _{unlearn}$, while the performance on $\\mathcal{D} _{train}$ and $\\mathcal{D} _{test}$ remain relatively constant. This supports the argument that rewinding is a key component of our unlearning algorithm and erases information about $\\mathcal{D} _{unlearn}$ in the model. We will improve the notation of Figure 1 and 2 to make this distinction clearer.\n\nThank you again for your thoughtful review, and please let us know if you have any further concerns about the paper."}]

Author rebuttal:

Meta-review: This paper proposes a first-order, black-box unlearning algorithm for non-convex loss problems. The proposed algorithm works by rewinding to an earlier model checkpoint during learning and then performing gradient descent on the retain dataset. They prove the certified unlearning guarantee of the proposed algorithm and provide the privacy-utility-complexity trade-off. They also provide a generalization bound for PL problems. Finally, they test their proposed algorithm in an empirical evaluation, showing its effectiveness. 

**Strengths**
- The problem of certified machine unlearning for non-convex loss functions is important and underexplored
- The idea of rewinding for certified unlearning, while embarrassingly simple, is interesting and practically relevant 
- The proposed algorithm has theoretical guarantees on nonconvex functions, and empirically outperforms certified and non-certified methods in a wide range of benchmarks, datasets, and baselines. 
- The method does not require access to internal training dynamics or full gradient history, making it deployable in practical, real-world scenarios. Especially, Algorithm 3 introduces a proximal fixed-point iteration to approximate historical checkpoints, enabling backward recovery without explicit training logs.


**Weaknesses**
- The writing somewhat makes it not straightforward to understand, as pointed out by Reviewer PXQd. For example, the role of $K$ and the notion of "back-box" have not been elaborated well enough in the writing. 
- Some concern about the technical novelty of the paper given the algorithm is simple, but I think the authors have done a fairly good job of positioning their contribution in a broader context (see the author response in comparison with the D2D algorithm, when responding to Reviewer PXQd)

There were mixed feedbacks initially among the reviewers. After the rebuttal, the authors have successfully convinced two reviewers to turn into the acceptance front.
Decision: Accept (poster)