Certified Unlearning for Neural Networks
Authors: Anastasia Koloskova
Youssef Allouah
Animesh Jha
Rachid Guerraoui
Sanmi Koyejo
Venue: ICML 2025 poster (2025)
Keywords: machine unlearning
privacy amplification by stochastic post processing
privacy amplification by iteration
Primary area: social_aspects->privacy

Abstract: We address the problem of machine unlearning, where the goal is to remove the influence of specific training data from a model upon request, motivated by privacy concerns and regulatory requirements such as the “right to be forgotten.” Unfortunately, existing methods rely on restrictive assumptions or lack formal guarantees.
To this end, we propose a novel method for certified machine unlearning, leveraging the connection between unlearning and privacy amplification by stochastic post-processing. Our method uses noisy fine-tuning on the retain data, i.e., data that does not need to be removed, to ensure provable unlearning guarantees. This approach requires no assumptions about the underlying loss function, making it broadly applicable across diverse settings. We analyze the theoretical trade-offs in efficiency and accuracy and demonstrate empirically that our method not only achieves formal unlearning guarantees but also performs effectively in practice, outperforming existing baselines.

Certified Unlearning for Neural Networks
Anastasia Koloskova"
Youssef Allouah" *2
Animesh Jha
Rachid Guerraoui Sanmi Koyejo
Abstract
ulation (GDPR) of the European Union (Voigt & Von dem Bussche, 2017) enforce the "right to be forgotten" requir- ing organizations to delete user data upon request. However, simply removing data from storage is insufficient if the in- formation remains embedded in a trained model. This has led to the growing interest unlearning techniques, which seek eliminate the influence of specific data points while preserving the overall utility of the model. Achieving ef- ficient and reliable unlearning is particularly challenging when working with large-scale neural networks, where full retraining from scratch is computationally prohibitive.
We address the problem of machine unlearning. where the goal is to remove the influence of specific training data from model upon request, motivated by privacy concerns and regulatory requirements such as the "right to be forgot- ten." Unfortunately, existing methods rely on restrictive assumptions or lack formal guarantees. To this end, we propose novel method for certified machine unlearning, leveraging the connection between unlearning and privacy amplification by stochastic post-processing. Our method uses noisy fine-tuning on the retain data, i.e., data that does not need to be removed, to ensure provable unlearning guarantees. This approach requires no assumptions about the underlying loss function, making it broadly applicable across diverse settings. We analyze the theoretical trade-offs in efficiency and accuracy and demonstrate empirically that our method not only achieves formal unlearning guarantees but also performs effectively in practice, outperforming existing baselines. Our code available at https: httpp://github.com stai r- a htt.eaaaeeeeeeeeeeeeeeeea lerrniig--- neural - wwwp:ooooo-iiml-2-11
The idea of machine unlearning dates back to Cao & Yang (2015) and has since inspired a range of approaches. Broadly, unlearning techniques fall into two categories: ex- act unlearning, which aims completely erase the influ- ence of specific data points, and approximate unlearning, which seeks computationally efficient but approximate removal of information. While exact unlearning offers the strongest theoretical guarantees, it is rarely practical for large-scale models or frequent unlearning requests due to its prohibitive computational costs (Ginart al., 2019; Bour- toule et al., 2021). As a result, many existing methods adopt relaxed guarantees, but these often come with sig- nificant trade-offs. For instance, some approaches rely on restrictive assumptions about loss functions, such convex linear models (Guo et al., 2020), while others lack rigorous thcoretical guarantees (Graves et al., 2021; Kurmanji et al., 2024) or require extensive retraining (Bourtoule al., 2021). One common heuristic method is fine-tuning on retained data, and potentially gradient ascent on the forget data, to induce catastrophic forgetting in the affected parts of the model (Triantafillou et al., 2024). While this technique has shown promise in reducing the retained influence of forgot- ten data, it does not inherently provide certifiable guarantees of unlearning, leaving open questions about its reliability in privacy-sensitivv applications.
1. Introduction
Machine unlearning- process of removing the influ- ence of specific training data from a model-has become an increasingly important challenge in modern machine learn- ing (Nguyen al., 2022). With the widespread adoption of deep learning in fields such healthcare, natural language processing, and computer vision, concerns over data privacy, security, and control have grown significantly. In particular, regulatory frameworks like the General Data Protection Reg-
To address these limitations, propose mate unlearning framework that builds on the concept of privacy amplification by stochastic cost-processing (Balle et al., 2019). Our method leverages noisy fine-tuning on retained data to enforce provable unlearning guarantees while maintaining computational efficiency. Unlike exist- ing approaches, our framework does not impose restrictive assumptions the loss function, making it particularly
approxi-
Stanford University, USA "EPFL, Switzerland. Conresonndence to: Anastasia Koloskova <anakolos@ @stanforrdcadu.. Youssef Allouah cyoussef.allouah@eee @fh.....
'Equal contribution
Proceedings of the nnnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Certified Unlearning for Neural Networks
well-suited for non-convex optimization problems such as deep learning. We interpret each noisy fine-tuning step as form of stochastic post-processing, ensuring that privacy improves progressively with each iteration while balane- ing the trade-offs between accuracy and computational cost. Through rigorous theoretical analysis and extensive empir- ical validation, we demonstrate that our method provides both formal guarantees and strong practical performance, making it viable solution for real-world machine learning applications where frequent unlearning requests must be handled efficiently.
inapplicable to neural networks. Most prior methods rely restrictive assumptions about the model or loss function that do not hold for deep learning.
Several works focus on convex tasks (Guo et al., 2020; Neel et al., 2021; Sekhari et al., 2021; Allouah et al., 2025), but this limits their applicability to deep learning. These methods work in practice for logistic regression tasks and do not extend to neural networks due to non-convexity.
Recent works aim to achieve certified unlearning for non- convex tasks (Golatkar et al., 2020; Chourasia & Shah, 2023; Chien et al., 2024; Mu & Klabjan, 2024; Zhang et al., 2024; Allouah et al., 2025), but still impose significant constraints.
Our key contributions can be summarized as follows:
All require the loss function to be smooth, limiting them to networks with smooth activations. Most (Chourasia & Shah, 2023; Chien al., 2024; Mu & Klabjan, 2024) also require knowledge of the smoothness constant, restricting appli- cability to simpler models where this constant is tractable. Furthermore, Allouah et al. (2025) additionally assumes a unique minimizer, excluding virtually all practical neu- ral architectures. Zhang et al. (2024) additionally requires knowledge of the minimal eigenvalue of the Hessian at the unique optimal model. To the best of our knowledge, our ap- proach is the first certified unlearning method that supports arbitrary non-convex tasks, enabling provable unlearning guarantees for practical deep learning models.
A novel certified unlearning method that integrates noisy fine-tuning with privacy amplification by stochastic post- processing, offering principled approach to approxi- mate unlearning.
Rigorous unlearning guarantees that do not depend on restrictive assumptions such as loss function smoothness, making the method applicable to broad range of models, including deep neural networks.
Empirical validation in deep learning applications, demonstrating that our approach not only meets formal unlearning guarantees but also surpasses existing base- lines in performance and model utility.
1.1. Related Work
Unlearning applications. A separate line of research fo- cuses on concept unlearning, which aims to remove specific topics or themes from language models, beyond forgetting particular training samples (Liu et al., 2024). For instance, work in this domain has explored techniques for eliminat- ing knowledge of topics like "Harry Potter" or other po- tentially harmful or unethical content from large language models (Eldan & Russinovich, 2023). These methods of- ten involve intervention at the representation or knowledge distillation level, rather than enforcing formal guarantees of data removal. In contrast, our work focuses on data point unlearning, ensuring that information associated with specific training samples is provably removed while pre- serving model utility. Other explored unlearning settings include unlearning in graph neural networks (Chien et al., 2022), in min-mav optimization settings (Liu et al., 2023), and the adversarial setting with the server possibly forging unlearning (Thudi et al., 2021).
Amplification by post-processing. Our approach is inspired by privacy amplification via stochastic post- processing, a concept in differential privacy where random- ized transformations that do not use private data enhance privacy guarantees. The foundational work of Feldman et al. (2018) introduced privacy amplification by iteration, demonstrating that when training with differentially private stochastic gradient descent (DP-SGD) on convex objectives, the privacy of an unused training sample improves with the number of optimization steps. Balle et al. (2019) extended this result, refining the analysis of amplification by iteration and introducing amplification by mixing, which establishes that privacy is further strengthened when applying a Markov kernel satisfying specific mixing conditions. Subsequent work by Asoodeh et al. (2020) showed that under bounded domain assumptions, these mixing conditions hold for the Gaussian mechanism, leading to tighter privacy guarantees for DP-SGD. Our proposed unlearning framework basedd on noisy fine-tuning on retained data-operates as a stochas- tic post-processing step that does not access the data to be forgotten. Thus, we extend privacy amplification techniques beyond convex settings to enable certified unlearning in deep learning models.
2. Problem Statement
We consider model & Rd trained using algorithm A on dataset D of n training examples, i.e., x = A(D). We place no restrictions on A; it may be SGD, Adam, momentum- SGD, etc. An unlearning request specifies a subset Dy C D, referred to as the forget set, which we wish to erase from the model. Ideally, we could retrain the model from scratch on
Certified unlearning. There is a growing body of work on certified unlearning, but existing approaches are largely
2

---

Certified Unlearning for Neural Networks
the retain set D Dy. yielding x A(D Dÿ), but this is often computationally prohibitive. Instead, we aim to design an approximate unlearning algorithm U/ that outputs model retaining "no information" about D.. To this end, 2/ takes as input the original model & = A()). the unlearning request Dy, and the full training dataset D. Formally, unifying several prior definitions (Ginart et al., 2019; Guo et al., 2020), we require 2/ to satisfy the guarantees below.
in practice, as the required noise magnitude is large, which can significantly degrade the utility of the model.
Another baseline is retraining from scratch, where the for- get dataset D is discarded, and the model is retrained from scratch on the remaining data D DD using the algorithm A. Although this guarantees perfect unlearning (i.e., (0, 0)- unlearning). it is computationally expensive and requires substantial memory resources. which undermines the effi- ciency objectives of approximate unlearning.
Definition 2.1 ((e, Junleaarnn Let & 2 0,6 E [0, 1]. We say that U is (e, -uunlearni algorithm for A if there exists a certifying algorithm A, such that for any forget and initial datasets D C 'D and any observation O E Rd,
3. Algorithm
Our approach is based on fine-tuming the model with stochas- tic gradient descent (SGD) using only the retained data D Dy, while incorporating regularization. Recall that in this approach, we initialize from the original model & and update it for T 2 1 iterations as follows for every t E (O.....T-1) 1-1::
PH D,) = 0] e 0] + 6, Pr[A(D)P))) = OJ S ef PT[M(A()) D, Dy) = 0] +
For simplicity, we refer to approximate unlearning as 0)
unlearning for some values of и and 6, inspired by () differential privacy (Dwork Roth, 2014). This formulation parallels differential privacy by treating D as "private" and D \ D as "public," thereby ensuring (e, -)-rrivacy for the forget set. Indeed, this notion ensures it is statistically difficult to distinguish the output of the unlearning algorithm U from that of a certifying algorithm A that has no access to the forget set Dy.
X,+1 Xx - (gg + AXx),
XD X,
(2)
where ge is the stochastic gradient computed on the retained data, Y is the learning rate, and À a regularization parameter.
While this method may induce some empirical forget- ting due to the phenomenon of catastrophic forgetting in SGD (Goodfellow et al., 2013), it does not provide formal (e, d0-uneaggn as required by Definition 2. 1. Therefore, to frame each fine-tuning step as a stochastic post-processing operation (Balle et al., 2019) applied to the initial model x, we introduce gradient clipping and model clipping, both combined with Gaussian privacy noise. These modifica- tions allow us to map the process to different stochastic post-processing mechanisms (Balle al., 2019).
Importantly, the definition does not fix A but only requires its existence, allowing flexibility to capture various prior definitions. For example, setting A = AA recovers defini- tions from (Ginart et al., 2019; Guo et al., 2020), while setting A = U(A(D) \ D \ Dy. 2) aligns with (AI- louah et al., 2025; Sekhari et al., 2021). We primarily adopt the latter form in this work. Note that our choice of the certifying algorithm A is purely theoretical and does not require rumning additional computational steps in practice. Finally, we emphasize that Definition 2.1 naturally supports non-adaptive sequential unlearning, where data points are removed one-by-one without revisiting earlier removals.
Gradient clipping. Our primary approach relies on gra- dient clipping, where we clip gradients before applying updates, followed by noise addition. This method resembles standard DP-SGD (Abadi et al., 2016) but differs in that gradient updates exclude any "private" (forget) data points:
Baselines. We now describe two straightforward baselines for achieving (s, Junnlerrnin The first baseline is outpul perturbation, which applics the standard Gaussian mech- anism to the original model & The procedure involves clipping the model parameters to ensure bounded sensitivity and adding Gaussian noise to the model's 's output. Formally, the unlearning procedure is defined as:
X9 = -TTc, (X):
X,+1 = X1 - (Ilo, (gr) + Axx) + Ex41s
where Ex+1 (N(0, is Gaussian noise and Ic. Te are the clipping operators of radius Co > 0 and C1 > 0 respectively'. We analyze this method in the theoretical framework of privacy amplification by iteration (Feldman et al., 2018), to show that redistributing noise across mul- tiple steps enables a reduction noise at the initial step while maintaining strong privacy guarantees. This noise reduction retains the original model's performance. The reg- ularization with parameter À additionally allows implicitly
Xo= = -Icc (x) + Eo: Eo L (0, SCB In In(1.25/8)
where Ilc. represents the clipping operation, and E, is noise sampled from the Gaussian distribution, with sufficient mag- nitude to ensure privacy (Dwork & Roth, 2014). While the- oretically sound, output perturbation often performs poorly
Following standard differential privacy mechanisms, our clip- ping is by norm, i.c., [c(x)) == x ming C 1) with radius C.
[XT
3

---

Certified Unlearning for Neural Networks
controlling the norm of the model x, that is increased due to the presence of the noise E.-
functions to the non-convex case. The key ingredient in our analysis is the shift-reduction lemma (Lemma A.6), which enables us to control the growth of the Rényi divergence between (i) the unlearned model initialized from the full model and (ii) the unlearned model initialized from training only on the retained data, across iterations.
Model clipping. An alternative approach involves model clipping, where each update is clipped to a predefined radius before noise addition:
X = x
Unlike the original privacy amplification by iteration frame- work, which assumes smoothness and convexity of the loss function (Feldman et al., 2018), our approach circumvents these assumptions by introducing gradient clipping. This is reflected in the sufficient noise magnitude required to achieve (e, Junllarn,, as given in (5). Specifically, in the absence of regularization À = 0, gradient clipping at threshold C1 induces dependence of the form:
(4)
X(+1 = IIc, (x: - (g: + xxx)) + Er+1:
where f1-1 ~ (2a)) and E. ~ (N, La)) Since the gradient g: is computed solely on the retain data, the argu- ment of the clipping operator can be interpreted
post- processing transformation of the private model, given by the mapping (xx) := X, (x(=+ The clipping and noise addition ensure differential privacy guarantees (Dwork & Roth, 2014). Standard results on post-processing state that such transformations preserve or improve existing differen- tial privacy guarantees. Additionally, privacy amplification by stochastic post-procsssing (Balle et al., 2019) suggests that each additional step can further enhance privacy beyond that of the previous model.
o² 02=0(Lo(())) (00(1((1/0) 62
( +
Intuitively, for a large enough number of iterations, we can trade off the effect of the initial clipping radius Cg for a minor cost proportional to the learning rate y and the per- iteration clipping radius Cj. Fortunately, this cost can be controlled by choosing sufficiently small learning rate 7 In particular, if
4. Theoretical Analysis
Co. then asymptotically in T we get C
a2 = O Co 1og((11/)) This implies that the required noise =T
We now present the approximate unlearning guarantees of the gradient and model clipping variants of our unlearning method introduced in the previous section. We also theo- retically compare these with previous non-convex certified unlearning algorithms. We defer all proofs to Appendix A,
magnitude decreases as the number of iterations T increases, ultimately tending to zero in the limit T + co.
Given Co, C₁ and y, we can upper bound the optimal num- ber of unlearning steps by minimizing (7). Specifically, setting T larger than
4.1. Unlearning Guarantees
We first present in Theorem 4.1 the unlearning guarantees of the Gradient clipping approach, as defined in Equation (3).
{
C T
+ TTT = Co 70
T == arg min T
Theorem 4.1 (Gradient clipping). Lei 2 1, > 0, 0, 8 E 1)  e (0, 30 log((/))) Consider T iterations of the unlearning algorithm defined in (3). We obtain (c, unlearning if:
leads to more iterations (T'> T*) with increased noise per iteration (ør 2 GT- by definition of T*), while achieving the same (e, 6) -unlearrnn
Finally. in the regularized case > O, the noise expres- sion (6) for achieving (c, -uunlearnig simplifies to:
1. Without regularization (A A= 0):
9log(1/8)
0² = =o -0(2log(11 (xc3 (xp-ex)(-XxT) + - ) (8)
a²
(Co + CCTT) E²T
(5)
22
2. With regularization (A (>>00 0): if E (2,11) and
Here, regularization enables an exponential reduction in T of the dependence on the initial clipping threshold Co. effectively mitigating its impact over time. However, this comes the cost of an increased dependence on the per- iteration clipping threshold C1 scaling inversely with the regularization factor X. While this suggests a smaller noise magnitude per iteration, overly strong regularization may degrade the model's 's performance, as we further analyze in the next section. Finally, we provide a refined, but complex, formula for noise magnitudes in Theorem A.9 (appendix)
0² 12>>log(118) Co (co(1-
+ 9
(6)
The proof relies on techniques from privacy amplification by iteration introduced by Feldman et al. (2018). which is a form of privacy amplification through stochastic post- processing (Balle et al., 2019). We extend the original anal- ysis Feldman et al. (2018) that is applicable only to convex
4

---

Certified Unlearning for Neural Networks
using Rényi divergences, which we apply before precise Rényi-to-DP conversion (Balle al., 2020) in practice.
effective method should minimize noise per iteration while keeping the number of iterations reasonable to preserve model accuracy. Since all methods rely noisy updates, we focus on the magnitude of noise injected. A summary of our findings is provided in Table 1, with details below.
Next, we state the unlearning guarantees of the Model clip- ping approach, as defined in Equation (4).
Theorem 4.2 (Model clipping). Let 2 1, Co, 00,0
and 8 E (0, 1). Denote for every r > 0,
Output perturbation. We recall that this is a natural baseline, defined in (1), whereby we first project the orig- inal model with clipping threshold Co and add noise of magnitude o² Sim(1.25/8)Cá which guarantees (2, unlearning for E, 8 E (0. following (Dwork & Roth, 2014, Theorem A.
(r(r) = Q ( - - EQ ( + 2
(9)
where for all t E R. Q(t) = VZx S. epe
Consider T iterations of the unlearning algorithm defined in (4). We obtain (e, 8))-m))armninn if
1og(1/5) + log ( (200)
DP training. Training with DP guarantees unlearning for free; we do not need to inject noise after receiving unlearn- ing requests. However, the noise needed may be larger than with other unlearning methods. Indeed, consider unlearning set of l samples with DP- JP-SGD. For this, we need group- DP: if a mechanism is (s, 5)-DP for single-record changes, then it is (KE, O) for any pair of datasets that differ in S l records (Vadhan, 2017, Lemma 2.2). Consequently, to attain the same (s, -umlearnnn guarantee one must run g² (In( 1.25k) + kz). This is
T
(10)
log (1/Oa 2()))
In particular, for any T 2 1, (0, 1), it suffices to have
0² 8C3 (1..5)
1 + T [n([125/0]- oße²
1
62
8C8
(11)
The proof of Theorem 4.2 relies on recent advances in privacy amplification by stochastic post-processing due to Balle et al. (2019) and Asoodeh et al. (2020). The initial iter- ation in (4) provides (Eu, 66) unlearning since it is the stan- dard Gaussian mechanism from differential privacy (Dwork & Roth, 2014). Moreover, assuming that the model at step of Algorithm (4) guarantees (E,, 6.)-ullra,,,, using the contraction coefficients (Asoodeh et al., 2020) approach, we show that the next iteration amplifies the unlearning guarantee as follows:
DP-SGD with noise 0² = 20* typically much larger noise than with our techniques, given that it is at least quadratic in k, which may scale with the size of the dataset. This is in line with recent findings on the theoretical separation between DP and certified unleam- ing (Sekhari et al., 2021; Allouah et al., 2025).
Gradient clipping. From Theorem 4.1, T 2 1 itera- tions of Gradient clipping (3) with noise magnitude o² 9 (log(1/6) (Co + CiTT)² satisfies (s, -)nlleanng assum- ing E & (lo((1/)). Setting T = Co minimizes the noise to
(e+118841) (Ec, 0g( (C 6z),
70,
where the expression of the amplification factor 0,( (C²2
C6, (1g(1
(0, 1) is given in (9). This means that after T' iterations, our algorithm guarantees (Er, = (Eo. (e (²C2)T TT)) 5u) unlearn- ing, Stated differently, given any target e, 8 and any noise magnitudes o², o and clipping thresholds C1, Co we show that it sufficient for the number of iterations to be at least that in (10) to guarantee (e, -0-nllarnnn
(12)
This substantially reduces noise per iteration compared to output perturbation by a factor of Ca. which is significant when y < &.. A small learning rate or large initial clipping Co can make this method particularly effective in preserving model accuracy.
Ciy.
While the expression of the amplification factor 0,(20: a given in (9) is complex, we remark that it is decreasing function of taking values in (0, 1). In fact, assuming that e E (0, 1), and given any number of iterations T, we state a simple expression of the sufficient noise magnitude o² in (11). This simplified expression is only for analytical purposes, since it gives looser unlcarning guarantces.
For the regularized version of gradient clipping we recall that noisy gradient descent with T iterations and constant noise level, given by the expression 2² = 727 (og(8) (1 (1-- x) 2 satisfies (c,
unlearning under the assumption e I 3 log(118). Setting T= 1 log( ACo of Ci
nd
4.2. Theoretical Comparison
0² - L9ylog(1/8)
(13)
A
To compare the various unlearning methods, we analyze the number of iterations required and the noise injected per iter- ation to achieve the same (c, Junleanngg guarantee. An
This approach outperforms the unregularized variant when Ci requiring only logarithmic iterations in the initial
X > co
5

---

Certified Unlearning for Neural Networks
Algorithm
Variance of Noise Injected
Assumptions
Max. per lteration
Iterations
Output Perturbution (buseline)
C3
Gradient Clipping
CC
Co/1C
Grudient Clipping (w/ regularization)
7C//X
log (ACa/Cil/1A
Model Clipping (4)
C2
log(1/8)
Lungevin Diffusion (Chourasia & Shuh, 2023)
no explicit expression
smoothness, boundedness, noisy training
Rewind-to- to- Delete (Mu & Klabjan, 2024)
exponentiol in smoothness consiont
smoothness, noisy training
Table 1. Summary comparison of certified unlearning accountants for non-convex tasks. Co: initial clipping threshold, C1/C2: running clipping threshold for gradient and model clipping resp., "y: learning rate, A: fz-regularization factor. We ignore absolute constants and multiplicative factor log(1/5) which is in the noise variance of all methods. We note that the entry "Langevin Diffusion" also covers the work of Chien et al. (2024). Model Clipping and Grudient Clipping algorithms effectively reduce the maximum noise per iteration at the cost of doing more noisy SGD steps compared the output perturbation. More details on the comparison given in Section 4.2.
clipping radius Cp. This suggests that projecting onto a larger set can better preserve accuracy, though may require stronger regularization, which could degrade performance in some tasks.
and are tailored specific training algorithms. For instance, Chourasia & Shah (2023) and Chien et al. (2024) analyze training with noisy projected gradient descent, leveraging both smoothness and specific training dynamics to establish unlearning guarantees, These guarantees stem from the con- vergence of the training process to a limiting distribution, but additional restrictive assumptions are required. Notably, the smoothness constant needed not only for theoretical analysis but also to determine the appropriate noise level at each step achieve (c, 8) 6)-uleearn This constraint limits the applicable function class to those where the smoothness constant is easily computable, effectively excluding modern neural networks. Chourasia & Shah (2023) assume that the loss function is bounded, while Chien et al. (2024) require that the training's limiting distribution satisfies an isoperi- metric inequality. These constraints significantly limit the applicability of their methods, primarily to smooth con- vex tasks such logistic regression (Chien et al., 2024). Similarly, Mu & Klabjan (2024) address non-convex loss functions but assume that training follows gradient descent with output perturbation. Their approach also relies on smoothness and requires injecting noise with a magnitude that scales exponentially with the smoothness parameter, which can be prohibitive in practice. In contrast, our ap- proach removes these smoothness constraints and is not tied to a specific training algorithm, making it applicable to broader class of learning problems.
Model clipping. We recall from Theorem 4.2 that T 2 iterations of Model clipping (4) with noise magnitude
0² 8C3 lm(2225)
8C2 ln(1.)5)
oā=²
In(1.25/0)
Ts²
808
is provably sufficient to achieve (e, uullearingg As- sume that the initial noise magnitude oß at most 8C (5112)/ as the latter magnitude is sufficient to obtain (c, unnlearnnn in one iteration in the output pertur- bation baseline. Therefore, the order of magnitude of the minimum value of the noise
0² 8C2 ln(.25))
(14)
g2
can be attained within T In (1225/0) iterations. This represents significant improvement over the baseline, re-
ducing the noise per iteration by factor of Cā If C2 is C
small or if the initial clipping threshold Co is aggressive, this reduction can be substantial. Compared to amplifica- tion by iteration, this method requires fewer iterations (only logarithmic in 1/5), though it may introduce more noise per iteration when the learning rate small.
5. Experimental Evaluation
Prior works. Existing certified unlearning methods that do not assume convexity of the loss function in- clude (Chourasia & Shah, 2023; Chien et al., 2024: Mu & Klabjan, 2024). However, unlike approach, these meth- ods rely on the assumption that the loss function is 2
In this section, we present an empirical evaluation of our proposed unlearning method, in its two variants Gradient Clipping (3) and Model Clipping (4), on two benchmark datasets: MNIST (Deng, 2012) and CIFAR-10 10 (Krizhevsky et al., 2014). We first detail the experimental setup, and then describe the results and observations stemming from
That is, for some I. 2 0, by denoting the loss function, have [[V((x) v<(y)] & T. || - y for x,y Rdd
6

---

Certified Unlearning for Neural Networks
0.51
0.50
0.50
0.75
Validation Actu/ac)
0.45
Vallddatoon Accuracy
01.11
0.40
0.65
0.35
0.30
0.5
Output Perturattion c-1
Rwtrei" from szracch a0
Curpui Pnrturbation ce1
Actroin from scratch c-0
soird cloping c-1
Hodel Casping s-1 ceacheen mml..
020
arodle capping t010
Compute Budget (Epacho)
Compute Budget (Epochs)
(a) CIFAR-10
(b) MNIST
Figure 1. Accuracy Gradient and Model Clipping versus compute budget (epochs) on CIFAR-10 10 (left) and MNIST (right), to satisfy (1, 1010--5 11,10-5)-unlennnn -unnlarnnng We compare baselines: retraining from seratch and output perturbation, detailed in Section 2. Across all the compute budgets gradient and model clipping achieves higher accuracy than the basclines, with the difference being larger for smaller compute budgets.
Accuracy
Baselines
Noisy Fine-Tuning (ours)
Retrain
Output Perturbation
Gradient Clipping
Model Clipping
30%
6
5 (es 16 % faster)
4 (s= 33 % faster)
(#= 50 % faster)
35%
11
7 41 % faster)
6 (Rs 50 % faster)
(ts faster)
40%
18
12 (se 33 % faster)
10 (te 44 % faster)
10 (ec 44 % faster)
45%
23
17 (Ae 26 % faster)
16 (As 30 % faster)
17 (e: 26 % faster)
50%
30 25 (Ao faster)
23
faster) (#: 20 % faster)
Table 2. Number of epochs required to reach the target accuracy for our algorithms and the baselines, and their saving compared to retraining from scratch for the CIFAR-I0 dataset. Gradient Clipping and Model Clipping consistently save above 20% of compute, sometimes reaching 50% of compute savings, The output perturbation baseline also consistently improves over the retrain from scratch, however is consistently slower than the Gradient and Model clipping algorithms.
Table 2 and Figures and
the best of our knowledge, no existing method provides cer- tified unlearning guarantees for non-convex tasks without requiring knowledge of the smoothness constant of the loss function.
5.1. Setup
For MNIST, we train a small neural network with two layers and approximately 4,000 parameters. For CIFAR-I0, we use a slightly larger network with two convolutional blocks followed by a linear layer, totaling 20,000 parameters. In both cases, the forget set consists of randomly selected 10% subset of the full dataset.
Procedures. When retraining from scratch, the model is reinitialized using the same distribution as in the original training phase. In all experiments, we first train a model on the entire dataset until convergence. We set = 1, = 10-5 for experiments. For our unlearning algorithms, we continue clipping and adding noise until the desired (s, 8)- unlearning guarantee met. In all experiments, the privacy target is reached before exhausting the iteration budget, in less than 100 iterations (see Appendix B for the exact num- ber of unlcarning steps to reach target privacy). We there- fore continue fin-ttning the model on the retained dataset without additional noise or clipping, using the same hyper- parameters as in retraining from scratch. This means that in
Baselines. We compare our methods against two baselines presented in Section 2: retraining from scratch and output perturbation (1). Retraining from scratch involves fully re- training the model after removing the forget set. Output perturbation applies noise directly to the final model param- eters to achieve certified unlearning, before fine-tuning the model on the retain data if the compute budget allows. To

---

Certified Unlearning for Neural Networks
variants, consistently achieves higher accuracy compared to output perturbation and retraining from scratch across all compute budgets. This improvement is particularly pro- nounced in low-compute settings, where retraining from scratch struggles to recover performance due to the limited number of optimization steps. In contrast, our methods ef- fectively leverage the retained model parameters, enabling faster recovery while ensuring certified unlearning. This provides substantial savings, for example, to reach ac- curacy of 40% on CIFAR dataset, both gradient and model clipping needs only 10 epochs, while output perturbation needs 12 epochs (20% longer), and retrain from scratch requires 18 epochs (=s 80% longer).
03
Veldetion Accurssy
1100 Wy 3crts
0.-
Doeetnn ng (Gradient clyping
Navey Scepe (Gradert Chpppegs
netoer Scratch
Thiined Mode
Pandom
12 15
10
21
26
27
Untaaming Progression [Epachs)
Figure 2. Convergence behavior of Gradient Clipping with 7y 0.01, Co 20, C1 10, À 50, 0.25 and the retraining from scratch baseline on the CIFAR-10 dataset. The gradient clipping method is applied for the first 30 iterations, followed by standard fine-tuning. Initially, gradient clipping degrades per- formance but retains useful information, allowing fine-tuning to recover and surpass the retraining baseline quickly.
As the compute budget increases, the performance gap be- tween our methods and retraining from scratch gradually narrows. This suggests that while algorithms provide strong advantage in essurce-constrriinee scenarios, full retraining may still be the optimal choice given sufficient computing power. However, we note that in practical set- tings, where compute resources are finite, our approaches offer substantial time savings to reach a particular accuracy.
all of our experiments unlearning is cheap and effectively finds a new initialization for the finetuning process, that preserves some information from the original model All training, unlearning, and fine-tuning phases use stochastic gradient descent (SGD) with constant step size. Further experimental details are provided in the appendix.
Convergence curve. In Figure 2, we illustrate the con- vergence behavior for the gradient clipping algorithm on the CIFAR-10 dataset with parameters y = 0.01, Co 50. In that case, unlearning is
20, C = 10, and performed for the first 30 iterations, which significantly decreases the accuracy of the original model to almost zero. However, during the fine-tuning stage, the accuracy quickly catches up and outperforms retraining from scratch in around 1 epoch. This suggests that our stochastic post- processing approach does not completely erase all prior training. Despite the bad accuracy initially, the model can recover the useful information stored in it quickly. A similar convergence curve is observed in all other settings, as un- learning is always performed for relatively small number of steps (< 100, see Appendix B). These findings highlight the robustness of our approach and its adaptability across different datasets and model architectures.
5.2. Results and Observations
We now present our experimental comparison. We compare the algorithms for fixed target accuracy and fixed compute budget, and finally show convergence behavior.
Fixed target accuracy. In Table 2, we present the time required for each algorithm to reach the target accuracy for unlearning on CIFAR-10. Our results show that both gradient clipping and model clipping achieve the desired accuracy a comparable number of steps, significantly outperforming the baseline methods. Notably, compared to retraining from scratch, algorithms offer substantial computational savings-reducht to 50%. Interestingly, while the simple output perturbation baseline also improves upon retraining from scratch, its efficiency gains are less pronounced. This suggests that while output perturbation approach can be beneficial, more advanced unlearning methods such gradient and model clipping yield considerably greater improvements.
Overall, we observe that both variants of our method- gradient and model clipping-achieve considerable gains of up to 50% of time savings over the baselines. Further analysis of our results shows that the noise magnitude and clipping strategies play crucial role in balancing unlearn- ing guarantees with model utility. We found that gradient clipping has a larger range of hyperparameters that achieve an advantage over the baselines, making it casier to tune.
the required steps by up
Fixed compute budget. On Figure 1, we show the re- sulting accuracy for varying compute budgets for gradient and model clipping approaches on MNIST and CIFARI0 datasets. Our experiments demonstrate that our proposed unlearning method, both its gradient and model clipping
5.3. Transfer Learning and Comparison with DP-SGD
To evaluate our methods in more complex settings, we con- ducted experiments on CIFAR-100 and CIFAR-10 using ResNet architectures (He et al., 2016) pretrained on public
8

---

Certified Unlearning for Neural Networks
0.6
0.85
0.5
Valldst Accurasy
0.80
Val halidotton Accu/acy
044
0.3
0.70
0.2
045
Metran DP-SCD Lm2
01
RetTART C-0
060
(3-500 c230
Gondent Capping
000
orddentcispnn 2-10
22
Compute Budget (Epacha)
Compute Budget (spochs]
(a) CIFAR-10
(b) CIFAR-100
Figure Accuracy Gradient Clipping versus compute budget (epochs) on CIFAR-10 (left) and CIFAR-100 (right) using a ResNet-18 feature extractor pretrained public data, satisfy (1, 10 --ulllrrnn,
data (ImageNet (Deng et al., 2009)). This setup, where unlearning applied to the last few layers of pretrained model, has become standard in recent certified approximate unlearning works (Guo et al., 2020; Chien et al., 2024), al- though the latter works focus on logistic regression task. More precisely, we remove the last layer of ResNet-18 (pre- trained on public data) and replace with a 3-layer fully connected neural network head, which makes the task non- convex. We first train the head the full data, and then unlearn the forget data from the head. While unlearn only the head, certify the whole model because the frozen feature extractor is public and unchanged. In this setting we also compare against DP-SGD with group-privacy base- line as defined Section 4.2, this produces a certified un- learnt model, so we spend the unlearning compute budget on finetuning the model on the retain data. On CIFAR-10 method attains 85 % accuracy in 9 epochs, 10 % faster than retrain and 47 % faster than DP-SGD (Fig. 3). The gap widens on CIFAR-100: we reach 60 % accuracy in 32 epochs versus 34 for retrain, while DP-SGD never exceeds 20 within the 50-epoch budget. The poor DP-SGD curve confirms the theoretical predictions from Sec. 4.2: group- privacy forces vk more noise, being the number forget samples, and thus hurts accuracy even under much weaker privacy budget = 50 vs. our
set, our methods achieve both theoretical soundness and practical effectiveness, outperforming existing baselines in empirical evaluations.
Despite these strengths, our approach has certain limita- tions. First, the effectiveness our method constrained by the curse of dimensionality inherent in differential pri- vacy, which can make scaling to models with very large numbers of parameters more challenging. Second, our un- learning framework is designed specifically for stochastic gradient descent (SGD) during the unlearning stage, do not retain memory from earlier steps. However, this restriction does not apply to the initial model training or post-unlearning fine-tuning, allowing for flexibility in those phases. Future work could explore extensions to more complex architectures and alternative optimization meth- ods, potentially improving scalability while maintaining strong unlearning guarantees. Our findings highlight the feasibility of certified unlearning in realistic deep learning settings for the first time, offering promising direction for and efficient machine learning.
Impact Statement
This paper presents work whose goal is to advance the field of Machine Learning. There many potential societal consequences of our work, none of which we feel must be specifically highlighted here.
6. Conclusion and Future Work
introduced a new certified machine unlearning method that provides formal guarantees while remaining broadly ap- plicable modern neural networks. Our approach leverages the connection between unlearning and privacy amplifica- tion through stochastic post-processing, enabling effective removal of data influence without imposing assumptions on the loss function. By applying noisy fine-tuning to the retain
A Acknovledgements
SK acknowledges support by NSF 2046795 and 2205329, IES R305C240046, ARPA-H, the MacArthur Foundation, Schmidt Sciences, OpenAl, and Stanford HAI YA acknowl- edges support by SNSF grant 200021

---

Certified Unlearning for Neural Networks
References
Deng, L. The mnist database of handwritten digit images
for machine learning research. IEEE Signal Processing Magazine, 29(6): 141-142, 2012.
Abadi, M., Chu, A., Goodfellow, I., McMahan, H. B., Mironov, I., Talwar, K., and Zhang, L. Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC conference on computer and communications security, pp. 308-318, 2016.
Dwork, C. and Roth, The algorithmic foundations of differential privacy. Foundations and Trends@ in Theo- retical Computer Science, 9(3-4):21 1112111477, 2014.
Allouah, Y., Kazdan, J., Guerraoui, R., and Koyejo, S. The utility and complexity of and out-of-distribution ma- chine unlearning. In The Thirteenth International Con- ference Learning Representations, 2025.
Eldan, R. and Russinovich, M. Who's harry pot- ter? approximate unlearning in llms. arXiv preprint arXiv:2310.02238, 2023.
Feldman, V., Mironov, I., Talwar, K., and Thakurta, A. Pri- vacy amplification by iteration. In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pp. 521-532. IEEE, 2018.
Asoodeh, S., Diaz, M., and du Pin Calmon, Contraction of F divergeeee and its applications privacy. 2020. URL https: http::::/appaaaaaapae http:/pp..seaaancccco........a.. CorpusID:25680830
Ginart, A., Guan, M., Valiant, G., and Zou, Y. Making ai forget you: Data deletion in machine learning. Advances in neural information processing systems, 32, 2019.
Balle, B., Barthe, G., Gaboardi, M., and Geumlek, J. Privacy amplification by mixing and diffusion mecha- nisms. In Neural Information Processing Systems, 2019. URL https: /tmps::/ap0/
Golatkar, A., Achille, A., Ravichandran, A., Polito, M., and
CorpusID: 68170121.
Soatto, S. Mixed-privacy forgetting deep networks. 2021 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pp. 792-801, 2020. URL.
Balle, B., Barthe, G., Gaboardi, M., Hsu, J., and Sato, T. Hypothesis testing interpretations and renyi differential privacy. In International Conference on Artificial Intelli gence and Statistics, pp. 2496-2506. PMLR, 2020.
Corpus ID:22967:222
Bourtoule, L., Chandrasckaran, V., Choquette-Chood C. A., Jia, H., Travers, A., Zhang, B., Lie, D., and Papernot, N. Machine unlearning. In 2021 IEEE Symposium Security and Privacy (SP), pp. 141-159. IEEE, 2021.
Goodfellow, I. J., Mirza, M., Xiao, D., Courville, A., and Bengio, Y. An empirical investigation of catastrophic for- getting in gradient-based neural networks. arXiv preprint 2013.
Cao, Y. and Yang. J. Towards making systems forget with machine unlearning. In 2015 IEEE Symposium on Security and Privacy, pp. 463-480, 2015. doi: 10. 11110//PP.0.....0
Graves, L., Nagisetty, V., and Ganesh, Amnesiac ma- chine learning. In Proceedings of the AAAI Conference Artificial Intelligence, volume 35, pp. 11516-11524, 2021.
Chien, E., Pan, C., and Milenkovic, O. Certified graph unlearning, 2022. URL BtLhhttss///rxivo http:///.aa.w/aaaaba// /bs/ 2206.09140.
Guo, C., Goldstein, T., Hannun, A., and Van Der Maaten, L. Certified data removal from machine learning models. International Conference on Machine Learning, pp. 3832-3842. PMLR, 2020.
Chien, E., Wang, H. P., Chen, Z., and Li, P. Langevin unlearning: A new perspective of noisy gradient de- scent for machine unlearning.
He, K., Zhang, X., Ren, S., and Sun, J. Deep residual learn- ing for image recognition. Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 770-778, 2016.
The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024. URL https:://///.. / http//pppneeveeee...eee forum? dd33kkuC&rby..
Krizhevsky, A., Nair, V., and Hinton, G. The cifar- 10 dataset. online: http://www. cs. toronto. edu/kriz/cifar, html, 55 (5), 2014.
Chourasia, R. and Shah, N. Forget unlearning: Towards true data-deletion in machine learning. In International Con- ference on Machine Learning, pp. 6028-6073. PMLR, 2023.
Kurmanji, M., Triantafillou, P., Hayes, J., and Triantafillou. E. Towards unbounded machine unlearning. Advances in Neural Information Processing Systems, 36. 2024.
Deng. J., Dong, W., Socher, R., L.-J., Li, K., and Fei-Fei, L. Imagenet: A large-scale hierarchical image database. In 2009 IEEE conference on computer vision and pattern recognition, pp. 248-255 leee, 2009.
Liu, J., Lou, J., Qin, Z., and Ren, K. Certified minimax unlearning with generalization rates and deletion capacity.
10

---

Certified Unlearning for Neural Networks
In Proceedings of the 37th International Conference on Neural Information Processing Systems, NIPS '23, Red Hook, NY, USA, 2023, Curran Associates Inc.
Voigt, P. and Von dem Bussche, A. The EU general data protection regulation (GDPR). A Practical Guide, 1st Ed., Cham: Springer International Publishing, 10(3152676); 10-5555, 2017.
Liu, S., Yao, Y., Jia, J., Casper, S., Baracaldo, N., Hase, P. Yao, Y., Liu, C. Y,, Xu, X., Li, H., et al. Rethinking machine unlearning for large language models. arXiv preprint arXiv:2402.08760 2024.
Zhang, B., Dong, Y., Wang, T., and Li, J. Towards certified unlearning for deep neural networks. In Proceedings of the 41st International Conference Machine Learning, ICML'24 JMLR.org. 2024.
Mironov, I. Rényi differential privacy. In 2017 IEEE 30th computer security s symposium (CSF), pp. 263- 275. IEEE, 2017.
Mu, S. and Klabjan, D. Rewind-to-delete: Certified ma- chine unlearning for nonconvex functions. arXiv preprint arXiv:2409.09778, 2024.
Neel, S., Roth, A., and Sharifi-Malvajerdh S. Descent-to- delete: Gradient-based methods for machine unlearning. In Algorithmic Learning Theory, pp. 931-962. PMLR, 2021.
Nguyen, T., Huynh, T. T., Nguyen, P. L., Liew, A. W.-C., Yin, H., and Nguyen, Q. H. A survey machine unlearning. arXiv preprint 22x.:2209900299, 2022.
Sekhari, A., Acharya, J., Kamath, G., and Suresh, A. T. Re- member what you want to forget: Algorithms for machine unlearning. Advances in Neural Information Processing Systems, 34: 14715055-18 2021.
Smith, L. N. and Topin, N. Super-convergence: Very fast training of residual networks using large learning rates. ArXiv, abs/1708.07120,, 2017. URL https:
htrpli.smaaticsccoooarrrrrreeeee 23376859.
Thudi, A., Jia, H., Shumailov, I., and Papernot, N. On the necessity of auditable algorithmic definitions for machine unlearning. CoRR, abs/2110. 1891, 2021. URL https: //arxiv.crggaas//22. /ttp://bbb/111.199..
Triantafillou, E., Kairouz, P., Pedregosa, F., Hayes, J., Kurmanji, M., Zhao, K. Dumoulin, V., Junior, J. J., Mitliagkas, I., Wan, J., et al. Are we making progress in unlearning? findings from the first neurips unlearning competition. arXiv preprint arXiv:2406.09077 2024.
Vadhan, S. The Complexity of Differential Privacy, pp- 347-450. Springer International Publishing, Cham, doi: 10.1007/978-3- 319-57048-8.7. URL htttttts://oooor//////oo /ttp://o....o///.0000//////////1 978- 778-3-319-5700 900-----74888.77
2017. ISBN 978-3-319-57048-5
Van Erven, T. and Harremos, P. Rényi divergence and kullback-leibler divergence. IEEE Transactions on Infor- mation Theory, 60(7):397-33820,, 2014.

---

Certified Unlearning for Neural Networks
A. Proofs
A.1. Theorem 4.2: Model Clipping
Preliminaries. We first recall the hockey-stick divergence and previous results on privacy amplification by stochastic post-procsssing (Balle al., 2019).
Definition A.1 (Hockey-stick divergence). Let O, and p. two probability measures defined over Rd We define
(x / dlp
v++++ dlu-évu++=
sup ACR
(u(A) - -
where [. == max -
Lemma A.2 (Baalee et al., 2019). Theorem (adapted)). Let 2 0, K be a Markov kernel taking inputs in IRd, and μ. be two probability distributions over Rd. We have
Eş(uK || vK) s (e(
sup XI
(K((x))) (x2))).
Lemma A.3 ((Asoodeh et al., 2020), Lemma 2). Lese 2 0, 11 # u2 E Rd and o > 0. We have 0 Ia)) = (e( Ia) (12,,
80
|4 12l
eQ @
60
|| - 142
|4 142
20
| 12l
20
where for all t R. Q(t)= Vx -e 12
Lemma A.4 (Dwwork & Roth, 2014), Theorem A.1 (paraphrased)). Let E E (0, 1) and pe # pb E RR, 0 > 0. We have
o²E²
Ee I || (( S exp
2 (|l 11 12
Main proof. We now proceed proving the main theorem.
Theorem 4.2 (Model clipping). Let T 2 1, Co, Co, > O, and ō (0, Denote for every 0,
eQ (2(r) = @ (f - - (-+5)) +.
()
(9)
where for all t E R. Q(t)===+ -.
e- 12
Consider T' iterations of the unlearning algorithm defined in (4). We obtain (s, 8)unlearrning
log(1/8) + log O- (Cch
(10)
log (1/0g 2C2)
In particular, for any T 2 1,6 E (0, 1), it suffices to have
a² 8C2 ln(1.25)
1 + T [n((1.25/))
=²=²
(11)
22
SC8
Proof: Let 7 2 1, Co, C2, To. > 0, and 5 E (0. 1),c e (0, log(1/5)) Consider T iterations of the unlearning algorithm defined in (4), and analogously define the following sequence initialized at the projected model trained without the forget data x1= = Il,,,(A(2 Dy)) + Eu. Eo ~ NO La):
X
II,, (xt GG(x)) + E.
&~N(00,
(15)
Recall from Definition A.I the definition of the hockey-stick divergence Eg, Also, we recall from Lemma A.2 that for any Markov kernel K:
Be(KK [K) <
sup
| K K(x2)) (K(())) Ee(a v).
12

---

Certified Unlearning for Neural Networks
In particular, by introducing x (g(N(UT,, (x1 - -((xx)),,oAL) ( o we have
Ex(x+ || x(+1) a- Ex || x().
Applying the above recursively over T iterations, and denoting 3 = (AD) Il (ATD, Dy)), (f)),, yields:
(xT x S a² Eg (xo || X4) a B.
Therefore, in order to satisfy (c, -umleaimmn,n,, it suffices to achieve (x( || x/x)) S 6, which can be achieved by having:
T> log(1/6) + log
log(1/o)
Now, since for any X2 it holds that [xı -G(()) ITc, (x2 -x(x)) 2C2 and + ( 2/1 e²Q ( + ) increasing (Asoodeh al., 2020), using the exact expression of the hockey-stick divergence between Gaussians from Lemma A.3 yields
(x -G((x))), o 1a) |I (x2 - (G(x))), ozL)
sup Xi xR
$
5D
C2
)
-c
E0
+ -
2C2
2C2
Similarly, since [[Ic, (A(D)) - IIc (A(D) Df)) < 2Co, we have
B (NN(c WTTc, (A(D) (A(D) of)).o(aa)) S
800
Co
EQ
800
Co
2Cu
du
2Cu
ou
Therefore, to achieve (c.d))unlearning it suffices have
log(1/0) + log (Q
cae
e
Co
T - log (@
20
on
20
dp
ca
C2
e
Q
sa
+
C2
2C's
Alternatively, using the simpler upper bound from Lemma A.4 on the hockey-stick divergence between Gaussians, we obtain
o²=² 802
= sup (x - ER
Il (xlls -
-G(x S e.25
Similarly, have
oge²
8 (NN((TI, (())) N(Tc, (A(D) Df)), ojta)) < 1x25
808
Therefore, assuming 2²
802 1n(125)
to achieve (s, 8) Junleaann,, suffices to have
T ln(1.25/8)
SCT
ln(1.25)
8C
This can be rewritten
8C2 l1.25))
8C2 (1.25)
0/=²
o² >
In(1.25/6)
T
80
This concludes the proof.
13

---

Certified Unlearning for Neural Networks
A.2. Theorem 4.1: Gradient Clipping
Preliminaries. We first recall some important definitions and state useful lemmas before proceeding the proof of the main theorem. We first recall the definition of the Rényi divergence, which will mainly use to prove Theorem 4.1.
Definition A.5 (Rényi divergence), Let q 0, + 1. The q-Rényi divergence between two probability distributions μ and // is defined as
1 a-1 log Exao (
Dg(N || 2) =
We recall the shifted Rényi divergence introduced by Feldman al. (2018). For any 2 2 0, 2 1, and two distributions μı, defined on Rd, we define
D (u ( v) = wi: (a
inf Do(n' [],
(16)
where (..) = ((.) ess (xp | is the oc- W-sssessstin distance, and I'(2', 10) is the collection of couplings of its arguments, i.e., joint measures whose marginals are μl and μ respectively.
Lemma A.6 (Feedmman et al., 2018), Lemma 20 (adapted)). Let q 2 1, 2, 2 0 and X, Y arbitrary random variables. If ~ OV(, > 0, then
ga?
D + + +') < D2 ((2+0) (X Y))
20
Lemma A.7. Let 2 1,,, 3b Rd + Rd and X, Y arbitrary random variables. If i satisfies Vx, x' E Rdd [|x((x)) xx)xl S / - x + then
D/ ((
(Y)) D (X Y).
Proof. For any measure we denote by u the push oush-forward measure of by sb Assume that & satisfies Vx, E Rd, [1,llb((x''' - +x)] S p ||x - x|| + 8. By definition of the oc- oc-Wasserstein distance, it follows immediately that
Wo (1h#1, vh4v) S W (P,, v) + 8.
(17)
Therefore, by definition (16) of the shifted Rényi divergence and using the data processing inequality for Rényi diver- gences (Van Erven & Harremos, 2014), we have
(16(X) || (VY))) #:: W ((
inf
Dz(m' l1 (Y))
inf x W ((()))))()))))) Dy(0(X') |I (YY)
x (X: (v(('))) ((Y))
inf
(Inequality (17))
S x (X1,
inf
Dx(X' ||
(Data Processing inequality)
= (x
This concludes the proof.
Lemma A.8. Let
0, G: Rd + d.d. be arbitrary function, and v/: x (Ic()())) + Xx). Then sb satisfies: (x)]l < 4 -
Vx, x' Rd (1x((x)))))) -
Proof. We have for any x.x' E R that
(1b(x) (xx')l = ||x - (X
< |1 >yy x x +, (
(Triangle inequality) ())x)) < C)
< [1 Xn/ x x 22C.
14

---

Certified Unlearning for Neural Networks
Main proof. We are interested in the following iterative unlearning procedure (generalizing (3) regularization and varying stepsizes and noise variances), starting from the projected model trained the full data Xp == Nc, (A(D)), where for all & E
T [O....,T--1]
X, 7/ (Ile, (G(x))) + Axx) + &
& ~ o0
(18)
For the analysis, we analogously define the following sequence initialized at the projected model trained without the forget data x/1 == ITc, (A(D) \ Dy)):
X = =x (x (G(x)) + xxx) + +
& oL
(19)
Theorem A.9. Let T 2 -. 2 0,00 TT-1 > 0, 0 and consider the two sequences {xiTOSIST, (xSSST as defined above. Denote by D2 the Rényi divergence of order 9. Assume that for every E (O,...,T 11.70 < 1. Denote for every 1 E {O..... 1}, == 2n, Pt 1 7ad
If //onn...,,r--. 2 0 satisfy E/ (TT--T Pk) = (II'=o Pt) 2C + Et= (ITK-1 1 Pk) 8t: then
T-1 qua
Dx(XT || x47)
Σ
(20)
20
In particular, we have
(ITL Pr) 20 + Et-11
[Ik--
[T--1-t Pk)
St 2
(x || x/2) <
(21)
E
-1- [II==
p of
Proof. Let t E I 1}. Recall the sequence of iterates defined in (18), and analogously define the following sequence initialized at the projected model trained without the forget data xy= = IIc, (A(D) D))))
x14 x 7 (Ile, (G(x)) + Ax,) + c
C~N
(22)
Therefore, for any oe 2 0. using the bound above with Lemma A.6 yields
D D(aun) (x || xx(+1)=
D( vi (Il, (G(x.)) + Axx) + & || x 7u (Wl. (G(x4)) + Xx)) + +
q
(o0)) (x: yt (Ic, (G(x))) + Ax;) x 7 (ITc (G(x)) + Xx()) + qag
D q
20
Now, using Lemma A.8, and the fact that 7t- < 1 we establish that vh: x x x x (G(x)) satisfies Vx, x' Rd (x/) - th (x)]l $ (1 - Xrye) I|x' x|| 2%, Consequently, denoting st = 21 and Pt == Aays using the previous fact and Lemma A.7 in the bound above yields
((44)((x+)) x(++1 < D( (x: - 7/ (TTc, (G(x:)) Axx)) x|x Th (G(x)) xx())
quz
20²
(a111ta--s)) =1))
qa²
< D, p
(x: xx)=
207
By denoting == Ar
(z+11 a st), we have by recursion over t E (O...., - 1} for any 2o, ao. .., ar 0:
T-1 1
D(2r) (XT
|| x)})
<
<D(
D(200
x6) +
Σ
qa²
(23)
20 7
1=
T-1
2T
II
Pt
z0 Σ
II Pk
(a+ 8t)-
(24)
t=
15

---

Certified Unlearning for Neural Networks
Observe that, upon taking 20 = 2Co, since ||x; x6ll S 2Co, it is immediate from definition (16) that D2
xx)
Additionally, taking 2T in the last equation implies that for all :............................... 0T-1 ; 2
such that
--t II
T-1
1-t
Pk
ar
II t=
Pt
2C
II
Pk
(25)
1=0
we have
7-1 1
qa
(x || xx) =
[xT
(26)
2
t=0
This concludes the first part of the second statement of the theorem. The second part of the second statement is direct consequence of setting, for E tO...., 1}.
T-I-K II 1=
[IT Pk) og
II K=0
Ph
20p
+
Pt
(27)
Σ
[ pf o?
k=0
Theorem 4.1 (Gradient clipping). Let T 2 1,,,00 0, E (0, E (0,3 Consider T iterations of the unlearning algorithm defined in (3). We obtain (s, juunlarrnn if:
1. Without regularization (A 0):
o² 9log(1/0) ET (Co + C
(5)
2. With regularization (A 0): if E ( 1) and
0² = 727Alog(1/8)
(co(1- + G x -
(6)
Proof. The proof of the first claim follows immediately by taking constant noise variance, stepsize, and zero regularization in the second statement of Theorem A.9, before converting from Rényi to (e, -)-nlearnng using standard conversion methods (Mironov, 2017).
Similarly, the proof of the second claim follows immediately by taking constant noise variance, and stepsize in the second statement of Theorem A.9 (which assumes that yd 1), before converting from Rényi to (e, 6-unleamnng using standard conversion methods (Mironov, 2017). Indeed, we then get that it is sufficient to set
7\(2 - 7A) (1 (1 - )
2C
(1 - 11-(111 -11-1)))3]
0² Z
20 (1 - 72)² +
A
The right-hand side above be upper bounded by (1gg This concludes the proof.
Co (1 72)² + + when assuming that >d 4.
16

---

Certified Unlearning for Neural Networks
B. Experiments
use small custom networks for training on MNIST and CIFARIO
used for mnist
class TinyNet (nn. Module) num_classes: int
compcct
def call_ x, train: bool True, mutable=None)
X = x. reshape (x. shape[0], -1))
Dense www.Deeseeeeetrrreeee (features=5) (x)
X nn. re)
10
x om. (features==e f.nrrcclsssseeeeeese (x)
11
return
class CIFARLOTinyKNet (nn.Module):
14
num classes:
15
16
def
x, train: boel True);
18
he he_init nn, initializers. saaprssshh_neeamr1
19
x nn, Con.Convvcee www. (featurre,,, kernel_sizes (3, 3), padding="same",
x)
(x)u
avg avg_ (x, window_shape= 2), strides= (2, 2)
22
X nn, Conv (featureee,, kernel_size- (3, 3), padding="sana kernel init=be init)
x)
23
X nn. (xlu
nn.avg_pool (x, xindow_shape- (2, 2), strides- (2, 2))
25
xaxean(axis-11.. (1, 2))
26
x nn. (self. num classes, kernel init=he init) (x)
27
ret return x
In Tables 3 and 4 we give complete experimental details for the CIFAR and MNIST experiments.
Dataset
CIFAR-10
Architecture
Tiny Convolution Net (20k params)
Training objective
Cross entropy loss
Evaluation objective
Top- accuracy
Batch size
128
Training learning rate
0.1
Training learning rate schedule
Linear One Cycle (Smith & Topin, 2017)
Train weight decay
0.0005
Number of train epochs
100
Forget set size
10%
Number of unlearning epochs
50
Noise schedule
constant
Unlearning learning rate schedule
constant
Post Unlearning learning rate
0.06
Post Unlearning learning rate schedule
Linear One Cycle
Post Unlearning weight decay
0.0005
Table 3. Experimental Setting CIFAR10
17

---

Certified Unlearning for Neural Networks
Dataset
MNIST
Architecture
Tiny 2 Layer Net (4k params)
Training objective
Cross entropy loss
Evaluation objective
Top-I accuracy
Batch size
128
Training learning rate
0.06
Training learning rate schedule
Linear One Cycle (Smith & Topin, 2017)
Train weight decay
0.0005
Number of train epochs
30
Forget set size
10%
Number of unlearning epochs
10
Noise schedule
constant constant
Unlearning learning rate schedule
Post Unlearning learning rate
0.06
Post Unlearning learning rate schedule
Linear One Cycle
Post Unlearning weight decay
0.0005
Table 4. Experimental Setting MNIST
Compute Budget
X
Ci
7
Co
Unlearning Steps
10.0
100.0
0.0001
0.01
0.028270
750.0
10.0
0.0001
0.01
6
0.007752
750.0
10.0
0.0001
0.01
0.007752 6
750.0
10.0
0.0001
0.01
0.007752 6
10.0
100.0
0.0001
0.01
0.028270 1
1
750.0
10.0
0.0001
0.01
0.007752 6
10.0
100.0
0.0001
0.01
0.028270
10.0
100.0
0.0001
0.01
0.028270
10.0
100.0
0.0001
0.01
0.028270
10
10.0
100.0
0.0001
0.01
0.028270
Table 5. Hyperparameters for Gradient Clipping MNIST
Compute Budget
C2
A
Unlearning Steps
1
0.001
0.01
0.0001
900.00
1
0.001
0.01
0.0001
900.00
1
0.001
0.01
0.0001
900.00
1
0.001
0.01
0.0001
500.00
I
5
0.001
0.01
0.0100
0.01
1
6
0,010
0.01
0.0010
900.00
1
0.001
0.01
0.0010
10.00
1
0.001
0.01
0.0100
900.00
0.001
0.01
0.0001
10.00
1
10
0.001
0.01
0.0010
10.00
Table 6. Hyperparameters for Model Clipping MNIST
18

---

Certified Unlearning for Neural Networks
Compute Budget (epochs)
X
C1
Co
Unlearning Steps
200.0
100.0
0.0010
0.1
0.254558
50.0
10.0
0.0100
1.0
5
0.275702
7
50.0
10.0
0.0100
20.0
0.256790 11
10
50.0
100.0
0.0001
0.1
0.088213 10
13
1.0
10.0
0.0010
0.1
0.089197 10
16
50.0
10.0
0.0010
0.1
0.077256 10
19
1.0
10.0
0.0010
0.1
0.089197 10
50.0
100.0
0.0001
0.1
0.088213 10
25
500.0
100.0
0.0010
1.0
0.275702 5
28
50.0
10.0
0.0100
20.0
0.256790 11
31
500.0
100.0
0.0010
20.0
0.256790 11
34
50.0
1.0
0,0010
1.0
0.012501 93
37
50.0
100.0
0.0010
0.1
0.275772 1
40
500.0
100.0
0.0010
1.0
0,275702 5
1.0
10.0
0.0100
0.1
0.281429
46
500.0
100.0
0.0010
20.0
11
0.256790
1
49
1.0
10.0
0.0100
0.1
0.281429
Table 7. Hyperparamcters for Gradient Clipping CIFAR
Compute Budget (epochs)
C2
11
Unlearning Steps
0.200
0.2
0.0100
100.0
6
0.500
0.5
0.0010
10.0
6
7
0.500
0.5
0.0010
10.0
6
10
0.625
0.5
0.0001
100.0
9
13
0.625
0.5
0.0010
100.0
9
16
0,625
0.5
0.0001
0.0
9
19
0.500
0.5
0.0001
0.0
6
22
0.500
0.5
0.0010
0.0
6
25
0.625
0.5
0.0001
10.0
28
0.625
0.5
0.0010
100.0
9
31
0.625
0.5
0.0001
1.0
9
34
0.975
0.5
0.0001
10.0
36
37
0,625
0.5
0.0100
10.0
9
40
0.975
0.5
0.0001
1.0
36
43
0.500
0.5
0.0001
10.0
6
46
0.975
0.5
0.0001
10.0
36
49
0.500
0.5
0.0100
100.0
6
Table 8, Hyperparameters for Model Clipping CIFAR
19

---

Certified Unlearning for Neural Networks
Compute Budget (epochs)
Co
1.00
9.689610
4
0.10
0.968961
7
0.10
0.968961
10
0.10
0.968961
13
0.10
0.968961
16
0.10
0.968961
19
0.10
0.968961
22
0.10
0.968961
25
0.10
0.968961
28
0.10
0.968961
31
0.10
0.968961
34
0.10
0.968961
37
0.10
0.968961
40
0.01
0.096896
43
0.01
0.096896
46
0.10
0.968961
49
0.01
0.096896
Table 9. Hyperparameters for Output Perturbation CIFAR
Compute Budget (epochs)
Co
1
0.01
0.096896
2
0.01
0,096896
3
0.01
0.096896
4
0.01
0.096896
5
0.01
0,096896
6
0.01
0.096896
7
0.01
0.096896
8
0.01
0.096896
9
0.01
0.096896
10
0.01
0.096896
Table 10. Hyperparameters for Output Perturbation MNIST
C. Transfer Learning Experiments
We use small three layer network as the head on top of frozen pretrained (on Imagenet) ResNet18 backbone for transfer learning experiments on CIFAR-10 and CIFAR-100
class ThreeLayerNN (nn. Module)
num_classes: int
8nn. compact
def
call 1ell1_(seee,, x, train: boel True, mutable=None)
resaape shape [0], -1))
nn. Dww.Deneeeeeeeeeeeeee (features33 (x)
X nn. relu
X nn, Dense (aeseefeeee (features-32) (x)
nn. relu(x)
Dense (wwatures=self.nn.... wtwpeeefffuuu__eesssseeeeeeeeeee (x)
12
return
In Tables 11, 12, and 13 we give complete experimental details for the CIFAR-10 and CIFAR-100 transfer learning experiments.
20

---

Certified Unlearning for Neural Networks
Architecture
Frozen Resnet-18 Backbone + 3 Layer NN
Training objective
Cross entropy loss Top- accuracy
Evaluation objective
Batch size
128
Training learning rate
0.1
Training learning rate schedule
Linear One Cycle (Smith & Topin, 2017)
Train weight decay
0.0005
Number train epochs
100
DP-SGD II-Il2 -clip
0.5
DP-SGD target group
50
DP-SGD target group
0.00001
Forget set size
10%
DP-SGD forget set size
0.5%
Number of unlearning epochs
50
Noise schedule
constant
Unlearning learning rate schedule
constant
Post Unlearning learning rate
0.06
Post Unlearning learning rate schedule
Linear One Cycle
Post Unlearning weight decay
0.0005
Table 11. Experimental Setting CIFAR- 10 and CIFAR- 100
Compute Budget (epochs)
À
Ci
Co
Unlearning Steps
500.0
100.0
0.001
0.01
0. 0.148492
100.0
10.0
0.0001
0.01
10
0.008698
7
0.50
1.0
0.001
0.01
0.008932 10
10
0.50
10.0
0.0001
0.01
10
0.008943
13
0.50
10.0
0.0001
0.01
10
0.008943
16
10.0
10.0
0.001
0.01
0.028 143
19
10.0
10.0
0.001
0.01
0.028 143
10.0
10.0
0.001
0.01
0.028 143
25
10.0
10.0
0.001
0.01
0.028 143
28
10.0
10.0
0.001
0.01
0.028 143
31
100.0
100.0
0.0001
0.01
0.028143
34
10.0
1.0
0.01
0.01
0.026870
37
0.50
10.0
0.001
0,01
0.028277
40
0.50
10.0
0.001
0.01
0.028277
43
0.50
10.0
0.001
0.01
0.028277
0.50
10.0
0.001
0.01
0.028277
49
0.50
10.0
0.001
0.01
0.028277
Table 12. Hyperparameters for Gradient Clipping Transfer Learning CIFAR-10
21

---

Certified Unlearning for Neural Networks
Compute Budget (epochs)
X
C1
?
Co
Unlearning Steps
500
100
0.001
0.01
0.148492
4
0.50
1
0.001
0.01
10
0.008932
7
10
0.001
0.01
10
0.008698
10
10
0.10
0.01
0.10
30
0.008524
13
10
10
0.0001
0.01
0.008920 10
16
100
1
0.001
0.10
30
0.008524
19
0.50
0.001
0.01
0.008932 10
22
500
0.0001
0.01
10
0.007726
25
100
0.001
0.10
30
0.008524
28
0.50
0.001
0.01
10
0.008932
31
500
10
0.001
0.025667 10
34
0.50
10
0.0001
0.01
0.008943 10
37
500
10
0.001
0,025667 10
40
500
10
0.001
0.025667 10
43
500
0.001
0.025667
46
500
10
0.001
10
0.025667
49
500
10
0.001
10
0.025667
Table 13. Hyperparameters for Gradient Clipping Transfer Learning CIFAR-100
D. E Sweep
In this section, we evaluate how the choice affects the performance of our algorithm. For that, in addition to c used in the paper, plot the performance of the gradient clipping algorithm (3) for 0.1 and e 10. We kept fixed d 10-5 for all of the epsilons. See Figure 4 for results. We can see that 0.1 degrades the performance of our algorithm significantly compared to 1. There is very little difference between = 1 and 10 but performance penalty for 0.1 that is more visible with the harder task (CIFAR-10).
0.50
035
0.50
0.75
Validation Accurscy
048
Validaatin Accuracy
0.10
0.25
055
Gradient Cleaine--0 rexdect dipoingest urddion
Gradiet Cioping c=01 cesdent riieing trad ont cioping c-100
0.0
Compute (Lpachs)
Compute (tpacho)
(a) CIFAR-10
(b) MNIST
Figure Accuracy of Gradient Clipping compute budget (epochs) CIFAR-10 (left) and MNIST (right), satisfy (e, 10 10-3). unlcarning for & E (0.1, 1, 10).
22

---

Certified Unlearning for Neural Networks
Compute Budget (epochs)
C1
Co
Unlearning Steps
0.1
500
100
0.001
0.871847
4
0.1
500
100
0.001
5
0.871847
7
0.1
500
100
0.001
5
0.871847
10
0.1
500
100
0.001
5
0.871847
13
0.1 500
100
0.001
0.871847 5
16
0.1 500
100
0.001
0.871847
0.1 500
100
0.001
0.871847
0.1 500
100
0.001
0.871847
25
0.1 500
100
0.001
0.871847
28
0.1 500
100
0.001
0.871847
31
0.1 500
100
0.001
5
0.871847
34
0.1 500
100
0.001
0.871847
37
0.1 500
100
0.001
0,871847
40
0.1 500
100
0.001
0.871847
43
0.1
100
0.001
0.871847
46
0.1
500
100
0.001
0.871847 5
49
0.1
500
100
0.001
0.871847
500
100
0.001
0.275702 5
10
0.001
0.1
0.089197 10
7
500
100
0.001
0,275702 5
10
0.001
0.1
0.089197 10
500
100
0.001
0.275702
500
100
0.001
0.275702
19
500
100
0.001
0.275702
22
500
100
0.001
0.275702
25
500
100
0.001
0,275702
28
500
100
0.001
0,275702
31
500
100
0.001
0,275702
500
100
0.001
0,275702
37
500
100
0.001
0.275702
40
500
100
0.001
0.275702 5
43
1
500
100
0.001
0.275702
46
500
100
0.001
0.275702 5
49
I
500
100
0.001
0,275702 5
10
100
0.1
0.1
4.512385
10
10
0.1
0.1
0,487463
0.1
10
0.1
0.889955
10
10
0.1
10
0.1
0.1
0.491483
13
10
0.1
10
0.1
0.889955
16
10
0.1
10
0.1
0.1
0.491488
19
10
10
0.1
0.1
0.487463
22
10
0.1
10
0.1
0.1
0,491488
25
10
0.1
10
0.1
0,889955
0.1
0.01
0.1
0.007260
31
10
0.1
0.1
0,026744 53
34
10
25
0.01
10
0.071419 19
37
10
0.1
10
0.1
0.1
0.491488 10
40
10
10
0.001
0.1
0.028207
43
10
25
0.01
10
19
0,071419
46
10
25
0.01
19
0.071419
49
10
0.1
0.1
30
0.026955
Table 14. Hyperparameters for Gradient Clipping CIFAR-10 for {10, 1,0.1)
23

---

Certified Unlearning for Neural Networks
Compute Budget (epochs)
A
C1
Co
Unlearning Steps
750
10
0.0001
0.01
0.002451
10
2
750
10
0.0001
0.01
0.002451
10
3
750
10
0.0001
0.01
6
0.002451
10
4
750
10
0.0001
0.01
0.002451
10
5
10
100
0.0001
0.01
0.008940
10
6
750
10
0.0001
0.01
0.002451
7
100
0.0001
0.01
0.008940
8
750
10
0.0001
0.01
0.002451
9
10
100
0.0001
0.01
0.008940
1
10
100
0.0001
0.01
0.028270
2
750
10
0.0001
0.01
6
0.007752
3
750
10
0.0001
0.01
0.007752
4
750
10
0.0001
0.01
0,007752
5
10
100
0.0001
0.01
0.028270
100
0.0001
0.01
0.028270
7
750
10
0.0001
0.01
0.007752
8
10
100
0.0001
0.01
0.028270
9
10
100
0.0001
0.01
0.028270
0.1
10
100
0.0001
0.01
0.089398
2
10
100
0.0001
0.01
0,089398
0.1
3
10
100
0.0001
0.01
0.089398
0.1
4
750
10
0.0001
0.01
0.024514
0.1
5
100
0.0001
0.01
0.089398
0.1
6
10
100
0.0001
0.01
0.089398
0.1
7
10
100
0.0001
0.01
0.089398
0.1
8
10
100
0.0001
0.01
0.089398
0.1
9
10
100
0.0001
0.01
0.089398
Table 15. Hyperparameters for Gradient Clipping MNIST for e E 1,0.1
24


Reviews:
[{"review_id": "mOjQn7RSQI", "reviewer": "Reviewer_7Qas", "summary": "**Main Results**: Although the idea of fine-tuning an originally trained model on retained data has been proposed before, it has traditionally been viewed as an empirical forgetting strategy for non-convex tasks. This paper provides certified unlearning guarantees for neural networks without requiring knowledge of the smoothness constant of the loss function.\n\n**Main Algorithmic/Conceptual Ideas**: The authors propose two clipping-based strategies: gradient clipping and model clipping. The core idea involves either \"clip-before-updating\" or \"update-before-clipping,\" with the addition of Gaussian noise to the output.\n\n**Main Findings**: The authors provide approximate unlearning guarantees for both methods. Then they compare the performance of their methods with the baseline (output perturbation) when achieving the same unlearning guarantee.\n\n## update after rebuttal\n\nThe authors have addressed most of my concerns by conducting additional empirical evaluations, and the results looks reasonable. Considering the comments and responses from the other reviewers, I have decided to raise my score to \"weak accept.\"", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the detailed and constructive feedback, and we address the key points below.\n\n\n**1. Baseline Comparisons:**\n\nWe choose only output perturbation and retraining from scratch since these algorithms are the only baselines in the literature that can achieve certified unlearning without additional assumptions on the loss function or modification of the original training. \nIn more details:\n* Newton updates [1]: assume **convexity and smoothness** of the loss function, therefore, are inapplicable for the unlearning deep neural networks. \n* Golatkar et al [2]: impose the **smoothness assumption** on the loss function, which frequently does not hold in deep learning if activation functions are non-smooth. Moreover, their unlearning definition is based on mutual information, and it is non-trivial how to connect it with our differential privacy-based definition of unlearning.\n* Allouah et al [3]: impose additional assumptions of either **strong convexity and smoothness** or assume **smoothness and that the minima is unique and achievable from any initialization**. Such assumptions do not hold in the deep learning setting. \n* Zhang et al. [4]: require the loss function to be **L-smooth, as well as the knowledge of the minimal eigenvalue of the hessian**, limiting its applicability to the general deep learning setting.\n\nWe are unaware of any other work that can tackle certified unlearning in the same generality as our work without limiting additional assumptions on the loss functions.\n\nWe will add this discussion to the next version of our manuscript.\n\n**2. Utility-complexity tradeoff:**\n\nThank you for suggesting a discussion of utility-complexity tradeoffs as explored in [1]. However, such tradeoffs typically require strong assumptions such as convexity or smoothness. Given our primary contribution is providing guarantees for general non-convex settings without these assumptions, clearly characterizing utility-complexity tradeoffs becomes inherently challenging—particularly due to issues like the curse of dimensionality and non-smoothness. We will clarify this inherent difficulty in our revised manuscript.\n\n\n**3. Empirical Justifications (Accuracy and AUC of MIA):**\n\nOur goal is to provide rigorous theoretical guarantees without imposing restrictive assumptions such as smoothness or knowledge of eigenvalues of Hessian matrices, as required by [2]. Hence, empirical measures such as MIA scores, used to evaluate methods without strong theoretical guarantees, are not directly comparable or necessary in our theoretical setting. Nevertheless, connecting theoretical unlearning guarantees to practical empirical metrics is an intriguing direction for future exploration, but beyond the scope of this work. \n\n**4. Accuracy Improvements (Fig. 2):**\n\nOur experimental results (Table 2, Figure 1) show consistent improvement over retraining from scratch across all compute budgets and accuracy targets. Notably, Figure 1 illustrates that with a small compute budget, our method improves test accuracy by up to 8%. The improvement is most significant in low-compute settings, while larger compute budgets make retraining from scratch more effective. In Figure 2, where the compute budget is relatively large, the accuracy improvement is less pronounced. Importantly, both our method and retraining from scratch employ fine-tuning on the retained set. Our approach preserves useful information from the trained model, making fine-tuning more effective.\n\n**5. Experimental Setup and Practical Settings:**\n\nWe agree that extending our experimental framework (e.g., sequential or microbatch deletion settings, as suggested by the reviewer) would provide additional practical insights. While our current focus remains on fundamental theoretical generality, we recognize the value of practical validation and will explicitly outline these as future directions.\n\n**6. Terminology Clarification:**\n\nWe acknowledge the confusion caused by unclear terminology (\"privacy target,\" \"iteration budget,\" etc.). Yes, your interpretations are correct—the \"privacy target\" refers to the \"$(\\varepsilon, \\delta)$-unlearning guarantee,\" while the \"iteration budget\" corresponds to the maximum allowed iterations. We will clearly define these terms in the revised manuscript.\n\n\n\n\n\n### References\n\n[1] Guo et al. Certified Data Removal from Machine Learning Models. ICML 2020.\n\n[2] Golatkar et al. Mixed-privacy forgetting in deep networks. ICCV 2021.\n\n[3] Allouah et al. \"The Utility and Complexity of In- and Out-of-Distribution Machine Unlearning.\" ICLR 2025.\n\n[4] Zhang et al. \"Towards Certified Unlearning for Deep Neural Networks.\" ICML 2024.", "claims_and_evidence": "The authors offer detailed proofs to support the certified unlearning guarantees of their proposed methods, and upon review, these proofs appear sound and logical. \n\nHowever, the experimental analyses presented are somewhat basic and do not sufficiently explore or demonstrate the effectiveness/feasibility of the proposed approaches in more complicated scenarios. See more details in *Methods And Evaluation Criteria* and *Experimental Designs Or Analyses*.", "methods_and_evaluation_criteria": "The evaluation criteria include: 1) the number of steps required to achieve a fixed target accuracy, and 2) the validation accuracy attained when the number of update steps is fixed. \n\nTo strengthen their analysis, the authors could provide theoretical justifications regarding the utility and complexity trade-offs, as discussed in [1]. Alternatively, they could offer empirical justifications focusing on relearn time, the accuracy of membership inference attacks (MIA), and the AUC score of MIA, as explored in [2].\n\n[1] Youssef Allouah, et al. \"The Utility and Complexity of In- and Out-of-Distribution Machine Unlearning.\" ICLR 2025.\n[2] Binchi Zhang, Yushun Dong, Tianhao Wang, Jundong Li. \"Towards Certified Unlearning for Deep Neural Networks.\" ICML 2024.", "theoretical_claims": "I reviewed the proofs of Theorem 4.1 and Theorem 4.2, and they seemed logical and coherent to me. However, I must admit that I did not examine their correctness in great detail.", "experimental_designs_or_analyses": "+ The authors primarily compare their methods to output perturbation and the most naive baseline method, 'retrain.' However, it would be beneficial to include comparisons with other related methods that also provide certified unlearning guarantees, such as using Newton updates [1], Fisher forgetting [2], and state-of-the-art methods proposed in [3] and [4].\n\n+ The authors do not conduct experiments in more practical settings to verify the feasibility of their proposed methods. For example, \n    - the sequential setting where users can send unlearning requests at different time points in sequence\n    - the microbatch deletion setting where the size of the forget set varies, such as 0.1%, 1%, 10%, etc.\n\n+ Regarding the statement on page 7: “the privacy target is reached before exhausting the iteration budget, in less than 100 iterations,” the terms “privacy target” and “iteration budget” are somewhat confusing. It seems these terms have not been clearly defined earlier in the text.\n    - What is the relationship between these terms and the “accuracy target” and “compute budget” mentioned later?\n    - Does the \"privacy target\" refer to the “(ε, δ)-unlearning guarantee,” and does the \"iteration budget\" refer to the number of iterations required to reach the target accuracy?\n\n+ In Figure 2, if I understand correctly, the accuracy improvement seems to primarily result from standard fine-tuning on the retained set, as the accuracy after the noisy steps drops to nearly zero. Moreover, from the convergence curve, it appears that this \"first-noisy-then-standard\" fine-tuning procedure only results in less than a 0.1 accuracy improvement compared to retraining from scratch, however, with a similar computational cost and more significant fluctuations (especially during the early unlearning epochs) . The authors are expected to provide more justifications for those findings.\n\n\n\n\nReferences:\\\n[1] Certified Data Removal from Machine Learning Models. \\\n[2] Golatkar, A., Achille, A., Ravichandran, A., Polito, M., and Soatto, S. (2021). Mixed-privacy forgetting in deep networks. ICCV. \\\n[3] Youssef Allouah, et al. \"The Utility and Complexity of In- and Out-of-Distribution Machine Unlearning.\" ICLR 2025. \\\n[4] Binchi Zhang, Yushun Dong, Tianhao Wang, Jundong Li. \"Towards Certified Unlearning for Deep Neural Networks.\" ICML 2024.", "relation_to_broader_scientific_literature": "N/A", "essential_references_not_discussed": "It appears that the authors have overlooked a highly relevant paper that addresses a similar problem:\n\n[1] Binchi Zhang, Yushun Dong, Tianhao Wang, Jundong Li. \"Towards Certified Unlearning for Deep Neural Networks.\" ICML 2024.", "other_strengths_and_weaknesses": "**Originality**: The problem of establishing a certified unlearning guarantee for fine-tuning-based methods in non-convex cases is well-motivated.\n\n**Clarity**: As noted in the previous comments, the paper uses somewhat vague language and lacks sufficient theoretical or empirical justification for its methods. Many unclear statements should be clarified in the revised version. Refer to [Questions for Authors] X for specific areas needing improvement.\n\nSignificance: I think the methods proposed in this paper could be of interest to the machine unlearning community.", "other_comments_or_suggestions": "A Minor Comment:\n\nThe authors use several terms—\"epoch,\" \"iteration,\" \"time,\" \"compute budget,\" and \"iteration budget\"—that seem to convey similar meanings. Could the authors clarify the distinctions between these terms?", "questions_for_authors": "The authors are expected to address all previously mentioned issues, especially the sections on *Methods and Evaluation Criteria* and *Experimental Designs or Analyses.*", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "l3GYBaQVcX", "reviewer": "Reviewer_THT1", "summary": "The paper proposes a novel certified unlearning method that integrates noisy fine-tuning with privacy amplification by stochatic post-processing, which introduces gradient clipping and model clipping, both combined with Gaussian privacy noise. The authors provide rigorous theoretical analysis for unlearning guarantees that do not depend on restrictive assumptions. Empirical results demonstrate the effectiveness of the proposed method.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their time and constructive feedback.\n\n1. Thanks for pointing to the papers about unlearning for graph neural networks and minmax models. We will add these references to the related works section.\n\n2. We acknowledge that our experiments currently focus on fundamental settings (MNIST, CIFAR10), yet our primary contribution lies in providing rigorous theoretical guarantees without restrictive assumptions such as smoothness or convexity.\n\n3. We will add the explanation of notations $C_0,C_1,C_2, \\lambda$, and $\\gamma$ to the table caption.\n\n4. Regularization factor $\\gamma$: Thank you for raising this question. The regularization factor $\\gamma$ plays a crucial role in our theoretical analysis, related to privacy amplification via iteration (see Sec. 4.1), as the required noise magnitude decreases exponentially in the number of iterations $T$ thanks to regularization. In practice, it helps control the norm of the model parameters throughout fine-tuning, which directly influences the amount of noise required per iteration to ensure certified unlearning guarantees. We will clarify this role of $\\gamma$ explicitly in the revised manuscript.", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "The reviewer did not check the correctness of the proofs.", "experimental_designs_or_analyses": "The reviewer has checked all of the experimental designs.", "relation_to_broader_scientific_literature": "This paper presents work whose goal is to advance the field of machine unlearning, which is specifically oriented to improve the trustworthiness of machine learning.", "essential_references_not_discussed": "The paper focuses on the field of certified machine unlearning. However, it only cites certified unlearning methods under the conventional convex setting while missing the works for other specific settings, e.g., graph neural networks [1] and minimax models [2].\n\n[1] Eli Chien, Chao Pan, and Olgica Milenkovic. “Certified Graph Unlearning”.\n\n[2] Jiaqi Liu, Jian Lou, Zhan Qin, and Kui Ren. “Certified Minimax Unlearning with Generalization Rates and Deletion Capacity”. In NeurIPS 2023.", "other_strengths_and_weaknesses": "Strengths:\n\n1. The unlearning guarantees do not depend on restrictive assumptions such as loss function smoothness. The theoretical analysis is rigorous.\n2. The paper is overall well-structured. The narrative is easy to follow.\n\nWeaknesses:\n\n1. The network used in the experiments is simple, and the datasets are small. Although this paper mainly focuses on the theoretical part, it would be better to include the experimental results on larger datasets, e.g., ImageNet.", "other_comments_or_suggestions": "1. Lack of explanation of notations ($C_0, C_1, C_2, \\lambda$ and $\\gamma$) in the table caption.", "questions_for_authors": "It seems that the regularization factor $\\gamma$ does not affect the unlearning guarantee results of model clipping. Please explain the role of $\\gamma$ here.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "CQ99K8fKV8", "reviewer": "Reviewer_GtAL", "summary": "The paper presents a post processing technique to guarantee approximate unlearning in non-convex settings. The paper builds on several works in the differential privacy literature that incorporated noise during the optimization process to improve privacy guarantees. The paper proposes two methods: gradient clipping and model clipping to achieve unlearning. The paper theoretically computes the degree of noise required in each setting as a function of clipping and number of iterations. Further results show that the proposed method requires a significantly smaller amount of noise per iteration compared to the baselines.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their time and constructive feedback.\n\n1. We acknowledge that our experiments currently focus on fundamental settings (MNIST, CIFAR10), yet our primary contribution lies in providing rigorous theoretical guarantees without restrictive assumptions such as smoothness or convexity.\n\n2. DP-SGD changes the training algorithm fundamentally and, therefore, does not fit into our setting. Moreover, if we were to implement the DP-SGD baseline, we would need the per iteration noise to be scaled linearly with the forget set size, compared to the standard DP training. Since our forget set size is 5000 for CIFAR-10 and 6000 for MNIST, we do not expect any good practical performance. There is also theoretical evidence that unlearning for free via DP is severely limited in high dimensions (Allouah et al, 2024).\n\n3. Including additional experiments varying $\\varepsilon$ is a great suggestion. We will include such results clearly in our revised paper. We do not expect any significant difference in the relative performance.\n\n4. We appreciate the suggestion regarding exact unlearning systems, which indeed modify the training algorithm. We are unaware of any exact unlearning system that does not modify original training, except for retraining from scratch. We will add a discussion on this alternative approach to the related work of our paper. The exact unlearning systems typically modify the training, losing the performance quality of the model e.g., SISA (Bourtoule et al., 2019), however, they might be more efficient when unlearning.", "claims_and_evidence": "Strengths:\n\n\n- The paper is well motivated and very easy to follow.\n\n- The paper proposes a simple method for approximate unlearning backed by theoretical guarantees that extend to non-convex settings. This removes the need to know several characteristics of the existing loss function like the smoothness constant.", "methods_and_evaluation_criteria": "Weaknesses:\n\n- The evaluation of the paper seems limited as the experiments only focus on MNIST and CIFAR10 datasets, and use very small scale neural networks. I would like to see results using larger models and more complex datasets. Specifically, I'm interested to know if the updates could be applied to a subset of the model parameters to achieve $(\\epsilon, \\delta)$ unlearning.\n\n- An obvious baseline that I would like to see is DP-SGD. What if we trained the model from scratch using differential privacy? How does the unlearning performance compare with DP-SGD?\n\n- The paper should report more experiments using different levels of $\\epsilon$. Report the final accuracy and the number of iterations required for different $\\epsilon$. \n\n- In Table 2, we observe that the proposed method requires a large number of fine-tuning steps that is comparable to retraining the model from scratch. How does this compare with exact unlearning systems? These systems reduce the unlearning steps by using modular systems and can retain high performance. I understand that this is a different paradigm of unlearning, but it would be interesting to discuss and compare the shortcomings of each unlearning technique. \n\n\n[1] https://arxiv.org/abs/1912.03817\n\n[2] https://arxiv.org/pdf/2406.16257", "theoretical_claims": "The theoretical claims in the paper look good to me. However, I'm not an expert in differential privacy and the proofs of the theoretical claims are beyond the scope of my expertise.", "experimental_designs_or_analyses": "NA", "relation_to_broader_scientific_literature": "NA", "essential_references_not_discussed": "NA", "other_strengths_and_weaknesses": "NA", "other_comments_or_suggestions": "NA", "questions_for_authors": "Please respond to the weaknesses above.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "DO15vChni0", "reviewer": "Reviewer_z3Fs", "summary": "This paper proposes to analyze the formal unlearning guarantees of two varieties of clipped noisy finetuning (either model or gradient clipping) by using recent post-processing DP analyses. Specifically they propose to first project and add noise to the original model, and then apply $T$ steps of clipped (either model weights or gradients) noisy SGD on the retain dataset. The analysis then follows from several techniques of privacy amplification from the initial DP guarantee given by the initial projection and Gaussian noise. This is claimed to be the first algorithm agnostic to the original training algorithm. However this is for a definition of unlearning that is different to the unlearning definitions used in past work. Experimental results for the method are presented for CIFAR10 and MNIST, and they observe they improve efficiency over retraining from scratch (though retraining from scratch provides different unlearning guarantees).\n\n## Update after Rebuttal\n\nThe rebuttal helped clarify the literature from which the proposed definition came from, and I raised my initial score given this. The authors now also provide experiments comparing to DP-SGD and on more datasets, and I raised my score once more to an accept given this. While I did not follow why there was additional fine-tuning for DP-SGD in this comparison, I trust the authors will explain more in the camera-ready.\n\nI hope the authors will incorporate much of our discussion into the camera-ready, as to also help future readers understand the subtle differences between the various unlearning definitions, and acknowledge potential limitations (which are open-problems). In particular, that this post-processing definition is weaker, but it may still be enough for some settings. I now believe one of the key contributions of this paper is motivating future study on this definition, and perhaps stating this explicitly will help future readers. For example, maybe something along the lines of \"We hope future work studies applications for post-processing unlearning, given this paper showed that it allows for more efficient unlearning, with guarantees, and agnostic to the original training algorithm.\"", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your time and valuable comments that will allow us to improve our manuscript. \n\n\n### **Clarification on Definition 2.1:**\n\nWe apologize for the confusion caused. We believe that the reviewer misinterpreted our definition. We would like to note that **no modification to the training algorithm is required in our work**.\n\nOur Definition 2.1 is intended as a general and unifying framework that covers multiple previous definitions of unlearning. We want to clarify that in Definition 2.1. we did not predefine the certifying algorithm $\\bar A$ for generality. We only ask for the existence of such a certifying algorithm $\\bar A$ and its independence from the dataset $D_f$. Specifically, our definition captures:\n\n* (Ginart et al., 2019; Guo et al., 2019), where the certifying algorithm $\\bar A$ equals the training algorithm $A$.\n* (Sekhari et al., 2021; Allouah et al., 2024), where $\\bar A(.) = U(A(.), . ,∅)$.\n\nIn our work we provide certification with $\\bar A(.) = U(A(.), . ,\\varnothing)$. A similar choice was made in several prior works, such as (Sekhari et al, 2021) and (Allouah et al, 2024), and therefore is not a novelty of our work. Such a choice allows us to prove the unlearning guarantees of our algorithms (3) and (4).\n\nImportantly, our choice of the certifying algorithm $\\bar A$ is purely theoretical and does not require running additional computational steps in practice. Thus, there is no practical modification of the original training required. Consequently, comparisons with methods that fundamentally modify training (e.g., SISA or naive DP training) fall outside our experimental setup.\nWe appreciate your suggestion about explicitly clarifying these points in the manuscript. We will revise Definition 2.1 and associated discussions clearly stating how our definition captures prior definitions and the choice of the certifying algorithm $\\bar A$.\n\n### **About Thudi et al. (2022):**\n\nWe would like to thank the reviewer for pointing to the related work. We will add it to the next version of our paper. \n\nConsidering the adversarial setting with server possibly forging unlearning as was done in (Thudi et al, 2022) is an interesting problem but beyond the scope of our work. In our work, we focus on developing the algorithms for how to achieve unlearning in the non-adversarial (honest server) setting, a problem that has previously remained unsolved for general non-convex functions. Providing a certification algorithm for our approach in the adversarial setting is an interesting direction for future work but orthogonal to current work.\n\n### **Responses to Specific Questions:**\n\n1. **Accuracy on CIFAR-10 and MNIST:** Our reported accuracy is indeed lower than typical ResNet results because we employed much smaller neural networks. Higher-dimensional settings suffer performance degradation similar to standard DP-training methods. We will highlight this in the paper, and we acknowledge that future experiments with larger, state-of-the-art architectures are certainly valuable.\n\n\n2. **Hyperparameter selection:** The hyperparameters were tuned based on standard grid search procedures to balance performance guarantees, while strictly following the theoretical guidelines relating the parameters (e.g., Theorem 4.1 indicates the noise magnitude given the number of iterations). We list the result of our grid search in Appendix B. We will provide explicit explanations in the revised manuscript. \n\nWe hope that we have successfully clarified any confusion regarding our definition 2.1 and addressed the concerns raised by the reviewer. If this is the case, we kindly ask the reviewer to reconsider their evaluation and raise their score accordingly.", "claims_and_evidence": "The paper claims Definition 2.1 paraphrases the DP inspired unlearning definitions presented in  (Ginart et al 2019) and (Guo et al, 2019). This is incorrect, as in those papers $\\bar{A} = A$, i.e., the certifying algorithm must be the original training algorithm, while in this paper they let $\\bar{A}$ be free and implicitly use $\\bar{A} = U(A(D \\setminus D_F), D \\setminus D_f, \\emptyset)$. Note $\\bar{A} = A$ is widely the definition used for unlearning, even in adaptive settings: see “Adaptive Machine Unlearning”  (Gupta et al, 2021). To make their method fit the unlearning definition of past work, we would need the original training algorithm be $A = U(A(D \\setminus D_F), D \\setminus D_f, \\emptyset)$, which in the context of the methods in the paper, requires an additional T steps of projected noisy SGD after the original training run. So their algorithm does require assumptions on training (the authors claim otherwise). However, the impact of this additional assumption on the performance of the models and compute to unlearn is not evaluated.\n\n\nThis discrepancy also means the proposed methods should be compared to past certified unlearning work that also modify the training algorithm to have faster unlearning to justify the improvements of the method: e.g., SISA as proposed by (Bourtoule et al, 2021), or naive DP training. No such comparisons are made.\n\nI point the authors to “On The Necessity of Auditable Algorithmic Definitions for Machine Unlearning” (Thudi et al, 2022) for results motivating why unlearning is widely defined with a fixed training algorithm, and is not just a property of the final model.", "methods_and_evaluation_criteria": "The evaluation does not capture the fact the method requires modifications to the training algorithm. Specifically:\n\n1) No comparison to other certified approaches which modify the training algorithm are made\n\n2) No analysis/experiments of the impact on the required additional noisy projected fine-tuning is presented", "theoretical_claims": "See claims and evidence for issues with the unlearning definition and how it then presents inconsistencies with past work.\n\nThis said, I believe the proofs are correct given the training algorithm ends with $T$ steps of clipped (either gradient or model) noisy fine-tuning on the training dataset. I checked the main proofs of Theorem 4.1 and 4.2.", "experimental_designs_or_analyses": "I have several questions regarding how hyperparameters were selected, and the apparent weak performance of the models on CIFAR10 and MNIST. In particular, the model used only reaches $\\sim 55$% accuracy on CIFAR10 and $\\sim 80$% on MNIST, while reaching $>90$% is widely standard in the literature for both datasets when using ResNets. Given their unlearning algorithm actually presents changes to the training algorithm, I believe further exploration of the impact to performance of their method is necessary (as we cannot assume it will provide the same performance as current SOTA training algorithms).", "relation_to_broader_scientific_literature": "Unlearning is proposed as a technique to meet privacy and copyright legislation ( Machine Unlearning Doesn't Do What You Think: Lessons for Generative AI Policy, Research, and Practice” (Cooper et al., 2024) ) to address and detect data poisoning (“Threats,\nattacks, and defenses in machine unlearning: A survey” (Liu et al., 2024) ), amongst other concerns requiring changes to datasets. In the context of the unlearning literature, this paper tackles an important and novel problem of providing an algorithm with unlearning guarantees in novel settings (however claims need to be clarified).", "essential_references_not_discussed": "No essential references missing that I noticed, though as pointed earlier, past work is misrepresented.", "other_strengths_and_weaknesses": "Strengths:\n\n1) The proof techniques seemed a novel application of past ideas (despite the correction needed)\n\n2) If the claims are corrected as suggested below, I believe it is possible this also improve the state of certifiably unlearning large groups of data with modifications to the training algorithms (where SISA does not scale well)\n\nWeaknesses:\n\n1) The current claims are incorrect and consequently misrepresent the past iterature on unlearning", "other_comments_or_suggestions": "What follows are potential changes to the paper to remedy issues with the current claims. I am willing to revisit my score if the the issues I've raised regarding the claims are addressed.\n\n1) Rephrase Definition 2.1 to be the same as past work, and state explicitly what training algorithm you are unlearning in the theorem statements. Alternatively, present the definition as a new unlearning definition, however given past negative results on auditing unlearning using just model weights, I currently find this definition hard to justify.\n\n2) Provide experiments exploring the impact of the additional noisy clipped fine-tuning needed to the training algorithm across models and datasets. In particular consider evaluating performance degradation, and account for the additional costs to training this presents compared to naively retraining. I believe it simply doubles the current cost analysis, which would mean the method is less efficient than retraining, but the additional training cost is a one-time cost and may be less important over many unlearning requests.\n\n3) Given the method requires modifications to training, provide a more detailed comparison to the standard (modifying training) exact unlearning algorithm SISA. Note Figure 6 in (Bourtoule et al, 2021) suggests it can cut unlearning costs by $⅓$ with minimal performance degradation for image classification, though as the size of the forget set grows their unlearning cost increases and so eventually the methods in this paper could be more efficient.", "questions_for_authors": "I described my main concerns in the previous sections, but now list specific (but more minor) questions:\n\n1) Why is the accuracy on CIFAR10 and MNIST much lower than standard ResNet results? I understand the architecture is relatively small to the ResNets commonly used, but is there a specific reason not to use ResNet for these experiments? My current hypothesis for the results could be that the method suffers similar performance degradation as DP training.\n2) How were the hyperparameters chosen for the figures in the main body? I found the tables of hyperparameters in the appendix but did not connect how the tables were used to choose the final hyperparameters.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper studies the problem of developing provable unlearning algorithms for neural networks by leveraging ideas from differential privacy. The basic idea is that you clip gradients before applying gradient updates (but only to the retain set) and then add noise. An alternative is where the model parameters are clipped prior to adding noise. In both cases the algorithms are proven to satisfy approximate unlearning guarantees. The claimed technical innovation beyond prior work is the relaxation of the requirement of convexity and smoothness functions in the analysis step. During the rebuttal the authors clarified with the reviewers on where the work is situated with respect to the varying definition of unlearning (z3Fs) and provided additional empirical evaluations on CIFAR10 and CIFAR100 (z3Fs, 7Qas). I think its important to include the above empirical results and discussions within the manuscript. In addition, from my reading of the discussion, the response to reviewer 7Qas does a good job of highlighting how the theoretical asssumptions of proving (eps-del) unlearning here were distinct from Guo, Golatkar, Allouah and Zhang's work, but it does a poor job of reckoning with the lack of empirical validation on how much of a difference the relaxation of smoothness and convexity actually makes in practice. i.e. is there a continuum of tradeoffs in algorithms that relax theoretical performance in approximate unlearning with empirical performance? I think discussing what this manuscript does not do in the discussion would further strengthen directions for future work.
Decision: Accept (poster)