PaperlayerView exact revision on arXiv

Source-linked AI summary

Machine Unlearning of Features and Labels

Alexander Warnecke, Lukas Pirch, Christian Wressnegger, Konrad Rieck

arXiv:2108.11577v4cs.LGcs.CR

TL;DR

Existing unlearning methods do not scale well from individual data points to larger groups of features and labels. This paper uses influence functions to derive closed-form parameter updates for retrospective corrections, providing certification for strongly convex losses and faster empirical unlearning for non-convex models.

  • Problem

    Existing methods remove individual data points but are inefficient or reduce fidelity when privacy leaks affect many instances, features, or labels.

  • Method

    The paper reformulates influence estimation as unlearning and maps retrospective training-data changes to closed-form model-parameter updates.

  • Results

    For strongly convex losses, the method provides certified unlearning; for non-convex models, it achieves effective unlearning significantly faster than retraining and sharding with similar accuracy.

  • Takeaways & Limitations

    The approach can correct sensitive features, unintended language-model memorization, and poisoned labels while preserving model functionality in demonstrated scenarios.

  • Takeaways & Limitations

    Unlearning efficacy decreases as affected features and labels increase, and changing millions of data points exceeds the method’s capabilities.

Abstract

from arXiv · show

Removing information from a machine learning model is a non-trivial task that requires to partially revert the training process. This task is unavoidable when sensitive data, such as credit card numbers or passwords, accidentally enter the model and need to be removed afterwards. Recently, different concepts for machine unlearning have been proposed to address this problem. While these approaches are effective in removing individual data points, they do not scale to scenarios where larger groups of features and labels need to be reverted. In this paper, we propose the first method for unlearning features and labels. Our approach builds on the concept of influence functions and realizes unlearning through closed-form updates of model parameters. It enables to adapt the influence of training data on a learning model retrospectively, thereby correcting data leaks and privacy issues. For learning models with strongly convex loss functions, our method provides certified unlearning with theoretical guarantees. For models with non-convex losses, we empirically show that unlearning features and labels is effective and significantly faster than other strategies.

I. INTRODUCTION

Existing unlearning methods target isolated data points, but privacy leaks can span many instances or affect features and labels. The paper introduces closed-form feature- and label-level unlearning, with certification under convexity and empirical efficiency for non-convex models.

  • Existing methods partially reverse training to delete learned data points, helping mitigate privacy leaks and satisfy user removal requests.
  • Leaks distributed across many posts or messages make instance-based removal inefficient and can require substantial model changes.
  • Existing approaches lose runtime advantages and model fidelity when many affected points must be removed, motivating feature- and label-level corrections.
  • The paper proposes retrospective influence adjustment through closed-form parameter updates, enabling corrections across larger affected data regions.
  • Under convexity and continuity assumptions, two gradient-based strategies provide certified unlearning; for non-convex models, the approach is empirically faster than retraining and sharding.
  • The framework corrects individual features or labels directly, offering efficiency when privacy issues span multiple instances but remain localized to particular attributes.

IV. UNLEARNING WITH INFLUENCE

The method models training-data changes as perturbations and approximates their effect by updating the original optimum. This produces compact, efficiently computed parameter updates rather than solving training again.

  • The learning setup minimizes regularized empirical risk over a dataset, with an optional vector enabling noise for certified unlearning.
  • Perturbing one data point changes the optimum, but replacing it exactly is expensive and offers no advantage over resolving the original optimization.
  • Up-weighting corrected data and down-weighting original data lets the method revert training influence without explicitly removing points.
  • The framework generalizes to sets of original and corrected points, representing larger training-data changes through a closed-form parameter update.
  • The update has the model’s dimension, is sparse, and affects only necessary weights.
  • First- and second-order derivatives compute the update; setting the corrected set empty also yields data-point removal updates.

B. Unlearning Features and Labels

The framework represents feature and label corrections as perturbations, including replacement or revocation of features. It supports fine-grained updates, while certification and some revocation steps depend on model and loss assumptions.

  • Replacing features: Feature replacement overwrites sensitive values with alternatives, including individually selected values for fine-grained corrections.
  • Replacing labels: Label replacement addresses unwanted information in targets, including language-model labels, and can be combined with feature replacement in one update.
  • Revoking features: Feature revocation removes inputs from a model, reducing its input dimension and making direct model updates more difficult than ordinary correction.
  • Revoking features: For models using linear transformations, removing features is equivalent to setting them to zero during retraining, under the stated model class.
  • Revoking features: The revocation procedure zeroes affected feature values, computes an update, and then removes corresponding model inputs such as neural-network input neurons.
  • The first-order update applies to differentiable losses, whereas the second-order update requires an invertible Hessian matrix.

A. First-Order Update

The paper develops first- and second-order parameter updates for retrospectively unlearning changed data. The first-order update uses gradient differences, while the second-order variant removes the need to calibrate an unlearning rate but requires an inverse Hessian.

  • First-order update: The first-order update computes a parameter change from gradients on original and perturbed data, with step size controlled by the unlearning rate τ.It moves the model toward the gradient difference between original and perturbed data.
  • First-order update: The first-order update has gradient-computation cost O(p), where p is the number of model parameters.Its unlearning rate must be calibrated to ensure complete data replacement, for example using exposure.
  • Second-order update: Under twice differentiable, strictly convex loss, influence estimates yield closed-form updates that extend linearly from one data point to multiple points.The second-order update derives parameter weighting from the inverse Hessian and therefore needs no parameter calibration.
  • Second-order update: The second-order update is preferred for strongly convex, twice differentiable losses, but constructing an inverse Hessian is difficult for large models.Forming and inverting the Hessian requires O(np^2 + p^3) time and O(p^2) space.
  • Second-order update: For deep neural networks, an approximate inverse Hessian enables unlearning from large models, although the approximation weakens theoretical guarantees.The approach is presented as a practical alternative when explicit Hessian storage is infeasible.

A. Certified Unlearning of Features and Labels

The paper establishes certified feature and label unlearning for strongly convex models by bounding the difference between unlearning and retraining. Noise calibration converts gradient-residual bounds into (ε, δ)-certified guarantees.

  • Assumptions: The theoretical guarantees assume a twice differentiable, strictly convex loss and L2 regularization; logistic regression and support vector machines satisfy these assumptions.Strict convexity ensures the inverse Hessian exists and the optimum is unique.
  • Residual-based analysis: The gradient residual norm measures how far an unlearned model is from the unique model obtained by retraining on corrected data.For strongly convex losses, the residual is zero exactly at the retrained optimum.
  • Residual-based analysis: Theorem 1 bounds gradient residuals for first- and second-order updates under bounded inputs and Lipschitz gradient assumptions.The bounds depend on affected-feature magnitudes and are used to calibrate certified unlearning.
  • Certification: The certification argument compares the output distribution of unlearning with the distribution obtained by retraining on corrected data.Theorem 2 links bounded gradient residuals and noise-density conditions to max-divergence guarantees.
  • Certification: Theorem 3 provides certified unlearning guarantees by selecting the noise distribution for the update vector according to the residual bound and privacy budget.A Gaussian choice yields (ε, δ)-certification with δ = 1.5e−c^2/2.

VII. EMPIRICAL ANALYSIS

The empirical analysis evaluates unlearning across sensitive features, unintended memorization, and data poisoning, comparing efficacy, fidelity, and efficiency against several baselines. In the sensitive-feature experiments, the second-order update offers the strongest overall trade-off, while privacy noise limits fidelity as more features are affected.

  • Experimental setup: The experiments compare retraining, fine-tuning, differential privacy, sharding, and the proposed updates using efficacy, fidelity, and efficiency measures.The scenarios cover linear-model feature removal, language-model memorization, and label-poisoning correction.
  • Evaluation criteria: Efficacy is assessed with gradient residuals, which increase as more features are removed or replaced and indicate greater divergence from retraining.Exposure is also identified as a measure for memorization in language models.
  • Sensitive features: The second-order update has gradient residual norms an order of magnitude lower on the Spam, Malware, and Diabetis datasets than competing methods.It significantly outperforms the other methods in this scenario.
  • Sensitive features: Accuracy decreases as more features are affected because certified unlearning increases noise on model weights, with stronger fidelity decline on high-dimensional data.The experiments use ε = 0.1 and δ = 0.01, a strict privacy budget that limits how many features can be adapted.
  • Sensitive features: The second-order update remains close to retraining when up to 60 features are changed, whereas most other methods lose accuracy with 20 or fewer features.Sharding is nearly identical to retraining on low-dimensional datasets but unstable on high-dimensional ones.
  • Sensitive features: 90× is the first-order update’s speed-up over retraining, compared with 4× for the second-order update, 6× for sharding, and 2× for fine-tuning.The first-order update considers only corrected points rather than the entire dataset.
  • Sensitive features: The sensitive-feature takeaway is that convex-loss models support theoretically guaranteed removal or replacement, with the second-order update balancing efficacy, fidelity, and efficiency.This conclusion is specific to the certified unlearning setting described in the experiments.

B. Unlearning Unintended Memorization

The study evaluates feature-and-label unlearning for unintended memorization in a character-level language model containing inserted telephone numbers. It measures removal efficacy, model fidelity, and runtime against retraining and other unlearning strategies.

  • Experimental setup: The experiment inserts telephone-number canaries of lengths 5, 10, 15, and 20 into an LSTM trained on Alice in Wonderland.The model uses character-level training, 64-dimensional embeddings, two 512-unit LSTM layers, and 3.3 million parameters.
  • Evaluation criteria: Because the language-model loss is non-convex, the study evaluates unlearning with exposure rather than certified guarantees or direct retraining comparison.Exposure relates a sequence’s model rank to all possible sequences of the same length.
  • Unlearning efficacy: The inserted telephone number is an outlier in the perplexity distribution, while replacement strings move it toward the distribution center after unlearning.Figure 7 reports log-perplexity for three replacement sequences.
  • Unlearning efficacy: Exposure values below 0.001 from both first-order and second-order updates make extraction impossible across all tested sequence lengths.Retraining and SISA also reach zero exposure, whereas fine-tuning leaves substantial exposure and varies with training-data order.
  • Unlearning efficacy: Replacement choice affects unlearning: all tested substitutions impede extraction, with exposure values ranging from 0.01 to 0.3.The experiments select the replacement with the lowest exposure.
  • Fidelity: The corrected model does not overfit to replacement strings, instead producing language-structured completions reflecting the novel’s wording.This behavior is reported for second-order updates with replacement strings of different lengths.
  • Fidelity: For small changes, most methods approach retraining accuracy, while larger changes reduce the accuracy of both proposed updates.The second-order update performs slightly better because its Hessian incorporates information about unchanged samples; fine-tuning preserves fidelity but fails to remove injected sequences.
  • Efficiency: The first-order method is fastest, providing a speed-up of three orders of magnitude over retraining; the second-order method is 28 times faster.The first-order update offers the best overall performance when correcting fewer than 1,000 points, balancing efficacy, fidelity, and efficiency.

C. Unlearning Poisoning Samples

The paper evaluates unlearning methods for poisoned labels in computer vision, comparing accuracy restoration, runtime, scalability, and practical limitations. First-order updates and fine-tuning offer the strongest efficiency–fidelity trade-off, while effectiveness declines as poisoning grows.

  • Experimental setup: A CIFAR10 convolutional network reached 87% clean accuracy, but label poisoning caused an average 10% accuracy drop.The model contained 1.8 million parameters and used three VGG blocks plus two dense layers.
  • Accuracy: First-order and second-order updates, together with fine-tuning, came close to original performance after 2,500 poisoned labels, but no method fully removed the attack effect.Performance continuously declined as the number of poisoned labels increased.
  • Accuracy: At 10,000 poisoned labels, none of the methods sufficiently restored accuracy; sharding was unaffected by poison count but achieved the lowest performance.Sharding retrains all shards with corrected labels, explaining its robustness to the number of poisoned labels.
  • Efficiency: Approximately 10 seconds for first-order updates and fine-tuning versus over 15 minutes for retraining made them the most efficient strategies.The second-order update took 20.8 seconds, while sharding offered no advantage over retraining.
  • Scalability: Scaling model parameters from 1.8 million to 42 million preserved roughly constant accuracy while runtime increased with an almost linear slope.A slight runtime peak appeared near hardware limits.
  • Limitations: Unlearning remains effective for hundreds of sensitive features and thousands of labels, but correcting millions of affected data points exceeds the method’s capabilities.Certified guarantees apply only to strongly convex losses; neural-network updates require an additional measure to validate success.

APPENDIX

The appendix analyzes why sharding becomes inefficient as affected samples accumulate and derives first- and second-order parameter updates for retrospective corrections.

  • A. Stochastic Analysis of Sharding: Sharding assigns data across separate models, but affected samples can force retraining many or all shards.The analysis studies the probability that affected samples reach every shard, producing the worst-case need to retrain all shards.
  • A. Stochastic Analysis of Sharding: The inclusion-exclusion principle corrects overlaps among combinations of unaffected shards when calculating the sharding probability.Directly summing terms would double-count configurations sharing unaffected shards.
  • A. Stochastic Analysis of Sharding: The probability that all shards are affected quickly approaches one even for small numbers of samples, independently of dataset size.This makes sharding inefficient when many unlearning requests occur.
  • First-order update: The first-order update uses a Taylor approximation of the corrected loss around the original optimum and moves along the gradient difference between modified and original data.The step size is controlled by a small constant τ, and gradient linearity extends the derivation to multiple affected points.
  • Second-order update: The second-order update assumes a twice-differentiable, strictly convex loss and uses the inverse Hessian to account for curvature.Replacing a data point completely corresponds to setting ϵ = 1 in the update formulation.

C. Calculating Updates Efficiently

The method approximates inverse-Hessian vector products without explicitly storing the Hessian, using iterative Hessian-vector computations, damping, batching, and averaging.

  • C. Calculating Updates Efficiently: Hessian-vector products compute H^-1v without explicitly storing H or H^-1.The approach evaluates Hv efficiently and uses these products to obtain the inverse-Hessian vector product needed for second-order updates.
  • C. Calculating Updates Efficiently: A truncated Taylor expansion approximates H^-1 when the absolute values of all Hessian eigenvalues are below one.A damping term is added to the diagonal and the loss is rescaled to ensure convergence without changing the optimal parameters.
  • C. Calculating Updates Efficiently: Each iteration estimates the Hessian from a sampled data point, while Hessian-vector products evaluate the required operations in O(p) time.This avoids explicitly forming the Hessian during the iterative approximation.
  • C. Calculating Updates Efficiently: Averaging data batches and multiple runs improves convergence and reduces the variance of the inverse-Hessian approximation.The algorithm exposes batch size, iterations, damping, scaling, and repetitions as update parameters.

D. Proofs for Certified Unlearning

The appendix proves bounds for first- and second-order update residuals and establishes certified unlearning guarantees under stated smoothness, boundedness, and noise assumptions.

  • D. Proofs for Certified Unlearning: The proofs analyze first- and second-order updates through bounds on the gradient residual after unlearning.The derivation splits the affected and remaining data and treats the two update strategies separately.
  • Assumptions: The update bounds require assumptions including bounded data points and Lipschitz gradients with respect to features or parameters.These assumptions define the smoothness and boundedness conditions used in the theorem and supporting lemmas.
  • First-order update: The first-order bound relies on Taylor’s theorem and γ-Lipschitz continuity of the gradient.The resulting bound is obtained after controlling the Hessian norm in the Taylor remainder.
  • Second-order update: The second-order bound compares Hessian changes under feature modifications and assumes Lipschitz continuity of the relevant derivatives.The proof combines gradient and Hessian bounds to obtain the theoretical second-order residual bound.
  • Certified unlearning theorem: The certified-unlearning theorem assumes a unique minimum and a sufficiently small gradient residual for the unlearned model.Under these conditions, specified noise distributions yield certified guarantees, including an (ϵ, δ) guarantee in the Gaussian case.

E. Relation to Differential Privacy

The paper relates certified unlearning to differential privacy: differential privacy is sufficient for certification, while the proposed updates aim to retain performance closer to retraining.

  • E. Relation to Differential Privacy: The differential-privacy definition compares algorithm outputs on equal-sized datasets differing by one replaced sample.The guarantee is expressed over measurable subsets of the model-parameter space.
  • E. Relation to Differential Privacy: Differential privacy is sufficient for certified unlearning because indistinguishable outputs make later removal unnecessary.The paper obtains the same bound by using the identity function as the unlearning method.
  • E. Relation to Differential Privacy: Strong privacy guarantees may reduce model performance, motivating a compromise between differential privacy and the performance of costly retraining.The paper states that its update strategies produce models closer in performance to retraining than differential privacy alone.

F. Multiple Unlearning Steps

The method can apply unlearning either in one shot or through sequential updates. Sequential updates increase computational cost but reduce residual error, while certification bounds grow linearly with the number of updates.

  • Sequential update strategy: Splitting affected data into T subsets enables T consecutive updates instead of one-shot unlearning.The one-shot error rises with the number of affected points and total perturbation.
  • Computational cost: Sequential updates require recalculating intermediate quantities, increasing computational effort compared with one-shot updating.The empirical comparison is reported in Appendix G3.
  • Certification: Sequential certification retains a gradient residual bound below TC, where C bounds a single update.The bound follows by applying the single-step guarantee at each update and using the triangle inequality.
  • Certification: Applying the update repeatedly causes the gradient residual bound to rise linearly with the number of applications.This behavior is consistent with composition results for differential privacy.

G. Evaluation of Certified Unlearning

The evaluation examines fidelity, efficiency, sequential updating, and feature unlearning for linear and neural models. The results show close agreement with retraining, substantial efficiency gains in some settings, and small accuracy changes when many features are removed.

  • Fidelity evaluation: The second-order update has the highest correlation with retraining, with points closest to the identity line and less variance on Adult and Spam.The identity line represents perfect unlearning in the test-loss comparison.
  • Efficiency evaluation: The inverse-Hessian computation is faster than retraining on the Diabetis and Adult datasets for removing or replacing 100 feature combinations.These results make the second-order update particularly efficient in those cases.
  • Sequential unlearning steps: Sequential updates slightly improve accuracy while strongly decreasing gradient residuals, especially on the Diabetis and Adult datasets.The comparison covers one-shot and sequential first- and second-order updates.
  • Certification scope: The neural-network evaluation omits theoretical certification because its loss is non-convex, using accuracy as a rough performance reference instead.Noise is dropped from the neural-network experiment, whereas certified unlearning is available for the strongly convex logistic-regression setting.
  • Neural networks and linear models: Both neural networks and logistic regression unlearn 120 features with accuracy drops below 1 percentage point across all datasets.The reported result applies to both first-order and second-order updates.
  • Neural networks and linear models: Neural networks exceed logistic-regression accuracy by less than 5%, and by less than 1% on Spam, Malware, and Adult.The paper describes the two models as achieving comparable accuracy in this unlearning scenario.
Loading 2108.11577v4…