A Certified Unlearning Approach without Access to Source Data

We thank the reviewer for their constructive comments. Please see our responses below.

About the datasets: It is worth noting that prior works in certified unlearning have similarly employed datasets such as CIFAR‑10 and StanfordDogs [R5-R7]. Our primary objective in using these datasets was to provide a controlled experimental validation of our theoretical results rather than to claim state‑of‑the‑art empirical performance.The fact that our method performs comparably to fully‑retrained models confirms that our unlearning approach preserves model utility while offering certification guarantees.

[R5] A. Golatkar, A. Achille, A. Ravichandran, M. Polito, and S. Soatto, ‘Mixed-Privacy Forgetting in Deep Networks’, in Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), 2021, pp. 792–801.

[R6] E. Chien, H. P. Wang, Z. Chen, and P. Li, ‘Langevin Unlearning: A New Perspective of Noisy Gradient Descent for Machine Unlearning’, in The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024.

[R7] B. Zhang, Y. Dong, T. Wang, and J. Li, ‘Towards Certified Unlearning for Deep Neural Networks’, in Forty-first International Conference on Machine Learning, 2024.

Difference between DP and DP-inspired unlearning: The key difference between DP and DP‑inspired unlearning lies in the nature of their statistical guarantees. In traditional Differential Privacy (DP), the guarantee is based on the statistical distance between the output distributions of an algorithm when run on two adjacent datasets. In contrast, DP‑inspired unlearning focuses on ensuring statistical indistinguishability between the output of a fully‑retrained model and the output of the unlearning mechanism. This distinction means that while both approaches aim to limit the leakage of sensitive information, DP‑inspired unlearning calibrates noise based on the distance between these two different mechanisms rather than on adjacent datasets. We elaborate on this point further in Appendix B.

Typo: Thanks for pointing this, we will fix this in the revised version.

We thank the reviewer for their constructive comments.

Justification of the motivation: In our experiments, most surrogate datasets were synthetically generated to provide a controlled environment for evaluating our theoretical results. However, for real-world applications, surrogate datasets need not be generated purely synthetically. In practice, surrogate data can be obtained from publicly available sources or even generated by leveraging the trained model to capture aspects of the original distribution.

Regarding the motivation, there exist numerous real-world scenarios where the original dataset is no longer accessible. For example, regulatory policies may require data deletion after a fixed retention period, while models trained on this data continue to be deployed. Similarly, in collaborative or federated learning settings, data privacy constraints often prevent access to the full original dataset, leaving only a surrogate or limited statistical summary available.

Finally, we clarify the assumption regarding access to the original training dataset. In our framework, we assume that the unlearning mechanism does not have direct access to the retain portion of the original dataset ($\mathcal{D}_r$). It only has access to the samples to be forgotten ($\mathcal{D}_u$), which may for instance be provided by a specific user. Although one might expect that having access to the forget samples ($\mathcal{D}_u$) would simplify approximating the Hessian for the retained data ($\mathcal{D}_r$), in practice, this is nontrivial. The distribution of $\mathcal{D}_u$ can differ significantly from that of $\mathcal{D}_r$ (as in class unlearning), making Hessian estimation challenging when relying solely on the forget samples. This reflects our intent to keep the unlearning framework broadly applicable.

Assumptions on loss functions and practicality: Yes, we agree with the reviewer that Assumption 4.1 is indeed strong; while it may not hold for all deep neural network loss functions, it is important for tractability of the theoretical analyses of second-order unlearning methods which is a key first step towards the analysis of the more general setting. To satisfy these conditions while still achieving competitive performance in practice, we leverage a mixed linear network [R4] implementation. Mixed linear networks combine the simplicity and theoretical tractability of linear models with select non-linear components, which enables them to meet the convexity and smoothness criteria. As demonstrated in the table below, our implementation achieves a significant unlearning performance depending on the accuracy metrics while also achieving significant training accuracy. Extending our theoretical guarantees to general non-convex settings in the source-free setting is an important future direction.

[R4] A. Golatkar, A. Achille, A. Ravichandran, M. Polito, and S. Soatto, ‘Mixed-Privacy Forgetting in Deep Networks’, in Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), 2021, pp. 792–801.

Class unlearning: Thanks for raising this interesting question. Yes, it is possible to unlearn an entire class. We conducted experiments to unlearn class 0 from the CIFAR10 dataset, using our mixed linear network implementation, which satisfies the convexity assumptions while maintaining competitive accuracy. We show our results in the second row of the table above. We observe that we can effectively remove the influence of the targeted class while preserving performance on the remaining data. We believe the proposed method not only facilitates class unlearning but also can be extended to tackle scenarios such as unlearning all poisoned samples.

Original model results: We added the original model results in every table we provided in this rebuttal (tables under Reviewer a1HE and the table provided above).

Experiments with different seeds: To address the inherent randomness introduced by noise calibration, we conducted our experiments over multiple runs and report the averaged values with their error margins (table under Reviewer a1HE, the table provided above, Figure 1-4 and Table 1-2 in link). This evaluation demonstrates that our method is robust with performance variations well within acceptable margins.

Typo: Thanks, we will fix this in the revised version.

We thank the reviewer for their constructive comments.

Experiments with different forget ratios: We conducted extensive experiments on the StanfordDogs dataset with varying forget ratios to assess how forget set ratio impacts unlearning. The results in the table below show that our method Unlearn(-) scales well across different forget set ratios (FR). Also, results under the MIA and RT columns indicate that similar unlearning performance is achieved across FR with Unlearn(+) (the model achieved after unlearning with the exact data samples) and Retrain models. These findings confirm the robustness of our approach.

Justification of the heuristic method and practicality: We conducted experiments on both synthetic and real datasets to justify the heuristic KL‐divergence estimation (Sec. 4.2) and the corresponding empirical unlearning error $\hat{\Delta}$. In Figs. 1 and 3 (link), we plot both the “exact” and “approximated” results (our heuristic method) for the KL‐divergence and the respective noise $\sigma$. For the synthetic data experiments, the exact KL divergence is computed using its closed-form for Gaussians. For real data experiments, since the exact KL divergence was not available, we estimated it using the Donsker-Varadhan bound as a reference, leveraging both exact and surrogate data samples. Figs. 1–4 and Tables 1–2 (link) show our approximations closely match exact values.

To address whether the approximate certificate is practically useful, we report both $\Delta$ (exact) and $\hat{\Delta}$. The results confirm that even if the estimated bounds grow, model performance aligns with Unlearn(+). For completeness, we ran multiple trials with different seeds, included error bars in all figures, and included error margins into the tables demonstrating consistency across repeated experiments. Overall, these findings validate the heuristic’s reliability and practical utility in estimating KL‐divergence and unlearning error.

Non-vacuous upper bound for statistical distances: While a trivial upper bound on the TV distance is available ($TV(\rho \| \nu) \leq 2$), extending this to a non-vacuous bound on the KL divergence is challenging without further assumptions on the retained data. Our primary goal was to maintain generality and avoid introducing new restrictions with the assumptions about the data distributions. To that end, we proposed a heuristic method to approximate the KL distance using the model parameters. Using this approximation, showed that as the distance between exact and surrogate distributions increases, achieving certified unlearning requires adding more noise calibrated using Corollary 4.4. Figs. 1 and 3 (link) further show that our method can approximate the exact KL distance using only the model parameters, without access to the original data samples, making it suitable for source-free unlearning.

Limitations: Regarding the assumptions, we build on the mixed linear network which enables us to meet the strong convexity criteria while also achieving competitive accuracy results. We believe that this choice satisfies both the necessary theoretical conditions and provides a solid foundation for our experimental evaluation. Please also see our response to Reviewer mUHz, where we provide further details about this network under "Assumptions on loss functions and practicality".

While our current formulation focuses on single-batch unlearning for classification models as noted by the reviewer, this also provides an important and tractable first step. Extending our mechanisms to sequential unlearning requires new theoretical insights on the certification budget considering the noise added after each unlearning step [R2, R3]. This is an interesting future direction we are actively exploring.

[R2] E. Chien, H. P. Wang, Z. Chen, and P. Li, ‘Langevin Unlearning: A New Perspective of Noisy Gradient Descent for Machine Unlearning’, in The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024.

[R3] B. Zhang, Y. Dong, T. Wang, and J. Li, ‘Towards Certified Unlearning for Deep Neural Networks’, in Forty-first International Conference on Machine Learning, 2024.

We thank the reviewer for their constructive comments. Please see our responses below.

Experiments on complex models: Our main focus in the current work was the theoretical foundations, to explore provable certified unlearning mechanisms in the source-free setting, and provide rigorous theoretical guarantees for certified unlearning using surrogate datasets. To that end, our empirical evaluations ranged - as a proof-of-concept - from simple linear models to networks with one or two convolutional layers (see Table 5 in the paper) that demonstrate that our certified unlearning mechanism maintains competitive performance across various complexity levels.

To further address the concern about moderately complex architectures, we introduce in this rebuttal a mixed linear network implementation. This model satisfies the strong convexity assumptions made in our analysis—particularly regarding the loss function—and provides a more expressive and realistic evaluation setting than standard linear models. Despite its increased complexity, it remains analytically tractable and directly reflects the practical applicability of our theory. We gave more details about mixed linear networs in our responses to Reviewer mUHz under “Assumptions on loss functions and practicality”. As shown in the table given under the same response, our certified unlearning mechanism performs effectively in this mixed linear setting. This strengthens our claim that the theoretical results extend meaningfully to models beyond simplistic settings, including those with moderate complexity.

In response to the reviewer’s comment, we evaluate our method on a ResNet-18 model by computing the full-model Hessian using the Conjugate Gradient method. The results are shown in the table below. We observe a performance drop on the forget set after the unlearning update for both Unlearn (+) (retrained with exact data) and Unlearn (−) (our method). Importantly, Unlearn (−) performs comparably to Unlearn (+), demonstrating that our method achieves similar unlearning behavior without access to the retain dataset, even on complex models like ResNet-18.

Noise variance and forget score:

• Noise Variance ($\sigma$): Our method derives $\sigma$ based on the theoretical bounds provided in Theorems 4.2 and 4.3 using an upper bound on the statistical distance between the true data distribution and the surrogate distribution, which control the term $\|w_{r}^* - \hat{w}_r\|_2$ (see Equation (8)). In practice, when we do not know the exact upper bound on the statistical distance between the two datasets, we estimate it using the heuristic method explained in Sec. 4, and this estimate is then substituted into Equation (6) to compute the calibrated noise variance. To do so, we first sample from the trained model parameters using Langevin dynamics (details in App. D3) and then estimate the KL distance using the Donsker-Varadhan bound (Equation (12)).
• Forget Scores: To quantify the quality of forgetting, we compute per-example $\epsilon$ estimates that capture the strength of an optimal attacker's ability to distinguish between the outputs of the unlearned model and a model retrained from scratch. These per-example estimated $\epsilon$ values are then aggregated into an overall forget score using a binning approach to ensure granularity and robustness. Our forget score methodology and implementation follows along the lines of Triantafillou et al. [R1], and we report three variants: “FS1(+)” (using noise calibrated with the original data), "FS1(-)” (using noise calibrated with the surrogate data, our method), and “FS2(-)” (adding noise calibrated with the original data but applied without re-calibration to the surrogate data).

We hope this clarifies how the noise variance and forget scores are computed for the datasets in Figure 2 in our paper.

Finally, we agree with the reviewer’s suggestion on moving the surrogate dataset part earlier, we will present this part earlier in the revised version.

[R1] Triantafillou, E., Kairouz, P., Pedregosa, F., Hayes, J., Kurmanji, M., Zhao, K., Dumoulin, V., Junior, J. J., Mitliagkas, I., Wan, J., et al. Are we making progress in unlearning? Findings from the first NeurIPS unlearning competition, arXiv:2406.09073, 2024.