## Towards Certified Unlearning for Deep Neural Networks

Binchi Zhang 1 Yushun Dong 1 Tianhao Wang 1 Jundong Li 1

## Abstract

In the field of machine unlearning, certified unlearning has been extensively studied in convex machine learning models due to its high efficiency and strong theoretical guarantees. However, its application to deep neural networks (DNNs), known for their highly nonconvex nature, still poses challenges. To bridge the gap between certified unlearning and DNNs, we propose several simple techniques to extend certified unlearning methods to nonconvex objectives. To reduce the time complexity, we develop an efficient computation method by inverse Hessian approximation without compromising certification guarantees. In addition, we extend our discussion of certification to nonconvergence training and sequential unlearning, considering that real-world users can send unlearning requests at different time points. Extensive experiments on three real-world datasets demonstrate the efficacy of our method and the advantages of certified unlearning in DNNs.

deleting user data and its lineage from a machine learning model. Although the target data can be effectively unlearned by retraining the model from scratch, this method can incur a high computational cost, limiting its practical applications. To address this problem, certified unlearning was proposed to find an efficient approximation of the retrained model. In particular, the difference between the distributions of the unlearned model and the retrained model is bounded, making certified unlearning a stringent unlearning notion.

## 1. Introduction

In modern machine learning applications, model training often requires access to vast amounts of user data. For example, computer vision models often rely on images sourced from platforms such as Flickr, shared by its users (Thomee et al., 2016). However, as concerns about user data privacy grow, recent legislation such as the General Data Protection Regulation (GDPR, 2016) and the California Consumer Privacy Act (CCPA, 2018) have underscored the importance of the right to be forgotten , which enables users to request the deletion of their data from entities that store it. The emergence of the right to be forgotten has prompted the development of a new research domain known as machine unlearning (Sommer et al., 2022; Mercuri et al., 2022; Nguyen et al., 2022; Xu et al., 2023; Zhang et al., 2023), i.e.,

1 University of Virginia, Charlottesville, V A, USA. Correspondence to: Jundong Li &lt;jundong@virginia.edu&gt;.

Proceedings of the 41 st International Conference on Machine Learning , Vienna, Austria. PMLR 235, 2024. Copyright 2024 by the author(s).

Despite the extensive study of certified unlearning in various machine learning models such as linear models (Guo et al., 2020; Izzo et al., 2021; Mahadevan &amp; Mathioudakis, 2021), general convex models (Ullah et al., 2021; Sekhari et al., 2021; Neel et al., 2021), Bayesian models (Nguyen et al., 2020), sum-product networks (Becker &amp; Liebig, 2022), and graph neural networks (Pan et al., 2023; Chien et al., 2023; Wu et al., 2023b;a; Dong et al., 2024), the understanding of certified unlearning for deep neural networks (DNNs) remains nascent. Most of the previous unlearning methods applied to DNNs (Golatkar et al., 2020; 2021; Tarun et al., 2023; Chundawat et al., 2023) only introduced empirical approximation of the retrained model and failed to obtain a theoretical certification. Although Mehta et al. tentatively analyzed the certification for DNNs, their results strongly rely on the convexity assumption, which is unrealistic and yields a significant gap between certified unlearning and DNNs.

To bridge the gap between certified unlearning and DNNs, we investigate the problem of certified unlearning without relying on convexity assumptions. First, we divide certified unlearning into two steps, estimating the retrained model with a bounded error and adding random noises corresponding to the approximation error bound. Existing works (Golatkar et al., 2020; 2021; Mehta et al., 2022; Warnecke et al., 2023) typically estimate the retrained model based on a single-step Newton update for convex objectives. In this paper, we demonstrate that by making simple modifications to the Newton update, we can establish an approximation error bound for nonconvex (more precisely, weakly convex (Davis &amp;Grimmer, 2019; Davis &amp; Drusvyatskiy, 2019)) functions such as DNNs. It is worth noting that our proposed techniques can be adapted to different approximate unlearning strategies for convex models to improve their soundness in DNNs. To improve the efficiency of the Newton up-

date, we follow previous work to exploit a computationally efficient method to estimate the inverse Hessian in the Newton update and prove that the efficient method preserves a bounded approximation error. In addition, we explore the flexibility of our method to complex real-world scenarios in two specific cases where strategies such as early stopping can stop the training from convergence and users can send unlearning requests at different time points. Consequently, we adapt our certified unlearning approach to the nonconvergence training (the trained model is not a local optimum) and the sequential manner (the current unlearning process stems from a formerly unlearned model) without compromising certification guarantees. Finally, we conduct extensive experiments including ablation studies to verify the effectiveness of our certified unlearning for DNNs in practice. In particular, we use different metrics such as membership inference attacks (Chen et al., 2021) and relearn time (Golatkar et al., 2020) to evaluate the unlearning performance in preserving the privacy of unlearned samples, providing empirical evidence of the effectiveness of our approach. Further analysis explores the advantages of certified unlearning, e.g., stringency (certified unlearning outperforms other unlearning baselines with a relatively loose certification budget), efficiency, and robustness under sequential unlearning.

## 2. Certified Unlearning

Preliminary. Let D be a training dataset with n data samples derived from the sample space Z , and let H be the parameter space of a hypothesis class. Let A : Z n → H be a randomized learning process that takes the training set D as input and outputs the optimal w ∗ ∈ H that minimizes the empirical risk on D as

$$w ^ { * } = \mathcal { A } ( \mathcal { D } ) = \arg \min _ { w \in \mathcal { H } } \mathcal { L } ( w, \mathcal { D } ). \quad ( 1 ) \quad \text{the 1} \dots.$$

L is the empirical risk function that measures the error of a model over each training sample as L ( w , D ) = 1 n ∑ x ∈D l ( w x , ) , where l ( w x , ) is the loss function of the model w on the sample x , e.g., cross-entropy loss and mean squared error. After the learning process, we obtain a trained model w ∗ = A D ( ) .

In machine unlearning, to remove some training samples D u ⊂ D from the trained model w ∗ , a common way is to leverage a randomized unlearning process U to update w ∗ and obtain an unlearned model w -= U ( w ∗ , D u , D ) , consequently. We denote the number of unlearned samples as n u = |D | u . A straightforward but exact unlearning process is to retrain the model from scratch. Let ˜ w ∗ be the retrained model and D r = D\D u , then we have ˜ w ∗ = argmin w ∈H L ( w , D r ) . Despite the rigor of retraining, the high computational cost makes it a trivial method that cannot be used in practice. Instead, certified unlearning processes find an unlearned model similar to the re-trained model, but with much less computation cost. Next, we introduce the definition of certified unlearning (Guo et al., 2020).

Definition 2.1. ( ε -δ certified unlearning) Let D be a training set, D u ⊂ D be an unlearned set, D r = D\D u be the retained set, H be the hypothesis space, and A be a learning process. U is an ε -δ certified unlearning process iff ∀ T ⊆ H , we have

$$\text{cl} \quad \Pr \left ( \mathcal { U } \left ( \mathcal { D }, \mathcal { D } _ { u }, \mathcal { A } \left ( \mathcal { D } \right ) \right ) \in \mathcal { T } \right ) \leq e ^ { \varepsilon } \Pr \left ( \mathcal { A } \left ( \mathcal { D } _ { r } \right ) \in \mathcal { T } \right ) + \delta, \quad ( 2 ) \\ \text{ing} \quad \Pr \left ( \mathcal { A } \left ( \mathcal { D } _ { r } \right ) \in \mathcal { T } \right ) \leq e ^ { \varepsilon } \Pr \left ( \mathcal { U } \left ( \mathcal { D }, \mathcal { D } _ { u }, \mathcal { A } \left ( \mathcal { D } \right ) \right ) \in \mathcal { T } \right ) + \delta.$$

Certified Unlearning and Differential Privacy. It is worth noting that Definition 2.1 is derived from the notion of differential privacy (Dwork, 2006). Specifically, a randomized algorithm M : N n →R gives ε -δ differential privacy iff ∀ T ⊆ R and ∀ x y , ∈ N n such that ∥ x -y ∥ 1 = b ,

$$\Pr ( \mathcal { M } ( x ) \in \mathcal { T } ) \leq e ^ { \varepsilon } \Pr ( \mathcal { M } ( y ) \in \mathcal { T } ) + \delta. \quad ( 3 )$$

Here, x and y can be seen as two adjacent datasets with b different data records. Noting the similarity of certified unlearning and differential privacy, we clarify their relationship as follows.

Proposition 2.2. If learning algorithm A provides ε -δ differential privacy, A D ( ) is an ε -δ certified unlearned model.

Proposition 2.2 indicates that differential privacy is a sufficient condition of certified unlearning. One of the advantages of differential privacy is its weak assumptions: differential privacy can be achieved without any requirements on convexity or continuity. Such property perfectly fits DNNs, which are usually nonconvex. Luckily, Proposition 2.2 enables achieving certified unlearning by borrowing the techniques in differential privacy. Consequently, we have the following theorem for certified unlearning.

Theorem 2.3. Let ˜ w ∗ be the empirical minimizer over D r and ˜ = w F ( w ∗ , D u , D ) be an approximation of ˜ w ∗ . Define ∆ as an upper bound of ∥ ˜ w -˜ w ∗ ∥ 2 , then we have U ( w ∗ , D u , D ) = ˜ + w Y is an ε -δ certified unlearning process, where Y ∼ N (0 , σ 2 I ) and σ ≥ ∆ ε √ 2ln(1 25 . /δ ) .

The proof of Theorem 2.3 is provided in Appendix A. With Theorem 2.3, we divide the problem of certified unlearning into two parts, estimating the retrained model and adding noise corresponding to the approximation error . We illustrate the framework of certified unlearning in Figure 1. Next, our primary goal is to find the approximation function F where the output ˜ = w F ( w ∗ , D u , D ) estimates the minimizer ˜ w ∗ with a bounded approximation error .

Additional Remarks on Privacy and Unlearning. The deduction of our certification budgets stems from results in differential privacy (Dwork et al., 2014). According to recent

Figure 1. Illustration of certified unlearning, where the first step is to estimate the retrained model based on the original model, and the second step is to add noise to it. According to Theorem 2.3, we can guarantee the difference in distributions between the unlearned model and the retrained model is bounded by certification budgets.

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00920v2-figure-5a8db47b-42d9-4ff1-921d-c38423a66dac.jpg)

literature (Balle &amp; Wang, 2018) in differential privacy, we notice that our certification budgets can be further tightened, i.e., we can achieve ε -δ certified unlearning by adding a noise with a smaller variance σ . In particular, we can find a smaller σ by satisfying Φ( ∆ 2 σ -εσ ∆ ) -e ε Φ( -∆ 2 σ -εσ ∆ ) ≤ δ , where Φ is the cumulative distribution function of the standard Gaussian. For simplicity, we still use the results in Theorem 2.3 in the following discussion.

In addition, in the classical differential privacy (Dwork et al., 2014), the value of privacy level ε is less than 1 . However, this condition is sometimes difficult to satisfy in certified unlearning for DNNs. Luckily, according to the Theorem 4 in (Balle &amp; Wang, 2018), the certification of unlearning can be preserved when ε ≥ 1 by increasing the variance of the noise σ (scaled by a factor O ( √ ε ) ).

## 3. Methodology

Existing Studies. In existing studies (Guo et al., 2020; Golatkar et al., 2020; 2021; Mehta et al., 2022), a single-step Newton update is widely used to estimate the empirical minimizer ˜ w ∗ and then add noise to satisfy unlearning. Assuming the second-order derivative of L with respect to w exists and is continuous, one can take the Taylor expansion of ∇L at w ∗ as

$$\nabla \mathcal { L } ( \tilde { w } ^ { * }, \mathcal { D } _ { r } ) \approx \nabla \mathcal { L } ( w ^ { * }, \mathcal { D } _ { r } ) + H _ { w ^ { * } } ( \tilde { w } ^ { * } - w ^ { * } ), \ ( 4 ) \quad \text{Then},$$

where H w ∗ = ∇ L 2 ( w ∗ , D r ) denotes the Hessian of L over D r at w ∗ . We also have ∇L ( ˜ w ∗ , D r ) = 0 since ˜ w ∗ is the minimizer. Move ˜ w ∗ term to the left-hand side and we have

$$\tilde { w } ^ { * } \approx \tilde { w } = w ^ { * } - H _ { w ^ { * } } ^ { - 1 } \nabla \mathcal { L } ( w ^ { * }, \mathcal { D } _ { r } ). \quad ( 5 ) \quad ( 2 ).$$

In Equation (5), we consider the right-hand side as an approximation of ˜ w ∗ and use ˜ w to denote the approximation value. Equation (5) cannot directly serve as the function F unless it satisfies two requirements simultaneously: (1). bounded approximation error ; and (2). computational efficiency , which are extremely challenging due to the nature of DNNs. However, we found that we can make the single-step Newton update satisfy these requirements by making simple revisions to Equation (5). Next, we provide a detailed analysis.

Approximation Error. In Equation (4), we truncate the Taylor series and only consider the first-order term, hence Equation (5) has an error in estimating the value of ˜ w ∗ . Prior to further discussion, we first make the following assumptions.

Assumption 3.1. The loss function l ( w x , ) has an L -Lipschitz gradient in terms of w .

Assumption 3.2. The loss function l ( w x , ) has an M -Lipschitz Hessian in terms of w .

Assumption 3.1 and Assumption 3.2 are widely used in existing works (Guo et al., 2020; Sekhari et al., 2021; Chien et al., 2023; Wu et al., 2023a;b). In contrast to most existing works, our assumption does not necessitate the convexity of the objective, enabling our discussion to be applicable to DNNs in practice. The following proposition provides a preliminary result on the approximation error bound.

Lemma 3.3. Let w ∗ = argmin w ∈H L ( w , D ) and ˜ w ∗ = argmin w ∈H L ( w , D r ) . Let ˜ = w w ∗ -H -1 w ∗ ∇L ( w ∗ , D r ) be an approximation of ˜ w ∗ . Consider Assumption 3.2, we have

$$\| \tilde { w } - \tilde { w } ^ { * } \| _ { 2 } \leq \frac { M } { 2 } \| H _ { w ^ { * } } ^ { - 1 } \| _ { 2 } \cdot \| w ^ { * } - \tilde { w } ^ { * } \| _ { 2 } ^ { 2 }. \quad ( 6 )$$

The proof of Lemma 3.3 can be found in Appendix A. From Lemma 3.3, we can find that the approximation error bound is determined by two factors: ∥ H -1 w ∗ ∥ 2 and ∥ w ∗ -˜ w ∗ ∥ 2 2 . Next, we aim to bound these two factors separately.

(1). The norm of the inverse Hessian ∥ H -1 w ∗ ∥ 2 : For nonconvex objective L ( w , D r ) , ∥ H -1 w ∗ ∥ 2 can be arbitrarily large. To bound the value of ∥ H -1 w ∗ ∥ 2 , we exploit the local convex approximation technique (Nocedal &amp; Wright, 2006). Specifically, we add an ℓ -2 regularization term to the objective as L ( w , D r ) + λ 2 ∥ w ∥ 2 2 when computing the Hessian. Then, we have ˜ w = w ∗ -( H w ∗ + λ I ) -1 ∇L ( w ∗ , D r ) and the norm of the inverse Hessian changes to ∥ ( H w ∗ + λ I ) -1 ∥ 2 , correspondingly. Intuitively, we use local convex approximation to make the nonconvex objective ( λ min &lt; 0 ) strongly convex with parameter λ + λ min at w ∗ .

(2). The squared ℓ -2 distance between w ∗ and ˜ w ∗ : ∥ w ∗ -˜ w ∗ ∥ 2 2 : We find that ∥ w ∗ -˜ w ∗ ∥ 2 2 is completely determined by the optimization problem in the learning process. To bound the value of ∥ w ∗ -˜ w ∗ ∥ 2 2 , we modify the optimization problem by adding a constraint ∥ w ∥ 2 ≤ C in the learning process . Then we have w ∗ = argmin ∥ w ∥ ≤ 2 C L ( w , D ) and ˜ w ∗ = argmin ∥ w ∥ ≤ 2 C L ( w , D r ) , correspondingly. It is

worth noting that previous studies (Guo et al., 2020; Sekhari et al., 2021) assume the objective to be Lipschitz continuous and strongly convex simultaneously. However, these assumptions are contradictory unless the norm of model parameters is bounded (see Appendix C). In this paper, we directly achieve the important requirements of bounded model parameters which is implicitly required in previous works. We resort to projected gradient descent (Bertsekas, 1997) to solve this constrained optimization problem in the learning process. By considering this constraint, we can obtain a worst-case upper bound of the term ∥ w ∗ -˜ w ∗ ∥ 2 2 which is independent of the size of the unlearned set .

By leveraging the local convex approximation and the constraint on the norm of the parameters, we can further derive a tractable approximation error bound.

Theorem 3.4. Let w ∗ = argmin ∥ w ∥ ≤ 2 C L ( w , D ) and ˜ w ∗ = argmin ∥ w ∥ ≤ 2 C L ( w , D r ) . Denote λ min as the smallest eigenvalue of H w ∗ . Let ˜ w = w ∗ -( H w ∗ + λ I ) -1 ∇L ( w ∗ , D r ) be an approximation of ˜ w ∗ , where λ &gt; ∥ H w ∗ ∥ 2 . Consider Assumption 3.2, we have

$$\| \tilde { w } - \tilde { w } ^ { * } \| _ { 2 } \leq \frac { 2 C ( M C + \lambda ) } { \lambda + \lambda _ { m i n } }. \quad \quad ( 7 ) \quad \frac { J o n } { ( n - 1 ) } \\ \ w h e$$

The proof of Theorem 3.4 is provided in Appendix A. Theorem 3.4 provides a basic result for the approximation error bound. In contrast to previous studies, our result does not require the objective to be convex. We compare the approximation error bounds with and without the convexity assumption in Appendix B to show our progress.

Computational Efficiency. The main advantage of certified unlearning compared with retraining from scratch is computational efficiency. Noting the importance of efficiency for certified unlearning, we aim to reduce the computational cost of ˜ = w F ( w ∗ , D u , D ) while keeping the approximation error bound . The computation cost contains two parts: the inverse Hessian ( H w ∗ + λ I ) -1 (with local convex approximation) and the gradient ∇L ( w ∗ , D r ) . First, assuming the number of learnable parameters is p , the computation of the inverse Hessian requires a complexity of O np ( 2 + p 3 ) . Since the scale of the DNNs can be extremely large, we adopt a computationally efficient algorithm, LiSSA (Agarwal et al., 2017), to estimate the inverse Hessian. In particular, we let X ∈ D r be a random variable of the retained training samples. Given s independent and identically distributed (i.i.d.) retained training samples { X ,. . . , X 1 s } , we can obtain s i.i.d. samples { H 1 ,λ , . . . , H s,λ } of the Hessian matrix H w ∗ + λ I , where H i,λ = ∇ L 2 ( w ∗ , X i ) + λ I . Then, we can construct an estimator of the inverse Hessian.

Proposition 3.5. Given s i.i.d. samples { H 1 ,λ , . . . , H s,λ } of the Hessian matrix H w ∗ + λ I , we let

$$\tilde { H } _ { t, \lambda } ^ { - 1 } = I + \left ( I - \frac { H _ { t, \lambda } } { H } \right ) \tilde { H } _ { t - 1, \lambda } ^ { - 1 }, \, \tilde { H } _ { 0, \lambda } ^ { - 1 } = I, \quad ( 8 ) \quad \text{Cons}$$

where ∥∇ 2 l ( w ∗ , x ) + λ I ∥ ≤ H , ∀ x ∈ D r . Then, we have that ˜ H -1 s,λ H is an asymptotic unbiased estimator of the inverse Hessian ( H w ∗ + λ I ) -1 .

The proof of Proposition 3.5 can be found in Appendix A. By incorporating the Hessian-vector product technique, we can compute ˜ H -1 s,λ ∇L ( w ∗ , D r ) with a complexity of O sp ( 2 ) which is independent of n . Second, to compute the gradient ∇L ( w ∗ , D r ) efficiently, we leverage the property of the minimizer w ∗ that ∇L ( w ∗ , D ) = n u n ∇L ( w ∗ , D u ) + n -n u n ∇L ( w ∗ , D r ) = 0 . Noting that the number of unlearned samples is usually much smaller than the number of retained samples, we can replace the gradient ∇L ( w ∗ , D r ) as ∇L ( w ∗ , D r ) = -n u n -n u ∇L ( w ∗ , D u ) and reduce the complexity from O np ( ) to O n p ( u ) where n u ≪ n . After exploiting the two efficient techniques, we prove the approximation error is still bounded as follows.

Theorem 3.6. Let w ∗ = argmin ∥ w ∥ ≤ 2 C L ( w , D ) and ˜ w ∗ = argmin ∥ w ∥ ≤ 2 C L ( w , D r ) . Let λ min be the smallest eigenvalue of H w ∗ , and s be the recursion number for the inverse Hessian approximation. Let ˜ w = w ∗ + n u ( n -n u ) H ˜ H -1 s,λ ∇L ( w ∗ , D u ) be an approximation of ˜ w ∗ , where λ &gt; ∥ H w ∗ ∥ 2 . Consider Assumption 3.1 and Assumption 3.2, the following inequality holds with a probability larger than 1 -ρ .

$$\underset { \text{evit} \nu } { s \, \text{not} } \underset { \text{eq} } { \ e \, \text{ap-} } \quad \| \tilde { w } - \tilde { w } ^ { * } \| _ { 2 } \leq \frac { 2 C ( M C + \lambda ) } { \lambda + \lambda _ { m i n } } + \left ( \frac { 3 2 \sqrt { \ln d / \rho } } { \lambda + \lambda _ { m i n } } + \frac { 1 } { 8 } \right ) \, L C. \ ( 9 )$$

The proof of Theorem 3.6 is provided in Appendix A. Finally, we obtain a computationally efficient F with bounded approximation error as

$$\text{ncy} _ { \text{onal} } \quad \mathcal { F } ( w ^ { * }, \mathcal { D } _ { u }, \mathcal { D } ) = w ^ { * } + \frac { n _ { u } } { ( n - n _ { u } ) H } \tilde { H } _ { s, \lambda } ^ { - 1 } \nabla \mathcal { L } ( w ^ { * }, \mathcal { D } _ { u } ). \ ( 1 0 )$$

Based on our discussion, the complexity of computing F is O sp ( 2 + n p u ) . Consequently, we can achieve certified unlearning based on F according to Theorem 2.3. We formulate the overall algorithm for certified unlearning in Algorithm 1.

## 4. Practical Consideration

Nonconvergence. In previous results, we let w ∗ and ˜ w ∗ be the exact minimum of L over D and D r , respectively. However, the training process of DNNs usually stops before reaching the exact minimum, e.g., early stopping, for better generalization. Hereby, we analyze the approximation error bound under the nonconvergence condition. In the nonconvergence case, w ∗ and ˜ w ∗ are not the exact minimum which is intractable. We further assume that the norm of the gradient ∥∇L ( w ∗ , D ∥ ) and ∥∇L ( ˜ w ∗ , D r ) ∥ are bounded by G . Consequently, we have the adjusted approximation error bound in nonconvergence cases.

## Algorithm 1 Single-Batch Certified Unlearning for DNNs

Input : original trained model w ∗ ; certification budget ε and δ ; local convex coefficient λ ; norm upper bound C ; Hessian norm bound H ; number of recursion s ; unlearned set D u . Output : certified unlearning model w -.

- 1: Compute s i.i.d. Hessian samples { H 1 ,λ , . . . , H s,λ } .
- 2: P 0 ,λ ←∇L ( w ∗ , D u ) .
- 3: for j = 1 , . . . , s do
- 4: P j,λ ←∇L ( w ∗ , D u ) + ( I -H j,λ H ) P j -1 ,λ .
- 5: end for
- 6: ˜ w ← w ∗ + n u ( n -n u ) H P s,λ .
- 7: Compute the error bound ∆ based on Equation (11).
- 8: σ ← ∆ ε √ 2ln(1 25 . /δ ) .
- 9: w -← ˜ + w Y , where Y ∼ N (0 , σ 2 I ) .

Proposition 4.1. Let w ∗ and ˜ w ∗ be two learned model in practice such that ∥∇L ( w ∗ , D ∥ ∥∇L ) , ( ˜ w ∗ , D r ) ∥ ≤ G and ∥ w ∗ ∥ ∥ , ˜ w ∗ ∥ ≤ C . Let λ min be the smallest eigenvalue of H w ∗ , and s be the recursion number for the inverse Hessian approximation. Let ˜ = w w ∗ + n u ( n -n u ) H ˜ H -1 s,λ ∇L ( w ∗ , D u ) be an approximation of ˜ w ∗ , where λ &gt; ∥ H w ∗ ∥ 2 . Consider Assumption 3.1 and Assumption 3.2, the following inequality holds with a probability larger than 1 -ρ .

$$\| \tilde { w } - \tilde { w } ^ { * } \| _ { 2 } & \leq \frac { 2 C ( M C + \lambda ) + G } { \lambda + \lambda _ { m i n } } \\ & \quad + \left ( \frac { 1 6 \sqrt { \ln d / \rho } } { \lambda + \lambda _ { m i n } } + \frac { 1 } { 1 6 } \right ) ( 2 L C + G ). \begin{array} { c } \text{$row_{k}^{*}$ b} \\ \tilde { H } _ { s, \lambda, } \\ \arg m i \\ i s \text{ the} \\ \| \mathcal { H } _ { s }. \end{array}$$

The proof of Proposition 4.1 is provided in Appendix A. With Proposition 4.1, we can derive a more precise approximation error bound in practice, knowing the tractable residual gradient of the learning algorithm A ∥∇L : ( w ∗ , D ∥ ) .

Sequential Unlearning. In practical scenarios, the user can send unlearning requests at different time points in a sequential order (Guo et al., 2020; Nguyen et al., 2022). For example, after unlearning one user's data, another user sends the unlearning request. In such a case, we should unlearn the second user's data based on the unlearned model of the first user's data. Consequently, certified unlearning should be able to work in a sequential setting to fit realworld scenarios. We next show that our certified unlearning algorithm can be easily implemented in a sequential manner. Let D u k be the unlearned set of the k -th unlearning request and D r k = D\ ∪ k i =1 D u i be the retained set after the k -th unlearning request. We estimate the retrained model sequentially as ˜ w k = ˜ w k -1 -1 H ˜ H -1 s,λ,k -1 ∇L ( ˜ w k -1 , D r k ) where ˜ H -1 s,λ,k -1 is the approximation of the inverse Hessian over D r k at ˜ w k -1 . Note that in sequential approximation, we cannot use the efficient computation of ∇L ( ˜ w k -1 , D r k ) as ˜ w k -1 is not a minimum. After estimating the retrained model after the k -th unlearning request, we add noise to

## Algorithm 2 Sequential Unlearning for DNNs

Input : original trained model w ∗ ; certification budget ε and δ ; local convex coefficient λ ; norm upper bound C ; number of recursion s ; unlearned sets {D u 1 , . . . , D u k } .

Output : certified unlearning model w -.

- 1: ˜ w 0 ← w ∗ , D r 0 ←D .
- 2: for i = 1 , . . . , k do
- 3: D r i ←D r i -1 \D u i .
- 4: Obtain ∇L ( ˜ w k -1 , D r k ) and { H 1 ,λ,i , . . . , H s,λ,i } .
- 5: P 0 ,λ,i ←∇L ( ˜ w k -1 , D r k ) .
- 6: for j = 1 , . . . , s do
- 7: P j,λ,i ←∇L ( ˜ w k -1 , D r k )+( I -H j,λ,i H ) P j -1 ,λ,i .
- 8: end for
- 9: ˜ w i ← ˜ w i -1 -P s,λ,i H .
- 10: end for
- 11: Compute the error bound ∆ based on Equation (11).
- 12: σ ← ∆ ε √ 2ln(1 25 . /δ ) .
- 13: w -← ˜ w k + Y , where Y ∼ N (0 , σ 2 I ) .

obtain the unlearned model according to Theorem 2.3. We can prove that our sequential approximation also has the same approximation error bound as single-step cases.

Proposition 4.2. Let ˜ w 0 be a model trained on D , w ∗ k be a model trained on D r k , and ˜ w k = ˜ w k -1 -˜ H -1 s,λ,k -1 ∇L ( ˜ w k -1 , D r k ) be an approximation of w ∗ k = argmin ∥ w ∥ ≤ 2 C L ( w , D r k ) for k = 1 2 , , . . . , where λ min is the smallest eigenvalue of ∇ L 2 ( ˜ w k -1 , D r k ) and λ &gt; ∥ H w ∗ ∥ 2 . Consider Assumption 3.1 and Assumption 3.2 and assume ∥∇L ( ˜ w k , D r k -1 ) ∥ ∥∇L , ( w ∗ k , D r k ) ∥ ≤ G for k = 1 2 , , . . . , the sequential approximation error ∥ ˜ w k -w ∗ k ∥ 2 has the same upper bound as Proposition 4.1.

The proof of Proposition 4.2 is provided in Appendix A. Proposition 4.2 provides a theoretical guarantee on the certification for sequential unlearning. As mentioned before, our constraint on model parameters provides a worst-case upper bound of ∥ w ∗ -˜ w ∗ ∥ 2 2 independent on D u so that our error bound in Equation (11) remains unchanged as the number of unlearned data gradually increases. We illustrate the details of sequential unlearning in Algorithm 2. It is worth noting that we fix the number of unlearned samples in a single unlearning process to be b in Definition 2.1. During the sequential unlearning process, the number of unlearned samples keeps increasing. We can adapt the value of b after each unlearning request to fit the size of the current unlearned set in a post hoc manner. Another rigorous way to preserve the certification while fixing the unlearning granularity b is to incorporate the group privacy notion (Dwork et al., 2014) into the sequential unlearning process. Specifically, we can fix the unlearning granularity as the number of unlearning samples in a single unlearning request by linearly increasing the certification budget ε as kε , where k is the number of

the unlearning requests.

Reducing the Approximation Error Bound. With a lower approximation error bound, we can achieve the same certification budget by adding a smaller noise, leading to a smaller impact on the performance of the unlearned model. Therefore, we summarize our results and list several ways to reduce the approximation error bound in practice.

- · Increasing the value of λ . According to Equation (11), we can easily obtain that the approximation error bound decreases after increasing the value of λ .
- · Decreasing the value of C . Similarly, we can reduce the approximation error bound by decreasing the value of C . However, reducing C can impact the effectiveness of the original model. We should carefully select a proper C without compromising the model performance distinctly.
- · Increasing the regularization. Adding a larger regularization would increase the value of λ min . According to Equation (11), the approximation error bound decreases when λ min increases, which is consistent with the empirical results in (Basu et al., 2021).

## 5. Experiments

## 5.1. Dataset Information

We conduct experiments based on three widely adopted real-world datasets for image classification, MNIST (LeCun et al., 1998), SVHN (Netzer et al., 2011), and CIFAR10 (Krizhevsky et al., 2009) to evaluate certified unlearning for DNNs. The MNIST dataset consists of a collection of 60,000 handwritten digit images for training and 10,000 images for testing. The CIFAR-10 dataset contains 60,000 color images in 10 classes, with each class representing a specific object category. The dataset is split into 50,000 training images and 10,000 test images. The SVHN dataset consists of house numbers images captured from Google Street View. The dataset is divided into three subsets: 73,257 training images, 26,032 test images, and 531,131 extra images. We only use the training set and the test set.

## 5.2. Baseline Information

To evaluate unlearning methods, we choose three different types of original models for the image classification task. In particular, we train a three-layer MLP model, an AllCNN(Springenberg et al., 2015) model, and a ResNet18 (He et al., 2016) model for MNIST, CIFAR-10, and SVHN, respectively. Moreover, we compare the performance of our certified unlearning method with five unlearning baselines shown as follows. Retrain from scratch : retraining from scratch is an ideal unlearning baseline since it is usually considered as an exact unlearning method; Fine tune (Golatkar et al., 2020): fine-tuning the original model on the retained set D r for one epoch after training the original model; Negative gradient (Golatkar et al., 2020): conducting the gradient ascent based on the gradient in terms of the unlearned set D u for one epoch after training the original model; Fisher forgetting (Golatkar et al., 2020): after training the original model, the Fisher forgetting baseline exploits the Fisher information matrix to substitute the Hessian in the single-step Newton update; L-CODEC (Mehta et al., 2022): after training the original model, L-CODEC selects a subset of the model parameters to compute the Hessian based on the Fisher information matrix for efficiency.

## 5.3. Implementation

We implemented all experiments in the PyTorch (Paszke et al., 2019) package and exploited Adam (Kingma &amp; Ba, 2015) as the optimizer. All experiments are implemented on an Nvidia RTX A6000 GPU. We reported the average value and the standard deviation of the numerical results under three random seeds. For the values of L and M in our theoretical results, since finding a practical upper bound of the Lipschitz constant can be intractable for real-world tasks, we follow most previous works (Koh &amp; Liang, 2017; Wu et al., 2023a;b) to set them as hyperparameters which can be adjusted flexibly to adapt to different scenarios. The choice of these hyperparameters will not affect the soundness of our theoretical results, but render an imprecise value of the certification level, discussed in Appendix D. More detailed hyperparameter settings of certified unlearning and baselines can be found in Appendix D and Section 5.8. Our code is available at https://github.com/zhangbinchi/ certified-deep-unlearning .

## 5.4. Unlearning Performance

To evaluate the performance of all unlearning baselines, we select different unlearning metrics according to existing studies. Table 1 exhibits the model utility, i.e., micro F1-score of the predictions over the unlearned set D u , retained set D r , and the test set D t . Based on the meaning of machine unlearning, we expect the results of a desirable unlearning method to be close to the results of the retrained model . Hence, we use the retrain-from-scratch baseline as a standard for evaluating the unlearning baselines. Regarding the performance of unlearning baselines, we have the following observations derived from the comparison of our method with unlearning baselines. (1). The micro F1-score of the certified unlearning method on the unlearned set D u is closest to the retrained model for most cases. (2). The micro F1-score of the certified unlearning method on the retained set D r and the test set D t is closest to the retrained model on MNIST and CIFAR-10. (3). Compared with the original training, certified unlearning obtains an unlearned

Table 1. Comparison between the certified unlearning method and unlearning baselines over three popular DNNs across three real-world datasets. We record the micro F1-score of the predictions on the unlearned set D u , retained set D r , and test set D t .

| Method    | MLP &MNIST   | MLP &MNIST   | MLP &MNIST   | AllCNN &CIFAR-10   | AllCNN &CIFAR-10   | AllCNN &CIFAR-10   | ResNet18 &SVHN   | ResNet18 &SVHN   | ResNet18 &SVHN   |
|-----------|--------------|--------------|--------------|--------------------|--------------------|--------------------|------------------|------------------|------------------|
| Method    | F1 on D u    | F1 on D r    | F1 on D t    | F1 on D u          | F1 on D r          | F1 on D t          | F1 on D u        | F1 on D r        | F1 on D t        |
| Original  | 98.30 ± 0.51 | 98.37 ± 0.06 | 97.50 ± 0.08 | 87.97 ± 3.01       | 90.71 ± 1.11       | 83.04 ± 0.20       | 94.53 ± 0.74     | 95.00 ± 0.47     | 93.26 ± 0.34     |
| Retrain   | 97.20 ± 0.29 | 98.27 ± 0.09 | 97.19 ± 0.15 | 82.67 ± 0.57       | 90.10 ± 0.98       | 82.39 ± 0.98       | 93.13 ± 0.80     | 95.73 ± 0.60     | 93.34 ± 0.15     |
| Fine Tune | 97.67 ± 0.33 | 98.35 ± 0.15 | 97.22 ± 0.09 | 89.84 ± 1.99       | 92.25 ± 0.26       | 84.31 ± 0.54       | 93.73 ± 0.33     | 95.23 ± 0.47     | 93.75 ± 0.41     |
| Neg Grad  | 97.83 ± 0.59 | 98.09 ± 0.28 | 97.22 ± 0.16 | 79.60 ± 1.92       | 85.98 ± 2.97       | 78.66 ± 1.94       | 92.13 ± 0.77     | 92.10 ± 0.60     | 92.10 ± 0.60     |
| Fisher    | 97.70 ± 0.90 | 97.56 ± 0.14 | 96.69 ± 0.05 | 87.97 ± 3.69       | 90.71 ± 1.36       | 83.04 ± 0.24       | 94.23 ± 0.91     | 94.84 ± 0.49     | 93.06 ± 0.29     |
| L-CODEC   | 98.27 ± 0.61 | 98.35 ± 0.07 | 97.46 ± 0.09 | 88.20 ± 3.70       | 90.98 ± 1.28       | 83.33 ± 0.23       | 95.00 ± 1.06     | 95.83 ± 0.35     | 93.53 ± 0.08     |
| Certified | 97.60 ± 0.96 | 98.28 ± 0.05 | 97.37 ± 0.11 | 87.83 ± 3.62       | 90.68 ± 1.32       | 83.04 ± 0.38       | 93.73 ± 0.76     | 94.61 ± 0.57     | 92.94 ± 0.49     |

Table 2. Comparison between the certified unlearning method and unlearning baselines over three popular DNNs across three real-world datasets. We record the relearn time, the accuracy of the membership inference attack, and the AUC score of the membership inference attack for measuring the unlearning performance.

Table 3. The value of approximation error bound, approximation error, and approximation error without constraint under different values of the local convex coefficient λ over the AllCNN backbone on CIFAR-10.

| Method    | MLP &MNIST   | MLP &MNIST   | MLP &MNIST   | AllCNN &CIFAR-10   | AllCNN &CIFAR-10   | AllCNN &CIFAR-10   | ResNet18 &SVHN   | ResNet18 &SVHN   | ResNet18 &SVHN   |
|-----------|--------------|--------------|--------------|--------------------|--------------------|--------------------|------------------|------------------|------------------|
| Method    | Relearn T    | Attack Acc   | Attack AUC   | Relearn T          | Attack Acc         | Attack AUC         | Relearn T        | Attack Acc       | Attack AUC       |
| Retrain   | 25           | 93.10 ± 0.33 | 95.16 ± 0.47 | 17                 | 79.82 ± 0.35       | 88.71 ± 0.43       | 7                | 90.47 ± 0.14     | 93.07 ± 0.27     |
| Fine Tune | 17           | 93.65 ± 0.23 | 95.37 ± 0.46 | 14                 | 79.42 ± 1.05       | 88.13 ± 0.66       | 7                | 90.63 ± 0.32     | 92.96 ± 0.31     |
| Neg Grad  | 21           | 93.73 ± 0.45 | 95.42 ± 0.43 | 17                 | 78.63 ± 1.23       | 87.58 ± 0.96       | 9                | 90.02 ± 0.13     | 92.89 ± 0.22     |
| Fisher    | 21           | 93.85 ± 0.22 | 95.37 ± 0.51 | 14                 | 79.70 ± 1.03       | 88.58 ± 0.76       | 9                | 90.47 ± 0.84     | 93.13 ± 0.19     |
| L-CODEC   | 20           | 95.05 ± 0.05 | 95.31 ± 0.21 | 14                 | 83.60 ± 0.62       | 92.18 ± 0.17       | 7                | 93.22 ± 0.35     | 93.75 ± 0.54     |
| Certified | 24           | 93.22 ± 0.46 | 95.28 ± 0.50 | 25                 | 78.00 ± 1.18       | 87.22 ± 1.13       | 9                | 88.63 ± 1.58     | 92.18 ± 1.16     |

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00920v2-figure-e0f0075b-091d-4382-87ed-c20420071c49.jpg)

Figure 2. Comparison of unlearning time between the certified unlearning method and unlearning baselines over three popular DNNs across three datasets.

model with a lower F1-score over D u , D r , and D t , but the utility over D u always decreases the most, consistent with the goal of unlearning. In general, we can find that the negative gradient baseline leads to a large utility drop over all subsets and the L-CODEC baseline yields a distinct utility increase over all subsets. In contrast, our method has a lower prediction utility over the unlearned set D u and maintains a desirable utility over the retained set D r and the test set D t .

In Table 2, we record several different unlearning metrics, i.e., relearn time, F1-score of membership inference attack, and AUC score of membership inference attack. By relearning the unlearned model over the unlearned set, relearn time is the number of epochs for the loss function over the unlearned set D u to descend to a fixed threshold. We tried using the loss value of the original model over the forget set as the threshold but led to a very small relearn time that cannot

| λ    |   Err Bound |   Approx Err |   Approx Err (N) |
|------|-------------|--------------|------------------|
| 0    |  35077.8    |      26.5146 |          46.8936 |
| 10   |    390.33   |      26.1841 |          46.7587 |
| 10 2 |     78.4548 |      26.1724 |          46.724  |
| 10 3 |     46.9586 |      26.1692 |          46.7091 |
| 10 4 |     43.8059 |      26.1688 |          46.7035 |

discriminate any two baselines (most methods can recover the performance within 1 epoch). Finally, we artificially choose the threshold small enough to make the results of different baselines distinguishable. As an unlearning metric, a lower relearn time indicates the unlearned model retains more information of the unlearned samples. Moreover, we use the membership inference attack to evaluate the information leakage of the unlearning methods. Membership inference attack trains an adversary to infer whether a data sample is used to train the unlearned model. We choose the state-of-the-art membership inference attack method (Chen et al., 2021) for evaluating machine unlearning methods. Specifically, we use the accuracy and the AUC score to measure the utility of the membership inference attack. A higher attack success rate indicates the unlearned model contains more information of the unlearned samples. The experimental results demonstrate that our method is more effective

than other unlearning baselines in removing the information of the unlearned samples. It is worth noting that the retraining baseline is less desirable than other unlearning methods in some cases regarding the membership inference attack results. The reason is that the retraining baseline is directly used to train the shadow unlearned model in the membership inference attack framework (Chen et al., 2021) while the attack model is transferred to attack other unlearning baselines. In conclusion, our method can effectively remove the information of unlearned samples from the unlearned model and preserve the privacy of unlearned samples.

## 5.5. Efficiency

Efficiency is a crucial advantage of certified unlearning compared with retraining. We record the time cost in the unlearning stage for different unlearning baselines and exhibit the results in Figure 2. From the experimental results, we can observe that (1). Negative gradient has the shortest unlearning time and retraining has the longest unlearning time. (2). Certified unlearning has over 10 times speedup compared with exact unlearning (retrain) over DNNs. (3). Negative gradient, fine-tuning, and L-CODEC have shorter unlearning time but less desirable unlearning performance than certified unlearning. In addition, an important advantage of certified unlearning is its efficiency in adjusting hyperparameters. In practice, we should choose a proper group of hyperparameters considering the tradeoff between the utility of unlearning target data and the utility of predicting remaining data. Although the prediction utility can be evaluated efficiently by prevalent utility metrics such as accuracy and F1-score, evaluating unlearning utility is much more costly. For the unlearning methods without a certification, we can only obtain the unlearning utility by comparing the prediction utility with retrained models or launching membership inference attacks. In contrast, for certified unlearning methods, the certification budgets can be an effective clue of the unlearning utility and we can adjust the hyperparameters efficiently corresponding to the certification budgets.

## 5.6. Ablation Study

Knowing that certified unlearning for DNNs is practical in real-world experiments, we conduct ablation studies to verify the effectiveness of adopted techniques separately. Specifically, to verify the effectiveness of the local convex approximation, we remove the local convex approximation by setting λ = 0 . We gradually increase the value of λ and record the approximation error and the approximation error bound computed by Equation (11). Moreover, to verify the effectiveness of the constraint ∥ w ∥ 2 ≤ C , we remove the constraint and record the approximation error under each λ . To compute the approximation error, we compute the Euclidean distance of the unlearned model parameters and the retrained model parameters. We present the experimental results in Table 3. We can observe from Table 3 that (1). Local convex approximation can distinctly reduce the approximation error bound and slightly reduce the real approximation error as well. (2). Certified unlearning with the constraint ∥ w ∥ 2 ≤ C has a much lower approximation error (bound). (3). There exists a potential of the approximation error bound to be further tightened.

In addition, we also remove the inverse Hessian approximation to verify its effect in reducing the time complexity. In practice, we use torch.linalg.solve function to compute the exact inverse matrix of the full Hessian instead of using the inverse Hessian approximation. Due to the memory limitation, we only conduct the experiment with MLP on the MNIST dataset. The results show that the inverse Hessian approximation brings 470 times speedup compared with computing the exact value of the inverse Hessian.

## 5.7. Sequential Unlearning

We conduct experiments on certified unlearning in a sequential setting to verify its feasibility in practice. In particular, we sequentially delete 10,000 training samples from a trained ResNet-18 model over the SVHN dataset in 10 iterations. Experimental results are shown in Figure 3. Note that each unlearning step can be seen as a single-step Newton update that reduces the loss value over the corresponding retain set. In the sequential setting, the estimation in each unlearning step reduces the loss value over the corresponding retain set. It is worth noting that the retained set in each step is a subset of the retained set in any previous step. Hence, the loss value over the retained set in the k -th unlearning step D r k is reduced in each previous unlearning step. Subsequently, the gradient norm ||∇L ( ˜ w k -1 , D r k ) || also decreases as the model parameters approach a local optimum, so does the approximation error bound according to Equation (11). As a result, in a sequential setting, we can still launch the certified unlearning method, while robustly maintaining the utility of the unlearned model.

## 5.8. Parameter Study

In this experiment, we discuss the tradeoff between certification budgets ( ε , δ ) and the utility of the unlearned model. According to Theorem 2.3, to achieve a tighter certification budget, we have to add a larger noise, which can also lead to utility degradation and limit the practical application of certified unlearning. To demonstrate the effects of the certification budgets ε and δ on the unlearned model utility, we record the micro F1-score of the unlearned model over the test set when adding Gaussian noises with different standard deviations. We repeat the experiment with different values of the local convex coefficient λ and present the results in Figure 4. We fix the budget δ = 0 1 . for Figure 4(a)



![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00920v2-figure-6da5ce51-e01b-4135-8ba9-d6bf0b2242d6.jpg)

















 



















 



(b) Error Bound

(c) Test F1-Score

Figure 3. Gradient norm, approximation error bound, and model utility after each unlearning step.

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00920v2-figure-3efad52a-11bd-4713-8d26-8e71c3734fd3.jpg)

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00920v2-figure-c552dea2-0e79-4b01-b060-c7d4e5fad27b.jpg)



2015), K-Means (Ginart et al., 2019), random forest (Brophy &amp; Lowd, 2021), deep neural networks (Bourtoule et al., 2021; Aldaghri et al., 2021; Kim &amp; Woo, 2022), and graph neural networks (Chen et al., 2022). Despite having desirable unlearning effectiveness, exact unlearning methods cannot scale to large stochastic models or tackle with batch unlearning settings (Nguyen et al., 2022).

δ

(b) Test F1- curve

Figure 4. The effect of local convex coefficient λ and certification budget ε and δ over the MLP backbone on MNIST.

and ε = 1 e 3 for Figure 4(b). From the experimental results, we can obtain that (1). The unlearned model utility will decrease as the certification budget becomes tighter. (2). Under a fixed certification budget, the model utility increases when increasing the value of the local convex coefficient λ . (3). When increasing the value of the local convex coefficient λ , the model utility becomes more sensitive in terms of the certification level. It is worth noting that the utility increase indicates a smaller noise added in the unlearning stage. A smaller noise under a fixed certification level further indicates a lower approximation error. Therefore, Figure 4 also verifies the effectiveness of local convex approximation in mitigating the approximation error bound. Although the certification budgets in Figure 4 cannot decrease to a very small value when maintaining a desirable utility, our certified unlearning outperforms most unlearning baselines in various unlearning metrics even with a relatively loose budget according to Table 1 and Table 2, which verifies the stringency of certified unlearning. Meanwhile, the potential to decrease the certification budget also necessitates further studies on tightening the approximation error bound under nonconvex neural models.

## 6. Related Works

## 6.1. Exact Unlearning

Exact unlearning is a straightforward method for machine unlearning. The idea of exact unlearning is to find efficient ways to retrain the original model from scratch. From the beginning of machine unlearning, exact unlearning has been widely studied for statistical query learning (Cao &amp; Yang,

## 6.2. Certified Unlearning

Certified unlearning was proposed based on the definition of differential privacy. The idea of certified unlearning is to find an approximation model similar to the retrained model in distribution by computationally efficient methods. Existing certified unlearning methods focus primarily on linear models (Guo et al., 2020; Izzo et al., 2021; Mahadevan &amp; Mathioudakis, 2021), general convex models (Ullah et al., 2021; Sekhari et al., 2021; Neel et al., 2021), Bayesian models (Nguyen et al., 2020), sum-product networks (Becker &amp; Liebig, 2022), and graph neural networks (Pan et al., 2023; Chien et al., 2023; Wu et al., 2023a;b; Dong et al., 2024). It is worth noting that most aforementioned certified unlearning methods are based on Newton update, i.e., influence function (Koh &amp; Liang, 2017), to estimate the retrained model. Some existing works (Mehta et al., 2022) took a tentative step towards certified unlearning for DNNs, relying on strong assumptions on the convexity of the objective.

## 7. Conclusion

Despite the extensive study of certified unlearning in many convex machine learning models, the application of certified unlearning in DNNs still poses challenges. In this paper, we proposed two simple techniques to extend certified unlearning to nonconvex objectives and incorporated an inverse Hessian approximation approach to improve efficiency. Regarding the real-world scenarios, we also provide the theoretical analysis of the certification under nonconvergence training and sequential unlearning settings. We conducted extensive empirical experiments to verify the efficacy of our proposed methods and the superiority of certified unlearning in efficiently deleting the information and protecting the privacy of unlearned data.











## Acknowledgements

This work is supported in part by the National Science Foundation under grants (IIS-2006844, IIS-2144209, IIS-2223769, CNS-2154962, CNS-2213700, and BCS2228534), the Commonwealth Cyber Initiative Awards under grants (VV-1Q23-007, HV-2Q23-003, and VV-1Q24011), the JP Morgan Chase Faculty Research Award, and the Cisco Faculty Research Award.

## Impact Statement

This paper extends the certification of machine unlearning to nonconvex, nonconvergence, and sequential settings in real-world scenarios. The goal of this work is to advance the field of Machine Learning. There are many potential societal consequences of our work, none of which we feel must be specifically highlighted here.

## References

Agarwal, N., Bullins, B., and Hazan, E. Second-order stochastic optimization for machine learning in linear time. arXiv preprint arXiv:1602.03943 , 2016.

Agarwal, N., Bullins, B., and Hazan, E. Second-order stochastic optimization for machine learning in linear time. The Journal of Machine Learning Research , pp. 4148-4187, 2017.

Aldaghri, N., Mahdavifar, H., and Beirami, A. Coded machine unlearning. IEEE Access , pp. 88137-88150, 2021.

Balle, B. and Wang, Y.-X. Improving the gaussian mechanism for differential privacy: Analytical calibration and optimal denoising. In International Conference on Machine Learning , pp. 394-403, 2018.

Basu, S., Pope, P., and Feizi, S. Influence functions in deep learning are fragile. In International Conference on Learning Representations , 2021.

Becker, A. and Liebig, T. Certified data removal in sumproduct networks. arXiv preprint arXiv:2210.01451 , 2022.

Bertsekas, D. P. Nonlinear programming. Journal of the Operational Research Society , pp. 334-334, 1997.

Bourtoule, L., Chandrasekaran, V., Choquette-Choo, C. A., Jia, H., Travers, A., Zhang, B., Lie, D., and Papernot, N. Machine unlearning. In 2021 IEEE Symposium on Security and Privacy (SP) , pp. 141-159, 2021.

Brophy, J. and Lowd, D. Machine unlearning for random forests. In International Conference on Machine Learning , pp. 1092-1104, 2021.

Cao, Y. and Yang, J. Towards making systems forget with machine unlearning. In 2015 IEEE symposium on security and privacy , pp. 463-480, 2015.

CCPA. https://oag.ca.gov/privacy/ccpa. 2018. URL https: //oag.ca.gov/privacy/ccpa .

Chen, M., Zhang, Z., Wang, T., Backes, M., Humbert, M., and Zhang, Y. When machine unlearning jeopardizes privacy. In Proceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security , pp. 896-911, 2021.

Chen, M., Zhang, Z., Wang, T., Backes, M., Humbert, M., and Zhang, Y. Graph unlearning. In Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security , pp. 499-513, 2022.

Chien, E., Pan, C., and Milenkovic, O. Efficient model updates for approximate unlearning of graph-structured data. In International Conference on Learning Representations , 2023.

Chundawat, V. S., Tarun, A. K., Mandal, M., and Kankanhalli, M. Can bad teaching induce forgetting? unlearning in deep networks using an incompetent teacher. In Proceedings of the AAAI Conference on Artificial Intelligence , volume 37, pp. 7210-7217, 2023.

Davis, D. and Drusvyatskiy, D. Stochastic model-based minimization of weakly convex functions. SIAM Journal on Optimization , 29(1):207-239, 2019.

Davis, D. and Grimmer, B. Proximally guided stochastic subgradient method for nonsmooth, nonconvex problems. SIAM Journal on Optimization , 29(3):1908-1930, 2019.

Dong, Y., Zhang, B., Lei, Z., Zou, N., and Li, J. Idea: A flexible framework of certified unlearning for graph neural networks. arXiv preprint arXiv:2407.19398 , 2024.

Dwork, C. Differential privacy. In Proceedings of the 33rd international conference on Automata, Languages and Programming-Volume Part II , pp. 1-12, 2006.

Dwork, C., Roth, A., et al. The algorithmic foundations of differential privacy. Foundations and Trends® in Theoretical Computer Science , pp. 211-407, 2014.

GDPR. https://gdpr-info.eu/. 2016. URL https:// gdpr-info.eu/ .

Ginart, A., Guan, M., Valiant, G., and Zou, J. Y. Making ai forget you: Data deletion in machine learning. Advances in neural information processing systems , 2019.

Golatkar, A., Achille, A., and Soatto, S. Eternal sunshine of the spotless net: Selective forgetting in deep networks. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition , pp. 9304-9312, 2020.

| Golatkar, A., Achille, A., Ravichandran, A., Polito, M., and Soatto, S. Mixed-privacy forgetting in deep networks. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition , pp. 792-801, 2021.        | Mercuri, S., Khraishi, R., Okhrati, R., Batra, D., Hamill, C., Ghasempour, T., and Nowlan, A. An introduction to machine unlearning. arXiv preprint arXiv:2209.00939 , 2022.                                                                                     |
|-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|
| Guo, C., Goldstein, T., Hannun, A., and Van Der Maaten, L. Certified data removal from machine learning models. In International Conference on Machine Learning , pp. 3832-3842, 2020.                                              | Neel, S., Roth, A., and Sharifi-Malvajerdi, S. Descent-to- delete: Gradient-based methods for machine unlearning. In Algorithmic Learning Theory , pp. 931-962, 2021.                                                                                            |
| He, K., Zhang, X., Ren, S., and Sun, J. Deep residual learn- ing for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition , pp. 770-778, 2016.                                       | Netzer, Y., Wang, T., Coates, A., Bissacco, A., Wu, B., and Ng, A. Y. Reading digits in natural images with unsupervised feature learning. 2011. Nguyen, Q. P., Low, B. K. H., and Jaillet, P. Variational                                                       |
| Izzo, Z., Smart, M. A., Chaudhuri, K., and Zou, J. Approx- imate data deletion from machine learning models. In International Conference on Artificial Intelligence and Statistics , pp. 2008-2016, 2021.                           | bayesian unlearning. Advances in Neural Information Processing Systems , 33:16025-16036, 2020. Nguyen, T. T., Huynh, T. T., Nguyen, P. L., Liew, A. W.-C., Yin, H., and Nguyen, Q. V. H. A survey of machine unlearning. arXiv preprint arXiv:2209.02299 , 2022. |
| Kim, J. and Woo, S. S. Efficient two-stage model retraining for machine unlearning. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition , pp. 4361-4369, 2022.                                     | Nocedal, J. and Wright, S. J. Numerical Optimization . Springer, 2006.                                                                                                                                                                                           |
| Kingma, D. P. and Ba, J. Adam: A method for stochastic optimization. In International Conference on Learning Representations , 2015.                                                                                                | Pan, C., Chien, E., and Milenkovic, O. Unlearning graph classifiers with limited data resources. In Proceedings of the ACM Web Conference 2023 , pp. 716-726, 2023.                                                                                              |
| Koh, P. W. and Liang, P. Understanding black-box predic- tions via influence functions. In International conference on machine learning , pp. 1885-1894, 2017.                                                                      | Paszke, A., Gross, S., Massa, F., Lerer, A., Bradbury, J., Chanan, G., Killeen, T., Lin, Z., Gimelshein, N., Antiga, L., et al. Pytorch: An imperative style, high-performance deep learning library. Advances in neural information                             |
| Krizhevsky, A., Hinton, G., et al. Learning multiple layers of features from tiny images. 2009.                                                                                                                                     | processing systems , 32, 2019. Sekhari, A., Acharya, J., Kamath, G., and Suresh, A. T. Re- member what you want to forget: Algorithms for machine                                                                                                                |
| Kurmanji, M., Triantafillou, P., Hayes, J., and Triantafillou, E. Towards unbounded machine unlearning. Advances in Neural Information Processing Systems , 36, 2023.                                                               | unlearning. Advances in Neural Information Processing Systems , pp. 18075-18086, 2021.                                                                                                                                                                           |
| LeCun, Y., Bottou, L., Bengio, Y., and Haffner, P. Gradient- based learning applied to document recognition. Proceed- ings of the IEEE , 86(11):2278-2324, 1998.                                                                    | Sommer, D. M., Song, L., Wagh, S., and Mittal, P. Athena: Probabilistic verification of machine unlearning. Proc. Privacy Enhancing Technol , 3:268-290, 2022.                                                                                                   |
| Liu, J., Ram, P., Yao, Y., Liu, G., Liu, Y., SHARMA, P., Liu, S., et al. Model sparsity can simplify machine unlearning. Advances in Neural Information Processing Systems , 36, 2023.                                              | Springenberg, J. T., Dosovitskiy, A., Brox, T., and Ried- miller, M. Striving for simplicity: The all convolutional net. In International Conference on Learning Represen- tations, Workshop Track Proceedings , 2015.                                           |
| Mahadevan, A. and Mathioudakis, M. Certifiable ma- chine unlearning for linear models. arXiv preprint arXiv:2106.15093 , 2021.                                                                                                      | Tarun, A. K., Chundawat, V. S., Mandal, M., and Kankan- halli, M. Fast yet effective machine unlearning. IEEE Transactions on Neural Networks and Learning Systems , 2023.                                                                                       |
| Mehta, R., Pal, S., Singh, V., and Ravi, S. N. Deep unlearn- ing via randomized conditionally independent hessians. In Proceedings of the IEEE/CVF Conference on Com- puter Vision and Pattern Recognition , pp. 10422-10431, 2022. | Thomee, B., Shamma, D. A., Friedland, G., Elizalde, B., Ni, K., Poland, D., Borth, D., and Li, L.-J. Yfcc100m: The new data in multimedia research. Communications of the ACM , pp. 64-73, 2016.                                                                 |

- Ullah, E., Mai, T., Rao, A., Rossi, R. A., and Arora, R. Machine unlearning via algorithmic stability. In Conference on Learning Theory , pp. 4126-4142, 2021.
- Warnecke, A., Pirch, L., Wressnegger, C., and Rieck, K. Machine unlearning of features and labels. In Network and Distributed System Security Symposium, NDSS , 2023.
- Wu, J., Yang, Y., Qian, Y., Sui, Y., Wang, X., and He, X. Gif: A general graph unlearning strategy via influence function. In Proceedings of the ACM Web Conference 2023 , pp. 651-661, 2023a.
- Wu, K., Shen, J., Ning, Y., Wang, T., and Wang, W. H. Certified edge unlearning for graph neural networks. In Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining , pp. 2606-2617, 2023b.
- Xu, H., Zhu*, T., Zhang, L., Zhou, W., and Yu, P. S. Machine unlearning: A survey. ACM Computing Surveys , 2023.
- Zhang, H., Nakamura, T., Isohara, T., and Sakurai, K. A review on machine unlearning. SN Computer Science , 2023.

## A. Proofs

## A.1. Proof of Proposition 2.2

Proof. Let the unlearning process be an identical map in terms of the model, i.e., U D D ( , u , A D ( )) = A D ( ) . Since A is a differentially private algorithm, we have ∀ T ⊆ H ,

$$\Pr ( \mathcal { A } ( \mathcal { D } ) \in \mathcal { T } ) \leq e ^ { \varepsilon } \Pr ( \mathcal { A } ( \mathcal { D } _ { u } ) \in \mathcal { T } ) + \delta.$$

Similarly, we also have ∀ T ⊆ H ,

$$\bar { \bar { \ } } ^ { \cdot } \quad \Pr ( \mathcal { A } ( \mathcal { D } _ { u } ) \in \mathcal { T } ) \leq e ^ { \varepsilon } \Pr ( \mathcal { A } ( \mathcal { D } ) \in \mathcal { T } ) + \delta.$$

According to Definition 2.1, A D ( ) is an ε -δ certified unlearned model under our defined unlearning process U .

## A.2. Proof of Theorem 2.3

Proof. Refer to the proof of Lemma 10 in Sekhari et al. (2021).

## A.3. Proof of Lemma 3.3

Proof. First, we have

$$\tilde { w } - \tilde { w } ^ { * } = w ^ { * } - H _ { w ^ { * } } ^ { - 1 } \nabla \mathcal { L } ( w ^ { * }, \mathcal { D } _ { r } ) - \tilde { w } ^ { * }.$$

Considering that ˜ w ∗ = argmin w ∈H L ( w , D r ) , we have ∇L ( ˜ w ∗ , D r ) = 0 . By substitute this equation into Equation (14) we have

$$\tilde { w } - \tilde { w } ^ { * } = w ^ { * } - \tilde { w } ^ { * } - H _ { w ^ { * } } ^ { - 1 } \left ( \nabla \mathcal { L } ( w ^ { * }, \mathcal { D } _ { r } ) - \nabla \mathcal { L } ( \tilde { w } ^ { * }, \mathcal { D } _ { r } ) \right ).$$

According to Assumption 3.2, the loss function L has the second-order derivative. Consequently, according to the fundamental theorem of calculus, we have

$$\nabla \mathcal { L } ( w ^ { * }, \mathcal { D } _ { r } ) - \nabla \mathcal { L } ( \tilde { w } ^ { * }, \mathcal { D } _ { r } ) = \int _ { 0 } ^ { 1 } H _ { w ^ { * } + t ( \tilde { w } ^ { * } - w ^ { * } ) } ( \tilde { w } ^ { * } - w ^ { * } ) d t.$$

By incorporate Equation (16) into Equation (15), we have

$$\text{v.p.v. } \text{v.p.v. } \text{v.p.v. } \text{v.p.v. } \text{v.p.v. } \text{v.p.v. } \text{v.p.v. } \text{v.p.v. } \text{v.p.v. } \text{v.p.v. } \text{v.p.v. } \text{v.p.v. } \text{v.p.v. } \text{v.p.v. } \text{v.p.v. } \text{v.p.v. } \text{v.p.v. } \text{v.p.v. } \text{v.p.v. } \text{v.p.v. } \text{v.p.v. } \\ \tilde { w } - \tilde { w } ^ { * } & = H _ { w ^ { * } } ^ { - 1 } \cdot \int _ { 0 } ^ { 1 } ( H _ { w ^ { * } } - H _ { w ^ { * } + t ( \tilde { w } ^ { * } - w ^ { * } ) } ( \tilde { w } ^ { * } - w ^ { * } ) d t. \\ \text{mute the norm of both side-and obtain the right hand side-are}$$

We compute the norm of both sides and obtain the right-hand side as

$$\sim \partial \, \cos \, \cos \, \cos \, \cos \, \sin \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \sin \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \sin \, \cos \, \cos \, \cos \, \cos \, \sin \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \tan \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \tan \, \cos \, \cos \, \cos \, \cos \, \sin \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \ cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \ cos \, \cos \, \cos \, \cos \, \cos \, \sin \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \ sin \, \cos \, \cos \cos \cos \cos \cos \cos \cos \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \.cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \,  \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \} \, d t. \\ \Lambda \, \text{$\sim} \, \text{$1$} \cdot \int_{0}^{1}(\Lambda_{w^{*} -1_{0} \cdot \cdot \int_{0}^{1}(\Lambda_{w^{*} -1_{0} \cdot \cdot \int_{0}^{1}(\Lambda_{w^{*} -1_{0} \cdot \cdot \int_{0}^{1}(\Lambda_{w^{*} -1_{0} \cdot \int_{0}^{1}(\Lambda_{w^{*} -1_{0} \cdot \int_{0}^{1}(\Lambda_{w^{*} -1_{0} \cdot \int_{0}^{1}(\Lambda_{w^{*} -1_{0} \cdot \int_{0}^{1}(\Lambda_{w^{*} -1_{0} \cdot \int_{0}^{1}(\Lambda_{w^{*} -1_{0} \cdot \int_{0}^{1}(\Lambda_{w^{*} -1_{0} \cdot \int_{0}^{1}(\Lambda_{w^{*} -1_{0} \cdot \int_{0}^{1}(\Lambda_{w^{*} -1_{0}} \cdot \int_{0}^{1}(\Lambda_{w^{*} -1_{0} \cdot \int_{0}^{1}(\Lambda_{w^{*} -1_{0} \cdot \int_{0}^{1}(\Lambda_{w^{*} -1_{0} \cdot \int_{0}^{1}(\Lambda_{w^{*} -1_{0} \cdot \int_{0}^{1}(\Lambda_{w^{*} -1_{0} \cdot \int_{0}^{1}(\Lambda_{w^{*} -1_{0} \cdot \int_{0}^{1}(\Lambda_{w^{*} -1_{0} \cdot \int_{0}^{1}(\Lambda_{w^{*} -1_{0 } \cdot \int_{0}^{1}(\Lambda_{w^{*} -1_{0} \cdot \int_{0}^{1}(\Lambda_{w^{*} -1_{0} \cdot \int_{0}^{1}(\Lambda_{w^{*} -1_{0} \cdot \int_{0}^{1}(\Lambda_{w^{*} -1_{0} \cdot \int_{0}^{1}(\Lambda_{w^{*} -1_{0} \cdot \int_{0}^{1}(\Lambda_{w^{*} -1_{0} \cdot \int_{0}^{1}(\Lambda_{w^{*} -1_{0} \cdot \int_{0}^{1}(\Lambda_{w^{*} -1_{0.0} \cdot \int_{0}^{1}(\Lambda_{w^{*} -1_{0} \cdot \int_{0}^{1}(\Lambda_{w^{*} -1_{0} \cdot \int_{0}^{1}(\Lambda_{w^{*} -1_{0} \cdot \int_{0}^{1}(\Lambda_{w^{*} -1_{0} \cdot \int_{0}^{1}(\Lambda_{w^{*} -1_{0} \cdot \int_{0}^{1}(\Lambda_{w^{*} -1_{0} \cdot \int_{0}^{1}(\Lambda_{w^{*} -1_{0} \cdot \int_{0}^{1}(\Lambda_{w^{*} -1_0.0)}(\Lambda_{w^{*} -1_{0} \cdot \int_{0}^{1}(\Lambda_{w^{*} -1_{0} \cdot \int_{0}^{1}(\Lambda_{w^{*} -1_{0} \cdot \int_{0}^{1}(\Lambda_{w^{*} -1_{0} \cdot \int_{0}^{1}(\Lambda_{w^{*} -1_{0} \cdot \int_{0}^{1}(\Lambda_{w^{*} -1_{0} \cdot \int_{0}^{1}(\Lambda_{w^{*} -1_{0} \cdot \int_{0}^{1}(\Lambda_{w^{*} -1_{0} \cdot \int_{0}^{1}}(\Lambda_{w^{*} -1_{0} \cdot \int_{0}^{1}(\Lambda_{w^{*} -1_{0} \cdot \int_{0}^{1}(\Lambda_{w^{*} -1_{0} \cdot \int_{0}^{1}(\Lambda_{w^{*} -1_{0} \cdot \int_{0}^{1}(\Lambda_{w^{*} -1_{0} \cdot \int_{0}^{1}(\Lambda_{w^{*} -1_{0} \cdot \int_{0}^{1}(\Lambda_{w^{*} -1_{0} \cdot \int_{0}^{1}(\Lambda_{w^{*} -1_{0} \cdot \int_{0}^{1 }(\Lambda_{w^{*} -1_{0} \cdot \int_{0}^{1}(\Lambda_{w^{*} -1_{0} \cdot \int_{0}^{1}(\Lambda_{w^{*} -1_{0} \cdot \int_{0}^{1}(\Lambda_{w^{*} -1_{0} \cdot \int_{0}^{1}(\Lambda_{w^{*} -1_{0} \cdot \int_{0}^{1}(\Lambda_{w^{*} -1_{0} \cdot \int_{0}^{1}(\Lambda_{w^{*} -1_{0} \cdot \int_{0}^{1}(\Lambda_{w^{*} -1_{0} \cdot \int_{0}^{1)}(\Lambda_{w^{*} -1_{0} \cdot \int_{0}^{1}(\Lambda_{w^{*} -1_{0} \cdot \int_{0}^{1}(\Lambda_{w^{*} -1_{0} \cdot \int_{0}^{1}(\Lambda_{w^{*} -1_{0} \cdot \int_{0}^{1}(\Lambda_{w^{*} -1_{0} \cdot \int_{0}^{1}(\Lambda_{w^{*} -1_{0} \cdot \int_{0}^{1}(\Lambda_{w^{*} -1_{0} \cdot \int_{0}^{1}(\Lambda_{w^{*} -1_{0} \cdot \int_{0}^{2}(\Lambda_{w^{*} -1_{0} \cdot \int_{0}^{1$$

According to Assumption 3.2, the loss function l has an M -Lipschitz Hessian. Hence, the loss function L also has an M -Lipschitz Hessian. Consequently, we have

$$\| H _ { w ^ { * } } - H _ { w ^ { * } + t ( \tilde { w } ^ { * } - w ^ { * } ) } \| \leq M t \| w ^ { * } - \tilde { w } ^ { * } \|.$$

Incorporating Equation (19) into Equation (18) leads to

$$\text{uation} \left ( 1 9 \right ) \text{ into Equation} \left ( 1 8 \right ) \text{ leads to} \\ & \quad \left \| H _ { w ^ { * } } ^ { - 1 } \cdot \int _ { 0 } ^ { 1 } ( H _ { w ^ { * } } - H _ { w ^ { * } + t ( \bar { w } ^ { * } - w ^ { * } ) } ) ( w ^ { * } - \bar { w } ^ { * } ) d t \right \| \\ \leq & \| H _ { w ^ { * } } ^ { - 1 } \| \cdot \int _ { 0 } ^ { 1 } M t \| w ^ { * } - \tilde { w } ^ { * } \| ^ { 2 } d t \\ = & \frac { M } { 2 } \| H _ { w ^ { * } } ^ { - 1 } \| \cdot \| w ^ { * } - \tilde { w } ^ { * } \| ^ { 2 }. \\ \text{f, we can incorporate Equation} \left ( 2 0 \right ) \text{ into Equation} \left ( 1 7 \right ) \text{ and let the norm} \text{ be the $\ell-2$ norm.}$$

To finish the proof, we can incorporate Equation (20) into Equation (17) and let the norm be the ℓ -2 norm.

## A.4. Proof of Theorem 3.4

Proof. Following the proof of Lemma 3.3, we have

$$\tilde { w } - \tilde { w } ^ { * } = w ^ { * } - \tilde { w } ^ { * } - ( H _ { w ^ { * } } + \lambda I ) ^ { - 1 } ( \nabla \mathcal { L } ( w ^ { * }, \mathcal { D } _ { r } ) - \nabla \mathcal { L } ( \tilde { w } ^ { * }, \mathcal { D } _ { r } ) ) \,.$$

Based on Assumption 3.2, Equation (16) still holds. Incorporating Equation (16) into Equation (21) leads to

$$\tilde { w } - \tilde { w } ^ { * } = ( H _ { w ^ { * } } + \lambda I ) ^ { - 1 } \cdot \int _ { 0 } ^ { 1 } ( H _ { w ^ { * } } + \lambda I - H _ { w ^ { * } + t ( \tilde { w } ^ { * } - w ^ { * } ) } ) ( w ^ { * } - \tilde { w } ^ { * } ) d t.$$

Then, we compute the norm of both sides and obtain the right-hand side as

$$\cdot, \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \colon \\ & \left \| ( H _ { w ^ { * } } + \lambda I ) ^ { - 1 } \cdot \int _ { 0 } ^ { 1 } ( H _ { w ^ { * } } + \lambda I - H _ { w ^ { * } + t ( \tilde { w } ^ { * } - w ^ { * } ) } ) ( w ^ { * } - \tilde { w } ^ { * } ) d t \right \| \\ \leq & \| ( H _ { w ^ { * } } + \lambda I ) ^ { - 1 } \| \cdot \int _ { 0 } ^ { 1 } \left ( \lambda + \| H _ { w ^ { * } } - H _ { w ^ { * } + t ( \tilde { w } ^ { * } - w ^ { * } ) } \| \right ) \cdot \| w ^ { * } - \tilde { w } ^ { * } \| d t. \\ \text{with to a condition } 3 \, 2 \, \text{ Enation } 1 0 \cup \text{ still hold the } R v \text{ in-ordering Enation } 1 0 \cup \text{int} \, \text{Enation } 1 0 \cup \text{int} \, \text{Enation } 1 0 \cup \text{int} \, \text{2} \cup \text{two hours}$$

According to Assumption 3.2, Equation (19) still holds. By incorporating Equation (19) into Equation (23), we have

$$\ln \text{ to Assumption } 3. 2, \text{ Equation } ( 1 9 ) \text{ still holds. By incorporating Equation } ( 1 9 ) \text{ into Equation } ( 2 3 ), \text{ we have} \\ & \quad \left \| ( H _ { w ^ { * } } + \lambda I ) ^ { - 1 } \cdot \int _ { 0 } ^ { 1 } ( H _ { w ^ { * } } + \lambda I - H _ { w ^ { * } + t ( \bar { w } ^ { * } - w ^ { * } ) } ) ( w ^ { * } - \bar { w } ^ { * } ) d t \right \| \\ \leq & \| ( H _ { w ^ { * } } + \lambda I ) ^ { - 1 } \| \cdot \int _ { 0 } ^ { 1 } M t \| w ^ { * } - \bar { w } ^ { * } \| ^ { 2 } + \lambda \| w ^ { * } - \bar { w } ^ { * } \| d t \\ = & \left ( \frac { M } { 2 } \| w ^ { * } - \bar { w } ^ { * } \| + \lambda \right ) \| ( H _ { w ^ { * } } + \lambda I ) ^ { - 1 } \| \cdot \| w ^ { * } - \bar { w } ^ { * } \|. \\ \text{ inverse Hessian term. We then have}$$

For the inverse Hessian term, We then have

$$\text{verse Hessian term, We then have} \\ \| ( H _ { w ^ { * } } + \lambda I ) ^ { - 1 } \| _ { 2 } & = \sqrt { \lambda _ { m a x } [ ( ( H _ { w ^ { * } } + \lambda I ) ^ { - 1 } ) ^ { \top } ( H _ { w ^ { * } } + \lambda I ) ^ { - 1 } ] } \\ & = \sqrt { \lambda _ { m a x } [ ( ( H _ { w ^ { * } } + \lambda I ) ( H _ { w ^ { * } } + \lambda I ) ^ { \top } ) ^ { - 1 } ] } \\ & = \frac { 1 } { \sqrt { \lambda _ { m i n } [ ( H _ { w ^ { * } } + \lambda I ) ( H _ { w ^ { * } } + \lambda I ) ^ { \top } ] } } \\ & = \frac { 1 } { \lambda _ { m i n } [ H _ { w ^ { * } } + \lambda I ] } \\ & = \frac { 1 } { \lambda + \lambda _ { m i n } [ H _ { w ^ { * } } ] }, \\ \inf _ { 1 } [ H _ { w ^ { * } } ] \text{ and } \lambda _ { m a x } [ H _ { w ^ { * } } ] \text{ denote the minimum and maximum eigenvalue of the Hessian } H _ { w ^ { * } }. \text{ In addition, we} \\ \dots ^ { * } \| \geq \sim \dots ^ { * } \| \dots ^ { * } \| \geq \dots ^ { * } \|. \dots$$

where λ min [ H w ∗ ] and λ max [ H w ∗ ] denote the minimum and maximum eigenvalue of the Hessian H w ∗ . In addition, we also have ∥ w ∗ ∥ 2 ≤ C and ∥ ˜ w ∗ ∥ 2 ≤ C . Consequently, we have

$$\| w ^ { * } - \tilde { w } ^ { * } \| _ { 2 } \leq 2 C.$$

To finish the proof, we can incorporate Equation (25), Equation (26), and Equation (24) into Equation (22) and let the norm be the ℓ -2 norm.

## A.5. Proof of Proposition 3.5

Proof. We compute the expectation value for both sides of Equation (8). Considering { H 1 ,λ , . . . , H s,λ } are i.i.d. samples from the Hessian H w ∗ + λ I , we have

$$\mathfrak { n } \mathcal { H } _ { w ^ { * } } + \lambda I, \, \text{we have} \\ \mathbb { E } [ \tilde { H } _ { t, \lambda } ^ { - 1 } ] = & \mathbb { E } \left [ I + \left ( I - \frac { H _ { t, \lambda } } { H } \right ) \tilde { H } _ { t - 1, \lambda } ^ { - 1 } \right ] \\ = & I + \mathbb { E } [ \tilde { H } _ { t - 1, \lambda } ^ { - 1 } ] - \frac { 1 } { H } \mathbb { E } [ H _ { t, \lambda } \tilde { H } _ { t - 1, \lambda } ^ { - 1 } ] \\ = & I + \mathbb { E } [ \tilde { H } _ { t - 1, \lambda } ^ { - 1 } ] - \frac { 1 } { H } \mathbb { E } [ H _ { w ^ { * } } + \lambda I ] \mathbb { E } [ \tilde { H } _ { t - 1, \lambda } ^ { - 1 } ]. \\ \dots$$

Let s →∞ , the limit E [ ˜ H -1 ∞ ,λ ] = lim t →∞ E [ ˜ H -1 t,λ ] exists as ∥ E [ H t,λ ] H ∥ ≤ 1 . We then compute the limit for both sides of Equation (27) and have

$$\mathbb { E } [ \tilde { H } _ { \infty, \lambda } ^ { - 1 } ] = & \, I + \mathbb { E } [ \tilde { H } _ { \infty, \lambda } ^ { - 1 } ] - \frac { 1 } { H } \mathbb { E } [ H _ { w } + \lambda I ] \mathbb { E } [ \tilde { H } _ { \infty, \lambda } ^ { - 1 } ].$$

Consequently, we have

$$\mathbb { E } \left [ \frac { \tilde { H } _ { \infty, \lambda } ^ { - 1 } } { H } \right ] = & \mathbb { E } [ ( H _ { w ^ { * } } + \lambda I ) ^ { - 1 } ].$$

Hence, we have proved that ˜ H -1 s,λ H is an asymptotic unbiased estimator of the inverse Hessian ( H w ∗ + λ I ) -1 .

## A.6. Proof of Theorem 3.6

Proof. Following the proof of Lemma 3.3, we have

$$\text{Proof. Following the proof of Lemma 3.3, we have} \\ \tilde { w } - \tilde { w } ^ { * } & = w ^ { * } - \tilde { w } ^ { * } + \frac { n _ { u } } { ( n - n _ { u } ) H } \tilde { H } ^ { - 1 } _ { s, \lambda } \nabla \mathcal { L } ( w ^ { * }, \mathcal { D } _ { u } ) \\ & = w ^ { * } - \tilde { w } ^ { * } - \frac { \tilde { H } ^ { - 1 } _ { s, \lambda } } { H } \nabla \mathcal { L } ( w ^ { * }, \mathcal { D } _ { r } ) \\ & = w ^ { * } - \tilde { w } ^ { * } - \frac { \tilde { H } ^ { - 1 } _ { s, \lambda } } { H } ( \nabla \mathcal { L } ( w ^ { * }, \mathcal { D } _ { r } ) - \nabla \mathcal { L } ( \tilde { w } ^ { * }, \mathcal { D } _ { r } ) ) \\ & = w ^ { * } - \tilde { w } ^ { * } - \left ( ( H _ { w } ^ { * } + \lambda I ) ^ { - 1 } + \frac { \tilde { H } ^ { - 1 } _ { s, \lambda } } { H } - ( H _ { w } ^ { * } + \lambda I ) ^ { - 1 } \right ) \cdot ( \nabla \mathcal { L } ( w ^ { * }, \mathcal { D } _ { r } ) - \nabla \mathcal { L } ( \tilde { w } ^ { * }, \mathcal { D } _ { r } ) ) \,. \\ \text{The right-hand side of Equation (30) can be divided into two parts, (1). \ w ^ { * } - \tilde { w } ^ { * } - ( H _ { w } ^ { * } + \lambda I ) ^ { - 1 } ( \nabla \mathcal { L } ( w ^ { * }, \mathcal { D } _ { r } ) -$$

The right-hand side of Equation (30) can be divided into two parts, (1). w ∗ -˜ w ∗ -( H w ∗ + λ I ) -1 ( ∇L ( w ∗ , D r ) -∇L ( ˜ w ∗ , D r )) and (2). (( H w ∗ + λ I ) -1 -˜ H -1 s,λ /H )( ∇L ( w ∗ , D r ) -∇L ( ˜ w ∗ , D r )) . We compute the norm for both sides of Eq. (30) and the norm of the right-hand side is smaller than the summation of the norm of the part (1) and the norm of the part (2). To find an upper bound of ∥ ˜ w -˜ w ∗ ∥ , we can find upper bounds for the norm of part (1) and the norm of part (2). According to Theorem 3.4, the norm of part (1) is bounded by 2 C MC ( + ) λ λ + λ min . Next, our goal is to find the upper bound of the norm of part (2). In particular, the norm of part (2) is smaller than the product ∥ ( H w ∗ + λ I ) -1 -˜ H -1 s,λ /H ∥ · ∥∇L ( w ∗ , D r ) -∇L ( ˜ w ∗ , D r ) ∥ . Refer to Lemma 3.6 (Agarwal et al., 2016), we have

$$\left \| ( H _ { w ^ { * } } + \lambda I ) ^ { - 1 } - \frac { \tilde { H } _ { s, \lambda } ^ { - 1 } } { H } \right \| > \left ( \frac { 1 6 \sqrt { \ln d / \rho } } { \lambda + \lambda _ { m i n } } + \frac { 1 } { 1 6 } \right ),$$

with a probability smaller than ρ . According to Assumption 3.1, we also have

$$\| \nabla \mathcal { L } ( w ^ { * }, \mathcal { D } _ { r } ) - \nabla \mathcal { L } ( \tilde { w } ^ { * }, \mathcal { D } _ { r } ) \| \leq L \| w ^ { * } - \tilde { w } ^ { * } \| \leq 2 L C.$$

Then, we incorporate Equation (31) and Equation (32) and obtain the upper bound of the norm of part (2): ( 32 √ ln d/ρ λ + λ min + 1 8 ) LC . To finish the proof, we can combine the upper bounds for the norm of part (1) and the norm of part (2) and then obtain Equation (9).

## A.7. Proof of Proposition 4.1

Proof. Following the proof of Lemma 3.3, we have

$$P r o o f \text{: Following the proof of Lemma } 3. 3, \, \text{we have} \\ \tilde { w } - \tilde { w } ^ { * } & = w ^ { * } - \tilde { w } ^ { * } + \frac { n _ { u } } { ( n - n _ { u } ) H } \tilde { H } _ { s, \lambda } ^ { - 1 } \nabla \mathcal { L } ( w ^ { * }, \mathcal { D } _ { u } ) \\ & = w ^ { * } - \tilde { w } ^ { * } - \frac { \tilde { H } _ { s, \lambda } ^ { - 1 } } { H } \nabla \mathcal { L } ( w ^ { * }, \mathcal { D } _ { r } ) \\ & = w ^ { * } - \tilde { w } ^ { * } - \frac { \tilde { H } _ { s, \lambda } ^ { - 1 } } { H } \left ( \nabla \mathcal { L } ( w ^ { * }, \mathcal { D } _ { r } ) - \nabla \mathcal { L } ( \tilde { w } ^ { * }, \mathcal { D } _ { r } ) \right ) - \frac { \tilde { H } _ { s, \lambda } ^ { - 1 } } { H } \nabla \mathcal { L } ( \tilde { w } ^ { * }, \mathcal { D } _ { r } ).$$

We compute the norm for both sides of Equation (33) and have

$$\| \tilde { w } - \tilde { w } ^ { * } \| \leq \left \| w ^ { * } - \tilde { w } ^ { * } - \frac { \tilde { H } _ { s, \lambda } ^ { - 1 } } { H } ( \nabla \mathcal { L } ( w ^ { * }, \mathcal { D } _ { r } ) - \nabla \mathcal { L } ( \tilde { w } ^ { * }, \mathcal { D } _ { r } ) ) \right \| + \left \| \frac { \tilde { H } _ { s, \lambda } ^ { - 1 } } { H } \nabla \mathcal { L } ( \tilde { w } ^ { * }, \mathcal { D } _ { r } ) \right \|.$$

∗

To find an upper bound of ∥ ˜ w -˜ w ∥ , we can find an upper bound for each norm value on the right-hand side. According to the proof of Theorem 3.6, we have ∥ ∥ ∥ ∥ w ∗ -˜ w ∗ -˜ H -1 s,λ H ( ∇L ( w ∗ , D r ) -∇L ( ˜ w ∗ , D r )) ∥ ∥ ∥ ∥ is upper bounded by 2 C MC ( + ) λ λ + λ min + ( 32 √ ln d/ρ λ + λ min + 1 8 ) LC with a probability larger than 1 -ρ . Next, our goal is to find the upper bound for ∥ ∥ ∥ ∥ ˜ H -1 s,λ H ∇L ( ˜ w ∗ , D r ) ∥ ∥ ∥ ∥ .

In particular, we have

$$\left \| \frac { \tilde { H } _ { s, \lambda } ^ { - 1 } } { H } \nabla \mathcal { L } ( \tilde { w } ^ { * }, \mathcal { D } _ { r } ) \right \| & \leq \| ( H _ { w ^ { * } } + \lambda I ) ^ { - 1 } \nabla \mathcal { L } ( \tilde { w } ^ { * }, \mathcal { D } _ { r } ) \| + \left \| ( \frac { \tilde { H } _ { s, \lambda } ^ { - 1 } } { H } - ( H _ { w ^ { * } } + \lambda I ) ^ { - 1 } ) \nabla \mathcal { L } ( \tilde { w } ^ { * }, \mathcal { D } _ { r } ) \right \| \\ & \leq \| ( H _ { w ^ { * } } + \lambda I ) ^ { - 1 } \| \cdot \| \nabla \mathcal { L } ( \tilde { w } ^ { * }, \mathcal { D } _ { r } ) \| + \left \| \frac { \tilde { H } _ { s, \lambda } ^ { - 1 } } { H } - ( H _ { w ^ { * } } + \lambda I ) ^ { - 1 } \right \| \cdot \| \nabla \mathcal { L } ( \tilde { w } ^ { * }, \mathcal { D } _ { r } ) \|.$$

According to Equation (25), we have ∥ ( H w ∗ + λ I ) -1 ∥ ≤ 1 λ -∥ H w ∗ ∥ . According to Equation (31), we have ∥ ( H w ∗ + λ I ) -1 -˜ H -1 s,λ /H ∥ &gt; ( 16 √ ln d/ρ λ + λ min + 1 16 ) with a probability smaller than ρ . Wealso have ∥∇L ( w ∗ , D ∥ ∥∇L ) , ( ˜ w ∗ , D r ) ∥ ≤ G . By incorporating these results into Equation (35) we have

$$\left \| \frac { \tilde { H } _ { s, \lambda } ^ { - 1 } } { H } \nabla \mathcal { L } ( \tilde { w } ^ { * }, \mathcal { D } _ { r } ) \right \| \leq \left ( \frac { 1 } { \lambda - \| H _ { w ^ { * } } \| } + \frac { 1 6 \sqrt { \ln d / \rho } } { \lambda + \lambda _ { m i n } } + \frac { 1 } { 1 6 } \right ) G.$$

To finish the proof, we can incorporate Equation (36) and results of Theorem 3.6 into Equation (34).

## A.8. Proof of Proposition 4.2

Proof.

$$\rho _ { \text{roof} } \text{ Follow the proof of Proposition 4.1.}$$

Intuitively, the error bound will increase as the unlearning algorithm runs for multiple steps since the second term of the error bound ∥ w ∗ -˜ w ∗ ∥ 2 2 in Lemma 3.3 tends to increase. However, we consider the worst-case bound when tackling this term ∥ w ∥ 2 ≤ C →∥ w ∗ -˜ w ∗ ∥ 2 ≤ 2 C , which is independent of the unlearning steps. As a result, the error bound remains unchanged regardless of how large the proportion of the unlearned set is. In addition, it means that the error bound can be tightened if we add further assumptions on the distance of the two minimal points ∥ w ∗ -˜ w ∗ ∥ 2 .

## B. Comparison Between Convex and Nonconvex Objectives

In this section, we focus on the results shown in Theorem 3.4. Our results proposed in this paper do not require the objective to be convex. However, if we further assume the objective to be convex, we can obtain a tighter approximation upper bound as follows.

Proposition B.1. Let w ∗ = argmin ∥ w ∥ ≤ 2 C L ( w , D ) and ˜ w ∗ = argmin ∥ w ∥ ≤ 2 C L ( w , D r ) . Let ˜ w = w ∗ -H -1 w ∗ ∇L ( w ∗ , D r ) be an approximation of ˜ w ∗ . Consider Assumption 3.2 and assume l ( w x , ) to be K -strongly convex with respect to w , then we have

$$\| \tilde { w } - \tilde { w } ^ { * } \| _ { 2 } \leq \frac { 2 M C ^ { 2 } } { K }.$$

Proof. As the loss function l is K -strongly convex, the loss function L is also K -strongly convex. Consequently, we have ∥ H w ∗ ∥ 2 ≥ K and ∥ H -1 w ∗ ∥ 2 ≤ 1 K . In addition, Equation (26) still holds. By incorporating the upper bound ∥ H -1 w ∗ ∥ 2 ≤ 1 K and Equation (26) into Lemma 3.3, we can obtain Equation (37).

Table 4. The hyperparameter settings of original models on the corresponding datasets.

| Hyperparameter   | MLP     | AllCNN   | ResNet   |
|------------------|---------|----------|----------|
| learning rate    | 1 e - 3 | 1 e - 3  | 1 e - 3  |
| weight decay     | 5 e - 4 | 5 e - 4  | 5 e - 4  |
| epochs           | 50      | 50       | 50       |
| dropout          | 0.5     | 0.5      | 0.5      |
| batch size       | 128     | 128      | 128      |
| param bound C    | 10      | 20       | 20       |

Considering the similarity between λ + λ min in Equation (7) and K in Equation (37) (both measuring the objective's convexity), we use λ + λ min to replace K in Equation (37) and derive the approximation error bound for convex models as 2 MC 2 λ + λ min . Comparing the result with Equation (37), we find that the Newton update method has a lower approximation error bound for convex models versus nonconvex models. This result highlights the fact that our method works under both convex and nonconvex objectives . In particular, our approximation obtains a tighter upper bound for strongly convex objectives.

## C. Bounded Model Parameters is also Necessary for Convex Models

In this section, we demonstrate our observation that previous works (Sekhari et al., 2021) on certified unlearning for convex models implicitly rely on the requirement of bounded model parameters ∥ w ∥ 2 ≤ C , which means our proposed constraint on model parameters is also suitable for convex models.

Previous works (Sekhari et al., 2021) studied the certified unlearning and its generalization for convex models. In particular, they jointly assume the objective to be L -Lipschitz continuous and M -strongly convex in the proof of certification. Next, we demonstrate that these two assumptions jointly indicate ∥ w ∥ 2 ≤ C . Let w 1 , w 2 be two models in the hypothesis space, and L be the loss function. Based on the strong convexity, we have

$$\| \nabla \mathcal { L } ( w _ { 1 } ) - \nabla \mathcal { L } ( w _ { 2 } ) \| \geq M \| w _ { 1 } - w _ { 2 } \|.$$

In addition, according to the Lipschitz continuity, we have

$$\| \nabla \mathcal { L } ( w ) \| \leq L,$$

for any w in the hypothesis space. Incorporate Eq. (39) into Eq. (38) and we have

$$2 L \geq \| \nabla \mathcal { L } ( w _ { 1 } ) - \nabla \mathcal { L } ( w _ { 2 } ) \| \geq M \| w _ { 1 } - w _ { 2 } \|.$$

Consequently, we have ∥ w 1 -w 2 ∥ ≤ 2 L M for any w 1 and w 2 in the hypothesis space. The certification requires any two models in the hypothesis space to have a bounded distance, which is a non-trivial condition. Luckily, by letting C = L M , our constraint on model parameters ∥ w ∥ ≤ C satisfy the condition for certification. Hence, we find that the assumptions in previous works naturally necessitate a constraint of bounded norm to the model parameters. In this paper, we exploit projected gradient descent to actively restrict the norm of model parameters for bounding the approximation error. We argue that this technique is also necessary for fulfilling the assumptions made in previous works to derive the certification for convex models.

## D. Implementation

We implemented all experiments in the PyTorch (Paszke et al., 2019) package and exploited Adam (Kingma &amp; Ba, 2015) as the optimizer for training. For the training of original models, we exploited Adam as the optimizer. We set the learning rate as 1 e -3 , the weight decay parameter as 5 e -4 , and the training epochs number as 50 . We ran all experiments on an Nvidia RTX A6000 GPU. All experiments are conducted based on three real-world datasets: MNIST (LeCun et al., 1998), CIFAR-10 (Krizhevsky et al., 2009), and SVHN (Netzer et al., 2011). All datasets are publicly accessible (MNIST with GNU General Public License, CIFAR-10 with MIT License, and SVHN with CC BY-NC License). We reported the average value and the standard deviation of the numerical results under three different random seeds. For the relearn time in Table 2, we directly report the rounded mean value without the standard deviation as the value of the epoch number is supposed to be an integer. The unlearned data is selected randomly from the training set. Detailed hyperparameter settings of the original models are presented in Table 4. The hyperparameter settings of unlearning baselines are shown as follows.

- · Retrain from scratch : size of unlearned set: 1,000.
- · Fine tune : size of unlearned set: 1,000; learning rate: 1 e -3 ; epochs: 1.
- · Negative gradient : size of unlearned set: 1,000; learning rate: 1 e -4 ; epochs: 1.
- · Fisher forgetting : size of unlearned set: 1,000; α : 1 e -6 for MLP, 1 e -8 for AllCNN and ResNet.
- · L-CODEC : size of unlearned set: 1,000; number of perturbations: 25; Hessian type: Sekhari; ε : 100; δ : 0.1; ℓ -2 regularization: 5 e -4 .
- · Certified unlearning : size of unlearned set: 1,000; number of recursion s : 1,000; standard deviation σ : 1 e -2 for MLP, 1 e -3 for AllCNN and ResNet; continuity coefficients L : 1, M : 1; minimal eigenvalue of Hessian λ min : 0; convex coefficient λ : 1 for MLP, 200 for AllCNN, 2,000 for ResNet; Hessian scale H : 10 for MLP, 20,000 for AllCNN, 50,000 for ResNet.

The detailed meanings of hyperparameters in unlearning baselines can be found in the original papers. For λ , since finding a practical upper bound of the norm of Hessian can be intractable for real-world tasks, we follow most previous works (Koh &amp; Liang, 2017; Wu et al., 2023a;b) to set it as a hyperparameter which can be chosen flexibly to adapt to different scenarios. In addition, we compute the norm of the Hessian in the case of MLP over MNIST. To reduce the time complexity, we use the Hessian with respect to a single random mini-batch of D r as an unbiased estimation of the full Hessian. The results of the mean value and the variance of the norm of the stochastic Hessian (under 10 different random seeds) is 12 11 . ± 0 63 . , which falls into the range of λ in Table 3. When λ &lt; 12 11 . , the computed error bound is still valid (from Table 3, as the value of λ decreases, the computed error bound increases correspondingly, indicating that a smaller choice of λ can still lead to a valid but larger error bound). In this case, the certification requires adding a larger noise to hide the (overestimated) remaining information of the unlearned data. Different from λ , the values of L M , , and λ min only affect the value of the approximation error bound ∆ . In practice, following previous works (Guo et al., 2020), we first determine the variance of noise σ (to preserve the model utility after adding noise) and then obtain the certification level ε and δ which can be achieved. Hence, the certification holds for any choices of L M , , and λ min , but the calculated certification level can be imprecise in some cases. To weaken the dependency of the approximation error bound on the Lipschitz constants, we leave more general theoretical results as future works. It is also worth noting that the values of certification budgets ε and δ are flexible in our experiments. In particular, we fixed the noise and the budgets ε and δ can be tuned in a range for specific needs (we have ε ∈ [1 e , 2 5 e 3 ] when δ ∈ [0 1 . , 1] , and the decrease of one can lead to the increase of the other). Detailed results regarding the certification budgets are shown in the parameter study in Section 5.8. In addition, we list some key packages in Python required for implementing certified unlearning as follows.

- · python == 3.9.16
- · torch == 1.12.1
- · torchvision == 0.13.1
- · numpy == 1.24.3
- · scikit-learn == 1.2.2
- · scipy == 1.10.1

## E. Additional Experiments

## E.1. Effect of Bounded Model Parameters

In our experiments, we adopt PGD during the training of the original model and the retrained model. PGD is conducted solely for ensuring the strictness of our theoretical results while trying not to affect the model utility. To achieve this, we deliberately choose the value of C in the constraint | w | 2 &lt; C to make PGD have little impact on the model utility. After verifying with experiments, we find that C = 10 for MLP over MNIST, C = 20 for CNN over CIFAR-10, and C = 20 for ResNet over SVHN can be a desirable choice. In this experiment, we record and report the utility metrics (micro F1-score over the test set) of the original model and retrained model without conducting PGD in Table 5. Compared with the corresponding results in Table 1, we can verify that our adopted PGD modification with a carefully chosen constraint does not affect the model utility distinctly.

## Towards Certified Unlearning for Deep Neural Networks

| Table 5. The micro F1-score of the original model and the retrained model without using PGD.   | MLP &MNIST   | CNN &CIFAR-10   | ResNet &SVHN   |
|------------------------------------------------------------------------------------------------|--------------|-----------------|----------------|
| Original                                                                                       | 97.03 ± 0.25 | 83.16 ± 0.62    | 93.92 ± 0.19   |
| Retrain                                                                                        | 96.80 ± 0.20 | 83.39 ± 0.59    | 93.80 ± 0.31   |

Table 6. Comparison of accuracy among three advanced unlearning baselines over three popular DNNs across three real-world datasets. We record the micro F1-score of the predictions on the unlearned set D u , retained set D r , and test set D t .

| Method      | MLP &MNIST   | MLP &MNIST   | MLP &MNIST   | AllCNN &CIFAR-10   | AllCNN &CIFAR-10   | AllCNN &CIFAR-10   | ResNet18 &SVHN   | ResNet18 &SVHN   | ResNet18 &SVHN   |
|-------------|--------------|--------------|--------------|--------------------|--------------------|--------------------|------------------|------------------|------------------|
| Method      | F1 on D u    | F1 on D r    | F1 on D t    | F1 on D u          | F1 on D r          | F1 on D t          | F1 on D u        | F1 on D r        | F1 on D t        |
| SCRUB       | 98.10 ± 0.60 | 98.12 ± 0.05 | 97.25 ± 0.04 | 90.73 ± 2.63       | 96.83 ± 0.82       | 86.31 ± 0.31       | 94.07 ± 0.38     | 96.09 ± 1.25     | 94.02 ± 0.38     |
| NegGrad+    | 97.43 ± 0.60 | 98.92 ± 0.01 | 97.68 ± 0.07 | 80.70 ± 8.79       | 96.58 ± 0.47       | 86.05 ± 1.52       | 91.03 ± 1.32     | 97.58 ± 0.45     | 95.07 ± 0.12     |
| ℓ -1 Sparse | 97.83 ± 0.47 | 98.40 ± 0.19 | 97.24 ± 0.12 | 87.17 ± 2.80       | 92.26 ± 0.37       | 83.99 ± 0.32       | 94.33 ± 0.61     | 95.55 ± 0.33     | 93.67 ± 0.16     |

## E.2. Comparison with Advanced Baselines

To strengthen the soundness of certified unlearning, we supply three more advanced baselines for approximate unlearning: SCRUB (Kurmanji et al., 2023), NegGrad+ (Liu et al., 2023), and ℓ -1 Sparse (Liu et al., 2023). For SCRUB, we adopt the provided hyperparameter settings in the code base (small scale for MLP and large scale for CNN and ResNet). For NegGrad+, we tune the hyperparameter manually and find the optimal setting α =0.95, epoch=1, and learning rate=1e-4. For ℓ -1 Sparse (Liu et al., 2023), the proposed framework consists of two parts, pruning and unlearning. The pruning step is orthogonal to all other unlearning baselines. Hence, we drop the pruning step for all baselines to ensure a fair comparison (similar to the case that we use PGD during training for all baselines). It is worth noting that other than pruning, ℓ -1 sparse unlearning proposes a novel unlearning technique as well (adding an ℓ -1 penalty to the objective). As a result, we include ℓ -1 sparse unlearning without pruning in the additional results shown in Table 6. Comparing the additional results with Table 1, we can observe that our proposed certified method still has the most desirable and robust performance. Compared with the negative gradient method, NegGrad+ improves the utility over the retain and test sets but still has a lower performance on the forget set. With the ℓ -1 penalty, the ℓ -1 sparse unlearning has a distinct improvement compared with vanilla fine-tuning.
Binchi Zhang Yushun Dong Tianhao Wang Jundong Li
Towards Certified Unlearning for Deep Neural Networks
In the field of machine unlearning, certified unlearning has been extensively
studied in convex machine learning models due to its high efficiency and strong
theoretical guarantees. However, its application to deep neural networks
(DNNs), known for their highly nonconvex nature, still poses challenges. To
bridge the gap between certified unlearning and DNNs, we propose several simple
techniques to extend certified unlearning methods to nonconvex objectives. To
reduce the time complexity, we develop an efficient computation method by
inverse Hessian approximation without compromising certification guarantees. In
addition, we extend our discussion of certification to nonconvergence training
and sequential unlearning, considering that real-world users can send
unlearning requests at different time points. Extensive experiments on three
real-world datasets demonstrate the efficacy of our method and the advantages
of certified unlearning in DNNs.