Hessian-Free Online Certified Unlearning
Authors: Xinbao Qiao
Meng Zhang
Ming Tang
Ermin Wei
Venue: ICLR 2025 Poster (2025)
Keywords: machine unlearning; certified data removal; privacy
Primary area: alignment, fairness, safety, privacy, and societal considerations

Abstract: Machine unlearning strives to uphold the data owners' right to be forgotten by enabling models to selectively forget specific data. 
Recent advances suggest pre-computing and storing statistics extracted from second-order information and implementing unlearning through Newton-style updates.
However, the Hessian matrix operations are extremely costly and previous works conduct unlearning for empirical risk minimizer with the convexity assumption, precluding their applicability to high-dimensional over-parameterized models and the nonconvergence condition.
In this paper, we propose an efficient Hessian-free unlearning approach. 
The key idea is to maintain a statistical vector for each training data, computed through affine stochastic recursion of the difference between the retrained and learned models. 
We prove that our proposed method outperforms the state-of-the-art methods in terms of the unlearning and generalization guarantees, the deletion capacity, and the time/storage complexity, under the same regularity conditions.
Through the strategy of recollecting statistics for removing data, we develop an online unlearning algorithm that achieves near-instantaneous data removal, as it requires only vector addition.
Experiments demonstrate that our proposed scheme surpasses existing results by orders of magnitude in terms of time/storage costs with millisecond-level unlearning execution, while also enhancing test accuracy.

Published as a conference paper at ICLR 2025
HESSIAN-FREB ONLINE CERTIFIED UNLEARNING
Xinbao Qiao'
Meng Zhangl Ming Tang²
Ermin Wei
'Zhejiang University Southern University of Science and Technology
Northwestern University
x xinbaoqiao8zju. edu.c.ccccuuuu
ABSTRACT
Machine unlearning strives to uphold the data owners' right to be forgotten by enabling models to selectively forget specific data. Recent advances suggest pre- computing and storing statistics extracted from second-order information and implementing unlearning through Newton-style updates. However, the Hessian matrix operations extremely costly and previous works conduct unlearning for empirical risk minimizer with the convexity assumption, precluding their appli- cability to high-dimensional erer-parameterized models and the nonconvergence condition. In this paper, we propose an efficient Hessian-free unlearning approach. The key idea is maintain statistical vector for each training data, computed through affine stochastic recursion of the difference between the retrained and learned models. We prove that our proposed method outperforms the state-of-the- art methods in terms of the unlearning and generalization guarantees, the deletion capacity, and the time/storage complexity, under the same regularity conditions. Through the strategy of recollecting statisties for removing data, we develop an online unlearning algorithm that achieves near-instantaneous data removal, as it requires only vector addition. Experiments demonstrate that our proposed scheme surpasses existing results by orders of magnitude in terms of time/storage costs with millisecond- level unlearning execution, while also enhancing test accuracy.
INTRODUCTION
Recent data protection regulations, e.g. General Data Protection Regulation, aim to safeguard individual privacy. These regulations emphasize the provisions of the Right to be Forgotten, which grants individuals the ability to request the removal of personal data. This regulation mandates that the data controller shall erase personal data without undue delay when data providers request to delete it. Within the context of the right to be forgotten, data owners can request the removal of their personal data's 's contribution from trained models. This be achieved through the concept of machine unlearning, which involves erasing data that pertains to the data owner's 's personal information.
straightforward unlearning algorithm is to retrain learned model from scratch, which is however impractical as it incurs unaffordable costs. It is especially challenging in time-sensitive applications such fraud detection online learning. as delayed updates upon receiving deletion request would impede the system's 's ability to respond effectively to subsequent inputs, compromising its performance and reliability. Moreover, attaining a model entirely identical to the one achieved through retraining for an unlearning method represents a notably demanding criterion. Therefore, many approximate methods have been proposed aiming to minimize the impact of forgetting data. Inspired by differential privacy, Guo et al. (2020) introduced relaxed definition of certified unlearning, which aims to make the output distribution of unlearned algorithm indistinguishable from that of the retraining.
Second-order unlearning methods have been recently studied due to their rigorous unlearning certifi- cation and the generalization guarantee. Sckhari et al. (2021) initially proposed the Newton update method and introduced the definition of deletion capacity understand the relationship between generalization performance and the amount of deleted samples. These method and concepts were later extended, e.g. Suriyakumar et al. (2022); Liu et al. (2023); Mahadevan & Mathioudakis (2021); Chien et al. (2022). The key idea of these works is to extract Hessian information of the loss function and achieve computational and memory efficiency by pre-computing and storing these second-order statistics prior to any deletion request. In particular, Sekhari et al. (2021) and Suriyakumar et al.
"Corresponding Author

---

Published as a conference paper at ICLR 2025
Table Summary of Results. Here, d, n, and m denote the model parameters size, training dataset size, and forgetting dataset size, respectively, The unlcarning guarantee is derived under the same regularity conditions as prior second-order unlearning studies, with p being a constant less than 1.
Methods
Computation time
Storage
Unlearning time
Unlearning guarantee
Sekhari et al. (2021)
(nd)) O + nd))
(dd)
Old + maf + mal) Old + mdd O(md))
Ómm² /v2) Olm² /m² ((mp"))
Suriyakumar ct al. (2022)
Old))
Proposed method
(n)d)
((nd))
(2022) revealed that for models that approximate the minimization of convex and sufficiently smooth empirical minimization objectives, unlearning can be efficiently executed through a Newton style step, facilitated by pre-storing Hessian matrix. These methods and theoretical analyses are subsequently extended to graph learning (Chien al. (2022)) and minimax learning (Liu et al. (2023)) scenarios.
While these works have demonstrated the effectivvness of the second-order method to approximate retrained models with limited updates, they do have few fundamental challenges: existing second- order algorithms (i) lack the capability to handle multiple deletion requests in online because they require explicit precomputing Hessian (or its inverse), and (ii) the learned model needs to be empirical risk minimizer, (iii) with assumption of convexity to ensure the invertibility of Hessian. Consequently, these limitations preclude their applicability to high-dimensional models (e.g., over-parameterized neural networks) for computing the Hessian. For non-convex problems (e.g., deep networks), we cannot guarantee the invertibility of the Hessian, and it is non-trivial for a learned model to converge to an empirical risk minimizer. Even for convex problems, the stt-stationartty of data (Hazan (2016)) is another common issuc in the incremental model update scenarios (c.g.. continual learning) where training is sequential but not concurrent, making it challenging for the model adapt and converge to the optimal solution. Consequently, we are motivated to answer the following key question:
(Q) How can efficient second-orde unlearning be achieved without incurring the high cost of Hessian operations, and how can effective certified unlearning be implemented under non-convex assumptions for the objectives and non-convergence conditions for the models?
In this paper, we take the first step towards tackling (Q) from innovative Hessian-free perspective. In contrast to existing schemes that extract second-order information exclusively from the optimal learned model, we leverage details from learning models during training procedure. We analyze the difference between the learning model and the retraining model by recollecting the model update trajectory discrepancy. Subsequently, demonstrate that the discrepancies can be characterized through an affine stochastic recursion. We summarize our main contributions below and in Table 1.
Hessian-Free Model Update Method. We propose a method to extract the Hessian information by analyzing each sample's impact on the training trajectory without explicitly computing the Hessian matrix. Our Hessian-free method enables efficient handling of deletion requests in an online manner. Moreover, the proposed method does not require that the learned model is empirical risk minimizer, which enjoys better scalability compared to existing second-order methods. (Section 3).
Improved Guarantees and Complexity. Under identical regularity conditions, we analytically show that our proposed method outperforms the state-of-the-art theoretical studies in terms of unlearning guarantee (See Corollary 5), generalization guarantee (See Theorem 6), deletion capacity (See Theorem 7), and computation/storage complexity (See Subsection 4.4). Moreover, the unlearning guarantee can be applied to both convex and non-convex settings. (Section 4).
Instantaneous Unlearning Algorithm. Building upon the aforementioned analysis, develop Hessian-free certified unlearning algorithm. To our knowledge, our algorithm is near-instantaneous and is currently the most efficient as it requires only a vector addition operation. (Section 4).
Extensive Evaluation. We conduct experimental evaluations using a wider range of metrics compared to previous theoretical second-order studies, and release our open source code.' The experimental results verify our theoretical analysis and demonstrate that our proposed approach surpasses previous certified unlearning works. In particular, our algorithm incurs millisecond- unlearning runtime to forget per sample with minimal performance degradation. (Sections and 6).
'Or code is available at O Hessian Free Certified Unlearning
2

---

Published as a conference paper at ICLR 2025
1.1
RELATED WORK
Machine unlearning can be traced back to Cao & Yang (2015), which defines "the completeness of forgetting". demanding the models obtained through retraining and unlearning exhibit consistency. Exact Unlcarning, e.g., Bourtoule et al. (2021); Brophy & Lowd (2021); Schelter et al. (2021);
Yan al. (2022); Chen et al. (2022b:a), typically train the submodels based on different dataset partitions and aggregation strategies (See elaborated exact unlcarning background in Appendix A). Approximate Unlearning. e.g. Wu et (2020); Nguyen et al. (2020); Golatkar al. (2020a); Izzo et al. (2021); Mehta et al. (2022); Wu et al. (2022); Tanno et al. (2022); Becker & Liebig (2022); Jagielski et al. (2023); Warnecke et al. (2023); Tarun et al. (2023), seeks to minimize the impact of forgetting data to an acceptable level to tradeoff for computational efficiency, reduced storage costs, and flexibility (See elaborated approximate unlearning backgroumd in Appendix A). In particular, Guo et al. (2020) introduces a relaxed definition of (e, -uunleaan, in anticipation of ensuring the output distribution of an unlearning algorithm is indistinguishable from that of the retraining. Building upon this framework, diverse methodologies, e.g. Sekhari al. (2021); Suriyakumar al. (2022); Gupta et al. (2021); Neel et al. (2021); Liu et al. (2023); Chien et al. (2022), have been devised.
In the certified unlearning definition, the bessian-based approaches (Sekhari al. (2021); Suriyaku- mar et al. (2022); Liu et al. (2023)) are aligned with our methodology, which involves pre-computing data statistics that extract second-order information from the Hessian and using these precomputed "recollections" to facilitate data forgetting. Specifically, (1) Newton Step (NS). Sekhari et al. (2021) proposed, through the precomputation and storage of the Hessian offline, to achieve forgetting upon the arrival of a forgetting request using a Newton step. However, NS is limited by its high compu- tational complexity of (dF), making impractical for large-scale deep models. Furthermore, can only perform certified unlearning for empirical minimizers under convexity assumption. (2) Infinitesimal Jackknife (IJ). Suriyakumar et al. (2022) extended the work NS, attaining strong convexity through non-smooth regularizer by leveraging the proximal IJ with reduced unlearning time (d.)). However, a few important challenges still remain, i.e., existing second-ore -orderr methods still require expensive Hessian computations and perform forgetting for empirical risk minimizer with the convexity assumption. In contrast, our method overcomes the limitations of existing second-order methods by achieving near-instantaneous unlearning and performing forgetting for models in any training step. Hence, our approach is applicable to scenarios where models are continuously updated.
2 PROBLEM FORMULATION
Learning. Let ((;:2) be loss function for a given parameter w over parameter space W and sample z over instance space Z. Learning can be expressed a population risk minimization problem:
min F(w) = B.- ([=:)(((;:)))
(1)
Addressing this problem directly is challenging. the probability distribution D is usually unknown. For a finite dataset S = {z )/ one often solves the following empirical risk minimization problem:
min Fs(w)
((w; 21).
A standard approach to solve the problem (2) is the stochastic gradient descent (SGD), iterating towards the direction with stepsize Tee of the negative gradient (stochastically):
We.b+1 +- Webb
Be
(e
(3)
Be,b
IEB.,
for the index of epoch update e E (0, ..., E+1} and batch update E (0.... B+1}, where E is total epochs and B is batches per epoch. Here, B.b denotes the set that contains the data sampled in the e-th epoch's 's b-th update, and [Bao is the size of Be,s, where [ is the maximum batchsize.
Unlearning Consider scenario where user requests to remove a forgetting dataset U= {u, { S S. To unleam U. retraining from scratch is considered naive unlearning method, which aims to minimize Fsye (w). Specifically, for ease of understanding, each sample appears only in one (mini-)hatch per epoch, we define the data point uj in U to be sampled in B Be,((,,) during the e-th
3

---

Published as a conference paper at ICLR 2025
epoch's b(t update in the learning process, where b(uy) represents the batch update index when u is sampled. In accordance with the linear scaling rule discussed in Goyal et al. (2017), ie. in order to effectively leverage batch sizes, one has to adjust the step size in tandem with batch size. In other words, the step size to batch size ratio during retraining is consistent with the learning process. Therefore, the update rule of retraining process during e-th epoch is given by,
-U w e,b+1 < Web
ne,b [Be,
Ve(we, e,b 2.).
(4)
iEB..b
Specifically, for the training data u, sampled into Be,M in the learning process, the removal of sample új in the retraining process results in the following update:
U (e
-U (a,)(
Σ
Vl(w R,b(ay)) ) mi).
(5)
To avoid the unaffordable costs incurred by the retraining algorithm, aim approximate the retrained model through limited updates on the learned model web++1- We thus consider the relaxed definition of model indistinguishabiliyy defined by Sekhari et al. (2021).
Definition ((e, -eeettfied unlearning). Let S be a training set and Q : 2" - W be an algorithm that trains on S and oulputs model w, T(S) represents the additional data statistics that need be stored (lypically not the entire dataset). Given an output of the learning algorithm S2 E W and a set of data deletion requests U. we obtain the results of the unlearning algorithm (()(()), T(S)) E W and the retraining algorithm (2(1(()) 9) through a removal mechanism Q. For 0 < e E and's V W C Rdd S S 2, we say that the removal mechanism 5 satisfies (c, -ccertift unlearning if P(D(((S)) T(S)) e P(Q(SSSS 0))) + 8, and P(D(((()))))) e (((((()), ((S))) + 8.
0.
(6)
Although classical Gaussian mechanisms (Dwork & Roth (2014)) assume 0 < << 1, Balle & Wang (2018) addressed e by using Gaussian cumulative density function instead of a tail bound approximation. For consistency with prior works, we use classical mechanisms in the main text.
3 MAIN INTUITION AND SOLUTION JUSTIFICATION
Before detailing our analysis, let us informally motivate our main method. Specifically, we focus on studying the discrepancy between the learning and the retraining model by analyzing the impact of each sample on the update trajectory. Our main observation that the difference between the retraining and learning models analyzed through SGD recursion can be described by affine stochastic recursion. Suppose retraining and learning processes share the same initialization, such as using the same random seed or pre-trained model. We now commence the main procedure follows:
Unlearning a single data sample. We start with designing an approximator for a single sample (i.c., U (m)) on the training (the learning and retraining) updates, considering the difference between the learning model Equation (3) and the retraining model obtained without the knowledge of u in Equation (4). In partieular, we consider the following two cases of model updates in the e-th epoch.
Case 1 (u not in Bo.d): The difference between retraining and learning updates in the e-th epoch is ii 2:) - VV Ve(We,siz)).
0 W e.b41 We.b+1 e.h Web
ne,
Σ
(Ve(W
B
(7)
BEB...
Suppose loss function é E G² (Rd), i.e. E is twice continuously differentiable. Therefore, from the Taylor expansion of Vl 2;) around We,b. we have Ve(w 2;) ~ Ve(we,;; 2;) + V ( bi (w - We,b). Let H Ha,,=1/|B..a EiEB, F2t(We,t; F
24) denote the Hessian matrix of the loss function, we can then approximate the recursion of Equation (7) as
ebb+1 We,b+1 (I (r.,HH,,)((_3. wa,b).
(8)
Case 2 (u in Beb(()):: The difference between retraining and learning updates in the e-th epoch is:
w We.b(a)-1 W1 R3 (I- -e, c(b()))
(W -Web(u))++
Ne,b(u) BB,
Vl(We,b(w))))
(9)
Approximate impact epoch
4

---

Published as a conference paper at ICLR 2025
where I denotes identity matrix of appropriate size. Combining the observations in Cases 1 and 2, along with same imitialization, we now define the recollection matrix Mr.b(u) and the approximator E. backtracking the overall difference between the retrained model and learned model:
ag u
E
De, Σ McM()) Ve( u), where Ma,6(a) = (Be,b(u) B
HE,B-I- 1-0,001-
(10)
We define H HE.B----.,
(I- n- H F. 1/- F...HH............ Me) H.
which represents the product of I from E-thh epoch's B - 1-th update to e-th epoch's b(u) 1-th update. 2 This provides an approximation of the impact of sample u on the training trajectory:
W E,B WEBB R ag
(11)
Colloquially, simple vector a addition model WE,B can approximate retrained model w WE.B for forgetting the sample u. We define A = E,B WE,B a as the approximation error.
The approximator designed in Equation (11) enables us to exploit the Hessian vector product (HVP) technique (Pearlmutter (1994)) to compute it without explicitly computing Hessian. When computing the product of the Hessian matrix and an arbitrary vector for the neural networks, the HVP technique first obtains gradients during the first backpropagation, multiplying the gradients with the vector, and then performing backpropagation again. This results in a time complexity of ((d) (Dagréou computing gradient. We defer the
et al. (2024)), which has the same order of magnitude detailed calculation process of Equation (11) using HVP to Appendix B.3. We note that the existing second-order methods require proactively storing a Hessian (or its inverse) (Sekhari et al. (2021); Suriyakumar et al. (2022); Liu et al. (2023)). It is thus unable to deploy HVP in their settings.
Note that our proposed analysis does not require to invert Hessian matrix, distinguishing it from existing Newton-like methods (Sekhari et al. (2021); Suriyakumar et al. (2022); Liu et al. (2023)). This eliminates the need for assuming convexity ensure the invertibility of the Hessian matrix. Moreover, when it comes to forgetting set of samples, we have.
Theorem (Additivity). When m sequential deletion requests arrive, the sum of m approximalors is equivalent to performing batch deletion simultaneously. Colloquially, for u1,...y Um sequence of
-w E5 us = -ド= ag.B
continuously arriving deletion requests, we demonstrate that ag
See complete analysis and proofs of Section 3 in Appendix C.1 and Appendix C.2. This elucidates that by storing the impact of updates for each sample, nearly instantaneous data removal can be achieved through vector additions. Note that it non-trivial retrain and store a lcave-one-out model for each sample, as such process cannot accommodate sequential deletion requests. If we were to consider all possible combinations of forgetting data, retraining need to pretrain O(2") models, which yields computation complexity ( Bd). The additivity enables our Hessian-free method to handle multiple deletion requests in an online manner. Previous Hessian-based methods, lacking additivity, fail to utilize HVP as the forgetting sample is unknown before a deletion request arrives.
4 THEORETICAL ANALYSIS AND ALGORITHM DESIGN
In this section, we theoretically analyze the ① Unlearning Guarantee (Theorem 4), @ Generaliza- tion Guarantee (Theorem 6), and ① Deletion Capacity Guarantee (Theorem 8). Particularly, demonstrate that under the Assumption 1, our method can outperform existing theoretical certified unlearning methods (Sekhari et al. (2021); Suriyakumar et al. (2022); Liu et al. (2023)) in terms of unlcarning guarantec, generalization guarantec, and deletion capacity. In contrast to these works, the analysis of unlearning guarantee is applicable to both convex and non-convex settings, as our proposed method does not involve Hessian inversion. Based on the foregoing analysis, we further develop an almost instantaneous online unlearning algorithm, which is one of the most efficient, as requires only vector addition operation to delete each training data. Finally, conduct storage and computation complexity analysis and show that in most scenarios where weer-parameterized models and the ratio of E to B are much smaller than the parameters, it is more efficient than previous works.
2 Similar analysis has been conducted in other lines of work to investigate the behavior of SGD dynamics, e.g. Gürbüüzalaaan et al. (2021) focused on the properties of the matrix I 7,H, which is termed multiplicative noise, serving the main source of heavy-tails in SGD dynamics and governing the update hehavior of we.b.
5

---

Published as a conference paper at ICLR 2025
4.1 APPROXIMATION ERROR ANALYSIS
-U To analyze the approximation error A E.B. we introduce the following lemmata. We first show that the geometrically decaying stepsize strategy facilitates us to derive an upper bound for the error term. Assumption 1. For any and w. loss f(w,z) is X-strongly convex, L-Lipschitz and M M-smooth in w. Lemma 2. For any e. b and 2 Be,b, there exists G such that G max VV =)]l co.
Consider geometrically decaying stepsizes satisfying le,,b1 Me, where O < < 1 and = 1/0-
During the e-th epoch's 's b-th batch update, we have:
-- geB+bb
l| We,bll S 2m/
(12)
1-9
See proof in Appendix C.3. Then, we further analyze the eigenvalue of the Hessian matrix: Lemma 3. For any e, b and vector v E RR,, there exists À and M such that AI 3 V (2l(Wo,p z.) 1 MI, and let max{11 [1- - -e,bo> |1 "oo.M be the spectral radius of I Tle He, we have He, S p|lv].
Combining Equation (11), Lemma and Lemma 3, we have the approximation error bound: Theorem 4 (Unlearning Guarantee). For any subset U {u, to be forgotten, with 0 E oo and g < p. the unlearming model w E = W., a yields an approximation ervor bounded by | E,B where the total number of batch updates per epoch B [n/[BB].
E,B
U U
EEB O(nCmp"B//1))
(13)
See proofs and analysis in Appendix C.4. We note that in general, Theorem 4 does not require the objectives to be strongly convex as it does not involve inverting the Hessian. Therefore, our method accommodates most non-convex and non-M-smooth functions. On the other hand, considering that previous theoretical works require the convexity assumption, for further comparing with these works and better analyzing the following generalization results Subsection 4.2, we show that L regularized convex problems with random regularization coefficients fall into the scope of Theorem 4.
To achieve a tighter bound, we consider the standard Assumption 1, which are similar to those in unlearning works (Suriyakumar al. (2022); Liu et al. (2023)). We have the following conclusion, Corollary 5. Suppose Assumption I satisfied, and we choose n < 2/ (M + X) to ensure gradient descent convergence and p < 1. Then, Theorem 4 yields an approximation error bound by O(mp").
Under same Assumption 1, the derived bound surpasses the state-of-the-an O(m²) /n?) in Suriyaku- mar et al. (2022); Liu et al. (2023), representing an improvement for unlearning guarantee. Moreover, Corollary implies that the unlearning model can closely approximate the retrained model.
4.2 GENERALIZATION PROPERTIES ANALYSIS
Despite that our proposed method is applicable to both convex and non-convex settings, we temporar- ily impose Assumption 1 for the analytical simplicity of generalization guarantee. This assumption will be relaxed for algorithm design, unlearning analyses, and experiments. We further analyze the generalization guarantee and compare the results with previous works.
Theorem (Generalization Guarantee). Let Assumption hold, Choose S 2 such that p p< 1 MAX for 0 < E< oo. Let w be the minimizer of the population risk in Equation (1). Considering noise perturbation to ensure (e, -ulleanan,, the unlearned model w E.B satisfies the excess risk bound,
-U
4L2
21 +
2mLnGGVd//n (1/8) )) (14)
F(WE. - E[ =E]F("))= X(n m) + +pn//BB)
See proof in Appendix C.6. The result of our proposed method yields the order O(dà Under these conditions and the fact that n 2(m). our proposed method outperforms the performance of the state-of-the oh-the-art methods (Suriyakumar et al. (2022); Liu et al. (2023)), which are O /n²). Moreover, measure the maximum number of samples to be forgotten while ensuring good excess risk guarantee, we provide our proposed scheme's 's deletion capacity, following the analysis in Sekhari al. (2021). Due the space limit, we defer the definition and analysis Appendix B.2.

---

Published as a conference paper at ICLR 2025
Algorithm 1: Hessian-Free Online Unlearning (HF) Algorithm
Stage I: Learning model W on dataset 5 = {2i] for
0, 1.... E do
for b = 0, 1....... + do
Gradient descent: We.b-1 f- We.b - Te.. [a [ EieB,,. Ve (We,ti
end end
Stage II: Pre-computing and Pre-storing unlearning statistics T(S) = {agg j=1² for
1,2,2 do
Recursive HVP based on Algorithm 2: E 14 +- Ee=d M. Mu) Ve(We,,(u)) u).
end
11 Stage III: Unlearning when user requests to forget the subset U= (=(u, و on model W
F. 12 Compute: W W-U f --W -- F, ot | Delete unlearning statistics: {a [am,Blj= 1=
U -U 13 Sample: n NO, oI), Return w W +
4.3 EFFICIENT UNLEARNING ALGORITHM DESIGN
Building on the foregoing techniques and analysis of Theorem 4, we propose a memory and compu- tationally efficient unlearning scheme in Algorithm 1. To the best of our knowledge, our algorithm one of the most efficient method, as it only requires a vector addition by utilizing pre-computed statistics. This is particularly advantageous in time-sensitive scenarios and non-optimal models.
We present our approach in Algorithm 1. In Stage we perform conventional model training. Upon completing the model training, proceed to Stage II, where we compute the unlearning statistics vector a for each sample u. To reduce computational complexity, we leverage the HVP
technique as described in Appendix B.3. The computed approximators { are then stored for further use.3 A deletion request initiates Stage III. In this stage, the indistinguishabiiity of the (e, 6) unnlearnin as defined in Definition 1, is achieved through single vector addition with noise perturbation. Notably, Algorithm does not necessitate accessing any datasets during Stage III.
4.4 COMPARISON TO EXISTING APPROACHES
We provide brief overview of the second-order unlearning algorithms and compare the complexity of our method with these works in terms of pre-computation, storage, and unlearning time. Newton Step (NS). Sekhari et al. (2021) proposed a certified unlearning algorithm by pre-computing Hessian 2 ((w;z)) When request arrives to forget U=(u,)
1m the update for NS is as follows:
W NS
= ー m
V2 (((;)))))
Σ (
Σ ve(w:u)) u,). JEU
(15)
m
jEU
Infinitesimal Jackknife (IJ). Suriyakumar al. (2022) builded upon the work of NS and facilitated forgetting by pre-computing and storing the inverse Hessian. The update for NS thus is as follows:
U IJ
w 1
V
(((
ve(w;y))
(16)
JEU
These methods fail to use HVP, for Hessian Σ EjEU v2l(w; uy) in NS and gradient Vl(w, uy) in both NS and IJ, (i) forgetting sample uj is unknown before deletion request arrives, and (ii) the learned empirical risk minimzer w will be deleted after processing a deletion request, while subsequent unlearned model is also unknown forgetting sample u, is unpredictable. Therefore, explicit pre-computing is required for Σn [((w; 2,) in NS and (E (2((W;; in IJ.
'Storing additional data- dependent vectors may incur supplementary privacy risks. A straightforward solution is to have the users retain custody of these vectors. Analogous to Ghazi et al. (2023), upon submitting deletion request, the user is then required to furnish the corresponding approximators as part of the deletion request.
7

---

Published as a conference paper at ICLR 2025
Comparison of Precomputation. For single data, Algorithm entails computing the HVP O(En/IB) times. To precompute the Hessian-free (HF) approximators ayF for all n samples, the complexity is O(n'dE/IB)) Typically, the ratio of E' to [B] is much smaller than d or (Smith (2018)), which simplifies the complexity to (n)2)) HF method is highly efficient when dealing with overparameterized models, especially when d n. This is because computing the full Hessian for NS requires ((nd²) time, and computing and inverting the Hessian H for IJ requires (nd+).)..
Comparison of Storage. When compute the approximator, it requires storing ( (B]) models in Stage I, leading to a maximum complexity of ((ndE/1B) + nd). which can simplify to ((2n)). After complete precomputing. Algorithm only needs the storage of (nd). This is lower than the overhead introduced by storing matrices for NS and I/ in overparameterized models, which is (dd))
Comparison of Unlearning Computation. When an unlearning request with m forgetting data arrives, Algorithm I utilizes precomputed and prestored approximators to achieve forgetting, requiring a simple vector addition that takes ((md) time. For NS, requires computing and inverting different Hessian that depends on the user requesting the deletion. This necessitates substantial computational cost of O Od ([dd+mmmmmm) each time a deletion request arrives. Although IJ reduces this to +d2) by precomputing the inverse Hessian, it is still not as efficient compared to our method.
EXPERIMENTS FROM DEVELOPER'S PERSPECTIVE
We devised the following experimental components: Verification and @ Application. Verification experiments are centered on evaluating the disparity between the unlearning model w WF,B and retrained models WE across both convex and non-convex settings. Application experiments are geared towards evaluating the performance of different unlearning algorithms after perturbing w WE.B with noise n with a specific focus on determining the accuracy, pre-computation/sttraa and unlearning time. Considering the space limit, we defer a portion of experiments to the Appendix D.
-U
5.1 VERIFICATION EXPERIMENTS
Our principal aim is validate the differences between the proposed Hessian-free (HF) approximator aμF U and the actual w W W where a smaller difference indicates the unlearned model is closer to retrained model and also reflects the degree of data forgetting. Therefore, we evaluate the degree of forgetting from two perspectives: distance and correlation. Specifically, we use the n.2mnorm ||wE,8 - WE.B- "| to measure the distance metric. A smaller distance metric indicates the approximators accurately capture the disparity between the retrained and learned models. Additionally, we utilize the Pearson (Wright (1921)) and Spearman (Spearman (1961)) coefficients WE,B by mapping them from nigh-dimensional space scalar loss values, i.e. the approximate loss change f(WE,B U; U-- ((w E,B; U) and the actual change f(w E. -U)-((EE,))) B.B; ((: U' on the forgetting dataset U. The correlation scores range from to 1, where the higher score, the more the unlearned model performs like the retrained model.
to assess the correlation between a -U and W -U!
Configurations:
We conduct experiments in both convex and non-convex scenarios. Specifically, we trained a multinomial Logistic Regression (LR) with total parameters d = 7850 and a simple convolutional neural network (CNN) with total parameters d = 21840 on MNIST dataset (Deng (2012)) for handwriting digit classification. We apply a cross-entropy loss and the inclusion of an 1.-regularizzation coefficient of 0.5 to ensure that the loss function of LR is strongly convex. For LR, training was performed for 15 epochs with a stepsize of 0.05 and a batch of 32. For CNN, training was carried out for 20 epochs with a stepsize of 0.05 and batch size of 64. Given these -U -U Basu et al. (2021), a damping factor of 0.01 is added to the Hessian to ensure its invertibility when implementing NS and IJ. Besides, conducted experiments with 7 random seeds to obtain average results. For the sake of clear visualizations, we use the minimum and maximum values as error bars.
configurations, we separately assess the distance and correlation between approximators AHF a -
ag deletion rates in the set (1%, 5%, 10%, 15%, 20%, 25% 30%). Following the suggestion in
'Deep networks for computation vision tasks are typically trained with a number of model parameters that far exceeds the size of the training dataset (Chang et al. (2021)). For general neural language model, the empirical parramtee scaling law also expected remain d 0.74 suggested in Kaplan al. (2020).
8

---

Published as a conference paper at ICLR 2025
Euglideum Bistance
0.00
Iropried Hethod
Spearman Pearson 2
50
Spearman Pearzon 0
0.6
0.8
0.20
40
0.2
Euclidenn
6.10
6.05
Deletion Rates
Deletion Rates
Deletion Rates
Deletion Rates
(a) Convex Setting
(b) Non-Convex Setting
Figure 1: Verification experiments I on (a) LR and (b) CNN, respectively. The left of (a)(b) shows I].
the distance to the retrained model, i.e. || W B a a correlation between the approximate loss change and actual loss change on the forgetring dataset.
The right of (a)(b) shows the
Table 2: Application experiments I. An online scenario with 20% samples to be forgotten, where each unlearning request involves forgetting single data point with each execution. A performance
gap against Retrain is provided in (.). We compute the total computational/storagg cost for all samples.
Unlearning Computation
Pre-Computaion
Storage
Test Accuracy (%)
Model
Runtime (Sec)
Speedup
Runtime (Sec)
(GB)
Unlearned model
LR
x.09 x 10
1.34x
2.55x 10
0.23
86.25 (-1.50)
NS
CNN
5,81 x 10
0.12x
2.91x 104
1.78
83.50 (-10.25)
LR
0.23 102
29.64
2.55x
0.23
86.25 (-1.50)
CNN
1.91 x02
3.63x
x.9
1.78
82.75 (-11.00)
LR
0.0073
93,376x
2,20x 102
0.03
87.50 (-0.25)
HF
CNN
0.0268
25,821
5.34x 102
0.08
91.50 (-2.25)
The convex setting. As shown in Figure 1 (a), our approach outperforms previous works. First, by distance evaluation, the approximation error || -0 E.B of the proposed method is lower than that of the previous NS and works. At deletion rate 30%, the error 0.2097, lower than that of NS and IJ, which have errors of 0.246554 and 0. 0.246557, respectively. Second, in assessing the loss change for the forgotten dataset U, our proposed method more accurately captures the actual changes. Particularly when removing 30% of the samples, the proposed method maintains a high correlation, with Pearson and Spearman being 0.96 and 0.95, respectively. These evaluations demonstrate the efficacy of both Hessian-free and Hessian- based methods in accurately approximating the retrained model. Our proposed approach not only achieves closer approximation to the retrained model but also exhibits lower complexity compared to previous methods. This substantiated by the results of Application Experiments I, which provide empirical evidence supporting our theoretical findings.
The non-convex setting. As illustrated in Figure (b), the proposed HF method demonstrates superior performance, exhibiting less dependency random variations compared to NS and IJ. When 30% of the samples are removed, our method maintains lower approximation error of 0.90, surpassing the performance of NS and IJ. Our methods achieve Spearman and Pearson correlation coefficients of 0.81 and 0.74, respectively, accurately capturing actual loss changes, contrast to NS and IJ which are far from the actual values in non-convex settings. In Appendix D.2, explain the volatility of the results in the prior works on non-convex setting, and provide more large-scale results, which not achievable in NS and /J (Sekhari et al. (2021); Suriyakumar al. (2022): Liu et al. (2023)) due to out-of-memory to precisely computing the Hessian matrix (or its inverse).
5.2 APPLICATION EXPERIMENTS
We compare the cost and performance of our method with the previous certified unlearning methods. Evaluations are conducted from two perspectives: runtime and utility. Specifically, runtime focuses on the time spent pre-computing unlearning statistics and the speedup of the unlearning algorithm compared to the retraining. Moreover, evaluate the utility by the test accuracy of unlearned model to ensure generalization guarantee. We train LR and CNN with 20% data to be forgotten, where the configuration is identical to the foregoing verification experiments I. We conduct experiments with the unlearning guarantee = 1, 10 3 for LR and e 100, 8 0.1 for CNN. We provide larger scale results in Appendix D.3, and have not evaluated NS and IJ due out-of-memony

---

Published as a conference paper at ICLR 2025
Target Model: LR
Target Model: CNN
Tared 1ob
Area Under the Curve (AUC)
1.0
Progoned Mestoal
True Positive Rate
True Positiive Rate
ALCC
80%
Seatten Stap
50%
ARCC
ACC
10%
Prammet buil pac-- Min
Non- Hon-Comec
False Positive O5
False Positive Rate
Figure 2: Membership Inference Attack I. The first plot shows the MIA-L and error bars show 95% confidence intervals; the second and third plots depict the MIA-U results; and the fourth plot illustrates the privacy-utility tradeoff. Proposed method successfully defends MIA-L and mitigates excessive privacy leakage from MIA-U without sacrificing performance when applied with appropriate noise.
Application experiment results, Table 2 demonstrates that the proposed algorithm outperforms other baselines by significant margin. Strikingly, the proposed algorithm outperforms benchmarks of certified unlearning regarding all metries with millisecond-level unlearning and minimal performance degradation in both convex and non-convex settings. When models exceed the complexity of LR, precisely estimating the full Hessian becomes infeasible. This conclusion is supported by Table 2 and Mehta al. (2022). Therefore, demonstrate that the proposed Hessian-free perspective method exhibits great potentials for over-parameterizee models compared to the Hessian-bbsse approaches.
6 EXPERIMENTS FROM ADVERSARY'S PERSPECTIVE
To further investigate the effectiveness of data removal for auditing, we perform membership inference attack (MIA) experiments from the attacker's perspective, including two state-of-the-an art MIA: O MIA against Learning (MIA-L) (LiRA MIA Carlini al. (2022)) and @ MIA against Unlearning (MIA-U) (Chen et al. (2021)). Specifically, MIA-L enables an adversary to query a trained ML model to predict whether specific example was included in the model's training dataset; MIA-U involves querying two versions of the ML model to infer whether target sample is part of the training set of the learned model but has been removed from the corresponding unlearned model (primarily targeting retrain algorithm). See Appendix D.4 for detailed introduction and more experimental results.
MIA results with 5% data to be forgotten. As shown in the first plot of Figure 2, our proposed method effectively defends against MIA-L even in low-privacy scenarios, evidenced by effective approximation of the retrained model in the verification experiment. However, MIA-U exploits discrepancies between the outputs of the model's retrained and original versions. The verification experiment also reveals that our unlearned model's s loss change correlation coefficient is closely aligned with that of the retrained model, indicating that, like the retrained model, it is similarly vulnerable to such attacks. As depicted in the second and third plots, MIA-U shows high AUC values for the retrained method (light red line) and our method (red line) without perturbation (e oo). Nevertheless, adding appropriate noise to the model can mitigate MIA-U. As demonstrated in the fourth plot, introducing an appropriate noise level (c for LR and c 120 for CNN) effectively reduces the excessive privacy leakage without compromising performance. Besides, further increasing the model perturbation tradeoff privacy- utilliy does not significantly reduce the effectiveness of such attacks. To better defend MIA-U, we will consider measures like noised SGD in future work.
CONCLUSION
We proposed novel Hessian-free certified unlearning method. Our analysis relies on an affine stochastic recursion to characterize the model update discrepancy between the learned and retrained models, which does not depend on inverting Hessian and model optimality. We provide results of unlearning, generalization, deletion capacity guarantees, and time/memory complexity that are superior to state-of- ofate-of-the-ase art methods. We then develop an algorithm that achieves near-instantaneonn unlearning. We show that the proposed method can reduce the precomputation time, storage, and unlearning time to On²d), O (nd). Odd. respectively. Experimental results validate that our work benefits certified unlearning with millisecond-level unlearning time and improved test accuracy.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGMENTS
This work was supported in part by NSF grants CMM1-2024774 and ECCS-2030251, and in part by the National Natural Science Foundation of China under Grant 62202427.
REFERENCES
Krizhevsky Alex. Learning multiple layers of features from tiny images. https://www. cs. toronto. TR. pdf. 2009. 29
Borja Balle and Yu-Xiang Wang. Improving the gaussian mechanism for differential privacy: Analyt- ical calibration and optimal denoising. In Jennifer G. Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsmässan. Stock- holm. Sweden, July 10-15, 2018, volume 80 of Proceedings of Machine Learning Research, pp- 403 412. PMLR, 2018. 4
Samyadeep Basu, Xuchen You, and Soheil Feizi. On second-order group influence functions for black-box predictions. In Proceedings of the 37th International Conference on Machine Learning. ICMI. 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pp. 715-724. PMLR, 2020. 17, 29, 30
Samyadeep Basu, Phillip Pope, and Soheil Feizi. Influence functions in deep learning are fragile. In 9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021. OpenReview.net, 2021. 8, 17, 29, 30
Alexander Becker and Thomas Liebig. Certified data removal in sum-product networks. In Peipei Li, Kui Yu, Nitesh V. Chawla, Ronen Feldman, Qing Li, and Xindong Wu (eds.), IEEE International Conference on Knowledge Graph, ICKG 2022, Orlando, FL, USA, November 30 Dec. 2022, pp. 14-21. IEEE, 2022. 3
Lucas Bourtoule, Varun Chandrasekaran, Christopher A. Choquette- Chho, Hengrui Jia, Adelin Travers, Baiwu Zhang, David Lie, and Nicolas Papernot. Machine unlearning. In 42nd IEEE Symposium on Security and Privacy, SP 2021, San Francisco, CA, USA, 24-27 May 2021, pp. 141-159, IEEE, 2021. 17, 32
Jonathan Brophy and Daniel Lowd. Machine unlearning for random forests. In Marina Meila and Tong Zhang (eds.), Proceedings of the 38th International Conference Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event, volume 139 of Proceedings of Machine Learning Research, pp. 1092-1104. PMLR, 2021. 17
Yinzhi Cao and Junfeng Yang. Towards making systems forget with machine unlearning. In 2015 IEEE Symposium on Security and Privacy, SP 2015, San Jose, CA, USA, May 17-21, 2015, pp. 463-480. IEEE Computer Society, 2015. 3, 17
Nicholas Carlini, Steve Chien, Milad Nasr, Shuang Song, Andreas Terzis, and Florian Tramèr. Membership inference attacks from first principles. In 43rd IEEE Symposium on Security and Privacy, SP 2022, San Francisco, CA, USA, May 22-26, 2022, pp. 1897-1914. IEEE, 2022. 10, 32
Xiangyu Chang, Yingcong Li, Samet Oymak, and Christos Thrampoulidis. Provable benefits of overparameterization in model compression: From double descent to pruning neural networks. Artificial Intelligence, AAAI 2021, Thirty-Thire Conference
In Thirty-Fifth AAAI Conference on Innovative Applications of Artificial Intelligence, IAAI 2021, The Eleventh Symposium on Educational Advances in Artificial Intelligence, EAAI 2021, Virtual Event, February 2-9, 2021, pp. 6974-6983. AAAI Press, 2021. 8
Chong Chen, Fei Sun, Min Zhang, and Bolin Ding. Recommendation unlearning. In Frédérique Laforest, Raphaël Troncy, Elena Simperl, Deepak Agarwal, Aristides Gionis, Ivan Herman, and Lionel Médini (eds.), WWW '22: The ACM Web Conference 2022, Virtual Event, Lyon, France, April 25 29, 2022, pp. 2768-2777 ACM, 2022a. 3, 17

---

Published as a conference paper at ICLR 2025
Min Chen, Zhikun Zhang, Tianhao Wang, Michael Backes, Mathias Humbert, and Yang Zhang. When machine unlearning jeopardizes privacy. In Yongdae Kim, Jong Kim, Giovanni Vigna, and Elaine Shi (eds.), CCS 221 2021 ACM SIGSAC Conference Computer and Communications Security, Virtual Event, Republic of Korea, November 15 19, 2021, pp. 896-911. ACM, 2021. 10, 32, 33
Min Chen, Zhikun Zhang, Tianhao Wang, Michael Backes, Mathias Humbert, and Yang Zhang. Graph unlearning, In Heng Yin, Angelos Stavrou, Cas Cremers, and Elaine Shi (eds.), Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security, CCS 2022, Los Angeles, CA, USA, November 7-11, 2022, pp. 499-513. ACM, 2022b. 3, 17
Xiangyi Chen, Steven Z Wu, and Mingyi Hong. Understanding gradient clipping in private sgd: A geometric perspective. Advances Neural Information Processing Systems, 33:13773-13782. 2020. 36
Eli Chien, Chao Pan, and Olgica Milenkovic. Efficient model updates for approximate unlearning of graph-structured data. In The Eleventh International Conference on Learning Representations, 2022. 1, 2, 3, 17, 21
Mathieu Dagréou, Pierre Ablin, Samuel Vaiter, and Thomas Moreau. How to compute hessian-vector products? In The Third Blogpost Track at ICLR 2024, 2024. 5, 19
Li Deng. The mnist database of handwritten digit images for machine learning research. IEEE Signal Processing Magazine, 29(6); 141-142, 2012. 8
Cynthia Dwork. Differential privacy. In International colloquium on automata, languages, and programming, pp. 1-12. Springer, 2006. 17
Cynthia Dwork and Aaron Roth. The algorithmic foundations of differential privacy. Found. Trends Theor. Comput. Sci., (13-4):211-407 2014.
Badih Ghazi, Pritish Kamath, Ravi Kumar, Pasin Manurangsi, Ayush Sekhari, and Chiyuan Zhang. Ticketed dearning-unlearnigg schemes. In Gergely Neu and Lorenzo Rosasco (eds.), The Thirty Sixth Annual Conference on Learning Theory, COLT 2023, 12-15 July 2023, Bangalore, India, volume 195 of Proceedings of Machine Learning Research, pp. 5110-5139, PMLR, 2023. 7
Justin Gilmer, Behrooz. Ghorbani, Ankush Garg, Sneha Kudugunta, Behnam Neyshabur, David Cardoze, George Edward Dahl, Zachary Nado, and Orhan Firat. A loss curvature perspective on training instabilities of deep learning models. In International Conference on Learning Represen- tations, 2022. 18, 34,35 35
Antonio Ginart, Melody Guan, Gregory Valiant, and James Zou. Making ai forget you: Data deletion in machine learning. Advances in neural information processing systems, 32, 2019. 17
Aditya Golatkar, Alessandro Achille, and Stefano Soatto. Eternal sunshine of the spotless net: Selective forgetting in deep networks. In 2020 IEEE/CVF Conference on Computer Vision and Pattern Recognition, CVPR 2020, Seattle, WA, USA, June 13-19, 2020, pp. 9301-9309. Computer Vision Foundation / IEEE, 2020a. 3, 17
Aditya Golatkar, Alessandro Achille, and Stefano Soatto. Forgetting outside the box: Scrubbing deep networks of information accessible from input-output observations. In Andrea Vedaldi, Horst Bischof, Thomas Brox, and Jan-Michael Frahm (eds.). Computer Vision ECCV 2020 16th European Conference, Glasgow, UK, August 23-28, 2020, Proceedings, Part XXIX, volume 12374 of Lecture Notes in Computer Science, pp. 383-398. Springer, 2020b. 17
Aditya Golatkar, Alessandro Achille, Avinash Ravichandran, Marzia Polito, and Stefano Soatto. Mixed-privace forgetting in deep networks. In IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2021, virtual, June 19-25, 2021, pp. 792-801. Computer Vision Foundation IEEE, 2021. 17
Priya Goyal, Piotr Dollár, Ross B. Girshick, Pieter Noordhuis, Lukasz Wesolowski, Aapo Kyrola, Andrew Tulloch. Yangqing Jia, and Kaiming He. Accurate, large minibatch SGD: training imagenet in 1 hour. CoRR, abs/1 706.02677 2017. 4
12

---

Published as a conference paper at ICLR 2025
Chuan Guo, Tom Goldstein, Awni Y. Hannun, and Laurens van der Maaten. Certified data removal from machine learning models. In Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pp- 1832-3842 PMLR, 2020. 1, 3, 17
Varun Gupta, Christopher Jung. Seth Neel, Aaron Roth, Saeed Sharifi-Malvajerde and Chris Waites. Adaptive machine unlearning. In Mare' Aurelio Ranzato, Alina Beygelzimer. Yann N. Dauphin, Percy Liang, and Jennifer Wortman Vaughan (eds.), Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurlPS 2021, December 6-14, 2021, virtual, pp. 16319-16330, 2021.
Mert Gürbüüzalaban, Umut Simsekli, and Lingjiong Zhu. The heavy-tail phenomenon in SGD. In Marina Meila and Tong Zhang (eds.), Proceedings of the 38th International Conference Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event, volume 139 of Proceedings of Machine Learning Research, pp. 3964 3975. PMLR, 2021.
Anisa Halimi, Swanand Kadhe, Ambrish Rawat, and Nathalie Baracaldo. Federated unlearning: How to efficiently erase a client in f?? arXiv preprint
2022. 17
Boris Hanin. Which neural net architectures give rise to exploding and vanishing gradients? In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett (eds.), Advances Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018. 36
Satoshi Hara, Atsushi Nitanda, and Takanori Maehara. Data cleansing for models trained with SGD. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d' Alché-Bucc Emily B. Fox, and Roman Garnett (eds.), Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pp. 4215 4224, 2019. 17
Elad Hazan. Introduction online convex optimization. Found. Trends Optim.,, 2(3 2016. 2
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In 2016 IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2016, Las Vegas, NV, USA, June 27-30, 2016, pp. 770-778. IEEE Computer Society, 2016. 29, 31
Gary B. Huang, Manu Ramesh, Tamara Berg, and Erik Leamed-Miller, Labeled faces in the wild: database for studying face recognition in unconstrained environments. Technical Report 07-49, University of Massachusetts, Amherst, October 2007. 29
Zachary Izzo, Mary Anne Smart, Kamalika Chaudhuri, and James Zou. Approximate data deletion from machine learning models. In Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, pp. (008-2016. 2021. 3, 30
Matthew Jagielski, Om Thakkar, Florian Tramèr, Daphne Ippolito, Katherine Lee, Nicholas Carlini, Eric Wallace, Shuang Song, Abhradeep Guha Thakurta, Nicolas Papernot, and Chiyuan Zhang Measuring forgetting of memorized training examples. In The Eleventh International Conference on Learning Representations, ICLR 2023, Kigali, Rwanda, May 1-5, 2023. OpenReview.net, 2023.
Jared Kaplan, Sam McCandlish, Tom Henighan, Tom B. Brown, Benjamin Chess, Rewon Child, Scott Gray, Alec Radford, Jeffrey Wu, and Dario Amodei. Scaling laws for neural language models. CoRR, abs/2001.08861,, 2020. 8
Korbinian Koch and Mareus Soll. No matter how you slice it: Machine unlearning with sisa comes at the expense of minority classes. In 2023 IEEE Conference on Secure and Trustworthy Machine Learning (SaTML), pp. 622-637. IEEE, 2023. 17
Pang Wei Koh and Percy Liang. Understanding black- box predictions via influence functions. In Doina Precup and Yee Whye Teh (eds.), Proceedings of the 34th International Conference on Machine Learning. ICML 2017, Sydney, NSW. Australia, 6-11 August 2017, volume 70 of Proceedings of Machine Learning Research, pp. 1894. PMLR, 2017. 17, 21
13

---

Published as a conference paper at ICLR 2025
Meghdad Kurmanji, Peter Triantafillou, Jamie Hayes, and Eleni Triantafillou. Towards unbounded machine unlearning. Advances in Neural Information Processing Systems, 36, 2024. 17
Xiaoyu Li, Zhenxun Zhuang, and Francesco Orabona. A second look at exponential and cosine step sizes: Simplicity, adaptivity, and performance. In Marina Meila and Tong Zhang (eds.), Proceedings of the 38th International Conference Machine Learning. ICML 2021, 18-24 July 2021, Virtual Event, volume 139 of Proceedings of Machine Learning Research, pp. 6553-6566 PMLR, 2021. 24
Jiaqi Liu, Jian Lou, Zhan Qin, and Kui Ren. Certified minimax unlearning with generalization rates and deletion capacity. In Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, NeurIPS 2023., 2023. 1, 2, 3, 5, 6, 9, 17, 21, 30
Ziwei Liu, Ping Luo, Xiaogang Wang, and Xiaoou Tang. Deep learning face attributes in the wild. In Proceedings of International Conference Computer Vision (ICCV), December 2015. 29
Ananth Mahadevan and Michael Mathioudakis. Certifiable machine unlearning for linear models.
CoRR, abs/2106 0ess21006150990 15093, 2021. 2,
Vien V Mai and Mikael Johansson. Stability and convergence of stochastic gradient clipping: Beyond lipschitz continuity and smoothness. In International Conference on Machine Learning, pp. 7325-7335. PMLR, 2021. 36
Ronak Mehta, Sourav Pal, Vikas Singh, and Sathya N. Ravi. Deep unlearning via randomized conditionally independent hessians. In IEEE/CVF Conference on Computer Vision and Pattern Recognition, CVPR 2022, New Orleans, LA, USA, June 18-24, 2022, pp. 10412-10421. IEEE, 2022. 3, 10, 17
Seth Neel, Aaron Roth, and Saeed Sharifi- Manejii-MMi..jrrdi... Descent-to-dellte: Gradient-based methods for machine unlearning. In Vitaly Feldman, Katrina Ligett, and Sivan Sabato (eds.), ), Algorithmic Learning Theory, 16-19 March 1021, Virtual Conference, Worldwide, volume 132 of Proceedings of Machine Learning Research, pp. 931-962. PMLR, 2021.
Quoc Phong Nguyen, Bryan Kian Hsiang Low, and Patrick Jaillet. Variational bayesian unlcarning. In Hugo Larochelle, Marc' Aurelio Ranzato, Raia Hadsell, Maria- Maria-Florina Balcan, and Hsuan- Tien Lin (eds.), Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurlPS 2020, December 6-12, 2020, virtual, 2020.
Barak A. Pearlmutter. Fast exact multiplication by the hessian. Neural Comput., 6(1):147-160, 1994.
Levent Sagun, Leon Bottou, and Yann LeCun. Eigenvalues of the hessian in deep learning; Singularity and beyond. arXiv preprint arXiv:1611.07476, 2016. 36
Levent Sagun, Utku Evci, V. Ugur Güney, Yann N. Dauphin, and Léon Bottou. Empirical analysis of the hessian of over-parametriize neural networks. In 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 May 3, 2018, Workshop Track Proceedings. OpenReview.net, 2018. 36
Sebastian Schelter, Stefan Grafberger, and Ted Dunning. Hedgecut: Maintaining randomised trees for low-latency machine unlearning. In Guoliang Li, Zhanhuai Li, Stratos Idreos, and Divesh Srivastava (eds.), SIGMOD '21: International Conference on Management of Data, Virtual Event, China, June 20-25, 2021, pp. 1545-1557. ACM, 2021. 3, 17
Ayush Sekhari, Jayadev Acharya, Gautam Kamath, and Ananda Theertha Suresh. Remember what you want forget: Algorithms for machine unlearning. In Advances in Neural Information Processing Systems 34, NeurlPS, pp. 18075-18086, 2021. 1, 2, 3, 4, 5, 6, 7, 9, 17, 18, 19, 29, 30
Shai
Ohad Shamir, Nathan Srebro, and Karthik Sridharan. Stochastic convex optimization. In COLT 2009 The 22nd Conference on Learning Theory, Montreal, Quebec, Canada, June 18-21, 2009, 2009. 27
14

---

Published as a conference paper at ICLR 2025
Leslie N Smith. A disciplined approach to neural network hyper-parammetes: Part 1 1-learning rate, batch size, momentum, and weight decay. arXiv preprint arXiv:/803.09820, 2018. 8
Charles Spearman. The proof and measurement of association between things. 1961. 8
Ningxin Su and Baochun Li. Asynchronous federated unlearning. In IEEE INFOCOM 2023 - IEEE Conference on Computer Communications, New York City, NY, USA, May 17-20, 2023, pp. 1-10. IEEE, 2023. 17
Vinith M. Suriyakumar, Ashia C. Wilson, al. Algorithms that approximate data removal: New results and limitations. In Advances in Neural Information Processing Systems 35, NewrlPS, 2022.
1, 6, 7, 9, 21, 29, 30
Ryutaro Tanno, Melanie F. Pradier, Aditya V. Nori, and Yingzhen Li. Repairing neural networks by leaving the right past behind. In NeurlPS, 2022.
Ayush Kumar Tarun, Vikram Singh Chundawat, Murari Mandal, and Mohan S. Kankanhalli. Deep regression unlearning. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett (eds.), International Conference on Machine Learning, ICML 2023, 23-29 July 2023, Honolulu, Hawaii, USA, volume 202 of Proceedings of Machine Learning Research, pp. 33921 33921-33939, 33939. PMLR, 2023. 3, 29
Alexander Warnecke, Lukas Pirch, Christian Wressnegger, and Konrad Rieck. Machine unlearning of features and labels. In 30th Annual Network and Distributed System Security Symposium, NDSS 2023, San Diego, Califormia, USA, February 27 March 3. 2023. The Internet Society, 2023. 3, 17
Sanford Weisberg and R Dennis Cook. Residuals and influence in regression. 1982. 21
Kaiyue Wen, Tengyu Ma, and Zhiyuan Li. How sharpness-aware minimization minimizes sharp- ness? In The Eleventh International Conference on Learning Representations, ICLR 2023, Kigali, Rwanda, May 1-5, 2023. OpenReview.net, 2023. 18
Sewall Wright. Correlation and causation. Journal of agricultural research, 20(7):557-585, 1921. 8
Ga Wu, Masoud Hashemi, and Christopher Srinivasa. PUMA: performance unchanged model augmentation for training data removal. In Thirty-Sixth AAAI Conference on Artificial Intelligence, AAAI 2022, Foirty-Fourth Conference on Innovative Applications of Artificial Intelligence, IAAI 2022, The Twelveth Symposium on Educational Advances in Artificial Intelligence, EAAI 2022 Virtual Event, February 22- March 1, 2022, pp. 8675-8682, AAAI Press, 2022. 3, 17
Kun Wu, Jie Shen, Yue Ning, Ting Wang. and Wendy Hui Wang. Certified edge unlearning for graph neural networks. In Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, KDD '23, pp. 2606-2617, 2023. 17
Lei Wu, Chao Ma, and Weinan E. How SGD selects the global minima in over- aver-parameterized learning: A dynamical stability perspective. Samy Bengio, Hanna M. Wallach, Hugo Larochelle, Kristen Grauman, Nicolò Cesa- Bianchi, and Roman Garnett (eds.), Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurIPS 2018, December 3-8, 2018, Montréal, Canada, pp. 8289-8298, 2018. 34
Yinjun WU, Edgar Dobriban, and Susan B. Davidson. Deltagrad: Rapid retraining of machine learning models. In Proceedings of the 37th International Conference on Machine Learning. ICML 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pp. 10355 10366. PMLR, 2020. 3, 30
Haonan Yan, Xiaoguang Li, Ziyao Guo, Hui Li, Fenghua Li, and Xiaodong Lin. ARCANE: an efficient architecture for exact machine unlearning. In Proceedings the Thirty- First International Joint Conference on Artificial Intelligence, IJCAI 2022, Vienna, Austria, 23-29 July 2022, pp.
4013-4013, 2022. 3, 17
Binchi Zhang, Yushun Dong, Tianhao Wang, and Jundong Li. Towards certified unlearning for deep neural networks. arXiv preprint a4Xiv:2408. 00920, 2024. 17
Jingzhao Zhang, Tianxing He, Suvrit Sra, and Ali Jadbabaie. Why gradient clipping accelerates training: A theoretical justification for adaptivity. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020, 2020. 36
15

---

Published as a conference paper at ICLR 2025
CONTENTS OF APPENDIX
An Expanded Version of The Related Work
17
Discussions
18
B.1 Limitations and Future Works
18
B.2 Deletion Capacity Guarantee
B.3 Hessian-Vectte Products Technique in Stage II of Algorithm 1
19
B.4 Unleaming-RRppiring Strategy in Stage III of Algorithm 1
20
C Proofs
21
C.I Detailed Analysis of Equation (11)
C.2 Detailed Proof of Theorem
23
C33 Detailed Proof of Lemma
24
C,4 Detailed Proof of Theorem 4
24
C55 Additional Definitions of Assumption
26
C.6 Detailed Proof of Theorem 6
27
Supplementary Experiments
28
D.I Hardware, Software and Source Code
28
D.2 Additional Verification Experiments
D.3 Additional Application Experiments
31
D.4 Additional Adversary Experiments
32
E Sensitivity Analysis and Ablation Studies
33
E.1 Impact of Step Sizes
34
E.2 Impact of Epochs
35
E,3 Impact of Stepsize Decay
36
E,4 Impact of Gradient Clipping
36
16

---

Published as a conference paper at ICLR 2025
A AN EXPANDED VERSION OF THE RELATED WORK
Machine Unlearning, the terminology can be traced back to the paper of Cao & Yang (2015), and their work defined the notion of "the completeness of forgetting". There are two main categories based on the completeness of forgetting: Exact Unlearning and Approximate Unlearning-
Exact Unlearning aims to accelerate the speed of retraining and completely eliminate the influence of forgotten data on learned model. The majority of existing Exact Unlearning methods are derived from the work of Bourtoule et al. (2021), which proposed the notable SISA framework, grounded in ensemble learning techniques. Specifically, the training dataset is partitioned into mutually disjoint shards, and then sub-models are trained these shards. Upon unlearning, SISA only needs to retrain the sub-model correlated with the relevant data shard and then make the final prediction by assembling the knowledge of each sub-model, which significantly lowers retraining computational costs. Under the SISA framework, other Exact Unlearning methods have also been proposed, e.g., Chen et al. (2022b) extended SISA graph learning by partitioning the original training graph into disjoint shards, parallelly training a set of shard models, and learning an optimal importance score for each shard model. RecEraser (Chen al. (2022a)) extended SISA to recommendation systems. KNOT (Su & Li (2023)) adopted the SISA for client-level asynchronous federated unlearming during training and introduced clustered mechanism that divides clients into multiple clusters. Other methods, such as DaRE (Brophy& & Lowd (2021)) and HedgeCut (Schelter et al. (2021)), I), addressed the issue that SISA cannot be applied to decision trees and proposed exact unlearning solutions; and Ginart et al. (2019) aimed to achieve forgetting in K-means clustering. Furthermore, ARCANE (Yan et al. (2022)) introduced a bassed data partitioning strategy to enhance the performance of SISA.
However, the SISA framework adopts structure that completely separates the data, resembling ensemble learning approaches where predictions or models are aggregated only at the end. This separation restricts the model training process from fully leveraging the entirety of the segmented datasets and also hampers its extensibility, leading to lower accuracy and performance compared to a model trained on the entire unsegmented dataset. In experimental evaluation conducted by Koch & Soll (2023), it was found that simply down-sampling the data set to achieve a more balanced single shard outperforms SISA in terms of unlearning speed and performance.
Approximate Unlearning thus seeks to minimize the impact of forgetting data to an acceptable level to trade off computational efficiency, reduced storage costs, and flexibility. There are many approaches to approximate unlearning, such as Kurmanji et al. (2024) developed a distillation sesillation-based method; Halimi et al. (2022) adopted a gradient ascent approach on forgotten data to achieve forgetting. Among these, second-order methods have been widely studied, with most of these methods (e.g.. Sekhari et al. (2021); Suriyakumar al. (2022); Liu al. (2023); Chien al. (2022); Wu et al. (2023); Mehta et al. (2022); Warnecke et al. (2023); Wu et al. (2022)) inspired by influence function studies (Koh & Liang (2017); Basu et al. (2021; 2020); Hara et al. (2019)), aiming to extract information from the Hessian of loss function and achieve forgetting through limited model updates. In particular, inspired by differential privacy (Dwork (2006)), Guo et al. (2020) introduced certified unlearning (c. 8). anticipating ensuring that the output distribution of an unlearning algorithm is indistinguisaable from that of retraining. Moreover, due to costly Hessian operations, Fisher-baat based methods (Golatkar et al. (2020a;b; 2021)) have emerged approximate Hessian. Our paper concentrates on the Hessian- approach, yet obviates the need for Hessian inversion and explicit calculation of the Hessian.
Among these Hessian-based certified unlearning methods, Sekhari et al. (2021); Suriyakumar et al. (2022); Liu et al. (2023) established the theoretical foundation for Hessian-based methods and provided the generalization result in terms of the population risk, as well as derived the deletion capacity guarantee. In the definition of certified unlearning, their works align with our method, which lies in pre-computing statisties of data that extract second-order information from the Hessian and using these "recollections" to forget data. However, existing second-order methods still require expensive matrix computations and can only perform forgetting for optimal models under convexity assumption. Although Zhang et al. (2024) offered certified unlearning for deep model through adding sufficient large regularization to guarantee local strong convexity. but the optimality problem remains unsolved, particularly due to the non-convyxity of modern deep models, making impractical to find the empirical risk minimizer. Even for convex models, in most non-concurrent training scenarios, such online learning or continual learning, the model cannot converge to the optimal solution.
17

---

Published as a conference paper at ICLR 2025
B DISCUSSIONS
B.1 LIMITATIONS AND FUTURE WORKS
Limitations. Although we have made the above contributions, there are some significant limitations:
① Our proposed algorithm necessitates (nn²d) precomputation and ((nd) storage, which remains costly, particularly scenarios involving extensive data and larger-scale models. Consequently, conducting experiments concurrently with both large-scale datasets and models is anticipated to significantly extend the time required for precomputing unlearning statistics.
@ As demonstrated by the results in Theorem 4, it is important to recognize that the proposed method is highly sensitive to the the stability of the training process or well-conditioned Hessian on non-convex setting. The addition of a large explicit regullrlrr to the objective or utilizing small step sizes can ensure meaningful bound. However, we are not aware of any popular non-convex machine learning problem that can satisfy all the conditions of Theorem 4. If the learning process is unstable, unlearning will introduce significant error. For instance, Appendix E. employing an aggressive step size (17 0.1) can lead to a substantial increase in approximation error.
@ While we propose a new method that does not rely on convexity, our analysis builds upon the theoretical framework of previous works for comparison purposes and much of our theoretical results rely on convexity- except for our unlearning-relatee conclusions. Providing a nonconvex theoretical framework is meaningful, and we will explore potential extensions in further research.
Future work. Therefore, to solve the problems mentioned above, we briefly propose some solutions.
① Specifically, our proposed framework offers the feasibility to unlearn arbitrary subset of the entire datasets, allowing a trade-off that further reduces the precomputation and storage complexity, for instance, consider typical scenario at the user level, where there are users (k << n). By focusing on the unlearning of a single user's 's dataset or a subset of users' datasets, we can maintain vectors for & users' dataset instead of maintaining n vectors for all data points. Therefore, we can further reduce precomputation and storage to (kndd) and Okk)), respectively.
@ Moreover, based on our analysis in Theorem 4 and Appendix E. the main source of the approxima- tion error is p, which mainly consists of two components: the step size 7) and the maximum eigenvalue A of Hessian. Reducing the step size is straightforward method, but we cannot expect every training process to have a sufficiently small step size. Therefore, reducing a during optimization, will not only improve the generalization ability of the learned model but also reduce the approximation error in the unlearning stage. Possible approaches are through stepsize warm-up strategies (Gilmer et al. (2022)) or sharpness-aware minimization (Wen et al. (2023)) to effectively reduce Å₁-
B.2 DELETION CAPACITY GUARANTEE
We analyze the deletion capacity of our method based the analysis of Sekhari al. (2021), which formalizes how many samples can be deleted from the model parameterized by the original empirical risk minimizer while maintaining reasonable guarantees on the test loss. We establish the relationship between generalization performance and the amount of deleted samples through deletion capacity, and our analysis indicates that our proposed method outperforms previous works in both generalization and deletion capacity. The lower bound on deletion capacity can be directly derived from the generalization guarantee (Theorem 6). Below, we first formalize the deletion capacity.
Definition 2 (Definition of Deletion Capacity (Sekhari et al. (2021))). Lei e, ô 2 O. Let S be dataset of size n drawn i.i.d. from D. For pair of learning and unlearning algorithms Ω, that are nu, (c. 5)-eetiif unlearning, the deletion capacity m (d, n) is defined as the maximum number of
samples U to be forgotten, while still ensuring excess population risk is Specifically.
0.0 mi (d. max
(()(0()));((())F((())) S sn). USS.UUIm
max
(17)
where the expectation above is with respect S ~ D and output of the algoritimss Ω and f2
Similar to Sekhari et al. (2021), we provide upper bound and lower bound of deletion capacity for algorithm. We first give the upper bound of deletion capacity.
18

---

Published as a conference paper at ICLR 2025
Theorem (Upper Bound of Deletion Capacity Sekhari et al. (2021)). Let 8 S 0.005 and 1. There exists a 4-Lipschitz and I-strongly convex loss function f. and a distribution D such that for any learning algorithm A and removal mechanism M that satisfies (c, -e.le-unnn and has access to all remaining samples SXU then the deletion capacity is:
A.M (d. n)) S en
(18)
m,,6,7
where depends on the properties of function f and is strictly less than 1.
comprehensive proof of Theorem 7 is available in Sekhari et al. (2021). Furthermore, based on Theorem 6, we present the lower bound of deletion capacity below:
Theorem 8 (Deletion Capacity Guarantee). There exists learning algorithm Q and unlearning algorithm S2 such that for any convex (and hence strongly convex), L-Lipschitz, and M-Smoothness loss f and distribution D. Choose step size 1j S _2 and w F.B objective function Fsyu (.,U(),, (w), then we have
w-U is the empirical risk minimizer of M+3
R.ft (d, n) = ( m 6,6,7
(19)
Proof of Theorem 8. Based on Theorem 6, we have
4L2
+ 2L2
B 2Ta / (1/0))
F(WF-1,9 E[F (w") = 0 A(n - m)
(20)
e
Note that p < 1, The above upper bound on the excess risk thus implies that we can delete at least
(1/8)d1 pm) m m ( (I
(21)
MV
samples while still ensuring an excess risk guarantee of y. Accordingly, it yields order of O (db))"/db), Therefore, we have completed the proof.
B.3 HESSIAN- VECTOOR PRODUCTS TECHNIQUE STAGE II OF ALGORITHM
We provide the detailed Hessian- Vector Products (HVP) procedure in Algorithm 2. Notably, when recursively computing the product the matrix and an arbitrary vector (I - 7H)v, we can derive from лHv. Here, Hy involves HVP through modern automatic differentiation frameworks such as JAX or PyTorch. For more explanation of the HVP, please refer to Dagréou et al. (2024).
Algorithm Matrix Vector Products in Stage of Algorithm
Stage II: Pre-computing and Pre-storing statistics T(S) = {ag,BIja
in
initialization -M1 1a = 0, {v_ in J = O; {ag,B]j=1
for e 0, E E do
for 0, ... B 1, do
for == 1.2 do
Compute: a (I ne H He,t)a
(I Je,b H..6)
B.
if gradient of sample u, computed in this update step then ;4)
Uj Vl(w uy
else
e.b 0
11
end
12
end
13
end
end
19

---

Published as a conference paper at ICLR 2025
B.4 UNLEARNING- ONLEARNING-REPAIRING REPAIRING STRATEGY IN STAGE III OF ALGORITHM
While our approach does not require accessing any datasets in Stage III, we can mitigate the perfor- mance degradation caused by excessive deletions and make our algorithm more robust through simple fine-tuning strategy if we can still access the remaining dataset in Stage III. We only consider this as a preliminary attempt in this section; other experiments do include this Finetune strategy. This strategy allows our method to be used as a heuristic algorithm in non non-privacy scenarios, without the need for theoretical certified guarantees, such as in bias removal.
Specifically, when the continuous incoming deletion requests to forget data, we can rapidly implement data removal through vector addition. This involves augmenting the current model with approximators. where errors accumulate during this process and thus cause performance degradation. Suppose, upon arrival of a new round of deletion requests for particular model and dataset, the model's accuracy significantly drops due the removal of substantial amount of data. As remedy in Algorithm 3, we can address this performance degradation by fine-tuning the current model for E, epochs the remaining dataset, referred to the 'repairing" process. Additionally, by computing the approximators for the remaining dataset during the repairing process, and adding these approximators during the repairing process to the pre-stored approximators during the learning process, obtain the new set of approximators for the remaining data. In Figure 3, we conduct an experiment on ResNet- 18 using the CelebA dataset demonstrate the efficacy of the repairing strategy.
85
Teal Actursty
Unkeaming 23%
65-
Reparing
Unkerring 43%
02
Riporing
Epach
Figure 3: Unlearning-Repaiine Strategy. The blue, red, and green lines respectively represent the learning, unlearning, and repairing process. When a significant amount of data is removed, leading loss in model performance, performing fine-tuning the remaining dataset and recording the approximators during this period can help avoid performance degradation.
Algorithm 3: Hessian-Free Cilearning-Repairii Strategy in Stage III of Algorithm 1
Stage III: Unlearning when user requests to forget the subset (=(u,) on model WF,B"
2lm(1. -- UU
Compute: WE.B < Wg.B+ag et | Sample: n ~ (0, oI), Return: WE.B E,
Delete statisties: {ag,B)
Reparing (Fine-tuning) the model w E,B on the remaining dataset SAU = {=r)>-1 In-m,
for e = 0..,, do
for b 0....... do
Compute gradient: g [B,s EreB, Vl(We,
Gradient descent: We.b- f- We. 11,58
end Pre-computing statistics T(S) = (ag u. n-m the remaining dataset SYU = {2r 1r
10 end
12-m,
11
12 for r= 1,2 m do
13
Recursive computation by using HVP based on Algorithm
14 AE+E,.B +- -E. (e))( Ve(w ((.ee.((.)):))) + Hg.. B--.BB---,,00 10..)-1-0 - where: McMau) = Ne.b(u)) M
H B-
15
16 end
20

---

Published as a conference paper at ICLR 2025
C PROOFS
C.I DETAILED ANALYSIS OF EQUATION (11)
Before proceeding with the analysis of our method, we will first provide the analysis of previous works (Suriyakumar et al. (2022); Liu et al. (2023); Mahadevan & Mathioudakis (2021); Chien et al. (2022); Liu et al. (2023)) and discuss the circumstances that lead to its failure.
We first assume that the empirical risk in Equation (2) is twice-differentibble and strictly convex in the parameter space W. The original empirical risk minimizer can be expressed as
W arg min weW
Fs arg min weW
Σ (.: n
1
(22)
We reweight the sample u in the original empirical risk with weighting factor w.
W
= arg min WEW
((w; 21) + wl(w;
1m1
(23)
where
3
T
When weighting factor -1 13 Equation (23) is equivalent to the empirical risk minimizer without samle u. i.e. removing a training point u is similar to up-weighting its corresponding weight by - Following the classical result of Weisherg & Cook (1982), Koh & Liang (2017) aimed to approximate w- by the first-order Taylor expansion around the optimal learned model w, given by,
W
W
~
dw
V2 ((w((: 25)
Ve(w; u).
(24)
dw
However, we note that these works rely on several key assumptions: the convexity of the objective function ensure the invertibility of the Hessian matrix, and the optimality of the learned model. These assumptions are often stringent and may not be satisfied in practice, particularly in modern machine learning scenarios where the objective function may be non-convex and the empirical risk minimizer may not be attainable. In addition, in over- over-varamenn parameterized models, the computation of the Hessian matrix also requires a significant memory overhead.
In fact, aside from the optimal model, the training process contains more information, and our method aims utilize the information from the training process to address both issues simultaneously. Here, provide more detailed explanation for Equation (11). Specifically, of sample u during the e-th epoch, and then extend the analysis to all epochs. should be noted that necessary setting for method is that the retraining and learning process have the same initialization, model architecture, and training process.
first consider the impact
Analysis of Equation (I1). For ease of understanding, each sample appears only in one (mini-)batch per epoch. The update rule for the model parameters is typically given by,
WE,B41 < WE,B BE
7E
Σ Ve(WE,B;2))
(25)
iEBg.
Without loss of generality, for the e-th epoch, we define the sample u to be sampled in the e-th epoch's b(u)-th update. Reweighting the sample u in the each update process (rather than the empirical risk) with a weighting factor Equation (3) and Equation (4) can be represented by
WE t- WEB
TE.B
(VE(WE,Bi2) + +1 In- VL V iEBE,
Σ
(26)
B
where 1 bb= is an indicator function that equals I if the condition b = b(u) is true (that is, sample u is to be involved (sampled) in the b(u)-th update of the e-th epoch), and 0 otherwise. We define that when w 0, Equation (26) represents the original learning update, whereas -1 represents the
21

---

Published as a conference paper at ICLR 2025
update after forgetting training sample To obtain the difference between the learning model and retraining model, we calculate the derivative W8,8+1 w.r.t the weighting factor at w = 0, given by,
dw E+
W E WE,8+1 WE,B+llu=- WE,B+1
(27)
dw
w==
Based on the chain rule, we have,
dw
d.1. dW
(28)
dw
dwg
dw -==
w=0
Let H..bb = 1//1a,, EieB,,, V We.bi zi) denote the Hessian matrix of the loss function. For
Equation (26), we have that
dwg. 1WE.B11
HE,BHE,B Substituting into Equation (28).
dw 1,
(I 7E NE, dWE.B de which is equivalent to Equation (8) in the main text (Case 1), that is, We,b).
dw
(29)
dw
w=0
Webb+1 (I Me.
(30)
ebb+1
Recursively applying the chain rule until b==(()) = 1 during E-th epoch,
b(x)+1
d.
II
dw dW dw 1, for Equation (26), we obtain,
(I ME E,6))
(31)
du
b=
When the indicator function b==((u)
dw (.a)+1)+
dw (,
dW (.E)(()) dw
NE VI (WE,b(w)iu)
IIE HE,((U)
dw
dw
|BE
-=
(32)
which is equivalent to Equation (9) the main text (Case 2), that is, =,b(a)++1 We,b())+1 (I- (e) H He) e,b(u) We.b(u)) Substituting Equation (32) into Equation (31),
Ne,((u) (Be)((u)
Ve((e,b(w)uu). (33)
b(u)
b(u)+1
dw E,B+1
II
II (I- (E,
dw E.b(u) dw
Ne.b
II
(I
ME,HEN Ve (WF,M))):))
di
[B.bb
-=0
b= B
-==
b=
(34)
Therefore, the impact of sample on the model update trajectory during the E-th round is.
II HE. WE,
E.
WEBB R
6- B-1
(35)
b(u)+11
V((WR,Mu))))) II (I Hg, [B,,())]
(E)(())
bm 13
Since initially the retraining model w and the learning model Wo,0 are the same, the first term of Equation (35) will recursively reduce to the initial model and will equal 0, and sample participates in updates once per epoch, the second term is the sum over E epochs. Apply the above process recursively to complete the proof and, obtain the approximator for sample
E
Me,((w) Ve(We,b(u) u), where M Me,b(u) = 7e,b(()) H Hg.B----eMW)+
(36)
P.B
18 (Ba,(u)
We define H F. 1-0.B-1--,,,01111- (I 7E H...HHHBBB- 1I........(II,,,.. H He.b())+)) which means that the multiplication should begin with recent update and continue backward through previous updates.
$ Note that we assume sample u participates the gradient calculation exactly once per epoch. Therefore, Equation (36), the number of summations É represents that sample has participated in E gradient calculations. In general, due to the randomness of sampling, sample u may be sampled multiple times or not at all within single epoch. Nevertheless, understanding and draw relevant conclusions, all results in this work based the simplified assumption.
can derive the results for these situations in the same manner. To facilitate
22

---

Published as a conference paper at ICLR 2025
C.2 DETAILED PROOF OF THEOREM 1
Now, we demonstrate that in the case of continuous arrival of deletion requests, our algorithm is capable of streaming removing samples. Intuitively, this property can mainly explained by Taylor's linear expansion. For ease of exposition, we simplify our proof to a scenario with only two samples, #1 and Ug. That is, our goal is to prove that when #1 initiates a deletion request and the algorithm is executed, the arrival of deletion request from U2 after 41 (Streaming Deletion), is fully equivalent to the simultaneous execution of deletion requests from both in and U2 (Batch Deletion).
Without loss of generality, we assume that b(u1) b(u2). Based Equation (11), the approximators uu uu for and U2 are denoted as ag and ag respectively, follows:
ag. E
Ma.((r)) Ve(We,M(m)) where Mc,((r)))
(Be,bar))
H E, -e.
(37)
E
No.)(
02 a
Ma,((u))
Vi(We,M(ng3 U2), where Ma,
H H1.
E
B ((a))
==0
When we simultaneously delete and Uz the difference is,
ne. Σ
(Vl(w -V V((We,bizz)
Web++ We.b+1
W We.
|Be
iEB
(38)
Consider the Taylor expansion during the E-th epoch, have,
12- 21 W
E WE (I
T
H (W
-2--1 WF,...
(39)
[BE
When U1 and un are removed respectively, we have the following approximation:
E,b(us)+1
WE,b(ug)+1
(I
[Bg,)(us)
HE
- u WE,b(w))
E,b(u))
(E,b(us)
+
V((WEMMu)))z))
1 (F,,(
Approximate impact of vz e-th epach
NE,b(u) H HE,b(u)))
-1--1 W (,,())+1
WE,b(u))+ (I
WE,b(u))
[BE
E.b(ur)
(1,b(u))
ME V((WEM))))))
+ B [8g
V((WE,M(u))zp) U2) +
B Bg
Approximate impact of ug e-th epoch
Approximate impact of e-th epoch
(40)
Therefore, in the E-th epoch, we have the following affine stochastic recursion.
W W
WEBB
II
I
7E
Hg,1)
(WED
WE,D)+
BE
b(a))+1
b(ux)+1
[[
WEbb
HF,
(Ebb(u))
V VE(WF.M()))
II
TE
H
TE,b(u)))
V (T(WWFMMug))2)
B
BE,b(ug)
[Bg
(B
b=B-1
b=B-1
(41)
Apply it recursively to complete the proof, and we can simultaneously compute the impact of u1 and U2 on training for all epochs.
E M Mc)(u)) Vl(We,b(u)) u1) +
E
W
WE,B
Σ M. Me.((ug)
Ve( Vl(We,b(uz) u2) +.
==0
e=0
(42)
According to Eqs. (37) and (42), we have completed the proof of ag.B
-2-
ag.B + +aE.
23

---

Published as a conference paper at ICLR 2025
C.3 DETAILED PROOF OF LEMMA 2
Proof of Lemma 2. Now we begin the proof that the remainder term o(w We.b) in the e-th epoch, b-th round is bounded. Specifically, recalling Equation (4), we have,
7ec Σ
(Ve(W ve(We,tizi).
e.b-
We.b+1
c,6
We.
BB,b iEB.,
W e,
We,(u))1 ~ W -We,b(u)
e,b(u)
Ne,b(u)
Σ
(Ve( ((bl))i)) V(((e.(uu)zz)) + Te,b(u)) VE(We,Muu) u).
(Beb(uu)
[ [Beb(
iEBo, Mfu
(43)
For all e, and 2 E Be, suppose that exists G such that G max V((We,bi>)] <00.
w We.bll S W We.b-ill 2
(44)
Consider a simple geometrically step size decay strategy Ne, 9 where 0 q is the decay rate, and let be the initial stepsize. Recalling that t eB b, then get
w c.b
We.t
& l| e.b- We.b w 2n
(45)
Note that the initial retraining model and learning model are identical. Therefore, based on the above recursion, we can obtain the geometric progression follows,
| - We,bll S 2n 1-1 + +2nGg +... + 2nGr
=nn
(46)
R=0
2n 8²
9-1
Therefore, we have completed the proof of Lemma 2.
C.4 DETAILED PROOF OF THEOREM 4
Proof of Theorem 4. Let us recall the approximator of Equation (11) in Section 3, we have,
E
Ve( Ve(We,b(w) u), where Mg, = Ne.b(u)
16
Me
Hg.B-1-eeM04
(47)
(Be)(u))
0=0
For the E-th epoch' B-th update, we have the following Taylor approximation,
E.B WEB
ag. =[I 11. 1E..B E.B-1 WE,B-1)
(48)
TE,B-10
-WE.B-- a
For convenience, we define Aw E,B we begin to analyze the enror generated by each update,
E.B Wg,., and H I- 1E - H Here, W
w E E
A + 1 BBB E.
(49)
'Li et al. (2021) demonstrated that SGD with exponential stepsizes achieves (almost) optimal convergence for smooth non-convex functions, thus affecting the convergence of learning process our paper.
24

---

Published as a conference paper at ICLR 2025
Furthermore, observe that during the E-th epoch, Equation (49) can be obtained from affine stochastic recursion as follows,
B-1
Aw E,B ag.Bl I |I
II
H H AW 12
ag-1,
E,
b=0
170 B- b(u)
B-1
II
H (VelWEnnojiu) V((WEMMwji)) |I
18 BBDb(u))
b(mb
Approximation tern C2 during the E-th epoch
B-1
71 T- 1
x Aw
E.B E.B-1 + H AW +
B
II b=0
H g. A w
E.0
Approximation error term C1 during epoch
(50)
Through the above process, obtain the result of the E-the epoch approximation. Now let's bound the last two terms, i.e., the approximation error term C1 and C2 during the E-tth epoch.
Recalling Lemma 2, we have that for all cB b.
Aw |! We,bll s 21G d²
(51)
Recalling Lemma 3, we have that for all e, and is the spectral radius of I Ne, H.H
H. He II ne, He, Aw & Al S p. 20 1 1 d¹
(52)
q
Therefore, we can bound the approximation error terms C₁ and C2 during the E-th epoch as follows:
(1) we first bound the first approximation error term C1 during the E-th epoch. For clarity, We define T' as the total number of steps of SGD updates performed when obtaining a, where T = EB+ +
B-1
T- Aww
= E.B-1
T-
H M...-IAWELL E,B E, +..+t9 T-B II
H Hg g.0
b=0
-1--1
T-2 (TT-2)
p 27 q- T-B B (TT
2n
+ 2n
B (53)
1-9
1 1
1-q
G
T-B
Σ
p
T-I-k
22)).
1 T=T-1
(2) we then bound the second approximation error term C2 during the E-th epoch. Suppose the stochastic gradient norm [VVe(,e,b u)]l is bounded by G, and we thus have the following upper bound.
174 T- B+b(u)
B-1
2Gn T- B+b(w) ( B-b(u)-1 B
HE.((V((EBtoo)) V((WEM)))))) b=b(+)1
II
BE,b(W)
(54)
Similarly, for each epoch, we have the aforementioned approximation error bound. Moreover, is noted that when = 0, the initial models for the retraining process and the learning process same.
25

---

Published as a conference paper at ICLR 2025
Therefore, have the following overall approximate error across all epochs:
E B-1
[ E.B
w WEBBll
Sn
"' + q--2 H
q T
&
k= b=0
179 T B+b(u)
TBBb((u)
B-1
II b=b(w)+1
HE (( V +
II (V Ve(Wo,M(w;
BB,M(u)
b=0==b())+1
q (2(
227 9 T-2 2 q
(
p ... + 2r 90 -2x(0)
< 2ny²
1-9 p=-
1-q
1 1-9
2g
2G
T- (-B+b(w) p B-b(u)-1 + +
Mu)
p (-b())-1
q
B
B
2n T-1
2n/
T- 1a- -2bk +
T- ----B--bll- b(u))( (1
1 9
B
k=
e=0
(55)
Suppose q < p. Through the polynomial multiplies geometric progression, we obtain,
W E.B
E,B
2r
T-1
Σ
T-1
(
D
(23
B
T b()) (
E Σ 2yeB
2
k=0
6=
(56)
2n G 1-q q p-q
p" -q"
p"
2T p x²
2mG p" 9T
BB| B q p 1
B b(a) B-b(u)
M(u)
which yields an upper bound on the approximation error. For ease of comparison, we subsequently simplify the aforementioned result, as follows:
2r2 p" (0"-9" 9T
p 2T
2nA
PT
I E.B - WEBBll S 1-9
d2
+
B
pB
q
0 B-1
(57)
S 2n - )
179
(p 4) q²)
|B 9)
At this point, we have completed the proof of Theorem 4 as follows.
|| E,B w W < O(2)Gp") If Theorem 4 further satisfies Assumption 1, and we choose S 2/(M + A) to ensure gradient descent convergence well as p 1, thus obtain tight upper bound of O(p") for each sample.
(58)
C.5 ADDITIONAL DEFINITIONS OF ASSUMPTION 1
We provide the following standard definitions of X-strong convexity, L-Lippchitzzesss, M M-Somotthness. Definition (A-Strong convexity). The loss function l(w; 2) X-strongly convex with respect to w, Le., there exists a constant X > O such that for any z E Z and W1, W2 E Rdd, it holds that
W2) + A || ww1-
(w1i.) 2 8 (W2)z) + (V (w2; z).
(59)
2
or equivalently,
|| Z for all E Rd.
Definition (L-Lipschitzness), The loss function E(w; is L-Lipschitz with respect to w, Lee, there exists constant L > 0 such that for any Z and W1, W2 E Rdd, it holds that
/ (w1;;)
(W2; 2)1 & ||w] - -wll-
(60)
or equivalently, [V((w; S L for all w E Rd.
Definition 5 (Mf-Smoothness). The loss function E(w; 2) is M-smooth with respect to w, i.e., there exists a constant M > 0 such that for any z E Z and W1, W2 E R.d. holds that [ (W1;2) - Vl (wrtz)) & M [[w] - -wlll.
(61)
or equivalently, [w; < M for all w E Rd.
26

---

Published as a conference paper at ICLR 2025
C.6 DETAILED PROOF OF THEOREM 6
Before we commence with our proof, we present some necessary lemmata.
Lemma 9 (Shalev-Shwartz et al. (2009)). Let S {z:);-1 where S D Let w" denote minimizer of the population risk in Equation (1) and i denote a minimizer of the empirical risk without the knowledge of U in Equation (2) which aims to minimize Psyu(w) where [U] = m. Let Assumption 1 hold. we have,
4L2
B F (w- -
(ww))
(62)
A(n m)
Proof of Lemma 9. A comprehensive proof of Lemma 9 is available in Shalev-Shwartz et al. (2009).
For brevity and to save space, we present our generalization guarantee only for GD. Nevertheless, the results for SGD can be analogously obtained by similar process.
Lemma 10. For any z Z, the loss function E(w; 2) is X-strongly convex, L-Lipschitz and M- smooth. Let w-U argminw Fsyu(w) without the knowledge of U in problem Equation (2). For all e, and vector TRd, the spectral radius of Me,.He, b, is defined as p which is largest absolute eigenvalue of these matrices. We have that after T steps of GD with initial stepsize X
2
2M where p = max {11 - - - M <1.
||
1 S p
(63)
Proof of Lemma 10, Recalling that, according to the strong convexity and smoothness, X, M > we have AI N V2((w: 2) 3 MI. Therefore, we have
- 3
7/T
V'l(w"";20 ;2)) (1 MI).
(64)
BT
iEBT
2 Let 17 X+M Therefore, 1/ S
X+M which implies that for any T E (o):
2
- 7 < 1, 1 < 1.
(65)
It is seen from the fundamental theorem of calculus that
FFsU (w7") = EESW - FFSO (w (1'
V2 Esw (w, U) dr (wT" w U1)
(66)
where w, == WT T (w WT Here, {w, Jugrs1 forms a line segment between WT and w U. Therefore, According the GD update rule and based on Lemma 3, have.
[ T+1 - w- = I - Tr F' (w=²) dr) (w - w -
||I nr 22 Esw (w, "| /T"" U - w w-yll s <||WT - w w- (67)
< sup 05151
Apply it recursively,
|| - w " - p" V - w w-'ll, where p = max {|1 - n/// - 1- < 1.
(68)
By the assumption that A-strongly convex and L-Lipschitzness, which implies that
X l| - w u- <F(w U) - FFw-(1 (w-
2
(69)
2L2
F(w - F (w U) -
Therefore, have completed the proof as follows,
|| w -I < 5r 2L
where p max (11 n7/1 11 mM <1.
(70)
27

---

Published as a conference paper at ICLR 2025
Building upon the proofs presented in Lemma 9 and Lemma 10, we now prepared to establish the generalization results stated in Theorem 6.
Proof of Theorem 6. Let w- be the empirical risk minimizer of the objective function Fsyu (w).
where [U] = Let T be the total number of update steps. For any 2 the loss function ((w;)) is X-strongly convex, M-smoothness and L-Lipschitz. For a minimizer w of the population risk in Equation (1) and W E,B = WE,B B + n, we have that
E F(WE.B F Fww)] T. F( B.E F(w 4)
+ E
( U) F (ww)].
(71)
Based on Lemma 9, we get
4L.
E F (w U) F (w")) 1 A(n m)
(72)
Then we note that the function F(w) satisfies I.-L.ipschitz, therefore we can obtain,
41. X(n
E F (WE.B) - F (w")) I [[L||WE.B w
w-
(73)
m)
For the first term of Equation (73), we have
E
w E
E.B
U
+
E,B
U w
S E
1 W E,B
E.B
+
E
W
E.
U
w
U
(74)
C2
C₁
Therefore, we now bound the first term C3 and the second term C4 of Equation (74) as follows:
(1) C4: Based on Lemma 10 and w
E,B = WT we have that for 17 S
2
X+M
2L
E [[|lEl
U E,B w 11] S p" w-
where p = max {|1 n/1,
nMB <1
(75)
A
(2) C3: Based on Theorem 4, we obtain,
E Wi U E.
w WEBBl E[
|l!
E[[WEE + -U 2r
E.B W E.
U +
S
I U + vdc.
1
p² -- p" p"'qq""
GnnG
p² 9t
(76)
where
A E
B 1 0 q
p
1-q
p-q
p p-
B
And since the loss function E(w; satisfies M-smoothness and X-strongly convex, we thus have that 0 p Plugging the above bound Equation (75) and Equation (76) into Equation (74), have
4L2
222 A
+ /dv/2m (1.25/5)
F(WEl)) - F (ww))
+ +p"
+1) L A. (77)
X(n m)
e
Therefore, we have completed the proof.
Tightness Analysis of Theorem 6. Furthermore, the following settings, where i close to q, might render the bound on the approximation error vacuous and also lead to high approximation error. We note that the first and third terms of | || can be equivalently written O(-"=q" -==="""
E.Bll
p-o
TT E (2)s + Ee
p) B)). These terms increase / approaches q, however are always upper bounded by - TT-TTTB.7 .T). In our analysis. T = EB + B is a fixed constant, so this bound remains meaningful, although may not be tight in some cases. Such as when T oc, in this 2nG
scenario p is close 1, the bound therefore is equivalent to ( تn 2nG I-q² + =- ). Fortunately,
SGD typically does not need find a local minima infinite time, hence p is always less than
D SUPPLEMENTARY EXPERIMENTS
D.1 HARDWARE, SOFTWARE AND SOURCE CODE
The experiments were conducted on the NVIDIA GeForce RTX 4090. The code were implemented in PyTorch 2.0.0 and leverage the CUDA Toolkit version 11.8. Our comprehensive tests were conducted on AMD EPYC 7763 CPU 1 1.50GHz with 64 cores under Ubuntu20.04.8 LTS. Source Code: Our code is available at O Hessian Free Certified Unlearning
28

---

Published as a conference paper at ICLR 2025
D.2 ADDITIONAL VERIFICATION EXPERIMENTS
The verification experiments in this section consist of two parts: (1) We first investigate the reasons behind the randomness of previous works under the non-convex setting. We select forgetting samples under different random seeds, and show that previous works exhibit dependence for forgetting samples. This implies that the forgetting effect in prior studies benefits certain samples while negatively impacting others. (2) Second, we perform experiments on a larger-scale dataset and model with more metrics, Prior studies were unable to achieve this due to the costly Hessian computation.
Sensitivity to the forgetting samples. We conduct experiments on simple CNN and the hyperpa- rameter setup is consistent with the verification experiments I in the main paper. As shown Figure 4, we provide intuitive insights into the reasons for the decline of prior works in non-convex settings. Specifically, we investigated the I,² norm of the approximate parameter change ||a-U|| || and the norm of the exact parameter change across different selections of the forgetting sample. We observed that the performance of NS and I/ depends on the selection of the forgetting data points, i... NS and IJ can approximate actual changes well for some data while generating large approximation errors for others under the non-convex setting, as illustrated in Figure 4. The dependency of forgetting data points results in the decrease in distance and correlation coefficient metries observed in Figure/ 1 (b). The observed results for NS and IJ are consistent with previous studies on influence functions (Basu et al. (2021; 2020)), where these methods display random behavior under the non-convex setting, resulting in decrease in correlation with retraining, In contrast, our approach can effectively approximate the actual norm of parameter changes, regardless of the selection of the forgetting sample.
Additional experiments. We further evaluate using larger-scale model ResNet-18 (He et al. (2016)) which features 1M parameters with three datasets: CIFAR-10 (Alex (2009)) for image classification, CelebA (Liu et al. (2015)) for gender prediction, and LFWPeople (Huang et al. (2007)) for face recognition across 29 different individuals. Since previous second-order works (NS Sekhari al. (2021)) and (IJ Suriyakumar et al. (2022)) are difficult to compute (Hessian) in this scenario, we instead use the following fast baselines, as described and similarly set up in Tarun et al. (2023):
FineTune: In the case of finetuning, the learned model is finetuned the remaining dataset.
NegGrad: In the case of gradient ascent, the learned model is finetuned using the negative of update direction on the forgetting dataset.
For Tune and NegGrad, we adjust the hyperparameters and execute the algo- rithm until the accuracy on the forgetting dataset approaches that of the retrained model. Here are our detailed hyperparameter settings: (1) We conducted evaluation on ResNet-19 18 trained on CIFAR- 10 with 50,000 samples. The learming stage is conducted for 40 epochs with step size of 0.001 and batch size of 256. For Fine'Tune, 10 epochs of training are performed with step size of 0.001 and batch size of 256. For NegGrad, we run gradient ascent for 1 epoch with step size of 5 x 10-5 and batch size of 2. (2) We conducted evaluation on ResNet-18 trained on LFW with 984 samples, for the classification of 29 facial categories. The learning stage is conducted for 50 epochs with step size of 0.004 and batch size of 40. For FineT epochs of training are performed with step size of 0.004 and batch
Configurations:
Ours Charget aad
16
Oura Chorpet 39%
Norm of Approximate
Paremeter Change uage
15.0
Ours Clerpet 10%)
Norm Approximate
Change
14
Ours Charpet 5p%1
12.5
12
Herget 10%0
ffreget 10%0
10.0
7.5
5.0
2.5
0.0
0.2 0.3 0.5 0.6 0.8 1.0 Norm Exact Paremeter Change
0.2 0.3 0.4 0.6 0.7 0.8 0,9 1.0
Norm of Exact Paremeter Change
(a) Low Deletion Rates
(b) High Deletion Rates
Figure 4: Verification experiments II. Evaluation shows a comparison between the norm of approximate parameter change |a -=|| and norm of exact parameter change ||W WE & across different random seeds. Intuitively, the NS and IJ methods are contingent on the selection of forgetting data. In contrast, our approach consistently approximates the actual values effectively.
29

---

Published as a conference paper at ICLR 2025
size of 40. For NegGrad, we gradient ascent for I epoch with step size of 4e and batch size of 1. (3) We conducted evaluation on ResNet- 18 trained on CelebA with 10,000 samples. The learning stage is conducted for 5 epochs with step size of 0,01 and batch size of 64. For FineTune, 2 epochs of training are performed with step size of 0.01 and batch size of 64. For NegGrad, we run gradient ascent for epoch with step size of 0.0005 and batch size of 1. We threshold the gradients within 10 for the above experiments. Finally, we uniformly unlearned 50 data points for each dataset. We denote the test data as D., the remaining data as D,, and the forgetting data as Dy.
The following Table 3-5 are our evaluation results: we employ five widely-used metrics to evaluate the performance of unlearning methods: Acc
Acc_D, Dr (accuracy on D2). error Dr (error on D.), error D, (error on D,), error D (error on D)), Distance (L² norm between unlearned and retrained model).
We still maintain model indistinguishabiityy from the retrained model on more complex tasks and larger models, where the distance is only 0.06 on CIFAR 10 and 0.29 on CelebA. The results also show that the unlearned model of proposed method performs similarly to the retrained model in terms of the accuracy metric. Moreover, compared to these baselines, our method achieves forgetting at only the millisecond level, demonstrating the potential our method on larger-scale models. Additionally, we noticed that when training is unstable, our method would lead to larger performance degradation, such as on the LFW dataset. Although our method has similar accuracy on the forgetting dataset, it sufferss performance loss on the remaining dataset. This implies that our method is sensitive to the training process and hyperparameters in non-convex scenarios. We summarize the limitations in Appendix B.1, and provide possible schemes to address these problems.
Performances of our scheme:
Model indistinguishability: For FineTTne, we can observe that even though the accuracy results are similar the retrained model, the distance metric is very large (e.g. 2.21 CIFAR- 10 and 2.36 on CelebA). For NegGrad, we observe that the accuracy on forgetting dataset Dy and remaining dataset D, would rapidly decrease simultaneously, but even this case, the distances are is still lower than that of Tune for all three datasets. This demonstrates that small difference in accuracy does not indicate the model indistinguishability Therefore, we use the L norm and correlation metric as the primary measure of forgetting completeness, which are commonly employed in studies related to influence function (Basu al. (2021; 2020)). These studies serve as inspiration for prior certified unlearning papers (Sekhari et al. (2021); Suriyakumar et al. (2022); Liu et al. (2023)) that compare. Measuring forgetting through La norm is also used unlearning research, e.g., Wu et al. (2020); Izzo et al. (2021), ), but necessitates retraining model, which is impractical for real-world applications.
Table 3: Verification experiments III. Unlearning results on Resnet- trained on CIFAR- 10 dataset.
Method
Acc D: (%)
Err D, (%)
Err D, (%)
Err Dy (%)
Distance
Runtime (Sec)
Tine
79.34
20.66
15.92
22.00
2.21
106.76
NegGrad
40.61
59.39
59.15
70.00
0.11
0.56
Retrain
79.63
20.37
16.19
24.00
468.65
Ours
79.62
20.38
16.15
22.00
0.06
0.0006
Table 4: Verification experiments IV. Unlearning results on Resnet- 18 trained on LFW dataset.
Method
Acc. D, (%)
Err D2 (%)
Err D, (%)
Err Brr_D, (%)
Distance
Runtime (Sec)
FineTTne
76.02
23.98
8.99
4.00
0.52
15.60
NegGrad
63.01
36.99
15.63
20.00
0.48
0.46
Retrain
80.89
19.11
4.07
26.00
77.43
Ours
71.92
28.08
14.91
22.00
0.33
0.001
Table 5: Verification experiments V. Unlearning results on Resnet- 18 trained on CelebA dataset.
Method
Acc D, (%)
Err Drr_D, (%)
Err Err_D, (%)
Err_D, y (%)
Distance
Runtime (Sec)
FineTune
95.78
4.22
1.07
4.00
2.36
35,09
NegGrad
37.95
62.05
58.12
60.0
1.13
0.96
Retrain
95.72
4.28
1.20
4.00
87.72
Ours
95.57
4.43
1.12
2.00
0.29
0.0006
30

---

Published as a conference paper at ICLR 2025
D.3 ADDITIONAL APPLICATION EXPERIMENTS
Furthermore, we evaluate the performance on different datasets and models in real-world applications. Our evaluations are conducted from two perspectives: runtime and utility. Specifically, run-time focuses on the time spent precomputing unlearning statistics and the speedup of the unlearning algorithm compared to the retraining algorithm. Moreover, we evaluate the utility by the test accuracy of the unlearned model to ensure that generalization performance not compromised. Finally, we record the area under the curve (AUC) for the MIA-L attack.
We assess the performance on various datasets and models, as presented in Table 6. The values in parentheses indicate the difference in test accuracy compared to the retrained model. (1) We train a LR and simple CNN on MNIST with 1,000 training data 20% data points to be forgotten, which have setups identical to the aforementioned verification experiments I. We further evaluate on FMNIST with 4,000 training data and 20% data points to be forgotten using CNN and LeNet with a total of 61,706 parameters. The training is conducted for 30 epochs with stepsize of 0.5 and a batch size of 256. (2) Moreover, we assessed our method on Resnet-18 (He et al. (2016)) trained on the CIFARIO dataset for image classification with 50,000 data points, CelebA dataset for gender prediction with 10,000 data points, and LFWPeople dataset for face recognition with 984 data points. we uniformly add noise with a standard deviation of 0.01. The configurations align with those detailed in Table 3-5. In these circumstances, we have not evaluated NS and IJ due to out-of-memory.
Configurations:
Application experiment results show that our proposed method is computationally efficient and performs well in realistic environments, outperforming benchmarks of certified unlearning regarding all metrics by a significant margin, as demonstrated in Table 6. achieves minimal computational and storage overhead while maintaining high performance in both convex and non-convex settings. We further investigate data removal with large-scale datasets using ResNet-18, 18, as shown in Table Our proposed Hessian-free method demonstrates significant potential for over-parameterized models, as previous second-orde certified unlearning works are unable to compute the full Hessian matrix in such cases. Notably, for unlearning runtime, by precomputing statistical data before unlearning requests arrive, we only need to execute simple vector additions, achieving millisecond-lever efficiency (0.6 ms) with minimal performance degradation in test accuracy. Finally, although our method has lower computation and storage complexity compared to previous works, it still requires O precomputation and ((nd) storage which is expensive when facing both larger-scale datasets. We summarize the limitations in Appendix B.1, and provide possible schemes to address these problems.
Table 6: Application experiments II. We conduct two types of comparisons: (1) on small-scale models and datasets with previous second-order algorithms, where we compute the total computa- tional/storage cost for all samples; and (2) on large-scale models and datasets with fast unlearning algorithms, where we compute the computational/coss overhead of per- sample forgetting.
Mathod
Dataset
Madel
Runtime (Sec)
Unlearning Computaton
Speelup
PreComputaton
Runtime (Sec)
Storage (GB)
MIX-
Distance
Test Accuracy (%)
Unlearned model
LR
3,09x10"
1.34x
2.55% 10"
0.23
0.51
0.18
86.25 (-1.50)
MNIST
NS
CNN
5.81x10
0.12x
2
1.78
0.51
1.78
83.50 (-10.25)
FMNIST
CNN
2.31x104
0.54x
116x10
1.78
0.54
2.41
57.69 (:22.25)
LeNet
8.53x104
0.15x
4.27%x10*
14.18
0.54
1.10
62.00 62.00 (-18.50)
MNIST
LR
0.23x10
29.64x
2.5
0.18
(-1.50)
13
CNN
1.9
3.63x
1
1.78
0.51
3.12
82.75 (-11.00)
FMNIST
CNN
2.95x10'
424x
1.16x10"
1.78
0.51
0.94
69 (-4.25)
LeNet
3.24x10
402x
4.27x10²
14.18
0.54
0.57
76.75 (-3.75)
MNIST
LR
0.0073
93,376
1
0.03
0.51
0.15
87.50 (-0.25)
CNN
0.0268
25,821
5.34x 10a
0.08
0.51
0.68
91.50 (-2.25)
FMNIST
CNN
0.127
98,468x
3066x10'
0.32
0.51
0.74
77.85 (-2.09)
LeNet
0.163
79,828x
4.4
0.48
0.53
0.53
78.63 (-1.87)
Method
Datasel
Model
Unlearning Computaion Runtime (Sec)
Speedup
PreComputaton Runtime (Sec)
Storage (GB)
MIA.L
AUC
Distance
Accuracy (%) Unlearned model
CHARID
4.39
2.21
79.34 (:029)
FineTune
LFW
Resnet 18
15.60
4.96
0.53
0.52
76.02 (-4.87)
CelebA
2.50
2.36
95.78
CIFARIO
0.56
$36.88
0.51
0.11
40.61 (:39.03)
NegGrad
LFW
18
168.33
0.46
(-17.88)
ColobA
0.96
91.3% x
0.50
1.13
37.95 (-57.77)
CHARRD
781,083x
0.06
79.62 (-001)
HE
LFW
Resnet1s 18
0.001
77,430
84.99
0.043
0.56
0.31
71.92 (-8.77)
ColcbA
0.0006
146,200
0.042
0.34
0.29
95.57 (-0.15)
31

---

Published as a conference paper at ICLR 2025
D.4 ADDITIONAL ADVERSARY EXPERIMENTS
Membership Inference Attack against Learning (MIA-L) aims to determine whether a specific example is part of the training set of the learned model. Carlini et al. (2022) introduced the Likelihood Ratio Attack (LiRA), which leverages the model's per-example difficulty scores and employs a well-calibrated Gaussian likelihood estimate to gauge the probability of a sample being part of training data. Finally, the adversary queries the confidence of the target model on a specific example and outputs a parametric likelihood-ratio test. Membership Inference Attack against Unearning (MIA-U) seeks to predict whether a target sample is part of the learned model's 's training set but not in the corresponding unlearned (retrained) model's training set. Chen et al. (2021) proposed MIA-U to attack Scratch methods, specifically the Retrain and SISA (Bourtoule et al. (2021)) algorithms, where the adversary jointly utilizes the posteriors of the two models as input to the attack model, either by concatenating them or by computing difference. Specifically, it includes five methods to construct features for the attack model: Direct difference (DirectDiff), Sorted difference (SortedDiff), Direct concatenate (DirectConceee Sorted concatenate (SortedConcat), and Euclidean distance (EucDist).
Configuration: (1) We investigate the Area Under the Curve (AUC) of MIA-U at different deletion rates. (2) We report the Receiver Operating Characteristic (ROC) curve of MIA-U in large-scale experiments as well. (3) Finally, as a complement to the results of the DirectDiff method reported in the main text, present the ROC of the remaining four feature construction methods in MIA-U. We maintain the other hyperparameters consistent with previous experiments.
Different deletion rates. As illustrated in Figure 5, clear correlation exists between the deletion rate and the effectiveness of MIA-U attacks. Specifically, at a low deletion rate of 1%, the AUC of MIA-U attacks reaches 91% for our proposed method and 89% for the retrain method in the LR model, indicating that unlearning algorithms may increase the risk of privacy breaches. When the deletion rate exceeds 5%, the performance of MIA-U attacks approaches random guessing (AUC= 50%), suggesting that removing a larger amount of data between successive model releases makes it increasingly difficult for MIA-U attacks to accurately infer the deleted individual information.
Under the Curve
Retrain from Scratch Proposed Methed
90%
Retrain Scretch
Proposed Methed
Area the
90%
Infinitesinal jacknife Step
80%
80%
70%
70%
60%
60%
50%
50%
40%
15
5%
10%
15%
20%
25%
30%
1%
5%
10%
15%
20%
25%
30%
Deletion Rates
Deletion Rates
Figure 5: Membership Inference Attack II. The AUC values of MIA-U at different deletion rates. The feature construction method employed in MIA-U is DirectDiff, with error bars representing 95% confidence intervals. The target model in the first plot is LR, while the second plot corresponds to CNN. The findings show that lower deletion rates lead to privacy leakage, whereas higher deletion rates diminish MIA-U's attack performance, bringing it closer to random guessing.
Target Model: ResNet18
Target Model: ResNet18
Target Model: ResNet18
1.6
10
1.0
True Positive Rate
True Positive Rate
0.0
0.0
0.0
0.c
0.6
True Positive
0.6
0.4
0.4
aumee (AAL AR) LABC
Nutrac 0, LRIC
Netren UMA 03511 0.6
0,60
0.2
0.8 1.0
000
0.2
0.4
3.0
0.80
0.2
0.4
False Positive Rate
False Positive Rate
False Positive Rate
Figure 6: Membership Inference Attack III. ROC curves for MIA-U on ResNet18. The datasets used in the figure, from left to right, are CIFAR-10, 10, LFW, and CelebA. For large-scale setups. our method (red line) performs consistently with the retraining algorithm (light red line) under MIA-U.
32

---

Published as a conference paper at ICLR 2025
Feature Construction: SertedDit
Feature Constructor: CirectCnncet
Feature Carstructee:: SarfedCencet
Featore Constraction:
Trus Positive Rate
True Positiive Rate
True Positivv
True Positive
S4
02
2.5
10
CA 02
60
10
E6
10
10
02
10
testtre Construction Nectedinn
Peature Construction Drectieenna
reatere Constraction: Sorteiienncat
resture Construction: meceist
True Positive Rate
Trum Prosiiive Rate
Pesitiue Rete
000
02
2.5
1.0
3.5 3.
21
10
'83
23 2.6. 00 3.0
False Positive Rate
Falee Positive
False Positive Rate
False Positive Rate
(a) SortedDif
(b) DircctConcat
(c) SortedConcat
(d) EucDist
Figure 7: Membership Inference Attack IV. ROC curve for different feature construction methods. The target model in the first row is overfitted CNN, whereas the second row is -ell-gener LR.
Different feature construction methods. As shown in Figure 7, we experiment with a well- generalized LR model and overfitted CNN model, and the experimental results consis- tent with the conclusion of Chen et al. (2021): sorting the posteriors improves attack perfor- mance; concatenation-basel methods achieve higher attack performance difference-basee methods perform better on the well-generalized LR. In addition, we observe that perturbing the unlearning model can effectively defend the EucDist method. However, for other feature construction methods, adding noise to perturb the model after certain level does not reduce the AUC of the attack model. This reveals a fundamental dilemma of most certified data removal processes developed so far: Although the goal is to achieve performance similar to a gold-standard retrained algorithm, the retrained model itself remains vulnerable to MIA-U, exposing the failure modes of certified unlearning. Nonetheless, as shown in Figure 5, removing at least 5% of the data when releasing the unlearned model can mitigate privacy leakage. However, we are not aware of any recent certified data removal mechanisms that can satisfy the deletion capacity exceeding 5% of the training set. Fortunately, one of the defense mechanisms proposed by Chen et al. (2021), which employs Differentially Private Stochastic Gradient Descent (DP-SGD), can effectively mitigate MIA-U but requires careful trade-off amongst privacy, unlearning efficiency, and model utility.
the overfitted CNN; and
E SENSITIVITY ANALYSIS AND ABLATION STUDIES
In this section, we investigate the effects of different step sizes, epochs, stepsize decay rates, and gradient clipping on the proposed approach. We conducted simulations in both convex and nonconvex scenarios, using LR for the convex case and 2-layer CNN for the non-convex case, respectively.
Takeaway. Let's first provide a brief summary of the main results of ablation studies.
(1) Impact of Step Sizes. Firstly, a smaller step size enables our model be closer to the retrained model. However, when the step size exceeds a certain threshold, the bound will become meaningless and result in significant approximation errors. (2) Impact of Epochs. Secondly, when the step size is sufficiently small, the approximation error is insensitive and exhibits slow growth with respect to the number of epochs, i.e. excessive iterations in this scenario do not lead to significant errors. (3) Impact of Stepsize Decay Rates. Thirdly, our results indicate that as the decay rate q decreases, the approximation error diminishes. Specifically, The stepsize decay strategy introduces a bound on approximation error, preventing a continuous increase in error the size of epochs grows. (4) Impact of Gradient Clipping. To prevent gradient explosion, we introduced gradient clipping. We show that gradient clipping, which scales the gradient based on its norm, has similar effect using a smaller step size. Although, in theory, clipping the gradient may introduce errors, our experiments indicate that this impact is negligible when the threshold is set large value.
33

---

Published as conference paper at ICLR 2025
E.1 IMPACT OF STEP SIZES
In this section, we investigated (i) the impact of step sizes and (ii) the impact of small stepsizes with more epochs. Additionally, we discussed the connection between learning generalization and our unlearning method.
Configurations: (i) We investigate the impact of step sizes (0.005, 0.01, 0.05, 0.1, 0.3) distance metrics in Table and Table 8. For LR, training was performed for 15 epochs with a stepsize of 0.05 and batch size of 32. For CNN, training batch size of 64. (ii) Furthermore, in Figure 9, to investigate the effect of epochs under small step sizes, LR was trained for 100 epochs and 200 epochs with a step size of 0.01 (initially 0.05 with 15 epochs). For CNN, training for 50 epochs and 500 epochs with step size of 0.025 (originally 0.05 with 20 epochs) was performed.
carried out for 20 epochs with step size of 0.05 and
Impact of step sizes. As shown in Table and Table 8, a smaller step size enables our model to be closer the retrained model. Specifically, as Theorem demonstrates that, in this process, the error arises from the scaled remainder term, i.c., the term of o we.b) is scaled by the subsequent Mc,b(u)- Therefore, the approximation eπror mainly consists of two components: (1) the step size Ne. and (2) the maximum eigenvalue Å of He.b- A smaller step size 7) contracts the eigenvalues of the matrix ne, He.b, thereby reducing the spectral radius of the matrix I 7), He,b. and ultimately reducing the approximation error.
when the step size is smaller than certain threshold. increasing the step size does not lead to significant errors. However, when the step size exceeds this threshold (making p not less than or close to 1), the errors will grow exponentially, as demonstrated in Table and Table 8 for step size 17 2 0.3. In this scenario, our method leads to a complete breakdown of the model, rendering it unusable. However, it is noteworthy that theoretical predictions (Wu et al. (2018)) and empirical validation (Gilmer al. (2022)) suggested that, across all datasets and models, successful training occurs only when optimization enters stable region of parameter space where X 77 I 2. Therefore, achieving good optimization results typically does not require a strategy of using aggressive stepsizes.
Furthermore,
The connection between learning and unlearning. There is connection between the sharpness of learning generalization studies and the unlearning method that we propose. Specifically, these studies aim explore the sharpness of the Hessian of loss function He,d; and the term 'sharpness' refers to the maximum eigenvalue of the Hessian, denoted as X in some studies, such as Gilmer et al. (2022). A flat loss space is widely recognized beneficial for gradient descent optimization, leading to improved convergence. Importantly, Gilmer et al. (2022) demonstrated the central role that λ plays in neural network optimization, emphasizing that maintaining a sufficiently small X during optimization is necessary condition for successful training (without causing divergence) at large step sizes, as shown in Figure Models that train successfully enter a region where λ₁ 7 S mid training (or fluctuate just above this bound). In our paper, we leverage the second-order information from the Hessian at each iteration during the training process to compute the approximators and achieve forgetting, As indicated in Theorem 4, small λ₁ of the Hessian is beneficial for reducing
Table 7: Impact of Step Sizes on Convex Setting. Stepsize 0.05 represents the hyperpa- rameter choice of experiments for LR in the main paper. It can be observed that as the step size decreases, the unlearned model closer to the retrained model. (Seed 42)
Table 8: Impact of step sizes on non-Convex setting. Stepsize 0.05 represents the hyperpa- rameter choice experiments for CNN the main paper. It can be observed that the step size decreases, the unlearned model is closer to the retrained model. (Seed 42)
Distance
Distance
Stepsize
Stepsize
1%
5%
20%
30%
1 1
5%
20%
30%
0.005
0.018
0.040
0.092
0.128
0.005
0.004
0.015
0.058
0.084
0.01
0.023
0.0518
0.127
0.178
0.01
0.017
0.069
0.257
0.372
0.05
0.027
0.064
0.149
0.210
0.05
0.167
0.380
0.584
0.825
0.1
0.028
0.066
0.154
0.217
0.1
0.437
0.795
1.722
2.72
0.3
5.581
17.48
28.45
40.64
0.3
122.2
393.4
1647
2455
34

---

Published as a conference paper at ICLR 2025
0.83
0.25
Unlearning Model: Approximationn Error
Learning Model: Test Accuracy
85-
75-
Stepsize
Figure 8: The connection between learning and unlearning. We conduct experiment on MNIST and keep the other hyperparameters fixed and adjust the learning rate from 0.001 to 0.31. Under fixed iteration budget, we have: (1) When the step size is small (less than the threshold 7 = 0.01),
the training is often insufficient, leading lower test accuracy. (2) Increasing the step size ensures sufficient training, but when the learning rate becomes too large, overfitting and instability lead to decrease test accuracy. We also observe the following phenomena the unlearning process: (1)
When the step size is below a threshold 7/2 0.25, the growth of approximation error is extremely slow. (2) However, once the step size exceeds this threshold, the error grows exponentially.
Euclidean Distance
O6-
8.584
0:10
Euclidean
0.329
0.05
02
0.00
E=15
E=1000 (n-0.005)
E=20
E=800
(0=0.05)
(1-0.95)
(n-0.005)
(a) Convex Setting
(b) Non-Convex Setting
Figure 9: Impact of Small Step Size with More Epochs. (a)(b) correspond to LRR and CNN with 20% of the data to be forgotten, respectively. The red bar represents the distance metric when using a larger step size; the blue bar represents the distance metric with a small step size during the larger epochs. It can be observed that even when training more epochs with smaller stepsize, the approximation error remains lower compared to training with larger stepsize. (Seed 42)
the approximation error. Therefore, effectively reducing X during optimization, so that the training enters flatter region, will only improve the generalization ability the learning stage model but also reduce the approximation error in the unlearning stage. As suggested in Gilmer et al. (2022), strategies like stepsize warm-up or initialization strategies for architectures can be employed to stabilize learning and potentially reduce unlearning errors by decreasing Y1 enabling training at larger step sizes.
Impact of small step size with more epochs. Finally, shown in Figure 9, with small step size (0.005) during model training, we observed a lower approximation error. Even with large epoch sizes, the approximation error remains lower compared to cases with large step size, such 0.05. Therefore, selecting an appropriately small step size ensures smaller approximation errors, as these errors typically converge smaller value as the number of epochs increases.
E.2 IMPACT OF EPOCHS
In this subsection, we began investigating the distance metric as the number of epochs increases.
Configurations: We investigated the distance by varying the epoch from 1 to 100. We conducted experiments with high deletion rate of 20% and a low deletion rate of 5%. The selection other hyperparameters remains consistent with the used previously.
35

---

Published as a conference paper at ICLR 2025
0.13
Forget 28% Data
Fagal 24 bata
Euclidean Distanoe
0.19
Euelidean Distance
0.14
0.4
0:12
03
02
Epoch
Epoch
(a) Convex Setting
(b) Non-Convex Setting
Figure 10: Impact of Epoch. (a) (b) illustrate that in the distance for LR and CNN by varying epoch from and 100. As shown Figure (a) (b), the error accumulates with the increase in epochs. However, with appropriate choice of step size, such growth is acceptable (Seed 42).
Impact of epochs. As shown in Figure 10, the distance exhibits convergent behavior, ultimately stabilizing at a constant value. This phenomenon consistent with our theoretical findings, as stated in Theorem 4, which demonstrates that the approximation error decreases with increasing number of epochs for convex models. The contractive mapping ensures a gradual reduction in the final error. In the case of non-convex models, the error tends to increase with the number of epochs, ultimately stabilizing. a phenomenon that can be explained by the degeneracy of the Hessian in over-parameterizeed models (Sagun al. (2018)), will discuss in further detail later.
E.3 IMPACT OF STEPSIZE DECAY
These experiments aim to study the impacts of stepsize decay. We consider two scenarios: one with stepsize decay (q 0.995) and the other without stepsize decay (q 1).
Impact of decay rates of stepsize: We can observe from Figure 11 that the Euclidean distance for the stepsize decay strategy generally smaller compared to that without the stepsize decay. This aligns with our earlier analysis of step size in Appendix E. i.e., smaller step size leads to smaller approximation error, and choosing an appropriate stepsize decay rate ensures a continuous reduction in step size, preventing the unbounded growth of the approximation error.
Additionally, in Figure 11 (b), It can be observed that the distance metric tends stabilize even without stepsize decay. This result can be explained by the conclusions in Sagun et al. (2018; 2016). Specifically, Sagun et (2018; 2016) analyzed the spectral distribution the Hessian eigenvalues during CNN training. It reveals that, initially, the Hessian eigenvalues are symmetrically distributed around As training progresses, they converge towards 0, indicating Hessian degeneracy. Toward the end of training, only small number of cigenvalues become negative, and a large portion of the Hessian eigenvalues approach when the training approaches convergence. Recall that our previous analysis of the stepsize in Appendix 1, where demonstrate that the approximation error is mainly determined by of I Ne. H. He and is determined by ne.6 and λ As the number of iterations increases, the eigenvalues of the Hessian He.p tends to O. This implies decrease in '₁ which leads to a slower increase in error. Therefore, in Figure 11 (b), the distance gradually stabilizes even without decay strategy due the decrease Aj during training, and it still increases due to the existence of some larger outlier eigenvalues.
E.4 IMPACT OF GRADIENT CLIPPING
Stochastic gradient algorithms are often unstable when applied to functions that lack Lipschitz continuity and/or bounded gradients. It is well-established that exploding gradients pose significant challenge deep learning applications (Hanin (2018)). Since our proposed method relies on backtracking historical gradients, the approach may fail completely when gradients tend toward infinity. To circumvent this issue, we incorporated gradient clipping into all the aforementioned experiments. Gradient clipping is widely adopted technique that ensures favorable performance in deep network training by restricting gradient norms from becoming excessively large (Mai & Johansson (2021); Chen et al. (2020); Zhang et al. (2020)). However, this operation indicates that
36

---

Published as a conference paper at ICLR 2025
1.2
Decay
-lippaiee Dosay Rate = 0.566
0.21
Euclidean Distance
0.8
0.18
Stepsize Decay Rata
Eucildean
Stepsiza Dacay Rate - 0.005
0.4
0.18
Epoch
Epoch
(a) Convex Setting
(b) Non-Convex Setting
Figure 11: Impacts of the stepsize decay rate on the Euclidean distances for (a) the LR and (b) the CNN with 20% data to be forgotten during 25 epochs. The red line represents learning with decay rate of 0.995, while the blue line represents without decay. can be observed that stepsize decay effectively reduces the approximation error of the unlearned model. (Seed 42)
07
CNN
Euclidean Distance
9.8
8.4
0.3
0.1
Threshold
Figure 12: Impacts of the gradient clipping the distance metric for the LR (orange) and the CNN (blue) with 20% data to be forgotten. (Seed 42)
the gradients in the Taylor expansion of Equation (2) are not the true gradients but rather the clipped gradients, which introduces an approximation error. Our subsequent experiments will demonstrate that this error can be rendered negligible. It is worth noting that our method does not inherently rely on gradient clipping but instead imposes requirements on the stability of the learning process.
Configurations: We investigate the impact of gradient clipping with thresholds set at [0.3, 0.5, 0.8, 2, 3, 4, 5, 6, 7, 8, 9, 10, 15, 20, 25, 30, 35). We remove 20% of the data while keeping other hyperparameter settings consistent with those described in the main text.
Impact of gradient clipping. As evidenced in Figure 12, the implementation of small clipping thresholds results in scaling down of the gradient proportional its norm, producing effect similar to using a smaller step size. Consequently, the application of lower clipping thresholds maintains the error surpasses certain range, the еттоr introduced by the clipping process becomes the predominant factor, culminating in an escalation of the overall error. Nonetheless, most gradients no longer require clipping during the optimization process. Therefore, the induced error diminishes until the threshold reaches a sufficiently elevated value, at which point no supplementary error is introduced. Once this threshold is attained, gradient clipping ceases to exert an influence on the performance of our proposed unlearning algorithm.
relatively minimal level. However, as the gradient clipping threshold
37


Reviews:
[{"review_id": "b81a3lzKtu", "reviewer": "Reviewer_kjAJ", "summary": "This paper addresses the challenge of certified unlearning, where models are required to forget information at the request of data providers. The authors introduce a novel approach leveraging details tracked during model training to approximate how the training process would have proceeded without the data marked for deletion. Notably, the proposed method circumvents the need for full Hessian computations or inversion by using Hessian-vector products for second-order information. Additionally, it does not assume that the original model is an empirical risk minimizer. The authors' theoretical analysis argues that their method offers enhanced unlearning guarantees, efficient storage and precomputation, faster data deletion, and improved generalization bound, particularly for overparameterized models. Empirical results support the approach's claim of rapid unlearning execution.", "questions": "1. In the abstract (Line 017) and introduction (Line 073), the authors claim that previous work requires strong convexity, while in Line 66 the authors said previous work requires convexity. It seems to me that convexity suffices in Sekhari et al. (2021) because unlearning for a convex loss function can be reduced to a problem with strong convex loss. Could the authors clarify what assumptions are needed in previous work? \n2. In Assumption 1 (Line 299), is the loss assumed to be jointly convex in both $z$ and $w$, only $w$, or only $z$? Similar questions for Lipschitzness and smoothness.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1. The idea of tracking algorithmic updates during training to facilitate unlearning is straightforward yet impactful, with sound theoretical analysis for unlearning privacy guarantee and descent empirical evaluation.\n2. Removing the assumption that the initial learned model must be an empirical risk minimizer is significant for the practical applicability of the method.\n3. The claimed efficiency improvements are particularly relevant for overparameterized deep models where the batch size is comparable to the number of training epochs, probably covering a substantial portion of common machine learning models.", "weaknesses": "1) The claim regarding the efficiency of precomputation and storage (lines 378–387) hinges on two critical assumptions: (i) the model's parameter size $d$ is significantly greater than the training data size $n$, and (ii) the number of epochs $E$ is of the same order as the batch size $|B|$. While the authors state (ii) as typical (\"Typically, $E$ and $|B|$ are of the same order\"), a reference would strengthen this claim. Moreover, the assumption may not hold in scenarios such as online learning or streaming applications. Qualifying its generality and highlighting this as an assumption similar to Line 299 would be beneficial and avoid misleading readers.\n\n2) The generalization analysis in Section 4.2 considers strong convex loss functions and focuses on excess risk bound. Excess risk bound consist of two terms: the first term comes from (a) the excess risk of the empirical risk minimizer, and the second term comes from (b) unlearning error, (c) optimization error, and (d) the noise for obfuscation (Line 14 of Algorithm 1). There are at least two problems with this analysis and theorem statement.\n\n2.1 In strong convex settings, the assumption that $E$ and $|B|$ are comparable can seem more questionable, especially as the excess risk bound expressed in big-O notations (Line 319) uses this assumption. It might be okay to make this assumption for controlling (b), but $E$ and $B$ also affects (c), i.e. whether the term $C_4$ in Equation 74 is small enough, which conceptually (roughly) translates to whether $w_{E, B}$ is a good empirical minimizer or not. It seems problematic to assert that the number of epoch required for convergence to empirical risk minimizer is the same order of magnitude as batch size. \n\n2.2 The first term comes from Lemma 9, which cites Shalev-Shwartz et al. (2009). The latter assumes i.i.d. of samples, which should translate to i.i.d. of the set $U$.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "sYmM78CHxa", "reviewer": "Reviewer_CNQV", "summary": "The paper proposes a new unlearning algorithm which extracts second-order information in a Hessian-free manner without the need to assume strong convexity. The key idea is to track and remove the impact of a specific sample in the entire update trajectory of the model, which is called affine stochastic recursion between the retrained and learned models in this work. It provides theoretical guarantees on generalization, deletion capacity, and space/time complexities. Experiments are conducted to demonstrate the superiority of the proposed algorithm.", "questions": "1) Could you explain why NS and IJ can't utilize HVP? Although they involve Hessian inverse, it could be approximated by using like least-square which essentially does HVP as well. \n2) Regarding the correlation metric on loss change, could you tell us what stopping rule you use while calculating those loss changes across different algorithms? I feel this is important for gauging performance.\n3) It is unclear whether fine-tuning was used for each of the algorithms in experiments.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "Strengths include:\n1) The paper proposes affine stochastic recursion to pinpoint the overall impact of a specific sample on the learned model.\n2) It makes the unlearning process efficient via the Hessian-free computation.\n3) It provides theoretical guarantees that cover generalization, deletion capacity, and space/time complexities. \n4) Experiments are provided to demonstrate the advantages of the proposed unlearning algorithm.", "weaknesses": "Weaknesses include:\n1) The recollection matrix M looks incorrect, based on the derivation given in Appendix C.1\n2) Limitations of the algorithms are not discussed. For example, the proposed algorithm may not perform well on large-scale datasets given the quadratic time complexity in data size.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ZyvXeVRfg4", "reviewer": "Reviewer_ia1D", "summary": "This paper proposes a Hessian-free approach to certified machine unlearning that aims to improve computational efficiency and scalability in removing specific data points from a model without full retraining. Instead of relying on direct Hessian computations, which are computationally prohibitive in high-dimensional and non-convex settings, the method approximates the impact of data removal through affine stochastic recursions that analyze model update discrepancies. The method achieves computational gains, reducing unlearning time to $\\mathcal{O}(md)$ and storage to $\\mathcal{O}(nd)$, outperforming existing second-order methods.", "questions": "Please refer to weaknesses.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 1, "contribution": 2, "strengths": "- Both online learning and certified unlearning are highly significant research areas in machine learning.\n The paper is the first to introduce a Hessian-free approach to certified unlearning, which is a notable change from the dominant reliance on Hessian-based methods in second-order unlearning.\n\n- Experimental validation shows unlearning runtime in milliseconds, robust generalization guarantees, and privacy improvements against membership inference attacks with an added noise mechanism.\n\n- The authors also include relevant code and pseudo-code in the appendix, which is helpful for reproducibility.", "weaknesses": "1. The paper’s theoretical guarantees hinge on assumptions of convexity and smoothness (Assumption 1), which restricts the scope of the analysis to settings that are arguably idealized for real-world applications involving non-convex (e.g. deep learning) models. Thus, the authors likely overstate their contributions.\n\n2. I would say, Hessian-free optimization for second-order (and even higher-order) algorithms is an active research area. Beyond the Machine Unlearning domain discussed in detail on page 3 and in Appendix A, the authors should connect the ideas presented here with a broader body of Hessian-free optimization work in classical parametric optimization. A numerical comparison, if feasible, is also encouraged, as this may better highlight the novelty of this paper’s contributions beyond merely applying existing Hessian-free methods to the Machine Unlearning field.\n\n3. While the authors present some experimental results, they lack diversity in dataset selection and only test the approach on ~5 datasets. The efficacy of this unlearning mechanism remains unclear in large-scale or high-dimensional applications where computational efficiency is critical.\n\n\n4. The writing quality of this work is limited and the presentation should be improved, for instance\n\n- the (2) is simply one case of (1) by replacing the $\\mathcal{D}$ with empirical distribution. i.e., the authors could remove (2) for simplicity, or just start from the (1)\n\n- I think the (3) should be written as $\\mathbf{w}\\_{e, b+1} \\leftarrow \\mathbf{w}\\_{e, b}-\\eta\\_{e, b} \\sum\\_{i \\in \\mathcal{B}_{e, b}} \\nabla \\ell\\left(\\mathbf{w}\\_{e, b} ; z\\_i\\right),$ since the linear scaling rule (Goyal et al. 2017) is introduced later in line 163.\n\n- line 156 and algo. 1: as your notation, the total epochs and batches would be $E+1$ and $B+1$. So as your complexity in section 4.4\n\n- when removing the $u\\_j$, why the normalization constant of $\\eta$ in your (5) is $ \\mathcal{B}\\_{e, b(u\\_j)}$ instead of $ \\mathcal{B}\\_{e, b(u\\_j)}-1$?\n\n- definition 1: how can you ask a learning algorithm within the (solution) parameter space $\\mathcal{W}$? Please revise the definition or rephrase your wording\n\n- in your lemma 2, I don't think there exists a valid $G$ such that $G=\\max \\left\\\\|\\nabla \\ell\\left(\\mathbf{w}_{e, b} ; z\\right)\\right\\\\|<\\infty$. This should be a consequence of the assumption that the grad of $l$ is uniformly upper bounded. Otherwise, this could be derived by your assumption 1, which is imposed later\n\n- Theorem 4 should be $B=\\left\\lceil \\frac{n}{|\\mathcal{B}|} \\right\\rceil$\n\n- if the intent is for the product to go in reverse order in line 10 of algo. 1, i.e. $\\prod_{k=E}^e \\prod_{b=B-1}^{b(u)+1}$, the notation should ideally be clarified in the text to avoid misunderstandings\n\n- font size in figures e.g., 1, 2, 7, is too small and needs to be enlarged for clarity\n\n- figure 4 caption: \"a comparison comparison between\"", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "CUPFQqz3Ui", "reviewer": "Reviewer_t2wR", "summary": "This paper proposes a Hessian-free machine unlearning algorithm. The authors theoretically analyze the approximation error for both convex and non-convex loss functions and prove the generalization theory for strongly convex loss functions. Extensive experiments demonstrate the efficiency of the proposed algorithm compared to other Hessian-based algorithms.", "questions": "1. The authors propose using HVP to avoid directly calculating the Hessian matrix and reduce computational complexity, as discussed in Section 4.4. Could other algorithms discussed in Section 4.4 also benefit from HVP? For example, for IJ, $H^{-1}\\nabla \\ell $ can be approximately computed using $K$ steps of the conjugate gradient method, where each step HVP can be applied. Could this approach enable IJ to achieve lower complexity and experiment time, considering the entire process of precomputation and unlearning?  In this case, how does the proposed algorithm compare to IJ?\n2. The authors discuss in Appendix E that a small step size leads to a smaller approximation error. However, a small step size may result in insufficient model training. Could the authors further explain the trade-off?", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The authors analyze the training trajectory and propose a machine unlearning algorithm, which is practical and innovative.\n2. Compared to other Hessian-based algorithms, the proposed Hessian-free algorithm is efficient, especially for high-dimensional problems.\n3. The authors conducted comprehensive experiments to validate the effectiveness of their proposed algorithm, and the experimental results are well presented.", "weaknesses": "Although the authors provide the approximation error analysis, there is no theoretical guarantee for the generalization performance of the unlearning model in the non-convex case.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)