PaperlayerView exact revision on arXiv

Source-linked AI summary

Unrolling SGD: Understanding Factors Influencing Machine Unlearning

Anvith Thudi, Gabriel Deza, Varun Chandrasekaran, Nicolas Papernot

arXiv:2109.13398v2cs.LGcs.CR

TL;DR

Machine unlearning must remove a datapoint’s influence without incurring the cost of retraining, while existing approximate methods use heterogeneous criteria. This paper taxonomizes those criteria, analyzes SGD, and derives practical mechanisms centered on verification error. It reports strong correlations between unlearning error and verification error and proposes SD loss to reduce both with little performance impact.

  • Problem

    Approximate-unlearning approaches use varied metrics that are difficult to compare, while verification error requires expensive and noisy retraining-based computation.

  • Method

    The paper taxonomizes unlearning methods and metrics, Taylor-expands SGD, introduces single gradient unlearning and unlearning error, and proposes SD loss.

  • Results

    Unlearning error strongly correlates with verification error, including correlations of 0.91 on CIFAR-10 and 0.81 on CIFAR-100 for amnesiac machine learning.

  • Takeaways & Limitations

    The analysis provides a cheaper proxy for verification error and informs training models that can later be approximately unlearned with lower verification error.

  • Takeaways & Limitations

    The second-sum terms in the SGD expansion can remain computationally significant and bound how well the effect of x* can reasonably be forgotten.

Abstract

from arXiv · show

Machine unlearning is the process through which a deployed machine learning model is made to forget about some of its training data points. While naively retraining the model from scratch is an option, it is almost always associated with large computational overheads for deep learning models. Thus, several approaches to approximately unlearn have been proposed along with corresponding metrics that formalize what it means for a model to forget about a data point. In this work, we first taxonomize approaches and metrics of approximate unlearning. As a result, we identify verification error, i.e., the L2 difference between the weights of an approximately unlearned and a naively retrained model, as an approximate unlearning metric that should be optimized for as it subsumes a large class of other metrics. We theoretically analyze the canonical training algorithm, stochastic gradient descent (SGD), to surface the variables which are relevant to reducing the verification error of approximate unlearning for SGD. From this analysis, we first derive an easy-to-compute proxy for verification error (termed unlearning error). The analysis also informs the design of a new training objective penalty that limits the overall change in weights during SGD and as a result facilitates approximate unlearning with lower verification error. We validate our theoretical work through an empirical evaluation on learning with CIFAR-10, CIFAR-100, and IMDB sentiment analysis.

1. Introduction

Machine unlearning seeks to remove a training datapoint’s influence without the cost of retraining. This work unifies approximate-unlearning metrics around verification error, analyzes SGD, and derives practical mechanisms for reducing it.

  • Motivation: Machine unlearning removes a training datapoint’s impact to address privacy and right-to-be-forgotten scenarios.Models can memorize training data, increasing the possibility that private information is leaked.
  • Retraining and approximate unlearning: Retraining offers a strong unlearning guarantee but remains computationally expensive and requires changes to the training pipeline.Approximate methods modify an existing model more efficiently, but provide weaker guarantees about residual influence.
  • Metric choice: Verification error, the L2 weight difference between an approximately unlearned model and a naively retrained model, subsumes a large class of unlearning metrics.The metric helps compare otherwise disparate approximate-unlearning claims, although it requires a retrained model and is noisy.
  • SGD analysis: Taylor-expanding SGD yields single gradient unlearning, an inexpensive approximate method depending only on initial weights plus approximation-error terms.The analysis also exposes variables affecting verification error and motivates an easier-to-compute proxy called unlearning error.
  • Training for unlearning: The proposed SD loss reduces unlearning error and consequently verification error by limiting overall weight change during training.The paper reports that models trained with SD loss can be unlearned using single gradient unlearning, with little impact on performance.

2. Primer on Deep Learning & Notation

The paper frames supervised learning as iterative optimization of model weights with loss minimization. Mini-batch SGD updates weights using batches of data and a learning-rate hyperparameter.

  • Learning setup: The supervised-learning setup uses datapoint-label pairs and a parameterized model whose weights are learned or modified.Inputs belong to X, labels to Y, and the model maps inputs to outputs through weights w.
  • Unlearning context: Figure 1 organizes approximate-unlearning methods by their motivating definition of unlearning and their success metric.The taxonomy’s two dimensions are the horizontal definition axis and vertical measurement axis.
  • Learning objective: Training minimizes a loss function measuring prediction error, with cross-entropy identified as a standard choice for classification.The loss evaluates predictions against labels, including one-hot class vectors.
  • Optimization: Mini-batch SGD learns weights iteratively because non-convex models such as DNNs lack an analytically available closed-form solution.Each update uses the previous weights and a mini-batch of training data.

3. Taxonomy of Approximate Unlearning

Approximate unlearning spans different definitions, model spaces, metrics, and update mechanisms. The paper presents verification error as a unifying weight-space metric while contrasting its computational costs and the weaker guarantees of approximation.

  • Taxonomy: The taxonomy distinguishes unlearning criteria by whether they concern weights, outputs, or other operational notions of forgetting.The paper emphasizes that prior approaches use varied metrics, making claims difficult to compare directly.
  • Definitions: Unlearning can be formalized over distributions of model weights or input-output functions, and these choices produce different notions of success.The distributions HD, S, and HD′ represent models from original training, unlearning, and training without the target point.
  • Exact versus approximate unlearning: Naive retraining without x* exactly recovers the distribution for the reduced dataset, but its computational overhead motivates approximate alternatives.Approximate methods instead modify final weights, alter architecture, or filter outputs while relaxing exact equality to small distance.
  • Metrics: Verification error is the L2 distance between weights of a naively retrained model and an approximately unlearned model.The paper argues that this metric captures a large class of other unlearning metrics, subject to stated assumptions.
  • Metric limitations: Verification error is expensive and noisy because it requires retraining and can vary across runs due to randomness and numerical instability.KL-based metrics likewise require estimating the distribution of models trained without the target point.
  • Methods: Prior methods include output filtration, logged-update reversal, distributional scrubbing, and Hessian-based updates for different model or metric choices.These methods modify logits, weights, weight distributions, or final parameters depending on the approach.

4. Verification Error & Other Metrics

The paper motivates verification error as a weight-space metric that bounds a broad class of other unlearning metrics, while noting its computational cost and assumptions. It also finds no monotonic relationship between privacy risk score and verification error in the tested CIFAR setups.

  • A bound on verification error implies bounds on all Lp weight-space metrics for p ≥ 1, motivating it as a broad unlearning metric.
  • The analysis considers SGD distributions over final weights for datasets with and without x∗, using fixed initial weights and batch size 1.
  • Verification error measures the L2 distance between approximately unlearned and naively retrained model weights.
  • In CIFAR-10 and CIFAR-100 experiments, privacy risk score and verification error had correlations of -0.29 and -0.02, respectively.
  • The paper concludes that there is no monotonic relation between privacy risk score and verification error, while leaving constrained relationships for future study.

5. Defining the Unlearning Error

The paper expands SGD updates to separate an order-independent gradient contribution from a recursive, order-dependent Hessian contribution. This yields single-gradient unlearning and an inexpensive unlearning-error proxy whose tightness depends on training dynamics and loss curvature.

  • 5.1. Expanding SGD: Expanding SGD isolates terms that can be easily unlearned from recursive terms that depend on data order.
  • 5.1. Expanding SGD: The order-independent effect of x∗ is a gradient evaluated at the initial weights, which can be reversed by adding that gradient back to the final weights.The update is scaled by the learning rate, batch size, and number of epochs.
  • 5.2. Approximating the Second Sum Series: The recursive second sum contains Hessian-vector products and is expensive to compute because all terms involving x∗ must be accounted for.The analysis counts t − 1 such terms involving the datapoint.
  • 5.2. Approximating the Second Sum Series: The second-sum bound depends linearly on ||w_t − w_0||_2, the maximum Hessian singular value σ, and the number of updates t.The bound becomes tighter as the loss landscape becomes more linear, and vanishes when t = 1 or σ = 0.
  • 5.2. Approximating the Second Sum Series: Hessian-vector products are at least as expensive as gradients, and the unaddressed second sum therefore bounds how completely single-gradient unlearning can forget x∗.With batch size 1, the cost can equal training; generally it is approximately 1/b of training cost.
  • 5.2. Approximating the Second Sum Series: Unlearning error approximates the second-sum bound using the average Hessian singular value σ_avg rather than its maximum.Using the average can reduce computation by evaluating singular values only every few steps, and the quantity can be computed before unlearning.

6. Reducing the Unlearning Error

The analysis identifies training steps, singular values, and total weight change as drivers of unlearning error, then evaluates simpler training modifications and proposes standard deviation loss. Fewer steps reduce error but hurt accuracy, while SD loss targets smaller weight changes for easier unlearning.

  • Analysis-informed factors: Unlearning error depends on training steps, average singular value, and the final-versus-initial weight difference.These variables arise from the SGD analysis and motivate modifications to training rather than the unlearning procedure itself.
  • Strawman approaches: Training for fewer steps reduces unlearning error almost proportionally, but also degrades prediction accuracy.Figure 3 shows the increase is practically linear in the number of training steps.
  • Strawman approaches: ℓ2 regularization provides no consistent unlearning-error benefit and often increases the error.The experiments use λ ∈ {0.0, 0.001, 0.01, 0.1} with t = 7812 steps for the CIFAR-10 models.
  • Our Proposal: Standard Deviation Loss: Standard deviation loss moves the loss minimum closer to the initial weights, reducing the weight change required to reach it in the binary-classifier analysis.Increasing γ reduces the minimum change in weights needed to reach a loss minimum.
  • Our Proposal: Standard Deviation Loss: If standard deviation loss does not increase singular values, its smaller weight changes reduce unlearning error and support single-gradient unlearning.The loss is implemented by adding a regularization term to the training objective.

7. Implementation

The experiments use specified GPU, CPU, memory, operating-system, and software configurations, while evaluating the same datasets and models as earlier sections plus pretrained DistilBERT on IMDb reviews.

  • Hardware and software: Experiments ran on T4 Nvidia GPUs with 16 GB memory, Intel Xeon Silver 4110 CPUs, 32 GB RAM, and Ubuntu 18.04.2 LTS.The reported hardware and operating-system configuration is shared across the described experiments.
  • Hardware and software: The implementation used PyTorch 1.8.1, CUDA 10.2, and Python 3.7.
  • Evaluation settings: Evaluation reused the earlier datasets and models and added a text-domain evaluation with pretrained DistilBERT fine-tuned on IMDb reviews.

8. Evaluation

The evaluation tests whether SD loss reduces unlearning error, how training variables affect it, and whether unlearning error tracks verification error across models and datasets. Results show lower unlearning error and strong correlation with verification error, with limited accuracy cost and no consistent SD effect on PRS.

  • 8.1. SD Loss Decreases Unlearning Error: The SD loss minimum approaches a = b as regularization strength increases, motivating its effect on training dynamics.Figures 5 and 6 visualize this behavior through gradients and the loss landscape over the two outputs.
  • 8.1. SD Loss Decreases Unlearning Error: SD loss reduces unlearning error as regularization strength increases, while model accuracy declines with stronger regularization.The reported accuracy penalty is moderate in tested setups, while larger regularization values can produce larger drops.
  • 8.2. An Ablation Study: Unlearning error grows with training duration, and the reduction achieved by a fixed regularization strength diminishes as pretraining increases.The evaluation varies pretraining amount N and subsequent training steps t to examine this dependence.
  • 8.2. An Ablation Study: SD loss decreases unlearning error primarily by reducing the final weight change ||w_t − w_0||_2, while its effect on σ_avg is minimal.After initial oscillation, SD loss leaves σ_avg largely unchanged; the reduction in weight change strengthens with γ.
  • 8.3. Relationship Between Unlearning and Verification Error: Unlearning error is strongly linearly correlated with verification error across training stages, regularization strengths, architectures, and tasks.Reported Pearson coefficients include 0.934 across training steps, 0.96 and 0.81 for two CIFAR-10 vision models, and 0.998 for DistilBERT on IMDB.
  • 8.4. The Effect on PRS: Single gradient unlearning decreases baseline PRS by roughly 2×, but SD regularization has no consistent monotonic effect on PRS.The varying Spearman correlations can switch sign, despite SD regularization greatly decreasing verification error.

9. Discussion

The discussion examines how unlearning error behaves across methods, metrics, architectures, and regularization settings, while identifying open questions about when unlearning is sufficient and which models are easier to unlearn.

  • When is unlearning achieved?: The authors do not establish a universal threshold for sufficient unlearning, arguing that the criterion depends on the application and the user’s goal.Verification error and unlearning error provide reductions relative to a zero-regularization baseline but no absolute notion of enough.
  • Experimental constraints: The experiments impose SGD-focused restrictions, including constant learning rate, no data augmentation, and no momentum or ADAM.The authors note these restrictions are common in differential-privacy settings and may be relaxed in future work.
  • Unlearning error across methods: Unlearning error correlates strongly with verification error under amnesiac unlearning, with correlations of 0.91 on CIFAR-10 and 0.81 on CIFAR-100.The analysis varies batch sizes, training amounts, and regularization strengths across 104 settings.
  • Metrics and unlearning: Figure 13 shows inconsistent signs and magnitudes of PRS correlations before and after unlearning across all four SD-regularization settings.PRS represents membership-inference confidence in this experiment.
  • Architectures and domains: The paper leaves open whether model architecture or domain features make unlearning easier or harder, because SD-loss effects vary across ResNet-18, VGG-19, and DistilBERT.For DistilBERT, unlearning error drops substantially while accuracy declines less significantly.

10. Conclusion

The conclusion frames approximate unlearning around verification error, derives single-gradient unlearning and its proxy from an SGD analysis, and proposes SD loss to reduce the resulting error.

  • 10. Conclusion: The paper’s taxonomy identifies verification error as a metric that captures a large class of approximate-unlearning criteria under stated assumptions.Verification error compares approximately unlearned weights with weights from ideal retraining.
  • 10. Conclusion: A Taylor-series decomposition of SGD yields single-gradient unlearning and the unlearning error proxy, which avoids directly computing the retrained model.The proxy is presented as effective for the paper’s unlearning method.
  • 10. Conclusion: SD loss effectively decreases unlearning error and, in turn, the verification error associated with the proposed unlearning method.The regularizer is motivated by variables identified in the SGD analysis.

Availability

The paper provides code for the reported experiments in the cleverhans-lab/unrolling-sgd GitHub repository.

  • Availability: Experimental code is available at the cleverhans-lab/unrolling-sgd GitHub repository.The paper links directly to the repository.

1. Proofs

The proofs relate verification error to distributions of noisy weights, derive bounds under boundedness and Lipschitz assumptions, and connect the analysis to regularization experiments.

  • 1. Proofs: The proof uses equal Lipschitz constants for translated weight-noise distributions to relate shifts in distributions to the unlearning updates.The argument assumes each P_I is Lipschitz, as for Gaussian noise.
  • 1. Proofs: For SGD-based approximate unlearning, the analysis represents the unlearning update as u_I and the analytic verification error as v_I = u_I + d_I.Here d_I captures the difference associated with the ordering I, while v averages the corresponding norms.
  • 1. Proofs: The proof models verification error through differences between weight distributions after approximate unlearning and ideal retraining.The quantity v is described as an expectation difference under zero-mean noise.
  • 1. Proofs: Assuming bounded training-noise support and a uniform density-distance bound b, the analysis derives an upper bound on expected verification error.The bounded-support condition is represented by a finite integral a, while b bounds the density difference.
  • 1. Proofs: Reducing the maximum value of ||P(w)−P′(w)||2 yields a smaller bound on the expectation of verification error.This is the proof’s stated connection between distributional closeness and verification-error control.
  • 1. Proofs: The experimental section compares weight changes and singular values under different ℓ2-regularization strengths and reports unlearning error with test accuracy for ℓ2 and SD regularization.Tables 3 and 4 vary regularization strength and pretraining amount across four settings.
Loading 2109.13398v2…