Near-Optimal Pure Machine Unlearning for Smooth Strongly Convex Losses

Unknown

Conceptio › Archive › arXiv CS

arXiv CSopen access

Near-Optimal Pure Machine Unlearning for Smooth Strongly Convex Losses

Unknown · 2026 · arxiv_cs

arXiv CS · Papers · License: Open Access · 2026

Open Source ↗Direct PDF ↓

cryptography, security, privacy, cybersecurity

Near-Optimal Pure Machine Unlearning for Smooth Strongly Convex Losses Matthew Regehr∗

Gautam Kamath†

Andrew Lowy‡

arXiv:2606.01527v1 [cs.LG] 1 Jun 2026

June 2, 2026 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. The optimal rate is the usual statistical error plus an unlearning penalty that interpolates between the retraining-from-scratch rate and an exponentially smaller term as ε/d grows, where d is the dimension of the model. In particular, when ε ≫ d, our ε-unlearning algorithm offers an exponential accuracy improvement over retraining the model from scratch and differentially private baselines. On the other hand, when ε ≤ d, retraining from scratch is optimal.

Introduction

Machine unlearning [CY15] is motivated by legal, institutional, and user-facing requirements to remove the influence of individuals’ data from trained models, such as the right to be forgotten [Eur16, GGHvdM20]. Given a model trained on a dataset, an unlearning procedure receives a request to “delete” or “unlearn” a subset of the training samples and must update the model so that the result is statistically close to what would have been produced had those samples never been used. We consider unlearning in stochastic convex optimization (SCO). Given i.i.d. samples Z = (z1 , . . . , zn ) ∼ P n , the goal is to approximately minimize the population loss function min FP (w) := E [f (w, z)] , (1) w∈W

z∼P

where W ⊆ R is a convex parameter domain and f (·, z) is a loss function. The quality of a solution w is measured by its excess population risk ∆FP (w) := FP (w) − FP∗ , where FP∗ := minw′ ∈W FP (w′ ). In the unlearning setting, a learning algorithm A first receives the full dataset Z and outputs a model, possibly together with side information. Later, an unlearning algorithm Ã receives an unlearning request U ⊆ Z, with |U | ≤ m, and must output an updated model. Informally, approximate ε-unlearning requires that this updated model be ε-indistinguishable (in the max-divergence sense, à la differential privacy) from the output of the learning algorithm run directly on the retained dataset Z \ U . A key goal is to obtain small excess population risk while satisfying this unlearning constraint for every unlearning set of size at most m. In this paper, we investigate the smallest excess risk that is achievable in smooth strongly convex SCO subject to this ε-unlearning constraint. d

There are two naïve baseline methods for unlearning. First, differential privacy (DP) [DMNS06] automatically gives unlearning: if the original training algorithm is private enough to hide the contribution of any possible ∗ University of Waterloo. [email protected].

† University of Waterloo and Vector Institute. [email protected].

‡ CISPA Helmholtz Center for Information Security. [email protected].

unlearning set, then no special update is needed at unlearning time. However, this can be overly conservative, since a DP algorithm must hide all possible changes in advance, before the unlearning set is known; it does not leverage knowledge of U . Second, discarding the trained model and retraining the model from scratch on Z \ U gives exact 0-unlearning; but it discards part of the dataset and intuitively seems inefficient from a utility perspective. Can we improve over these two baseline approaches? A line of recent work has developed algorithms and excess-risk upper bounds for approximate unlearning in smooth strongly convex stochastic optimization [SAKS21, AKGK25, VWLNS25, ZAK+ 25, QZTW25]. These works showed that unlearning can improve over differentially private baselines in certain regimes and initiated the study of utility, computation, and storage tradeoffs under different assumptions. However, no excess risk bounds were given for the retraining-from-scratch baseline in prior work, and it was unclear whether it is possible to improve over retraining-from-scratch. In particular, the following fundamental question has remained open: Question. What is the minimax optimal excess population risk for ε-unlearning up to m samples in smooth strongly convex stochastic optimization? Our contributions. We nearly resolve the question above. Up to a condition-number factor, our upper and lower bounds characterize the minimax optimal excess-risk rate for smooth strongly convex stochastic optimization as 1 m 2 −2ε/(d+2) e . (2) + n n The rate (2) has a natural interpretation. The 1/n term is the usual statistical error present even without unlearning requirements [NY83], while the second term is the unlearning penalty. Retraining from scratch achieves the unlearning penalty (m/n)2 , and our lower bound shows that this is unimprovable when ε ≲ d. In this parameter regime, retraining from scratch also improves over the standard DP baseline. When ε ≫ d, our algorithm uses the unlearning set to reduce the unlearning penalty by the exponential factor exp(−2ε/(d + 2)). Thus approximate unlearning can be exponentially more accurate than retraining from scratch, DP-based unlearning, and prior unlearning algorithms. These comparisons are summarized in Table 1, which reports the closest apples-to-apples baselines for our rate comparison; broader related work is discussed in Appendix A. Our main contributions are: 1. Nearly tight minimax bounds for smooth strongly convex SCO. We give an ε-unlearning algorithm for smooth strongly convex stochastic optimization whose excess risk matches (2) up to a condition-number factor. We complement this with a lower bound showing that no unlearning algorithm can improve the dependence on n, m, ε, d. 2. A sharp characterization for mean estimation. For mean estimation over the unit ball in Rd , our upper and lower bounds match up to constants. 3. Sharper analyses of baseline and prior algorithms. We give a sharp analysis of the exact 0-unlearning baseline retrain-from-scratch, showing that it achieves 1/n + (m/n)2 excess risk and is optimal when ε ≲ d. In the appendix, we sharpen the analysis of the Newton-step algorithm of [SAKS21] to get a quadratic improvement in the unlearning error term. We also identify a bug in the utility analysis of [AKGK25] and give a corrected guarantee for their warm-start ERM procedure. Our lower bounds apply to all ε-unlearning algorithms, in contrast to the DP-based lower bounds of [HC25]. Techniques. Our key algorithmic idea is a novel way to exploit information available at unlearning time. The empty-deletion run on a retained dataset S = Z \ U returns a point near ŵS with high probability, but also places a small amount of probability mass over a region covering all possible full-data ERM solutions. When an unlearning request U arrives, the unlearner forms S = Z \ U , reconstructs this noise distribution by retraining from scratch. It then moves the high-probability mass near the reduced-data ERM solution ŵZ\U to the full-data ERM solution ŵZ . We calibrate the optimal geometry and probabilities needed to satisfy the ε-likelihood-ratio constraint while achieving an advantage over retraining from scratch by a factor of e−Θ(ε/d) .

Table 1: Excess-risk rates for ε-unlearning up to m points. We suppress logarithmic, Lipschitz, strongconvexity, smoothness, and condition-number factors. For prior algorithms, we report the sharpened or corrected rates proved in the Appendix. Method / result DP baseline Retrain from scratch ERM / warm-start unlearning Newton-step unlearning Our upper bound Our lower bound

Excess-risk rate

Reference / comments

1 d2 m2 + 2 2 n ε n m 2 1 + n n m 2 1 + n n m 2 1 d2 m4 + + 2 4 n n ε n m 2 1 + e−2ε/(d+2) n n m 2 1 + e−2ε/(d+2) n n

Group DP and [ALD21] Exact 0-unlearning; Theorem 5 [AKGK25]; corrected in Theorem 7 [SAKS21]; sharpened in Theorem 8; requires Lipschitz Hessian Optimal up to condition number; tight for mean estimation Optimal up to condition number; tight for mean estimation

Our lower bound uses packing techniques, but departs from standard DP packing arguments. In unlearning, the algorithm may see the unlearning set and arbitrary side information, so DP-style neighboring-dataset indistinguishability alone is not enough. Instead, we construct many separated mean-estimation instances whose nonzero signal samples can be deleted with high probability. After deletion, the retained datasets collapse to a common reference dataset, so ε-unlearning forces the output distributions for all packed instances to be close to one common reference distribution. A packing argument then yields the matching e−Θ(ε/d) unlearning penalty.

1.1

Preliminaries

Let ∥ · ∥ denote the Euclidean norm. Let Bd denote the d-dimensional Euclidean unit ball and let W ⊆ Rd be a domain. For a differentiable function h : W → R, we say h is L-Lipschitz if |h(w) − h(u)| ≤ L∥w − u∥ for all w, u ∈ W; µ-strongly convex if h(u) ≥ h(w) + ⟨∇h(w), u − w⟩ + µ2 ∥u − w∥2 for all w, u ∈ W; and β-smooth if h(u) ≤ h(w) + ⟨∇h(w), u − w⟩ + β2 ∥u − w∥2 for all w, u ∈ W. For smooth strongly convex losses, κ := β/µ denotes the condition number. We make the following assumption throughout, which is standard in the theoretical study of unlearning [SAKS21, AKGK25]. Unlike [SAKS21], we do not require that Hessian of the loss is Lipschitz. Assumption 1 (Smooth strongly convex SCO). The following conditions hold: 1. The parameter domain W ⊆ Rd is closed, convex, and has finite Euclidean diameter supw,w′ ∈W ∥w − w′ ∥. 2. For every z ∈ Z, the loss f (·, z) : W → R is differentiable and L-Lipschitz on W. 3. For every z ∈ Z, the loss f (·, z) is µ-strongly convex on W. 4. For every z ∈ Z, the loss f (·, z) is β-smooth on W. 5. The population minimizer wP∗ := argminw∈W FP (w) satisfies ∇FP (wP∗ ) = 0. Moreover, we will fix throughout a dataset size n ≥ 1 as well as unlearning capacity 1 ≤ m < n. As in [SAKS21], non-trivial unlearning guarantees can only be provided in the regime where m ≤ cn for a constant c < 1. In particular, we assume throughout that n − m = Ω(n). Now, for a dataset Z = (z1 , . . . , zn ), let Pn FbZ (w) := n1 i=1 f (w, zi ) and, for an unlearning set U ⊆ Z, let Z \ U denote the retained dataset. Approximate Unlearning. For random variables X, Y on the same measurable space, write X ≈ε,δ Y if for every measurable event E, both Pr(X ∈ E) ≤ eε Pr(Y ∈ E) + δ and Pr(Y ∈ E) ≤ eε Pr(X ∈ E) + δ. We follow the definition of approximate unlearning used in [SAKS21] but do not impose any storage constraints

on the unlearner. On input data Z, any learning algorithm A(Z) is applied. Afterward, the unlearner Ã takes as inputs the unlearning set U and the dataset Z and must return a model that is ≈ε,δ -close to the model that the unlearner would return given a learner input Z \ U in the absence of any unlearning request. In general, the unlearner would also take the output of the learner A(Z) as well as some stored information T (Z) instead of necessarily the whole dataset Z. In our case, we allow the unlearner full storage, meaning T (Z) = Z. Thus, in our setting, the unlearner has access to the full data set Z and the unlearning set U , as well as the learned model A(Z). Definition 1 (Approximate ε-unlearning). An algorithm Ã satisfies ε-unlearning for up to m deletions if, for every dataset Z ∈ Z n and every deletion set U ⊆ Z with |U | ≤ m, Ã(U, Z) ≈ε,0 Ã(∅, Z \ U ). We measure utility by worst-case expected excess population risk after up to m deletions. Definition 2. We say that Ã achieves expected excess unlearning risk α if for every distribution P ∈ ∆(Z) and n − m ≤ N ≤ n and any adversarial unlearning request U (Z) ⊆ Z such that |Z \ U (Z)| ≥ n − m, we have h i FP (Ã(U (Z), Z)) − FP∗ ≤ α. E Ã,Z∼P N

We note that our definition is slightly different than that of prior work including [SAKS21], which only requires good performance on Ã(U, Z), Z ∼ P n , the model released after an unlearning request. Our stronger definition also requires good performance on Ã(∅, S), S ∼ P n−m , the model trained on the dataset in which the unlearned data was not included to begin with. We present in Section B analogous matching upper and lower bounds for the weaker definition more common in prior work. We argue that the optimal unlearner in that setting behaves in a way contrary to the spirit of machine unlearning and we therefore advocate the adoption of our stronger notion of utility. Retraining from scratch (RFS) is defined by Ã(U, Z) := argminw∈W FbZ\U (w) in combination with empty unlearning request run Ã(∅, Z \ U ) := argminw∈W FbZ\U (w); this satisfies exact 0-unlearning by definition. Differential privacy gives another generic route: if A is ε-DP for groups of size m, then A(Z) is already ε-close in distribution to A(Z \ U ), so no unlearning-time update is needed (i.e., Ã(U, Z) = A(Z)). In particular, by group privacy, an (ε/m)-DP algorithm at the individual-sample level yields ε-unlearning for unlearning sets of size at most m.

Upper Bounds for ε-Unlearning

In this section, we provide a novel algorithm for ε-unlearning that achieves excess population risk 2 1 m 2 −2ε/(d+2) L + e , O κ µ n n for SCO and O(1/n + (m/n)2 e−2ε/(d+2) ) mean squared error for mean estimation on a unit ball. Thus, our algorithm gives an exponential improvement over the retrain-from-scratch rate of Θ((m/n)2 ) in the regime ε = Ω(d). These upper bounds are tight up to O(κ) and O(1) respectively. P 1 b For any dataset S, write FbS (w) := |S| z∈S f (w, z) and ŵS ∈ argminw∈W FS (w). Our algorithm. Consider the following two extreme algorithms for unlearning. To achieve high accuracy at the expense of providing no unlearning guarantees, an ERM unlearner given a dataset Z and an unlearning request U should simply ignore the request and return the full-data ERM solution ŵZ . On the other hand, to achieve a perfect unlearning guarantee at the expense of accuracy, the unlearner should retrain from scratch and return the ERM solution on the reduced dataset ŵZ\U .

Algorithm 1 Core-swap ε-unlearning for ERM Require: Dataset T ; deletion set U ⊆ T ; parameters L, µ, n, m, d, ε bS (w) as well as ŵT ← argminw∈W FbT (w) 1: Set S ← T \ U and compute ŵS ← argminw∈W F 2Lm 1 −ε/(d+2) 2: Set r ← µ(n−m) , τ ← r min{1, 2e }, and η ← ε d τ (e −1)( τ +r ) +1 ( Unif((τ + r)Bd + ŵS ) w.p. η 3: Sample w̃ ∼ Unif(τ Bd + ŵT ) w.p. 1 − η 4: return argminw∈W ∥w − w̃∥

At a high-level, our ERM unlearner works by optimally interpolating between these two algorithms to provide the desired level of unlearning while maximizing the accuracy. More precisely, given a dataset Z and a (possibly empty) unlearning request U , our unlearner returns with high probability a solution sampled uniformly from a small ball centered around the full-data ERM solution ŵZ . However, when the learner is run “dry” on a reduced dataset S and an empty unlearning request, the unlearner must provide plausible deniability to any true runs of the unlearner provided with a dataset Z and an unlearning request U that resolves to S = Z \ U . To achieve this, the unlearner also returns, with low probability, a sample from a wider ball centered around the reduced-data ERM ŵS that is just large enough to capture any full-data ERM solutions ŵZ that may reduce to S = Z \ U by a legal unlearning request. Figure 1 visualizes the sampling distributions of the unlearning process when run dry compared to a true run of the unlearner. Algorithm 1 provides the pseudocode, which is written for a generic input dataset T . In the true unlearning call, T = Z and the deletion set is U . In the reference empty-deletion dry run, T = Z \ U and the deletion set is ∅.

e A(∅, Z \ U)

e Z) A(U, w bZ

w bZ\U

Figure 1: We compare the distribution of Ã(∅, Z \ U ) to Ã(U, Z). Lightly shaded regions are sampled uniformly with low probability and heavily shaded regions are sampled uniformly with high probability. With high probability, Ã(∅, Z \ U ) returns a solution very close to the RFS ERM solution ŵZ\U and, with small probability, a sample from a ball surrounding it. Ã(U, Z) has the same distribution except that ball centered around the inaccurate RFS solution ŵZ\U is shifted to capture the full ERM solution ŵZ . Guarantees of Algorithm 1. We now formally record our main upper bound guarantees. Theorem 1 (Main Upper Bound). Grant Assumption 1. Then the unlearner Algorithm 1 satisfies εunlearning and runs in time O(d) after making two calls to an ERM oracle as well as a convex W-projection oracle. Moreover, Algorithm 1 achieves expected excess unlearning risk 2 L 1 m 2 −2ε/(d+2) α=O κ + e . µ n n 5

In the special case of mean estimation over the unit ball, i.e. W = Z = Bd and f (w, z) = 12 ∥w − z∥2 , Algorithm 1 achieves expected excess post-unlearning risk 1 m 2 −2ε/(d+2) α=O e . + n n The key proof idea is that the empty-deletion distribution for S = Z \ U places small probability mass near every possible full-data ERM ŵZ . The unlearning step moves the high-probability mass from a region near ŵS onto a region near ŵZ . Verifying the unlearning guarantee thus involves bounding just one likelihood ratio, while utility follows from carefully controlling the slack radius τ and the probability η of selecting a noisy solution. Our utility analysis separates the statistical error of ŵZ from the randomization cost of unlearning. To formally prove Theorem 1, we proceed in three steps. First, Proposition 1 shows that Algorithm 1 satisfies ε-unlearning. Second, Proposition 2 shows that its output is close to the full-data ERM ŵZ . Finally, we combine this ERM-distance guarantee with the standard stability-induced distance bound between ŵZ and the population minimizer wP∗ to obtain our excess population risk guarantee. Proposition 1. The unlearner Algorithm 1, satisfies ε-unlearning. Proof. Unlearning is preserved by postprocessing, so we may exclude the final projection onto W from our analysis. Now, fix U ⊆ Z ∈ Z N with n − m ≤ N ≤ n and |Z \ U | ≥ n − m. The distribution of Ã(∅, Z \ U ) before projection is W̃∅,Z\U = (1 − η)Unif(τ Bd + ŵZ\U ) + ηUnif((τ + r)Bd + ŵZ\U ) | | {z } {z } =:G

=:B

whereas the distribution of running Ã(U, Z) before projection is W̃U,Z = (1 − η)Unif(τ Bd + ŵZ ) + ηUnif((τ + r)Bd + ŵZ\U ). | {z } | {z } =:G′

We just need to argue that the likelihood ratio between these distributions lies in [e−ε , eε ]. Indeed, by the standard stability bound for strongly convex ERM (c.f. [SAKS21, Lemma 6]), ∥ŵZ − ŵZ\U ∥ ≤

2Lm 2L|U | ≤ = r. µ|Z \ U | µ(n − m)

In particular, G′ is contained in B and hence the likelihood ratio between these distributions differs only for w contained in either G or G′ , exclusively. In the first case, the ratio of probability density functions is d dW̃∅,Z\U (1 − η)/Vol(G) + η/Vol(B) 1 Vol(B) 1 τ +r (w) = =1+ −1 =1+ −1 = eε η/Vol(B) η Vol(G) η τ dW̃U,Z by choice of η and, analogously, we have

dW̃∅,Z\U (w) = e−ε for w ∈ G′ \ G. In particular, W̃∅,Z\U and W̃U,Z dW̃U,Z

are (ε, 0)-indistinguishable, as desired. Proposition 2 (Distance to the Full-Data ERM). For every n − m ≤ N ≤ n, dataset Z ∈ Z N , and deletion request U ⊆ Z with |Z \ U | ≥ n − m, the output Ã(U, Z) of Algorithm 1 satisfies 2 2 L m 2 −2ε/(d+2)) Ã(U, Z) − ŵ = O e . E Z µ2 n Ã Proof. Recall as in the proof of Proposition 1 that Ã(U, Z) is exactly the projection of w̃ ∼ (1 − η)Unif(τ Bd + ŵZ ) + ηUnif((τ + r)Bd + ŵZ\U ) 6

onto the convex domain W. But ŵZ ∈ W, so 2 2 2 E[∥Ã(U, Z) − ŵZ ∥ ] ≤ E[∥w̃ − ŵZ ∥ ] ≤ (1 − η)τ + η Ã

max w∈(τ +r)Bd +ŵZ\U

∥w − ŵZ ∥2 .

Recalling that n − m = Ω(n), the first term is bounded by 2 o2 n L2 m L2 m 2 −2ε/(d+2) 2 −ε/(d+2) τ = r min 1, 2e ≲ 2 e−2ε/(d+2) ≲ 2 e . µ n−m µ n As for the second term, recalling that ∥ŵZ\U − ŵZ ∥ ≤ r as well as our choice of τ ≤ r, we have ∥w − ŵZ ∥2 ≤ 2∥w − ŵZ\U ∥2 + 2∥ŵZ\U − ŵZ ∥2 ≤ 2(τ + r)2 + 2r2 ≤ 10r2 ≲

L2 m 2 µ2 n

for any w ∈ (τ + r)Bd + ŵZ\U . Moreover, if 2e−ε/(d+2) > 1, then η ≤ 1 = 12 ≲ e−2ε/(d+2) . More importantly, if 2e−ε/(d+2) ≤ 1, then clearly 1 ≤ 12 eε and τ = 2re−ε/(d+2) by choice of τ , so it follows that η= (eε − 1)

τ τ +r

≲ e−ε +1

2r τ

d d = e−ε eε/(d+2) = e−ε(1− d+2 ) = e−2ε/(d+2)

in this case as well. The result now follows by combining these bounds. Lemma 1 (ERM Distance to the Population Minimizer). For any N ≥ n − m and distribution P over Z, we have 2 L ∗ 2 , E ∥ŵZ − wP ∥ = O N µ2 n Z∼P where wP∗ = argminw∈W FP (w). Proof. This follows from the standard expected excess-risk bound for ERM with L-Lipschitz, µ-strongly convex losses, 2 2 L L ∗ =O , E [FP (ŵZ ) − FP ] = O µN µn Z∼P N see e.g. [SSSSS09], together with µ-strong convexity of FP and N = Ω(n). We now combine the above results to prove our main upper bound theorem. Proof of Theorem 1. Unlearning. The unlearning claim is exactly Proposition 1. Runtime. It is clear that Algorithm 1 makes only two ERM calls and requires only one convex projection onto W. The remaining runtime is dominated by the cost of uniform sampling from d-dimensional balls of the form ρBd + c, which can be implemented in O(d) time by noticing that G ∼ N (0, 1)d , T ∼ Unif([0, 1]) =⇒ T 1/d ·

G ∼ Unif(Bd ). ∥G∥

Excess risk. Fix any unlearning request strategy U (Z) ⊆ Z with |Z\U (Z)| ≥ n−m as well as n−m ≤ N ≤ n and consider smooth strongly convex SCO. By smoothness of FP and the assumption ∇FP (wP∗ ) = 0, FP (w) − FP∗ ≤

β ∥w − wP∗ ∥2 . 2

Applying ∥a + b∥2 ≤ 2∥a∥2 + 2∥b∥2 with w = Ã(U (Z), Z), we get FP (Ã(U (Z), Z)) − FP∗ ≤ β∥Ã(U (Z), Z) − ŵZ ∥2 + β∥ŵZ − wP∗ ∥2 . 7

In particular, Proposition 2 and Lemma 1 together yield 2 i h L 1 m 2 −2ε/(d+2) ∗ FP (Ã(U (Z), Z)) − FP = O κ + e , E µ n n Ã,Z∼P N where we used β/µ = κ. This is the claimed SCO bound. Similarly, for mean estimation over Bd , wP∗ = µP := EP [z] and FP (w) − FP∗ = 12 ∥w − µP ∥2 . and therefore FP (Ã(U (Z), Z)) − FP∗ ≲ ∥Ã(U (Z), Z) − ŵZ ∥2 + ∥ŵZ − µP ∥2 . PN Moreover, ŵZ = N1 i=1 zi , so E[∥ŵZ − µP ∥2 ] ≤ N1 ≲ n1 and, combining with Proposition 2, we get the desired excess unlearning risk 1 m 2 −2ε/(d+2) O + e . n n

Lower Bounds for ε-Unlearning

In this section we prove a lower bound nearly matching the rate of our ERM unlearner. We begin with a mean estimation lower bound. Theorem 2. Let Ã(U, Z) be an ε-unlearning algorithm and suppose that for all distributions P on Bd with mean µP , all unlearning requests U (Z) ⊆ Z with |Z \ U (Z)| ≥ n − m, and any n − m ≤ N ≤ n, we have the mean squared error guarantee h i ∥Ã(U (Z), Z) − µP ∥2 ≤ α. E Ã,Z∼P N

Then, it must be the case that α=Ω

1 m 2 −2ε/(d+2) e . + n n

The first term Ω(1/n) is the mean squared error lower bound even without unlearning requirements (see, e.g. [Duc21]). The second term is what we will prove in this section. As a consequence of our mean estimation lower bound, we obtain our SCO lower bound: Corollary 1. Suppose the loss satisfies Assumption 1 and that there is an ε-unlearning algorithm Ã with has excess unlearning risk α. Then we must have 2 L 1 m 2 −2ε/(d+2) α≥Ω + e µ n n The first term Ω(L2 /(µn)) holds for SCO without unlearning constraints [NY83]. The second follows from Theorem 2 and a standard reduction from SCO to mean estimation (see e.g., [LR25, Proof of Theorem 8]). Lower-bound intuition. We construct distributions whose means point in many separated directions, but whose nonzero signal samples can all be removed with high probability by a valid unlearning request. After this deletion, all hard instances induce the same retained dataset, so the unlearning guarantee forces their output distributions to be close to a common reference distribution. The packing size of the possible mean directions then limits how accurately all means can be recovered. Proof of Theorem 2. We now develop the tools that will be needed to prove Theorem 2. Just as our algorithm exploits covering geometry, our lower bound will exploit the packing geometry of the ball Bd .

Lemma 2. For any 0 < τ < 1, there exists V ⊆ Bd \ 12 Bd of size |V| ≥ 12 any v ̸= v ′ ∈ V.

1 d for which ∥v − v ′ ∥ > τ for τ

Indeed, by a standard volumetric packing argument (see e.g. Section 4.2 of [Ver18]), we can find a τ -separated d −d Vol(Bd \ 12 Bd ) Vol(Bd ) subset V ⊆ Bd \ 21 Bd of size |V| ≥ Vol(τ = Vol(Bτd d)−2 ≥ 12 τ1 . Bd ) Vol(Bd ) Next, we show that, for a well-structured class of contaminated mixture distributions, deleting on the order of m samples leaves a common distribution. Consequently, any algorithm that handles unlearning requests of size up to m cannot effectively distinguish these distributions. Lemma 3. Let n ≥ 1, v ∈ Bd , and η ∈ [0, 1/5] be such that m := 5ηn is an integer. There exists a distribution Pv,η on Bd with mean ηv such that, given Z ∈ Bnd , we can construct an unlearning request U (Z) ⊆ Z of size m for which P

n Z∼Pv,η

(Z \ U (Z) ̸= 0n−m ) ≤ 2−m ,

where 0n−m := (0, . . . , 0) denotes the dataset consisting of n − m zeroes. Proof. Consider the contaminated mixture Pv,η := (1 − η)10 + η1v . n Sample Z ∼ Pv,η and let K ∼ Bin(n, η) be the number of non-zero entries in Z. Now, consider the unlearning request U (Z) such that, when K > m, U (Z) removes any m entries from Z and, when K ≤ m, U (Z) removes all of the non-zero entries as well as other entries arbitrarily so that exactly m entries are removed in total.

Clearly, Z \ U (Z) = 0n−m as long as K ≤ m, so by a multiplicative Chernoff bound we get that 4 ηn e (K > 5ηn) ≤ ≤ (2−5 )ηn = 2−m . P n (Z \ U (Z) ̸= 0n−m ) ≤ P 55 Z∼Pv,η K∼Bin(n,η)

Finally, we require a slight variant of the standard technique of packing lower bounds from the differential privacy literature. Lemma 4. Let P ∗ , P1 , . . . , Pk be real-valued distributions such that we can find disjoint events E1 , . . . , Ek for which Pi (Ei ) ≥ p as well as Pi ≈ε,δ P ∗ for each i ≤ k. Assume additionally that we can find µ ∈ Rd so that EW ∼P ∗ [∥W − µ∥2 ] ≤ α and ∥w − µ∥ ≥ η for each w ∈ Ei and i ≤ k. Then eε ≥

kη 2 (p − δ). α

Proof. By disjointness of the Ei , we have α≥

2 E ∗ [∥W − µ∥ ] ≥

W ∼P

k Z X i=1

∥w − µ∥2 dP ∗ (w) ≥ η 2

k X

P ∗ (Ei ) ≥ kη 2 e−ε (p − δ),

i=1

which immediately yields the desired bound. We now have assembled all of the tools needed to show Theorem 2. For convenience, we will write g(X)|X∼P to denote the distribution of g(X), X ∼ P . √ √ α ≥ 81 η, we are done, so assume that α < 18 η and set τ := 4 η α < 1. d By Lemma 2, we can find a τ -separated V ⊆ Bd \ 12 Bd of size |V| ≥ 12 4√η α . m Proof of Theorem 2. Set η := 5n . If

√

Now, for each v ∈ V, recall the hard distribution Pv,η and corresponding delete request Uv (Z) as in Lemma 3. n We claim that Ã(Uv (Z), Z)|Z∼Pv,η ≈ε,2−m Ã(∅, 0n−m ). Indeed, for any event E, P

(Z \ Uv (Z) = 0n−m and Ã(Uv (Z), Z) ∈ E) + 2−m

(Ã(Uv (Z), Z) ∈ E) ≤

n Ã,Z∼Pv,η

≤ ≤

n Z∼Pv,η

−m P(Ã(Uv (Z), Z) ∈ E) Z \ Uv (Z) = 0n−m + 2 eε P(Ã(∅, Z \ Uv (Z)) ∈ E) Z \ Uv (Z) = 0n−m + 2−m Ã

Ã

= e P(Ã(∅, 0n−m ) ∈ E) + 2−m ε

Ã

and, analogously, PÃ (Ã(∅, 0n−m ) ∈ E) ≤ eε PÃ,Z∼P n (Ã(Uv (Z), Z) ∈ E) + 2−m as well. v,η

On the other hand, by Markov’s inequality and our assumption on the mean √ squared error, for every v ∈ V we have PÃ,Z∼P n (Ã(Uv (Z), Z) ∈ Ev ) ≥ 3/4 where Ev := {w : ∥w − ηv∥ ≤ 2 α}. Since the packing V has v,η

√

separation τ = 4 η α , the Ev are disjoint. In addition, we have h i 2 E ∥Ã(∅, 0n−m )∥ = Ã

h i 2 E n−m ∥Ã(∅, Z)∥ ≤ α

Ã,Z∼10

by the mean squared error assumption. Finally, for all v ∈ V and w ∈ Ev , since ∥v∥ > 1/2, we must have √ ∥w∥ ≥ ∥ηv∥ − ∥w − ηv∥ ≥ η/2 − 2 α ≥ η/4. Altogether, Lemma 4 yields d d+2 d+2 3 η η2 η m √ √ √ − 2−m ≥ ≥ = . 4 128α 4 α 128 α 640n α 1 m 2 −2ε/(d+2) In particular, we have α ≥ 640 e . 2 n eε ≥

|V|(η/4)2 α

Conclusion

We determined the minimax optimal rate for ε-approximate machine unlearning in smooth strongly convex stochastic optimization up to a condition-number factor. Our results show that the optimal excess population risk consists of the usual statistical error plus an unlearning penalty that depends exponentially on the ratio ε/d. In particular, retraining from scratch is statistically optimal when ε ≲ d, whereas in the regime ε ≫ d, our novel algorithm improves exponentially over retraining from scratch. For mean estimation over the unit ball, our upper and lower bounds match up to constants in the exponent, giving an essentially sharp characterization of the statistical price of unlearning in this canonical setting. Several questions remain open for future work. First, our upper and lower bounds for general smooth strongly convex SCO differ by a condition-number factor; closing this gap would give a fully sharp minimax characterization beyond mean estimation and would help pave the way for nonsmooth and non-strongly convex SCO algorithms. Extending the minimax theory of unlearning to nonconvex optimization is an important goal to aim for. Finally, we leave open the optimal rates for (ε, δ)-unlearning and for unlearning under explicit storage and/or computational constraints.

Acknowledgments We thank Hilal Asi for early discussions as well as Jacob Imola for discussions on efficient sampling. MR was supported by an NSERC CGS-D scholarship. GK was supported by a Canada CIFAR AI Chair, an NSERC Discovery Grant, and an Ontario Early Researcher Award. 10

References [AKGK25] Youssef Allouah, Joshua Kazdan, Rachid Guerraoui, and Sanmi Koyejo. The utility and complexity of in-and out-of-distribution machine unlearning. In The Thirteenth International Conference on Learning Representations, 2025. [ALD21] Hilal Asi, Daniel Levy, and John Duchi. Adapting to function difficulty and growth conditions in private optimization. volume 34, pages 19069–19081, 2021. [BCCC+ 21] Lucas Bourtoule, Varun Chandrasekaran, Christopher A. Choquette-Choo, Hengrui Jia, Adelin Travers, Baiwu Zhang, David Lie, and Nicolas Papernot. Machine unlearning. In Proceedings of the 42nd IEEE Symposium on Security and Privacy, pages 141–159. IEEE, 2021. [CWCL24] Eli Chien, Haoyu Peter Wang, Ziang Chen, and Pan Li. Certified machine unlearning via noisy stochastic gradient descent. In Advances in Neural Information Processing Systems, volume 37, 2024. [CY15] Yinzhi Cao and Junfeng Yang. Towards making systems forget with machine unlearning. In 2015 IEEE Symposium on Security and Privacy, pages 987–1004. IEEE, 2015. [DMNS06] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Theory of cryptography conference, pages 265–284. Springer, 2006. [Duc21] John Duchi. Lecture notes for statistics 311/electrical engineering 377. URL: https://stanford. edu/class/stats311/Lectures/full_notes.pdf, 2021. [Eur16] European Union. Regulation (EU) 2016/679 of the European Parliament and of the Council of 27 April 2016 on the protection of natural persons with regard to the processing of personal data and on the free movement of such data (General Data Protection Regulation). Official Journal of the European Union, L119, 1–88, 2016. [GGHvdM20] Chuan Guo, Tom Goldstein, Awni Hannun, and Laurens van der Maaten. Certified data removal from machine learning models. In Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 3832–3842. PMLR, 2020. [HC25] Yiyang Huang and Clément L. Canonne. Tight bounds for machine unlearning via differential privacy. Journal of Privacy and Confidentiality, 15(2), 2025. [ISCZ21] Zachary Izzo, Mary Anne Smart, Kamalika Chaudhuri, and James Zou. Approximate data deletion from machine learning models. In Proceedings of the 24th International Conference on Artificial Intelligence and Statistics, volume 130 of Proceedings of Machine Learning Research, pages 2008–2016. PMLR, 2021. [LLQR23] Jiaqi Liu, Jian Lou, Zhan Qin, and Kui Ren. Certified minimax unlearning with generalization rates and deletion capacity. Advances in Neural Information Processing Systems, 36:62821– 62852, 2023. [LR25] Andrew Lowy and Meisam Razaviyayn. Private stochastic optimization with large worst-case lipschitz parameter. Journal of Privacy and Confidentiality, 15:1, 2025. [NRSM21] Seth Neel, Aaron Roth, and Saeed Sharifi-Malvajerdi. Descent-to-delete: Gradient-based methods for machine unlearning. In Proceedings of the 32nd International Conference on Algorithmic Learning Theory, volume 132 of Proceedings of Machine Learning Research, pages 931–962. PMLR, 2021. [NY83] A. Nemirovski and D. Yudin. Problem complexity and method efficiency in optimization. Chichester, 1983. [QZTW25] Xinbao Qiao, Meng Zhang, Ming Tang, and Ermin Wei. Hessian-free online certified unlearning. In International Conference on Learning Representations, 2025.

[SAKS21] Ayush Sekhari, Jayadev Acharya, Gautam Kamath, and Ananda Theertha Suresh. Remember what you want to forget: Algorithms for machine unlearning. Advances in Neural Information Processing Systems, 34:18075–18086, 2021. [SSSSS09] Shai Shalev-Shwartz, Ohad Shamir, Nathan Srebro, and Karthik Sridharan. Stochastic convex optimization. In COLT, volume 2, page 5, 2009. [UMR+ 21] Enayat Ullah, Tung Mai, Anup Rao, Ryan A. Rossi, and Raman Arora. Machine unlearning via algorithmic stability. In Proceedings of Thirty Fourth Conference on Learning Theory, volume 134 of Proceedings of Machine Learning Research, pages 4126–4142. PMLR, 2021. [Ver18] Roman Vershynin. High-dimensional probability: An introduction with applications in data science, volume 47. Cambridge university press, 2018. [VWLNS25] Martin Van Waerebeke, Marco Lorenzi, Giovanni Neglia, and Kevin Scaman. When to forget? complexity trade-offs in machine unlearning. arXiv preprint arXiv:2502.17323, 2025. [ZAK+ 25] Haolin Zou, Arnab Auddy, Yongchan Kwon, Kamiar Rahnama Rad, and Arian Maleki. Certified machine unlearning under high dimensional regime. Journal of Machine Learning Research, 26(308):1–58, 2025.

Appendix A

Additional Related Work

We discuss additional related work on machine unlearning, certified removal, and differentially private baselines. See the introduction for the works most directly comparable to our results. Certified removal and approximate data unlearning. Guo et al. [GGHvdM20] introduced certified data removal, requiring that a model after data removal be statistically indistinguishable from one trained without the removed data, and developed certified-removal mechanisms for linear classifiers. Izzo et al. [ISCZ21] proposed approximate unlearning methods for linear and logistic models whose unlearning-time cost is linear in the feature dimension and independent of the number of training samples. These works emphasize efficient approximate unlearning for specific model classes, while our work characterizes minimax population-risk rates for ε-unlearning in smooth strongly convex stochastic optimization. Practical machine unlearning and exact unlearning frameworks. Bourtoule et al. [BCCC+ 21] introduced SISA training, a practical framework for accelerating unlearning by sharding, isolating, slicing, and aggregating the training procedure. Their work helped popularize machine unlearning as a practical datagovernance problem and focused primarily on reducing unlearning-time computation relative to retraining. This line of work is complementary to ours: we focus on the information-theoretic statistical cost of approximate unlearning in stochastic optimization. Gradient-based and stability-based unlearning. Neel et al. [NRSM21] study data unlearning for convex models and introduce gradient-based unlearning algorithms that can handle long sequences of adversarial updates with per-unlearning runtime and steady-state error not growing with the sequence length. Ullah et al. [UMR+ 21] connect unlearning to total-variation stability and design noisy-SGD-based algorithms with efficient unlearning procedures. Chien et al. [CWCL24] later study certified machine unlearning via projected noisy stochastic gradient descent and establish approximate unlearning guarantees under convexity assumptions. These works are algorithmic and computationally motivated; whereas our focus is the minimax statistical rate. Certified unlearning for convex and strongly convex learning. Sekhari et al. [SAKS21] initiated a population-risk study of certified unlearning for convex learning and gave algorithms with unlearning-capacity guarantees, including a Newton-step method for smooth strongly convex losses. Their method improves over 12

DP baselines in some regimes, but requires stronger smoothness assumptions such as Lipschitz Hessians. In Appendix E, we sharpen the analysis of this algorithm. Youssef et al. [AKGK25] study utility guarantees for in-distribution unlearning and propose a warm-start ERM procedure. In Appendix D, we identify a gap in their population-risk argument and provide a corrected retraining-level guarantee. Van Waerebeke et al. [VWLNS25] study computational aspects of unlearning for strongly convex losses. These works are the closest algorithmic precursors to ours. DP-based and restricted unlearning. Differential privacy gives a generic route to unlearning: by group privacy, an algorithm private enough for changes of size m automatically satisfies an unlearning guarantee for unlearning sets of size m. Huang and Canonne [HC25] give tight bounds for machine unlearning via differential privacy and for restricted unlearning models, including settings with a DP-based algorithm that does not use side information or the unlearning set. Their results show that DP-based unlearning is optimal in these restricted models. Our results show that unrestricted unlearning is more powerful than DP-based unlearning: by using the actual unlearning set and side information, retrain-from-scratch achieves superior excess risk to DP when ε ≤ d and our approximate unlearning algorithm can achieve an exponentially smaller unlearning penalty when ε ≫ d. Other optimization settings. Liu et al. [LLQR23] study certified unlearning for minimax models and derive generalization rates and unlearning-capacity bounds for convex-concave and strongly convex-strongly concave settings. Zou et al. [ZAK+ 25] study certified machine unlearning in proportional high-dimensional regimes, analyzing Newton-style procedures when the model dimension and sample size grow together. These works address different optimization or asymptotic settings and are complementary to our minimax analysis for smooth strongly convex stochastic optimization. Broader unlearning literature. There is also a large empirical and systems-oriented literature on machine unlearning for neural networks, graphs, federated learning, recommendation systems, and foundation models. These works address important practical settings and evaluation questions, but typically do not provide excess risk bounds under certified ε-unlearning. We therefore focus our theoretical comparisons on certified unlearning methods and DP-based baselines with formal guarantees.

Matching Bounds for Unlearning Under the Weaker Utility Assumption

In this section, we consider the effect of replacing the expected excess unlearning risk measure in Definition 2 with the weaker definition seen in prior work, which we call expected excess post-unlearning risk. Definition 3. We say that Ã achieves expected excess post-unlearning risk α if for every distribution P ∈ ∆(Z) and any adversarial unlearning request U (Z) ⊆ Z of size |U (Z)| ≤ m, we have h i FP (Ã(U (Z), Z)) − FP∗ ≤ α. E Ã,Z∼P n

B.1

Upper Bound for Post-Unlearning

Theorem 3 (Post-Unlearning Upper Bound). Grant Assumption 1 and assume d ≥ 2. Then the unlearner Algorithm 2 satisfies ε-unlearning and runs in time O(d) after making two calls to an ERM oracle as well as a convex W-projection oracle. Moreover, Algorithm 2 achieves expected excess post-unlearning risk 2 L 1 m 2 −2ε/d α=O κ + e . µ n n In the special case of mean estimation over the unit ball, i.e. W = Z = Bd and f (w, z) = 12 ∥w − z∥2 , Algorithm 2 achieves expected excess post-unlearning risk 1 m 2 −2ε/d α=O + e . n n 13

Algorithm 2 Core-diffusion ε-unlearning for ERM Require: Dataset T ; deletion set U ⊆ T ; parameters L, µ, n, m, d, ε bS (w) as well as ŵT ← argminw∈W FbT (w) 1: Set S ← T \ U and compute ŵS ← argminw∈W F ε d 2Lm τ +r 2: Set r ← µn , τ ← r min{1, 2e−ε/d }, K ← , and η ← max{e−ε , K−e τ K−1 } 3: if U = ∅ and |T | < n then 4: Sample w̃ ∼ Unif((τ + r)Bd + ŵS ) 5: else ( Unif((τ + r)Bd + ŵS ) w.p. η 6: Sample w̃ ∼ Unif(τ Bd + ŵT ) w.p. 1 − η 7: return argminw∈W ∥w − w̃∥

Critically, we note that Algorithm 2 inspects the sizes of the dataset and the unlearning request to determine whether it is performing a dry or a true unlearning run. Although this algorithm achieves the optimal rate for the post-unlearning utility model, we suggest that this algorithm’s behaviour goes against the spirit of machine unlearning. Therefore we advocate replacing the post-unlearning utility model Definition 3 with the stronger utility model Definition 2.

e A(∅, Z \ U)

e Z) A(U, w bZ

w bZ\U

Figure 2: We compare the distribution of Ã(∅, Z \ U ) to Ã(U, Z) for the unlearner Algorithm 2. Lightly shaded regions are sampled uniformly with low probability and heavily shaded regions are sampled uniformly with high probability. In this case, Ã(∅, Z \ U ) returns a noisy solution centered around the RFS ERM solution ŵZ\U . Ã(U, Z) has a similar distribution except some probability mass is transported into a small ball around the full ERM solution ŵZ . Proposition 3. The unlearner Algorithm 2, satisfies ε-unlearning. Proof. Unlearning is preserved by postprocessing, so we may exclude the final projection onto W from our analysis. Now, fix U ⊆ Z ∈ Z n , |U | ≤ m. If U = ∅, then clearly Ã(U, Z) ≡ Ã(∅, Z \ U ), so assume U = ̸ ∅. In this case, the distribution of Ã(∅, Z \ U ) before projection is W̃∅,Z\U = Unif((τ + r)Bd + ŵZ\U ) | {z } =:B

whereas the distribution of running Ã(U, Z) before projection is W̃U,Z = (1 − η)Unif(τ Bd + ŵZ ) + ηUnif((τ + r)Bd + ŵZ\U ). | {z } {z } | =:G′

2Lm = r. µn

In particular, G′ is contained in B and hence the likelihood ratio between these distributions differs only for w contained in either G′ or B, exclusively. In the first case, if w ∈ G′ , then dW̃∅,Z\U dW̃U,Z

(w) =

1/Vol(B) 1 1 = = ∈ [e−ε , 1] (1 − η)/Vol(G) + η/Vol(B) (1 − η)K + η K − η(K − 1)

′ since K−e K−1 ≤ η ≤ 1. In the latter case, if w ∈ B \ G , we have

dW̃∅,Z\U dW̃U,Z

(w) =

1/Vol(B) 1 = ∈ [1, eε ] η/Vol(B) η

since e−ε ≤ η ≤ 1. In particular, W̃∅,Z\U and W̃U,Z are (ε, 0)-indistinguishable, as desired. Proposition 4. Assume d ≥ 2. For every dataset Z ∈ Z n and every deletion set U ⊆ Z with |U | ≤ m, the output Ã(U, Z) of Algorithm 2 satisfies 2 2 L m 2 −2ε/d =O e . E Ã(U, Z) − ŵZ µ2 n Ã Proof. Recall as in the proof of Proposition 3 that Ã(U, Z) is exactly the projection of w̃ ∼ (1 − η)Unif(τ Bd + ŵZ ) + ηUnif((τ + r)Bd + ŵZ\U ) onto the convex domain W. But ŵZ ∈ W, so 2 2 2 E[∥Ã(U, Z) − ŵZ ∥ ] ≤ E[∥w̃ − ŵZ ∥ ] ≤ (1 − η)τ + η Ã

max w∈(τ +r)Bd +ŵZ\U

∥w − ŵZ ∥2 .

The first term is bounded by n o2 L2 m 2 −2ε/d τ 2 = r min 1, 2e−ε/d ≲ 2 e . µ n As for the second term, recalling that ∥ŵZ\U − ŵZ ∥ ≤ r as well as our choice of τ ≤ r, we have ∥w − ŵZ ∥2 ≤ 2∥w − ŵZ\U ∥2 + 2∥ŵZ\U − ŵZ ∥2 ≤ 2(τ + r)2 + 2r2 ≤ 10r2 ≲

L2 m 2 µ2 n

for any w ∈ (τ + r)Bd + ŵZ\U . Moreover, if 2e−ε/d > 1, then η ≤ 1 = 12 ≲ e−2ε/d . More importantly, if 2e−ε/d ≤ 1, then τ = 2re−ε/d by choice of τ , in which case d d d τ +r 2r 2r K= ≤ = = eε , τ τ 2re−ε/d and hence K − eε η = max e−ε , = e−ε ≤ e−2ε/d K −1 in this case as well. The result now follows by combining these bounds. As in the proof of Theorem 1, Theorem 3 now follows by combining Propositions 3 and 4 with Lemma 1. 15

B.2

Lower Bounds for Post-Unlearning

In this section we prove a lower bound matching the rate of Algorithm 2. At its core, this reduces to showing a mean estimation lower bound. Theorem 4. Let Ã(U, Z) be an ε-unlearning algorithm and suppose that, for all distributions P on Bd with mean µP and unlearning requests U (Z) ⊆ Z with |U (Z)| ≤ m, we have the mean squared error guarantee 2 ∥Ã(U (Z), Z) − µP ∥2 ≤ α ≥ . P 3 Ã,Z∼P n Then, it must be the case that α=Ω

1 m 2 −2ε/d + e . n n

By Markov’s inequality, the same lower bound applies up to constants for any algorithm with expected mean squared error O(α). Moreover, as in Section 3 the first term Ω(1/n) is the mean squared error lower bound even without unlearning requirements, so it just remains to derive the second term. As in Section 3, this implies the following SCO lower bound: Corollary 2. Suppose the loss satisfies Assumption 1 and that there is an ε-unlearning algorithm Ã with has excess post-unlearning risk α. Then we must have 2 L 1 m 2 −2ε/d + α≥Ω e µ n n The argument for Theorem 4 is very similar to that of Section 3, except that we rely on a weaker form of the packing technique. Lemma 5. Let P ∗ , P1 , . . . , Pk be distributions over a common space such that we can find disjoint events E1 , . . . , Ek for which Pi (Ei ) ≥ p as well as Pi ≈ε,δ P ∗ for each i ∈ {1, . . . , k}. Then eε ≥ k(p − δ). Proof. Indeed, by disjointness, we have 1≥

k X i=1

P ∗ (Ei ) ≥

k X

e−ε (Pi (Ei ) − δ) ≥

i=1

k X

e−ε (p − δ) = ke−ε (p − δ).

i=1

√ √ √ m Proof of Theorem 4. Set η := 5n . If α ≥ 21 η, we are done, so assume that α < 12 η and set τ := 2 η α < 1. By Lemma 2, we can find a τ -separated V ⊆ Bd of size d 1 η √ |V| ≥ . 2 2 α

Now, for each v ∈ V, recall the hard distribution Pv,η and corresponding delete request Uv (Z) as in Lemma 3. n As in the proof of Theorem 2, we have that Ã(Uv (Z), Z)|Z∼Pv,η ≈ε,2−m Ã(∅, 0n−m ) because Ã is ε-unlearning. On the other hand, by our assumption on the mean estimation error, for every v ∈ V we have √ 2 ≤ ∥Ã(Uv (Z), Z) − ηv∥ ≤ α . P 3 Ã,Z∼Pv,η n √ √ As the v ∈ V are 2 η α -separated, the {w : ∥w − ηv∥ ≤ α} are disjoint and hence Lemma 5 yields d d d 2 1 η η m ε −m √ √ √ e ≥ |V| −2 ≥ ≥ = . 3 6 2 α 12 α 60n α 2 −2ε/d In particular, we have α ≥ 6012 m e . n

Retrain-from-scratch Upper Bound

We first record the performance of the most basic exact-unlearning algorithm: retraining from scratch. Given a unlearning request U ⊆ Z, define ÃRFS (U, Z) := ŵZ\U ∈ argminw∈W FbZ\U (w), where FbZ\U (w) :=

X 1 f (w, zi ). |Z \ U | zi ∈Z\U

This algorithm ignores the original model and recomputes an empirical risk minimizer on the retained data. Its main drawback is that it requires storing the full dataset. Theorem 5 (Retrain-from-scratch upper bound). Assume that, for every z ∈ Z, the loss f (·, z) is L-Lipschitz, µ-strongly convex, and β-smooth over W. Let κ = β/µ. Then retraining from scratch is exact 0-unlearning. Moreover, L2 1 m 2 . max FP (ŵZ\U ) − FP∗ ≲ κ + En µ n n U ⊆Z: |U |≤m Z∼P Proof. The exact-unlearning guarantee is immediate. After receiving U , the algorithm outputs ŵZ\U , which is exactly the output obtained by running the learning algorithm directly on the retained dataset Z \ U . Hence the two output distributions are identical. It remains to prove the excess-risk bound. Let w∗ ∈ argminw∈W FP (w).

ŵZ ∈ argminw∈W FbZ (w),

Since F is β-smooth and w∗ minimizes F over W, we have FP (w) − FP∗ ≤

β ∥w − w∗ ∥2 2

∀w ∈ W.

Therefore, E

max

U ⊆Z: |U |≤m

FP (ŵZ\U ) − FP∗

β ∗ 2 ≤ E max ∥ŵZ\U − w ∥ 2 U ⊆Z: |U |≤m ∗ 2 ≤ β E ∥ŵZ − w ∥ + β E max

U ⊆Z: |U |≤m

∥ŵZ\U − ŵZ ∥

(3)

where the last step uses ∥a + b∥2 ≤ 2∥a∥2 + 2∥b∥2 . We bound the two terms in (3). First, standard stability/generalization bounds for L-Lipschitz, µ-strongly convex ERM imply L2 ∗ . E[FP (ŵZ ) − FP ] ≲ µn By µ-strong convexity of F , µ ∗ 2 ∗ E ∥ŵZ − w ∥ ≤ E[FP (ŵZ ) − FP ] , 2 and hence L2 ∗ 2 E ∥ŵZ − w ∥ ≲ 2 . µ n Second, the unlearning stability bound for strongly convex ERM gives, uniformly over all U ⊆ Z with |U | ≤ m, Lm ∥ŵZ\U − ŵZ ∥ ≲ . µn 17

For example, this is precisely the unlearning stability estimate used in [SAKS21, Lemma 6]. Therefore, L2 m2 max ∥ŵZ\U − ŵZ ∥2 ≲ 2 2 . E µ n U ⊆Z: |U |≤m Combining (3), (C), and (C) yields max E

U ⊆Z: |U |≤m

FP (ŵZ\U ) − FP∗

L2 ≲β 2 µ

1 m 2 . + n n

Since β/µ = κ, this is ≲κ

L2 µ

1 m 2 , + n n

as claimed. Remark 6. The proof uses only Lipschitzness, strong convexity, and smoothness on the constrained domain. Under these assumptions, the condition-number factor multiplies both the usual statistical term and the unlearning term. Removing the factor κ from the 1/n term would require an additional condition, such as an unconstrained/interior population minimizer or a smooth self-bounding inequality.

Corrected analysis of the ERM warm-start algorithm of [AKGK25]

In this section we revisit the ERM-based warm-start unlearning algorithm of [AKGK25]. At a high level, their algorithm is very close to retraining from scratch: after receiving a unlearning request, it approximately minimizes the empirical risk on the retained dataset, using the original trained model as a warm start, and then adds noise to certify unlearning. We give a corrected utility analysis showing that this approach achieves a retraining-from-scratch-level population-risk bound, up to the optimization error and the noise variance. We use our notation rather than the notation of [AKGK25]. Let Z = (z1 , . . . , zn ) ∼ P n , and for a unlearning set U ⊆ Z, let X 1 FbZ\U (w) := f (w, zi ), ŵZ\U ∈ argminw∈W FbZ\U (w). |Z \ U | zi ∈Z\U

The algorithm. The learner first computes an empirical risk minimizer ŵZ on the full dataset and stores the data Z. Upon receiving a unlearning request U , the unlearning algorithm runs an optimization method, initialized at ŵZ , on the retained empirical objective FbZ\U . Let wU denote the resulting approximate retained-data ERM. Finally, the algorithm outputs w̃U := ΠW (wU + v),

(4)

where v is the noise used to certify unlearning. When wU = ŵZ\U and v = 0, this is exactly retraining from scratch. The theorem below isolates the utility guarantee of this template. It applies to the warm-start algorithm of [AKGK25] once their optimization accuracy and noise calibration are substituted. Theorem 7 (Corrected utility bound for ERM warm-start unlearning). Assume that, for every z ∈ Z, the loss f (·, z) is L-Lipschitz, µ-strongly convex, and β-smooth over W. Let κ = β/µ. Suppose that for every unlearning set U ⊆ Z with |U | ≤ m, the unlearning-time optimizer returns wU ∈ W satisfying FbZ\U (wU ) − FbZ\U (ŵZ\U ) ≤ γ. Assume also that the noise v in (4) satisfies 2 2 E ∥v∥ ≤ σ .

(5)

Then

" E

Z∼P n

# sup

U ⊆Z: |U |≤m

∗ E[FP (w̃U ) − FP | Z, U ]

L2 ≲κ µ

1 m 2 + n n

β γ + βσ 2 . µ

In particular, if L2 γ≲ µ

1 m 2 + n n

and

L2 σ ≲ 2 µ

L2 µ

then the algorithm achieves the retraining-from-scratch rate " En

Z∼P

sup U ⊆Z: |U |≤m

∗ E[FP (w̃U ) − FP | Z, U ]

≲κ

1 m 2 + , n n

1 m 2 . + n n

Proof. Fix Z and U ⊆ Z with |U | ≤ m. Let w∗ ∈ argminw∈W FP (w). Since F is β-smooth and w∗ minimizes F over W, FP (w) − FP∗ ≤

β ∥w − w∗ ∥2 2

∀w ∈ W.

Using nonexpansiveness of projection and the inequality ∥a1 + · · · + a4 ∥2 ≤ 4

(6) P4

2 j=1 ∥aj ∥ , we obtain

β ∗ 2 E ∥w̃U − w ∥ | Z, U 2 ≲ β∥ŵZ − w∗ ∥2 + β∥ŵZ\U − ŵZ ∥2

∗ E[FP (w̃U ) − FP | Z, U ] ≤

+ β∥wU − ŵZ\U ∥2 + β E ∥v∥2 .

(7)

We now bound each term. First, as in the proof of Theorem 5, standard stability/generalization bounds for L-Lipschitz, µ-strongly convex ERM imply ∗ 2 E ∥ŵZ − w ∥ ≲ Z

L2 . µ2 n

Second, the unlearning stability bound for strongly convex ERM gives, uniformly over all U ⊆ Z with |U | ≤ m, Lm ∥ŵZ\U − ŵZ ∥ ≲ . µn Third, by µ-strong convexity of FbZ\U and the empirical accuracy condition (5), µ ∥wU − ŵZ\U ∥2 ≤ FbZ\U (wU ) − FbZ\U (ŵZ\U ) ≤ γ, 2 and hence ∥wU − ŵZ\U ∥2 ≤

2γ . µ

Finally, E ∥v∥2 ≤ σ 2 by assumption. Substituting these bounds into (7), taking the supremum over U , and then taking expectation over Z, gives " # L2 1 m 2 β ∗ sup + + γ + βσ 2 . E E[FP (w̃U ) − FP | Z, U ] ≲ β 2 µ n n µ Z U ⊆Z: |U |≤m Since β/µ = κ, the claimed bound follows.

Where the prior analysis breaks. The proof of [AKGK25, Proposition 1] attempts to convert an empirical-risk guarantee on the retained sample into a population-risk guarantee. The key error occurs in the line after the authors invoke smoothness of the loss. In our notation, smoothness can only give FP (w) − FP (θS∗ ) ≤ ⟨∇FP (θS∗ ), w − θS∗ ⟩ +

β ∥w − θS∗ ∥2 , 2

where θS∗ is the empirical minimizer used in their argument. The proof then effectively treats the linear term ⟨∇FP (θS∗ ), w − θS∗ ⟩ as zero. This is not justified: θS∗ minimizes the empirical risk, not the population risk, so in general ∇FP (θS∗ ) ̸= 0. Moreover, in constrained optimization, even the population minimizer need not have zero gradient. Thus the omitted first-order term can dominate the claimed bound, and the proposition does not establish the population-risk guarantee stated in [AKGK25]. The corrected analysis above avoids this step. Instead of expanding the population risk around an empirical minimizer and dropping the first-order term, we compare the warm-start output to the exact retained-data ERM, use strong convexity to convert empirical optimization error into parameter error, and then apply the same stability argument as retraining from scratch. This yields a retraining-level rate, plus the explicit contributions of optimization error and unlearning noise.

A Sharper Analysis of the Newton-step Algorithm of [SAKS21]

We revisit the Newton-step unlearning algorithm of [SAKS21]. Their algorithm was introduced as a way to improve over generic differentially private baselines for smooth strongly convex losses. In this section, we show that the same algorithm admits a sharper population-risk analysis than the one originally given. Throughout this section, assume that for every z ∈ Z, the loss f (·, z) is L-Lipschitz, µ-strongly convex, and β-smooth over W. We write κ = β/µ. We additionally assume, as in [SAKS21], that the Hessian is M -Lipschitz: ∥∇2 f (w, z) − ∇2 f (w′ , z)∥ ≤ M ∥w − w′ ∥ ∀w, w′ ∈ W, z ∈ Z. (8) For a dataset Z = (z1 , . . . , zn ), write n 1X FbZ (w) := f (w, zi ), n i=1

ŵZ ∈ argminw∈W FbZ (w).

The algorithm of [SAKS21] initializes at the full-data ERM ŵZ . After receiving a unlearning set U ⊆ Z, it takes one Newton step with respect to the retained empirical objective. Equivalently, the deterministic part of the update can be written as w̄U := ŵZ − ∇2 FbZ\U (ŵZ )−1 ∇FbZ\U (ŵZ ), where FbZ\U (w) :=

(9)

X 1 f (w, zi ). |Z \ U | zi ∈Z\U

The unlearning algorithm outputs a noisy version of this update, w̃U := ΠW (w̄U + v),

(10)

where v is calibrated Gaussian noise for (ε, δ)-unlearning, or calibrated multivariate Laplace noise for pure ε-unlearning. The projection is post-processing and can only improve the distance-to-w∗ bounds used below. 20

The original analysis of [SAKS21] gives, up to constants, p L2 m L3 M m2 d log(1/δ) + µ n µ3 εn2 for the Gaussian-noise (ε, δ)-unlearning version when m ≤ n/2. p When δ = 0, substituting Laplace noise for Gaussian in their algorithm yields the same bound but with d log(1/δ) replaced by d. We show that a more direct population-risk argument improves the generalization term from m/n to 1/n + (m/(n − m))2 , which is 1/n + (m/n)2 when m ≤ n/2, and squares the privacy contribution when converting parameter error to excess risk. Theorem 8 (Improved analysis of the Newton-step algorithm). Assume f (·, z) is L-Lipschitz, µ-strongly convex, β-smooth, and has M -Lipschitz Hessian for every z ∈ Z. Let w̃U be the Newton-step unlearning algorithm of [SAKS21] for unlearning sets of size at most m < n. For the Gaussian-noise version calibrated to satisfy (ε, δ)-unlearning, 2 ! 2 L2 1 m M L2 d m4 log(1/δ) ∗ sup + +β . E[FP (w̃U ) − FP ] ≲ κ µ n n−m µ3 ε2 n4 U ⊆Z: |U |≤m For the pure ε-unlearning version obtained by replacing Gaussian noise with multivariate Laplace noise, 2 ! 2 2 4 m M L2 d m L2 1 ∗ + +β . sup E[FP (w̃U ) − FP ] ≲ κ 3 µ n n−m µ ε2 n4 U ⊆Z: |U |≤m In particular, if m ≤ n/2, then the deterministic part of both bounds simplifies to L2 1 m 2 + κ . µ n n Proof. Fix any unlearning set U ⊆ Z with |U | ≤ m. The bounds below are uniform over such U , so taking the supremum gives the theorem. Let w∗ ∈ argminw∈W FP (w). Since F is β-smooth and w∗ minimizes F over W, FP (w) − FP∗ ≤

β ∥w − w∗ ∥2 2

∀w ∈ W.

(11)

Using nonexpansiveness of projection and ∥a + b∥2 ≤ 2∥a∥2 + 2∥b∥2 , we obtain β ∗ 2 E ∥w̃U − w ∥ 2 ≤ β E ∥w̄U − ŵZ ∥2 + β E ∥ŵZ − w∗ ∥2 + β E ∥v∥2 .

∗ E[FP (w̃U ) − FP ] ≤

(12)

We now bound the three terms in (12). First, by the definition of the Newton step (9), w̄U − ŵZ = −∇2 FbZ\U (ŵZ )−1 ∇FbZ\U (ŵZ ). The proof of [SAKS21, Lemma 9] gives, uniformly over all U ⊆ Z with |U | ≤ m, ∥w̄U − ŵZ ∥ ≲

Lm . µ(n − m)

(13)

L2 m2 . µ2 (n − m)2

(14)

Consequently, 2 E ∥w̄U − ŵZ ∥ ≲

Second, standard stability/generalization bounds for L-Lipschitz, µ-strongly convex ERM imply ∗ E[FP (ŵZ ) − FP ] ≲

By µ-strong convexity of F ,

L2 . µn

(15)

µ ∗ 2 ∗ E ∥ŵZ − w ∥ ≤ E[FP (ŵZ ) − FP ] . 2

Combining this with (15) gives ∗ 2 E ∥ŵZ − w ∥ ≲

L2 . µ2 n

(16)

Third, [SAKS21] show that the deterministic Newton-step map has unlearning sensitivity ∆≲

M L2 m2 . µ3 n2

(17)

Thus, for the Gaussian mechanism calibrated to (ε, δ)-unlearning, d ∆2 log(1/δ) ≲ E ∥v∥ ≲ ε2 2

M L2 µ3

d m4 log(1/δ) . ε2 n4

(18)

For the pure ε-unlearning version based on multivariate Laplace noise, 2 E ∥v∥ ≲

d2 ∆2 ≲ ε2

M L2 µ3

d2 m4 . ε2 n4

(19)

Plugging (14), (16), and either (18) or (19) into (12) gives L2 ∗ E[FP (w̃U ) − FP ] ≲ β 2 µ

1 + n

m n−m

2 !

+ β E ∥v∥2 .

Since βL2 /µ2 = κL2 /µ, the claimed bounds follow. If m ≤ n/2, then (n − m)−1 ≤ 2n−1 , giving the simplified deterministic term. Remark 9. The improvement comes from analyzing population risk through the squared distance to the fulldata ERM ŵZ . The original analysis effectively pays a first-order generalization term of order m/n. By instead using smoothness of F , the deterministic displacement of the Newton update contributes quadratically, giving (m/(n − m))2 , while the full-data ERM contributes the usual 1/n statistical term, up to the condition-number factor.

Record · ID 246435 · SHA-256 894988d7f254dc9f
Retrieved via Conceptio — every document is proof-bundled with source, license, and retrieval metadata.