1 Introduction↩︎

[ht]
\centering
\setlength\tabcolsep{5.5pt}
  \caption{\textbf{Our main contributions}, \(d\) is the dimensionality of the model parameters, and \(n\) is the total size of the dataset.}
  \label{Table321:32contribution}
  \begin{tabular}{ccccc}
\centering 
    Algorithm     &  Pre-computation time
  &Storage
& Unlearning time (per sample) & Description\\
    \midrule
    \cite{DBLP:conf/nips/SekhariAKS21}& 
$\mathcal{O}(nd^2)$ &$\mathcal{O}(d^2)$
&$\mathcal{O}(d^3)$ & Hessian based method \\
   \cite{DBLP:conf/nips/SuriyakumarW22} & 
$\mathcal{O}(d^3+nd^2)$ &$\mathcal{O}(d^2)$
&$\mathcal{O}(d^2)$  & Hessian based method \\ 
   Proposed method& $\mathcal{O}(nd)$ &$\mathcal{O}(nd)$&$\mathcal{O}(d)$ & Hessian free method  \\
    \bottomrule
  \end{tabular}

Recent data protection regulations, e.g. General Data Protection Regulation, aim to safeguard individual privacy and include provisions such as the Right to be Forgotten. This regulation mandates the data controller shall erase the personal data without undue delay when the data providers request to delete them. Within the context of the right to be forgotten, data owners can request the removal of their personal data’s contribution from the trained models. This can be achieved through the concept of machine unlearning, where the model provider erases the specific data that pertains to the data owner’s personal information.

A straightforward unlearning algorithm is to retrain the model from scratch, which is however impractical as it comes with unaffordable monetary and time costs. It is especially challenging in time-sensitive applications such as fraud detection or online learning, as neglecting timeliness may have a detrimental impact on system performance and responsiveness. To this end, prior efforts [1], [2] have been designing and evaluating unlearning by metrics including efficiency, measured by runtime, and efficacy, measured by the similarity to the retrained model. However, attaining a model entirely identical to the one achieved through retraining for an unlearning method represents a notably demanding criterion. Hence, inspired by differential privacy, [3] introduced a relaxed definition, in anticipation of ensuring the output distribution of the unlearning algorithm is indistinguishable from that of the retraining. Building upon this framework, diverse unlearning methodologies, e.g., [4]–[6], have been devised.

Online unlearning algorithms deal with deletion requests that come in an online manner [7], [8]. The key idea is to proactively pre-compute and store certain data statistics prior to the deletion requests, to achieve computational and memory efficiency while maintaining reasonable performance. These studies reveal that for models that approximate the minimization of convex and sufficiently smooth empirical minimization objectives, unlearning can be efficiently executed through a Newton style step, facilitated by the pre-storing Hessian. While these works have demonstrated the effectiveness of second-order method to approximate the retrained model, they do have a few fundamental limitations. First, the existing unlearning algorithms require explicit pre-storage of the Hessian matrix (or its inverse) and therefore are expensive to implement. This forms a stark contrast to many training algorithms leveraging Hessian-free solvers. Second, they are not applicable to most deep neural networks due to the need of convexity in the objective function. More concretely, we can ask, how can we design a method to efficiently pre-compute unlearning statistics with lenient assumption?

In this paper, we address these fundamental questions and introduce an efficient and private unlearning approach that departs significantly from prior works. First, we analyze the difference between the learned and the retrained models after forgetting each sample via recollecting the trajectory discrepancy. Subsequently, we demonstrate that these distinctions can be approximated and characterized through an affine stochastic recursion. In this work, we refer to this approximation technique as the approximator. Moreover, we employ the Hessian Vector Product (HVP) to improve efficiency in computing these approximators, thereby reducing the running time. We also employed gradient clipping to bound the errors introduced by approximation. Finally, building upon the aforementioned analysis and techniques, we propose an efficient algorithm that includes pre-computed and pre-stored statistics. When deletion requests arrive, machine unlearning is rapidly achieved by adding the corresponding approximators. Our algorithm requires minimal modifications to the training process, enabling fast unlearning with distinctive computational advantages. Equally importantly, we ensure forgetting by deleting the approximator of the corresponding sample post-unlearning, rather than storing such statistics.

We summarize our contributions below and in Table [Table321:32contribution].

• More Lenient Assumption, Less Cost. We propose a recollection approximator via analyzing the impact of each sample on the training trajectory. Our proposed approximator allows us to leverage the HVP technique, which is not feasible with existing algorithms. It thus achieves a lower-complexity pre-computation of individual data statistics. (Section 3).

• Computationally Efficient Algorithm. We then propose a Hessian-free algorithm for online unlearning which is near-instantaneous as it only requires a vector addition operation. Additionally, this algorithm provides a theoretical efficacy guarantee, showing that our approach ourperforms previous methods. (Section 4).

• Exceptional Performance. We experimentally validate our algorithm with a wide range of metrics. Our experiments elucidate the shortcomings of prior algorithms on non-convex settings. In contrast, our results show that the proposed method surpasses prior works, especially in unlearning time, our algorithm is only on the millisecond level to forget per sample. (Section 5).

1.1 Related Work↩︎

Machine unlearning can be traced back to [9] and their work defines the notion of Exact Unlearning, demanding that the models obtained through retraining and unlearning exhibit complete consistency. Similar methods, such as [10]–[15], train submodels based on different dataset partitions and aggregation strategies. Approximate Unlearning, e.g., [2], [16]–[25] seeks to relax definition and minimize the impact of forgetting data to an acceptable level to tradeoff for computational efficiency, reduced storage costs, and flexibility. Therefore, [3] introduced a relaxed definition, which aims to make the unlearned model indistinguishable from retrained model.

In this approximate definition, [7], [8], [26] align with our approach which lies in pre-computing statistics of data which extracts more precise second-order information from Hessian, and use these ‘recollections’ to forget data. Specifically, (1) Newton Step (NS). [8] proposes, through the precomputation and storage of the Hessian offline, to achieve forgetting upon the arrival of a forgetting request using a Newton step. However, this method necessitates strong assumptions, e.g. the objective function is required to be strongly convex. Its unlearning time, involving \(\mathcal{O}(d^3)\), becomes nearly impractical for over-parameterized deep neural networks. (2) Infinitesimal Jacknife (IJ). [7], [26] extends the work of NS, attaining strong convexity through a non-smooth regularizer by leveraging the IJ. Moreover, by trading the offline computation time to inverse the Hessian, the unlearning time is reduced to \(\mathcal{O}(d^2)\). However, the basic issues still exist, i.e., the overly strong assumptions of convexity and the difficulty of applying to over-parameterized deep models. On the contrary, as indicated in Table [Table321:32contribution], our approach evades the curse of model parameters dimensionality. Moreover, previous works necessitate maintaining the Hessian information to address the ongoing deletion requests, which poses the risk of violating the right to be forgotten and entails user privacy. Instead, our method goes beyond ‘recollecting to forget’ by also ‘forgetting the recollections’.

2 Problem Formulation↩︎

2.1 Learning↩︎

Let \(\ell(\mathbf{w}; z)\) be the loss function for a given parameter \(\mathbf{w} \! \in \! \mathbb{R}^d\!\) and on instance \(z\) over an instance space \(\mathcal{Z}\). Learning can be expressed as the population risk minimization problem: \[\min_{\mathbf{w}}\quad F(\mathbf{w}):=\mathbb{E}_{z \sim \mathcal{D}}[\ell(\mathbf{w}; z)]. \label{population32risk}\tag{1}\] Addressing this problem directly is challenging, as the probability distribution \(\mathcal{D}\) is usually unknown. For a finite dataset \(\mathcal{S}= \{z_i\}_{i=1}^n\) with \(n\) samples, one often solves the following empirical risk minimization problem: \[\min_{\mathbf{w}}\quad F_{\mathcal{S}}(\mathbf{w}):=\frac{1}{n}\sum_{i=1}^n \ell(\mathbf{w}; z_i). \label{2-1}\tag{2}\] The stochastic gradient descent (SGD) has been widely adopted to solve the problem (2 ). Specifically, for an initial model, we iteratively move in the direction with stepsize \(\eta\) of the negative gradient, and the one step update rule is: \[\mathbf{w}_{e, b+1} \leftarrow \mathbf{w}_{e, b}-\frac{\eta_{e,b}}{|\mathcal{B}_{e,b}|} \sum_{i \in \mathcal{B}_{e,b}} \nabla \ell \left(\mathbf{w}_{e, b};z_i\right), \label{2-2}\tag{3}\] for the index of epoch \(e \in \{0, ..., E\}\) and the index of batch \(b \in \{0, ..., B\}\). Here, \(\mathcal{B}_{e,b}\) denotes the dataset that contains the data sampled in the \(e\)-th epoch’s \(b\)-th update, and \(|\mathcal{B}_{e,b}|\) is the size of \(\mathcal{B}_{e,b}\), where \(|\mathcal{B}|\) is the maximum batch size.

2.2 Unlearning↩︎

Consider a scenario where a user requests to remove a forgetting dataset \(U\!\!=\!{\{u_j\}}_{j=1}^m \! \subseteq \! \mathcal{S}\). To unlearn \(U\), retraining from scratch is considered a naive unlearning method, which aims to minimize \(F_{\mathcal{S} \backslash U}(\mathbf{w})\). Specifically, since each data sample takes place only in one (mini-)batch per epoch, we define the data point \(u_j\) in \(U\) to be sampled in \(\mathcal{B}_{e,b(u_j)}\) during the \(e\)-th epoch’s \(b(u_j)\)-th batch update in the learning process, where \(b(u_j)\) represents the batch update index when \(u_j\) is sampled. Due to the removal of sample \(u_j\), the batch \(\mathcal{B}_{e,b(u_j)}\) is reduced to \(\mathcal{B}_{e,b(u_j)} \backslash \{u_j\}\). In accordance with the linear scaling rule discussed in [27], i.e., in order to effectively leverage batch sizes, one has to adjust the stepsize in tandem with the batch size. The retraining stepsize thus is concurrently scaled to \(\eta_{e,b(u_j)} \frac{| \mathcal{B}_{e,b(u_j)} \backslash \{u_j\}|}{|\mathcal{B}_{e,b(u_j)}|}\). Thus, the retraining update rule in \(e\)-th epoch is given by, \[\mathbf{w}_{e,b+1}^{-U} \leftarrow \mathbf{w}_{e,b}^{-U}-\frac{\eta_{e,b}}{|\mathcal{B}_{e,b}|} \sum_{i \in \mathcal{B}_{e,b} } \nabla \ell (\mathbf{w}_{e,b}^{-U};z_i). \label{2-3}\tag{4}\] Specifically, for the data point \(u_j\) sampled into \(\mathcal{B}_{e,b}\) during \(e\)-th epoch’s \(b(u_j)\)-th update, we have the following update: \[\!\! \mathbf{w}_{e,b(u_j)+1}^{-U}\!\!\! \leftarrow \! \mathbf{w}_{e,b(u_j)}^{-U}\! -\frac{\eta_{e,b(u_j)}}{|\mathcal{B}_{e,b(u_j)}|} \!\! \sum_{i \in \mathcal{B}_{e,b(u_j)} \backslash \{u_j\} } \!\!\!\!\!\!\!\!\! \nabla \ell (\mathbf{w}_{e,b(u_j)}^{-U};z_i). \label{2-4}\tag{5}\]

To avoid the unaffordable costs incurred by retraining, approximate unlearning algorithms aim to approximate the retrained model through limited updates on the learned model \(\mathbf{w}_{e, b+1}\). Our goal is to ensure the indistinguishability between the outputs of the unlearning algorithm and retraining algorithm. Therefore, we consider the notion of unlearning defined in [8].

3 Main Theoretical Results↩︎

Before detailing our analysis, let us informally motivate our main method. Specifically, we focus on studying the discrepancy between the learning and the retraining model by analyzing the impact of each sample on the update trajectory. Our main observation is that the difference between the retraining and learning models, analyzed through SGD recursion, can be described by an affine stochastic recursion.

Unlearning a single data sample. We start with designing an approximator for a single sample (i.e., \(U\!=\! \{u\}\)) on the model of training updates (the learning update and retraining update), by considering the difference between the learning model in 3 and the retraining model obtained without the knowledge of \(u\) in 4 . In particular, we consider the following two cases of model updates in the \(e\)-th epoch.

Case 1 (\(u\) not in \(\mathcal{B}_{e,b}\)): The difference between retraining and learning updates is \[\begin{align} \mathbf{w}_{e,b+1}^{-u} &-\mathbf{w}_{e,b+1} = \mathbf{w}_{e,b}^{-u}-\mathbf{w}_{e,b} \\ &-\frac{\eta_{e,b}}{|\mathcal{B}_{e,b}|}\!\!\sum_{i \in \mathcal{B}_{e,b} } \!\!\!\! \Big(\nabla \ell (\mathbf{w}_{e,b}^{-u};z_i)\! -\!\nabla \ell (\mathbf{w}_{e,b};z_i) \Big). \end{align} \label{3-1}\tag{6}\] From the Taylor expansion of \(\nabla \ell (\mathbf{w}_{e,b};z_i)\), we have \(\nabla \ell (\mathbf{w}_{e,b}^{-u};z_i) = \nabla \ell (\mathbf{w}_{e,b};z_i)+ \nabla^2 \ell (\mathbf{w}_{e,b};z_i) (\mathbf{w}_{e,b}^{-u} -\mathbf{w}_{e,b} )\) \(+ { o(\mathbf{w}_{e,b}^{-u}-\mathbf{w}_{e,b} )}.\) Let \(\mathbf{H}_{e,b} \!\!= \!\! \sum_{i \in \mathcal{B}_{e,b} } \!\!\!\! \nabla^2 \ell (\mathbf{w}_{e,b};z_i)\) denote the Hessian during the \(e\)-th epoch’s \(b\)-th update, we can then approximate the SGD recursion 6 as \[\mathbf{w}_{e,b+1}^{-u} -\mathbf{w}_{e,b+1} \approx \Big(\mathbf{I}- \frac{\eta_{e,b}}{|\mathcal{B}_{e,b}|}\mathbf{H}_{e,b}\Big)(\mathbf{w}_{e,b}^{-u}-\mathbf{w}_{e,b}). \label{3-3}\tag{7}\] Case 2 (\(u\) in \(\mathcal{B}_{e, b(u)}\)): The difference in this case is: \[\begin{align} & \mathbf{w}_{e,b(u)+1}^{-u}- \mathbf{w}_{e,b(u)+1}\approx \underbrace{ \frac{\eta_{e,b(u)}}{|\mathcal{B}_{e,b(u)}|} \nabla \ell (\mathbf{w}_{e,b(u)};u)}_{\text{Approximate impact of u in epoch \textit{e}}} \\ & + \underbrace{\Big(\mathbf{I} - \frac{\eta_{e,b(u)}}{|\mathcal{B}_{e,b(u)}|} \mathbf{H}_{e,b(u)}\Big)(\mathbf{w}_{e,b(u)}^{-u} - \mathbf{w}_{e,b(u)})}_{\text{Approximate impact of u in previous epoches}}, \label{3-3461} \end{align}\tag{8}\] where \(\mathbf{I}\) denotes identity matrix of appropriate size. Combining the observations in Cases 1 and 2, we now define the recollection matrix \(\mathbf{M}_{e,b(u)}\), backtracking the overall difference between the retrained and the learned models: \[\! \mathbf{M}_{e,b(u)}= \frac{\eta_{e,b(u)}}{|\mathcal{B}_{e,b(u)}|} \prod^E_{k=e}\prod_{b=b(u)+1}^{B-1}\Big(\mathbf{I}\! - \! \frac{\eta_{k,b}}{|\mathcal{B}_{k,b}|} \mathbf{H}_{k,b}\Big), \label{Definiton:32M}\tag{9}\] and affine stochastic recursion approximator \(\mathbf{a}_{E,B}^{-u}\) as \[\begin{align} \mathbf{a}_{E,B}^{-u}&:=\sum_{e=0}^E\mathbf{M}_{e,b(u)} \nabla \ell (\mathbf{w}_{e,b(u)};u ). \label{ASR} \end{align}\tag{10}\] We will see that \(\mathbf{a}_{E,B}^{-u}\) can approximate the impact of sample \(u\) on the training trajectory as follows, given by \[\begin{align} \mathbf{w}_{E,B}^{-u} &-\mathbf{w}_{E,B} \approx \mathbf{a}_{E,B}^{-u}, \end{align}\] That is, a simple vector addition to model \(\mathbf{w}_{E,B}\) can obtain an approximate retrained model for forgetting the sample \(u\). We define \(\Delta_{E,B}^{-u}\) as the approximation error, given by¹ \[\begin{align} \Delta^{-u}_{E,B}:= \mathbf{w}_{E,B}^{-u} -\mathbf{w}_{E,B} -\mathbf{a}_{E,B}^{-u}. \label{3-4} \end{align}\tag{11}\]

Our designed approximator in 10 enables us to exploit the Hessian vector product (HVP) technique [29] to compute it without explicitly computing the Hessian. When computing the product of the Hessian matrix and an arbitrary vector for the deep neural networks, the HVP technique first obtains gradients during the first backpropagation, multiplying the gradients with the vector, and then performing backpropagation again. This results in a time complexity of \(\mathcal{O}(d)\). We note that the existing second-order methods require to proactively store a Hessian matrix [7], [8], [26]. It is thus unable to deploy the HVP in their settings.

We will analyze the approximation error based on the spectral radius \(\rho\) of recollection matrix \(\mathbf{M}_{e,b(u)}\) which governs the difference between the retrained model and the original learned model \(\mathbf{w}_{E,B}^{-U}-\mathbf{w}_{E,B}\) in Section 4.

Unlearning a set of data samples. Furthermore, when it comes to forgetting a set of data samples, we have that

This elucidates that by storing the impact of updates for each data point, nearly instantaneous data removal can be achieved through a series of simple vector additions.

4 Proposed Method↩︎

In this section, we analyze the properties of the approximator \(\mathbf{a}_{E,B}^{-u}\) and the approximation error \(\Delta_{E,B}^{-u}\), which followed by the introduction of our proposed online unlearning algorithm. We finally present a detailed convergence and complexity analysis of the proposed method. The detailed proof can be found in Appendix 7.

4.1 Approximation Error Analysis↩︎

Gradient clipping is a technique widely adopted to achieve favorable performances in the deep networks training, by ensuring gradient norms not excessively large [30]. We further show that the gradient clipping with geometrically decaying stepsizes also facilitates us to derive an upper bound for the approximation error in the following:

To furthermore analyze the approximation error in 11 , we first introduce the following lemma:

Therefore, combining 10 , Lemma 1 and Lemma 2, we have the following approximation error bound:

Intuitively, Theorem 2 shows that through stochastic matrix recursions of 7 and 8 , the approximation error terms \(o(\mathbf{w}_{e,b}^{-u} \!\!-\!\! \mathbf{w}_{e,b})\) of the previous rounds are scaled by subsequent matrices \(\mathbf{M}_{e,b}\), and generate a new remainder term in this round, which is a polynomial multiplies geometric progression. Specifically, if the step size is small enough such that \(\rho \!<\!1\), the series converges, and as \(T \!\! \rightarrow \! \infty\), the approximation error approaches 0.

4.2 Online Unlearning Algorithm Design↩︎

Based on the above methods and the analysis of Theorem 2, we propose an memory and computationally efficient unlearning scheme in Algorithm 1. To the best of our knowledge, our approach is currently one of the most efficient, as it only requires a single vector addition by utilizing offline computed unlearning statistics. From a theoretical perspective, our designed method has strong interpretability and theoretical performance guarantees as well.

We present our approach in Algorithm 1. In Stage , we bound approximation error through gradient clipping, which is benefit for the optimization process [31]. In Stage , we compute the unlearning statistics vector \(\mathbf{a}_{E,B}^{-u}\) for each sample \(u\), exploiting the HVP technique to reduce computational complexity. The deletion request triggers Stage , in which only a single vector addition with introduced noise ensures the indistinguishably of \((\epsilon,\delta)\)-unlearning guarantee in Definition 1. Moreover, unlike previous works that requires retaining privacy-sensitive statistics to handle subsequent forgetting requests, our approach eliminates the need to retain statistics post-unlearning. Finally, while our approach does not require accessing any datasets in stage , we can enhance the robustness of our algorithm through a simple fine-tuning strategy if we can still access the remaining dataset. Specifically, this involves training on a small number of epochs with the remaining dataset, and then adding the corresponding approximators during this period to the original approximators. The detailed repairing strategy is deferred to Appendix 9.2.

4.3 Convergence Analysis↩︎

To discuss the performance guarantee of our proposed method, we further analyze the generalization capability. We first give a convergence of the excess risk defined in 1 and then we provide an asymptotic analysis for our method.

We use the following assumptions which are similar to [7] to establish convergence bound:

Here, we perform an asymptotic analysis for Theorem 3. Specifically, the result of our proposed method is expected to converge to \(\mathcal{O}(\frac{4L^2}{\lambda(n-m)})\) as \(T\) approaches infinity. It is noteworthy that, under these conditions and \(n \!\! \gg \!m\), our proposed approximator outperforms the performance of previous methods [7], [8] which are greater than \(\mathcal{O}( \frac{4L^2}{\lambda(n-m)})\). Furthermore, to measure the maximum number of samples to be forgotten while still ensuring good excess risk guarantees, we analyzed our method’s deletion capacity proposed by [8]. To save space, we defer to Appendix 9.1.

4.4 Comparison to Existing Approaches↩︎

We give a brief overview of previous methods that employed the related (pre-storing statistics) strategies to ours.
Newton Step (NS). [8] proposed an efficient forgetting method by pre-storing the Hessian \(\sum_{i=1}^n \nabla^2 \ell (\mathbf{w}_{E,B}; z_i)\). When a request arrives to forget \(m\) samples \(U\), obtaining a unlearned model \(\mathbf{w}^{-U}_{E,B}\) by adding the approximator \(\mathbf{a}^{-U}_{\text{NS}}\) to original learned model \(\mathbf{w}_{E,B}\). \[\begin{align} \mathbf{a}^{-U}_{\text{NS}} =& \frac{1}{n-m} \mathbf{H}_{\text{NS}}^{-1}\sum_{i \in U} \nabla \ell (\mathbf{w}_{E,B}; z_i),\\ \!\! \!\! \mathbf{H}_{\text{NS}}\!\! =\! \frac{1}{n\!-\!m} & \! \Big( \! \sum_{i=1}^n\! \nabla^2 \ell (\mathbf{w}_{E,B};\! z_i)\!\!-\!\!\sum_{i \in U}\! \nabla^2 \ell (\mathbf{w}_{E,B};\! z_i)\! \Big).\! \end{align}\] Infinitesimal Jacknife (IJ). [7] extends the work of NS by employing the IJ, and the main difference lies in the strategy of pre-computing and storing the inverse Hessian \((\sum_{i=1}^n \nabla^2 \ell (\mathbf{w}_{E,B}; z_i))^{-1}\), thereby trading computation time to reduce unlearning time. When a sample \(u\) requests to be forgotten, it enables unlearning by adding the approximator \(\mathbf{a}^{-u}_{\text{IJ}}\) to the learned model \(\mathbf{w}_{E,B}\). \[\begin{align} \mathbf{a}^{-u}_{\text{IJ}} & = \frac{1}{n} \mathbf{H}_{\text{IJ}}^{-1} \nabla \ell (\mathbf{w}_{E,B}; u), \\ \mathbf{H}_{\text{IJ}} & =\frac{1}{n} \sum_{i=1}^n \nabla^2 \ell (\mathbf{w}_{E,B}; z_i). \end{align}\] Comparison of Pre-Computation. First, for a single data point \(u\), Algorithm 1 entails computing the HVP of the gradient vectors \(\nabla \ell (\mathbf{w}_{e,b};u)\) \(T\) times, which requires \(\mathcal{O}(Td)\) running time. To compute the approximators \(\mathbf{a}^{-u}_{\text{Ours}}\) for all \(n\) samples, the computation steps are performed \(n\) times, resulting in a total running time of \(\mathcal{O}(nTd)\). Our method is highly efficient when dealing with overparameterized deep models, especially when \(d \gg n\). This is because computing the full Hessian \(\sum_{i=1}^n \nabla^2 \ell (\mathbf{w}_{E,B}; z_i)\) for NS requires \(\mathcal{O}(nd^2)\) running time, and computing and inverting the full Hessian \(\mathbf{H}^{-1}_{\text{IJ}}\) for IJ requires \(\mathcal{O}(d^3+nd^2)\) running time.

Comparison of Storage. Algorithm 1 involves storing a vector of model parameter size for \(n\) data, requiring the storage of \(\mathcal{O}(nd)\). This is significantly lower than the overhead introduced by storing matrices for NS and IJ, which is \(\mathcal{O}(d^2)\), when the dataset size \(n\) is lower than the dimension \(d\) of model parameters².

Comparison of Unlearning Computation. When a forgetting request with \(m\) data to be forgotten arrives, Algorithm 1 utilizes precomputed and prestored approximators to achieve forgetting, requiring a simple vector addition that takes \(\mathcal{O}(md)\) time. For NS, it requires computing and inverting a different Hessian that depends on the user requesting the deletion. This necessitates substantial computational overhead of \(\mathcal{O}(d^3+md^2+md)\) each time a deletion request arrives. Although IJ reduces this to \(\mathcal{O}(md^2+md)\), it is still not as efficient compared to our method.

5 Experiments↩︎

We conduct experiments to answer these questions:

• RQ1: Approximation Errors. How good the proposed approximator in 10 (Section 3) accurately capture the disparity between the retrained and learned models under both convex and non-convex setting?

• RQ2: Model Similarity. Does the unlearned model in Algorithm 1 (Section 4) perform similarly to the retrained model?

• RQ3: Practical Applications. How do these methods perform across different models and datasets?

To answer the three research questions, we devised the following experimental components: verification and application. Verification experiments are centered on evaluating the disparity between the unlearned models and the retrained models, across both convex and non-convex settings. Application experiments are geared towards evaluating the performance of different unlearning algorithms with a specific focus on determining the effectiveness, convergence, pre-computation, and unlearning runtime of these methods. Due to the space limit, we present the more results to Appendix 8, focusing solely on comparative experiments.

5.1 Verification Experiments↩︎

Our primary objective is to validate the differences between the proposed approximator \(\mathbf{a}^{-U}_{\text{Ours}}\) in 11 and the actual \(\mathbf{w}_{E,B}^{-U} - \mathbf{w}_{E,B}\). We approach the evaluation from two perspectives: distance and correlation. Specifically, we use the \(L_2\) norm metric \(\|\mathbf{w}_{E,B}^{-U} - \mathbf{w}_{E,B} - \mathbf{a}^{-U}_{\text{Ours}}\|\) to measure the distance of the approximation error. A smaller distance metric indicates a closer approximation of the unlearned model to the retrained model. Additionally, we utilize the Pearson [33] and Spearman [34] coefficient to assess the correlation between \(\mathbf{a}^{-U}_{\text{Ours}}\) and \(\mathbf{w}_{E,B}^{-U} - \mathbf{w}_{E,B}\) by mapping them from high-dimensional space to scalar loss values, i.e., the approximate loss change \(\ell (\mathbf{w}_{E, B} + \mathbf{a}^{-U}_{\text{Ours}}; U) - \ell (\mathbf{w}_{E, B} ; U)\) and the actual loss change \(\ell (\mathbf{w}^{-U}_{E, B} ; U) - \ell (\mathbf{w}_{E, B} ; U)\) on the forgetting dataset \(U\). Intuitively, the resulting correlation scores, ranging from -1 to 1, offer insights into the level of correlation between our methods’ unlearned model and the retrained model concerning the performance on the forgetting dataset \(U\).

Configurations: we conduct experiments in both convex and non-convex scenarios. Specifically, we trained a multinomial Logistic Regression (LR) with total parameters \(d=7850\) and a simple convolutional neural network (CNN) with total parameters \(d=21840\) on MNIST dataset with 1,000 data samples for handwriting digit classification. We apply a cross-entropy loss function and the inclusion of an \(L_2\) regularization coefficient of \(10^{-6}\) to ensure that the loss function of LR is strongly convex. For LR, training was performed for 100 epochs with stepsize of 0.05. For CNN, training was carried out for 20 epochs with stepsize of 0.05 and a batch size of 64. Given these configurations mentioned above, we separately assessed the distance and correlation between our approximators \(\mathbf{a}^{-U}_{\text{Ours}}\), \(\mathbf{a}^{-U}_{\text{NS}}\), \(\mathbf{a}^{-U}_{\text{IJ}}\) at deletion rates in the set {1%, 5%, 10%, 15%, 20%, 25%, 30%}. Following the suggestion in [35], a damping factor of 0.01 is added to the Hessian matrix to ensure its invertibility when implementing NS and IJ. In addition, for the sake of clear visualizations, we use the minimum and maximum values as error bars.

In the context of convex setting models, as shown in Fig. 2 (a), our approach surpasses previous works. First, by distance evaluation, the approximation error \(\|\mathbf{w}_{E,B}^{-U} - \mathbf{w}_{E,B} - \mathbf{a}^{-U}\|\) of the proposed method is lower than that of the previous NS and IJ works. At a deletion rate of 30%, our approximation error is 0.171638, slightly lower than that of IJ and NS, which have errors of 0.178244 and 0.178246, respectively. Despite the results being close in convex scenarios, our method does not necessitate strong assumptions similar to those employed by IJ and NS, i.e., when a model has not fully converged to the optimal values, the Hessian computed by IJ and NS may have negative eigenvalues, leading to its non-invertibility. On the contrary, our approach involves fewer assumptions and incurs less approximation error in the convex non-convergent setting. Second, in assessing the loss change for the forgotten dataset \(U\), our proposed method more accurately captures the changes in actual \(\ell (\mathbf{w}^{-U}_{E, B} ; U)-\ell (\mathbf{w}_{E, B} ; U)\). In particular, when removing 30% of the samples, the proposed method maintains a high correlation, with Pearson and Spearman being 0.96 and 0.95, respectively. We conducted all experiments with 7 random seeds to obtain average results.

In the context of non-convex setting, as illustrated in Fig. 2 (b), our approximator demonstrates superior performance, exhibiting less dependency on random variations compared to NS and IJ. The observed outcomes for NS and IJ are consistent with prior research [35], [36], where these methods display substantial random behavior, resulting in a non-significant correlation with retraining across different deletion rates. When 30% of the samples are removed, our proposed method maintains a lower approximation error of 0.96, surpassing the performance of IJ and NS. In contrast to IJ and NS which are far from the actual values in non-convex settings, our proposed methods achieve Spearman and Pearson correlation coefficients of 0.80 and 0.74, respectively, accurately capturing actual loss changes. Additionally, in Fig. 3, we intuitively provide insights into the reasons for the failure of prior works in non-convex settings. Specifically, we investigated the norm of approximate parameter change \(\|\mathbf{a}^{-U}\|\) and the norm of exact parameter change \(\|\mathbf{w}_{E,B}^{-U} - \mathbf{w}_{E,B}\|\) across different selection of the forgetting sample. We observed that, NS and IJ depend on the selection of the forgetting data, i.e., they can approximate actual changes well for partial data points while generating huge approximation errors for others, as illustrated in Fig. 3. This dependency on the data selection leads to failures in Fig. 2. On the contrary, our approach is not impacted by the selection of forgetting data, and can effectively approximate the actual norm of parameters changes.

5.2 Application Experiments↩︎

Furthermore, we evaluate the performance in real-world applications. Our simulations are conducted from two perspectives: runtime and utility. Specifically, run-time focuses on the time spent precomputing unlearning statistics and the speedup of the unlearning algorithm compared to the retraining algorithm. Furthermore, we evaluate the utility by the test accuracy of the unlearned model to ensure that generalization performance is not compromised, and the values in parentheses represent the difference in test accuracy compared to the retrained model.

Configurations: we evaluate our approach performance on different datasets with 20% data to be forgotten: (1) we train a LR and simple CNN on MNIST which have setups identical to the aforementioned experiments. We further simulated on FMNIST with 4,000 data using CNN and LeNet with total 61,706 parameters. The training was conducted for 30 epochs with stepsize of 0.5 and a batch size of 256. (2) Moreover, we assessed our method on non-pretrained ResNet18 [37] with 1,000 data for the CelebA dataset [38] for gender prediction. Training was performed for 10 epochs with stepsize of 0.05 and batch size of 32. In this scenario, we have not evaluated NS and IJ due to the out of memory for storing the Hessian.

Application experiment results show that our proposed method exhibits efficient computation and performs well in realistic environments. Table 1 demonstrates that when each forgetting request contains only one piece of data and a total of 20% of the data was forgotten, the proposed algorithm outperforms other baselines by a significant margin. Specifically, our approach achieves a small computational and storage overhead while maintaining high performance in both convex and non-convex setting. In Fig. 3, we explore batch-wise processing of 200 data points for forgetting, achieving highly efficient forgetting at the millisecond level compared to retraining on ResNet 18 for CelebA. It is important to highlight the challenges associated with evaluating the prior studies NS and IJ. This is primarily due to their high complexity requirements and the more restrictive assumptions made. Hence, in order to further evaluate our experimental results on larger models and datasets, we instead use the following baselines, lacking theoretical indistinguishability guarantees, as described and set up similarly in [25], which we defer the evaluation in the Appendix 8.2.

6 Conclusion↩︎

In this work, we proposed a novel online machine unlearning method that can achieve low-complexity and near-instantaneous unlearning. Specifically, we introduced an approximator based on affine stochastic recursion to characterize the trajectory discrepancy between the learned and retrained models of each forgotten sample. Based on this approximator, we proposed a near-instantaneous Hessian-free algorithm, employing HVP and gradient clipping techniques to mitigate the computation time and bound the approximation errors, respectively. We theoretically showed that our proposed method can reduce the pre-computation time, storage, and unlearning time (per sample) to \(\mathcal{O}(nd)\), \(\mathcal{O}(nd)\), \(\mathcal{O}(d)\), respectively. Experimental results validate that our proposed method benefits machine unlearning with reduced computation and storage costs and improved accuracy.

Impact Statements↩︎

This paper introduces a Hessian-free online unlearning method via maintaining a statistical vector for each data sample, computed through affine stochastic recursion approximation of the difference in the retrained and the unlearn models. We have shown that our approach outperforms the existing results in terms of time/memory costs, while also enhancing accuracy. While the unlearning algorithm was initially proposed to assist organizations in complying with data protection regulations (e.g., GDPR) and help build trust in AI systems by demonstrating the ability to correct mistakes or biases, it is important to be mindful of potential negative consequences: Unlearning algorithms can introduce unforeseen biases or inaccuracies in subsequent predictions or decisions. In addition, adversarial actors could potentially exploit machine unlearning processes to manipulate or subvert models.

7 Proofs↩︎

7.1 Detailed Proof of Eq. 10↩︎

Here, we provide a more detailed proof and explanation for 10 . Specifically, we first consider the impact of sample \(u\) on the \(e\)-th epoch, and then extend the analysis to all epochs.

7.2 Detailed Proof of Theorem 1↩︎

Now, we demonstrate that in the case of continuous arrival of deletion requests, our algorithm is capable of streaming removing samples. Intuitively, this property can be mainly explained by Taylor’s linear expansion. For ease of exposition, we simplify our proof to a scenario with only two samples, \(u_1\) and \(u_2\). That is, our goal is to prove that when \(u_1\) initiates a deletion request and the algorithm is executed, the arrival of a deletion request from \(u_2\) after \(u_1\) (Streaming Deletion), is fully equivalent to the simultaneous execution of deletion requests from both \(u_1\) and \(u_2\) (Batch Deletion). Without loss of generality, we assume that \(b(u_1) < b(u_2)\). Based on 10 , the approximators for \(u_1\) and \(u_2\) are denoted as \(\mathbf{a}_{E,B}^{-u_1}\) and \(\mathbf{a}_{E,B}^{-u_2}\), respectively, as follows: \[\begin{align} \mathbf{a}_{E,B}^{-u_1} &= \sum_{e=0}^E\mathbf{M}_{e,b(u_1)} \nabla \ell (\mathbf{w}_{e,b(u_1)};u_1)\\ \mathbf{a}_{E,B}^{-u_2} &= \sum_{e=0}^E\mathbf{M}_{e,b(u_2)} \nabla \ell (\mathbf{w}_{e,b(u_2)};u_2) \label{Equation:32Proof32of32Corollary-1} \end{align}\tag{14}\] When we simultaneously delete \(u_1\) and \(u_2\), the difference between retraining the model and learning the model is as follows, \[\begin{align} \mathbf{w}_{e,b+1}^{-u_2-u_1} -\mathbf{w}_{e, b+1} &\leftarrow \mathbf{w}_{e,b}^{-u_2-u_1}-\mathbf{w}_{e, b}- \frac{\eta_{e,b}}{|\mathcal{B}_{e,b}|} \sum_{i \in \mathcal{B}_{e,b}} \left( \nabla \ell \left(\mathbf{w}_{e,b}^{-u_2-u_1};z_i\right) - \nabla \ell (\mathbf{w}_{e, b};z_i) \right)\\ \mathbf{w}_{e,b(u_2)+1}^{-u_2-u_1} -\mathbf{w}_{e, b(u_2)+1} &\leftarrow \mathbf{w}_{e,b(u_2)}^{-u_2-u_1}-\mathbf{w}_{e, b(u_2)}- \frac{\eta_{e,b(u_2)}}{|\mathcal{B}_{e,b(u_2)}|} \sum_{i \in \mathcal{B}_{e,b(u_2)}} \left( \nabla \ell (\mathbf{w}_{e,b(u_2)}^{-u_2-u_1};z_i) - \nabla \ell (\mathbf{w}_{e, b(u_2)};z_i) \right)\\ \mathbf{w}_{e,b(u_1)+1}^{-u_2-u_1} -\mathbf{w}_{e, b(u_1)+1} &\leftarrow \mathbf{w}_{e,b(u_1)}^{-u_2-u_1}-\mathbf{w}_{e, b(u_1)}- \frac{\eta_{e,b(u_1)}}{|\mathcal{B}_{e,b(u_1)}|} \sum_{i \in \mathcal{B}_{e,b(u_1)}} \left( \nabla \ell (\mathbf{w}_{e,b(u_1)}^{-u_2-u_1};z_i) - \nabla \ell (\mathbf{w}_{e, b(u_1)};z_i) \right). \end{align}\] Consider the Taylor expansion. For the \(E\)-th epoch, we have, \[\begin{align} \mathbf{w}_{E,b+1}^{-u_2-u_1} -\mathbf{w}_{E,b+1} &\approx (\mathbf{I}- \frac{\eta_{E,b}}{|\mathcal{B}_{E,b}|}\mathbf{H}_{E,b})(\mathbf{w}_{E,b}^{-u_2-u_1}-\mathbf{w}_{E,b})\\ \mathbf{w}_{E,b(u_2)+1}^{-u_2-u_1} - \mathbf{w}_{E,b(u_2)+1} &\approx \; (\mathbf{I} - \frac{\eta_{E,b(u_2)}}{|\mathcal{B}_{E,b(u_2)}|} \mathbf{H}_{E,b(u_2)})(\mathbf{w}_{E,b(u_2)}^{-u_2-u_1} - \mathbf{w}_{E,b(u_2)}) + \underbrace{\frac{\eta_{E,b(u_2)}}{|\mathcal{B}_{E,b(u_2)}|} \nabla \ell (\mathbf{w}_{E,b(u_2)};u_2)}_{\text{Impact of u_2 in e-th epoch }}\\ \mathbf{w}_{E,b(u_1)+1}^{-u_2-u_1} - \mathbf{w}_{E,b(u_1)+1} &\approx \; (\mathbf{I} - \frac{\eta_{E,b(u_1)}}{|\mathcal{B}_{E,b(u_1)}|} \mathbf{H}_{E,b(u_1)})(\mathbf{w}_{E,b(u_1)}^{-u_2-u_1} - \mathbf{w}_{E,b(u_1)}) + \underbrace{\frac{\eta_{E,b(u_1)}}{|\mathcal{B}_{E,b(u_1)}|} \nabla \ell (\mathbf{w}_{E,b(u_1)};u_1)}_{\text{Impact of u_1 in e-th epoch }}. \end{align}\] Therefore, in the \(E\)-th epoch, we have the following affine stochastic recursion, \[\begin{align} \mathbf{w}_{E,B}^{-u_2-u_1}& -\mathbf{w}_{E,B} \approx \prod_{b=0}^{B-1}(\mathbf{I}- \frac{\eta_{E,b}}{|\mathcal{B}_{E,b}|}\mathbf{H}_{E,b})(\mathbf{w}_{E,0}^{-u_2-u_1}-\mathbf{w}_{E,0})\\&+ \prod_{b=b(u_1)}^{B-1}(\mathbf{I}-\frac{\eta_{E,b}}{|\mathcal{B}_{E,b}|}\mathbf{H}_{E,b}) \frac{\eta_{E,b(u_1)}}{|\mathcal{B}_{E,b(u_1)}|} \nabla \ell (\mathbf{w}_{E,b(u_1)};u_1)+ \prod_{b=b(u_2)}^{B-1}(\mathbf{I}- \frac{\eta_{E,b}}{|\mathcal{B}_{E,b}|}\mathbf{H}_{E,b}) \frac{\eta_{E,b(u_2)}}{|\mathcal{B}_{E,b(u_2)}|} \nabla \ell (\mathbf{w}_{E,b(u_2)};u_2). \end{align}\] Apply it recursively to complete the proof, and we can simultaneously compute the impact of \(u_1\) and \(u_2\) on training for all epochs. Since the initial models are identical, recursion stops at \(e=0, b=b(u_1)\), and we eventually obtain, \[\mathbf{w}_{E,B}^{-u_2-u_1} -\mathbf{w}_{E,B} \approx \sum_{e=0}^E\mathbf{M}_{e,b(u_1)} \nabla \ell (\mathbf{w}_{e,b(u_1)};u_1)+\sum_{e=0}^E\mathbf{M}_{e,b(u_2)} \nabla \ell (\mathbf{w}_{e,b(u_2)};u_2) := \mathbf{a}_{E,B}^{-u_2-u_1}. \label{Equation:32Proof32of32Corollary-2}\tag{15}\] According to 14 and 15 , we have completed the proof of \(\mathbf{a}_{E,B}^{-u_2-u_1}= \mathbf{a}_{E,B}^{-u_1}+ \mathbf{a}_{E,B}^{-u_2}\).

7.3 Detailed Proof of Lemma 1↩︎

7.4 Detailed Proof of Theorem 2↩︎

7.5 Additional Notation↩︎

We provide the definition of \(\lambda\)-strongly convex and \(L\)-Lipschitz with \(M\)-Smooth.

7.6 Detailed Proof of Theorem 3↩︎

Before we commence with our proof, we present some necessary lemmas.

Based on Lemma 3 and Lemma 4, we begin the proof of convergence in Theorem 3.

8 sec:Additional32Experiments↩︎

The experiments were conducted on the NVIDIA GeForce RTX 4090. The code were implemented in PyTorch 2.0.0 and leverage the CUDA Toolkit version 11.8. Our comprehensive tests were conducted on AMD EPYC 7763 CPU @1.50GHz with 64 cores under Ubuntu20.04.6 LTS.
Source Code: https://github.com/Anonymous202401/If-Recollecting-were-Forgetting

8.1 Detailed Hyperparameters Settings↩︎

In this subsection, we provide detailed hyperparameter configurations.

• In the Verification Experiments, we utilized the MNIST dataset for method evaluation, consisting of 1,000 data points. For Logistic Regression, training was conducted for 50 epochs with stepsize of 0.05 and full batch updates. Additionally, the stochastic gradient norm was clipped at 10 during training. For CNN, training was carried out for 20 epochs with stepsize of 0.05 and a batch size of 64. Similar to LR, a threshold of 10 was employed for the stochastic gradient norm during training. In both the convex setting and the non-convex setting, the step size decay is set to 0.995.

• In the Application Experiments, our hyperparameter configurations for both Logistic Regression and CNN on MNIST dataset are consistent with the verification experiments. Additionally, we evaluated CNN and LeNet on Fashion MNIST, which consists of 4,000 data points, and assessed ResNet-18 on CelebA, consisting of 1,000 data points. Specifically, for CNN and LeNet, training was conducted for 30 epochs with a step size of 0.5 and a batch size of 256. the threshold of 0.5 was used for the stochastic gradient norm during training. for ResNet-18, training was conducted for 10 epochs with a step size of 0.05 and a batch size of 32, and a threshold of 10 was used for the gradient norm during training. For all the aforementioned scenarios, we introduced noise scale with \(0.1\), and the step size decay was set to 0.995.

Multinomial Logistic Regression for the MNIST dataset. It comprises a single layer that performs a linear transformation on the input data. The model has a total of 7,850 parameters. Specifically, the input tensor x is flattened to a one-dimensional shape, and then it undergoes a linear transformation. This transformation is essentially a weighted sum of the input features, producing the final output of the model. The purpose of reshaping the input is to facilitate this linear transformation.

A simple CNN for the MNIST/FMNIST dataset comprises a total of 21,840 parameters and consists of two convolutional layers for image classification. The first layer processes input data with a specified number of channels, using 10 filters of size 5x5, followed by a ReLU activation function and 2x2 max pooling. The subsequent layer employs 20 filters of size 5x5, incorporating a ReLU activation function and 2x2 max pooling with dropout regularization to mitigate overfitting. The flattened output is then connected to a fully connected layer with 320 input features, succeeded by another fully connected layer with 50 units and a ReLU activation. The final layer produces the model’s output with several classes specified by the task, and a log-softmax function is applied for classification purposes.

8.2 sec:Additional32Experiments↩︎

We further evaluate on larger-scale model (ResNet18) and more sophisticated dataset (CIFAR10 [40]) with more data points (50,000). In addition to the distance between the learned model and the retrained model, we also consider different metrics in terms of accuracy on the forgetting dataset and accuracy on the remaining dataset. Since the previous works NS and IJ are difficult to compute in this scenario, we instead use the following baselines, lacking theoretical indistinguishability guarantees, as described and similarly set up in [25]:

• FineTune: In case of finetuning, the original learned model is finetuned on the remaining dataset.

• NegGrad: In case of gradient ascent, the learned model is finetuned using negative of the models gradients on the forgetting dataset.

Configurations: We evaluated on ResNet18 for CIFAR-10 featuring a total of 11,689,512 parameters with 50,000 data samples. The Learning stage was conducted for 40 epochs with stepsize of 0.001 and a batch size of 256. For FinetuTune, 10 epochs of training are done with a learning rate of 0.001. For NegGrad, we run gradient ascent for 2 epochs with a learning rate of 0.0001 and batchsize of 1. We define \(D_f\) as the forgetting dataset, \(D_r\) as the remaining dataset, and \(D_t\) as the test dataset. We randomly unlearned 50 data points. The following Table 2 are our evaluation results:

The values in parentheses represent the change in accuracy compared to the original learned model. For example, in the retrain method, 78.00 (-2) means that the accuracy on decreased by 2% compared to the original learned model and dataset.

Performances of Our Scheme: We still maintain model indistinguishability and accuracy indistinguishability from the retrained model on more complex tasks and larger models, where the distance is only 0.09. Moreover, compared to other baselines, our method achieves forgetting in only 0.6 ms, demonstrating the potential of our method on larger models.

Model Indistinguishability v.s. Accuracy: For FineTune, we can observe that even though the accuracies are similar to retained model, the distance is very large at 2.21. For NegGrad, we ran on with a very small learning rate to avoid gradient explosion. We observe that the accuracy on forgetting dataset \(D_f\) and the accuracy on remaining dataset \(D_r\) would rapidly decrease simultaneously, but even in this case, the distance is still lower than that of FineTune. This demonstrates that a small difference in accuracy does not indicatethe model indistinguishability. Furthermore, although distance can serve as a reliable metric to evaluate model indistinguishability for assessing the algorithm of a theoretical work, it is completely impractical in real-world scenarios because it requires retraining a model. Therefore, exploring more effective metrics to evaluate model indistinguishability is an interesting and important topic in the future.

8.3 sec:Ablation32Studies↩︎

Here, we investigate the sensitivity of the proposed approach to hyperparameters. Specifically, we evaluated the effects of different step sizes, epochs, decay rates of step size, and dataset sizes on proposed approach. We conducted simulations in both convex and non-convex scenarios, using Logistic Regression for the convex case and CNN for the non-convex case, respectively. Additionally, we performed the aforementioned ablation studies on both MNIST datasets by using the distance metric between unlearned model and retrained model to evaluated similarity, and accuracy metric to evaluated performance.

Configurations: Building upon the hyperparameter settings outlined in the paper, we systematically varied these parameters to investigate the impact of hyperparameters on our method. We discuss the results of these hyperparameter settings under low deletion rates (1%, 5%) and high deletion rates (20%, 30%).

Takeaway. Let’s first provide a brief summary for the main results of ablation studies.

• Impact of Step Sizes. Firstly, a smaller learning rate enables our model to be closer to the retrained model. This is because the remainder term \(o(\mathbf{w}_{e,b}^{-u} - \mathbf{w}_{e,b})\) which is the source of approximation error will be scaled by subsequent \(\mathbf{I} - \frac{\eta_{e,b}}{|\mathcal{B}_{e,b}|} \mathbf{H}_{e,b}\). Specifically, the analysis results from Theorem 2 and 3 indicate that the spectral radius \(\rho\) of \(\mathbf{I} - \frac{\eta_{e,b}}{|\mathcal{B}_{e,b}|} \mathbf{H}_{e,b}\) determines error of our proposed method. If \(\rho > 1\), approximation error will exponentially increase. Therefore, a smaller stepsize constrain the maximum eigenvalue of the matrix \(\frac{\eta_{e,b}}{|\mathcal{B}_{e,b}|} \mathbf{H}_{e,b}\), finally leading to a reduction in the error by decreasing the value of \(\rho\). Moreover, with a small step size, increasing epochs does not lead to significant approximation errors; instead, it exhibits better performance under the distance metric compared to a large step size.

• Impact of Epochs. Secondly, similar to Theorem 2 and the preceding analysis of stepsize, when the step size is sufficiently small, the approximation error is insensitive and exhibits slow growth with respect to the number of epochs, i.e., excessive iterations in this scenario do not lead to significant errors. Besides, it’s important to note that the computational cost is related to the number of \(T\), and thus choosing a smaller step size may result in increased computational overhead. This requires a tradeoff based on the practical considerations of the specific scenario.

• Impact of the Decay Rates of Step Size. Thirdly, our results indicate that as the decay rate \(q\) decreases, our approximation error diminishes. Specifically, the step size decay strategy introduces an upper bound on our error, preventing a continuous increase in error as epochs progress. Besides, it is crucial to avoid excessively small decay rates to prevent the step size from rapidly decaying to 0, which may hinder the convergence of the learned model.

• Impact of Dataset Sizes. Finally, our numerical findings show that the approximation error reduces with larger datasets. Intuitively, as the dataset size increases, the impact of individual data points on model updates diminishes during training. This is typically reflected in the training process, where with an increase in the dataset size, each batch update is less likely to frequently sample a specific data point. Consequently, the impact of any individual data point on updates between the retrained original models diminishes, leading to a more accurate approximation in our method.

8.3.1 Impact of Step Sizes↩︎

We investigate the impact of varying step sizes {0.001, 0.005, 0.01, 0.05, 0.1, 0.5, 1} on both distance and accuracy metrics.

As shown in Table [Table:32Impact32of32Step32Sizes32on32Convex] and Table [Table:32Impact32of32Step32Sizes32on32Non-Convex], a smaller learning rate enables our model to be closer to the retrained model. Specifically, as Theorem 2 demonstrates that, in this process, the error arises from the scaled Peano remainder term, i.e., the term \(o(\mathbf{w}_{e,b}^{-u} - \mathbf{w}_{e,b})\) is scaled by the subsequent \(\mathbf{M}_{e,b(u)}\), where \(\mathbf{M}_{e,b(u)} = \frac{\eta_{E,b(u)}}{|\mathcal{B}_{E,b(u)}|} \prod^E_{k=e} \prod_{b=b(u)}^{B-1}(\mathbf{I} - \frac{\eta_{k,b}}{|\mathcal{B}_{k,b}|} \mathbf{H}_{k,b})\). Therefore, a smaller step size can shrink the maximum eigenvalue \(\lambda_1\) of the average Hessian matrix \(\frac{1}{|\mathcal{B}_{e,b}|} \mathbf{H}_{e,b}\), thereby reducing the spectral radius \(\rho\) of the matrix \(\mathbf{I} - \frac{\eta_{e,b}}{|\mathcal{B}_{e,b}|} \mathbf{H}_{e,b}\), and finally reducing approximation error.

Furthermore, If the step size is extremely large, the maximum eigenvalue \(\lambda_1\) of the average Hessian will be amplified, leading to an exponential growth in errors, as shown in Table [Table:32Impact32of32Step32Sizes32on32Convex] and Table [Table:32Impact32of32Step32Sizes32on32Non-Convex] for initial stepsize \(\eta =1\). In this scenario where \(\eta \geq 1\), our method leads to a complete breakdown of the model, rendering it unusable. However, it is noteworthy that theoretical predictions [41] and empirical validation [42] suggest that, across all datasets and models, successful training occurs only when optimization enters a stable region of parameter space where \(\lambda_1 \cdot \eta \leq 2\). Therefore, achieving good optimization results typically does not require a strategy of using aggressive step sizes.

In fact, we can gain insights from these works. Specifically, these studies aim to explore the sharpness of the loss Hessian \(\frac{1}{|\mathcal{B}_{e,b}|} \mathbf{H}_{e,b}\), and the term ‘sharpness’ refers to the maximum eigenvalue of the loss Hessian denoted as \(\lambda_1\) in some studies, such as [42]. Previous works [43], [44] have pointed out that flat minima are advantageous for generalization. A flat loss space is widely recognized as beneficial for gradient descent optimization, leading to improved convergence properties. Importantly, [42] demonstrates the central role that \(\lambda_1\) plays in neural network optimization, emphasizing that maintaining a sufficiently small \(\lambda_1\) during optimization is a necessary condition for successful training (without causing divergence) at large step sizes. Models which train successfully enter a region where \(\lambda \cdot \eta \leq 2\) mid training (or fluctuate just above this bound). In our work, we leverage the second-order information from the loss Hessian at each iteration during the training process to achieve forgetting. As indicated in Theorem 2, our analysis indicates that a small \(\lambda_1\) of the loss Hessian is beneficial for reducing the approximation error. In other words, when training requires a large step size \(\eta\), as suggested in [42], strategies like stepsize warm-up or initialization strategies for architectures can be employed to stabilize learning and potentially reduce unlearning approximation errors by decreasing \(\lambda_1\). We will explore such strategies in the future to implement our unlearning method at aggressive stepsizes.

Finally, with a very small step size during model training, we observed a low approximation error. To investigate the impact of epochs under small step sizes, LR was trained for 750 epochs (converged) and 2000 epochs (overfitting) with a step size of 0.001 (originally 0.05 with 50 epochs). Additionally, when the step size is very small (0.001) in LR, the step size decay strategy causes premature decay to zero before the model convergence. We thus increased the step size decay rate from 0.995 to 1. Subsequent experiments will demonstrate that this leads to an increase in approximation error. For CNN, training for 50 epochs (converged) and 500 epochs (overfitting) with a step size of 0.025 (originally 0.05 with 20 epochs) was performed. As shown in Fig. 5, even as the model approaches overfitting, the approximation error remains lower than in the case with a step size of 0.05. This suggests that a smaller step size reduces the approximation error, bringing our algorithm closer to the retrained model. It is crucial to note that a smaller step size requires more iterations to converge, resulting in increased computational cost. Therefore, choosing an appropriate step size is essential based on different scenarios.

8.3.2 Impact of Epochs↩︎

Our previous experiments indicate that the increase in epochs does not become a major factor affecting approximation errors when applying small step sizes, i.e., with LR at a step size of 0.001 and CNN at a step size of 0.025, the growth of epochs does not significantly impact the approximation error. Conversely, in the case of small step sizes, even as epochs extend to a point where the model approaches overfitting, the error remains lower than scenarios with larger step sizes.

Furthermore, we explore the impact of the epoch with a fixed and larger step size, such as the one \(\eta=0.05\) we selected in our study. In this scenario, we evaluate the impact of the epochs on both the distance and accuracy metrics. Specifically, we investigated the distance under the epoch set {10, 25, 50, 75, 100} and provided the accuracy on 100 epoch after forgetting 20% data. In addition, the selection of other hyperparameters remains consistent with the ones used previously.

In Fig. 6, we can observe that the distance slowly increases with the growth of epochs. This is attributed to the fact that each iteration involves an approximation, and multiple rounds of iterations lead to the accumulation on approximation error. However, as the right of Fig. 6 (a)(b) shows that, the accumulation of this error is sufficiently small and does not lead to a significant performance degradation. Additionally, we find that the distance gradually stabilizes (i.e., the error generated with each iteration becomes progressively smaller.) as epochs continue to increase. We attribute this behavior to the step size decay strategy, and we will provide detailed results in subsequent experiments.

8.3.3 Impact of Decay Rates of Stepsize↩︎

This experiments aim to study the impacts of stepsizes. We consider two scenarios: one with stepsize decay (\(q=0.995\)) and the other without stepsize decay (\(q=1\)). We keep the other hyperparameters constant and only increase epochs.

From Fig. 7 (a)(b), we can observe that the Euclidean distance for the stepsize decay strategy is generally smaller compared to that without the stepsize decay. This aligns with our earlier analysis of step size in Appendix 8.3.1, i.e., a smaller step size leads to a smaller approximation error and choosing an appropriate step size decay rate ensures a continuous reduction in step size, preventing the unbounded growth of the approximation error.

Additionally, as in Fig. 7 (b), we find that the Euclidean distance of CNN tends to stabilize even without step size decay. This result can be explained by the conclusions in [45], [46]. Specifically, [45], [46] analyze the spectral distribution of the Hessian eigenvalues during CNN training. It reveals that, initially, the eigenvalues of loss Hessian are symmetrically distributed around 0. As training progresses, they converge towards 0, indicating Hessian degeneracy. Towards the end of training, only a small number of eigenvalues become negative and a large portion of the Hessian eigenvalues approach 0 when the training closes to convergence. Let’s recall our previous analysis of stepsize in Appendix 8.3.1 and the Theorem 2, where we demonstrates that the approximation error is primarily determined by \(\rho\) of \(\mathbf{I} - \frac{\eta_{e,b}}{|\mathcal{B}_{e,b}|} \mathbf{H}_{e,b}\), and \(\rho\) is determined by \(\eta_{e,b}\) and \(\lambda_1\). Here, \(\lambda_1\) represents the maximum eigenvalue of the average Hessian matrix \(\frac{1}{|\mathcal{B}_{e,b}|}\mathbf{H}_{e,b}\). As the number of iterations increases, the eigenvalues of the loss Hessian \(\mathbf{H}_{e,b}\) tends to 0. This implies a decrease in \(\lambda_1\), leading to a slower increase in error. Therefore, in Fig. 7 (b), the distance gradually stabilizes even without a decay strategy due to the decrease in \(\lambda_1\) during training, and it still increases due to the existence of some larger outlier eigenvalues.

8.3.4 Impact of Dataset Sizes↩︎

Finally, we assess the impacts of different dataset sizes. To maintain the total number of iterations, we adapt the number of epochs based on the dataset size. We keep other hyperparameters constant.

As shown in Table [Table:32Impact32of32Dataset32Sizes32on32Convex] and Table [Table:32Impact32of32Dataset32Sizes32on32Non-Convex], we observe that larger dataset size generally tends to decrease the approximation error, making the unlearned model more closely resemble the retrained model. A reasonable explanation is that the enlargement of the dataset implies less frequent sampling of a specific data point for updating the model, consequently reducing the impact of data on the model updates in Eq. 3 . This, in turn, leads to a decrease in the approximation error.

9 Discussion↩︎

9.1 sec:Deletion32Capacity↩︎

Subsequently, we analyzed the deletion capacity of our method based on [8], which formalizes how many samples can be deleted from the model parameterized by the original empirical risk minimizer while maintaining reasonable guarantees on the test loss.

Similar to [8], we provide upper and lower bounds for our algorithm. Intuitively, according to Theorem 3, in the optimal situation, we discussed the excess loss of our algorithm and demonstrated its superiority over previous approaches, indicating a potentially improved deletion capacity. We first give the upper bound of deletion capacity.

A comprehensive proof of Theorem 5 is available in [8]. Furthermore, Based on Theorem 3, we present lower bound of deletion capacity below:

9.2 Online Unlearning-Repairing Strategy↩︎

Unlike most unlearning methods, our proposed unlearning approach does not require access to the remaining data set \(\mathcal{S}/U\) or forgetting data \(U\) in Stage III. However, if we do have access to the remaining dataset, we can adopt a simple fine-tuning strategy to mitigate the performance degradation caused by excessive deletions and make our algorithm more robust.

Specifically, when the continuous incoming deletion requests to forget data, we can rapidly implement certified unlearning through vector addition. This involves augmenting the current model with approximators, where errors accumulate during this process and thus cause the performance degradation. Suppose, upon the arrival of a new round of deletion requests for a particular model and dataset, the model’s accuracy significantly drops due to the removal of a substantial amount of data. In such a scenario, we can address this performance degradation by fine-tuning the current model for \(E_r\) epochs (usually just 2 epoch) on the remaining dataset, referred to as the ‘repairing’ process. Additionally, by computing the approximators for the remaining dataset during the repairing process, and adding these approximators during the repairing process to the pre-stored approximators during the learning process, we obtain the new set of approximators for the remaining data.

Through the aforementioned strategy, we repair the model’s accuracy and update the approximators corresponding to the remaining dataset. When subsequent forgetting requests occur, we can still utilize the new approximators to implement forgetting. We conducted a simple validation on ResNet-18. Specifically, the hyperparameter configuration remains consistent with the previous setup in the application experiment, i.e., we use a relatively large learning rate to train the model, which can result in our method generating larger errors as described in Section 8.3.1. Each time we forget 20% of the data, we apply the repairing strategy outlined in Algorithm 9, conducting \(E_r=2\) epoch on the remaining dataset to repair performance. As shown in Figure 8, our method performs a fine-tuning operation on the remaining dataset every time 20% of the data was forgotten, reparing the model performance to a satisfactory level. Through the Online Unlearning-Repairing Strategy, our approach can handle more forgetting requests on ResNet-18 without causing significant performance losses.

References↩︎