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 seeks to remove a training point’s impact from a model, and approximate approaches offer an alternative to retraining from scratch. This paper analyzes SGD to derive an unlearning-error proxy and propose SD loss; it reports that the proxy correlates strongly with verification error and that SD loss reduces unlearning error.

  • Problem

    Machine unlearning seeks to remove a training datapoint’s impact, motivated in part by privacy leakage and users revoking access to their data.

    Source: §1 · p. 1

  • Method

    The paper taxonomizes approximate-unlearning approaches and metrics, analyzes SGD, derives an inexpensive unlearning-error proxy, and proposes SD loss to limit weight changes.

    Source: §1 · p. 2

  • Results

    Unlearning error is strongly correlated with verification error in relevant contexts, while SD loss decreases unlearning error and thus verification error with little impact to performance.

    Source: §1 · p. 2

  • Takeaways & Limitations

    Models trained with SD loss can have a point unlearned using single-gradient unlearning.

    Source: §1 · p. 2

    Hessian-vector products can remain computationally expensive in practice, limiting how well the effect of a point can be forgotten.

    Source: §5.2 · p. 7

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

The paper identifies verification error as a unifying metric for approximate unlearning and analyzes SGD to develop a cheaper proxy and a training loss intended to reduce it. It also introduces single gradient unlearning and evaluates the approach on CIFAR-10, CIFAR-100, and IMDb sentiment classification.

1. Introduction

  • Unlearning addresses privacy risks from models memorizing training data, including cases where a data owner later revokes access.The GDPR’s right-to-be-forgotten is one motivation for such requests.Source: §1 · p. 1
  • Retraining removes a point before training anew but remains expensive, while approximate unlearning modifies an existing model more efficiently at the cost of weaker guarantees.Retraining can support transparent right-to-be-forgotten requests; approximate methods include gradient-ascent and Hessian-based updates.Source: §1 · p. 1
  • Verification error, the ℓ2 weight difference from a naively retrained model, subsumes a large class of unlearning metrics and offers a common basis for comparing methods.Measuring it requires retraining, however, and the comparison can be noisy; its ability to subsume other metrics also depends on specific method properties.Source: §1 · p. 1
  • SGD analysis motivates single gradient unlearning, an inexpensive approximate method that depends only on the initial weights, with additional terms capturing approximation error.The method is derived by expanding SGD with a Taylor series and analyzing the result.Source: §1 · pp. 1–2
  • The authors derive unlearning error as a cheaper proxy for verification error that avoids retraining and its associated noise, and report strong correlation between the two in relevant contexts.Its form also makes apparent which training variables can be changed to reduce it.Source: §1 · p. 2
  • The proposed standard deviation (SD) loss reduces unlearning error and, consequently, verification error by encouraging less overall change in model weights during SGD.The paper reports that this approach has little impact on performance and validates it on CIFAR-10, CIFAR-100, and IMDb sentiment classification.Source: §1 · p. 2

2. Primer on Deep Learning & Notation

The section establishes supervised-learning notation and explains that deep neural networks are trained by minimizing a loss through iterative mini-batch SGD.

2. Primer on Deep Learning & Notation

  • The paper studies supervised learning, representing examples as input-label pairs and models as weight-parameterized functions; experiments use deep neural networks.Boldface denotes vectors and tensors.Source: §2 · p. 2
  • Classification training minimizes a prediction loss, with cross-entropy (CE) described as the de-facto choice.The loss measures prediction error for labels given inputs.Source: §2 · p. 2
  • Because non-convex models such as DNNs lack an analytical closed-form solution, their weights are learned iteratively using schemes derived from mini-batch SGD.At step t, weights use the previous step's weights, a mini-batch, and learning-rate hyperparameter η.Source: §2 · p. 2

3. Taxonomy of Approximate Unlearning

The section organizes approximate unlearning around metrics of forgetting and the model changes used to achieve it, after defining exact and approximate unlearning.

3.1. Defining Unlearning

  • Exact unlearning transforms the trained-model distribution into the distribution from training without x*, measured over weights or outputs; approximate methods seek smaller distances through cheaper model changes.Naive retraining without x* guarantees both notions of exact unlearning but is computationally expensive.Source: §3.1 · p. 3

3.2. Unlearning Metrics

  • Verification error is the ℓ2 distance between approximate-unlearning weights and naively retrained weights, but computing it requires costly retraining and terminal weights can vary across runs.Wu et al. use this metric.Source: §3.2 · p. 3
  • Other weight-distribution metrics include KL divergence and privacy leakage, including (ε, δ)-unlearning bounds by Sekhari et al. [10] and ε bounds by Guo et al. [11].KL divergence requires estimating the retrained-model distribution from samples; privacy leakage measures information about the point to be unlearned.Source: §3.2 · p. 3
  • Membership inference compares model outputs to assess whether x* was forgotten, but false positives on a retrained model mean lower inference likelihood alone does not establish unlearning.This approach is used by Graves et al. [8] and Baumhauer et al. [12].Source: §3.2 · p. 4

3.3. Unlearning Methods

  • Sekhari et al. [10] report that differentially private learning permits deletion of only O(n√d) datapoints while retaining meaningful bounds, and propose a strongly convex-loss unlearning algorithm using Hessian updates and final-weight noise.Source: §3.3 · p. 4

4. Verification Error & Other Metrics

The section treats verification error as a broad weight-distribution metric with implications for output similarity, while showing that it does not consistently track membership-inference privacy risk.

4.1. Verification Error implies Lp Weight Metrics

  • Average verification error bounds the sup-norm difference between approximate-unlearning and retraining weight distributions, and therefore bounds all Lp weight metrics for p ≥ 1.The derivation assumes batch size 1 and an unlearning update based only on the initial weights and batch ordering; its training-noise assumptions do not yield strict DP-like guarantees.Source: §4.1 · pp. 4–5

4.2. Convergence in the Outputs over Finite Sets

  • As verification error approaches zero, model outputs converge on any finite input set, but identical outputs do not imply identical weights.Permuting a neural network’s weights can preserve its outputs while leaving verification error nonzero.Source: §4.2 · p. 5

4.3. Connection to Membership Inference

  • For CIFAR-10 and CIFAR-100, PRS-verification-error correlations were -0.29 and -0.02, respectively, and the study found no monotonic relation.The authors note that a monotonic or linear relationship may hold under particular constraints, which they leave for future study.Source: Figure 2 · p. 6, §4.3 · p. 6

5. Defining the Unlearning Error

The section derives unlearning error as an inexpensive proxy for verification error by expanding SGD’s weight updates around the initial weights. It separates order-independent gradients that can be reversed from recursive, order-dependent terms that are costly to remove.

5.1. Expanding SGD

  • SGD expansion separates order-independent initial-weight gradients, which can be reversed by adding back ηm∂L/∂w|w0,x∗, from recursive terms that depend on data order.The second sum is not unlearned because computing its x∗-dependent terms costs at least as much computation as training; the analysis and method depend on initial weights w0, which may be pretrained.Source: §5.1 · p. 6

5.2. Approximating the Second Sum Series

  • The second-sum bound depends linearly on ||wt − w0||2, σ, and t; removing its x∗-dependent terms requires at least t − 1 Hessian-vector products.Hessian-vector products cost at least as much as gradient computations, making removal computationally expensive; the bound is zero when t = 1 or σ = 0 and tighter for a more linear loss landscape.Source: §5.2 · p. 7

5.3. Unlearning Error

  • Unlearning error e approximates the second-sum bound using the average Hessian singular value, and can be computed before applying the unlearning method.Using average rather than maximum singular value better approximates the bound and allows σ1,i to be computed every few steps, reducing cost.Source: §5.3 · p. 7

6. Reducing the Unlearning Error

The section studies training changes that reduce factors in unlearning error while leaving the unlearning method itself unchanged. It proposes standard deviation loss to reduce the change in weights, thereby reducing unlearning error provided singular values do not increase.

6.1. Strawman Approaches

  • Unlearning error increases approximately linearly with training steps, so training less reduces it nearly proportionally but degrades prediction accuracy.The authors note that public-data pretraining could compensate for fewer training steps, but such data may not always be available.Source: Figure 3 · p. 8, §6.1 · p. 8
  • ℓ2 regularization does not consistently reduce unlearning error and often increases it, because lowering the bound on weight norms need not lower the weight difference of interest.The authors also report no benefit from a separate regularizer based on squared Hessian-diagonal entries of cross-entropy loss with respect to logits.Source: §6.1 · pp. 7–8, Figure 4 · p. 8

6.2. Our Proposal: Standard Deviation Loss

  • Standard deviation (SD) loss is proposed to move the loss minimum closer to the initial weights, reducing the weight change needed during training and facilitating lower-error unlearning.The argument assumes SD loss does not increase singular values; the authors report checking this for their evaluated neural networks in § 8.2.Source: §6.2 · p. 8

A Simple Binary classifier.

  • For a binary linear classifier trained on one datapoint, increasing SD-loss strength moves the loss minimum toward equal outputs and decreases the minimum weight change required to reach it.The analysis concludes that being near equal outputs, or having low output standard deviation, means being close to a loss minimum; lower weight change reduces unlearning error if singular values do not rise.Source: A Simple Binary classifier · p. 9

7. Implementation

The implementation reused the datasets and models from § 6.1 and added an IMDb sentiment-analysis evaluation using fine-tuned DistilBERT.

7. Implementation

  • Experiments ran on T4 Nvidia GPUs using the § 6.1 datasets and models, plus fine-tuned DistilBERT [33] on IMDb reviews for binary sentiment classification.IMDb sentences were truncated to 512 tokens, DistilBERT’s maximum input length; experiments used PyTorch 1.8.1, CUDA 10.2, and Python 3.7.Source: §7 · p. 9

8. Evaluation

The evaluation finds that SD loss reduces unlearning error, largely by limiting weight changes, and that unlearning error tracks verification error across the tested models and setups. Single-gradient unlearning lowers baseline PRS, while SD regularization has no consistent effect on PRS.

8. Evaluation

  • The evaluation uses batch sizes b > 1 although the theory’s Lemma 1 and Corollary 1 assume b = 1; results were consistent across batch sizes.The authors identify extending the theory to b > 1 as future work.Source: §8 · p. 10

8.1. SD Loss Decreases Unlearning Error

  • Increasing SD regularization slows unlearning-error growth and lowers its final value; DistilBERT’s final unlearning error fell 40×, while accuracy effects varied by model and regularization strength.For vision models, accuracy dropped within 5 percentage points for γ ≤ 5 and more for γ > 5; DistilBERT showed a subtle accuracy increase after a 2.5× unlearning-error reduction.Source: §8.1 · p. 10, Table 2 · p. 11

8.2. An Ablation Study

  • SD loss leaves σavg largely unchanged but significantly reduces the weight change ||wt − w0||2; its unlearning-error reduction generally diminishes as pretraining progresses, with a ResNet-18/CIFAR-10 exception.For VGG-19 on CIFAR-10, γ = 5 reduced unlearning error by 20% after 10 pretraining epochs and 4% after 30, as models approached their final weights.Source: §8.2 · p. 11, Figure 8 · p. 11

8.3. Unlearning Error & Verification Error

  • Unlearning error strongly tracks verification error: Pearson correlations were 0.934 and 0.9668 across training durations, 0.96 and 0.81 for two CIFAR-10 models across regularization strengths, and 0.9028 and 0.8813 across 160 CIFAR settings.For DistilBERT on IMDB, the correlation across regularization strengths was 0.998; the authors propose unlearning error as a proxy for comparing unlearning across architectures.Source: §8.3 · p. 12, Figure 12 · p. 13

8.4. The Effect on PRS

  • Single-gradient unlearning lowered baseline PRS by roughly 2×, but varying SD regularization had no consistent monotonic relationship with PRS.The authors note that regularization greatly reduces verification error even though it is not needed for the unlearning method to lower PRS.Source: §8.4 · pp. 12–13

8.5. SISA Cost Comparison

  • SISA’s exact-unlearning cost can be lower only under sufficiently large slice and shard counts; it requires O(S.R) storage, whereas single-gradient approximate unlearning requires no storage.The paper contrasts SISA’s cost, stated as 2S(R+1) times the retraining cost, with a single gradient costing retraining cost divided by N; it notes N is typically about 100,000 and that increasing S was observed to reduce performance.Source: §8.5 · p. 13

9. Discussion

The discussion highlights uncertainty about when unlearning is sufficient, limitations of the experimental setup, and open questions about whether unlearning-error analysis generalizes across methods and models.

When Is unlearning achieved

  • Declines in verification error do not necessarily mean declines in PRS, and neither verification error nor unlearning error indicates how much reduction is sufficient.The authors describe the sufficiency threshold as application-oriented and dependent on what the user wants unlearning to achieve; both errors can be compared with the baseline at regularization γ = 0.Source: §9 · p. 13, Figure 13 · p. 14

Experimental constraints

  • The experiments omit learning-rate scheduling, data augmentation, and momentum/ADAM because the derivation assumes constant-LR SGD and focuses on SGD.The cited implementation reaches 93% test accuracy on CIFAR-10 with ResNet18; the authors say the performance drop on CIFAR-10 and CIFAR-100 is less significant, and DistilBERT still achieves high test accuracy.Source: §9 · p. 13

Expanding analysis of verification error

  • Amnesiac machine learning [8] uses intermediate-weight gradients, so it violates the analysis assumptions and the bounds in § 4 do not apply to it.The authors leave extending the analysis and its assumptions to other classes of unlearning methods for future work.Source: §9 · p. 13

Architectures and unlearning error

  • SD loss reduced unlearning error with a smaller performance cost for ResNet-18 on CIFAR-10 than for VGG-19, while DistilBERT reduced unlearning error with less significant accuracy drops.On CIFAR-100, SD loss’s effect diminishes for ResNet-18, but less so than for VGG-19; the authors propose investigating which architectural or domain features make unlearning easier or harder.Source: §9 · pp. 13–14

Unlearning error and verification error for other unlearning methods

  • 0.91 on CIFAR-10 and 0.81 on CIFAR-100 are correlations between unlearning error and verification error for amnesiac machine learning [8].The authors ask whether unlearning error can proxy verification error for other approximate SGD-unlearning methods.Source: §9 · p. 13, Figure 14 · p. 14

Regularizers and unlearning error

  • Future work could investigate regularizers that reduce singular values and schedules for SD loss that account for its degrading impact.The authors also suggest improving SD loss’s performance through such regularization approaches.Source: §9 · p. 14

10. Conclusion

The paper argues that verification error captures a large class of approximate-unlearning metrics under some assumptions, then uses a first-order Taylor decomposition of SGD to develop a single-gradient unlearning method and a proxy metric. It also proposes an SD loss to reduce unlearning error and, consequently, verification error.

10. Conclusion

  • Verification error captures a large class of approximate-unlearning metrics under some assumptions, motivating its use to define approximate unlearning.The paper notes that verification error cannot be optimized directly because computing it requires a perfectly unlearned model.Source: §10 · p. 14
  • A first-order Taylor decomposition of SGD yields a single-gradient unlearning method and unlearning error, which effectively proxies verification error for that method.Source: §10 · p. 14
  • The proposed SD loss can decrease the unlearning error, and thus the verification error, associated with the method.The authors suggest future work could improve the loss, explore other machine-learning tasks, and extend the bounds to other contexts or relax assumptions.Source: §10 · p. 14

Appendix · 1. Proofs

The proofs relate approximate-unlearning verification error to differences between the resulting and retrained weight distributions. Under stated noise and support assumptions, a uniform bound on the density difference gives a smaller bound on expected verification error.

1. Proofs

  • If each shifted distribution PI is Lipschitz, then ||PI(w) − PI(w − dI)||2 ≤ L||dI||2, with the same L for every I.The passage notes that Gaussian noise satisfies the Lipschitz condition and that translating a function does not change its Lipschitz constant.Source: §1 · p. 16
  • For an approximate method using w0 and ordering I, the proof writes its weights as w′′I = wI + uI and adds noise g to define the resulting density.The construction defines vI = uI + dI in the subsequent comparison with retrained weights.Source: §1 · p. 16
  • The analytic verification error for ordering I is vI = uI + dI, the difference between approximate-unlearning weights and retrained weights; v averages its norm across orderings.The passage defines v as the average of all ||vI||2.Source: §1 · p. 16
  • The reverse-direction proof bounds average verification error v using a uniform bound between the approximate-unlearning and ideal-retraining densities.The proof denotes the approximate-unlearning density by P′′(w) and compares it with P′(w).Source: §1 · p. 16
  • The approximate-unlearning procedure induces a weight density P′′(w), which the reverse-direction proof compares with the ideal-retraining density P′(w).Source: §1 · p. 16
  • Assuming zero-mean noise and bounded support union with finite first moment, the proof relates v to density expectations; weaker tail integrability adds a constant term.The passage says it is enough for the integral outside a bounded domain to be finite, with analogous reasoning and an extra constant.Source: §1 · p. 16
  • A smaller uniform bound on the density difference gives a smaller bound on the expectation of verification error v.The proof assumes a uniform pointwise bound b on the difference between the approximate-unlearning and ideal-retraining densities.Source: §1 · p. 16

2. Additional Figures · 3. Additional Tables

The additional figures and tables document how regularization strength and pretraining relate to weight-change plots, unlearning error, and test accuracy across several experimental settings.

2. Additional Figures

  • Figure 16 plots both weight changes and singular values during ResNet-18 training on CIFAR-10 for different ℓ2 regularization strengths.Source: §2 · p. 16, Figure 16 · p. 16
  • Figures 14 and 15 use the same setups as Figures 12 and 9, respectively, but use amnesiac unlearning to produce model M.Source: §2 · p. 16

3. Additional Tables

  • Table 3 reports unlearning error for four settings across ℓ2 regularization strengths and pretraining amounts, compared with zero regularization.Source: §3 · p. 16, Table 3 · p. 17
  • Table 3 also reports testing accuracy for its four settings across ℓ2 regularization strengths and pretraining amounts.Source: §3 · p. 16, Table 3 · p. 17
  • Table 4 reports unlearning error for four settings varying Standard Deviation regularization strength and pretraining amount, with t = 1 epoch.Source: §3 · p. 16, Table 4 · p. 17
  • Table 4 also reports testing accuracy for its four settings varying Standard Deviation regularization strength and pretraining amount, with t = 1 epoch.Source: §3 · p. 16, Table 4 · p. 17

Related papers

Loading 2109.13398v2…