PaperlayerView exact revision on arXiv

Source-linked AI summary

Making AI Forget You: Data Deletion in Machine Learning

Antonio Ginart, Melody Y. Guan, Gregory Valiant, James Zou

arXiv:1907.05012v2cs.LGstat.ML

TL;DR

The paper addresses how to remove an individual’s data from a trained machine-learning model when continued use is no longer permitted, without routinely retraining from scratch. It formalizes deletion-efficient learning, develops k-means algorithms and design principles, and reports over 100× average speedup across six datasets with comparable clustering quality to k-means++.

  • Problem

    The paper asks how to update a trained model after deleting an individual data point so it matches training on the remaining data, since retraining can be computationally impractical.

  • Method

    The paper formalizes exact data deletion and online deletion efficiency, then proposes two theoretically guaranteed deletion-efficient algorithms for k-means clustering.

  • Results

    Over six datasets, the methods achieved an average of over 100× amortized-runtime speedup while producing clustering quality comparable to the canonical k-means++ baseline.

  • Takeaways & Limitations

    The results show that k-means can support efficient data deletion without sacrificing comparable statistical clustering quality.

  • Takeaways & Limitations

    The paper focuses on exact data deletion and defers a fuller discussion of approximate deletion to future work.

Abstract

from arXiv · show

Intense recent discussions have focused on how to provide individuals with control over when their data can and cannot be used --- the EU's Right To Be Forgotten regulation is an example of this effort. In this paper we initiate a framework studying what to do when it is no longer permissible to deploy models derivative from specific user data. In particular, we formulate the problem of efficiently deleting individual data points from trained machine learning models. For many standard ML models, the only way to completely remove an individual's data is to retrain the whole model from scratch on the remaining data, which is often not computationally practical. We investigate algorithmic principles that enable efficient data deletion in ML. For the specific setting of k-means clustering, we propose two provably efficient deletion algorithms which achieve an average of over 100X improvement in deletion efficiency across 6 datasets, while producing clusters of comparable statistical quality to a canonical k-means++ baseline.

1 Introduction

The paper frames efficient deletion of individual data points from trained machine-learning models as a response to data-withdrawal rights and costly retraining. It formalizes the problem, develops k-means solutions, and reports strong efficiency and clustering-quality results.

  • Motivation: Individuals may request that their data no longer be used, creating a challenge for models trained on large collections of personal records.The motivation includes UK Biobank withdrawals and legal requirements such as the GDPR and Right to Be Forgotten.
  • Problem: Deleting one training point should produce a model independent of that point and distributed as if trained on the remaining data.Retraining from scratch is often impractical because large-scale training can require substantial time, computation, and energy.
  • Research gap: Deletion efficiency had not previously been studied generally, leaving no established notion of asymptotic efficiency or the trade-offs faced by learning systems.The paper notes that only a handful of known algorithms supported fast deletion, and those were deterministic.
  • Results: Over six datasets, the proposed methods achieved an average of over 100× amortized-runtime speedup while performing comparably to the canonical k-means++ baseline on three clustering-quality metrics.The comparison is against Lloyd’s algorithm seeded by k-means++.
  • Contributions: The paper formalizes efficient data deletion and proposes two deletion-efficient k-means solutions with theoretical guarantees and strong empirical results.It also synthesizes four engineering principles for designing deletion-efficient learning systems.

2 Related Works

Prior work provides efficient deletion for several deterministic learning algorithms, while privacy methods address a different objective. Efficient deletion and privacy are therefore distinct properties.

  • Efficient deletion: Known efficient-deletion methods include linear models, certain lazy-learning techniques, recursive support vector machines, and co-occurrence-based collaborative filtering.Examples include kernel regression and nearest-neighbor methods among lazy-learning techniques.
  • Privacy distinction: Cryptography and differential privacy aim to protect or obscure data rather than provide efficient deletion operations.The paper distinguishes privacy from deletion: private algorithms need not support efficient deletion, and deletion-capable algorithms need not be private.

3 Problem Formulation

The paper defines exact data deletion and studies its computational challenge online, seeking sublinear deletion costs through algorithm design and supporting metadata. It identifies four design principles and applies them to k-means.

  • 3 Problem Formulation: Data deletion updates a model so its distribution matches that of the learning algorithm trained on the dataset with the selected point removed.The framework permits randomized algorithms and metadata that can support later deletions.
  • 3 Problem Formulation: Exact deletion requires the updated model to behave as if the deleted training point had never been seen.The paper notes that approximate deletion can instead bound distributional distance or divergence, but defers fuller treatment.
  • A Computational Challenge: Retraining on the reduced dataset is always valid, so the central challenge is making deletion computationally efficient.The formulation asks whether deletion can be sublinear in dataset size or original training time and how metadata memory affects efficiency.
  • Data Deletion as an Online Problem: The online formulation represents deletion as a stream of up to n distinct indices removed from an initially trained model.This setting supports amortized-runtime analysis over multiple deletion requests.
  • A Computational Challenge: Ω(n/m) is the amortized computation-time lower bound for sequential learning algorithms processing n points across m deletion requests.An algorithm attaining this bound is called deletion efficient.
  • A Computational Challenge: The k-means case study shows deletion efficiency can be achieved without sacrificing statistical performance.The paper presents this as an application of the general computational framework.
  • 3.1 General Principles for Deletion Efficient Machine Learning Systems: Four design principles are identified: linearity, laziness, modularity, and quantization.Linearity enables explicit parameter updates; laziness delays computation; modularity localizes recomputation; quantization exploits model stability.

4 Deletion Efficient Clustering

The paper develops deletion-efficient k-means clustering through quantized updates and divide-and-conquer structure, combining theoretical deletion guarantees with statistical-performance analysis. Q-k-means enables deletion by exploiting centroid stability, while DC-k-means partitions data into subproblems and recursively merges results.

  • Overview: The paper treats k-means centroids as the model to update when deleting datapoints and proposes two deletion-efficient algorithms.The algorithms are Q-k-means and DC-k-means.
  • Q-k-means: Q-k-means quantizes centroids during Lloyd’s iterations, using quantized stability so most deletions avoid recomputing centroids.Deletion checks whether removing a datapoint would change the quantized centroid; otherwise metadata is updated without recomputation.
  • Q-k-means: Q-k-means differs from canonical Lloyd’s through quantization, memoization, balance correction, and early termination.Quantization uses a randomly shifted uniform ϵ-lattice; early termination occurs when loss increases, and the algorithm terminates almost surely.
  • Q-k-means: Q-k-means supports m deletions in expected time O(m2d5/2/ϵ), with probability over quantization and k-means++ initialization randomness.Its statistical guarantee gives EL≤(8logk+16)L∗+ϵ, and the expected-loss upper bound can be as good as k-means++.
  • DC-k-means: DC-k-means partitions data into small independent k-means problems and recursively merges their results.For a depth-1 w-ary tree with w=Θ(n^ρ), it supports m deletions in expected time O(mmax{n^ρ,n1−ρ}d).
  • DC-k-means: Increasing DC-k-means tree width tends to decrease statistical performance, making width a trade-off knob for deletion efficiency and clustering quality.Depth-1 DC-k-means is reported to offer an empirically compelling trade-off between deletion time and statistical performance.
  • Deletion-efficiency guarantees: Q-k-means is α-deletion efficient in expectation when α≤1−β with ϵ=Θ(n^−β), while DC-k-means is α-deletion efficient when α<1−max{1−ρ,ρ}.These conditions apply for 0<β<1 and 0<ρ<1, respectively.

5 Experiments

The experiments benchmark deletion runtime and clustering quality for two proposed algorithms against the canonical k-means++ baseline across six datasets. Both proposed methods retain competitive clustering quality while providing orders-of-magnitude speedups, with their relative advantages depending on dimensionality and sample size.

  • Benchmark and metrics: The experiments cover five real datasets and one synthetic Gaussian-mixture dataset, spanning sample sizes from 1,018,298 to 12,009 and dimensions from 10 to 784.The datasets are Celltype, Covtype, MNIST, Postures, Botnet, and Gaussian.
  • Benchmark and metrics: The benchmark simulates 1,000 uniformly random deletions without replacement after one full-dataset training, while the baseline retrains from scratch for each request.Runtime is measured over the online deletion stream.
  • Benchmark and metrics: Clustering quality is evaluated using k-means loss, silhouette coefficient, and normalized mutual information.Silhouette measures density and separation without labels; NMI measures agreement with ground-truth labels.
  • Results: The three algorithms achieve competitive statistical clustering performance across the reported loss, silhouette, and NMI evaluations.Tables 1–3 report these quality measures for each algorithm on each dataset.
  • Results: Both proposed algorithms yield orders-of-magnitude speedups over the k-means++ baseline in deletion efficiency.Q-k-means is faster when dimension is lower relative to sample size, whereas DC-k-means is more consistent across dimensionalities.
  • Results: 1,000 deletions represent less than 10% of every tested dataset, while statistical performance remains virtually unchanged throughout the benchmark.Figure 1 plots amortized runtime against the number of deletions in the stream.

6 Discussion

The discussion presents deletion-efficient learning as a broader design agenda beyond clustering. It proposes applying quantization, modularity, and stable updates to several supervised learning families, while noting substantial requirements for neural-network settings.

  • Broader applications: The paper identifies four design principles intended as pillars for deletion-efficient learning algorithms beyond the clustering case study.The authors discuss potential applications to other supervised learning techniques.
  • Broader applications: Segmented regression could combine Q-k-means with separate linear least-squares models for each cluster, updating only the model associated with a deletion.This proposal relies on Q-k-means keeping clusters stable.
  • Broader applications: Random Fourier feature kernel regression could support efficient deletions by updating only the linear layer over data-independent features.The passage also notes that random Fourier feature methods have affinity for quantization.
  • Broader applications: Decision trees could use quantized or randomized splitting criteria, while random forests could exploit bagging to impose modularity.These are presented as promising approaches rather than evaluated methods.
  • Broader applications: Applying deletion-efficient ideas to deep neural networks may require quantized gradient updates, larger batches, and fewer gradient steps for scalable SGD-style training.Approximate deletion may help address shortcomings of exact deletion methods for large neural models.

7 Conclusion

The conclusion presents deletion efficiency as a framework for large-scale learning, demonstrates provably efficient clustering algorithms, and identifies principles for extending the idea. It also acknowledges that the study relies on simplifying assumptions and leaves much to investigate.

  • Conclusion: The paper develops a notion of deletion efficiency for large-scale learning systems and proposes provably deletion-efficient unsupervised clustering algorithms.It also identifies potential algorithmic principles for other learning algorithms and paradigms.
  • Conclusion: The authors identify potential algorithmic principles that may enable deletion efficiency beyond the studied clustering setting.The conclusion characterizes the work as an initial exploration of deletion efficiency.
  • Conclusion: The study makes simplifying assumptions, including a setting with only one model and one database.The supplied conclusion passage indicates that these assumptions limit the scope of the current understanding.

A.1 Online Data Deletion

This appendix defines data deletion through an online sequence of updates whose output matches retraining on the remaining data, and defines efficiency relative to an amortized lower bound. It distinguishes average-case deletion from robust and approximate variants, highlighting adversarial and modeling limitations.

  • Definitions and setting: A learning algorithm may be randomized, must process every datapoint, and operates under sequential computation with runtime bounded by Ω(n).Models may include metadata that supports subsequent deletions.
  • Definitions and setting: A data deletion operation must produce, in distribution, the model that the learning algorithm would train on the dataset with the requested datapoint removed.The standard definition assumes the deletion index is selected independently of the trained model state.
  • Online deletion: The online deletion problem supplies distinct deletion indices one at a time and requires outputting the model trained on the dataset after each cumulative deletion.The operation can be represented as a sequence of deletion updates.
  • Robustness and relaxations: Robust deletion allows deletion requests selected with knowledge of the algorithm state, but adversarial requests can compromise DC-k-means exactness and make Q-k-means inefficient.For Q-k-means, repeatedly deleting an initial centroid can force retraining from scratch.
  • Online deletion: The paper analyzes average-case online deletion, where deletion indices are uniformly and independently selected without replacement; adversarial sequences are left for future work.Memory constraints are also identified as a possible additional consideration.
  • Efficiency: For m=Θ(n^α) deletions, an algorithm is α-deletion efficient when its amortized runtime is O(n^(1−α)), matching the sequential lower-bound scaling.The proposed k-means algorithms achieve the ideal lower bound only for sufficiently small α.
  • Scope boundary: Lazy and non-parametric methods fall outside the main notion of a learning algorithm because they process data at inference time rather than training time.The trade-offs among training, inference, and deletion time are left for future work.
  • Robustness and relaxations: Approximate deletion relaxes exact distributional matching, while differential privacy introduces online group-size and dataset-size leakage concerns.The appendix notes that technical details remain unresolved for privatization-based approximate deletion.

C.1 Proof of Theorem 4.1

The proof establishes that quantized k-means centroids remain unchanged under up to m deletions with high probability, enabling efficient deletion verification and fallback retraining. The resulting expected deletion time is O(m^2d^5/2/ϵ).

  • O(m^2d^5/2/ϵ) expected time supports m deletions with Q-k-means.
  • The theorem assumes data scaled to the unit hypercube, while a constant radial bound preserves the result for otherwise-scaled data.
  • 2dϵ′ bounds the probability that uniform quantization changes within an ϵ′-ball around a point.The argument reduces the failure event to boundary regions of a shifted quantization cell.
  • With probability greater than 1−2mTkd^3/2/(ϵγn), Q-k-means centroids are unchanged after deleting any at most m non-initialization points.The probability is over the randomness in the quantization phase.
  • The proof compares executions on D and D−∆ using identical initial centroids and identical independent quantization maps.Their only input difference is the deleted subset ∆.
  • The deletion procedure verifies stability using a training-time memo and retrains from scratch only when deletion would change the output.Expected runtime averages the verification cost and the fallback retraining cost.

C.2.1 Proof of Corollory 4.1.1

This proof transfers the k-means++ loss guarantee to Q-k-means by bounding quantization error, and analyzes DC-k-means deletion runtime through randomized data partitioning. The resulting loss and runtime bounds retain the k-means++ quality factor and sublinear dependence on partition width.

  • k-means++ achieves expected loss E[L++]≤(8lnk+16)L*.
  • E[L]≤(8lnk+16)L*+ϵ bounds Q-k-means loss on a problem instance.The bound adds a quantization-dependent ϵ term to the k-means++ guarantee.
  • O(mn^max(ρ,1−ρ)d) expected time supports m DC-k-means deletions with w=Θ(n^ρ) and a depth-1 w-ary tree.
  • DC-k-means assigns points independently to leaves, so deleting a point preserves the distribution of the remaining assignments.The number of leaves is rounded to a power of two to avoid deletion-dependent leaf counts.
  • The runtime bound separates deletion work at the leaves, O(kTdJ), from root work, O(n^ρk^2Td).J models the subproblem size for a randomly selected datapoint.

C.2.3 Proof of Corollary 4.2.1

The corollary identifies when Q-k-means remains deletion efficient under polynomial scaling of dataset size, deletion count, and quantization granularity.

  • α≤1−β is sufficient for deletion efficiency when ϵ=Θ(n^−β) and m=Θ(n^α).The amortized runtime comparison yields O(n^(1−α)+n^(α+β)).

C.2.4 Proof of Corollary 4.2.2

The corollary gives the polynomial scaling condition for deletion-efficient DC-k-means, while the appendix describes the six-dataset experimental protocol and parameter choices used to evaluate runtime and clustering quality.

  • C.2.4 Proof of Corollary 4.2.2: α≤1−max(ρ,1−ρ) is sufficient for deletion efficiency when w=Θ(n^ρ) and m=Θ(n^α).The per-deletion runtime is O(n^max(ρ,1−ρ)) and training time is O(n).
  • Experimental protocol: The experiments compare k-means, Q-k-means, and DC-k-means on six datasets using single-core wall-clock execution time as a deletion-efficiency proxy.
  • Experimental protocol: Each benchmark trains once, evaluates clustering quality, and then processes 1,000 uniformly random deletion requests without replacement.Five replicates are run for each method-dataset pair.
  • Experimental protocol: The implementations use a shared in-house Lloyd solver to reduce dependence on implementation-specific optimization routines.
  • Parameter selection: ϵ controls Q-k-means centroid stability versus quantization noise, while w controls DC-k-means subproblem size versus the number of subproblems.The appendix recommends ϵ=2^floor(−log10(n/(kd^3/2))−3) and w=n^0.3, each rounded to a power of two.
  • Evaluation metrics: Clustering quality is measured with silhouette coefficient and normalized mutual information, with silhouette computed on random 10,000-point subsamples.

D.3.1 Re-training During Deletion Stream for Q-k-means

The experiments examine how Q-k-means retraining, optimization loss, and amortized runtime vary with quantization granularity and tree width, alongside the broader deletion-efficiency/statistical-performance trade-off.

  • Re-training During Deletion Stream for Q-k-means: Higher effective dimensionality relative to sample size prevents Q-k-means centroids from stabilizing over extended deletion sequences.For MNIST, retraining follows a roughly constant slope across deletions.
  • Effects of Quantization Granularity and Tree Width on Optimization Loss: Q-k-means performance rapidly deteriorates as quantization granularity ϵ approaches 1 across all six datasets.The optimization loss is normalized to the k-means baseline in this comparison.
  • Effects of Quantization Granularity and Tree Width on Optimization Loss: DC-k-means shows a weaker relationship between tree width w and loss, generally decreasing in performance as width increases but not always monotonically.Variance across random seeds can dominate the impact of w for some datasets.
  • Effects of Quantization Granularity and Tree Width on Deletion Efficiency: Q-k-means amortized runtime on Covtype increases monotonically as ϵ approaches 0.The runtime sweep evaluates deletion efficiency as a function of quantization granularity.
  • Effects of Quantization Granularity and Tree Width on Deletion Efficiency: DC-k-means amortized runtime on Covtype is minimized at an optimal tree width of approximately 32–64 leaves.This comparison uses tree width as the varying parameter for deletion efficiency.
  • Deletion Efficiency vs. Statistical Performance: Deletion-efficient learning must balance efficient deletion operations against statistical performance.Complex processing can improve statistical learning while making deletion inefficient, whereas simpler structured processing supports efficient deletion but may reduce statistical performance.
Loading 1907.05012v2…