Certified Data Removal from Machine Learning Models

Venue: ICML 2020 · arXiv: 1911.03030 Verification: dblp for venue; PDF fetched.

Read status: pp. 2–4 read from page images — §2 Certified Removal (the (\varepsilon,\delta)-CR definition, insufficiency of parametric indistinguishability, relationship to DP), §3.1 Linear Classifiers (Eq. 3 Newton update, Theorem 1, loss perturbation, Theorem 3), §3.2 Practical Considerations (Corollary 1, multiple removals, batch removal, Theorem 4). §3.3 read from text extraction. §1, §4 experiments and proofs not read.

Origin of the "certified removal" line. Cited by Machine Unlearning §III.D as a strawman and by Towards Unbounded Machine Unlearning §4 as DP-inspired approximate unlearning.

1. The definition

(\varepsilon,\delta)-certified removal. For \delta > 0, if for all \mathcal{T} \subseteq \mathcal{H}, \mathcal{D} \subseteq \mathcal{X}, \mathbf{x} \in \mathcal{D}:

and symmetrically. "\delta upper bounds the probability for the max-divergence bound … to fail."

The trivial \varepsilon = 0 mechanism ignores A(\mathcal{D}) and evaluates A(\mathcal{D}\setminus\mathbf{x}) — i.e. retraining. "We seek mechanisms M with removal cost O(n) or less, with small constants."

Why "approximately close in parameters" is not enough

A neat counterexample worth carrying into the review, since it prefigures Towards Adversarial Evaluations for Inexact Machine Unlearning's Theorem 1 from the opposite direction:

"Consider a linear regressor trained on \mathcal{D} = \{(\mathbf{e}_1,1),\dots,(\mathbf{e}_d,d)\} where \mathbf{e}_i are the standard basis vectors. A regressor initialized with zeros, or with a weight decay penalty, will place a non-zero weight on w_i if (\mathbf{e}_i,i) is included in \mathcal{D}, and a zero weight if not. In this case, an approximate removal algorithm that leaves w_i small but non-zero still reveals that (\mathbf{e}_i,i) appeared during training."

Relationship to differential privacy

DP is sufficient for certified removal — set M to the identity: "if algorithm A never memorizes the training data in the first place, we need not worry about removing that data." But not necessary: "a nearest-neighbor classifier is not differentially private but it is trivial to certifiably remove a training sample in O(1) time with \varepsilon = 0."

Their framing, which is the cleanest one-line placement of this whole literature:

"We therefore view the study of certified removal as analyzing the trade-off between utility and removal efficiency, with re-training from scratch and differential privacy at the two ends of the spectrum, and removal in the middle."

2. The mechanism

For a regularised linear model L(\mathbf{w};\mathcal{D}) = \sum_{i=1}^n \ell(\mathbf{w}^\top\mathbf{x}_i, y_i) + \frac{\lambda n}{2}\|\mathbf{w}\|^2_2 with \ell convex and everywhere differentiable, and \mathbf{w}^\star the unique minimiser:

with \Delta = \lambda\mathbf{w}^\star + \nabla\ell((\mathbf{w}^\star)^\top\mathbf{x}_n, y_n) and H_{\mathbf{w}^\star} = \nabla^2 L(\mathbf{w}^\star;\mathcal{D}'). A one-step Newton update; H^{-1}\Delta "is also known as the influence function of the training point."

Cost: "The Hessian matrix … can be formed offline with O(d^2 n) cost. The subsequent Hessian inversion makes the removal mechanism O(d^3) at removal time."

Theorem 1 (gradient residual bound). If \|\nabla\ell\|_2 \le C, \ell'' is \gamma-Lipschitz and \|\mathbf{x}_i\|_2 \le 1:

A small gradient residual is not itself certification. "the direction of the gradient residual may leak information about the training sample that was 'removed'. To hide this information, we use the loss perturbation technique of Chaudhuri et al. (2011)": L_{\mathbf{b}}(\mathbf{w};\mathcal{D}) = \sum_i \ell + \frac{\lambda n}{2}\|\mathbf{w}\|^2_2 + \mathbf{b}^\top\mathbf{w}.

Theorem 3. With \|\nabla L(\mathbf{w}^-;\mathcal{D}')\|_2 \le \varepsilon': (i) p(\mathbf{b}) \propto e^{-(\varepsilon/\varepsilon')\|\mathbf{b}\|_2} gives \varepsilon-CR; (ii) \mathbf{b} \sim \mathcal{N}(0, c\varepsilon'/\varepsilon)^d gives (\varepsilon,\delta)-CR with \delta = 1.5\,e^{-c^2/2}.

Special cases (§3.2). For least-squares the Hessian \mathbf{x}_i\mathbf{x}_i^\top is independent of \mathbf{w}, so the gradient residual is exactly zero and the Newton update is \varepsilon-CR with \varepsilon = 0, no perturbation needed — "not surprising since the Newton update assumes a local quadratic approximation of the loss, which is exact for least-squares." For logistic regression, \|\nabla\ell\|_2 \le 1 and \ell'' is \gamma-Lipschitz with \gamma = 1/4.

3. The removal budget — a detail with practical teeth

Multiple removals. "The worst-case gradient residual norm after T removals can be shown to scale linearly in T": \|u_T\|_2 \le T\varepsilon'.

Batch removal (Eq. 6) with Theorem 4: \|\nabla L(\mathbf{w}^{(-m)};\mathcal{D}\setminus\mathcal{D}_m)\|_2 \le \frac{4\gamma m^2C^2}{\lambda^2(n-m)} — quadratic in the batch size m.

Their Algorithm 2 therefore carries an explicit fallback: when the accumulated bound exceeds the budget, Re-train from scratch using Algorithm 1. So certified removal is not an unbounded capability but a budget that depletes and periodically forces retraining — which is essentially Remember What You Want to Forget: Algorithms for Machine Unlearning's deletion capacity arriving from the algorithmic side rather than the information-theoretic one.

4. §3.3 — what this actually gives you for a deep network

This is the crux, and the authors state it plainly:

"Deep learning models often apply a linear model to features extracted by a network pre-trained on a public dataset like ImageNet … In such setups, we only need to worry about data removal from the linear model that is applied to the output of the feature extractor.

When feature extractors are trained on private data as well, we can use our certified-removal mechanism on linear models that are applied to the output of a differentially-private feature extraction network."

Their experiments follow suit: removal "is only applied to the linear model", and for SVHN "removal is applied to a linear model that operates on top of a differentially private feature extractor."

🔑 The sharpest available statement of what does not transfer

Certified removal never certifies the representation. It certifies a linear head. The feature extractor is either (a) frozen and public — in which case, as Machine Unlearning §III.D notes, no guarantee is provided for it at all — or (b) DP-trained, which reintroduces the accuracy cost DP was invoked to avoid.

For our Phase 1/2 setting this is decisive. SCRUB unlearns a ResNet-18 fine-tuned end to end, where the forget set influenced every layer. Certified removal has nothing to say about that model. It is not that its bounds are loose for deep networks — it is that the object it certifies is a different object.

This also explains why SISA's §III.D dismissal is fair rather than uncharitable, and why SCRUB can claim methods with guarantees "aren't applicable to deep networks" without overstating.

Three further barriers, on top of the scope issue:

1. O(d^3) at removal time. For ResNet-18, d \approx 1.1\times10^7, so d^3 \approx 1.3\times10^{21}. Even the O(d^2 n) offline Hessian is out of reach.
2. The 1/\lambda^2 in Theorem 1. The bound degrades quadratically as regularisation weakens, and deep networks are trained at weight decays of 5\times10^{-4}.
3. Convexity and a unique minimiser are assumed throughout §3.1.

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

• §4 experiments and all proofs unread; no reported number recorded here.
• No claim is made for end-to-end non-convex training; §3.3 is explicit that the guarantee attaches to the linear layer.
• The multiple-removal analysis is worst-case and linear in T; no adaptive-adversary analysis in the sections read.

6. Links

• Rejected as a strawman by Machine Unlearning §III.D on exactly the §3.3 grounds above ("they resort to pretraining models on public data … or from differentially-private feature extractors").
• Grouped with 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.
• Its removal budget depleting into forced retraining is the algorithmic counterpart of Remember What You Want to Forget: Algorithms for Machine Unlearning's deletion capacity.
• Its Newton update is the same object Eternal Sunshine of the Spotless Net: Selective Forgetting in Deep Networks derives and then abandons, and that Forgetting Outside the Box: Scrubbing Deep Networks of Information Accessible from Input-Output Observations §4.1 shows degenerates when d > n.
• Its "approximate closeness still leaks" counterexample complements Towards Adversarial Evaluations for Inexact Machine Unlearning's Theorem 1 from the opposite direction.

@inproceedings{guo2020certified,
  title         = {Certified Data Removal from Machine Learning Models},
  author        = {Chuan Guo and Tom Goldstein and Awni Hannun and Laurens van der Maaten},
  year          = {2020},
  booktitle     = {ICML 2020},
  eprint        = {1911.03030},
  archiveprefix = {arXiv},
  url           = {https://arxiv.org/abs/1911.03030}
}