Certified Unlearning for Neural Networks

Thank you for your time and valuable comments that will allow us to improve our manuscript.

Clarification on Definition 2.1:

We apologize for the confusion caused. We believe that the reviewer misinterpreted our definition. We would like to note that no modification to the training algorithm is required in our work.

Our Definition 2.1 is intended as a general and unifying framework that covers multiple previous definitions of unlearning. We want to clarify that in Definition 2.1. we did not predefine the certifying algorithm $\bar A$ for generality. We only ask for the existence of such a certifying algorithm $\bar A$ and its independence from the dataset $D_f$. Specifically, our definition captures:

• (Ginart et al., 2019; Guo et al., 2019), where the certifying algorithm $\bar A$ equals the training algorithm $A$.
• (Sekhari et al., 2021; Allouah et al., 2024), where $\bar A(.) = U(A(.), . ,∅)$.

In our work we provide certification with $\bar A(.) = U(A(.), . ,\varnothing)$. A similar choice was made in several prior works, such as (Sekhari et al, 2021) and (Allouah et al, 2024), and therefore is not a novelty of our work. Such a choice allows us to prove the unlearning guarantees of our algorithms (3) and (4).

Importantly, our choice of the certifying algorithm $\bar A$ is purely theoretical and does not require running additional computational steps in practice. Thus, there is no practical modification of the original training required. Consequently, comparisons with methods that fundamentally modify training (e.g., SISA or naive DP training) fall outside our experimental setup. We appreciate your suggestion about explicitly clarifying these points in the manuscript. We will revise Definition 2.1 and associated discussions clearly stating how our definition captures prior definitions and the choice of the certifying algorithm $\bar A$.

About Thudi et al. (2022):

We would like to thank the reviewer for pointing to the related work. We will add it to the next version of our paper.

Considering the adversarial setting with server possibly forging unlearning as was done in (Thudi et al, 2022) is an interesting problem but beyond the scope of our work. In our work, we focus on developing the algorithms for how to achieve unlearning in the non-adversarial (honest server) setting, a problem that has previously remained unsolved for general non-convex functions. Providing a certification algorithm for our approach in the adversarial setting is an interesting direction for future work but orthogonal to current work.

Responses to Specific Questions:

1. Accuracy on CIFAR-10 and MNIST: Our reported accuracy is indeed lower than typical ResNet results because we employed much smaller neural networks. Higher-dimensional settings suffer performance degradation similar to standard DP-training methods. We will highlight this in the paper, and we acknowledge that future experiments with larger, state-of-the-art architectures are certainly valuable.

2. Hyperparameter selection: The hyperparameters were tuned based on standard grid search procedures to balance performance guarantees, while strictly following the theoretical guidelines relating the parameters (e.g., Theorem 4.1 indicates the noise magnitude given the number of iterations). We list the result of our grid search in Appendix B. We will provide explicit explanations in the revised manuscript.

We hope that we have successfully clarified any confusion regarding our definition 2.1 and addressed the concerns raised by the reviewer. If this is the case, we kindly ask the reviewer to reconsider their evaluation and raise their score accordingly.

We thank the reviewer for their time and constructive feedback.

1. We acknowledge that our experiments currently focus on fundamental settings (MNIST, CIFAR10), yet our primary contribution lies in providing rigorous theoretical guarantees without restrictive assumptions such as smoothness or convexity.

2. DP-SGD changes the training algorithm fundamentally and, therefore, does not fit into our setting. Moreover, if we were to implement the DP-SGD baseline, we would need the per iteration noise to be scaled linearly with the forget set size, compared to the standard DP training. Since our forget set size is 5000 for CIFAR-10 and 6000 for MNIST, we do not expect any good practical performance. There is also theoretical evidence that unlearning for free via DP is severely limited in high dimensions (Allouah et al, 2024).

3. Including additional experiments varying $\varepsilon$ is a great suggestion. We will include such results clearly in our revised paper. We do not expect any significant difference in the relative performance.

4. We appreciate the suggestion regarding exact unlearning systems, which indeed modify the training algorithm. We are unaware of any exact unlearning system that does not modify original training, except for retraining from scratch. We will add a discussion on this alternative approach to the related work of our paper. The exact unlearning systems typically modify the training, losing the performance quality of the model e.g., SISA (Bourtoule et al., 2019), however, they might be more efficient when unlearning.

We thank the reviewer for their time and constructive feedback.

1. Thanks for pointing to the papers about unlearning for graph neural networks and minmax models. We will add these references to the related works section.

2. We acknowledge that our experiments currently focus on fundamental settings (MNIST, CIFAR10), yet our primary contribution lies in providing rigorous theoretical guarantees without restrictive assumptions such as smoothness or convexity.

3. We will add the explanation of notations $C_0,C_1,C_2, \lambda$, and $\gamma$ to the table caption.

4. Regularization factor $\gamma$: Thank you for raising this question. The regularization factor $\gamma$ plays a crucial role in our theoretical analysis, related to privacy amplification via iteration (see Sec. 4.1), as the required noise magnitude decreases exponentially in the number of iterations $T$ thanks to regularization. In practice, it helps control the norm of the model parameters throughout fine-tuning, which directly influences the amount of noise required per iteration to ensure certified unlearning guarantees. We will clarify this role of $\gamma$ explicitly in the revised manuscript.

We thank the reviewer for the detailed and constructive feedback, and we address the key points below.

1. Baseline Comparisons:

We choose only output perturbation and retraining from scratch since these algorithms are the only baselines in the literature that can achieve certified unlearning without additional assumptions on the loss function or modification of the original training. In more details:

• Newton updates [1]: assume convexity and smoothness of the loss function, therefore, are inapplicable for the unlearning deep neural networks.
• Golatkar et al [2]: impose the smoothness assumption on the loss function, which frequently does not hold in deep learning if activation functions are non-smooth. Moreover, their unlearning definition is based on mutual information, and it is non-trivial how to connect it with our differential privacy-based definition of unlearning.
• Allouah et al [3]: impose additional assumptions of either strong convexity and smoothness or assume smoothness and that the minima is unique and achievable from any initialization. Such assumptions do not hold in the deep learning setting.
• Zhang et al. [4]: require the loss function to be L-smooth, as well as the knowledge of the minimal eigenvalue of the hessian, limiting its applicability to the general deep learning setting.

We are unaware of any other work that can tackle certified unlearning in the same generality as our work without limiting additional assumptions on the loss functions.

We will add this discussion to the next version of our manuscript.

2. Utility-complexity tradeoff:

Thank you for suggesting a discussion of utility-complexity tradeoffs as explored in [1]. However, such tradeoffs typically require strong assumptions such as convexity or smoothness. Given our primary contribution is providing guarantees for general non-convex settings without these assumptions, clearly characterizing utility-complexity tradeoffs becomes inherently challenging—particularly due to issues like the curse of dimensionality and non-smoothness. We will clarify this inherent difficulty in our revised manuscript.

3. Empirical Justifications (Accuracy and AUC of MIA):

Our goal is to provide rigorous theoretical guarantees without imposing restrictive assumptions such as smoothness or knowledge of eigenvalues of Hessian matrices, as required by [2]. Hence, empirical measures such as MIA scores, used to evaluate methods without strong theoretical guarantees, are not directly comparable or necessary in our theoretical setting. Nevertheless, connecting theoretical unlearning guarantees to practical empirical metrics is an intriguing direction for future exploration, but beyond the scope of this work.

4. Accuracy Improvements (Fig. 2):

Our experimental results (Table 2, Figure 1) show consistent improvement over retraining from scratch across all compute budgets and accuracy targets. Notably, Figure 1 illustrates that with a small compute budget, our method improves test accuracy by up to 8%. The improvement is most significant in low-compute settings, while larger compute budgets make retraining from scratch more effective. In Figure 2, where the compute budget is relatively large, the accuracy improvement is less pronounced. Importantly, both our method and retraining from scratch employ fine-tuning on the retained set. Our approach preserves useful information from the trained model, making fine-tuning more effective.

5. Experimental Setup and Practical Settings:

We agree that extending our experimental framework (e.g., sequential or microbatch deletion settings, as suggested by the reviewer) would provide additional practical insights. While our current focus remains on fundamental theoretical generality, we recognize the value of practical validation and will explicitly outline these as future directions.

6. Terminology Clarification:

We acknowledge the confusion caused by unclear terminology ("privacy target," "iteration budget," etc.). Yes, your interpretations are correct—the "privacy target" refers to the "$(\varepsilon, \delta)$-unlearning guarantee," while the "iteration budget" corresponds to the maximum allowed iterations. We will clearly define these terms in the revised manuscript.

References

[1] Guo et al. Certified Data Removal from Machine Learning Models. ICML 2020.

[2] Golatkar et al. Mixed-privacy forgetting in deep networks. ICCV 2021.

[3] Allouah et al. "The Utility and Complexity of In- and Out-of-Distribution Machine Unlearning." ICLR 2025.

[4] Zhang et al. "Towards Certified Unlearning for Deep Neural Networks." ICML 2024.