acceptodds
Under review as a conference paper at ICLR 2027

Sequential Subspace Noise Injection Prevents Accuracy Collapse in Certified Unlearning

Abstract

Certified unlearning via differential privacy provides formal guarantees but remains impractical due to the severe accuracy collapse observed in current noisy fine-tuning (NFT) approaches. We propose Block-wise Noisy Fine-Tuning, which utilizes sequential subspace noise injection to partition the parameter space into orthogonal blocks and update only one block per step. This modification redistributes the noise budget over time; by restricting perturbations to lower-dimensional subspaces, we significantly reduce per-step distortion and prevent noise from overwhelming the training signal. We extend the privacy analysis to our block-wise schedule, proving that the same privacy budget is retained. Empirical results on image classification benchmarks demonstrate that our approach prevents accuracy collapse, bridging the gap between rigorous guarantees and practical utility.

Primary area:
alignment, fairness, safety, privacy, and societal considerations
Keywords:
certified unlearning, differential privacy

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 2 reviews, above 27% of the others.
Reviewer_gEKUOpenReview ↗
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
  1. 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.

  2. 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
  1. 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.

  2. 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.

  3. 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.

  4. 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.

  5. 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.

  6. 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.

  7. Connection between theoretical analysis and empirical results:** The paper provides theoretical derivations involving quantities such as T(σmin⁡2)T(\sigma_{\min}^{2}), 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
  1. Estimation of Δρ\Delta\rho: Does estimating Δρ\Delta\rho 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?

  2. 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?

  3. Theory versus experiments: How accurately do theoretical quantities such as T(σmin⁡2)T(\sigma_{\min}^{2}) predict the observed experimental behavior? Can the authors provide a direct comparison?

  4. Sequential unlearning: Can the proposed method support successive deletion requests while maintaining its certification guarantees and avoiding accumulated accuracy degradation?

  5. 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

We thank the reviewer for their feedback and suggestions. We have updated the paper, with changes highlighted in blue, and provide our responses below.

W2/Q1: Estimation of Δρ\Delta\rho

As stated in Section 3.2, we treat Δ(ρ)\Delta(\rho) 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.

W3/Q2: Computational efficiency

Thank you for this suggestion. We conducted an expanded wall-clock comparison on ViT-Tiny/CIFAR-10 for k∈2,4,8,16k\in{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.

MethodkConstructionReparam.Noisy phasePost-FTTotalStorage
Random orthogonal20.687±0.0020.066±0.0150.82±0.01109.71±3.32111.29±3.3485.08 MiB
40.696±0.0210.063±0.0001.40±0.03111.62±2.06113.78±2.0785.08 MiB
80.676±0.0150.078±0.0012.83±0.01108.59±3.04112.17±3.0585.08 MiB
160.708±0.0300.106±0.0017.01±0.07108.89±3.23116.72±3.3285.08 MiB
Random permutation20.033±0.0040.086±0.0130.48±0.03107.82±1.10108.42±1.110.36 MiB
40.035±0.0020.097±0.0280.89±0.03107.79±0.73108.81±0.780.36 MiB
80.041±0.0050.089±0.0201.83±0.04107.80±1.73109.76±1.670.36 MiB
160.057±0.0030.114±0.0083.66±0.02106.17±0.31110.00±0.330.36 MiB
Cyclic layer grouping20.004±0.0000.005±0.0000.44±0.01108.29±0.86108.74±0.870.36 MiB
40.005±0.0000.006±0.0000.86±0.03106.83±1.16107.70±1.180.36 MiB
80.008±0.0000.008±0.0001.67±0.05106.63±1.23108.31±1.210.36 MiB
160.012±0.0000.013±0.0003.51±0.05106.08±1.60109.61±1.610.36 MiB
NFT–––0.39±0.04111.42±4.00111.81±4.01–
Retraining––––2172.35±18.842172.35±18.84–

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.

Q3: Theory versus experiments

The theoretical quantity T(σmin⁡2)T(\sigma_{\min}^2) 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=2T=2 noisy steps for standard NFT and T=2T=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.

Q4/W4: Sequential unlearning

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.

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.

Reviewer_WaMhOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

The paper proposes Block-wise Noisy Fine-Tuning for certified machine unlearning. It updates orthogonal parameter blocks sequentially with clipped retained-data gradients and Gaussian noise, followed by full-model fine-tuning. It also replaces the initial worst-case distance bound with a calibrated proximity parameter. A shifted Renyi-divergence argument is intended to preserve the unlearning budget. A quadratic example motivates sequential correction, and image-classification experiments show improved utility over full-space noisy fine-tuning.

Critical strengths
  1. Sequential block updates offer a useful way to distribute perturbations over time while recomputing gradients. The quadratic example in Appendix K gives a concrete explanation of how later updates can correct earlier perturbations under its stated assumptions.

  2. The experiments include comparisons using the same empirical proximity parameter and investigate different block constructions. These help isolate the scheduling effect from the effect of tightening the initial-distance parameter. Appendix I.1 also explicitly acknowledges that the experimental calibration is not a formal confidence bound.

Critical weaknesses
  1. The high-probability proximity condition does not establish the unconditional certificate. Definition 3.3 bounds the initial distance with probability at least 1-rho, whereas Definition 4.3 requires an almost-sure coupling bound. Algorithm 1 substitutes Delta(rho)/2 for C0 and removes initial clipping, but the final budget in Theorem 4.1/Appendix F.2 does not account for rho. The discussion of a conditional guarantee does not supply the missing unconditional argument. For example, if a common coupling decomposes the two output laws into a shared good-event mass of at least 1-rho and the conditional laws satisfy a two-sided (epsilon, delta_0) guarantee, a standard mixture argument gives delta_total <= delta_0 + rho. Those premises must be established. Calibration confidence beta must also be treated explicitly, either as a separate confidence statement or through appropriate failure accounting. The maximum of ten paired runs, acknowledged to be empirical, does not establish the required quantile/confidence guarantee.

  2. The blockwise proof does not justify the same-budget claim as written. Lemma F.3 states a conclusion for a general shift vector, while its proof handles a shift initially supported only on the updated block. Under the displayed whole-space Lipschitz premise, the general conclusion is false: psi(x1,x2)=(x1+x2,x2) freezes block 2 and is Lipschitz with constant below 2, but maps points separated by (0,1) to points separated by (1,1). A permitted zero shift in block 1 therefore cannot remain zero. This counterexample concerns the stated lemma, not an impossibility result for the algorithm. A componentwise bound for the actual clipped update may repair it. Separately, approximate balance of random block norms does not imply a deterministic initial-distance bound Delta/sqrt(k) for every block. A rigorous allocation or a total squared-cost argument is needed. The RDP-to-DP conversion in Eq. (38) is not itself my objection. These gaps affect the central certificate; whether the same-budget utility gains survive their repair remains unresolved.

Questions for authors
  1. Please provide a complete certificate connecting the actual proximity/calibration assumptions to the final two-sided unlearning guarantee, including rho, beta, and the final delta. State whether the guarantee holds for each fixed deletion request or only over a specified request distribution. Specify the coupling and verify that its retained-model marginal matches the claimed retained-data reference training procedure. If the result is only conditional, please narrow the certification claims accordingly.

  2. Please replace Lemma F.3 with conditions satisfied by the actual update and give the full induction for arbitrary initial block shifts. A possible starting point, when 0 <= gammalambda <= 1, is ||psi_i(x)-psi_i(y)|| <= (1-gammalambda)||x_i-y_i|| + 2gammaC1_i, with all other blocks frozen and the clipping threshold C1_i actually enforced. Please show how all shifts reach zero and how the total Renyi cost is bounded without assuming equal initial block norms.

  3. Please provide the calibration distances/protocol and an auditable parameter table for the principal experiments: Delta, clipping thresholds, q, per-block Renyi costs, sigma^2, integer T, gamma, lambda, and the actual final delta. Check the noise condition at the realized integer T, and reconcile the delta values in Figures 3/6 with the procedure/Table 5. Recompute both methods' certificates under the corrected assumptions. If existing trajectories certify only weaker budgets, report those budgets; to retain the same-budget utility claim, compare both methods at the same valid final budget, rerunning affected configurations if needed. These requests concern the existing central claim, rather than additional application benchmarks.

2 comments

We thank the reviewer for their feedback and suggestions. We have updated the paper, with changes highlighted in blue, and provide our responses below.

W1/Q1: Unconditional guarantee

Theoretical guarantee. The analysis establishes a two-sided (ε,δ0)(\varepsilon,\delta_0) guarantee conditional on ∥x^−x^′∥≤Δ(ρ)\|\hat x-\hat x'\|\leq\Delta(\rho). Accounting for the failure probability ρ\rho yields an unconditional (ε,δ0+ρ)(\varepsilon,\delta_0+\rho) guarantee. A valid calibration with confidence 1−β1-\beta establishes this guarantee with the same confidence, or gives (ε,δ0+ρ+β)(\varepsilon,\delta_0+\rho+\beta) when calibration randomness is included. We have made this distinction explicit in Theorem 4.1 and Section 5.

Coupling. For each fixed DfD_f, we couple the training runs using shared initialization and training order, replacing each forgotten example in the reference run with an independent sample from DrD_r. This is distributionally equivalent to randomly permuting DrD_r and inserting additional retained samples at uniformly random positions. Thus, the reference training procedure depends only on DrD_r and the original dataset size, not on the forgotten examples, making it a valid retained-data reference for certification. Although its training distribution differs from standard retraining on DrD_r, we empirically observe comparable predictive accuracy.

Calibration confidence. As clarified in Appendix I.1, a valid calibration procedure provides the proximity bound with confidence 1−β1-\beta, and the (ε,δ0+ρ)(\varepsilon,\delta_0+\rho) guarantee holds with the same confidence. In our experiments, the maximum over 10 coupled runs is an empirical estimate without formal values of ρ\rho or β\beta. Both NFT and Block-wise NFT use this same estimate and are compared under the same conditional privacy budget. If the estimate is later revised upward, the certified budget can be recalculated without changing the optimization trajectories or the reported accuracy results (Appendix H).

W2.1/Q2: Lemma F.3

We thank the reviewer for pointing out that the conditions in Lemma F.3 were not sufficiently precise. We have clarified the componentwise condition for the active block, as suggested. We have also expanded the proof in Appendix F.2 to explicitly show how the two decomposed lemmas are applied sequentially, including the induction that eliminates the shifts in all blocks.

W2.2: Same-budget guarantee for Block-wise NFT

We thank the reviewer for pointing out that approximate balance does not justify a deterministic per-block bound of Δ(ρ)/k\Delta(\rho)/\sqrt{k}. We have clarified this argument and added Proposition 4.6 (Section 4.1, proof in Appendix F.3). Rather than assuming equal initial block discrepancies, we use orthogonality:

= \|\hat x-\hat x'\|_2^2 \leq \Delta(\rho)^2.$$ Together with $C_{1,i}=C_1/\sqrt{k}$ and Cauchy–Schwarz, this shows that the total Rényi cost is bounded by the same expression as in standard NFT. Thus, the original noise calibration remains valid without requiring individual bounds on $\Delta_i$, and the algorithm and reported experimental trajectories remain unchanged. > **Q3: Experimental calibration** The calibration protocol and experimental parameters are detailed in Appendix I.2 and Table 5. For each target $(\varepsilon,\delta)$, we select the Rényi order $q$ and the corresponding $\varepsilon^{\text{renyi}}$ to minimize the required NFT noise variance, as described in Appendix G.1. The number of iterations $T$ is determined by the certification analysis, with integer rounding. Both NFT and Block-wise NFT use the same global calibration parameters; the latter applies $C_{1,i}=C_1/\sqrt{k}$. As established by Proposition 4.6, this preserves the same total Rényi divergence bound without changing the experimental procedure. 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.

Thank you for the revisions. The componentwise bound and Proposition 4.6 resolve my concerns about cross-block dependence and unequal initial block discrepancies.

The remaining issue is how the reported experiments instantiate the certificate. Table 5 omits the realized qq and σ2\sigma^2, while Figures 3 and 6 use δ=10−3\delta=10^{-3} rather than 10−510^{-5}. For identical inputs, the released compute_sigma returns one quarter of the variance in Eq. (30). The default M=2,T=2M=2,T=2 path also performs one clipped-gradient step followed by one noise-only step. Please provide the executed configurations and recomputed budgets for both methods, reconciling the noise scale, integer-step schedule, and per-block clipping. Please also align the retained-only reference in Definition 2.1 with the replacement-based coupling described in your response. The clarification that the empirical proximity estimate supports a conditional guarantee is helpful, but the utility comparison at a common valid budget remains unverified. I will retain my score of 2.

Comments on the paper

2 comments

We thank the reviewer for their feedback and suggestions. We have updated the paper, with changes highlighted in blue, and provide our responses below.

Q1/W1: Proximity-based certificate

We thank the reviewer for raising this point. As detailed in our response to Reviewer WaMh ("W1/Q1: Unconditional guarantee"), the conditional (ε,δ0)(\varepsilon,\delta_0) guarantee yields an unconditional (ε,δ0+ρ)(\varepsilon,\delta_0+\rho) guarantee, with calibration confidence 1−β1-\beta treated separately. We also clarify that the experimental estimates of Δ(ρ)\Delta(\rho) do not establish formal values of ρ\rho or β\beta, and the reported budgets are conditional on the assumed proximity bound.

Q2/W2: Same-budget guarantee for Block-wise NFT

We thank the reviewer for this observation. As detailed in our responses to Reviewer WaMh ("W2.2: Same-budget guarantee for Block-wise NFT"), we have clarified the block-wise proof in Appendix F.2, including the dependence of gradients on other blocks.

Importantly, our revised analysis does not assume individual initial-distance bounds of Δ(ρ)/k\Delta(\rho)/\sqrt{k}. Instead, Proposition 4.6 (Section 4.1, proof in Appendix F.3) uses the total squared discrepancy to establish the same Rényi bound as standard NFT, without requiring a concentration argument. In our experiments, all blocks use the same noise variance and number of steps calibrated from the global parameters, with clipping thresholds C1,i=C1/kC_{1,i}=C_1/\sqrt{k}. The per-block Rényi costs are not assumed equal; their sum is bounded by the standard NFT budget.

Q3: conclusion clarification

Thank you for pointing this out. The reference to membership-inference auditing was included in error, and we have removed it from the conclusion.

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.

Reviewer_MC5HOpenReview ↗

Raised the score from 1 to 2 (weak rejection).

Thank you for the detailed response and for revising the theoretical analysis. The revised statement of the proximity-based guarantee addresses the ambiguity I raised: the distinction between the conditional (ε,δ0)(\varepsilon,\delta_0) result, the unconditional (ε,δ0+ρ)(\varepsilon,\delta_0+\rho) guarantee, and the separate calibration confidence is now much clearer.

The new total-squared-discrepancy argument in Proposition 4.6 also appears to address my main objection to the block-wise budget analysis. In particular, it avoids assuming a deterministic Δ(ρ)/k\Delta(\rho)/\sqrt{k} initial-distance bound for every block and instead controls the sum of the per-block Rényi costs. I also appreciate the clarification concerning cross-block gradient dependence and the removal of the unsupported membership-inference statement.

One important limitation remains: the experimental estimate based on ten coupled runs does not establish formal values of ρ\rho or β\beta. Consequently, the reported experimental budgets should still be interpreted as conditional on the assumed proximity bound rather than as unconditional certified budgets. My question about performance at substantially smaller values of ε\varepsilon also remains unanswered.

Overall, the revision substantially improves the soundness and scope of the claims, although the empirical certification and practical strength of the reported guarantees remain limited. In light of these changes, I have raised my score from 1 to 2 (weak rejection).

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.