- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper builds upon noisy fine-tuning (NFT) approaches in certified machine unlearning. In the standard NFT setting, the algorithm starts from a model trained on the full dataset and performs noisy fine-tuning using the retained data. However, injecting all the required noise at once can cause a substantial drop in test accuracy, from which the model may struggle to recover even after extended fine-tuning.
To address this issue, the authors propose a sequential subspace noise injection strategy. Specifically, they first orthogonalize the weight matrices and then inject noise gradually, one block at a time, rather than perturbing the entire model at once. The objective is to improve accuracy recovery while maintaining the ((\epsilon,\delta))-certified unlearning guarantee.
Critical strengths
-
The paper is well motivated within the existing literature on noisy fine-tuning for certified machine unlearning. It identifies an important practical limitation of conventional NFT approaches.
-
The problem statement is reasonable, and the authors provide empirical evidence that injecting all the noise at once can lead to a substantial accuracy drop. The proposed sequential injection strategy is an intuitive approach to mitigating this issue.
Critical weaknesses
-
Clarity and presentation: The paper is somewhat difficult to follow, particularly in its mathematical derivations and algorithmic descriptions. Several concepts and notations appear to be introduced with the assumption that readers are already familiar with the underlying formulation. Although the authors provide additional notation in the appendix, the main paper would benefit from clearer definitions and more intuitive explanations of the key steps. This would make the proposed method easier to understand and evaluate.
-
Practicality of estimating (\Delta\rho): Line 5 of Algorithm 1 replaces the clipping constant (C_0) with (\Delta\rho/2). However, my understanding is that estimating (\Delta\rho), which represents the distance between model parameters, requires running coupled training procedures on the full and retained datasets. The authors mention performing 10 such paired runs with fixed random seeds. This raises an important concern about the practical efficiency of the proposed method. If estimating (\Delta\rho) requires training models on both the full and retained datasets for every unlearning request, the computational overhead could undermine the primary motivation for efficient unlearning. Furthermore, from the plots (e.g., Figure 12), the parameter distance appears to keep increasing over training. It is therefore unclear how the authors determine when to stop the estimation procedure. Is the stopping criterion based on accuracy saturation, a fixed number of epochs, or some other convergence criterion? If only a small number of epochs is sufficient, how is that number determined, and how sensitive is the resulting estimate to the training duration? The authors should clarify whether this estimation is performed for every unlearning request or can be reused, how many training epochs are required, and how its computational cost compares with full retraining. This is particularly important because the efficiency of the proposed method depends on the practicality of this estimation step.
-
Computational overhead of orthogonalization: Another concern is the computational cost associated with orthogonalizing large weight matrices. Although Table 1 provides a theoretical complexity analysis, an empirical wall-clock comparison would be more informative. In particular, for the ViT-Tiny experiment, I would like to see the total runtime of full retraining, conventional NFT, and the proposed block-wise NFT with different values of (k). This comparison should include the overhead of orthogonalization and other preprocessing steps, as well as any additional estimation required by the method. If these matrix operations introduce substantial computational overhead, the practical advantage of the proposed method over conventional NFT or full retraining may be limited.
-
Sequential unlearning requests: It is unclear how the proposed method behaves under sequential unlearning requests. For example, suppose a user requests that their data be removed not only from the trained model but also from the underlying training dataset. For subsequent deletion requests, the original full-data model may no longer be an appropriate starting point, and the algorithm may need to operate on a previously unlearned model. In such a setting, approximation errors and injected noise could potentially accumulate across successive unlearning operations, leading to further accuracy degradation. The authors should discuss whether the certification guarantees and accuracy recovery properties extend to sequential unlearning, and ideally provide experiments evaluating this setting.
-
Limited ablation on deletion ratios: A more comprehensive evaluation across different percentages of deleted training data is needed. In particular, the authors should investigate how the proposed method behaves as the deletion ratio increases, both for one-shot deletion and, if supported, sequential deletion requests. This would help establish the robustness of the method under different unlearning workloads.
-
Incomplete evaluation metrics: The experimental evaluation appears to focus primarily on test accuracy. However, machine unlearning studies commonly report additional metrics, including forget-set accuracy, retain-set accuracy, and membership inference attack (MIA) performance. Although these empirical metrics do not replace or establish a formal certified unlearning guarantee, they provide useful complementary evidence about the behavior of the unlearned model. Reporting only test accuracy makes it difficult to determine whether the proposed sequential noise injection strategy introduces other trade-offs. The authors should provide a more comprehensive evaluation of retained performance and forgetting behavior.
-
Connection between theoretical analysis and empirical results:** The paper provides theoretical derivations involving quantities such as , but their relationship to the experimental results is not sufficiently demonstrated. In particular, it would be useful to investigate how accurately these theoretical predictions reflect the observed behavior during unlearning. For example, how closely does the theoretically predicted quantity match its empirical counterpart across different noise levels, block sizes, and training settings? Are the theoretical estimates tight, or are they overly conservative in practice? A direct comparison between the theoretical predictions and experimentally measured values would help establish the practical relevance of the analysis and provide stronger evidence for the proposed method.
Questions for authors
-
Estimation of : Does estimating require coupled training on the full and retained datasets for every unlearning request? How is the stopping point determined, and what is the associated computational overhead?
-
Computational efficiency: Can the authors provide wall-clock comparisons between full retraining, standard NFT, and the proposed method with different block sizes, including orthogonalization and estimation overhead?
-
Theory versus experiments: How accurately do theoretical quantities such as predict the observed experimental behavior? Can the authors provide a direct comparison?
-
Sequential unlearning: Can the proposed method support successive deletion requests while maintaining its certification guarantees and avoiding accumulated accuracy degradation?
-
Additional evaluation: Can the authors report results across different deletion ratios and include retain/forget accuracy and MIA metrics to complement test accuracy?
Please also see the Weaknesses section for further details and context regarding these questions.
2 comments
Thank you for the detailed rebuttal and additional experiments. I appreciate the new wall-clock comparisons, which substantially address my concern regarding computational efficiency. The clarification regarding the role of the theoretical bounds is also helpful.
However, some important concerns remain. In particular, the estimation of the proximity bound still relies on empirical calibration without a formal statistical guarantee, and the associated overhead is excluded from the runtime comparison. The current certification analysis also does not support successive deletion requests. Furthermore, the additional evaluations regarding deletion ratios, retain/forget accuracy, and MIA remain unaddressed.
Overall, while the rebuttal improves my understanding of the method and addresses some concerns, I do not think it sufficiently resolves the main limitations regarding practical certification and evaluation. Therefore, I will maintain my original rating.
We thank the reviewer for their feedback and suggestions. We have updated the paper, with changes highlighted in blue, and provide our responses below.
As stated in Section 3.2, we treat Δ(ρ) as a conditioning parameter and interpret both our theoretical and experimental results for a given proximity bound. Our main contribution is to improve the utility of noisy fine-tuning under this bound, rather than to develop an optimal procedure for estimating it.
In our experiments, we obtain a practical estimate from coupled training runs. The discrepancy is measured at the training checkpoint used to initialize unlearning; Figures 8–13 illustrate its evolution during training, rather than defining a separate stopping criterion. As discussed in Section 4.3 and Appendix I.1, we distinguish this empirical estimate from a formal statistical confidence bound. Calibration can be performed in advance and reused within a fixed experimental setting, rather than repeated for every unlearning run. We agree that developing more efficient and statistically rigorous proximity estimation procedures is an important direction for future work.
Thank you for this suggestion. We conducted an expanded wall-clock comparison on ViT-Tiny/CIFAR-10 for k∈2,4,8,16, including block construction, orthogonalization, reparameterization, noisy updates, and post-unlearning fine-tuning. The results are reported below and have also been added to Appendix J.2.
Across all block sizes and constructions, the end-to-end runtime remains comparable to standard NFT and substantially below full retraining. In particular, the orthogonalization overhead is below one second. The reported runtimes exclude the separate proximity-calibration procedure, which we discuss in our response to W2/Q1.
The theoretical quantity T(σmin2) characterizes the number of noisy updates required by the certification analysis, rather than predicting the model's accuracy or its recovery dynamics. In our experiments, the noise variance and the number of noisy steps are determined from the theoretical calibration before evaluating model performance, rather than fitted to the observed accuracy curves.
For the principal configurations in Table 5, we use T=2 noisy steps for standard NFT and T=2 steps per block for Block-wise NFT. Figure 3 then shows the observed accuracy trajectories, including the noisy phase and subsequent fine-tuning. Thus, the theory determines the certified update schedule, while the experiments evaluate its effect on utility. In our experiments, we use the theoretical analysis to select the noise scale and the number of noisy updates for a given privacy budget. We then evaluate the resulting model accuracy empirically. Thus, the theory determines the certification-compatible parameters, while the experiments assess the utility achieved under these parameters.
Our current analysis considers a single deletion request, with sequential updates referring to the processing of parameter blocks rather than successive deletion requests. Extending the certification analysis to multiple deletion requests, together with studying cumulative utility degradation, is an interesting direction beyond the scope of this work.
We hope our responses and the changes to the paper are helpful. We would appreciate it if you could reconsider your score in light of these changes.