Machine Unlearning for Streaming Forgetting

Thank you for the reviews. Below we provide responses to the weaknesses raised as well as address the questions.

W1 Heuristic Approach to Unlearning. The paper analyzes one heuristic approach to unlearning (Problem (1)), which jointly minimizes the loss on the retain and the KL divergence (from the model obtained via retraining from scratch) on the forget data. Unfortunately, it is not clear that this heuristic attains the objective of unlearning, which is being statistically indistinguishable from retraining without forgetting data. There are rigorous definitions of the unlearning objective (Ginart et al. 2019, Guo et al. 2020, Sekhari et al. 2021) which quantify the level of statistical indistinguishability and which are algorithmically attainable, and several works analyzing sequential (adaptive) requests towards this objective (Gupta et al. 2021, Chourasia et al. 2023). It is a missed opportunity to provide theoretical guarantees on the regret of the algorithm, without any guarantees on the central issue at hand, which is unlearning.

The main argument raised in the Weakness 1 is that our unlearning objective Eq. 1, is purely heuristic and unrelated to formal unlearning definitions. We respectfully disagree with this argument. From an optimization perspective, the optimal model obtained via retraining without forgetting data is also the optimal solution to Eq. 1 under appropriate conditions. In other words, if Eq. 1 is successfully optimized, the resulting model is not only statistically indistinguishable from retraining without the forget data—as required by formal unlearning definitions—but is mathematically equal to the retraining model when $\lambda=0$, and all theoretical guarantees also apply to this $\lambda=0$ scenario.

The inclusion of the KL divergence penalty term on the forgetting data serves an additional purpose: it ensures that the unlearned model can have a similar performance on the forgetting data as the retrained model. This introduces an important degree of flexibility, allowing control over the performance of forgetting data, a consideration that is absent in prior works. This flexibility may be crucial in practical applications where some performance requirement for forgetting data is explicitly desirable.

Overall, our approach aligns with the rigorous definitions proposed by (Ginart et al. 2019, Guo et al. 2020, and Sekhari et al. 2021) while extending their frameworks to incorporate additional practical considerations, specifically on forgetting data.

W2 Insufficient Experimental Validation of Unlearning. While there is no theoretical unlearning guarantee, as mentioned above, there is not enough experimental evidence on unlearning either. This is typically done through membership inference attacks, which are deferred to the appendix where they are not discussed enough, nor is the specific membership inference attack explained. The latter point is quite important since it is not trivial to adapt membership inference attacks for machine unlearning (Hayes et al., 2024). and Q2 Could the authors expand on the membership inference attack used in experiments? Which specific attack was employed, and were any adjustments made to suit the unlearning setting?

Thank you for raising these important concerns about our handling of membership inference attacks (MIA) in the paper. We have addressed your feedback in the updated version as follows:

• We have moved the MIA analysis from the appendix to the main text.
• We expanded the details of the MIA methodology. Specifically, we adapted the approach in [1] and [2], using the remaining data (positive) and real test data (negative) as the attacker model’s training set. The attacker was then evaluated on the forgetting data to measure attack success rates, providing insights into how well the unlearning method prevents data memorization. The implementation details are described in Lines 1145–1150 of the updated paper.
• We extended the discussion of MIA results to analyze not only which unlearning methods perform better but also why they do so. More factors such as the nature of the forgetting mechanism are explored in detail (Lines 437–443).

We hope these updates address the concerns raised and improve the clarity of our experimental validation.

• The authors have not addressed my main concern regarding guarantees on unlearning. I understand that Problem (1) could have a nice interpretation in relation with unlearning, but it still seems that there is no rigorous link with established definitions of unlearning, i.e., statistical indistinguishability from retraining from scratch (see references in my original review).
• If the authors concede to the point above, then perhaps the positioning of the paper should be rather empirical--which is also fine. However, regarding the empirical guarantees for unlearning which basically is success of membership inference attacks, it seems that the reported attack efficacies in Table 1 are almost all in the same range! There is unfortunately no interpretation of this part of the result, which is also a weakness of the current version of the paper. Could the author explain how their proposed method compares with existing ones in terms of defending against membership inference attacks?
• Thanks for expanding on the regret bound further. It seems that there are cases where the regret bound is superlinear. Do the authors agree that the bound is therefore vacuous in that case? Furthermore, are there practical cases (precise conditions) where this is guaranteed not happen, i.e., regret bound is surely sublinear?
• Thanks for adding a detailed comparison with Sekhari et al. Can the authors confirm that in the aforementioned work, there is an omitted dependence on the size of the dataset $n>m$, that yields a final bound of the form $m^2/n^2$? If so, this result does not appear weaker than the potential superlinear regret bound.

Q1: Eq. (1) and Line 111: The term $\mathcal{R}(F, w) = {1}/{|F|}\sum_{(\mathbf{x},y)\in F} d_{\text{KL}}(f(\mathbf{x};w), f(\mathbf{x};w^*))$ is confusing to me. If $w^*$ is defined as optimum $\mathcal{L}(D-L,w)$, wouldn't the KL term go to zero simply by minimizing the loss and then setting $w^* = \arg\min\mathcal{L}(D-L,w)$? Also, this seems at odds with Kurmanji et al., 2023. In their work they have a KL term on the subset of the data that they wish to forget weighted negatively.

We posit that $w^* = \arg\min \mathcal{L}(D-L, w)$ is also an optimizer for our proposed Eq. (1). Theoretically, optimizing Eq. (1) could lead to $w^* = \arg\min \mathcal{L}(D-L, w)$, suggesting that the KL divergence term may not be necessary.

However, as one of the key objectives is to achieve unlearning specifically on the forgetting data, we observe that optimizing $w^* = \arg\min \mathcal{L}(D-L, w)$ alone in a streaming setting, as shown by the w/o DSR line in Table 2, does not achieve unlearning accuracy (UA) as effectively as true retraining. This discrepancy can be attributed to the lack of constraints on the performance for the forgetting data. It is also worth noting that setting $\lambda = 0$ reduces the problem to unlearning via $\min \mathcal{L}(D-L, w)$. In this work, we propose a more general framework that allows flexibility to specifically consider the forgetting data in a streaming setting—an approach that has proven effective in our experiments considering various metrics.

While our objective aims to fully align with the retrained model—both on forgetting data and remaining data—Kurmanji et al. (2023) explicitly design their objective to produce poor predictions on the forgetting data, leading to large errors for those data points. As stated in your raised Q2, their method adopts a fundamentally different unlearning objective compared to retraining, which we have not yet explored in a streaming setting in this paper. The negative term in the objective proposed by Kurmanji et al. (2023) may introduce challenges in optimization under a streaming setting. We appreciate the comment highlighting this alternative approach and plan to explore it in future work.

Q2: What is the definition of forgetting for the authors? Please provide it clearly in the paper.

Thank you for raising this point. In this work, we define unlearning as the model that, after unlearning, should perform similarly to the model retrained solely on remaining data. The two models should show close performance on both remaining training data and other unseen data, such as forgetting or test data. Our definition is consistent with the ones in prior works ([2], [4], [5]), which describe general machine unlearning as "Unlearning guarantees that training on a point and unlearning it afterwards will produce the same distribution of models as not training on the point at all." This also emphasizes the importance of achieving performance similar to a retrained model on both the remaining and forgetting data predictions.

Based on the definition, the straightforward objective for unlearning is $w^* = \arg\min \mathcal{L}(D-L, w)$, which can ensure the post-unlearning model is close to the retrained model on the remaining data through retraining. But to effectively ensure that the forgetting data can also perform similarly to the retrained model, the objective can be formulated as:

where the regularizer $\mathcal{R}(F, w)$ is defined as:

and imposes restrictions on the forgetting data $F$ by encouraging divergence from the original model's outputs.

By optimizing the regularizer, we align the post-unlearning model's outputs on the forgetting data with the retrained model, ensuring forgetting is enforced.

Q3: I followed the proofs in the appendix carefully and they seem correct. I have a question regarding Theorem 2. Where does the inequality in Line 898 come from?

It comes from the upper-bounded gradient assumption in Theorem 1, where we assume $||\nabla R_{t}(w)||\le U$. Following this assumption, then gradient from $w$ to $w^*$, that is $\frac{|R_{t}(w) - R_{t}(w^*)|}{|w - w^*|}$ will also be less or equal than $U$. We have made it clear in the proof.

Q4: Eq. (5): Why is $w_t$ on the LHS?

It should be $w$ on the LHS and $\arg\min$ in the RHS. Thank you for raising this.

W3: Proper statistical testing is needed to confirm that the method indeed improves over the second-best baseline in most cases.

Thank you for highlighting this point. Following the suggestion, we conducted statistical testing on all the experimental results presented in Table 1. Methods that are significantly better than others are bolded based on a two-tailed t-test with a 90% confidence level. For instance, the p-values for RA, UA, and TA on the CIFAR-10 dataset are 0.0020, 0.0380, and 0.0008, respectively. These results demonstrate that the proposed method performs significantly better than the other methods.

Additionally, the p-values for RA, TA, and JS on the MNIST dataset are 0.0087, 0.0130, and 0.0919, respectively, and the p-values for RA, UA, TA, and JS on the FMNIST dataset are 0.0056, 0.0008, 0.0075, and 0.0342, respectively. These findings further confirm that the proposed method outperforms Unroll with at least 90% confidence.

To address the concern of 0.5% accuracy improvement and provide a more robust evaluation of the method's performance, we employ the Jensen–Shannon Divergence (JS) as an additional metric. Unlike accuracy, which evaluates only the correctness of discrete labels, JS captures the differences in the real-valued output distributions of the model. This approach reveals a substantially greater improvement (for example, SAFE can achieve less than 3.5 Remain JS while other baselines can only achieve 4.0 or higher Remain JS), showing that our proposed SAFE method is advancing SOTA.

W4: Ablations: The ablation results in Table 2 are slightly concerning. We often see that removing a component actually improves performance metrics. Why is this? Does this not contradict the claim that all model components are useful, or at least provide conflicting evidence?

Unlearning is inherently a dual-objective challenge: it requires maintaining the performance on both the retained data and test data while effectively unlearning the forgetting data. In our proposed method, each component plays a distinct role, contributing to specific aspects of the problem. Collectively, however, the proposed SAFE method achieves a balance between these dual objectives. In the following discussion, we elaborate on the role of each component and how the ablation study reflects their individual contributions.

• DSR, which stands for Distribution Shift Risk as presented in Table 2, is specifically designed for unlearning on the forgetting data. Without the DSR component, the JS and UA metrics—used to evaluate the performance on the forgetting data—are worse than those of the SAFE method. This demonstrates DSR's effectiveness in reducing performance on the forgetting data, aligning with its intended functionality.
• TR, representing the initial training risk, is essential for maintaining the performance of both the remaining data and the test data. The ablation study results reveal a more significant performance reduction without TR compared to the SAFE algorithm, demonstrating its role.
• FR, which stands for forgetting data risk, requires further evaluation. The results in Table 2 are presented as averages across all iterations in the streaming process. In Eq. 11, the FR component is calculated based on the forgetting data, which is relatively small at the beginning. This smaller size may compromise the reliability of FR's evaluation during initial iterations, leading to a less reliable average value in Table 2. To address this, we conducted an additional ablation study focusing on the final iteration, where sufficient forgetting data has accumulated to provide a more reliable estimation. The results, shown in the following tables using CIFAR10 data with the Logistic Regression (LR) and ResNet models, indicate that removing the FR component results in a higher UA—reflecting increased accuracy and reduced unlearning on the forgetting data. These additional results have been included in the appendix.

Thank you for the reviews. Below we provide responses to the weaknesses raised as well as address the questions.

W1: While the theoretical grounding is excellent, the experiments are too small scale to be convincing and the statistical analysis is poor or missing...Why focus entirely on image datasets?

Thank you for your suggestion. Following your advice, we have extended our evaluation to the large-scale tinyImageNet dataset with ResNet18 to assess our proposed SAFE method against baselines for Remaining Accuracy (RA), Unlearning Accuracy (UA), Test Accuracy (TA), Membership Inference Attack (MIA), and computational time. For methods that do not require training data, we have highlighted in bold the performance values that are closest to the Retain method and exhibit significant differences, determined through a two-fold t-test at a 95% confidence level. For computational time, the fastest method has been bolded instead. In addition, We have applied a two-fold t-test at a 95% confidence level to all results presented in the paper and highlighted the significantly better values in bold.

Compared to LCODEC and Descent, which do not require access to training data during unlearning, SAFE significantly outperforms these methods in both effectiveness and efficiency. Importantly, SAFE achieves the fastest computation time at just 7.30 seconds, demonstrating its high efficiency. When compared to Unroll and CaMU (which require the original training data), SAFE's performance remains competitive while being much more efficient. Overall, SAFE strikes an excellent balance between accuracy and efficiency, particularly when training data is unavailable.

We chose MNIST, Fashion-MNIST, and CIFAR-10 as these datasets are commonly used benchmarks in the literature for evaluating unlearning methods ([1], [2], [3]). They provide a standard baseline for comparing our results with prior work. Regarding NLP tasks, we have explored some and found that most NLP datasets rely on pretrained components, such as tokenizers, to encode information. Since unlearning a model trained from scratch is the primary focus of this work, the challenge of unlearning pretrained components is beyond the scope of the current study. In contrast, the widely used image datasets we evaluate have been shown to achieve high model performance without reliance on pretrained knowledge, making them well-suited for our focus. That said, we are still open to suggestions for NLP datasets that do not depend heavily on pretrained components and would be happy to explore them.

W2: The evaluation metrics are not defined. What do the RA, UA, TA, JS, GAP initializations mean? Does MIA refer to Membership Inference Attack? Thank you for pointing this out. The initilizations and metrics mean

• RA (Remaining Accuracy): The prediction accuracy of the model on the remaining data after unlearning.
• UA (Unlearning Accuracy): The prediction accuracy of the model on the forgetting data after unlearning.
• TA (Test Accuracy): The prediction accuracy of the model on the overall test data after unlearning.
• JS (Jensen–Shannon Divergence): Measures the divergence between the outputs of the model after unlearning and the outputs of the model retrained on the remaining data. Lower JS indicates smaller differences between the two outputs, signifying better unlearning performance.
• MIA (Membership Inference Attack): Refers to the model’s vulnerability to membership inference attacks.

We have updated them in the paper (Lines 378 to 388).

Thank you for your continued feedback.

Clarifications on "Similar" or "Close Performance

Firstly, we would like to clarify the statements regarding "similar" or "close performance." By this, we mean that the outputs of the unlearned model are comparable to the outputs of the retrained model on the same data [FR1].

Response to Q1: KL Divergence Term and Forgetting Data Performance

Regarding the concerns about Q1, our intention in adding the KL divergence term is to impose restrictions on the performance for the forgetting data. While it may not directly influence the optimization results of: $w^* = \arg\min \mathcal{L}(D-L, w),$ the additional regularizer term further ensures that the divergence between the predictions on the forgetting data and those of the retrained model is minimized. Without this regularizer term, although the performance of the model on the remaining data after unlearning may approach that of the retrained model, the performance on the forgetting data could significantly deviate from that of the retrained model.

For instance, in the case of an overfitting model where the loss on the remaining data ($\mathcal{L}(D-L, w)$) has been minimized during initial training, the gradients on $\mathcal{L}(D-L, w)$ might be negligible, which would result in unlearning being insufficiently achieved through $\mathcal{L}(D-L, w)$ alone. In contrast, the KL term plays a critical role, particularly in stream settings, by ensuring that the performance on forgetting data aligns closely with the retrained model through all rounds of unlearning requests.

Connection with Certified Unlearning

Regarding the relationship between our work and the mathematical definition of certified unlearning, the bounded gradient assumption in Theorem 2 of our work satisfies the requirements of Theorem 2 in [FR2]. Consequently, it can be proven that our proposed unlearning method constitutes an $(\epsilon, \delta)$-certified removal.

We appreciate your suggestion to provide a formal proof for this connection. In the revised paper, we will include the relevant proof to establish this connection clearly.

[FR1] Fan, et al. "SalUn: Empowering Machine Unlearning via Gradient-Based Weight Saliency in Both Image Classification and Generation." ICLR, 2024.

[FR2] Guo, et al. “Certified Data Removal from Machine Learning Models.” ICML, 2020.

Thank you for the reviews. Below, we provide responses to the three weaknesses raised.

W1. New technical novelties of this work compared to previous works (Zhao et al., 2024; Li et al., 2021).

The main technical contribution of our work is that it is the first to address the problem of streaming unlearning for classification models without requiring access to the original training data during the unlearning process. Moreover, our approach does not restrict the classification model architecture, making it broadly applicable. In comparison, Zhao et al. (2024) focus on object detection tasks and rely on a transformer-based structure, while Li et al. (2021) address regression tasks using linear models. Both of these methods require repeated access to the original training data in each round of the streaming phase, making them far less practical in scenarios where diverse model architectures are used and accessing data repeatedly is either impractical or impossible due to privacy concerns. 

In addition, we present a regret risk bound for our approach to the classification problem. Specifically, we show that the accumulated error can be bounded by $O(V_T\sqrt{T}+ \Delta_T)$. In contrast, simply extending existing results from prior work [1] would lead to a significantly less favourable regret bound of $O(T^2)$. While Zhao et al. (2024) do not provide any theoretical results, Li et al. (2021) offer a bound for the linear regression problem, which does not apply to the current classification problem and non-linear models.

[1] Sekhari, et al. "Remember what you want to forget: Algorithms for machine unlearning." NeurIPS, 2021.

W2. Why the above two works (Zhao et al., 2024; Li et al., 2021) are not considered as baselines.

The two works (Zhao et al., 2024; Li et al., 2021) were not considered as baselines in our experiments because their focus, methodologies, and requirements differ fundamentally from our approach. Our work is designed specifically for streaming unlearning in classification tasks without accessing the original training data, whereas Zhao et al. and Li et al. require access to training data during unlearning and focus on different types of learning problems (object detection and regression, respectively).

W3. Consider ImageNet related datasets, at least miniImageNet or tinyImageNet.

Thank you for your suggestion regarding the dataset. Following your advice, we have extended our evaluation to include tinyImageNet with ResNet18 to assess our proposed SAFE method against baselines for Remaining Accuracy (RA), Unlearning Accuracy (UA), Test Accuracy (TA), Membership Inference Attack (MIA), and computational time. For all methods that do not require training data, we have highlighted in bold the performance closest to the retrained method, except for computational time, where we have highlighted the quickest one.

Compared to LCODEC and Descent, which do not require access to training data during unlearning, SAFE significantly outperforms these methods in both effectiveness and efficiency. Importantly, SAFE achieves the fastest computation time at just 7.30 seconds, demonstrating its high efficiency. When compared to Unroll and CaMU (which require the original training data), SAFE's performance remains competitive while being much more efficient. Overall, SAFE strikes an excellent balance between accuracy and efficiency, particularly when training data is unavailable.

Thank you for the reviews. Below we provide responses to the weaknesses raised as well as address the questions.

W1 The performance analysis of SAFE is relatively weak or may be very straightforward, given the existing literature. For instance, the bound on the error of the t-th rounds is simply bounded by $O(\sqrt{T})$, which is straightforward and should not be a tight bound;

We appreciate the reviewer’s feedback on SAFE's performance analysis. However, we respectfully disagree with the assessment that "the performance analysis of SAFE is relatively weak or may be very straightforward given the existing literature" and that "$O(\sqrt{T})$, which is straightforward and should not be a tight bound."

To the best of our knowledge, this is the first work to provide a regret bound for the classification unlearning problem. Deriving these bounds required us to innovatively reformulate each round's unlearning process as a distribution shift problem and conduct the corresponding analysis about the potential range under different unlearning tasks like class-wise or instance-wise unlearning. This approach is not trivial and represents one of the key technical contributions of our work.

In comparison to existing unlearning literature, [1] focuses on the batch unlearning setting and provides an error bound that scales quadratically with the size of the unlearning set. When extended to streaming unlearning, the unlearning set size typically grows linearly with $T$, resulting in a regret bound of $O(T^2)$. In contrast, our regret bound achieves a significant improvement, ranging from $O(T^{3/2})$ to $O(\sqrt{T})$ (see more details in our response to Q1). This improvement demonstrates that our bound is tighter than those in existing literature.

W2 As noted by the authors, the accumulated regret is also not tight and compared to existing results.

While we have discussed some results from online learning in our paper and compared their bounds to our own, we would like to clarify that we did not characterize our regret bound as a weakness. On the contrary, we view it as a key contribution of our work, offering a significant improvement over a straightforward extension of existing results, as detailed in our response to W1.

While it is true that some online learning works have achieved bounds with lower dependence on $T$, these results cannot be directly extended to the unlearning problem without significant adaptation. The unique challenges and objectives of the unlearning problem distinguish it from standard online learning. Firstly, in machine unlearning, the initial model already has comprehensive knowledge about all the training data, including the data to be forgotten.Secondly, the availability of training data in online learning and online unlearning differs. Thirdly, from a practical standpoint, our online unlearning method, SAFE, does not assume any convexity or pseudo-convexity for the training loss. The detailed discussion has been provided in Line 155-161

Our discussion of online learning results in the paper is intended to provide context and insights for readers who may wish to explore these connections further, rather than as a direct comparison.

We hope this response clarifies the novelty and significance of our contribution and provides additional context for our discussion of related literature in online learning. We also remain open to suggestions for how the connections between unlearning and online learning could be better framed in future work.