Remember What You Want to Forget: Algorithms for Machine Unlearning

Venue: NeurIPS 2021 · arXiv: 2103.03279 Verification: dblp for venue; PDF fetched.

Read status: pp. 5–9 read from page images — §2.2 Unlearning (Defs. 2–3), §2.3 retraining baseline, §3.1 population vs empirical risk (Thm. 1), §3.2 separation from DP (Lemmas 1–2), §3.3 Theorem 2, §4 Assumption 1 and Algorithm 1 (Eqs. 6–8). §1, §5 and all appendices/proofs not read.

The paper Near-Optimal Pure Machine Unlearning for Smooth Strongly Convex Losses builds on and strengthens. Reading them together is the cleanest way into the certified-unlearning line for the review's theory section.

1. Setup — and the storage constraint that defines the paper

A learning algorithm A outputs A(S). An unlearning algorithm \bar A takes A(S) and a delete set U \subseteq S, and outputs \widetilde w. Crucially, besides U and A(S), \bar A may access additional data statistics T(S) — but not S directly.

"This set of statistics T(S) captures the additional storage required by the algorithm to support unlearning. Thus, one of our goals is to minimize |T(S)|, in particular aiming for memory requirements which are independent of the training data size n. This precludes strategies which involve storing and reusing the entire training set, or aggressive model checkpointing."

That single sentence excludes Machine Unlearning (stores everything, checkpoints per slice) and Amnesiac (logs per-batch updates) by construction — and it is exactly the constraint Near-Optimal Pure Machine Unlearning for Smooth Strongly Convex Losses later drops, granting full storage T(Z) = Z. The two papers therefore bound different problems, and the review must not present their rates as directly comparable.

2. Definition 2 — (\varepsilon,\delta)-unlearning

For all S of size n, delete requests U \subseteq S with |U| \le m, and W \subseteq \mathcal{W}:

and symmetrically. Explicitly "motivated by the definition of differential privacy."

Difference from Making AI Forget You: Data Deletion in Machine Learning, stated by the authors: Ginart et al. compare the unlearner's output to the learning algorithm on S\setminus U, which "require[s] the learning algorithm to be randomized, even in the situations when there would be no delete requests in the future. Thus, the output of the learning algorithm will suffer a degradation in its performance guarantees due to this added noise. On the other hand, our definition does not require the learning algorithm to be randomized… our definition is more general."

3. Definition 3 — deletion capacity

"the maximum number of samples U that can be unlearnt, while still ensuring an excess population risk of 0.01." A genuinely useful concept: it turns "can this method unlearn?" into "how much can it unlearn before utility breaks?"

4. The paper's central insight — population risk, not empirical risk

"Prior works consider unlearning from an optimization perspective, focusing on minimizing the empirical risk, and do not discuss the implications of unlearning on population risk/test loss. As we show in the next section, the two can be significantly different objectives even for some of the simplest learning problems."

Their mean-estimation example makes it concrete. With \hat w = \frac1n\sum_i z_i, on deletion of U one can rescale exactly:

This needs only O(d) storage and deletes exactly, with \varepsilon = \delta = 0. But with z_i \sim \text{Bernoulli}(1/2) and m adversarially chosen delete requests all equal to 1, the updated minimiser is smaller by m/n and has worse test loss.

Theorem 1. Let \delta \le 0.005, \varepsilon = 1. There exists a 4-Lipschitz, 1-strongly convex loss f and a distribution \mathcal{D} such that for any A and \bar A — even one with access to the undeleted samples S\setminus U — the deletion capacity satisfies m \le cn with c strictly less than 1.

"if we only care about minimizing the empirical loss, then we can delete up to n-1 sample points… However, the deletion capacity is inherently limited if we want to retain test loss guarantees."

This is a clean, citable result for the review: exact empirical deletion is easy and nearly unbounded; deletion that preserves generalisation is fundamentally capped.

5. Strict separation between unlearning and differential privacy

Lemma 1 (unlearning via DP). A DP algorithm unlearns "for free" — take \bar A(U, A(S), T(S)) = A(S), ignoring the delete request entirely — giving

Lemma 2 (Bassily et al. 2019). For any \bar A that does not use U, there is a 1-strongly convex, O(1)-Lipschitz loss and a distribution where one cannot unlearn even a single point if n \le c\sqrt d/\varepsilon. So the \sqrt d is unavoidable for the DP route.

Theorem 2. There exist A, \bar A such that for any convex, L-Lipschitz, M-Hessian-Lipschitz f:

with running time O(d^\omega), \omega \in [2, 2.38], and space |T(S)| = O(d^2).

The separation: "Theorem 2 and Lemma 2 together show that there exist problem settings where the deletion capacity in unlearning and DP is different by a multiplicative \Theta(d^{1/4}). In particular… we can delete O(n/d^{1/4}) samples while still retaining good performance on the unseen test loss, whereas DP only guarantees deletion of \Theta(n/d^{1/2}) samples."

And the title, explained: "our algorithm uses the samples in U during the unlearning phase. This paradox of storing and using information in order to delete it motivates the name of the paper: Remember what you want to forget."

6. The algorithm

Assumption 1. For any z, f(w,z) is \lambda-strongly convex, L-Lipschitz and M-Hessian Lipschitz with respect to w. (The Hessian-Lipschitz condition is precisely what Near-Optimal Pure Machine Unlearning for Smooth Strongly Convex Losses states it does not require.)

Learning: \hat w \leftarrow \arg\min \widehat F_n(w) = \frac1n\sum_{z\in S} f(w,z) (Eq. 6), returning \hat w and T(S) := \{\nabla^2 \widehat F(\hat w)\} — the Hessian at the output point.

Algorithm 1 (unlearning \bar A_{sc}):

Input: U = {z_j}_{j=1..m} ⊆ S, ŵ, T(S) = {∇²F̂(ŵ)}, loss f(w,z)
 1: γ ← 2Mm²L²/(λ³n²),   σ ← (γ/ε)·√(2 ln(1.25/δ))
 2: Ĥ ← (1/(n−m))·( n∇²F̂(ŵ) − Σ_{z∈U} ∇²f(ŵ,z) )                 (7)
 3: w̄ ← ŵ + (1/(n−m))·Ĥ⁻¹ Σ_{z∈U} ∇f(ŵ,z)                        (8)
 4: ν ~ N(0, σ²I_d)
 5: return w̃ := w̄ + ν

A Newton-style correction that removes the deleted points' contribution, plus Gaussian noise sized to buy the (\varepsilon,\delta) guarantee. The key technical claim: under Assumption 1, Eq. 8 approximates the empirical minimiser on S\setminus U to O(m^2/n^2), so only that much noise is needed.

7. What transfers to a ResNet — three concrete barriers

1. Assumption 1 is false, per example. \lambda-strong convexity, L-Lipschitzness and M-Hessian-Lipschitzness of f(\cdot, z) for every training point. None holds for a deep network.
2. |T(S)| = O(d^2) — the Hessian must be stored. For ResNet-18, d \approx 1.1\times10^7, so d^2 \approx 1.2\times10^{14} entries. At float32 that is roughly half a petabyte. The paper's own goal was storage independent of n; it is emphatically not independent of d.
3. Step 3 inverts \widehat H, a d\times d matrix, at O(d^\omega).

Barriers 2 and 3 are the same wall Eternal Sunshine of the Spotless Net: Selective Forgetting in Deep Networks hits and works around with a diagonal FIM approximation — which is exactly why Golatkar's implemented method drops the Newton step entirely. The theory prescribes an update the practice cannot afford, and the practical substitute is noise alone.

A framing for the review's "what transfers?" section. Sekhari, Golatkar and Regehr all arrive at a second-order correction plus calibrated noise. Sekhari derives it with a guarantee under strong convexity and O(d^2) storage; Golatkar keeps the noise and discards the correction because the curvature estimate is unaffordable; Regehr shows that in the regime where d is large the correction cannot help anyway. Read in that order, the three papers narrate the collapse of the second-order programme as d grows — which is a much more interesting story for the review than three separate summaries.

8. What the paper does not do (from sections read)

• No experiments in the sections read; §5 unread.
• Everything is stated for convex or strongly convex losses; no non-convex claim is made.
• Deletion capacity is defined against a fixed excess-risk threshold of 0.01, a convention rather than a derived quantity.
• Theorem 2's tightness is left open: "it is not clear if this dependence on d or n in the deletion capacity is tight or if it can be improved even further."

9. Links

• Strengthened by Near-Optimal Pure Machine Unlearning for Smooth Strongly Convex Losses, which drops the Hessian-Lipschitz assumption and grants full storage.
• Its Definition 2 is compared explicitly against Making AI Forget You: Data Deletion in Machine Learning's.
• Its storage constraint excludes Machine Unlearning and Amnesiac by construction.
• The second-order update it prescribes is the one Eternal Sunshine of the Spotless Net: Selective Forgetting in Deep Networks abandons in practice.
• Rejected as a "strawman" by Machine Unlearning §III.D under the certified-removal heading, alongside Certified Data Removal from Machine Learning Models.

@inproceedings{sekhari2021remember,
  title         = {Remember What You Want to Forget: Algorithms for Machine Unlearning},
  author        = {Ayush Sekhari and Jayadev Acharya and Gautam Kamath and Ananda Theertha Suresh},
  year          = {2021},
  booktitle     = {NeurIPS 2021},
  eprint        = {2103.03279},
  archiveprefix = {arXiv},
  url           = {https://arxiv.org/abs/2103.03279}
}