Near-Optimal Pure Machine Unlearning for Smooth Strongly Convex Losses

Venue: arXiv preprint, submitted 1 June 2026. No journal-ref. arXiv: 2606.01527 Verification: verified_fetched — arXiv abs page and the PDF.

⚠️ This paper postdates the assistant's training cutoff (May 2026). Every statement in this file is transcribed from the fetched PDF. Nothing is written from recollection, and nothing here should be assumed against background knowledge of the area.

Read status: pp. 3–8 read from page images — Table 1, §1.1 Preliminaries, Assumption 1, Definitions 1–2, Algorithm 1, Theorem 1, Propositions 1–2, Lemma 1, Theorem 2, Corollary 1, and the lower-bound intuition. §4 Conclusion and §5 (matching bounds for the weaker utility definition) not read.

1. What the paper does

Establishes matching upper and lower bounds on the excess population risk of pure (\delta = 0) \varepsilon-unlearning for smooth strongly convex stochastic convex optimisation. The rates agree up to the condition number, and are tight for mean estimation.

Its practical significance for this thesis is a single exponential factor, e^{-2\varepsilon/(d+2)}, whose behaviour in the deep-network regime is decisive. See §6.

2. Assumption 1 (Smooth strongly convex SCO)

Transcribed verbatim in substance:

1. The parameter domain \mathcal{W} \subseteq \mathbb{R}^d is closed, convex, and has finite Euclidean diameter \sup_{w,w'\in\mathcal{W}}\|w-w'\|.
2. For every z \in \mathcal{Z}, the loss f(\cdot,z): \mathcal{W}\to\mathbb{R} is differentiable and L-Lipschitz on \mathcal{W}.
3. For every z \in \mathcal{Z}, f(\cdot,z) is \mu-strongly convex on \mathcal{W}.
4. For every z \in \mathcal{Z}, f(\cdot,z) is \beta-smooth on \mathcal{W}.
5. The population minimiser w^*_P := \arg\min_{w\in\mathcal{W}} F_P(w) satisfies \nabla F_P(w^*_P) = 0.

\kappa := \beta/\mu is the condition number. Dataset size n, unlearning capacity 1 \le m < n, with n - m = \Omega(n); non-trivial guarantees only when m \le cn for some c<1.

Note the strength: conditions 2–4 hold per-example, not merely for the population objective. Also worth recording, they weaken one prior assumption — "Unlike [SAKS21], we do not require that Hessian of the loss is Lipschitz."

3. Definitions

Definition 1 (Approximate \varepsilon-unlearning). \tilde{\mathcal{A}} satisfies \varepsilon-unlearning for up to m deletions if for every Z \in \mathcal{Z}^n and every U \subseteq Z with |U| \le m:

where X \approx_{\varepsilon,\delta} Y means for every measurable E, \Pr(X\in E) \le e^\varepsilon\Pr(Y\in E)+\delta and symmetrically. \delta = 0 is what makes it "pure".

Definition 2 (Expected excess unlearning risk \alpha). For every P, every n-m \le N \le n, and every adversarial request U(Z)\subseteq Z with |Z\setminus U(Z)| \ge n-m:

Deliberately stronger than prior work. Sekhari et al. [SAKS21] require good performance only on \tilde{\mathcal{A}}(U,Z), the model released after a request. This paper additionally requires good performance on \tilde{\mathcal{A}}(\emptyset, S), S \sim P^{n-m} — the model trained on data that never contained the deleted points. Their stated reason: the optimal unlearner under the weaker definition "behaves in a way contrary to the spirit of machine unlearning."

Storage model. The unlearner is granted full storage, T(Z) = Z: it has access to the whole dataset Z, the unlearning set U, and the learned model \mathcal{A}(Z). This is a materially different access model from When to Forget? Complexity Trade-offs in Machine Unlearning, whose unlearners may only sample the retain set.

4. Table 1 — the rate landscape

Excess-risk rates for \varepsilon-unlearning up to m points, logarithmic/Lipschitz/ strong-convexity/smoothness/condition-number factors suppressed:

5. Main results

Algorithm 1 — Core-swap \varepsilon-unlearning for ERM (verbatim):

Require: Dataset T; deletion set U ⊆ T; parameters L, μ, n, m, d, ε
 1: Set S ← T \ U; compute ŵ_S ← argmin_{w∈W} F̂_S(w) and ŵ_T ← argmin_{w∈W} F̂_T(w)
 2: Set r ← 2Lm/(μ(n−m)),  τ ← r·min{1, 2e^{−ε/(d+2)}},
        η ← 1 / ( (e^ε − 1)(τ/(τ+r))^d + 1 )
 3: Sample w̃ ~ { Unif((τ+r)·B_d + ŵ_S)   w.p. η
                { Unif(τ·B_d + ŵ_T)       w.p. 1−η
 4: return argmin_{w∈W} ‖w − w̃‖

The mechanism interpolates between the two extremes: ignore the request and return the full-data ERM \hat w_Z (accurate, no guarantee), or retrain and return \hat w_{Z\setminus U} (guaranteed, less accurate). With high probability it samples a small ball around \hat w_Z; with probability \eta it samples a wider ball around \hat w_S "just large enough to capture any full-data ERM solutions \hat w_Z that may reduce to S = Z\setminus U by a legal unlearning request."

Theorem 1 (Main Upper Bound). Under Assumption 1, Algorithm 1 satisfies \varepsilon-unlearning, runs in time O(d) after two ERM-oracle calls and one convex projection, and achieves

For mean estimation over the unit ball (\mathcal{W}=\mathcal{Z}=\mathbb{B}_d, f(w,z)=\tfrac12\|w-z\|^2) the \kappa L^2/\mu factor drops.

Supporting pieces: Proposition 1 (\varepsilon-unlearning, via the strongly convex ERM stability bound \|\hat w_Z - \hat w_{Z\setminus U}\| \le \frac{2L|U|}{\mu|Z\setminus U|} \le r); Proposition 2 (\mathbb{E}\|\tilde{\mathcal{A}}(U,Z)-\hat w_Z\|^2 = O(\frac{L^2}{\mu^2}(\frac mn)^2 e^{-2\varepsilon/(d+2)})); Lemma 1 (\mathbb{E}\|\hat w_Z - w^*_P\|^2 = O(L^2/(\mu^2 n))).

Theorem 2 (Lower bound, mean estimation). Any \varepsilon-unlearning algorithm with MSE guarantee \alpha must satisfy \alpha = \Omega\!\left(\frac1n + \left(\frac mn\right)^2 e^{-2\varepsilon/(d+2)}\right).

Corollary 1 (SCO lower bound). \alpha \ge \Omega\!\left(\frac{L^2}{\mu}\left(\frac1n + \left(\frac mn\right)^2 e^{-2\varepsilon/(d+2)}\right)\right).

Lower-bound technique. Packing, but explicitly not standard DP packing: "In unlearning, the algorithm may see the unlearning set and arbitrary side information, so DP-style neighboring-dataset indistinguishability alone is not enough." They construct separated mean-estimation instances whose signal samples can all be deleted, so that after deletion every instance collapses to a common retained dataset, forcing all output distributions close to one reference — yielding the e^{-\Theta(\varepsilon/d)} penalty.

6. What transfers to a ResNet on CIFAR — the decisive factor

Everything turns on e^{-2\varepsilon/(d+2)}. The paper's own framing (p. 4):

"our algorithm gives an exponential improvement over the retrain-from-scratch rate of \Theta((m/n)^2) in the regime \varepsilon = \Omega(d)."

Read the factor in the two regimes:

Now put our numbers in. d is the parameter count:

Meaningful privacy parameters in the DP literature are single digits. An \varepsilon of 10^7 is not a privacy guarantee in any useful sense — e^{\varepsilon} is astronomically large, so the indistinguishability constraint is vacuous. In the overparameterised regime the theorem therefore says retraining from scratch is optimal, and it says so with a matching lower bound, not merely a loose upper bound.

This is the single sharpest statement of the theory/practice gap available across the three theory papers, and the review should lead the section with it.

Why this does not license despair about SCRUB. Four limits on the inference:

1. Assumption 1 fails comprehensively. Per-example \mu-strong convexity and \beta-smoothness of a ResNet loss are false, and condition 5 presumes a stationary population minimiser. Nothing in the theorem is claimed about non-convex losses.
2. "Pure" \delta = 0 is the strictest setting. The e^{-\Theta(\varepsilon/d)} penalty is specific to it; the paper's own Table 1 shows the (\varepsilon,\delta) Newton-step route has different structure.
3. Different currency again. The bound is on excess population risk under an indistinguishability constraint. SCRUB offers no \varepsilon whatsoever, and is measured by forget error and MIA advantage. There is no exchange rate between them.
4. The dimension d is the ambient parameter count. Whether the effective dimension of a trained network — the dimension that actually matters for indistinguishability — is anywhere near 1.1\times10^7 is exactly the sort of question nobody has answered. If the effective d were orders of magnitude smaller, the regime boundary moves.

Where a contribution might sit. Point 4 is the interesting one. The theory says the unlearning penalty is e^{-\Theta(\varepsilon/d)}; if one could argue that the relevant d for a trained network is an effective rather than ambient dimension — via the loss Hessian spectrum, say, which is famously low-rank for trained nets — the boundary between "retraining is optimal" and "unlearning helps" would move by orders of magnitude. That connects directly to the Fisher-information machinery Stage 7 has to build anyway for Fisher Forgetting and SSD.

7. What the paper does not test

It is a pure-theory paper: no experiments at all in the sections read. No deep networks, no datasets, no empirical validation of the rates. §4 Conclusion and §5 (the weaker utility definition) were not read and may qualify this.

8. Links

• Strengthens the utility definition of Remember What You Want to Forget: Algorithms for Machine Unlearning (their [SAKS21]) and drops its Lipschitz-Hessian requirement.
• Complementary access model to When to Forget? Complexity Trade-offs in Machine Unlearning: full storage and forget-set access here, retain-only there.
• The non-convex, no-\varepsilon contrast case is Towards Unbounded Machine Unlearning.
• Third theory-track paper: Machine Unlearning via Information Theoretic Regularization.

@misc{regehr2026nearoptimal,
  title         = {{Near-Optimal} Pure Machine Unlearning for Smooth Strongly Convex Losses},
  author        = {Matthew Regehr and Gautam Kamath and Andrew Lowy},
  year          = {2026},
  howpublished  = {arXiv preprint (no journal-ref as of verification)},
  eprint        = {2606.01527},
  archiveprefix = {arXiv},
  url           = {https://arxiv.org/abs/2606.01527},
  note          = {Not peer-reviewed}
}