PaperlayerView exact revision on arXiv

Source-linked AI summary

Approximate Data Deletion from Machine Learning Models

Zachary Izzo, Mary Anne Smart, Kamalika Chaudhuri, James Zou

arXiv:2002.10077v2cs.LGstat.ML

TL;DR

Deleting specific training points from trained ML models matters for privacy and other applications, but exact retraining is costly. This paper proposes approximate deletion for linear and logistic models, with linear-in-dimension cost independent of dataset size, and introduces the feature injection test to evaluate removal thoroughness.

  • Problem

    Removing an individual’s influence from a trained ML model is needed for privacy requirements such as the Right to be Forgotten, while retraining on remaining data is computationally costly.

  • Method

    The paper introduces projective residual update (PRU) for approximate deletion in linear and logistic regression and proposes the feature injection test (FIT) to evaluate model knowledge removal.

  • Results

    PRU has O(d) computational cost independent of n, improves on existing methods with Ω(d^2) cost, and experiments support the theoretical findings.

  • Takeaways & Limitations

    Approximate deletion can remove training-point effects from linear and logistic models without computational cost depending on the number of training data, while FIT evaluates deletion thoroughness.

  • Takeaways & Limitations

    The approximation’s accuracy decays as more deletion requests are processed, and extending the methods to fully online repeated batch requests remains future work.

Abstract

from arXiv · show

Deleting data from a trained machine learning (ML) model is a critical task in many applications. For example, we may want to remove the influence of training points that might be out of date or outliers. Regulations such as EU's General Data Protection Regulation also stipulate that individuals can request to have their data deleted. The naive approach to data deletion is to retrain the ML model on the remaining data, but this is too time consuming. In this work, we propose a new approximate deletion method for linear and logistic models whose computational cost is linear in the the feature dimension $d$ and independent of the number of training data $n$. This is a significant gain over all existing methods, which all have superlinear time dependence on the dimension. We also develop a new feature-injection test to evaluate the thoroughness of data deletion from ML models.

1 Introduction

Approximate data deletion addresses the need to remove training-point influence without infeasible full retraining. The paper introduces PRU for efficient deletion and FIT for evaluating removal of sensitive feature knowledge.

  • Motivation: Exact deletion generally requires retraining from scratch, which is infeasible for prompt online requests.For logistic regression trained by SGD, retraining takes O(ndP).
  • Motivation: Approximate deletion has both algorithmic and evaluation challenges.The paper makes progress on deleting points effectively and quickly and on quantifying deletion quality.
  • Contributions: PRU computes an approximate deletion update in O(d) time, independent of the number of training data n.Its cost matches the lower bound required to specify all d model-parameter entries and improves on existing methods with Ω(d^2) cost.
  • Contributions: PRU projects the exact parameter update onto a particular low-dimensional subspace and is optimal within a certain class of gradient-based deletion methods.The optimality criterion is deletion accuracy.
  • Contributions: FIT evaluates whether deletion removes the model’s knowledge of a sensitive, highly predictive feature.It injects a synthetic feature correlated with the label only for deleted points and measures the remaining weight on that feature.
  • Contributions: Experiments on real and synthetic datasets corroborate the paper’s theoretical findings.The reported support covers the proposed deletion method and evaluation criterion.

2 Notation and Problem Setup

The problem setup considers batch deletion requests for linear and logistic models under explicit dataset and regularization conventions. The framework permits precomputation but focuses on just-in-time cost for a single batch request.

  • Notation and request model: The notation uses n for training points, d for data dimension, and k for points deleted simultaneously in a batch.The setup assumes n ≫ d ≫ k.
  • Models and datasets: The full model minimizes the regularized loss on all training data, while the LKO model minimizes it after removing the requested points.For linear regression, the full-model parameters have an explicit ridge-regularized solution.
  • Assumptions: The deleted points need not resemble the remaining data, and removed outliers may substantially change model parameters.The setup makes no similarity or i.i.d. assumption for deleted points.
  • Computational model: Computational comparisons count just-in-time updating and rapid redeployment after a deletion request, while allowing reasonable precomputation.Precomputation cannot depend on which points will later be deleted.
  • Scope: The framework focuses on fulfilling one batch deletion request and identifies fully online repeated requests as future work.The authors note that precomputation between requests becomes significant in the online setting.
  • Model scope: The paper derives results for linear and logistic regression, emphasizing linear regression in the main text and treating logistic regression as an extension.The logistic extension uses iteratively reweighted least squares and approximates a Newton step through weighted least squares.
  • Model scope: The linear-model framework can apply to last-layer retraining when earlier neural-network layers are treated as a fixed feature map.The paper connects this reduction to prior influence and data-contribution analyses.

3 Methods

The methods range from exact retraining and Newton updates to influence-based approximation, with computational costs shaped by dataset size and feature dimension.

  • Exact retraining: Exact linear-regression deletion costs O(nd^2) analytically or O(ndP) with SGD.Analytic retraining forms a new Hessian, while SGD requires P passes over n examples.
  • Newton’s method: Newton’s method forms a quadratic approximation to the leave-one-out loss and gives an exact solution for least-squares linear regression.For quadratic losses, the approximation equals the original loss.
  • Influence method: Influence methods use a linear approximation around the full-data parameters, but their Hessian-gradient product costs O(d^2).This assumes access to the inverse Hessian, while the Hessian-gradient product remains the bottleneck.
  • Computational comparison: PRU is listed alongside exact and influence methods as an approximate retraining method with linear dependence on d.The shared precomputation for Newton, influence, and PRU is dominated by forming and inverting the full Hessian in O(nd^2) time.

4 The Projective Residual Update

The projective residual update uses synthetic data and gradient-based updates to approximate leave-k-out parameters by projecting the exact update onto the deleted points’ feature span. It supports linear and logistic regression with costs that scale linearly in d for small deletion groups.

  • Core idea: PRU constructs synthetic points using predictions for the deleted examples, then minimizes loss on those points with a modified gradient step.The synthetic targets are intended to move parameters toward the leave-k-out solution without knowing that solution directly.
  • Linear regression: Theorem 1 states that PRU returns θres = θfull + projspan(x1,...,xk)(θ\k − θfull) at cost O(k^2d).The update is the projection of the exact parameter change onto the deleted examples’ feature span.
  • Optimality: PRU is optimal among gradient-based updates whose parameter changes lie in the span of the deleted feature vectors.For square loss, every such gradient update remains in that span, and PRU achieves the largest possible improvement within the class.
  • Efficient subroutines: Leave-k-out predictions can be computed in O(k^3) time, enabling the synthetic targets required by the update.The method uses precomputed quantities such as the hat matrix to support efficient deletion-time computation.
  • Outlier deletion: For large-norm outliers, the influence update approaches no parameter change, whereas PRU’s improvement remains bounded away from zero and eventually outperforms influence.The contrast arises because the full Hessian increasingly diverges from the leave-one-out Hessian as the outlier scale grows.
  • Logistic regression: For logistic regression, PRU leverages iteratively reweighted least squares and computes a projected Newton update in O(k^2d) time.Algorithm 3 applies the linear-regression construction to weighted least squares induced by the logistic model.

5 Evaluation Metrics

The evaluation combines parameter-distance measurement with the feature injection test, which probes whether localized sensitive correlations disappear after deletion.

  • L2 distance: L2 distance measures how closely approximate parameters match parameters obtained by exact retraining from scratch.For models continuous in their parameters, a small parameter distance guarantees similar predictions.
  • Feature injection test: FIT evaluates whether an approximate method removes a specially injected sensitive feature from the model.The test targets fine-grained deletion of localized correlations that may matter to minority groups.
  • FIT construction: FIT injects a feature that is nonzero only for a small subset and perfectly correlated with the target label, then compares its learned weight before and after deletion.With strictly positive regularization, exact retraining sets this feature’s post-deletion weight to zero.

6 Empirical Validation

Experiments on synthetic and Yelp data validate the theoretical behavior of PRU for linear and logistic regression. PRU is especially effective for feature deletion in sparse settings, while runtime gains are strongest for high-dimensional, small-group deletions.

  • Synthetic data: PRU and influence are both significantly faster than exact retraining, with PRU more than 3000 times faster at d = 3000 and k = 1.PRU is faster than influence for small deletion groups.
  • Synthetic data: PRU can completely remove the injected feature when sparsity makes the deleted-point span contain or closely approximate the corresponding standard basis vector.This phenomenon appears in several tested synthetic settings.
  • Synthetic data: The influence method performs poorly compared with PRU in most FIT scenarios and exhibits substantially lower numerical stability.PRU’s standard errors were well below 5% of the mean.
  • Synthetic data: For L2 deletion of typical points, influence outperforms PRU, but its performance drops sharply as deletion groups grow while PRU remains nearly unaffected.Typical points are described as i.i.d. with the rest of the data when λ = 1.
  • Yelp: On Yelp, where large outliers are absent, influence outperforms PRU on the L2 metric, while PRU deletes the injected feature more effectively and remains more stable.The Yelp FIT comparison reports means with standard errors of the mean.
  • Logistic regression: PRU performs very well on both the L2 metric and FIT in the sparse logistic-regression setting.The experiment uses n = 5000 datapoints with d = 1000.

7 Related Work

Prior data-deletion work includes model-specific methods, warm-start retraining, statistical-query approaches, and sharding-based retraining. This work’s stated distinction is a deletion algorithm for parametric models with runtime linear in data dimension and independent of dataset size.

  • Prior approaches: Earlier approaches targeted specific model classes, including clustering, logistic regression, and more general statistical-query learning settings.The logistic-regression approach uses retraining with warm starts, while the statistical-query method covers a broader class of models.
  • Prior approaches: SISA reduces retraining cost through sharding and caching operations during training.SISA stands for Sharded, Isolated, Sliced, and Aggregated training.
  • Prior approaches: Influence- and Newton-based methods are closely related to several earlier deletion updates, including methods differing only in update step size.The cited Monari–Dreyfus method is described as the influence method with a different update step size.
  • Privacy-related work: Differential privacy addresses risks associated with training-set membership, but its stronger guarantees can reduce accuracy.The paper contrasts this with allowing users to opt out from a non-private model.
  • Positioning: The paper identifies PRU as the first deletion algorithm for parametric models with runtime linear in data dimension and independent of dataset size.It presents this as a key advantage for high-dimensional machine learning.

8 Conclusion

The paper studies approximate deletion for linear and logistic regression, introducing PRU for efficient updates and the feature injection test for evaluating deleted knowledge. Its guarantees and experiments support the approach, while repeated deletions and practical online deployment remain future work.

  • Contributions: The projective residual update (PRU) targets linear and logistic regression with computational cost linear in feature dimension.It improves on methods with quadratic dimension dependence.
  • Contributions: The feature injection test measures whether deletion removes model knowledge of a sensitive, highly predictive feature.The test adds a synthetic feature to deleted points and measures how much its weight is removed.
  • Evidence: Theoretical findings are corroborated by experiments on real and synthetic datasets.The experiments evaluate the proposed deletion and feature-injection procedures.
  • Limitations and future work: The approximation decays as more deletion requests are processed, motivating future work on repeated and fully online deletion.The paper identifies online settings with significant precomputation between requests as an important next step.
  • Efficiency: The total computational cost is O(k2d) when the batch size k is at most the feature dimension d.The component costs are O(k3), O(k2d), and O(kd).

B Performance analysis for outlier removal

This analysis characterizes approximate and exact deletion steps for outlier removal in linear regression. It shows that the influence-based step approaches the exact step as outlier size grows and derives efficient leave-k-out prediction computation.

  • Outlier-limit behavior: As the outlier size λ grows, the exact deletion step approaches C ˆΣ^-1x1, where C is data-dependent and ˆΣ is the covariance matrix without the outlier.This is stated as Proposition 7.
  • Outlier-limit behavior: The influence-based step has the same limiting value as the exact deletion step as λ approaches infinity.The proof compares the limits of θinf − θ\1 and θfull − θ\1.
  • Leave-k-out computation: The analysis assumes access to the full model’s hat matrix after training.This matrix supports efficient computation of leave-k-out quantities.
  • Leave-k-out computation: Leave-k-out predictions can be obtained by solving k linear equations in O(k3) time and recovering the predictions in an additional O(k) time.The construction uses residuals and the hat matrix.

D Generalization of Theorem 4 to weighted, ridge regularized least squares

Theorem 4 extends from ordinary least squares to weighted least squares with ridge regularization when the regularization strength is fixed independently of sample size.

  • Generalized objective: The weighted, regularized loss includes weighted residual terms and a ridge penalty λ∥θ∥2.The weights are nonnegative and λ is required to be fixed independently of the number of samples.
  • Generalization: The same leave-k-out prediction logic applies after replacing H with Hλ,w.The weight vector is fixed and the regularization strength must remain fixed.
  • Generalization: The generalized setting computes leave-k-out predictions in O(k3) time when Hλ,w is precomputed.Theorem 4 therefore holds for weighted, regularized least squares.

E Proof of Theorem 6

For logistic regression, the paper uses the iteratively reweighted least-squares structure to approximate a Newton deletion step. The resulting PRU step is the projection of the exact Newton step onto the deleted points’ feature span.

  • Logistic objective: The logistic classifier uses hθ(x) = 1/(1 + exp{−θ⊺x}), with predictions entering the gradient and Hessian.The Hessian uses diagonal terms hθ(xi)(1 − hθ(xi)).
  • Logistic extension: A logistic-regression Newton step reduces to solving a weighted least-squares problem.This enables the logistic extension of PRU.
  • Logistic extension: The method computes a fast approximation to the Newton step using precomputed full-loss quantities and a generalized leave-k-out procedure.The precomputed quantities include the gradient and a weighted hat matrix.
  • Theorem 6: The PRU step equals projspan(x1,...,xk)(θ\k−θfull), where θ\k−θfull is the Newton step.The computational cost calculation matches the linear-regression analysis.

F Synthetic data construction

The experiments construct synthetic linear and logistic datasets with controlled sparsity, deletion groups, outliers, and injected features. They then compare deletion methods using runtime, parameter-distance, and feature-removal outcomes.

  • General setup: Synthetic covariates are generated from Gaussian rows with a randomly selected covariance matrix, and linear responses use θ* plus Gaussian noise.The experiments set σ^2 = 1 and use n = 10d.
  • L2 experiment: The L2 experiment scales the first k points by λ to test deletion methods on outlier datapoints.Both covariates and responses for the points eventually deleted are multiplied by λ.
  • Feature-injection experiment: The feature-injection experiment makes the deleted points share a low-dimensional subspace, assigns them a unique injected feature, and perfectly correlates their responses with it.Only deleted points retain the injected feature, while the remaining points have that feature set to zero.
  • Sparse data construction: Sparse datasets are produced by zeroing entries with probability 1 − p, separately for the first k rows and the remaining entries.The procedure sparsifies the first k rows simultaneously and then sparsifies the rest of the matrix.
  • Logistic experiment: The logistic feature-injection setup restricts deleted points to the positive class and requires the full model to classify them correctly.These conditions define the logistic FIT data-generation assumptions.
  • Baseline results: Baseline experiments show runtimes rise sharply with dimension and slowly with group size, while parameter distance increases with deletions and outlier dissimilarity.For linear regression, the injected-feature baseline weight is close to its true value, 10.
  • Logistic results: For sparse logistic data, PRU can completely remove the injected feature for larger groups and becomes nearly as accurate as Newton’s method with faster runtime in the L2 experiment.Newton’s method completely removes the injected feature with strictly positive regularization but is substantially slower than PRU.
Loading 2002.10077v2…