When to Forget? Complexity Trade-offs in Machine Unlearning

Venue: ICML 2025, PMLR 267:60816–60832 · arXiv: 2502.17323 Verification: verified_fetched — PMLR abstract page, arXiv abs, and the PMLR PDF (obtained via the raw.githubusercontent.com/mlresearch/v267 asset link; PMLR's conventional /vNNN/author/author.pdf path 404s for this volume).

Read status: §3.2–§5.3 (pp. 4–8) read from page images: full formal setup, Definitions 1–2, Lemma 3.1, Assumption 2, Lemmas 4.1–4.2, Theorems 1–3, Corollaries 1–2, Discussion, and the experimental setting. Appendix proofs not read.

1. What kind of paper this is

Not a method paper. It asks when unlearning is worth doing at all, by bounding the minimax computation time of unlearning against retraining from scratch, for strongly convex objectives. The headline object is the unlearning complexity ratio T^U_e / T^S_e, and the result is a phase diagram with three regimes.

This is the paper that most directly supplies the thesis's "what transfers?" argument, because its efficiency conclusion depends on a ratio d/n that inverts in the overparameterised regime deep networks live in. See §6 below.

2. Formal setup

Update rule. A \in \mathbf{A} is a measurable function (Eq. 3)

with \boldsymbol\theta_t \in \mathbb{R}^d, \nabla_t a stochastic gradient, m_t a memory state, \omega a random seed. Deliberately general — the authors note it "contains most standard optimization algorithms used in machine learning", including momentum and adaptive step sizes via the memory state.

Learning algorithm (Eq. 4), initialised at \boldsymbol\theta_0 = 0:

Unlearning algorithm (Eq. 5), initialised at \boldsymbol\theta^\star, the unique minimiser of the full objective \mathcal{L}:

Critical modelling choice. Unlearning algorithms may only sample from the retain set. The paper states this explicitly and situates it in the DP-based MU literature (Neel et al. 2021; Fraboni et al. 2024; Huang & Canonne 2023; Allouah et al. 2024), while conceding that "more efficient unlearning methods might exist in scenarios in which the forget dataset is also available during unlearning."

SCRUB uses the forget set directly — its max-steps run over \mathcal{D}_f. So SCRUB sits outside this paper's algorithm class. Its bounds neither cover nor constrain SCRUB.

3. Two unlearning definitions

Definition 1 ((ε,δ)-Reference Unlearning), which this paper says was "first introduced by Ginart et al. (2019)".

⚠️ That attribution needs care, and the review should not repeat it unqualified. Ginart et al.'s main-body Definition 3.1 is exact — equality in distribution, not an (\varepsilon,\delta) bound. Their paper states: "Here we focus on exact data deletion … The above definition can naturally be relaxed to approximate data deletion … Refer to Appendix A … We defer a full discussion of this to future work."

So the (\varepsilon,\delta) form exists in Ginart only as a deferred appendix remark. Van Waerebeke et al. may be citing that appendix, but as written the attribution reads as though the (\varepsilon,\delta) definition is Ginart's main contribution, which it is not. See ginart2019deletion.md §4 for the full audit of how five different papers characterise Ginart. \mathcal{U} qualifies if there exists a reference \mathcal{A} \in \mathbb{A} such that for any (\mathcal{D}_r, \mathcal{D}_f) and any S \subset \mathbb{R}^d:

The paper criticises this (citing Georgiev et al. 2024) as "not satisfying in the sense that it makes the unlearning guarantee rely on the algorithm \mathcal{A} which is generally simple retraining on the retain set."

Definition 2 ((ε,δ)-Unlearning) — their stronger, reference-free definition. For any triplet (\mathcal{D}_r, \mathcal{D}_f, \mathcal{D}'_f), loss \ell, and S \subset \mathbb{R}^d:

(\epsilon,\delta) is the unlearning budget; lower is harder. The paper notes this is "very close to the notion of Differential Privacy. The only difference is that this one only ensures privacy of the forget set rather than the entire training set."

Lemma 3.1 (Equivalence). (\epsilon,\delta)-Unlearning ⟹ (\epsilon,\delta)-Reference Unlearning; and (\epsilon,\delta)-Reference Unlearning ⟹ (2\epsilon, (1+e^\epsilon)\delta)-Unlearning.

4. Minimax computation times

Time for a learning algorithm to reach excess risk e (Eq. 6), and for an unlearning algorithm starting from \boldsymbol\theta^\star (Eq. 7):

Minimax over the strongly convex class \mathcal{F}_{sc} (Eqs. 8–9):

Key quantities.

Lemma 4.1. If e \ge e_0 then T^S_e = T^U_e = 0.

Assumption 2 (Flexible distributions). For any p\in[0,1] there is A \subset \mathbb{R}^s with \mathbb{P}(\xi_r \in A) = p; and there exists \mathcal{D}'_f such that \mathrm{supp}(\mathcal{D}_r), \mathrm{supp}(\mathcal{D}_f), \mathrm{supp}(\mathcal{D}'_f) are pairwise disjoint. Described as "relatively weak, and usually verified for continuous distributions, as long as \mathrm{supp}(\mathcal{D}_r) and \mathrm{supp}(\mathcal{D}_f) do not cover the whole space."

Lemma 4.2. Under Assumption 2, if e < e_0: T^S_e = \Theta(e_0/e) (Eq. 10).

5. The three regimes

Theorem 1 (Trivial regime). If

Unlearning needs zero gradient access — adding Gaussian noise suffices. Intuition given: \|\boldsymbol\theta^\star - \boldsymbol\theta^\star_r\| is roughly proportional to r_f, so as r_f \to 0 the unlearner already starts at the optimum.

Theorem 2 (Inefficient regime). Let \delta \in [10^{-8}, \epsilon]. Under Assumption 2 there is a universal c>0 such that if

Unlearning cannot asymptotically outperform retraining. Proof by Le Cam's two-point method: construct \mathcal{L}^g and \mathcal{L}^{-g} whose optima over \mathcal{D} carry no information about \mathcal{D}_r, whose optima over \mathcal{D}_r are far apart, and on which any algorithm behaves nearly identically.

Corollary 1. For fixed r_f \in (0,1) and \kappa_{\epsilon,\delta} \ge 0: \liminf_{e\to 0} T^U_e/T^S_e > 0 (Eq. 13). The advantage of starting from a pretrained \boldsymbol\theta^\star vanishes as the target excess risk tightens.

Impossibility result for exact unlearning — with a caveat that matters for SISA. Exact unlearning means \kappa_{\epsilon,\delta} = +\infty, so Theorem 2 says no asymptotic gain is possible. But the paper immediately adds: "most existing exact MU algorithms rely on modifications of the training set and are thus not included in our framework." SISA (Bourtoule et al.) shards the training set, so it is explicitly outside this impossibility result. This caveat must not be dropped when the review states the result.

Theorem 3 (Noise and Fine-Tune Efficiency). For any e < e_0:

Achieved by "Noise and Fine-Tune" (Algorithm 2), an adapted perturbed gradient descent after Neel et al. (2021): sample g \sim \mathcal{N}(0, (\kappa_{\epsilon,\delta} r_f L/\mu)^2 I_d), initialise \boldsymbol\theta_0 = \boldsymbol\theta^\star + g, run T SGD steps with step size \tfrac{2}{\mu(t+1)}, return the weighted average \hat{\boldsymbol\theta} = \tfrac{2m_T}{(T+1)(T+2)}.

The authors flag as "quite surprising" that the r_f-proportional rate comes from convex convergence rates \mathcal{O}(LR/\sqrt T) rather than the faster strongly convex \mathcal{O}(L^2/\mu T).

Corollary 2 (Efficient regime). For any \gamma \in (0,1), if e \ge \frac{c}{\gamma}\left(\frac{r_f}{1-r_f}\right)^2(1+d\kappa^2_{\epsilon,\delta})e_0 then T^U_e/T^S_e < \gamma.

An acknowledged gap. "Since we rely on noising the model parameters to ensure unlearning, our bound scales with \sqrt d … While natural, this dependence is not matched by our lower bound in Theorem 2. We leave the exploration of this discrepancy to future work." The upper and lower bounds therefore do not match in the dimension dependence.

6. What transfers to a ResNet on CIFAR — the crux

The paper's own §4.5 Discussion does the practical arithmetic, and it is the most important passage in the paper for this thesis:

"if r_f \propto 1/n, then the unlearning complexity ratio is of the order d/n and unlearning can be very efficient in under-parameterized settings."

So the efficiency claim is explicitly conditioned on d/n being small. Our settings run the other way:

In both of our settings d/n \gg 1, which is the inefficient end of their own arithmetic. Taken at face value the theory predicts that noise-and-fine-tune unlearning should offer little or no computational advantage over retraining for our models.

Four reasons that inference does not directly apply, all of which the review must state rather than gloss:

1. Strong convexity fails. \mathcal{F}_{sc} is the strongly convex class; \boldsymbol\theta^\star is assumed a unique minimiser. A ResNet's loss surface has neither property. e_0 = L^2/(8\mu) is undefined without \mu > 0.
2. Forget-set access. Their unlearners may only sample \mathcal{D}_r. SCRUB, NegGrad+, Bad-T and SalUn all use \mathcal{D}_f directly. The bounds do not constrain that class.
3. Different currency. They bound computation time to a target excess risk, not forget quality. SCRUB's metrics — forget error, MIA advantage — have no counterpart here. The two literatures are not measuring the same thing.
4. Exact-unlearning caveat. The Theorem 2 impossibility result excludes training-set-modifying methods, hence excludes SISA.

Where a contribution might sit. The honest statement of the gap is that this paper gives a rigorous answer to "is unlearning cheaper than retraining?" in a regime (strongly convex, retain-only access, under-parameterised) that has essentially no overlap with the regime the empirical vision literature operates in (non-convex, forget-set access, massively over-parameterised). Nobody has shown which side of the phase diagram a ResNet actually sits on, because the diagram's axes are not measurable for it. Constructing an empirically estimable analogue of the complexity ratio for a deep network — even a crude one — would be a genuine bridge.

7. Experiments

Linear regression in \mathbb{R}^d (even d). Synthetic worst-case objective:

with g:\mathbb{R}^s\mapsto\{-1,1\} Rademacher, \mathbb{E}[g] = \tfrac{1}{2\sqrt T}, L=25, \mu=1. Real data: the Digit dataset of handwritten digits (subset of the larger set proposed in Alpaydin & Alimoglu 1996), cross-entropy with L^2 regularisation. r_f = 10^{-2} throughout. Learning by SGD (Garrigos & Gower 2023); unlearning by Algorithm 2. Figure 2 shows the empirical phase diagram recovering IR/ER/TR on both.

No deep networks, no image classification beyond digits, no comparison to any empirical unlearning method. This is not a criticism — it is a theory paper — but it bounds what may be claimed from it.

8. What the paper does not test

• Any non-convex objective.
• Any unlearning method with forget-set access.
• Any forget-quality or privacy metric; only computation time to a risk threshold.
• Whether the \sqrt d upper-bound dependence is tight (explicitly left open).
• Only r_f = 10^{-2} empirically, though the theory is stated for general r_f.

9. Links

• Builds the upper bound on perturbed GD from Descent-to-Delete: Gradient-Based Methods for Machine Unlearning.
• Definition 1 attributed to Making AI Forget You: Data Deletion in Machine Learning.
• Exact-unlearning caveat is what exempts Machine Unlearning.
• The contrast case for Towards Unbounded Machine Unlearning, which is non-convex and uses the forget set.
• Companion theory papers: Near-Optimal Pure Machine Unlearning for Smooth Strongly Convex Losses, Machine Unlearning via Information Theoretic Regularization.

@inproceedings{vanwaerebeke2025whentoforget,
  title         = {When to Forget? Complexity Trade-offs in Machine Unlearning},
  author        = {Martin Van Waerebeke and Marco Lorenzi and Giovanni Neglia and Kevin Scaman},
  year          = {2025},
  booktitle     = {Proceedings of the 42nd International Conference on Machine Learning (ICML 2025)},
  series        = {PMLR},
  volume        = {267},
  pages         = {60816--60832},
  eprint        = {2502.17323},
  archiveprefix = {arXiv},
  url           = {https://arxiv.org/abs/2502.17323}
}