acceptodds
Under review as a conference paper at ICLR 2027

Near-Optimal Machine Unlearning Utility for Smooth Strongly Convex Losses

Abstract

Machine unlearning is motivated by legal and user-facing requirements to remove the influence of individuals' data from trained models, such as the right to be forgotten. Prior work has developed algorithms and error bounds for unlearning in smooth strongly convex stochastic optimization but the fundamental statistical cost of unlearning has remained unclear. We nearly resolve this problem by proving upper and lower bounds on the excess population risk of approximate -unlearning; our bounds are tight up to a condition-number factor. For mean estimation over the unit ball, our upper and lower bounds match up to constants. In fact, our algorithm achieves -unlearning, which implies a notable separation between differential privacy (DP) and unlearning: -unlearning has no statistical advantage over pure -unlearning in stochastic convex optimization. The optimal rate is the usual sampling error plus an unlearning penalty that interpolates between the retraining-from-scratch rate and an exponentially smaller term as grows, where is the dimension of the model. In particular, retraining-from-scratch is statistically optimal when . On the other hand, for and large unlearning requests, our -unlearning algorithm offers an exponential accuracy improvement over retraining the model from scratch and over DP baselines.

Primary area:
alignment, fairness, safety, privacy, and societal considerations
Keywords:
Machine Unlearning, Strongly Convex Optimization, Statistics

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_dNX9OpenReview ↗
Rating
4
Confidence
4
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

The paper proves near tight upper-lower bounds on the utility unlearning algorithms can have (with DP like unlearning guarantees) for smooth strongly convex objectives. Their algorithm, which provides the upper-bound, notes that ERM has optimal error rates and so designs a mixture distribution which outputs near ERM solutions with high probability while still also outputting models near the desired retrained from scratch solution. The lower bound comes from a packing argument to show there are distributions which have different optimal solutions but you can remove mm samples and have identical ERM solutions on the retain set. Overall this paper makes significant progress on our understanding of unlearning and how it differs from differential privacy and other Trustworthy ML goals.

Critical strengths
  1. The results on upper and lower bounds are strong and novel. I agree with the authors that this lays the foundation for significant follow-up work.

  2. The presentation and techniques are elegant. In particular, I found the intuition that all one needs to do is choose to be near ERM before deletion request very insightful and made the rest of the proofs clear. I also appreciated that the authors chose to strengthen the utility assumptions from past work (i.e., the original training algorithm needs to have high utility) to make it more in line with the often cited goals of unlearning.

Critical weaknesses

I can only name very minor and out-of-scope weaknesses.

  1. I believe the results could be extended to non strongly convex losses. I found little discussion on this, though the authors acknowledge removing condition number to do so is important.

  2. Future work could now tackle getting computational costs down; the proposed algorithm has relatively high unlearning costs.

Questions for authors

I had no real questions after reading the paper and proofs: most of my margin notes were “cool!”. Below are mostly questions out of curiosity and the authors do not have to answer them.

  1. Could the upper-bound results be extended to non strongly convex settings? In particular, DP phased ERM achieves optimal DP convex rates by reducing to a series of regularized objectives where the regularization is dependent on the desired error: is there a reason an analogous algorithm for unlearning would not work?

  2. In the definition of approximate unlearning, could you not set A~(∅,Z)=A(Z)\tilde{A}(\emptyset, Z) = A(Z) without loss of generality; as in define the original training algorithm to be the emptyset unlearning algorithm given it has utility guarantees too? This would just make it clearer the simpler “training algorithm is fixed” view is equivalent to this setup, and given the matching upper-bounds under the weaker assumption, effectively say the literature can just focus on comparing unlearning to fixed training algorithms. Assuming this is correct, I think this is something valuable to further highlight.

1 comment

We thank the reviewer for their encouraging feedback. In light of the diverging assessments of our work, we hope the reviewer will reiterate their confidence to the AC.

Could the upper-bound results be extended to non strongly convex settings?

We could indeed use regularization to obtain an upper bound for non-strongly convex unlearning. Assuming global convexity and smoothness of the population objective, with a minimizer in W\mathcal W, the resulting rate is

\lesssim \frac{1}{\sqrt n} +\left(\frac{m}{n}\right)^{2/3} e^{-\frac{2\varepsilon}{3(d+2)}}$$ (holding other parameters constant). However, it is unclear whether iterative localization, analogous to DP phased ERM, improves this bound further: data-dependent deletion requests can make phase $i$’s output depend on phase $i+1$’s data batch, preventing direct application of the standard DP utility analysis. We would be happy to add this corollary and discussion to the revision. > In the definition of approximate unlearning, could you not set $\tilde{A}(\varnothing, Z) := A(Z)$ without loss of generality? **Yes, under our utility definition.** Defining $A(Z):=\widetilde A(\varnothing,Z)$ gives the equivalent requirement $$\widetilde A(U,Z)\approx_{\varepsilon,\delta}A(Z\setminus U),$$ and our utility guarantee already ensures that this fixed reference learner is accurate at every allowed dataset size. We agree that this equivalence is worth highlighting and will make it explicit.
Reviewer_jnFdOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper studies the minimax excess population risk of (ε, δ)-unlearning in smooth strongly convex SCO. The setting has a full-storage unlearner, adversarial deletions of up to m points, and a utility requirement both after deletion and for the empty-deletion reference run (Definition 2). The results are:

  1. Upper bound. A pure ε-unlearning algorithm (Algorithm 1) achieves O(κ·L²/μ·(1/n + (m/n)² e^{−2ε/(d+2)})) with Õ(κn) gradient and projection queries.
  2. Lower bound. For all (ε, δ)-unlearners with δ ≤ 1/5, the risk is Ω(L²/μ·(1/n + (m/n)² e^{−2ε/(d+2)})), matching the upper bound up to κ and up to constants for mean estimation.
  3. Conclusions drawn by the paper. δ > 0 does not help; retraining from scratch (RFS) is optimal for ε ≲ d; for ε ≫ d and large deletion sets, the algorithm improves exponentially over RFS and DP baselines.
Critical strengths
  1. Lower bound for general unlearners with a matching exponent. The lower bound covers all (ε, δ)-unlearners with δ ≤ 1/5, not only the restricted (e.g., DP-based) unlearners of Huang & Canonne (2025), and its exponent 2ε/(d+2) matches the upper bound exactly. This yields the clear, practically relevant conclusions that RFS is optimal for ε ≲ d and that a constant δ does not help.
  2. Dependence on the utility notion. Under the weaker post-unlearning notion, the optimal exponent becomes 2ε/d and is attained by an algorithm that detects reference runs from the dataset size. This is a useful argument for adopting the stronger notion.
Critical weaknesses
  1. The core lower-bound idea already appears in Sekhari et al. (2021) and is not credited. The paper calls its lower bound “novel” and says it “departs from standard DP packing arguments”: adversarial deletions collapse all hard instances to a common retained dataset, forcing their outputs close to one reference distribution. Sekhari et al.’s Theorem 1 already uses a two-point version of this argument. It takes two distributions at ℓ1 distance m/(2n), applies deletions after which the retained samples approximately share a distribution, and allows the unlearner to access the full sample. Its proof bounds the sum of the two excess risks below by e^{−ε}m²/(32n²) − 2e^{−m/12} − 2δ, and the 1-D instance embeds into any dimension. Hence, for constant ε, δ ≲ (m/n)², and m ≳ √n (the regime where the unlearning term matters), the Ω((m/n)²) bound and the optimality of RFS are already known. Sekhari et al. state this as a deletion-capacity bound (m ≤ cn), and the paper cites only that conclusion. The genuine additions are narrower than claimed: (a) the exact exponent for all ε, including RFS optimality for 1 ≲ ε ≲ d; (b) validity for constant δ; (c) the d+2 exponent obtained from requiring accuracy of the reference run.

  2. The upper-bound algorithm and its associated claims are problematic. (a) The claimed exponential improvement over DP and the claimed use of unlearning-time information likely fail. The paper claims exponential gains over “DP baselines” (abstract) and “DP-based unlearning” (introduction). However, Table 1’s DP rate d²m²/(ε²n²) decays only polynomially in ε, as with Laplace-type noise, which is suboptimal for large ε. Consider adding d-dimensional staircase noise to ŵ_Z instead: the density is constant on a core ball of radius γr and drops by e^ε across each successive shell of width r, where r is Algorithm 1’s deletion sensitivity. (a) A shift of norm at most r crosses at most one shell, so the mechanism is ε-unlearning with no unlearning-time computation, and it is also ε-DP for groups of size m. (b) With γ = 2e^{−ε/(d+2)} (as τ/r in Algorithm 1) and ε ≥ Cd, its error is O(r² e^{−2ε/(d+2)}). For d = 1 this matches Geng & Viswanath’s Θ(Δ² e^{−2ε/3}). For ε < Cd, e^{−2ε/(d+2)} ≥ e^{−2C}, so RFS is already optimal. If this sketch is correct, “RFS for small ε, staircase output perturbation for large ε” attains the paper’s rate up to constants. This contradicts both the claimed gain over DP and the stated “key algorithmic idea” of exploiting “information available at unlearning time”: for ε ≫ d, U is unnecessary. Algorithm 1 is itself a staircase-like construction, yet this literature is not discussed. (b) Algorithm 1 does not adapt to the actual deletions. Its noise radius τ = r·min{1, 2e^{−ε/(d+2)}} is fixed by the worst-case r = 2Lm/(μ(n−m)) + 2ρ. It therefore pays about (m/n)² e^{−2ε/(d+2)} even with no deletions or with random deletions, where RFS is exact and has O(1/n) error. Algorithm 1 is thus worse than RFS whenever (m/n)² e^{−2ε/(d+2)} ≫ 1/n, a range extending beyond ε ≲ d. For ε ≲ d and m ≫ √n, the gap is a factor of order m²/n. This is not discussed. (c) The positive result lives only in a vacuous privacy regime. The improvement requires ε ≫ d, i.e., likelihood-ratio bounds far beyond e^d (e.g., e^{1000} for d = 1000). In this regime, the true run outputs a point near the full-data ERM with probability 1−η ≈ 1. Whenever ‖w̃_Z − w̃_{Z\U}‖ > 2τ, the total-variation distance between the true and reference runs is 1−η ≈ 1, so an adversary can tell almost surely whether the deleted points were used. The paper should state explicitly that this regime offers essentially no protection, so that for meaningful ε its message is negative: one cannot statistically beat retraining.

Questions for authors
  1. Assumptions behind Theorem 8 (clarification). The improvement over Sekhari et al.’s m/n term requires β-smoothness and population stationarity (Assumption 1.5). Sekhari et al. implicitly use stationarity at the empirical minimizer but not β-smoothness, and they bound the risk via Lipschitzness. Moreover, κ(m/n)² beats m/n only when κm/n ≲ 1. Please state these conditions in Theorem 8, Table 1, and the contributions.
  2. Reduction for Corollary 1 (clarification). Please write out the SCO-to-mean-estimation reduction rather than citing the DP version in Lowy & Razaviyayn. Verify that it preserves (i) adversarial deletions, (ii) the accuracy requirement on Ã(∅, S) at N = n−m, on which the d+2 exponent relies, and (iii) Assumption 1.
  3. Resource budgets in Table 1 (suggestion). Algorithm 1 needs full storage and RFS-level runtime, whereas Newton-step unlearning needs O(d²) storage and O(d^ω) time. Please report these for a fair comparison.
  4. Minor. η denotes both the mixing probability and the contamination level. Definition 1 uses Z ∈ 𝒵ⁿ, but Definition 2 and the proof of Proposition 1 use Z ∈ 𝒵^N; please unify these and state |Z\U| ≥ n−m explicitly. In the proof of Proposition 3, Vol(G) should be Vol(G′). In the proof of Theorem 4, 1/42 should be 1/84 (this does not affect the result).
4 comments

We thank the reviewer for their careful reading and helpful feedback. We will address minor clarifications as needed. Our response to the two main critiques are as follows.

The core lower-bound idea already appears in Sekhari et al. (2021) and is not credited.

Our claim to a novel lower bound is not that we apply/discover a fundamentally new lower bound technique but rather that we correctly apply a standard technique from differential privacy (packing) to determine, for the first time, the optimal rates for unlearning in mean estimation and (up to κ\kappa factor) SCO. Indeed, our lower bound strengthens the lower bound of Sekhari et al. to obtain the optimal rate; we will explain this in the revision.

The genuine additions are narrower than claimed: (a) the exact exponent for all ε\varepsilon, including RFS optimality for 1≲ε≲d1 \lesssim \varepsilon \lesssim d; (b) validity for constant δ\delta; (c) the d+2d+2 exponent obtained from requiring accuracy of the reference run.

As far as we are aware, we do not claim anything beyond these points regarding our lower bound result. Can the reviewer point to a specific place where they would suggest softening the language? Indeed, these are the main novel insights of our lower bound result.

The upper-bound algorithm and its associated claims are problematic... The claimed exponential improvement over DP... likely fail.

We thank the reviewer for this observation. We agree that RFS for small ε/d\varepsilon/d, combined with staircase output perturbation for sufficiently large ε/d\varepsilon/d, provides an alternative way to attain our rate. Our algorithm provides a unified construction across these regimes. The alternative construction leaves our upper and lower bounds, and hence our minimax characterization, unchanged.

We agree that our comparison with DP-based approaches was too broad. We will distinguish the conventional (ε/m)(\varepsilon/m)-DP baseline in Table 1 from mechanisms satisfying ε\varepsilon-DP directly for groups of size mm. Specifically, we will relabel the existing baseline, add the staircase comparison in its applicable regime, cite the staircase literature, and remove the blanket claim of an exponential advantage over DP-based unlearning. The exponential improvement over RFS remains valid in the stated regime.

This contradicts ... the stated “key algorithmic idea” of exploiting “information available at unlearning time”

We agree that knowledge of the deletion set UU is not necessary to attain the optimal rate in the large-ε\varepsilon regime. Our intended point was that an approximate unlearner can improve utility by retaining information from the full dataset, including the deletion set UU. Both our construction and the staircase alternative exploit this possibility. We will revise the wording accordingly.

Algorithm 1 is worse with no deletions or with random deletions.

We agree that Algorithm 1 does not adapt to easy deletion requests, including small/random requests. Our utility guarantee is minimax over adversarial deletions; we do not claim that Algorithm 1 outperforms RFS on every deletion pattern. Studying worst-case utility over deletion sets of size at most mm follows prior work, including Sekhari et al. (NeurIPS 2021). We will explicitly clarify that our comparison with RFS concerns worst-case risk. Developing algorithms that adapt to easier deletion requests is an interesting direction for future work, beyond our paper's focus on minimax optimal rates.

The positive result lives only in a vacuous privacy regime.

We agree that ε≫d\varepsilon\gg d is not a practical if dd is very large. We do not claim otherwise and we will make this point explicit. In low dimensions, however, ε\varepsilon can exceed dd while still providing a meaningful guarantee protecting mm deletions jointly. Besides, our main contribution is to characterize when RFS has optimal utility and establish the best achievable rates across all regimes, up to the stated condition-number factor.

Please write out the SCO-to-mean-estimation reduction rather than citing the DP version in Lowy & Razaviyayn

This reduction is a simple calculation for the quadratic loss f(w,z):=12∥w−z∥2f(w, z) := \frac{1}{2} \lVert w - z \rVert^2: excess population risk equals half the squared distance from the population mean. This gives an immediate reduction that is not specific to the DP setting.

Assumptions behind Theorem 8.

Theorem 8 already invokes Assumption 1, including β\beta-smoothness and population stationarity. We will highlight these conditions in the theorem, Table 1, and the contributions, and clarify that the comparison of deletion terms, κ(m/n)2\kappa(m/n)^2 versus m/nm/n, is favorable when κm/n≲1\kappa m/n\lesssim1.

Resource budgets in Table 1.

We will add storage and unlearning-time requirements to Table 1 to make the different resource budgets explicit.

Minor notation and typographical issues.

We will distinguish the two uses of η\eta, unify the dataset-size notation, explicitly state ∣Z∖U∣≥n−m|Z\setminus U|\ge n-m, and correct the identified volume notation and numerical constant.

Hi there we are just reaching out to ask the reviewer if we have adequately addressed their concerns?

Thank you for the candid response, which addresses most of my concerns about framing. I also withdraw my concern about the large-ε regime in low dimensions. However, as the rebuttal confirms, the optimal rate is attainable by RFS combined with a staircase-type perturbation, and the lower bound extends Sekhari et al.’s bound via standard packing. I think the contribution is correct but incremental for ICLR, so I maintain my score of 2.

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

This paper studies the minimax excess population risk of approximate machine unlearning under adversarial deletions for smooth, strongly convex stochastic optimization. It establishes upper and lower bounds matching up to a condition-number factor, with constant-factor matching bounds for mean estimation. The proposed randomized ERM-based algorithm has runtime comparable to retraining.

Critical strengths
  1. The nearly matching upper and lower bounds provide a substantive statistical characterization within the specified setting, particularly for mean estimation.

  2. The refined analyses of retraining and existing algorithms, together with the comparison of utility definitions, clarify the population-risk guarantees of unlearning.

Critical weaknesses
  1. Restrictive assumptions. The analysis requires sample-wise strong convexity, smoothness, and a stationary population minimizer. Given existing certified unlearning results for nonconvex objectives (Mu and Klabjan, NeurIPS 2025), albeit under different guarantees, the paper should better justify these restrictions and explain the obstacles to extending its characterization.

  2. Limited relevance of the improvement regime. Substantial gains require ε >> d. For models with large parameter dimensions, this requires extremely large ε and therefore a weak unlearning guarantee. For ε ≲ d, retraining is already statistically optimal, limiting the practical relevance of the proposed advantage.

  3. Limited algorithmic guidance. The method accesses the full dataset and has runtime comparable to retraining. It establishes statistical achievability but offers limited guidance on reducing computation, storage, or handling repeated deletions.

  4. No concrete validation. No experiments demonstrate meaningful finite-sample improvements, even for mean estimation. Since the advantage depends on a specific parameter regime, its magnitude in total population risk remains insufficiently established.

Questions for authors
  1. Which conclusions survive without sample-wise strong convexity or the stationary-minimizer assumption? In particular, what prevents extending the analysis to nonconvex objectives under conditions such as the PL inequality?

  2. Can the authors provide concrete values of n, m, d, and ε for which total population risk improves substantially over retraining while retaining a useful unlearning guarantee? A controlled numerical comparison would help establish the significance of this regime.

3 comments

We thank the reviewer for their feedback.

The analysis requires sample-wise strong convexity, smoothness, and a stationary population minimizer... the paper should better justify these restrictions

We emphasize that our assumptions are no stronger than prior works that we build on. For example, Sekhari et al. (NeurIPS 2021) as well as the Allouah et al. (ICLR 2025) both require smoothness, Lipschitzness, and strong convexity.

We comment further on stationarity as well as the possibility of relaxing strong convexity to PL below.

Mu and Klabjan, NeurIPS 2025 offer certified unlearning results for nonconvex objectives

We thank the reviewer for pointing us toward Mu and Klabjan 2025. We note the result Cor 3.3 in that paper is not correct as stated. Maximizing the computational budget of unlearning (K=TK = T) in their algorithm leads to a claimed utility bound on the order of 1/n1/n, contradicting our lower bound (Thm 2). The issue can be seen near the end of page 19 of https://arxiv.org/abs/2409.09778, where the authors claim that E[fD′(w∗)]=F(w∗)\mathbb{E}[f_{D'}(w^\ast)] = F(w^\ast), which is not true for D′=D∖UD' = D \setminus U under arbitrary/adversarial data removal requests. Salvaging this claim requires an extra implicit assumption that the deletion request is chosen uniformly at random. This is not directly comparable to our setting of utility.

What prevents extending the analysis to nonconvex objectives under conditions such as the PL inequality?

Our lower bound applies to the PL setting directly. Also, our upper bound can be extended to PL with the same utility and runtime, replacing strong convexity and stationarity with different assumptions: proximal PL for empirical losses under arbitrary deletions, and population quadratic growth FP(w)−FP∗≳d(w,arg⁡min⁡FP)2F_P(w)-F_P^*\gtrsim d(w,\arg\min F_P)^2. These preserve our upper bounds without requiring exact stationarity.

However, our core goal is to resolve the statistically optimal unlearning rate in the simple and well-studied strongly convex setting. The extension to PL adds technical complexity without a clear benefit and it is straightforward to obtain these results by modifying our analysis with a small number of LLM prompts.

That said, if the reviewer believes this extension holds significant additional scientific value and is willing to increase their score, we are willing to include an appendix section with carefully written details of the PL extension.

Note that our results can also be partially extended to the non-strongly convex setting and we provide more detail in our response to Reviewer dNX9.

Substantial gains require ε≫d\varepsilon \gg d... No concrete validation... Can the authors provide concrete values?

Our contribution is a statistical characterization across parameter regimes, tight up to a condition-number factor for general SCO and up to constants for mean estimation. The improvement over RFS when ε≫d\varepsilon\gg d is not our main focus. A central takeaway is that we establish for the first time when RFS is statistically optimal: ε≲d\varepsilon\lesssim d, up to the stated condition-number factor.

Nonetheless, the rates illustrate potentially substantial gains for low-dimensional problems with large deletion requests. For example, take d=5d=5, ε=10\varepsilon=10, m=300m=300, and n=1000n=1000. The rate expressions, including sampling error, are

\quad\text{and}\quad \frac1n+\left(\frac mn\right)^2e^{-2\varepsilon/(d+2)}\approx0.00617.$$ Their ratio is approximately 15. This illustrates the rate separation; it is not a constant-explicit finite-sample guarantee. > Limited guidance on reducing computation, storage, or handling repeated deletions. We reiterate that our goal is to **establish a statistical characterization of unlearning**. Adversarial deletions break the i.i.d. assumption, making their statistical cost nontrivial even without computational constraints. Our bounds provide a beneficial baseline for future work focused on computation and help to **distinguish unavoidable statistical costs from losses caused by computational constraints**. This parallels the development of private SCO, where characterizing the optimal statistical rate laid the groundwork for faster algorithms. Our work similarly provides a foundation for understanding the utility–computation tradeoff in unlearning.

Thank you to the authors for the detailed response. The response has adequately addressed my main concerns and clarified the scope and contributions of the paper. I will therefore raise my score to 3.

Thank you for your engagement and discussion, and for increasing your score!

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.