--- kind: concept slug: influence-functions title: Influence functions summary: >- Influence functions estimate how a trained model changes when training rows change, using one Newton-style step instead of retraining. Two variants: certified removal of rows for L2-regularised convex models, with random loss perturbation (250x to 870x cheaper than retraining, author-reported); and closed-form replacement of features or labels, certified only for strongly convex losses. tags: [data-attribution, unlearning, data-poisoning] papers: ["1911.03030", "2108.11577"] related: [machine-unlearning, differential-privacy, differentially-private-sgd, data-poisoning] status: draft updated_at: 2026-11-01 --- ## 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 [arxiv:1911.03030 §3.1, eq. 3] [arxiv: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 [arxiv: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) [arxiv: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 [arxiv: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 [arxiv:2108.11577 §7.1, §7.2]. Its certificate covers the second-order update for strongly convex losses only [arxiv: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 [arxiv:1911.03030 §4.1]. Card: [Certified Data Removal from Machine Learning Models](/papers/1911.03030). 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 [arxiv: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² [arxiv: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 [arxiv: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 [arxiv: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 [arxiv: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 [arxiv: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 [arxiv: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 [arxiv:2108.11577 §1, §2, app. A.1]. Card: [Machine Unlearning of Features and Labels](/papers/2108.11577). ### 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 τ [arxiv: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 [arxiv:2108.11577 §5.1, §7.2]. For the CNN they give one value without a calibration procedure [arxiv:2108.11577 app. A.9]. The paper's summary of certified results covers only the second-order update [arxiv:2108.11577 §6]. ### Second-order replacement without a rate The same gradient difference is multiplied by the inverse Hessian at the trained parameters [arxiv:2108.11577 §5.2, eq. 8; app. A.2]. No rate is needed [arxiv:2108.11577 §5.2]. For large models the inverse is approximated with a truncated Neumann series over Hessian-vector products on mini-batches [arxiv:2108.11577 §5.2, app. A.3, alg. 1]. The guarantee does not hold for this approximation [arxiv: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 [arxiv:2108.11577 §6, thm. 1, thm. 3]. The noise can be norm-exponential for pure ε-certification, or Gaussian for (ε, δ) [arxiv:2108.11577 §6, thm. 3]. Repeated rounds add to the residual bound, and each round needs a new Hessian [arxiv:2108.11577 app. A.6, app. A.7.3]. ## When to use which | Situation | Use | Why | |---|---|---| | Model is a least-squares linear model, rows are removed | Exact removal | The residual is zero, so no noise is needed [arxiv:1911.03030 §3.2] | | Model is L2-regularised linear or logistic, convex loss, rows are removed rarely | Certified one-step removal | Removal is one Newton step, about 0.04 to 0.48 s on the paper's linear tasks against 15.6 to 124 s training [arxiv:1911.03030 tab. 1] | | Many row removals expected over the model's life | Batch removal with budget | The budget bounds how many removals run before a retrain is due [arxiv:1911.03030 alg. 2] | | One bad value, or wrong labels, spread over many rows, and the rows must not simply be deleted | Feature or label replacement | Replacing the values avoids deleting many rows, which costs about a retrain [arxiv:2108.11577 §1, §2] | | Need a guarantee for a convex, strongly convex model | Certified removal or second-order replacement | Both carry a certificate under strongly convex L2 assumptions [arxiv:1911.03030 §3.1, thm. 3] [arxiv:2108.11577 §6] | | Neural network, speed matters more than a guarantee | First-order replacement with an efficacy check | The paper reports it as the fastest option in its experiments, and gives no guarantee for neural networks [arxiv:2108.11577 §7, §8] | | Neural network, need to rely on the second-order step | Second-order replacement, with checks | On CIFAR-10 at 2500 poisoned labels it took 20.8 s against about 10 s for the first-order step [arxiv:2108.11577 §7.3, fig. 9]; the Hessian is approximated, so no guarantee holds [arxiv:2108.11577 §5.2] | | No rate can be calibrated against an efficacy measure | Second-order replacement | The second-order update needs no rate [arxiv:2108.11577 §5.2] | | Non-convex model, need a certificate | Not covered | Certified removal supports only convex losses [arxiv:1911.03030 §2, §6]; the replacement paper gives empirical checks only [arxiv:2108.11577 §8] | | Need the guarantee and accept a small accuracy loss | Certified removal | The paper's LSUN run drops from 88.6% to 83.3% with support for over 10,000 removals [arxiv:1911.03030 §4.2] | | Feature extractor must be private too | Differential privacy training | The paper compares against a fully DP CNN, which reached 22.7% on SVHN at ε ≈ 0.1, against 71.2% with the Newton update on the linear layer [arxiv:1911.03030 §4.3]. Different guarantee: see [differential privacy](/concepts/differential-privacy) | | Fidelity is high but the leak must be gone | Measure efficacy as well as fidelity | Fine-tuning kept fidelity high but left the canary exposed [arxiv:2108.11577 §7.2, tab. 3] | ## 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 [arxiv:1911.03030 §3.1, alg. 2]. ```pseudocode # 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 [arxiv: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 [arxiv: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 [arxiv:2108.11577 §5.1, §5.2]. ```pseudocode # 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) ``` ```pseudocode # 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 [arxiv:1911.03030 §3.1, thm. 3] [arxiv: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 [arxiv:2108.11577 §7.1, eq. 9]. Check the convention before calibrating noise. - **Experimental δ.** The removal paper uses δ = 1e-4 [arxiv:1911.03030 §4.1]. The replacement paper uses ε = 0.1 and δ = 0.01 for logistic regression [arxiv: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 [arxiv:2108.11577 §7.1] [arxiv: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 [arxiv:1911.03030 alg. 2] [arxiv:1911.03030 §3.2, cor. 1]. - Alg. 1 of the removal paper writes the regulariser as λn‖w‖², while §3.1 writes λn/2 [arxiv:1911.03030 alg. 1] [arxiv:1911.03030 §3.1]. - The removal paper's footnote gives 3×3 filters for the SVHN extractor; the code uses 5×5 [arxiv: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 [arxiv:2108.11577 alg. 1] [arxiv: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 [arxiv: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 [arxiv:2108.11577 tab. 5]. ## Papers - [Certified Data Removal from Machine Learning Models](/papers/1911.03030): 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](/papers/2108.11577): closed-form first- and second-order replacement of features or labels, with a certificate for the second-order update under strongly convex losses.