acceptodds
Under review as a conference paper at ICLR 2027

Certified Unlearning with Mild Regularization and non-Isotropic Data

Abstract

The growing demand for privacy and increase in regulatory requirements have made the problem of honoring requests to be forgotten increasingly important. This motivates the problem of machine unlearning: simulating the effect of the removal of a given set of samples without triggering a full retrain. Existing methods for provable machine unlearning typically combine a fast but approximate update such as a single Newton step, with noise calibrated to an upper bound on its distance from the ideal unlearned model. However, even for the relatively simple case of logistic regression, existing certified unlearning algorithms either come at a severe cost to the model's predictive power, or often trigger a retrain even for small removal requests. We show that these limitations stem from a dependence on Newton step error bounds that require very strong regularization (resulting in a significant bias), and do not adapt to the geometry of the data (making the noise more detrimental to the model's predictions). We introduce UNCLE (Unlearning Certifiably via Local Estimates) – a new algorithm for certified unlearning, which overcomes both of these issues. We obtain these improvements by applying a novel method for bounding the distance of any initial estimate from the ideal unlearned model, using only local properties of the loss landscape.

Primary area:
learning theory
Keywords:
machine unlearning, certified unlearning, logistic regression, generalized linear models, data attribution, Newton step, privacy

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_Up4eOpenReview ↗
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 ℓ∞\ell_\infty box on logits) instead of relying on global strong convexity, and adds Gaussian noise shaped by the retained data. On nine binary tasks at ε=1\varepsilon=1, it achieves higher deletion capacity than Guo et al. (2020) under mild regularization.

Critical strengths
  1. The local certificate is sound and cheap to check, and it removes the need for strong regularization that makes prior certified methods inaccurate.
  2. 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
  1. 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 2×2\times speedup, and no ablation separates the certificate from the noise geometry.
  2. 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
  1. 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.
  2. 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.
  3. Can you ablate the certificate with isotropic noise and an ellipsoid-only certificate? Positive results would raise my rating to 3.
  4. Do the gains hold with hyperparameters chosen without using the test set?
6 comments

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.

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-ϵ\epsilon 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.

Reviewer_gJKVOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
1
Soundness
2(+1)
Read review
Paper summary

This paper studies certified machine unlearning, building upon the foundational work of Guo et al., particularly in the setting of linear classifiers with logistic loss. The authors argue that existing certified unlearning approaches suffer from two major limitations: (1) they can lead to degraded test accuracy due to the need for strong regularization, and (2) they may require more frequent retraining from scratch because their certification bounds are overly conservative and do not adequately account for the geometry of the data.

To address these issues, the authors propose UNCLE, an algorithm designed to improve the trade-off between predictive performance and the frequency of retraining. The main idea is to derive tighter bounds on the approximation error between the estimated unlearned model and the ideal retrained model by exploiting local properties of the loss landscape, rather than relying primarily on global strong convexity assumptions.

Critical strengths
  1. Addresses an important theoretical limitation. The paper tackles a relatively overlooked issue in certified machine unlearning: the trade-off between predictive accuracy and the frequency of retraining triggered by certification requirements. In particular, the authors investigate how existing analyses depend on strong convexity assumptions, which can necessitate excessive regularization. The proposed approach, which exploits local loss geometry to enable milder regularization, is theoretically interesting and potentially valuable.

  2. Relevance to the broader development of machine unlearning. Fundamental theoretical studies of this kind are important for advancing our understanding of certified unlearning. Although the current analysis is limited to relatively simple models, developing tighter certification guarantees could eventually contribute to more practical unlearning methods. This direction is particularly relevant given the increasing importance of machine unlearning for large-scale models, including deep neural networks and LLMs.

Critical weaknesses
  1. The paper is difficult to follow, with several gaps in exposition and coherence. The presentation appears to assume substantial familiarity with the technical details of prior certified unlearning methods. While many relevant concepts are discussed, the connections between them are not always clearly established, making it difficult to follow the overall theoretical development. There are several abrupt transitions, and some notation is introduced without sufficient explanation. For example, on page 4, the quantity (\rho_{\mathrm{previous}}) appears without a clear definition or sufficient intuition for why it scales inversely with a power of the regularization parameter (\lambda). More generally, the paper would benefit from a clearer progression from the limitations of previous approaches to the theoretical insights and the resulting algorithm.

  2. Some important theoretical bounds require additional explanation. On page 5, the final inequality involving the bound (\rho^* d/2) is not immediately clear. There may be a derivation supporting this result, but the paper should provide additional intermediate steps or explicitly point readers to the relevant proof. Since the theoretical bounds are central to the contribution, their derivation and underlying assumptions should be easier to verify.

  3. The connection between the theoretical motivation and the proposed algorithm is insufficiently explained. The paper begins with a convincing motivation, explaining that the minimum eigenvalue of the logistic-loss Hessian can approach zero as the model parameters grow, making the global strong convexity parameter effectively dependent on the regularization coefficient (\lambda). This provides a useful explanation of why existing approaches may require strong regularization or excessive noise.

  4. However, after discussing the additive noise mechanism of Guo et al., the paper transitions rather abruptly to the proposed algorithm and its certification bound. I found it difficult to identify how this bound is derived from the preceding theoretical discussion and how the individual components of UNCLE follow from the stated insights. Given that the improved certification bound appears to be the main contribution, the authors should explain this connection more explicitly, ideally with a step-by-step overview of the derivation and its implications for algorithm design. As currently presented, several parts of the analysis feel disconnected, making the overall contribution harder to appreciate.

  5. The theoretical scope is relatively narrow. The authors acknowledge that their analysis focuses on logistic regression with linear classifiers. While this is understandable given the connection to the foundational certified unlearning framework of Guo et al., I believe the paper would be stronger if the results extended to a broader class of loss functions or models. I am not necessarily expecting theoretical guarantees for deep neural networks or LLMs, but even within the classical machine learning setting, establishing whether the proposed analysis applies to other losses or model classes would substantially strengthen the contribution. For a theory-focused paper at ICLR, the current scope limits the generality and potential impact of the results.

  6. The empirical behavior on the Dogfish dataset needs further justification. In Figure 3, UNCLE appears to achieve lower accuracy than the method of Guo et al. on the Dogfish dataset. This observation is not adequately discussed or explained. Since the paper focuses on a relatively controlled setting and makes theoretically motivated claims about improving the accuracy–certification trade-off, such an exception deserves closer examination. The authors should investigate whether this behavior can be explained by dataset geometry, regularization strength, conditioning, or other factors relevant to their theoretical analysis. An explanation connecting this empirical observation to the assumptions or limitations of the proposed method would be particularly valuable.

Questions for authors
  1. Derivation of the certification bound (Clarification): Could the authors provide a clearer explanation of how the proposed certification bound is derived and how it connects to the local properties of the loss landscape? In particular, how does this analysis translate into the design of UNCLE, and what specifically makes its bound tighter than that of Guo et al.?

  2. Justification of theoretical bounds (Clarification): Could the authors clarify the derivation of the final bound involving ρ∗d/2\rho^*d/2 on page 5? Additionally, what is the intuition behind the dependence of ρprevious\rho_{\mathrm{previous}} on the regularization parameter λ\lambda on page 4? References to the corresponding proofs would be helpful.

  3. Performance on the Dogfish dataset (Clarification): In Figure 3, UNCLE appears to achieve lower accuracy than Guo et al. on the Dogfish dataset. Can the authors explain this behavior? Is it related to the data geometry, regularization strength, or specific assumptions underlying the proposed theoretical analysis? Understanding this result would help assess when UNCLE provides an advantage over existing methods.

  4. Generality of the theoretical analysis (Scope of contribution): To what extent do the proposed certification bounds rely specifically on logistic loss and linear models? Could the authors identify which assumptions or steps in the derivation would prevent extending the analysis to other convex losses or classical model families? I am not requesting additional experiments on deep networks, but understanding whether the theoretical insights apply beyond logistic regression would materially affect my assessment of the contribution's generality.

6 comments

Thank you for your comments!

Derivation of the certification bound

Appendices B and D contain the derivations requested; we will clarify them in the next version of our paper and bring some of this derivation into the main body. Here we give an overview of the derivation, and we are happy to discuss it further during the discussion period.

For purposes of this discussion, we'll assume the goal is to take as input:

  • a dataset (x1,y1),…,(xn,yn)(x_1, y_1), \ldots, (x_n, y_n),
  • a deletion set T⊆[n]T \subseteq [n],
  • the empirical risk minimizer θ0\theta_0 for the whole dataset,
  • an estimate θ^\hat{\theta} of the minimizer θ⋆\theta^\star of the leave-TT-out loss, and
  • a radius RR fixed in advance,

and produce as output:

  • either a certificate that ∥Σ1/2(θ⋆−θ^)∥≤R\lVert \Sigma^{1/2} (\theta^\star - \hat{\theta}) \rVert \leq R, where Σ\Sigma is the second moment of the retained samples, or a report that certification failed.

Given a certificate, we add Gaussian noise with covariance roughly R2Σ−1R^2 \Sigma^{-1} to θ^\hat{\theta} to get a certified unlearning algorithm; if certification fails, we retrain from scratch. (This is a simplification; for example, our algorithm also uses some extra inputs that we pre-compute and cache at training time, before any deletion requests arrive.)

Write LL for the leave-TT-out loss, g=∇L(θ^)g = \nabla L(\hat{\theta}) for its gradient at our estimate, and H0H_0 for its Hessian at θ0\theta_0. Our certificate relies on three local properties of the loss, all measured relative to the local geometry H0H_0, which for well-behaved data is much larger than the global strong convexity λI\lambda I used by Guo et al.:

  1. θ^\hat{\theta} looks close to θ⋆\theta^\star as far as the gradient is concerned: the residual v=H0−1gv = H_0^{-1} g is small.
  2. The Hessian is locally stable: if sample ii's logit moves by at most ss from xi⊤θ0x_i^\top \theta_0, its contribution to the Hessian changes by at most s⋅mis \cdot m_i, where mim_i bounds the third derivative of the logistic loss near xi⊤θ0x_i^\top \theta_0. Locality is important here: for samples with large-magnitude logits at θ0\theta_0, mim_i is very small, because the derivatives of the logistic loss are small when the logits are large in magnitude.
  3. Deleted points don't change the Hessian much: H0⪰(1−q)HSH_0 \succeq (1-q) H_S, where HSH_S is the full-data Hessian at θ0\theta_0 and q<1q < 1 is computed from the kk deleted points.

The second and third properties combine into a single number GG, which bounds how much the Hessian can change, relative to H0H_0, while every logit stays within ss of its value at θ0\theta_0: ∑is mi xixi⊤⪯GH0\sum_i s \, m_i \, x_i x_i^\top \preceq G H_0. (This is GopG_{\mathrm{op}} in Algorithm 3. It is computed from the pre-computed full-data Hessian and qq.)

Now we'll explain how to put these properties together into a distance bound. For simplicity, we show the bound in the H0H_0-norm; the Σ\Sigma-norm version needed for the noise is analogous (Algorithm 3, Appendix B.3).

Since ∇L(θ⋆)=0\nabla L(\theta^\star) = 0, the fundamental theorem of calculus gives the exact identity

\theta^\star - \hat{\theta} = - \bar{H}^{-1} g, \tag{1}

where Hˉ\bar{H} is the average Hessian of LL on the segment from θ^\hat{\theta} to θ⋆\theta^\star. Suppose for the moment that the logits at both θ^\hat{\theta} and θ⋆\theta^\star are within ss of their values at θ0\theta_0. (For θ^\hat{\theta} this can be checked directly; θ⋆\theta^\star is the issue.) By convexity, the same then holds along the whole segment, so Hˉ⪰H0−∑is mi xixi⊤⪰(1−G)H0\bar{H} \succeq H_0 - \sum_i s \, m_i \, x_i x_i^\top \succeq (1-G) H_0. If G<1G < 1, this gives

∥θ⋆−θ^∥H0≤∥v∥H01−G,where ∥v∥H0=g⊤H0−1g.\lVert \theta^\star - \hat{\theta} \rVert_{H_0} \leq \frac{\lVert v \rVert_{H_0}}{1 - G}, \qquad \text{where } \lVert v \rVert_{H_0} = \sqrt{g^\top H_0^{-1} g}.

In other words, the distance from θ^\hat{\theta} to θ⋆\theta^\star is at most the Newton residual inflated by a factor 1/(1−G)1/(1-G), which is close to 11 when the Hessian is locally stable.

This argument shows that if the algorithm knew in advance that the logits at the unknown θ⋆\theta^\star are within ss of those at θ0\theta_0, it could bound ∥θ⋆−θ^∥H0\lVert \theta^\star - \hat{\theta} \rVert_{H_0}. To avoid this circularity, the algorithm guesses ss (in practice it tries a few fixed values) and assumes the logits at θ⋆\theta^\star are within ss of those at θ0\theta_0. It then checks that ss is "self-consistent": using the same identity (1) to bound each logit change xi⊤(θ⋆−θ^)x_i^\top (\theta^\star - \hat{\theta}), it verifies that the logits at θ⋆\theta^\star would then be strictly within ss of those at θ0\theta_0. Theorem 1.1 (Appendix D) shows that when this self-consistency check passes, the logits at θ⋆\theta^\star really are within ss of those at θ0\theta_0, and hence the distance bound above holds.

Compared with Guo et al., the two key changes are using the local curvature H0H_0 instead of λI\lambda I, and using the local bounds mim_i instead of a global bound on the third derivative.

Justification of theoretical bounds

Dependence of ρprevious\rho_{\text{previous}} on λ\lambda. ρprevious\rho_{\text{previous}} denotes the variance of the noise that previous Newton-step-based approximate-and-noise methods must add; we will define it explicitly in the next version. The basic idea is as follows (see Theorem 1 of Guo et al. and Proposition 1 of [1] for formal accounts):

  • The noise variance must scale with the square of the best bound the algorithm can certify on ∥θ⋆−θ^∥\lVert \theta^\star - \hat{\theta} \rVert, the distance between the retrained model and its one-Newton-step approximation.
  • Previous analyses obtain this bound from global strong convexity: for a λ\lambda-strongly-convex loss LL, ∥θ−θ⋆∥≤∥∇L(θ)∥/λ\lVert \theta - \theta^\star \rVert \leq \lVert \nabla L(\theta) \rVert / \lambda for every θ\theta. Applied at θ=θ^\theta = \hat{\theta}, this converts a bound on the gradient after the Newton step into a bound on the distance.
  • The unregularized logistic loss is not globally strongly convex: the smallest eigenvalue of its Hessian tends to 00 as ∥θ∥→∞\lVert \theta \rVert \to \infty. So the best global strong convexity constant is the regularization coefficient λ\lambda itself, even when the curvature near the solution is much larger.

Together, these give ρprevious∝1/λ2\rho_{\text{previous}} \propto 1/\lambda^2. The bound on the gradient after the Newton step also degrades with λ\lambda (in Theorem 1 of Guo et al., it scales as 1/λ21/\lambda^2), which is why the exponent cc can exceed 22. Our certificate instead uses the local curvature H0H_0, which for well-behaved data is much larger than λI\lambda I (see our answer to (1)).

Derivation of the ρd/2\rho d / 2 bound on page 5. Why noise ν∼N(0,ρΣtrain−1)\nu \sim \mathcal{N}(0, \rho \Sigma_{\text{train}}^{-1}) suffices for certified unlearning is covered in our answer to (1): ρ\rho here corresponds to R2R^2 there, up to the factor 2log⁡(1.25/δ)/ε22 \log(1.25/\delta) / \varepsilon^2 from the Gaussian mechanism (Theorem B.2, Appendix B.1). Here we justify the display equation in lines 266-267. This equation is meant as intuition for our choice of noise geometry rather than as a formal claim; we will add the following derivation, with its assumptions made explicit, to the appendix. We use the following notation and assumptions:

  • Σtrain\Sigma_{\text{train}} and Σtest\Sigma_{\text{test}} are the second moments of the training and test samples.
  • LL is the test loss, and Htest=∇2L(θ)H_{\text{test}} = \nabla^2 L(\theta) is its Hessian.
  • The noise ν\nu is small enough that LL is well approximated by its Taylor expansion of order 3 around θ\theta.
  • Htest⪯ΣtestH_{\text{test}} \preceq \Sigma_{\text{test}}. This holds whenever the second derivative of the loss with respect to the logit is at most 11; for logistic loss it is at most 1/41/4.
  • The training and test second moments are spectrally close, for instance 12Σtest⪯Σtrain⪯2Σtest\tfrac{1}{2} \Sigma_{\text{test}} \preceq \Sigma_{\text{train}} \preceq 2 \Sigma_{\text{test}}. (The constants 1/21/2 and 22 are arbitrary.)

Taylor expanding LL around θ\theta and taking the expectation over ν\nu, the first- and third-order terms vanish because ν\nu is symmetric, leaving

E[L(θ+ν)−L(θ)]≈12E[ν⊤Htestν]=ρ2Tr⁡(HtestΣtrain−1)≤ρ2Tr⁡(ΣtestΣtrain−1),\mathbb{E}[L(\theta + \nu) - L(\theta)] \approx \tfrac{1}{2} \mathbb{E}[\nu^\top H_{\text{test}} \nu] = \tfrac{\rho}{2} \operatorname{Tr}(H_{\text{test}} \Sigma_{\text{train}}^{-1}) \leq \tfrac{\rho}{2} \operatorname{Tr}(\Sigma_{\text{test}} \Sigma_{\text{train}}^{-1}),

where the equality uses E[νν⊤]=ρΣtrain−1\mathbb{E}[\nu \nu^\top] = \rho \Sigma_{\text{train}}^{-1}. If Σtrain=Σtest\Sigma_{\text{train}} = \Sigma_{\text{test}}, the trace equals dd, giving ρd/2\rho d / 2. Under the spectral-closeness assumption it is at most 2d2d; the ≲\lesssim in the paper hides this constant. Note that the bound does not depend on the conditioning of the data. This is the point of drawing the noise from Σtrain−1\Sigma_{\text{train}}^{-1} rather than isotropically: isotropic noise with the same masking power can increase the test loss by a factor that grows with the condition number of the covariates.

[1]: Koh, Ang, Teo, Liang, "On the Accuracy of Influence Functions for Measuring Group Effects".

Performance on the Dogfish dataset

Before diving into the specifics of DogFish, we note that we reported the results of UNCLE and Guo et al. on every dataset we ran experiments on – DogFish is the only dataset on which UNCLE did not strictly dominate Guo et al., and even then only when the number of samples to remove becomes large.

UNCLE's main advantage over Guo et al. appears for datasets where using large regularization is costly in terms of test accuracy. This isn't the case for DogFish – looking at Figure 3, we can see that increasing the regularization across several orders of magnitude has minimal effect. Since our experiments try to find an optimal regularization level for Guo et al. in order to compare fairly, this gives Guo et al. the opportunity to choose very high regularization and perform well. So we should not expect much advantage for UNCLE here.

As for why UNCLE appears, in Figure 1, to actually slightly underperform Guo et al. – we believe this is is an artifact of hyperparameter choices in UNCLE. We re-ran the same experiment with a small modification of UNCLE, where 19 possible values of the hyperparameter ss are tested to see if any of them produces a certificate, rather than 5 as in the original experiments. Our preliminary finding is that UNCLE's performance then improves over Guo et al. for the DogFish dataset. We are working to confirm this finding more carefully before posting a supplementary plot here, which we endeaver to do before the end of the discussion period.

Reviewer_tei6OpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes UNCLE, a certified machine unlearning based on the proposed algorithm in the [1] which attempts to improves the trade-off between unlearning guarantees, predictive accuracy, and computational efficiency. the key aspect of the research paper is regrious mathamatical formulation and investigation of the research. the proposed method attempts to bound the distance between an approximate unlearned model and the ideal unlearned model using local properties of the loss landscape.

Critical strengths

the paper targets the real source of looseness in prior guarantees for the strong convexity. UNCLE verifies curvature conditions within a carefully constructed local convex region.

Critical weaknesses

For the experiments, the statistical analysis and comprehensive tests of the multiple seeds is not shown in the plots.

line 178) suddenly the description shifts gear to logistic regressions. this part of the paper seems disconnected from the previous paragraph. revise it to tell the coherent story about the research problem

line 163) why a large reguralizer? can you reference the paper? In this paper [2], they attempt to address this assumption, so what is the advantage of your proposed method over them?

line 1246) "bounded, convex neighborhood" are specified for the parameter space, but then the theoretical proof of theorem d.1 doesn't reflect them in the formulation? How do you define neighborhood?

line 11) not proper writing for the conference paper. revise the abstract to academic and clear description.

line 51) informal writing

line 208) by only bounding the error unlearning approximate then you address the problem of strong convexity? Can you prove this that this assumption adverse the convexity assumption?

figure 2) c ) why the bounded selection is elliptical?

[1] ttai Rubinstein and Samuel B. Hopkins. On the accuracy of Newton step and influence function data attributions. In Proceedings of the 43rd International Conference on Machine Learning, volume 306 of Proceedings of Machine Learning Research. PMLR, 2026. URL https://arxiv.org/ abs/2512.12572.

[2] Zhang, B., Dong, Y., Wang, T., & Li, J. (2024). Towards certified unlearning for deep neural networks. arXiv preprint arXiv:2408.00920.

Questions for authors

see previous section

1 comment

Thank you for reading our paper and your comments! We address your comments below.

  • Evaluation with multiple seeds We include experiments with multiple seeds in Appendix C.5, showing that the variability under different seeds is limited. We will include visualization of this fact in the figures in the final version.

  • Line 178 We suspect the reviewer meant line 158, not line 178, given the mention of a transition to logistic regression. We had previously identified logistic regression as a canonical "simple" problem of focus earlier, in line 51. Once we introduce the dependence of previous methods on the global strong convexity property, we re-introduce logistic regression as a fundamental setting where this doesn't hold. We will make this transition clearer in the final version.

  • Line 163 Guo et al.'s necessity of a large regularizer is apparent if one inspects the role of λ\lambda in Theorem 1, Equation (4): the scale is 1/λ21/\lambda^2, or inverse-polynomial in the regularization parameter. The goal of [2] is somewhat different from ours. Our concern is obtaining tight provable guarantees for convex settings, when we may not have global strong convexity (which comes along with regularization). Their concern is focused on settings where the problem is not convex at all. While this setting is more general than the one we focus on, their guarantees are substantially looser (see, e.g., Theorem 3.4, Equation (7), which doesn't depend on the number of deleted samples and thus may be large even for a single deletion), and they impose new requirements, including a bounded parameter space and strong Hessian regularization. In short, their focus is getting non-trivial results for nonconvex settings, whereas we aim to get tight and geometry-dependent results for a fundamental convex setting.

  • Line 1246, "bounded convex neighborhood" To clarify, the bounded convex neighborhood A\mathcal{A} is any subset of the parameter space (satisfying the conditions in lines 1246 to 1248), the parameter space itself is unrestricted. The convexity and neighborhood assumptions are essential in the proof of Lemma D.2, which is used to prove Theorem D.1. Roughly speaking, the idea is that if we start in such a subset A\mathcal{A} and we run Newton flow, then we will end up at a local minimum that is also in A\mathcal{A}. While this holds for any such A\mathcal{A}, we instantiate UNCLE for a specific set which is defined, e.g., in Appendix B.2.

  • Line 11, 51, writing We are unclear on the reviewer's specific issues with the writing in these passages. Exposition here is casual to communicate the broad setting and convey intuition without introducing technical details prematurely. In subsequent parts of the paper, we are technically precise and rigorous. We are happy to consider specific suggestions that the reviewer might suggest, but we feel these capture the level of technicality that we hoped for at these points of the paper.

  • Line 208, convexity The exact question being asked is unclear to us, we would appreciate it if the reviewer could reword their inquiry. For the time being, we will interpret this as asking how we avoid a dependence on a global strong convexity parameter. In short: previous methods bounded the error of a single Newton step in terms of the global strong convexity parameter λ\lambda, which is how this dependence arises. In contrast, we prove Theorem 1.1 which allows us to bound the error of a Newton step in terms of the local geometry over a set A\mathcal{A}. We instantiate our framework with a set A\mathcal{A} with the following two properties: a) the width of A\mathcal{A} (in the appropriate geometry) is sufficiently small, thus bounding the error, and b) it is efficient to verify local conditions on A\mathcal{A}, thus allowing us to quickly certify if we can avoid retraining from scratch. This is necessarily a succinct explanation, a more thorough discussion is contained in Section 1.3.

  • Figure 2(c), elliptical The bounded area in Figure 2(b) (not 2(c)) is an ellipsoid: this is the setting in which Rubinstein and Hopkins were able to prove a bound. The bounded area in Figure 2(c) is not an ellipsoid: one of our key technical contributions is that we are able to handle more general regions. In particular, our algorithm considers a region which is the intersection of an ellipsoid and a set of linear constraints, as described in Section B.2 through the definition of A\mathcal{A}. The purpose for this shape is, as described in the previous answer, to simultaneously support conditions a) and b).

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.