Source-linked AI summary
Certified Data Removal from Machine Learning Models
Chuan Guo, Tom Goldstein, Awni Hannun, Laurens van der Maaten
TL;DR
The paper asks whether training data can be removed from a machine-learning model without retraining from scratch. It defines certified removal, develops a mechanism for linear classifiers, and evaluates when the approach is practical. The mechanism provides indistinguishability from a model that never saw the removed data, with substantial practical speedups in evaluated settings.
Problem
The paper asks whether data can be removed from a trained machine-learning model without retraining it from scratch.
Method
The paper defines certified removal and develops a Newton-step mechanism with residual masking for L2-regularized linear models trained with differentiable convex losses.
Results
The mechanism is practical in some settings, including over 10,000 LSUN removals after accuracy drops from 88.6% to 83.3%.
Takeaways & Limitations
Certified removal provides a strong guarantee that the post-removal model is indistinguishable from one that never observed the removed data.
Takeaways & Limitations
The trivial exact mechanism requires retraining from scratch, while the proposed approach has scope and computational limitations including Hessian inversion and unsupported non-convex losses.
Abstract
from arXiv · showhide
Good data stewardship requires removal of data at the request of the data's owner. This raises the question if and how a trained machine-learning model, which implicitly stores information about its training data, should be affected by such a removal request. Is it possible to "remove" data from a machine-learning model? We study this problem by defining certified removal: a very strong theoretical guarantee that a model from which data is removed cannot be distinguished from a model that never observed the data to begin with. We develop a certified-removal mechanism for linear classifiers and empirically study learning settings in which this mechanism is practical.
1. Introduction
The paper asks whether data can be removed from a pretrained model without retraining from scratch and introduces certified removal as a strong guarantee against recovering removed training information.
- Certified removal guarantees that an adversary cannot extract information about training data removed from a model.
- The guarantee bounds max-divergence between a model trained after removal and one trained without the removed instances.
- This guarantee makes membership-inference attacks unsuccessful on removed data.
- The authors develop a mechanism for L2-regularized linear models trained with differentiable convex losses, including logistic regression.
- The paper empirically studies settings in which certified removal is practical.
2. Certified Removal
Certified removal requires the post-removal model to be difficult to distinguish from one never trained on the removed sample. The paper contrasts this guarantee with practical costs, privacy conditions, and retraining-based alternatives.
- Certified Removal: Certified removal compares the output after removing x with a model trained on D \ x across all measurable model-output events.
- Certified Removal: The relaxed (ϵ, δ)-certified-removal notion allows the max-divergence bound to fail with probability at most δ.
- Practicality: Exact certified removal can be achieved trivially by retraining on D \ x, but this may be impractical whenever a sample is removed.
- Certified Removal: Approximate parametric closeness can still reveal whether a sample appeared during training, so certified removal targets indistinguishability instead.
- Relationship to Differential Privacy: Differential privacy is sufficient but not necessary for certified removal, and the paper frames removal as a utility-efficiency trade-off between privacy and retraining.
3. Removal Mechanisms
The paper develops certified-removal mechanisms for regularized linear models that approximate retraining after deletion, then mask residual information with randomized loss perturbation. The resulting guarantees cover individual and batch removals, with practical computational trade-offs and extensions to common regression and classification settings.
- Scope: The mechanism targets parametric models, beginning with strongly convex regularized linear models and extending to least-squares and logistic regression.The approach is designed for differentiable convex losses and L2-regularized linear models.
- Removal mechanism: A one-step Newton update uses the removed point’s gradient influence to approximately minimize the loss on the remaining dataset.The update is based on the Hessian at the original optimum and is also described as an influence function.
- Removal mechanism: The gradient residual measures approximation error: it is zero at the remaining-data minimizer and can be bounded for the Newton mechanism.Under the stated regularity conditions, the residual bound supports certification through a computable error parameter.
- Certification: Randomly perturbing the training loss masks information in the residual, enabling certified removal guarantees for approximate minimizers.The perturbation adds a random linear term, and the resulting density ratio is bounded by e^ϵ under Theorem 2.
- Certification: Suitable perturbation distributions yield either ϵ-certified removal or (ϵ, δ)-certified removal when the residual norm is bounded by ϵ′.The Gaussian choice uses b ∼ N(0, cϵ′/ϵ)^d with c > 0 for the (ϵ, δ) guarantee.
- Practical considerations: Repeated one-by-one removals accumulate residual norm at most (T + 1)ϵ′, while batch-removal bounds can scale quadratically with the number of removed samples.The quadratic batch behavior is attributed to evaluating the Hessian only once rather than once per removed datum.
4. Experiments
The experiments evaluate certified removal for standard linear models, public-feature linear models, and linear layers over differentially private features. Results show substantial removal capacity and faster updates, with trade-offs involving accuracy, privacy, and residual-bound tightness.
- The study evaluates certified removal in three settings: standard linear logistic regression, public-feature linear regression, and models using differentially private feature extractors.
- MNIST: The data-dependent gradient-residual bounds accumulate approximately linearly, but remain far above the true residual norm.The gap suggests that tighter analysis could improve the mechanism's utility.
- MNIST: On MNIST, the removal update varies substantially across samples: atypical digits are harder to remove, while prototypical 3s and 8s are easier.Large update norms correspond to oddly shaped digits; small norms correspond to prototypical digits.
- Public feature extractors: On LSUN, reducing accuracy from 88.6% to 83.3% supports over 10,000 removals, while removal costs are more than 250× lower than retraining.
- Public feature extractors: On SST, the regular model reaches 89.0% accuracy, and removal costs are 870× lower than retraining while supporting many removals at a small accuracy loss.
- Differentially private feature extractors: With differentially private SVHN features, certified removal achieves 71.2% accuracy at ϵ ≈0.1, versus 22.7% for the fully private baseline, with 0.27s removal time.Retraining the CNN from scratch takes more than 1.5 hour.
5. Related Work
Prior work studies exact or approximate removal through decremental learning, machine unlearning, and related clustering methods. Certified removal instead uses differential-privacy-style indistinguishability, connecting removal guarantees to privacy mechanisms.
- Prior decremental-learning and machine-unlearning studies target exact removal, measuring success by closeness to optimal parameters or objective values.
- Certified removal adopts differential privacy's indistinguishability notion, while prior work has developed private versions of models including PCA, matrix factorization, linear models, and neural networks.
- The authors identify future work on certified-removal algorithms with stronger guarantees and greater computational efficiency.
6. Conclusion
The conclusion presents certified removal as a fast, differentially private-style guarantee, while identifying computational, modeling, analytical, and conceptual limits that remain open.
- The mechanism makes the post-removal model indistinguishable from one that never saw the removed data, while operating quickly in some settings.
- The approach requires Hessian inversion, does not support non-convex losses, and has a substantial gap between data-dependent bounds and true residual norms.
- Some applications may require less constraining notions of data removal than certified removal.
A. Appendix
The appendix proves certified-removal guarantees for perturbed linear models, including Laplace and Gaussian perturbations, batch removal, and composition with differential privacy. The proofs relate gradient-residual bounds and density-ratio arguments to the resulting removal guarantees.
- Theorem 1: Theorem 1 bounds the gradient residual under bounded gradients, Lipschitz second derivatives, bounded feature norms, and strong convexity assumptions.The proof uses Taylor expansion, Hessian properties, and norm bounds to derive the residual guarantee.
- Theorem 2: Theorem 2 converts local density-ratio control for perturbation noise into a certified-removal guarantee for the resulting model distribution.Its proof bounds density ratios for nearby perturbations and applies the theorem to the optimizer’s induced distributions.
- Theorem 3: Theorem 3 gives certified-removal guarantees for a Newton-update mechanism when the reduced-data gradient at the pre-removal model has computable bound ϵ′.The guarantee uses perturbations whose distribution determines the security parameters.
- Theorem 4: The appendix extends the analysis to batch removal, where the Hessian contains n−m terms and the relevant change scales linearly with m.Theorem 4 states this extension under the same regularity conditions as Theorem 1.
- Theorem 5: Differentially private feature learning composes with certified removal, yielding parameters (ϵDP+ϵCR, δDP+δCR) for the full procedure.The proof integrates over the randomized feature extractor and combines the two guarantees.
Errata
The erratum corrects an assumption used in the removal analysis: because the perturbation vector is random, the relevant quantity lacks an absolute bound and instead requires concentration-based high-probability bounds.
- Erratum: The proof’s bound on ∆ must apply to the minimizer of the perturbed loss L_b(·; D), not only the unperturbed loss L(·; D).This distinction matters for applying Theorem 1 to Theorem 3, where b is sampled from a Laplace or Gaussian distribution.
- Erratum: Because b is random, ∆ cannot be upper bounded in absolute terms; concentration instead supplies high-probability bounds.The data-dependent bounds in Corollaries 1 and 2 are unaffected because they compute ∥∆∥2 directly.