Descent-to-Delete: Gradient-Based Methods for Machine Unlearning

Venue: Algorithmic Learning Theory (ALT) 2021 · arXiv: 2007.02923 Verification: dblp for venue; PDF fetched.

Read status: pp. 6–8 read from page images — §1.3 summary of results, §2 Model and Preliminaries (Defs. 2.1–2.4, Remark 2.5, Assumption 2.6), §2.1 ERM framework (Defs. 2.7–2.8), §2.2 loss properties (Defs. 2.9–2.11), §2.3 Lemma 2.12, §2.4 Theorem 2.13. §1–1.2, §3–§4 algorithms and all proofs not read.

Two structural ideas here appear nowhere else in this project's reading: sequences of updates (rather than one deletion) and the secret-state / published-model distinction. Both matter for the review's framing of what the field measures.

1. Update sequences, not a single deletion

Definition 2.1 (Update). An update u = (z, \bullet) with \bullet \in \mathcal{T} = \{\texttt{add}, \texttt{delete}\}, and an update sequence \mathcal{U} = (u_1, u_2, \dots):

Almost every other paper in our set models one deletion request against one trained model. This one models an ongoing stream of additions and deletions — which is what a deployed system actually faces. The consequences show up in Definition 2.8 below.

2. The publishing function — a distinction worth borrowing

A learning algorithm is \mathcal{A}: \mathcal{Z}^* \to \Theta; an unlearning algorithm is \mathcal{R}_\mathcal{A}: \mathcal{Z}^* \times (\mathcal{Z}\times\mathcal{T}) \times \Theta \to \Theta. But:

"The output of the unlearning algorithm itself will not be made public: before any model is made public, it must pass through a publishing function f_{\text{publish}}: \Theta \to \Theta."

Definition 2.3 ((\varepsilon,\delta)-indistinguishability). X \approx_{\varepsilon,\delta} Y if for all S \subseteq \Omega, \Pr[X\in S] \le e^\varepsilon\Pr[Y\in S] + \delta and symmetrically.

Definition 2.4 ((\varepsilon,\delta)-unlearning). For every update step i \ge 1, with \theta_i = \hat\theta_{i-1}:

If the same holds with \theta_i = \tilde\theta_{i-1} — i.e. chaining from the published model rather than the secret one — then \mathcal{R}_\mathcal{A} is (\varepsilon,\delta)-perfect unlearning.

Remark 2.5 spells out why this matters:

"an unlearning algorithm takes as input the model output by the previous round's unlearning algorithm, whereas a perfect unlearning algorithm takes as input the model output by the previous round's publishing algorithm. Since we require that the published outputs satisfy (\varepsilon,\delta)-indistinguishability, this means that unlearning algorithms may need to maintain secret state that does not satisfy the indistinguishability guarantee, but that perfect unlearning algorithms do not need to."

So ordinary unlearning is allowed to keep a hidden model that would betray the forget set if released; perfect unlearning may not. This is a sharper and more operational version of the auditability worry raised by Machine Unlearning via Information Theoretic Regularization and On the Necessity of Auditable Algorithmic Definitions for Machine Unlearning — and notably it is a design distinction rather than a critique.

3. Definition 2.8 — strong vs weak unlearning

With (\alpha,\beta)-accuracy defined (Def. 2.7) as \Pr[f_{\mathcal{D}_i}(\tilde\theta_i) - \min_\theta f_{\mathcal{D}_i}(\theta) > \alpha] < \beta for every i, and C_i the computational cost of unlearning at step i:

\mathcal{R}_\mathcal{A} is a "strong" unlearning algorithm if

1. \alpha and \beta are independent of the length of the update sequence, and
2. C_i / C_1 = \mathcal{O}(\log i) — cost grows at most logarithmically in the number of requests handled so far.

If (1) holds but C_i/C_1 = \Omega(\text{poly}(i)), it is "weak".

This is the only formal treatment in our reading of what happens under many sequential deletion requests, and it is the axis on which most empirical vision methods are simply silent. SCRUB, Bad-T, Fisher, CF-k/EU-k are all evaluated on a single forget request against a single trained model; none reports how cost or accuracy degrades over a stream. That is a genuine, citable gap for gaps.md — and one our own Phase 1/2 inherits, since we also evaluate single-request unlearning.

4. The convexity dependence, stated by the authors

Lemma 2.12 (Sensitivity). If f_z is L-Lipschitz and m-strongly convex, then for any dataset \mathcal{D} of size n and any update u:

This is the same strongly-convex ERM stability bound Near-Optimal Pure Machine Unlearning for Smooth Strongly Convex Losses uses (\|\hat w_Z - \hat w_{Z\setminus U}\| \le 2L|U|/(\mu|Z\setminus U|)), and it is the load-bearing step in that whole family: strong convexity is what makes deleting a point move the optimum only O(1/n). Remove strong convexity and the bound is vacuous — there is no guarantee the retrained optimum is anywhere near the original.

Theorem 2.13 gives the matching GD convergence, \|\theta_T - \theta^\star\|_2 \le \big(\frac{M-m}{M+m}\big)^T\|\theta_0-\theta^\star\|_2 for m-strongly convex, M-smooth h with step size \eta_t = \frac{2}{m+M}.

And the authors are explicit about where this stops:

"for strongly convex and smooth functions we can obtain a perfect unlearning algorithm … with the same asymptotic accuracy/runtime tradeoff, so long as the per-update run-time is at least logarithmic in the dimension. For non strongly convex functions, our techniques do not appear to be able to give perfect unlearning algorithms for non-trivial parameters; this is an intriguing direction for future work."

A clean, quotable admission for the review's "what transfers?" section: the authors themselves mark the boundary at strong convexity.

5. §3 — the two algorithm families, and where each stops working

The definitions the note records above are the scaffolding; §1.3 and §3 say what is actually built on it. Two families, and the boundary between them is the convexity assumption.

Family 1 — perturbed gradient descent. After each addition or deletion the update algorithm "starts from the previous model, and performs a small number of gradient descent updates — sufficient to guarantee that the model parameter is boundedly close to the optimal model parameter in Euclidean distance. It then perturbs the model parameter with Gaussian noise of sufficient magnitude to guarantee (\varepsilon,\delta)-indistinguishability with respect to anything within a small neighborhood of the optimal model."

The guarantee it earns depends entirely on the loss:

"We prove that this simple approach yields a strong, perfect unlearning algorithm for loss functions that are strongly convex and smooth. Without the strong convexity assumption, we can still derive strong unlearning algorithms, but ones which must maintain secret state."

Family 2 — partition, average, perturb, and resample. For high-dimensional data they bootstrap-sample the dataset, randomly partition it into K parts, optimise each part independently, average the parameter vectors and release the perturbed average. The update step is where the work is: "a variant of reservoir-sampling that maintains the property that the union of the partitions continue to be distributed as independent samples drawn with replacement from our current dataset", after which only the modified partitions are updated. Because the marginal distributions are preserved, the accuracy analysis survives "an arbitrary sequence of updates".

Where it stops. They are explicit about the edge of the technique:

"For non strongly convex functions, our techniques do not appear to be able to give perfect unlearning algorithms for non-trivial parameters; this is an intriguing direction for future work."

The three distinctions they claim as new

Stated at the end of §1.3, and each one is a lens this project can use: deletion algorithms that keep no secret state are called perfect, and "all prior work focuses on perfect deletion algorithms" — allowing secret state is what buys their improved bounds; updates are arbitrary sequences that "can include additions and deletions (rather than just deletions)"; and strong versus weak separates algorithms whose runtime grows with the length of the update sequence from those whose does not.

The second is the one the review leans on. Sequential deletion is not an afterthought here — it is the object of study, and the paper is organised around the fact that a bound which degrades with sequence length is not a bound anybody can deploy.

6. Their criticism of SISA, which is a cross-track edge

§2's related work contains a direct, sourced comparison with Machine Unlearning, and it is worth recording as a criticism rather than as background because it names four specific differences:

"Bourtoule et al. use a similar technique in the context of machine unlearning that they call 'SISA' (Sharded, Isolated, Sliced, Aggregated). Their goal is more ambitious (to perform deletion for non-convex models), but they have a weaker deletion criterion (that it simply be possible that the model arrived at after deletion could have arisen from the retraining process), and they give no error guarantees. Their algorithm involves full retraining on the affected partitions, a different aggregation function, no randomization, and does not include the reservoir sampling step that is crucial to our stronger indistinguishability guarantees."

Three things follow.

(a) It is a theory paper criticising a method paper, which is the direction the review's §5 is short of. Most cross-track traffic in this corpus runs the other way — methods borrowing definitions from theory — so an explicit theory-side assessment of a named method is unusual and citable.

(b) The criticism is precise about what is traded. SISA's ambition (non-convex models) is acknowledged, and the cost is named: a possibilistic deletion criterion and no error guarantee. That is the same trade bourtoule2021sisa.md records from SISA's own side, now stated by a paper that did not have to concede it.

(c) The shared ancestry is named. Both descend from "Subsample and Aggregate" in differential privacy, and Neel et al. note the resemblance to FederatedAveraging. SISA is not an unlearning-specific invention so much as an unlearning-specific application of a known partition-and-aggregate pattern — which is a cleaner way to describe it than the review currently does.

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

• §3–§4 algorithms (including "Distributed PGD") and all proofs unread; no rates recorded.
• Assumption 2.6 requires dataset size never to drop below n/2 over the update sequence — a technical convenience, but it does bound how much can be deleted.
• Update sequences are defined as non-adaptively chosen, though the authors note their §3 algorithms also cover adaptive sequences.
• ERM/parameter-vector setting throughout; no deep networks.

8. Links

• Its (\varepsilon,\delta)-unlearning generalises the deletion notion of Making AI Forget You: Data Deletion in Machine Learning to update sequences (stated in §2).
• Lemma 2.12's sensitivity bound is the same tool Near-Optimal Pure Machine Unlearning for Smooth Strongly Convex Losses uses.
• Cited by When to Forget? Complexity Trade-offs in Machine Unlearning as the basis of its "Noise and Fine-Tune" upper-bound algorithm (perturbed gradient descent).
• Grouped with Certified Data Removal from Machine Learning Models and Remember What You Want to Forget: Algorithms for Machine Unlearning as DP-inspired approximate unlearning by Towards Unbounded Machine Unlearning §4.
• Its strong/weak distinction is the sequential-request axis missing from every vision method in this project's Stage 7 list.

@inproceedings{neel2021descent,
  title         = {{Descent-to-Delete:} {Gradient-Based} Methods for Machine Unlearning},
  author        = {Seth Neel and Aaron Roth and Saeed Sharifi-Malvajerdi},
  year          = {2021},
  booktitle     = {Algorithmic Learning Theory (ALT) 2021},
  eprint        = {2007.02923},
  archiveprefix = {arXiv},
  url           = {https://arxiv.org/abs/2007.02923}
}