Influence functions

Overview

A trained model depends on every row it saw. The question is how the model changes when some of those rows change, without a full retrain. Influence functions answer with a single Newton-style step from the trained weights, computed from the gradient of the affected rows and the Hessian of the loss 1911.03030 §3.1, eq. 3 2108.11577 §5.2, eq. 8.

The step generalises from removal to replacement. The affected rows are paired with corrected rows, and the update approximates the minimiser of the loss with the old rows down-weighted and the new rows up-weighted. Removal is the special case in which nothing replaces the old rows 2108.11577 §4.1, eq. 3–5.

The two papers aim at different targets. For removal, the invariant is indistinguishability: after the change, the output distribution should be almost the same as that of a model trained without the row, within a factor e^ε (and an additive δ in the relaxed form) 1911.03030 §2, eq. 1. The Newton step alone does not reach this: it leaves a residual gradient, and that residual can reveal the removed row 1911.03030 §2, §3.1. The replacement paper instead measures fidelity to a retrained model and efficacy, such as the exposure of a planted canary sequence 2108.11577 §7.1, §7.2. Its certificate covers the second-order update for strongly convex losses only 2108.11577 §6. The variants below differ in how they handle these issues.

Variants

Certified one-step removal with loss perturbation

The main removal variant. Training adds a random linear term b to the regularised risk, with independent Gaussian coordinates. Removing a row is then one Newton step, and the residual is hidden by b [arxiv:1911.03030 §3.1, alg. 1, thm. 3]. With per-coordinate standard deviation chosen as in the theorem, removal is (ε, δ)-certified; the paper's experiments use δ = 1e-4 1911.03030 §4.1. Card: Certified Data Removal from Machine Learning Models.

The residual bound uses a data-dependent quantity from the training data. For logistic loss with ‖x_i‖ ≤ 1 it is the gradient norm times the spectral norm of the data matrix and the Newton step, with γ = 1/4 [arxiv:1911.03030 §3.2, cor. 1]. The paper reports this bound is much tighter than the worst case but still well above the true residual 1911.03030 §4.1, fig. 2.

Batch removal with a residual budget

For m rows removed together, the paper computes one Newton step over the batch and a residual bound that grows with m² 1911.03030 §3.2, eq. 6, thm. 4. The bounds of successive removals add up in a running total β. When β exceeds the budget σε/c, the model is retrained from scratch on the rows that remain 1911.03030 alg. 2. The number of removals the model supports is set by σ, ε and δ, and the paper's sweeps show that a larger σ costs accuracy 1911.03030 fig. 1, §4.1.

Exact removal for least squares

For squared loss the Hessian does not depend on w, so the residual is zero and the Newton update is exact. The paper therefore needs no loss perturbation and gets ε = 0 1911.03030 §3.2.

Closed-form replacement of features or labels

Rather than deleting rows, this variant swaps the bad values for good ones. The selected feature values, or the labels, of the affected rows are replaced 2108.11577 §4.2. Replacement can set different values per point, and a whole feature can be revoked. For revocation the method zeroes the feature, applies the update, then deletes the matching input units. This equals training without the feature only when the first layer is linear in the input 2108.11577 §4.2, lem. 1. The paper's motivation is that deleting many rows to remove one value spread across them costs about as much as retraining, and sharding loses its advantage quickly 2108.11577 §1, §2, app. A.1. Card: Machine Unlearning of Features and Labels.

First-order replacement with a tuned rate

The cheap update takes one step against the difference between the gradient sum over the corrected rows and that over the original rows, scaled by a rate τ 2108.11577 §5.1, eq. 6. It needs no Hessian. The rate must be calibrated against an efficacy measure; the authors use the exposure metric for this 2108.11577 §5.1, §7.2. For the CNN they give one value without a calibration procedure 2108.11577 app. A.9. The paper's summary of certified results covers only the second-order update 2108.11577 §6.

Second-order replacement without a rate

The same gradient difference is multiplied by the inverse Hessian at the trained parameters 2108.11577 §5.2, eq. 8; app. A.2. No rate is needed 2108.11577 §5.2. For large models the inverse is approximated with a truncated Neumann series over Hessian-vector products on mini-batches 2108.11577 §5.2, app. A.3, alg. 1. The guarantee does not hold for this approximation 2108.11577 §5.2. For strongly convex, L2-regularised losses, the residual bound grows with the square of the number of replaced points and the noise is set from it 2108.11577 §6, thm. 1, thm. 3. The noise can be norm-exponential for pure ε-certification, or Gaussian for (ε, δ) 2108.11577 §6, thm. 3. Repeated rounds add to the residual bound, and each round needs a new Hessian 2108.11577 app. A.6, app. A.7.3.

When to use which

Implementation sketch

Common core of the certified removal variant. The Hessian in the paper's equations is taken at the minimiser w*; the released code rebuilds it at the current approximate w on every removal 1911.03030 §3.1, alg. 2.

# Training with a random linear term  [arxiv:1911.03030 alg. 1]
def train_removal_enabled(X, y, lam, sigma):
    # Draw the perturbation b with i.i.d. Gaussian coordinates  [alg. 1]
    b = normal(0, sigma, size=d)                    # (d,)
    # Minimise the regularised risk plus b^T w  [§3.1]
    w = argmin_w(sum_i loss(w @ X[i], y[i])
                 + lam * n / 2 * dot(w, w) + dot(b, w))
    return w

# Removal of a batch B with the residual budget  [arxiv:1911.03030 alg. 2]
def remove_batch(w, X, y, batch, beta, lam, gamma, budget):
    # Gradient of the batch at w, with the regulariser term  [alg. 2, line 11]
    delta_vec = len(batch) * lam * w + sum(
        loss_grad(w, X[i], y[i]) for i in batch
    )
    X, y = remove_rows(X, y, batch)                 # (n - m, d)
    # Hessian of the remaining rows, with lam * (n - m) * I  [§3.2, cor. 1]
    hessian = regularised_hessian(w, X, y, lam)     # (d, d)
    step = solve(hessian, delta_vec)                # Newton step  [eq. 6]
    # Data-dependent residual bound  [§3.2, cor. 1]
    residual = spectral_norm(X) * norm(step) * norm(X @ step)
    beta = beta + gamma * residual
    # Budget spent: retrain from scratch with train_removal_enabled  [alg. 2]
    if beta > budget:
        return None
    # Otherwise apply the update  [alg. 2, line 19]
    return w + step, X, y, beta

Where variants differ: the least-squares case skips train_removal_enabled's perturbation and the residual budget 1911.03030 §3.2. Any caller must keep the loss in the same mean or sum form as the training objective, because the Newton step is wrong otherwise 1911.03030 §3.1, alg. 1.

Replacement variants share the gradient difference. The first-order and second-order updates differ only in how that difference is scaled 2108.11577 §5.1, §5.2.

# First-order replacement of points P by corrected points C
# [arxiv:2108.11577 §5.1, eq. 6]
def first_order_replace(theta, P, C, tau):
    # Gradient sum over the corrected points  [§5.1, eq. 6]
    g_new = sum(grad_loss(z, theta) for z in C)
    # Gradient sum over the points being replaced  [§5.1, eq. 6]
    g_old = sum(grad_loss(z, theta) for z in P)
    # Step against the difference, scaled by the rate tau  [§5.1, eq. 6]
    return theta - tau * (g_new - g_old)

# Second-order replacement  [arxiv:2108.11577 §5.2, eq. 8]
def second_order_replace(theta, P, C, hvp_batches):
    # Gradient difference, the vector v  [§5.2, eq. 8]
    v = (sum(grad_loss(z, theta) for z in C)
         - sum(grad_loss(z, theta) for z in P))
    # Approximate H^{-1} v with Hessian-vector products; no rate  [app. A.3]
    step = inverse_hvp_approx(theta, v, hvp_batches)
    # Newton-style update  [§5.2, eq. 8]
    return theta - step

Contradictions

Between papers. Only the two cards above are involved.

• Noise convention. The removal paper says each coordinate of b is drawn from N(0, cε′/ε) and its figure caption calls σ a standard deviation 1911.03030 §3.1, thm. 3 1911.03030 fig. 1. The replacement paper writes σ = βc/ε and calls the same kind of parameter a variance, while its code passes it as a standard deviation 2108.11577 §7.1, eq. 9. Check the convention before calibrating noise.
• Experimental δ. The removal paper uses δ = 1e-4 1911.03030 §4.1. The replacement paper uses ε = 0.1 and δ = 0.01 for logistic regression 2108.11577 §7.1. These are choices, not conflicting results.
• Runtime reports. The replacement paper's text and its table give different speed-up factors for the same Drebin setting 2108.11577 §7.1 2108.11577 tab. 2. Compare the reported runtimes, not the factors.

Within the papers. Check the paper before implementing.

• The Hessian in alg. 2 line 12 of the removal paper has no λ term, while cor. 1 and the code include λ(n−m)I 1911.03030 alg. 2 1911.03030 §3.2, cor. 1.
• Alg. 1 of the removal paper writes the regulariser as λn‖w‖², while §3.1 writes λn/2 1911.03030 alg. 1 1911.03030 §3.1.
• The removal paper's footnote gives 3×3 filters for the SVHN extractor; the code uses 5×5 1911.03030 §4.3, footnote.
• The replacement paper's alg. 1 returns the recursion without dividing by the scale and without the minus sign of eq. 8. Its code divides by the scale and follows eq. 8 2108.11577 alg. 1 2108.11577 §5.2, eq. 8.
• The replacement paper's damping and scale interact in the recursion, so changing the scale alone changes the effective damping [arxiv:2108.11577 alg. 1]. Calibrate both on a small model first.
• The replacement paper's text says the first- and second-order exposures are below 0.001, while its table shows 0 2108.11577 §7.2, tab. 3.
• The replacement paper's appendix table gives a second-order speed-up of 0.3 on Enron, meaning that update was slower than retraining there 2108.11577 tab. 5.

Papers

• Certified Data Removal from Machine Learning Models: certified one-step removal for L2-regularised convex models, with loss perturbation, a residual budget, and timings against retraining.
• Machine Unlearning of Features and Labels: closed-form first- and second-order replacement of features or labels, with a certificate for the second-order update under strongly convex losses.