Research map / Learning theory and algorithms / Prediction and decision losses
When to Forget? Complexity Trade-offs in Machine Unlearning
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Derives minimax upper and lower bounds on the time (stochastic gradient accesses) needed for approximate, DP-style machine unlearning relative to retraining from scratch, for strongly convex losses, and validates the resulting three-regime phase diagram on synthetic and digits data.
Problem
How much cheaper can machine unlearning be than full retraining, in terms of first-order computation time, when the unlearning algorithm only has access to the retain set and must reach a target excess risk under an (epsilon, delta) unlearning guarantee?
Approach
Defines the unlearning complexity ratio T^U_e / T^S_e (minimax unlearning time over minimax retraining time) and proves matching-regime bounds: a trivial regime (noise alone suffices), an inefficient regime (ratio bounded below by a constant via a two-point argument), and an efficient regime where a noise-and-fine-tune algorithm achieves a ratio scaling as r_f^2 (1 + d kappa^2) e_0/e.
Key results
- The paper proves an efficient-regime upper bound T^U_e/T^S_e = O((r_f/(1-r_f))^2 (1+d kappa^2) e_0/e) for noise-and-fine-tune unlearning, and a lower bound Omega(1) in an inefficient regime where e is below a term proportional to r_f^2(1+kappa^2)e_0.
- Trivial regime: for e in [r_f/(1-r_f)(r_f/(1-r_f)+sqrt(d) kappa) e_0, e_0), zero gradient steps are needed for unlearning.
- Experiments with r_f=10^-2 show the empirical ratio well below 1 in much of the phase diagram, with a level line of slope about 0.5 at the top matching the predicted inefficient-regime behaviour.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use noise-and-fine-tune unlearning instead of retraining from scratch | Noise and Fine-Tune · Strongly convex Lipschitz objectives | unlearning complexity ratio: O((r_f/(1-r_f))^2 (1+d κ_dp^2) e_0/e) | Helped |
| Add Gaussian noise to the trained parameters without gradient steps | Noise and Fine-Tune · Trivial unlearning regime | unlearning complexity ratio: 0 | Helped |
| Increase the target excess risk above the efficient-regime threshold | Noise and Fine-Tune · Strongly convex Lipschitz objectives | unlearning complexity ratio: < γ | Helped |
| Reduce the forget ratio | Noise and Fine-Tune · Strongly convex Lipschitz objectives | unlearning complexity ratio: scales with r_f^2 | Helped |
| Require very low excess risk | Gradient-based unlearning · Strongly convex Lipschitz objectives | unlearning complexity ratio: Ω(1) | Hurt |
| Increase the privacy constraint strength κ_dp | Noise and Fine-Tune · Strongly convex Lipschitz objectives | unlearning complexity ratio: 1+dκ_dp^2 | Hurt |
| Compare Noise and Fine-Tune with retraining across excess-risk thresholds and privacy budgets | Noise and Fine-Tune · Synthetic data and Digit dataset | unlearning complexity ratio | Mixed |
Surprising findings
- The convex O(LR/sqrt(T)) rate, rather than the faster strongly convex rate, is what yields the r_f-proportional convergence for unlearning.
- Exact unlearning (kappa infinity) cannot asymptotically beat retraining under the stated assumptions.
Limitations
- Results are restricted to first-order, iterative algorithms and strongly convex, Lipschitz losses, which do not directly apply to neural networks.
- Assumes the forget set is inaccessible to the unlearning algorithm; methods that use the forget set are not covered.
- The sqrt(d) dependence in the upper bound is not matched by the lower bound.
Experimental setup
Datasets: Digits handwritten digits dataset
Benchmarks: synthetic worst-case loss Digits
Metrics: empirical unlearning complexity ratio
Baselines: retraining from scratch (SGD) noise and fine-tune unlearning
Builds on: (epsilon, delta)-reference unlearning Gaussian mechanism perturbed gradient descent Le Cam two-point method
Closest papers by meaning
- What makes unlearning hard and what to do about it (NeurIPS 2024 · similarity 0.93)
- The Utility and Complexity of In- and Out-of-Distribution Machine Unlearning (ICLR 2025 · similarity 0.92)
- LoTUS: Large-Scale Machine Unlearning with a Taste of Uncertainty (CVPR 2025 · similarity 0.92)
- Machine Unlearning under Overparameterization (NeurIPS 2025 · similarity 0.91)
- Unlearning or Obfuscating? Jogging the Memory of Unlearned LLMs via Benign Relearning (ICLR 2025 · similarity 0.91)
- Fast Machine Unlearning without Retraining through Selective Synaptic Dampening (AAAI 2024 · similarity 0.90)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.