Machine Unlearning of Features and Labels

In plain words

A trained model can absorb things it should not keep: a phone number it repeats back, a credit card number, a biased input, or wrong labels. The usual fix is to retrain from scratch, which is slow, and the training data may no longer exist. Deleting whole training rows is clumsy when the bad value sits in one column across thousands of rows.

The method here edits the model's weights directly. It computes a correction that acts as if the bad input values or labels had been swapped for good ones. A cheap first-order version uses gradients and needs a step size that is tuned against a measure of success. A second-order version uses curvature (the Hessian). For convex models such as logistic regression it comes with a mathematical guarantee of closeness to retraining. For neural networks there is no such guarantee, so the authors check the result with outside tests, such as whether a memorised number can still be extracted.

TL;DR

Retraining is the only exact fix, and per-row unlearning does not scale when sensitive content spans many rows §1, §2. The paper unlearns features and labels with closed-form updates derived from influence functions §4, §5. For strongly convex losses with L2 regularisation, the second-order update is certified in the (epsilon, delta) sense, using calibrated Gaussian or norm-exponential noise §6. On neural networks it is only checked empirically, and the first-order update is the fastest option in the reported experiments §7. All numbers are author-reported.

Problem

Instance-based unlearning removes data points. When one leaked value appears in many points, removing those points costs about as much as retraining, and removing them all lowers the model's accuracy §1, §2. The paper also argues that sharding-based unlearning loses its advantage quickly: with 20 shards, about 150 changed points are enough to affect every shard §2, app. A.1. The threat model covers leaks in deployed models: credit card numbers and names memorised by text-completion models, and labels that have to be corrected after the fact §3. The method assumes the data to be removed is already known; finding leaks is out of scope §8.

Method

The approach treats the change to the data as a perturbation. Each point z = (x, y) in the set of points to be corrected, P, is paired with a corrected version z~ in a set P~. The corrected model is the minimiser of the original regularised empirical risk, with the old points down-weighted and the new points up-weighted by a small epsilon §4.1, eq. 3, eq. 4. A closed-form update Delta(P, P~) approximates that minimiser from the original model [§4.1, eq. 5]. Setting P~ to empty recovers ordinary point removal §4.1.

Features and labels are handled by choosing the perturbations §4.2:

• Replacing features sets selected feature values of the affected points to new values, which may differ per point §4.2.
• Replacing labels sets new labels on the affected points §4.2.
• Revoking features removes a feature entirely. The paper shows that a model with a linear first layer gives the same result when the feature is set to zero and trained, or removed and trained §4.2, lem. 1. So the method first zeroes the feature, computes the update, and then deletes the corresponding input units §4.2.

Two update rules are derived §5:

• First-order: Delta = -tau * (sum of gradients of the new points - sum of gradients of the old points) §5.1, eq. 6. The rate tau must be calibrated against an efficacy measure. The authors use the exposure metric for this §5.1, §7.2.
• Second-order: Delta = -H^{-1} * (same gradient difference) [§5.2, eq. 8], where H is the Hessian of the regularised training loss at the trained parameters. Derivation is in app. A.2. No rate is needed §5.2.

For large models the inverse-Hessian-vector product is approximated with the truncated Neumann-series scheme of Agarwal et al., using Hessian-vector products computed on mini-batches §5.2, app. A.3, alg. 1. This weakens the guarantee §5.2.

# Revoke features  [§4.2, lem. 1]
# Input:  model, dataset D, feature set F
# Output: model with the inputs for F removed

def revoke_features(model, data, features):
    # Find the points where a revoked feature is non-zero  [§4.2]
    points = [(x, y) for (x, y) in data if any(x[f] != 0 for f in features)]
    # Corrected points: the same rows with those features set to zero  [§4.2]
    corrected = [(zero_features(x, features), y) for (x, y) in points]
    # Compute the closed-form update  [§4.2, eq. 5]
    update = second_order_update(model, points, corrected)
    # Apply it, then remove the matching input units  [§4.2]
    return drop_input_units(model + update, features)

# First-order update  [§5.1, eq. 6]
# Input:  parameters theta (p,), points P, corrected points C, rate tau
# Output: corrected parameters

def first_order_update(theta, points, corrected, tau):
    # Gradient sum over the corrected points  [§5.1]
    grad_corrected = sum(grad_loss(z, theta) for z in corrected)
    # Gradient sum over the original points  [§5.1]
    grad_points = sum(grad_loss(z, theta) for z in points)
    # Step against the gradient difference, scaled by tau  [§5.1, eq. 6]
    return theta - tau * (grad_corrected - grad_points)

# Second-order update  [§5.2, eq. 8; alg. 1]
# Input:  parameters theta (p,), points P, corrected points C
# Output: corrected parameters

def second_order_update(theta, points, corrected):
    # Gradient difference, the vector v  [§5.2, eq. 8]
    v = sum(grad_loss(z, theta) for z in corrected)
    v = v - sum(grad_loss(z, theta) for z in points)
    # Approximate H^{-1} v without forming H  [app. A.3, alg. 1]
    return theta - inverse_hessian_vector(theta, v)

# Approximate H^{-1} v with a damped recursion  [app. A.3, alg. 1]
# Input:  vector v (p,), training batches, damping, scale, iteration count
# Output: approximation of H^{-1} v

def inverse_hessian_vector(theta, v, batches, damping, scale):
    # Start the recursion from v  [app. A.3]
    estimate = v
    for batch in batches:
        # Hessian-vector product on one mini-batch  [app. A.3]
        product = hessian_vector_product(theta, batch, estimate)
        # One recursion step; the damping and scale come from the paper's
        # algorithm, see Pitfalls for the exact convention  [app. A.3]
        estimate = v + (1 - damping) * estimate - product / scale
    return estimate / scale

Certification for strongly convex losses adds noise to the training objective. The noise term is a random vector b drawn from a density chosen so that the corrected model and a retrained model are close in probability [§4, §6]. Under the assumptions in §6 the bound on the gradient residual is:

• first-order: about (1 + tau * gamma * n) * gamma_z * M * |P| §6, Thm. 1;
• second-order: about gamma'' * (M * gamma_z / lambda)^2 * n * |P|^2 §6, Thm. 1.

M is the sum of the magnitudes of the feature changes, and gamma, gamma_z, gamma'' are Lipschitz constants of the loss gradient and Hessian §6, Thm. 1. Theorem 3 converts such a residual bound into a privacy level: the noise has a norm-exponential density for pure epsilon-certification, or a Gaussian density for (epsilon, delta)-certification §6, Thm. 3. The Gaussian scale is written as sigma = beta * c / epsilon with c = sqrt(2 * log(1.5 / delta)) §7.1, eq. 9, where beta bounds the gradient residual §7.1.

Hyperparameters

Results

Author-reported. Setup: logistic regression on four datasets (spam, Android malware, diabetes, census) and a 3.3 million-parameter character LSTM, plus a 1.8 million-parameter CIFAR-10 CNN §7.

Datasets tab. 1: Enron 33716 points, 4902 features; Drebin 49226 points, 2081 features; Adult 48842 points, 81 features; Diabetes 768 points, 8 features.

Gradient residual fig. 4: the second-order update gives residuals about an order of magnitude lower than the other methods on Enron, Drebin and Diabetes. Fidelity by test-loss scatter fig. 5, fig. 11 is closest to the identity line for the second-order update.

Appendix runtime, gradients and time tab. 5: retraining needs 1.4e6, 1.1e4 and 5.1e6 gradient computations on Enron, Diabetes and Adult.

Paper vs code

The official repository is linked in the conclusion §9. Its owner is the first author, so it counts as official. The code is MIT-licensed in LICENSE, with the copyright placeholder left unfilled. Searches: none needed beyond the paper's link. The code was read at commit code_commit.

• Logistic regression regulariser. The sklearn wrapper uses C = 1 / (N * lambda), the solver's penalty is 0.5 * ||theta||^2, and so the paper's lambda in Sum l + lambda * Omega corresponds to N * lambda in the code LRUnlearner.py. The docstring in the same file states the penalty as theta.dot(theta), which does not match sklearn's 0.5 factor LRUnlearner.py. The DP logistic regression class instead uses the penalty 0.5 * lambda * ||theta||^2 directly, with no factor N DPLRUnlearner.py. The two classes use different lambda conventions.
• Sign and scale of the second-order step. The paper's Algorithm 1 returns the recursion value without dividing by scale and without the minus sign of eq. 8 alg. 1 §5.2, eq. 8. The code divides the estimate by scale DNNUnlearner.py and applies theta - tau * H^{-1} (g_corrected - g_points) DNNUnlearner.py. The code follows eq. 8, not the printed algorithm.
• Gradient sums. Eq. 8 uses per-point sums. The neural-network code computes the gradient difference from a Keras loss, which is a mean over each chunk, and sums the chunk results DNNUnlearner.py. The scale of the difference therefore depends on the chunk size, and the paper's tau values assume the code's scale, which is not stated.
• Restricted update in the CNN. The paper says only fully connected layers are updated §7.3. The code takes the last six trainable tensors in layer order: the 512-unit dense layer's kernel and bias, its batch-norm scale and offset, and the output layer's kernel and bias core.py core.py. Batch-norm parameters are included.
• CNN architecture and learning rate. The paper does not mention batch normalisation or dropout app. A.9. The code adds batch normalisation after each convolution and after the dense layer, and dropout of 0.1, 0.1 and 0.2 after the three pooling layers model.py. The builder defaults to learning rate 1e-3, and train.py does not pass another value model.py train.py. The paper states 1e-4.
• CNN unlearning settings. The shipped config matches the paper's second-order values: HVP batch 1024, damping 1e-4, scale 2e5, patience 20, first-order tau 2e-5 unlearn.json.
• LSTM regularisation and size. The architecture defaults to two layers of 512 units, Adam with learning rate 1e-4 RNNUnlearner.py. Every LSTM and output kernel also carries an L2 penalty, with default strength 0.01 RNNUnlearner.py. The paper does not mention a regulariser §7.2. The released checkpoints are named for strength 0.0001 LSTM.
• LSTM example values. The memorisation example notebook uses taus = [0.0003, 0.0009], scales = [39000, 36000], damping 0.1, and batch 500 for second-order Unlearn-Unintended-Memorization.ipynb. These are a demo, not the paper's values, which are not stated.
• Logistic regression demo. The certified-unlearning notebook uses lambda_ = 1.0 Certified-Unlearning-Logistic-Regression.ipynb. The paper does not state its lambda.
• Noise scale. The paper calls the noise parameter in eq. 9 a variance §7.1. The code passes it to np.random.normal as a standard deviation DPLRUnlearner.py. The gradient-residual helper computes beta = sigma * epsilon / c with delta = 1e-4 in one place and delta = 0.01 in another LRExperiments.py LRExperiments.py.

Pitfalls

• Certification assumptions. The guarantee needs a strongly convex, twice-differentiable loss with L2 regularisation, bounded inputs (||x_i|| <= 1), and Lipschitz gradients §6, Thm. 1. The paper does not say whether the numeric features of Adult and Diabetes, or the bag-of-words features, meet ||x_i|| <= 1. The code checks at run time whether rows are normalised LRUnlearner.py, which suggests the question matters.
• beta is sampled, not proven. The §7.1 budget uses a gradient-residual bound estimated from 100 sampled feature combinations §7.1. The certificate holds for that estimate, not for every possible removal.
• Variance or standard deviation. Eq. 9 and the theorem use a variance-like parameter, and the code uses a standard deviation. Check the convention before calibrating noise §6, Thm. 3 §7.1, eq. 9 DPLRUnlearner.py.
• Damping and scale interact. In the code's recursion the fixed point gives an inverse of H + scale * damping * I, not H + damping * I DNNUnlearner.py. The CNN values therefore correspond to a diagonal shift of about 20 (2e5 times 1e-4). This is derived from the code, not stated in the paper. Changing scale alone changes the effective damping.
• Algorithm 1 does not match the code. The printed recursion does not divide by scale and does not apply the minus sign alg. 1. Follow the code's convention, or check the result on a small model.
• First-order rate must be calibrated. The rate tau is only meaningful relative to the loss scale and the set of corrected points. The paper calibrates it with the exposure metric for the LSTM §5.1, §7.2. For the CNN it gives a single value without a calibration procedure app. A.9.
• Sharding comparison is a worst case. The sharding baseline retrains every shard that contains any affected point, and in the canary and poisoning experiments all shards are affected §7 baselines §7.2, §7.3. The result is a bound on this variant, not on sharding in general.
• Fine-tuning looks good but does not unlearn. Fine-tuning keeps fidelity high while leaving the canary exposed §7.2, tab. 3. Measure efficacy as well as fidelity.
• Repeated updates add up. The residual bound grows linearly with the number of update rounds app. A.6. Second-order updates need a new Hessian for each round, which multiplies the cost by the number of rounds app. A.7.3.
• Second-order cost. Explicit Hessian inversion costs O(n p^2 + p^3) and O(p^2) memory §5.2. For larger models the code approximates the inverse with Hessian-vector products. The guarantee does not hold for the approximation §5.2.
• Non-convex models have no guarantee. Neural networks are checked only with outside measures: the exposure metric for the LSTM and accuracy for the CNN §8.
• Runtime comparisons mix hardware. The LSTM second-order run used a CPU because CUDA lacked second-order RNN support at the time, while the others used a GPU §7.2. Runtime ratios across rows are not like-for-like.
• Runtime table units. In the appendix table, the Enron first-order entry reads 0.04 ms, but its speed-up of 38 is consistent with 0.04 s and the retraining time of 1.52 s tab. 5. Treat the unit as a probable typo.
• Speed-ups do not agree. The text and the Drebin table disagree on the speed-ups of fine-tuning and sharding, and neither matches the runtimes listed in the same table tab. 2 §7.1. The first-order ratio 6.82 s / 0.02 s is about 341, not 90. Report the runtimes, not the speed-up factors.
• Table 3 spread. The ± values in the canary exposure table have no defined meaning in the caption tab. 3. Do not interpret them as confidence intervals.
• Exposure values. The text says the first- and second-order exposures are below 0.001 §7.2, while the table shows 0 tab. 3.
• Missing for reproduction. The LSTM training recipe and the lambda for the logistic regression experiments are not stated §7.1, §7.2.
• Lemma 1 scope. Zeroing a feature and retraining is equivalent to removing it only for models whose first layer is a linear map of the input §4.2, lem. 1. Check the first layer before applying the revocation step.

Lineage

• Builds on: influence functions of Cook and Weisberg and of Koh and Liang §2; certified data removal of Guo et al. §6; the differential-privacy framework of Dwork and of Chaudhuri et al. §6, §7; the Hessian-vector scheme of Agarwal et al. §5.2; the exposure metric of Carlini et al. §7.2.
• Compared against: retraining, naive fine-tuning, differentially private learning and sharding (SISA, Bourtoule et al.) §7.
• Superseded by: not known from the sources used for this card.