Approximate Data Deletion from Machine Learning Models

Venue: AISTATS 2021 · arXiv: 2002.10077 arXiv title differs: "Approximate Data Deletion from Machine Learning Models: Algorithms and Evaluations" (the AISTATS title drops the subtitle). Verification: dblp for venue; PDF fetched.

Read status: pp. 4–5 read from page images — Eq. 2 (the influence method), Table 1 (asymptotic costs), §4 The Projective Residual Update (Algorithms 1–2, Theorem 1, Definition 2, Corollary 3, Theorem 4), §4.1 Outlier deletion (Theorem 5), §4.2 Extension to logistic regression (Theorem 6). §1–3, §5–§7 and all experiments not read.

1. The method

Setting: linear regression. \theta(w) \equiv \arg\min_\theta \sum_i w_i \ell(x_i,y_i;\theta), with \theta^{\text{full}} = \theta(\mathbf{1}) and \theta^{\setminus k} the model with the first k weights zeroed — i.e. those k points deleted.

The influence method they compare against (Eq. 2):

The Projective Residual Update (PRU). The idea uses synthetic data: if we can compute the predictions \hat y_i^{\setminus k} = \theta^{\setminus k\top}x_i that the deleted model would make on the removed points — without knowing \theta^{\setminus k} — then taking a gradient step to fit those synthetic targets moves us toward \theta^{\setminus k}.

The trick for computing them is classical: "generalizing a well-known technique from statistics for computing leave-one-out residuals for linear models", via the hat matrix H \equiv X(X^\top X + \lambda I)^{-1}X^\top.

Algorithm 1  PRU(X, Y, H, θ_full, k)
  1: ŷ'_1..ŷ'_k ← LKO(X, Y, H, k)                    # leave-k-out predictions
  2: S⁻¹ ← PseudoInv( Σ_{i=1..k} x_i x_iᵀ )
  3: ∇L ← Σ_{i=1..k} (θ_fullᵀ x_i − ŷ'_i) x_i
  4: return θ_full − FastMult(S⁻¹, ∇L)

Algorithm 2  LKO(X, Y, H, θ_full, k)
  1: R ← Y_{1:k} − X_{1:k} θ_full
  2: D ← diag({ (1 − H_ii)⁻¹ })
  3: T_ij ← 1{i≠j} · H_ij / (1 − H_jj)
  4: Ŷ^{\k} ← Y_{1:k} − (I − T)⁻¹ D R

Theorem 1. Algorithm 1 computes \theta^{\text{res}} = \theta^{\text{full}} + \text{proj}_{\text{span}(x_1,\dots,x_k)}(\theta^{\setminus k} - \theta^{\text{full}}) in O(k^2 d).

Corollary 3 gives its optimality: for any gradient-based update using only the deleted points, \|\theta^{\setminus k} - \theta^{\text{res}}\| \le \|\theta^{\setminus k} - \theta^{\text{approx}}\|. The proof is one line — the gradient of squared loss at (x,y) is a scalar multiple of x, so any such update lies in \text{span}(x_1,\dots,x_k), and PRU is the projection onto exactly that span. As the authors put it, PRU "makes the most improvement possible for any parameter update which is a linear combination of the removed x_is."

2. The cost claim, stated precisely

Table 1 (asymptotic cost of the update):

"The projective residual update is the only method with linear dependence on d."

⚠️ Read that claim with its caveat, which the paper states plainly: "The precomputation costs for each of the methods (Newton, influence, and PRU) are approximately the same; they are dominated by forming and inverting the full Hessian, which takes time O(nd^2)."

So the linear-in-d property applies to the update, not the pipeline. The O(nd^2) Hessian is still required up front, which is the same wall Certified Data Removal from Machine Learning Models and Remember What You Want to Forget: Algorithms for Machine Unlearning hit. At d \approx 1.1\times10^7 this is out of reach regardless of how cheap the update step is. Quoting "linear in d" without the precomputation caveat would materially misrepresent the method.

3. §4.1 — the finding that transfers

Theorem 5. With D^{\text{full}} = \{(\lambda x_1, \lambda y_1)\} \cup D^{\setminus 1}, \theta^{\text{inf}} \to \theta^{\text{full}} as \lambda \to \infty.

In words: the influence method fails on outliers.

"when we try to delete points with large norm, the influence method will barely update the parameters at all, with the update shrinking as the size of the removed features increases … As the scaling factor \lambda grows, the full Hessian X^\top X + \lambda^2 x_1x_1^\top deviates more and more from the LOO Hessian X^\top X … On the other hand … the PRU computes the projection of this update onto the subspace spanned by the deleted points, and therefore in general its improvement will remain bounded away from 0 even as the outlier grows."

🔑 Why this matters well beyond linear regression

The points most likely to be the subject of a deletion request are atypical ones — the unusual medical record, the distinctive face, the memorised outlier. And those are exactly the points Membership Inference Attacks From First Principles and Inexact Unlearning Needs More Careful Evaluations to Avoid a False Sense of Privacy show are most vulnerable to membership inference, and that the memorisation literature identifies as the ones models actually memorise.

Theorem 5 says the influence-function family degrades precisely on that population. Since the influence/Newton correction is the shared skeleton of Certified Data Removal from Machine Learning Models, Remember What You Want to Forget: Algorithms for Machine Unlearning and Eternal Sunshine of the Spotless Net: Selective Forgetting in Deep Networks, this is a structural weakness of the whole second-order programme that is independent of the convexity and dimension arguments already recorded — a third, orthogonal reason it does not carry over.

It is stated and proved here only for linear regression, so the review must present it as suggestive for deep networks, not established there. But it is a sharp, citable observation and a plausible research thread: whether Fisher-based unlearning underperforms specifically on high-influence examples is something our Stage 6 harness could actually test, once per-example scores are stored.

4. Scope

§4.2 extends PRU to logistic regression via iteratively reweighted least squares — "a Newton step for logistic regression reduces to the solution of a weighted least squares problem" — with Theorem 6 giving the same O(k^2 d).

So the scope is linear and logistic regression. No deep networks, and none claimed. Not a Stage 7 candidate and not in SCRUB's comparison table.

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

• §1–3 and §5–§7 unread, including all experiments; no reported number recorded.
• Theorem 5's outlier result is proved for the influence method on linear regression; the extension to non-convex models is not addressed.
• O(nd^2) precomputation is acknowledged but not treated as a barrier, because d is small in their setting.

6. Links

• Grouped with Certified Data Removal from Machine Learning Models, Remember What You Want to Forget: Algorithms for Machine Unlearning and Descent-to-Delete: Gradient-Based Methods for Machine Unlearning as DP-inspired approximate unlearning by Towards Unbounded Machine Unlearning §4, and cited by When to Forget? Complexity Trade-offs in Machine Unlearning for adaptive unlearning requests.
• Shares the influence-function/Newton skeleton whose collapse across Remember What You Want to Forget: Algorithms for Machine Unlearning → Eternal Sunshine of the Spotless Net: Selective Forgetting in Deep Networks → Near-Optimal Pure Machine Unlearning for Smooth Strongly Convex Losses is the review's theory spine; Theorem 5 adds a third, orthogonal failure mode to that story.
• Its outlier finding connects to the per-example vulnerability variance in Inexact Unlearning Needs More Careful Evaluations to Avoid a False Sense of Privacy and Membership Inference Attacks From First Principles.

@inproceedings{izzo2021approximate,
  title         = {Approximate Data Deletion from Machine Learning Models},
  author        = {Zachary Izzo and Mary Anne Smart and Kamalika Chaudhuri and James Zou},
  year          = {2021},
  booktitle     = {AISTATS 2021},
  eprint        = {2002.10077},
  archiveprefix = {arXiv},
  url           = {https://arxiv.org/abs/2002.10077},
  note          = {arXiv version titled 'Approximate Data Deletion from Machine Learning Models: Algorithms and Evaluations'}
}