- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
The paper proposes UNCLE, a certified unlearning method for logistic regression that certifies the Newton-step error inside a local region (an ellipsoid intersected with an box on logits) instead of relying on global strong convexity, and adds Gaussian noise shaped by the retained data. On nine binary tasks at , it achieves higher deletion capacity than Guo et al. (2020) under mild regularization.
Critical strengths
- The local certificate is sound and cheap to check, and it removes the need for strong regularization that makes prior certified methods inaccurate.
- UNCLE consistently beats Guo et al. on all nine datasets with careful tuning of both methods (e.g., IMDb deletion capacity rises from 1 to 100).
Critical weaknesses
- The evaluation is too narrow to support the practical claim: Guo et al. is the only baseline, there is a single operating point with at most a speedup, and no ablation separates the certificate from the noise geometry.
- The theory only proves the guarantee holds, without showing when certification succeeds or what it costs in utility, so the title's claim rests on experiments alone.
Questions for authors
- Did you implement the data-dependent or the worst-case Guo et al. bound? If the latter, much of the reported gap would be in doubt.
- Does Thm. B.2 assume exact minimizers, and are the spectral norms computed as verified upper bounds? A clear fix could raise my Soundness score.
- Can you ablate the certificate with isotropic noise and an ellipsoid-only certificate? Positive results would raise my rating to 3.
- Do the gains hold with hyperparameters chosen without using the test set?
6 comments
Question 1: Nature of Guo et al. bound We implement the data-dependent Guo et al bound (Corollary 1 of their work). We will clarify this point in our paper.
Question 2: Theorem B.2 exact minimizers Theorem B.2 indeed assumes an exact minimizer in the sense that it proves that the output of our unlearning algorithm is statistically similar to outputting the exact minimizer plus noise and that when triggered, a full retrain yields an exact minimizer. Both assumptions are standard (see, e.g., Theorem 3 in Guo et al., 2019; Theorem 3 in Sekhari et al., 2021; Theorem 7 in Zou et al., 2025; and Theorem 2 in Pandey et al., 2026).
The fundamental goal of unlearning is to produce an output that has a limited dependency on the deleted samples. Therefore, a statistical similarity to any function of the retained samples (such as an exact minimizer of their loss) achieves this goal.
Second, the assumption that the full retrain yields an exact minimizer can be avoided in a number of ways (this is also noted by Guo et al. 2019). The simplest approach would be to add a very small additional Gaussian perturbation to the learned coordinates calibrated to the stopping threshold of the training algorithm.
In general, we acknowledge that our experimental implementation which is built on basic python libraries, might overlook important details that could be significant to some security / privacy focused users (e.g., we use numpy randomness and floating point operations, while some more stringent users might require cryptographic randomness or be more sensitive to floating point errors and side channels). We note that both are standard in the literature (e.g., Guo et al. 2019), and fitting for our paper’s goal of providing a qualitative comparison between two unlearning algorithms. Nevertheless, we will include a comprehensive list of these limitations in the final version of our paper.
Question 3: We are working to produce these ablations and will endeavor to post more detailed results and plots here before the end of the discussion period. Preliminary results on isotropic vs non-isotropic noise indicate that our non-isotropic noise improves significantly over isotropic noise in the small- regime, where the scale of the noise is large. Preliminary results on using a purely ellipsoidal certificate vs UNCLE indicate significantly worse deletion capacity for the purely ellipsoidal certificate.
Question 4: Gains on hyperparameters without test set Thank you for the question. This is a general problem with the existing literature: previous papers (e.g., Guo et al. 2019) do not prescribe a specific choice of unlearning hyperparameters (Sekhari et al. 2021 do offer an asymptotic scaling for the hyperparameters, but not an exact recipe). Given that our goal is to provide the most fair comparison possible between our new UNCLE algorithm and the baseline of Guo et al. 2019, our options were:
- Fix the hyperparameters of both algorithms without the test set.
- Fix the hyperparameters of UNCLE without the test set and compare to a test-optimized Guo et al.
- Optimize the hyperparameters of both algorithms.
We felt that option 1 might bias our comparison against Guo et al. (e.g., we would not know if we had made a bad selection of hyperparameters) and option 2 would be clearly biased against UNCLE. We selected option 3 as the least biased comparison between the algorithms. We agree that this evaluation is still limited, since it compares what each algorithm could achieve with optimal hyperparameters, rather than what they would actually achieve with a realistic hyperparameter selection, but even to determine what information should be taken into account in a “realistic” hyperparameter selection procedure seems dependent on details of the deployment context of an unlearning algorithm to which we would like our comparison to remain agnostic. We will make this limitation clearer in the final version of the manuscript.
Thank you for your careful reading and comments on our paper! Indeed, our method effectively adapts to local geometry, allowing us to consistently outperform the Guo et al. approach. We address your identified weaknesses and questions below.
Weakness 1: Comparison exclusively with Guo et al. We agree that a broader empirical evaluation of unlearning algorithms would be a significant contribution that would strengthen our claims. However, given that our submission is not a benchmark paper and our main goal is to introduce a new algorithm, we felt that an empirical evaluation on nine datasets spanning different domains and modalities should suffice and leave the goal of designing more comprehensive benchmarks for future work.
We understand the reviewer’s remark about a 2x speedup as follows – if we choose parameters of an unlearning algorithm so that a full retrain happens 50% of the time, then at best we can save a 2x speedup over fully retraining on every unlearning request. We agree, but the parameters of an unlearning algorithm can be chosen so that a full retrain happens much less frequently; we chose 50% as an illustrative example for figure 1. Our experimental data shows similar gains for UNCLE over Guo et al at 10% and 25% retrain rates as well. We are generating plots to illustrate this, which we will add to our paper, and endeavor to post here before the end of the discussion period.
Regarding the runtime of our certification algorithm, in practice for most datasets the cost of occasionally triggering a full retrain dominated the overall runtime of both algorithms. Therefore, the main computational bottleneck of both algorithms was the retrain rate, so a slower certification that succeeds in a higher fraction of cases would still yield a faster unlearning algorithm overall. As a result, we did not invest significant effort in optimizing the running time of UNCLE and it is entirely possible that the certification times would be diminished by further optimization.
Weakness 2: No provable utility guarantees We agree that having an additional asymptotic utility guarantee would strengthen our claim, however given the ML-focused venue, we believe that an empirical evaluation of utility is more standard. We feel that the unlearning guarantees that we prove are more crucial in this context, because (as we note in line 44-49) heuristic approaches to unlearning often do not hide the unlearned samples from worst-case adversaries.
There are a few types of provable guarantees one could desire from an unlearning algorithm: a) that the unlearning is certifiable, b) how often unlearning can be certified, and c) bounds on the risk. Our theoretical focus is entirely on the former: we show that, no matter what dataset is provided, every run of our algorithm has provable guarantees on the level of unlearning. These guarantees are sufficient to justify the title of the paper. Guarantees of the form of b) and c) would require assumptions on the data distribution, which are unlikely to hold for real-world datasets. Rather than proving results for a contrived setting, we chose instead to demonstrate utility on a diversity of datasets.