Making AI Forget You: Data Deletion in Machine Learning

In plain words

Sometimes an organisation must stop using one person's data, for example after the person withdraws consent under a data-protection law. If that data was used to train a model, the simple fix is to train again from scratch without it. For many models that is very expensive, so this paper asks whether the removal can be done much faster.

It studies a simple grouping method, k-means clustering, which places a fixed number of centres that summarise the points. The authors give two ways to drop one point cheaply. The first, Q-k-means, rounds each centre to a coarse grid with a random offset. Removing one point usually does not move a centre across a grid line, so the old centres can be kept and only the rare bad cases are retrained. The second, DC-k-means, splits the data into random groups, clusters each group, and then clusters the group centres. Removing a point only changes one group and the final step.

In the paper's experiments, each deletion is far faster than retraining, and the clustering quality is often close to the standard method, with some exceptions. The authors present this as a first step. They suggest the same ideas could apply to other models, but do not test that.

TL;DR

Two k-means variants support deleting one training point without retraining from scratch, which the paper calls deletion efficiency. Q-k-means quantizes its centroids and retrains only when a quantized centroid changes; DC-k-means recomputes one leaf and the root §4. Author-reported: amortized speedups of 2.2x to 584x over k-means++ retraining on six datasets, with loss ratios from 1.00 to 1.44 tab. 1 tab. 4. The mean speedup is about 226x for Q-k-means and about 30x for DC-k-means (computed here from tab. 4). The official code's deletion path has defects; see Paper vs code.

Problem

• Data deletion asks for a model that is distributed as if the point had never been used. Retraining on the remaining data is always a valid but costly answer §1 §3.
• The paper frames deletion as an online problem: a stream of m deletions on n points, with cost measured as amortized time. Any sequential learner needs Ω(n/m) amortized time, so the target is an algorithm that reaches this bound §3, Remark.
• The paper's motivation includes data-protection rules such as the GDPR and the Right to be Forgotten, and the risk that models trained on deleted data remain usable §1.
• The formal setting is exact deletion, average-case, with uniformly random deletion requests without replacement §3 app. A.1. Adversarial (robust) deletion is defined in the appendix, and the proposed algorithms are not claimed to satisfy it app. A.1. Approximate deletion is deferred to future work §3 app. A.2.
• Deterministic models already have fast deletion for some families, such as linear models, lazy learners and collaborative filtering §2. Stochastic learners such as k-means had no prior deletion-efficient method in the paper's survey §1 §2.

Method

The paper studies k-means, with the output centroids treated as the model whose points must be deletable §4. The baseline is k-means++ seeding followed by Lloyd iterations, and "retrain" means running that baseline on the reduced data §5. Both proposed methods are built on four design principles: linearity, laziness, modularity and quantization §3.1. Q-k-means uses quantization and DC-k-means uses modularity §4.

Q-k-means (quantized Lloyd iterations) §4.1 alg. 1 alg. 4.

1. Seed the centroids with k-means++ and record the seed points, because deleting a seed point is handled separately alg. 7 alg. 5.

2. Run up to T iterations. In each one, compute the cluster means from the current partition alg. 4.

3. Pull small clusters toward their previous centroid. A cluster counts as small if its size is below γn/k, with γ = 0.2 by default app. B.1 alg. 4. The code uses a convex average with weights size/M and 1 − size/M, where M = γn/k del_eff_kmeans.py.

4. Snap each centroid to a lattice of spacing ε with a fresh random phase θ drawn for each iteration app. B.1.2. The quantizer is

   Q(x) = \epsilon\big(\theta + \arg\min_{j \in \mathbb{Z}^d} \lVert x - \epsilon(\theta + j) \rVert_2\big)

   with θ uniform on [−1/2, 1/2]^d app. B.1.2.

5. Re-partition the points by the quantized centroids. Accept the step only if the loss drops; otherwise stop and keep the last accepted centroids alg. 4.

6. Save metadata for each step: the analog centroids, the phase, the quantized centroids and the cluster sizes. This adds O(ktd) memory §4.1 alg. 4.

# Q-k-means training  [alg. 4]
# Input:  data (n, d); k, T, gamma, eps
# Output: final centroids (k, d) and metadata for deletion

def train_q_kmeans(data, k, T, gamma, eps):
    # Seed the centroids with k-means++; remember the seed points  [alg. 7]
    centroids = kmeanspp_seeds(data, k)
    seed_indices = indices_of(centroids, data)
    # Partition by nearest centroid; the initial loss is the baseline  [alg. 4]
    partition = assign(data, centroids)
    loss = kmeans_loss(data, centroids, partition)
    for step in range(T):
        # Keep the previous centroids for the momentum correction  [alg. 4]
        previous = centroids
        # Average the points of each cluster  [alg. 4]
        centroids, sizes = cluster_means(data, partition)
        # Pull small clusters toward their previous centroid  [app. B.1]
        centroids = momentum(centroids, previous, sizes, gamma * n / k)
        # Snap centroids to a lattice with a new random phase  [app. B.1.2]
        phase = uniform(-0.5, 0.5, size=d)  # (d,)
        quantized = snap(centroids, eps, phase)
        # Save what the deletion check needs for this step  [alg. 4]
        save_step(step, centroids, phase, quantized, sizes)
        # Accept the step only if the loss drops, otherwise stop  [alg. 4]
        new_partition = assign(data, quantized)
        new_loss = kmeans_loss(data, quantized, new_partition)
        if new_loss >= loss:
            break
        centroids, partition, loss = quantized, new_partition, new_loss
    return centroids

Q-k-means deletion alg. 5 §4.1. The check decides, per deletion, whether the stored model is still valid. If not, the algorithm retrains from scratch.

1. If the deleted point is one of the initial k-means++ seeds, retrain alg. 5.
2. For each stored step, assign the point to its nearest analog centroid and form a perturbed centroid that removes the point from its cluster alg. 5.
3. If the perturbed centroid quantizes to a different lattice point than the stored one, retrain alg. 5.
4. Otherwise store the perturbed centroid and the reduced cluster size, and continue alg. 5.

# Deletion check for Q-k-means  [alg. 5]
# Returns True if the stored model stays valid without retraining

def can_delete(index, metadata):
    # A deleted initial seed always forces a retrain  [alg. 5]
    if index in seed_indices:
        return False
    # Only steps before the early stop are valid  [code: del_eff_kmeans.py#L258-L260]
    for step in accepted_steps(metadata):
        # Assign the point to its nearest analog centroid  [alg. 5]
        cluster = nearest(point, analog[step])
        centroid = analog[step][cluster]
        # Remove the point from its cluster mean, as written  [alg. 5]
        perturbed = centroid - point / sizes[step][cluster]
        # A changed quantized value means the stored model is stale  [alg. 5]
        new_quantized = snap(perturbed, eps, phases[step])
        if new_quantized != quantized[step][cluster]:
            return False
        # Store the perturbed state for later deletions  [alg. 5]
        update_step(step, cluster, perturbed)
    return True

DC-k-means (divide and conquer) §4.2 alg. 2 alg. 6. The paper's experiments use a depth-1 tree: w leaves, each solving for k centroids, then one merge step at the root whose input has size kn/w §4.2.

1. Assign each point to one of the w leaves uniformly at random alg. 2 §4.2.
2. On each leaf, run k-means++ followed by T Lloyd iterations, and keep the k centroids alg. 2.
3. Pool all leaf centroids and cluster them at the root with k-means++ and T iterations alg. 2.
4. Deletion: remove the point from its leaf, re-cluster that leaf, then re-cluster the root from all leaf centroids alg. 6.

# DC-k-means, depth-1 tree  [alg. 2] [§4.2]
# Input:  data (n, d); k, T, number of leaves w
# kmeans(points, k, T) = k-means++ seeding, then T Lloyd steps  [alg. 7]

def train_dc_kmeans(data, k, T, w):
    # Send each point to one of w leaves, uniformly at random  [alg. 2]
    leaf_of = [random_leaf(w) for _ in range(n)]
    leaves = [members_of(leaf_of, leaf) for leaf in range(w)]
    # Run k-means on each leaf  [alg. 2]
    leaf_centroids = [kmeans(data[members], k, T) for members in leaves]
    # Cluster the pooled leaf centroids at the root  [alg. 2]
    return kmeans(stack(leaf_centroids), k, T)

def delete_point(index):
    # Find the one leaf that held the point  [alg. 6]
    leaf = leaf_of[index]
    leaves[leaf].remove(index)
    # Recompute only that leaf's centroids  [alg. 6]
    leaf_centroids[leaf] = kmeans(data[leaves[leaf]], k, T)
    # Recompute the root from all leaf centroids  [alg. 6]
    return kmeans(stack(leaf_centroids), k, T)

Amortized analysis. The paper's deletion cost for Q-k-means is O(m² d^{5/2}/ε) in expectation for m deletions, and is independent of n for constant m and ε [Thm. 4.1] §4.1. Setting m = Θ(n^α) and ε = Θ(n^{−β}) gives amortized cost O(n^{1−α} + n^{α+β}) app. C. For DC-k-means with w = Θ(n^ρ), the expected time for m deletions is O(m · max{n^ρ, n^{1−ρ}} · d) [Prop. 4.2]. The paper's target is amortized time O(n^{1−α}) for α-deletion efficiency §4.3.

• Q-k-means is α-deletion efficient in expectation if α ≤ (1 − β)/2 [Cor. 4.2.1].
• DC-k-means is α-deletion efficient in expectation if α < 1 − max{1 − ρ, ρ} [Cor. 4.2.2].
• The paper's worst-case-over-datasets expected loss bound for Q-k-means is E L ≤ (8 ln k + 16) L* + ε√(nd(8 ln k + 16) L*) + ¼ nd ε² [Cor. 4.1.1] app. C.

Heuristics and parameter choices. The paper gives rules of thumb for ε and w, which it uses in the experiments app. D.1.2. It notes that tuning hyperparameters is itself a deletion problem, and suggests tuning on data unlikely to be deleted app. E.3.

Hyperparameters

Results

Author-reported. Setup: six datasets (above), k-means++ baseline with Lloyd iterations, 1,000 random deletions, five replicates, one CPU core §5 app. D.1. Tables 1–4 are reproduced from the paper. In Table 2 the paper lists "Gaussian" twice and omits MNIST; the row order matches Table 1, so the third row is probably MNIST, but the paper does not say so.

Loss ratio over k-means++ (lower is better) tab. 1:

Silhouette coefficient (higher is better) tab. 2, as printed:

Normalized mutual information (higher is better) tab. 3, as printed:

Amortized runtime in seconds for training once plus 1,000 deletions, divided by 1,000 tab. 4 app. D.1:

The abstract's "over 100×" average is true for Q-k-means only: the mean of its six speedups is about 226×, and the mean for DC-k-means is about 30× (both computed here from tab. 4). The paper's own text says the three methods are "competitive" in quality §5.2; the Celltype row, with a DC loss ratio of 1.44, is the largest gap.

Figures, described in words (not reproduced):

• fig. 1: amortized runtime against the number of deletions, for the three methods on six datasets §5.2.
• fig. 2: average number of retrains per deletion request for Q-k-means. On MNIST the count rises at a roughly constant slope, so quantization does not stabilise centroids for many deletions app. D.3.1.
• fig. 3: Q-k-means loss ratio against ε. Performance worsens quickly as ε approaches 1 app. D.3.2.
• fig. 4: DC-k-means loss ratio against tree width w. The trend is downward with width but not monotone, and seed variance can dominate app. D.3.2.
• fig. 5: Q-k-means amortized runtime on Covtype against ε. Runtime rises monotonically as ε → 0 app. D.3.3.
• fig. 6: DC-k-means amortized runtime on Covtype against w. The best width is about 32 to 64 leaves app. D.3.3.

Paper vs code

The official repository is https://github.com/tginart/deletion-efficient-kmeans, at commit 014d4c49f6037fe0c8a0d590b7021da07221b8f8, under the BSD-2-Clause license. The paper links it app. B. The repository contains one Python file, a README, a LICENSE file and a demo notebook. It does not contain the experiment scripts, the ε and w heuristics, or the datasets (the README links them externally). The points below come from reading the code. The deletion-path findings were not executed, because running Python was not approved in this session; each is marked "by reading."

• Seed check misses the first seed. Paper: deleting any initial k-means++ point forces a retrain alg. 5. Code: Kmeans._init_centroids records only the seeds drawn after the first one, so the first seed is missing from kpp_inits del_eff_kmeans.py. The deletion check uses kpp_inits del_eff_kmeans.py. By reading, deleting the first seed does not force a retrain. This matters, because the correctness argument needs the deleted points to avoid the initial centroids app. C, Lemma C.3.
• First iteration is always accepted. Paper: the loss of the initial partition is the reference, and a step is kept only if its loss is below it alg. 4. Code: minloss starts at infinity and is not set to the initial loss, so the first iteration is always saved del_eff_kmeans.py del_eff_kmeans.py.
• Momentum formula. Paper: the printed update c ← |π|c + (γn/k − |π|)c′ is not normalized alg. 4 app. B.1. Code: the weights are divided by M = γn/k, so the result is a true average del_eff_kmeans.py. The text says "averaged", which matches the code.
• Momentum threshold. The main text uses "≤ γn/k" §4.1, Algorithm 4 uses "<" alg. 4, and the appendix text applies the correction to clusters with size "≥ γn/k" app. B.1. The code uses "<" del_eff_kmeans.py del_eff_kmeans.py. Follow the code and Algorithm 4.
• Centroid removal is approximate. Paper: remove a point by c′ = c − p/|π| alg. 5. Code: the same formula del_eff_kmeans.py. A mean over |π| points gives (|π|c − p)/(|π| − 1) after removing p (my algebra from the definition of the mean in alg. 4). The two differ by about c/|π|. The paper does not say this form is approximate, and its proof (app. C) uses a different bookkeeping.
• Order of momentum and perturbation. Paper: perturb first, then apply the γ-correction if needed alg. 5. Code: apply the momentum correction to the analog centroid first, then perturb using the corrected size del_eff_kmeans.py.
• Point assignment during deletion. Both assign the deleted point to the nearest analog centroid of the same step alg. 5 del_eff_kmeans.py. But that step's centroid was averaged over a partition formed by the previous step's quantized centroids del_eff_kmeans.py del_eff_kmeans.py. The two partitions can differ. The paper does not discuss this.
• Metadata written at the wrong index (by reading). Deletion reads analog_c_meta[i+1] and clustersizes_record[i] del_eff_kmeans.py, but writes the perturbed state to analog_c_meta[i-1] and clustersizes_record[i-1] del_eff_kmeans.py. The paper saves the perturbed state at the same step alg. 5. For i = 0, the index −1 wraps to the last row. A later deletion would then read stale or wrong state.
• Certified deletions keep the row (by reading). A certified deletion zeroes the point and decrements n, but keeps the row in self.data del_eff_kmeans.py. _set_data derives n from the array shape del_eff_kmeans.py, and a later non-certified deletion calls np.delete and reruns on the whole array del_eff_kmeans.py del_eff_kmeans.py. The zeroed row can then re-enter a retrain as a phantom point at the origin.
• Early stop in deletion. Paper: Algorithm 5 loops over all T steps alg. 5. Code: it stops at the early-termination step and ignores later records del_eff_kmeans.py. The code is the correct reading, because the rejected step's records must not be used.
• DC deletion writes to the wrong layer (by reading). Training writes a child's centroids into self.data[l-1] del_eff_kmeans.py. Deletion writes them into self.data[l] del_eff_kmeans.py, the layer the leaf just read. The parent therefore never sees the new leaf centroids. Writes to indices below k·w also overwrite raw points at the leaf layer. The paper's Algorithm 6 updates the parent's dataset alg. 6.
• DC deletion index bug (by reading). self.valid_ids[del_idx] = self.valid_ids.pop() del_eff_kmeans.py pops before the assignment. For the last position the assignment then indexes past the end and raises IndexError. The demo draws positions uniformly [demo.ipynb cell 12], so this is rare but possible.
• Empty clusters (by reading, likely to fail). The mean divides by a zero count, which gives NaN for the empty cluster's row del_eff_kmeans.py. The k-means++ re-initialisation then computes selection probabilities over all centroids, including that NaN row del_eff_kmeans.py. The paper says empty clusters are re-initialised by k-means++ app. B.
• Child iteration count. The paper uses T for every node §4.2 alg. 2. Code: non-root nodes are hard-coded to 10 iterations, regardless of the constructor argument del_eff_kmeans.py.
• Quantizer convention. Paper: lattice points at ε(θ + j) with θ ∈ [−1/2, 1/2]^d app. B.1.2. Code: phase φ ∈ [0, 1), shifted by −1/2, rounded with np.round del_eff_kmeans.py del_eff_kmeans.py. The lattice is ε(j − θ) instead of ε(θ + j). Because θ is symmetric, the two are equal in distribution. np.round breaks ties to even.

Pitfalls

• Only the Q-k-means average beats 100x. The "over 100×" claim in the abstract matches the mean of Q-k-means' speedups (about 226×), not DC-k-means' (about 30×) tab. 4.
• Quality is not uniform. DC-k-means' Celltype loss ratio is 1.439 ± 0.157, and Q-k-means' Celltype ratio is 1.158 ± 0.099 tab. 1. The paper's "competitive" description §5.2 hides this. Q-k-means' NMI on Gaussian drops from 0.319 to 0.245 tab. 3.
• Results are not reproducible from the repository alone. The experiment scripts are not in the repository. The ε and w heuristics are described but not implemented, so the paper's numbers cannot be reproduced without writing them app. D.1.2 del_eff_kmeans.py.
• Timing depends on the implementation. The authors wrote their own Numpy Lloyd solver for all three methods to reduce implementation effects, but absolute times are hardware-specific app. D.1.1.
• The ε trade-off. Q-k-means' expected cost depends on ε: ε → 0 raises runtime fig. 5, while ε → 1 hurts loss fig. 3. The paper suggests ε shrinking with n for theory §4.1, but the experiments use fixed heuristics.
• Q-k-means in high dimension. The paper says its deletion time "may not scale well" in high dimension §4.1. MNIST (d = 784) gets 2.2x against k-means, and it needs retraining at a near-constant rate tab. 4 fig. 2.
• Adversarial deletions. Deleting initial centroids forces a retrain on every such request for Q-k-means, so an adaptive adversary can destroy its efficiency app. A.1. DC-k-means' correctness can be broken by deleting from chosen leaves app. A.1.
• Memory. Q-k-means stores O(ktd) extra state per run §4.1. DC-k-means' Algorithm 2 saves every node's dataset as metadata alg. 2, so memory grows with n·d. The paper does not state this memory cost.
• Asymptotic results depend on constant k, T and γ. The proofs treat k, T and γ as constants, and the Q-k-means bound is in expectation but worst case over dataset instances §4.1 app. C.
• Logarithm base. The main text writes "log k" in Corollary 4.1.1 §4.1, but the appendix uses the natural log app. C. Treat it as ln k.
• Corollary strictness. Cor. 4.2.1 is stated with "≤" in the main text, but its proof gives a strict inequality §4.3 app. C. Cor. 4.2.2 is strict in the main text, but "≤" in the appendix app. C. Use the strict forms.
• Typo in a proof. The second moment of the binomial is written as n(n−1)p + np; it should be n(n−1)p² + np, since E[B²] = Var + mean² app. C. The O(n^{1−ρ}) conclusion is unchanged.
• Stale cross-references. The appendix cites "Theorem 3.1" in the runtime proof, which is not defined there, and "Section 2" for the online lower bound, which is in Section 3 app. A app. C.
• Unstated details. The paper does not state the random seeds, the handling of ties in assignments, how k is chosen for each dataset, or the deletion count at which Tables 1–3 were measured. Appendix D says the statistical metrics were evaluated after 1, 10, 100 and 1,000 deletions app. D.1, but does not say which one the tables report.
• Scaling changes. Min–max scaling can change under deletions. The paper says retraining when an extremal point is deleted costs little in practice app. D.1.4.
• Silhouette sampling. Silhouette is computed on a random subsample of 10,000 points app. D.1.3, so small differences in tab. 2 may be sampling noise.

Lineage

• Builds on: Lloyd's algorithm with k-means++ seeding, the paper's baseline and the object of its deletion analysis §5 alg. 7.
• Related: quantized k-means of Schellekens et al. quantizes the data for memory or communication. The paper's Q-k-means quantizes the centroids to make deletion stable §4.1.
• Related: deletion-efficient linear models, lazy learners and collaborative filtering, from the paper's related-work survey §2.
• Compared against: retraining from scratch with k-means++ and Lloyd iterations §5.
• Superseded by: not stated.