Timeline: how the problem changed shape, 2015–2026
Not a list of dates. Four periods, each with a claim about what changed, and one observation about where the work was published that turns out to carry more argument than any individual paper.
The periods overlap deliberately. They are intellectual, not calendar, phases: the second-order programme and the definitional programme ran in parallel for two years, and the evaluation reckoning began while methods were still being proposed.
A caveat that governs everything below. This is a curated corpus of 27 papers, not a
census. Absences are evidence about our reading, not about the field, and are marked as
such. Where a claim depends on what a paper says, it is drawn from a section recorded as
read in papers.yaml; several papers' introductions were never read and no claim is made
about their framing (see VERIFICATION_REPORT.md correction 9).
Period 1 — 2015: founded broad, and founded in security
The claim: unlearning was born as a computational problem with three motivations, only one of which was privacy.
Cao et al. 2015 coins the term and gives the field its two original metrics — completeness ("how completely they can forget data") and timeliness ("how quickly they can do so") — explicitly in service of "restoring privacy, security, and usability." The three motivations are named and separate:
- Privacy: system inference attacks, their term in place of model inversion.
- Security: training data pollution. "The detector must forget the injected data to regain security."
- Usability: removing noise, or data a user no longer wants influencing results.
The mechanism is a summation form: convert learning into a small number of sums of efficiently computable transforms, so forgetting means updating sums rather than retraining. Generality is claimed via statistical query learning, and — uniquely in this corpus — the approach covers feature selection as well as model fitting. Every later paper assumes a fixed architecture and unlearns only weights.
The separation from differential privacy is already stated, ten years before it was formalised: DP "preserves the privacy of each individual item in a data set equally and invariably", whereas "forgetting systems aim to restore privacy on select data."
Then a four-year gap in this corpus. Nothing between 2015 and 2019. That is a fact about what we selected, and we cannot responsibly claim the field was quiet.
Period 2 — 2019–2021: definition, and the certified line
The claim: the goal was redefined from outputs to distributions over models, the problem was named as computational, and success narrowed to proximity to a retrain oracle.
Ginart et al. 2019 is the pivot. Definition 3.1 requires the deletion operation's output
and A(D_{-i}) to be equal in distribution — a real advance on output equality, and
still exact, not approximate (see taxonomy.md §1.2). Two framings from it set the
agenda:
- "Every learning algorithm A supports a trivial data deletion operation corresponding to simply retraining … Because of this, the challenge of data deletion is computational."
- Remark 3.1's \Omega(n/m) amortised lower bound for m deletion requests online — a complexity result for unlearning in 2019, six years before Van Waerebeke et al. 2025 bounds the ratio of unlearning to retraining time.
Its §3.1 design principles — linearity, laziness, modularity, quantization — map most of
what followed, including SISA two years early (see taxonomy.md §7).
The certified line then arrives in quick succession:
| Year | Paper | What it added |
|---|---|---|
| 2020 | Guo et al. 2020 | (\varepsilon,\delta)-certified removal; one-step Newton update plus loss perturbation; DP is sufficient but not necessary |
| 2021 | Sekhari et al. 2021 | deletion capacity; population risk rather than empirical; storage T(S) independent of n; strict \Theta(d^{1/4}) separation from DP |
| 2021 | Neel et al. 2021 | an ongoing sequence of additions and deletions; the publishing function; strong vs weak unlearning |
| 2021 | Izzo et al. 2021 | the Projective Residual Update — provably the best any gradient-based update using only the deleted points can do |
Bourtoule et al. 2021 runs alongside it on the opposite strategy: rather than approximating retraining, make retraining cheap. Sharding, slicing and checkpointing give exactness by construction, at the cost of moving the intervention to training time.
Where the narrowing happened. Cao et al. 2015 measured completeness and timeliness against three motivations. Ginart et al. 2019 Def. 3.1, Guo et al. 2020 §2 and Sekhari et al. 2021 Def. 2 each define success as proximity to a reference model trained on \mathcal{D}_r, with no counterpart to security or usability. That is the narrowing — visible in the definitions, which we read, and asserted about nothing else.
Period 3 — 2020–2023: the deep-network turn, and the second-order programme's fate
The claim: the second-order programme was derived for deep networks, found not to survive contact with them, and quietly replaced by heuristics — often within the same paper.
The clearest instance is Golatkar et al. 2020a. It defines forgetting via a Forgetting Lagrangian, derives an optimal scrubbing function under a quadratic-loss, gradient-flow assumption, notes it reduces to a Newton update at convergence, approximates the Hessian by the Fisher Information Matrix — and then, in the authors' own construction, what is actually implemented is far simpler than the theory. The companion Golatkar et al. 2020b linearises in the NTK regime and derives a closed-form one-shot forgetting vector, and its §4.1 shows the Newton update degenerates when d > n, which is the regime every network in this corpus occupies.
The collapse points are independent, which is why §5 of the review treats them separately:
- Convexity. Guo et al. 2020 §3.1 assumes a convex loss with a unique minimiser.
- Dimension. The Newton step costs O(d^3) at removal time; for ResNet-18, d \approx 1.1 \times 10^7.
- Scope. Guo et al. 2020 §3.3 is explicit that the guarantee attaches to a linear head over a frozen public or DP-trained feature extractor. It never certifies the representation. That is not a loose bound for deep networks; it is a different object.
What replaces it is avowedly heuristic and mostly distillation- or saliency-shaped: Graves et al. 2021 relabelling, Chundawat et al. 2023's two teachers, Kurmanji et al. 2023's selective disobedience, Jia et al. 2023's prune-then-unlearn, Fan et al. 2024's weight saliency, Foster et al. 2024's Fisher-guided dampening — which is the second-order machinery repurposed as a selection rule rather than as a certified update.
Kurmanji et al. 2023 is the period's turning point in framing as well as method. It rejects weight-space proximity to the retrain oracle as the target, on the grounds that the supporting assumptions — SGD stability, "small enough" forget sets — are ones deep networks violate, and it replaces the single objective with three applications: RB (removing biases, wanting maximal forget error), RC (resolving confusion), and UP (user privacy, wanting forget error only as high as the oracle's, since more is itself a leak). SCRUB+R's rewinding exists precisely because RB and UP pull in opposite directions.
The arc worth stating
SCRUB's three applications are much closer to Cao et al. 2015's original breadth — privacy, security, usability — than to the intervening oracle-matching definitions. RC is recovery from label pollution, which is Cao & Yang's security motivation; RB is their usability motivation. SCRUB's claim to be first to argue that forgetting is application-dependent is fair with respect to the evaluation literature, and the breadth it recovers was present in the founding paper and lost in between.
This is only visible because we read the 2015 paper, which most reproductions of SCRUB would have no reason to open.
Period 4 — 2022–2026: the evaluation reckoning, and a theory line that returns
The claim: the measurement apparatus was attacked on three orthogonal axes, in several cases by the authors of the methods being measured — and meanwhile the theory line came back with results that no longer assume what the earlier one did.
Three independent lines of attack, which the review presents together because no single paper does:
| Axis of attack | Papers | The objection |
|---|---|---|
| The oracle is the wrong target | Goel et al. 2022, Thudi et al. 2022a, Xu et al. 2025 | matching a particular retrained model is neither necessary nor sufficient (Thm. 1); the metric is noisy against any one draw; the anchor is unknown and so the criterion is inauditable |
| The attacks are too weak | Carlini et al. 2022, Hayes et al. 2024, Triantafillou et al. 2024 | privacy is worst-case, so report TPR at low FPR; population U-MIAs are far weaker than per-example ones; use the strongest attacker per example |
| The artifact cannot be audited at all | Thudi et al. 2022b | forging means unlearning "is not well-defined over the logs (and thus the models)" for minibatch SGD; verify the process |
And one that runs the other way: Chen et al. 2021 shows unlearning creates a leak, because the discrepancy between the original and unlearned models is itself attackable.
The authorship overlap is part of the story. Three of SCRUB's four authors appear on
Triantafillou et al. 2024, and Hayes et al. 2024 is from the same group. The
strongest critiques of the evaluation apparatus come from the people who built the methods
being evaluated — which is a sign of a field correcting itself, and also a reason to be
careful about treating those critiques as independent (recorded in
VERIFICATION_REPORT.md, "Authorship overlaps that affect independence").
Meanwhile the theory line returns, and it is not the same theory line:
- Van Waerebeke et al. 2025 bounds the minimax computation time of unlearning against retraining for strongly convex objectives, giving a three-regime phase diagram. Ginart's 2019 instinct, made precise.
- Regehr et al. 2026 gives matching upper and lower bounds on excess population risk for pure (\delta = 0) \varepsilon-unlearning — and drops Sekhari et al. 2021's storage constraint, granting full storage, which is why the two papers' rates are not comparable.
- Xu et al. 2025 does something different again: it assumes no convexity, states its criterion in output space, and targets deep learning explicitly. It is the one theory paper in the corpus whose barrier is estimability rather than transfer.
The observation about venues
Sorting the corpus by venue rather than by year produces a pattern that no individual paper mentions.
| Group | Count | Where it was published |
|---|---|---|
Deep-network method papers (vision_heuristic) |
10 | CVPR, ECCV, AAAI ×3, NeurIPS ×2, ICLR, TNNLS, and one preprint. None at a security venue. |
| Evaluation critiques, peer-reviewed | 4 | CCS, IEEE S&P, USENIX Security, EuroS&P. All four at security venues. |
| Evaluation critiques, preprints | 2 | arXiv only |
| The certified/theory line | 7 | ICML, NeurIPS, ALT, AISTATS, ICML, and 3 preprints |
| The founding papers, and SISA | 3 | IEEE S&P ×2 and NeurIPS |
So: the field was founded at a security conference, and SISA — still the canonical exact method — was published there too. The deep-network methods then migrated wholesale to machine-learning conferences, and not one of the ten went to a security venue. The sustained criticism of how those methods are evaluated stayed behind: all four peer-reviewed critiques are at CCS, S&P, USENIX Security and EuroS&P.
Three honest qualifications.
- This corpus was assembled from SCRUB's citation graph, the project's reading list and a deliberate search for evaluation critiques — not with venue in mind — but it is a selection, and the pattern is a property of that selection.
- The split is by
papers.yamlcategory, and one paper strains it: Goel et al. 2022 is classified as a method paper because it contributes CF-k and EU-k, but its Theorem 1 and Interclass Confusion test are squarely evaluation critique. Counted the other way the pattern is unchanged, since it is a preprint either way. - Two of the six critiques have no peer-reviewed venue at all, and they are the two most recent and most directly relevant: Hayes et al. 2024 and Triantafillou et al. 2024. That is the relevant datum for us, not a footnote — the panel's peer-review constraint bites hardest exactly where the field is most self-critical, which is why SCRUB rather than a critique is the reproduction target.
What this timeline does not cover
- Anything outside image classification. No language-model, federated, graph or generative unlearning paper is in the corpus, by the project's scope constraint.
- 2016–2018, where the corpus is empty.
- Results. No experimental number from any period appears above. The only reported numbers this project holds are SCRUB Table 7 and Jia Table 2.
- Anything about how papers motivate themselves rhetorically, since most introductions were not read.