Certified Data Removal from Machine Learning Models

In plain words

Data owners can ask for their data to be removed from a system. A model trained on that data still carries traces of it, and retraining from scratch every time is slow. This paper asks whether a trained model can be changed so that it behaves as if the data had never been used, and it defines that in a strong sense: the changed model should look almost the same as one that never saw the data.

The method covers simple models whose training problem is convex, such as linear and logistic regression. Removing a point takes one Newton step, a cheap correction that moves the model close to the retrained one. That step leaves a small error, so during training the authors add a random linear term to the objective. The noise hides the error, and the strength of the guarantee follows from how much noise was added. Each removal adds to the error, so the model keeps a running budget and is retrained once the budget is spent.

The authors test this on linear models over fixed feature extractors. In their runs a single removal in the linear step takes under half a second.

TL;DR

• Removal-enabled training for L2-regularised convex linear models: a random linear term is added to the training loss §3.1, alg. 1.
• Removing a point is one Newton step, whose leftover gradient residual has a data-dependent bound §3.1, eq. (3) §3.2, cor. 1.
• The guarantee is (ε, δ)-certified removal; the Gaussian variant gives δ = 1.5·e^(−c²/2) §3.1, thm. 3.
• Residual bounds add up over removals, so the model is retrained once the budget σε/c is exceeded §3.2, alg. 2.
• Author-reported timing: removal takes 0.04 to 0.48 s on the linear tasks, against training times of 15.6 to 124 s; a removal from a linear layer on a DP extractor takes 0.27 s, against 1.5 h to train the CNN tab. 1.

Problem

Ideally, after a point x is removed, the output of the removal mechanism M should have nearly the same distribution as the output of training on the reduced dataset. Formally, for every set of models T, every dataset D and every x in D, the ratio of the two probabilities should lie between e^(−ε) and e^ε §2, eq. (1):

e^{-\epsilon} \le \frac{P\big(M(A(\mathcal{D}), \mathcal{D}, x) \in \mathcal{T}\big)} {P\big(A(\mathcal{D} \setminus x) \in \mathcal{T}\big)} \le e^{\epsilon} \qquad [\text{eq. } 1]

The relaxed (ε, δ) version adds δ to each side of the inequality §2. Retraining from scratch satisfies the definition exactly, but it costs a full training run §2. Making the parameters merely close to the retrained ones is not enough: the paper gives a linear example where an approximate removal leaves a clear trace of the removed row §2.

Differential privacy also implies this property, because the removal mechanism can be the identity §2, eq. (2). DP training, however, costs accuracy, so the paper treats removal as a point between full retraining and DP training §2.

Assumptions: the loss ℓ is convex and differentiable, with a bounded gradient, a Lipschitz second derivative and ‖x_i‖₂ ≤ 1 §3.1, thm. 1. The L2 term makes the objective strongly convex §3.1. Non-convex losses are not supported §6.

Method

Setting §3.1. The training set D has n rows (x_i, y_i) with x_i in R^d. The learner minimises the L2-regularised empirical risk. The minimiser w* is unique:

L(w; \mathcal{D}) = \sum_{i=1}^{n} \ell(w^\top x_i, y_i) + \frac{\lambda n}{2}\lVert w \rVert_2^2

Step 1: train with loss perturbation §3.1, alg. 1. Draw a random vector b with independent Gaussian coordinates and minimise L(w; D) + bᵀw. The paper uses the standard deviation σ as the perturbation scale fig. 1. The random term is what hides the removal residual later.

# Training a removal-enabled model  [alg. 1]
# Input: X (n, d) with ||x|| <= 1, labels y, lam > 0, sigma > 0
# Output: w (d,), and the perturbation b

def train_removal_enabled(X, y, lam, sigma):
    # Draw the random linear term; sigma is a std  [alg. 1, line 2] [fig. 1]
    b = normal(mean=0, std=sigma, size=d)           # (d,)
    # Minimise the regularised risk plus the linear term  [alg. 1, line 3] [§3.1]
    w = argmin_w(
        sum_i loss(w @ X[i], y[i])
        + lam * n / 2 * dot(w, w)
        + dot(b, w)
    )
    return w, b

Step 2: remove the last row with one Newton step §3.1, eq. (3). For the row (x_n, y_n), form the gradient Δ and the Hessian H of the loss on the reduced set D' = D \ (x_n, y_n), both at w*. The removed model is the Newton update:

w^- = M(w^*, \mathcal{D}, (x_n, y_n)) := w^* + H_{w^*}^{-1}\Delta, \qquad \Delta = \lambda w^* + \nabla \ell\big((w^*)^\top x_n, y_n\big) \qquad [\text{eq. } 3]

This is the influence-function update §3.1. Forming H costs O(d²n) and can be done at training time; only the O(d³) inversion is needed at removal time §3.1.

# One-step Newton removal of a single row  [§3.1, eq. 3]
# Input: w_star (d,), X_rest and y_rest (the reduced set), removed row (x, y)

def newton_remove(w_star, X_rest, y_rest, x, y, lam):
    # Gradient at the removed row, including the regulariser term  [§3.1]
    delta = lam * w_star + loss_grad(w_star, x, y)  # (d,)
    # Hessian of the regularised loss on the reduced set, at w_star  [§3.1]
    hessian = regularised_hessian(w_star, X_rest, y_rest, lam)  # (d, d)
    # One Newton step  [eq. 3]
    return w_star + solve(hessian, delta)

Step 3: bound the residual §3.1, thm. 1; §3.2, cor. 1. The gradient of the reduced objective at w⁻ is the residual. It is zero only at the exact minimiser. Theorem 1 bounds its norm with bounded gradients C and a γ-Lipschitz second derivative of ℓ:

\lVert \nabla L(w^-; \mathcal{D}') \rVert_2 = \lVert (H_{w_\eta} - H_{w^*}) H_{w^*}^{-1} \Delta \rVert_2 \le \gamma (n-1) \lVert H_{w^*}^{-1}\Delta \rVert_2^2 \le \frac{4\gamma C^2}{\lambda^2 (n-1)} \qquad [\text{eq. } 4; \text{thm. } 1]

where w_η lies on the segment between w* and w⁻. The data-dependent corollary is usually the one that matters in practice §3.2:

\lVert \nabla L(w^-; \mathcal{D}') \rVert_2 \le \gamma \lVert X^- \rVert_2 \, \lVert H_{w^*}^{-1}\Delta \rVert_2 \, \lVert X^- H_{w^*}^{-1}\Delta \rVert_2 \qquad [\text{cor. } 1]

Here X⁻ is the data matrix of D'. For logistic regression with ‖x_i‖ ≤ 1, the gradient norm is at most 1 and γ = 1/4 §3.2.

Step 4: hide the residual §3.1, thm. 2 and thm. 3. A small residual is not enough, because its direction can leak the removed row §3.1. The guarantee comes from the random term b. Theorem 2 says that if b's density changes by at most e^ε when b moves by ε', then the perturbed minimiser's density changes by at most e^ε. Theorem 3 combines this with the residual bound ε' §3.1:

• (i) If b has density proportional to exp(−(ε/ε')‖b‖₂), removal is ε-certified.
• (ii) If each coordinate of b is N(0, cε'/ε), removal is (ε, δ)-certified with δ = 1.5·e^(−c²/2).

The paper uses variant (ii) in its experiments, with c = √(2 log(1.5/δ)) in Algorithm 2 alg. 2. Variant (i) appears in the theorem but its sampling procedure is not used in the released code (see Paper vs code).

Step 5: repeated removals and batches §3.2, eq. (6), thm. 4, alg. 2. Removing one row at a time, the residual bound grows linearly with the number of removals, by induction on the number of removals §3.2. The paper therefore keeps a running total β. For a batch of m rows B, the update uses

w^{(-m)} = w^* + \big[H^{(m)}_{w^*}\big]^{-1}\Delta^{(m)}, \qquad \Delta^{(m)} = m\lambda w^* + \sum_{j \in B} \nabla\ell\big((w^*)^\top x_j, y_j\big) \qquad [\text{eq. } 6]

with H^(m) the Hessian of the loss on D \ B §3.2. Its residual bound is 4γm²C²/(λ²(n−m)) §3.2, thm. 4. Computing H once at the current solution makes the bound grow quadratically in the number of removals instead of linearly §3.2.

Step 6: budget and retraining §3.2, alg. 2. The budget is σε/c. When the accumulated bound β exceeds it, the model is retrained from scratch on the remaining rows with Algorithm 1 alg. 2, lines 16–17. Otherwise the Newton update is applied to w alg. 2, line 19.

# Removal of one batch with the residual budget  [alg. 2, lines 11-19]
# State: w (d,), X and y (rows still present), K = X^T X (d, d), beta
# Setup: c = sqrt(2 * log(1.5 / delta))  [alg. 2, line 7]
#        budget = sigma * eps / c        [alg. 2, line 16]
# gamma = 1/4 for logistic loss [§3.2]

def remove_batch(w, X, y, batch, K, beta, lam, gamma, budget):
    # Gradient of the batch at the current w, with the lam term  [line 11]
    delta_vec = len(batch) * lam * w + sum(
        loss_grad(w, X[i], y[i]) for i in batch
    )
    # Drop the batch rows from X, y and K = X^T X  [lines 13-14]
    removed = X[batch]                              # (m, d)
    X, y = remove_rows(X, y, batch)                 # (n - m, d)
    K = K - removed.T @ removed                     # (d, d)
    # Hessian over the remaining rows, with lam * (n - m) * I  [line 12]
    hessian = regularised_hessian(w, X, y, lam)     # (d, d)
    step = solve(hessian, delta_vec)                # H^{-1} Delta, (d,)
    # sqrt(||K||_2) = ||X||_2 for the remaining rows  [line 15]
    residual = sqrt(spectral_norm(K)) * norm(step) * norm(X @ step)
    beta = beta + gamma * residual
    # Residual budget exceeded: caller retrains with alg. 1  [lines 16-17]
    if beta > budget:
        return None
    # Otherwise apply the Newton update  [line 19]
    return w + step, X, y, K, beta

Gradient and Hessian for logistic regression

For labels y_i in {−1, +1} and loss ℓ(wᵀx, y) = −log σ(y wᵀx), the paper gives the gradient and Hessian in closed form §3.2:

\nabla \ell = \big(\sigma(y w^\top x) - 1\big)\, y\, x, \qquad \nabla^2 \ell = \sigma(y w^\top x)\big(1 - \sigma(y w^\top x)\big)\, x x^\top

The regularised Hessian of the reduced set is X⁻ᵀ D_w X⁻ + λ(n−1) I_d, with D_w diagonal and holding ℓ'' for each remaining row §3.2, cor. 1.

Least squares

For least squares the Hessian does not depend on w, so the residual is exactly zero and the Newton update is exact (ε = 0), without loss perturbation §3.2.

Optimiser

The paper uses L-BFGS to minimise the perturbed objective in Algorithm 1, as it was the fastest of the optimisers the authors tried §3.2, Pseudo-code.

Hyperparameters

Results

Author-reported. Setups are as stated in each row. Table 1 gives the timings; the rest come from the text and figures.

Other reported results: the data-dependent bound is several orders of magnitude below the worst-case bound, but still well above the true residual norm [§4.1, fig. 2]. Removing atypical training digits has a larger update norm than removing prototypical ones, so they consume more of the budget §4.1, fig. 3.

Paper vs code

The code is the repository the paper links §4, pinned to the commit in the frontmatter. It is licensed CC BY-NC 4.0 (non-commercial); this card paraphrases it and quotes none of it.

• SVHN extractor kernel. The paper's footnote says 3×3 filters §4.3, footnote. The code builds two conv layers with kernel size 5, ReLU and 2×2 pooling fast_grad_models.py, and sizes its classifier input as 5×5×64 train_svhn.py. The code uses 5×5.
• Extractor δ and data. The paper fixes δ = 1e-4 for the SVHN comparison §4.3. The README example trains a (0.1, 1e-5)-DP extractor README.md and extracts with δ = 1e-5 README.md. The code trains on SVHN train plus extra train_svhn.py; the paper says only "private data" §4.3.- Budget check is missing. Algorithm 2's retrain branch (lines 16–17) and the constant c are not in test_removal.py. The script accumulates the bound per removal and prints it, and it never compares it with σε/c or retrains test_removal.py.
• Hessian regulariser. Algorithm 2 line 12 writes H as a sum of loss Hessians with no λ term. Corollary 1 and the code include λ(n−m)I test_removal.py.
• Regulariser scale in Algorithm 1. Algorithm 1 writes λn‖w‖² with no ½, while §3.1 writes λn/2 alg. 1 §3.1. The code uses λ/2 on the mean-form loss, which is the same minimiser as λn/2 on the sum form test_removal.py test_removal.py.
• Hessian recomputed per removal. Each removal rebuilds X⁻ᵀDX over the remaining rows at the current approximate w, not at w* test_removal.py test_removal.py. Algorithm 2 line 12 also uses the current w, so the paper's algorithm and code agree on this. Equation (3) and Corollary 1 are written at w*. The §3.2 offline trick, which forms H at training time, covers only the first removal (derived by us).
• Gradient-bound constant. The code divides the bound by 4, which is γ = 1/4 test_removal.py test_removal.py. This matches §3.2.
• Spectral norm. The code estimates ‖X‖₂ with 20 power iterations from a random start on K = XᵀX test_removal.py. A power-iteration estimate can fall below the true norm, which would understate β (derived by us). The paper uses the exact spectral norm.
• Feature normalisation. The paper assumes ‖x_i‖ ≤ 1 but does not say how this is achieved. The code L2-normalises every feature vector utils.py. For MNIST, the code also subtracts 0.5 from each pixel utils.py utils.py. Neither step is stated in the paper.
• Negative-subsampling weights. The code weights each kept negative by one over the number of kept rows, so each one-vs-rest loss is a per-class mean test_removal.py test_removal.py. The paper says only that negatives are subsampled §4.2.
• Removal order. The code randomly permutes the training rows and removes them in that order test_removal.py. The paper does not say how the removed rows are chosen.
• Distribution for variant (i). The code samples only Gaussian perturbations test_removal.py test_removal.py. The ε-certified variant (i) with density proportional to exp(−(ε/ε')‖b‖) is not implemented.
• Example parameters. The README commands set λ and σ for one run each README.md README.md. These are not the paper's per-figure settings, which are only plotted fig. 1.
• Appendix errata. The appendix errata say the norm bound on Δ must be taken at the minimiser of the perturbed loss, which is random, so the bound holds only with high probability. The data-dependent bounds are unaffected app. Errata.

Pitfalls

• The noise must stay hidden. The guarantee treats b as unseen by whoever checks for removal. The paper does not say how b is stored or discarded §3.1.
• Budget and retraining. The number of supported removals is set by σ, ε and δ, and the paper's own plot shows that a larger σ costs accuracy fig. 1 §4.1. The budget is filled by the data-dependent bound of cor. 1, which is much tighter than the worst case but still has to be computed for every removal §4.1.
• Outliers cost more. Atypical rows have large ‖H⁻¹Δ‖, so removing them uses budget faster fig. 3 §4.1.
• The bound is loose. The data-dependent bound is still well above the true residual norm, so the number of supported removals is an estimate, not a measured limit fig. 2 §4.1.
• Mean versus sum form. The Hessian and Δ must use the same scale as the training objective. Mixing a mean-form loss with a sum-form Hessian gives a wrong Newton step, and the code keeps the forms consistent test_removal.py test_removal.py.
• Per-removal cost. Inversion is O(d³) per removal, and the code also rebuilds H each time at O(n·d²) test_removal.py. The paper's O(d²n) offline claim covers only the first removal (derived by us). The d³ term matters for large feature dimensions; MNIST pixels give d = 784 utils.py.
• Numerical conditioning. H includes λ(n−1)I, so a small λ or large n gives a poorly conditioned H. The code computes in float32 test_removal.py test_removal.py. The paper does not state the precision.
• Composition for DP extractors. Theorem 5 adds the extractor's ε_DP to the removal's ε_CR §3.3, thm. 5. The SVHN experiment removes rows only from the linear layer and treats the extractor as fixed §4.3.
• Unstated training details. Learning rates, epochs and clipping for the DP extractor are in the code, not the paper train_svhn.py train_svhn.py.
• Scope. Only convex losses are covered. Non-convex losses and models whose removal is not a convex update are unsupported §6.
• Costs the abstract hides. Retraining is still needed after the budget is spent, and the removal-enabled model is less accurate than a model that supports no removal (LSUN: 88.6% to 83.3%) §4.2.

Lineage

• Builds on: influence functions for the one-step update (keys cook1982residuals and koh2017understanding) §3.1; differential privacy (key dwork2011differential) §2; objective perturbation (key chaudhuri2011dperm) §3.1; DP-SGD (key abadi2016deep) for the private extractor §3.3.
• Related work named in the paper: decremental learning (keys cauwenberghs2000incremental, karasuyama2009multiple, tsai2014incremental), machine unlearning (key cao2015towards), k-means removal (key ginart2019making), and a concurrent exact-removal method with ε = 0 (key bourtoule2019machine) §5.
• Compared against: retraining from scratch and a fully DP-trained CNN §2 §4.3.
• Superseded by: not known from content in this wiki.