PaperlayerView exact revision on arXiv

Source-linked AI summary

Machine Unlearning

Lucas Bourtoule, Varun Chandrasekaran, Christopher A. Choquette-Choo, Hengrui Jia, Adelin Travers, Baiwu Zhang, David Lie, Nicolas Papernot

arXiv:1912.03817v3cs.CRcs.AIcs.LG

TL;DR

Machine learning can memorize sensitive personal data, making regulated deletion difficult because removing a point's influence from a trained model is challenging. SISA training limits that influence through sharding, isolation, slicing, and aggregation, reducing retraining costs. Across simple and complex tasks, it improves unlearning time, while accuracy trade-offs depend on task complexity and can be reduced with transfer learning.

Abstract

from arXiv · show

Once users have shared their data online, it is generally difficult for them to revoke access and ask for the data to be deleted. Machine learning (ML) exacerbates this problem because any model trained with said data may have memorized it, putting users at risk of a successful privacy attack exposing their information. Yet, having models unlearn is notoriously difficult. We introduce SISA training, a framework that expedites the unlearning process by strategically limiting the influence of a data point in the training procedure. While our framework is applicable to any learning algorithm, it is designed to achieve the largest improvements for stateful algorithms like stochastic gradient descent for deep neural networks. SISA training reduces the computational overhead associated with unlearning, even in the worst-case setting where unlearning requests are made uniformly across the training set. In some cases, the service provider may have a prior on the distribution of unlearning requests that will be issued by users. We may take this prior into account to partition and order data accordingly, and further decrease overhead from unlearning. Our evaluation spans several datasets from different domains, with corresponding motivations for unlearning. Under no distributional assumptions, for simple learning tasks, we observe that SISA training improves time to unlearn points from the Purchase dataset by 4.63x, and 2.45x for the SVHN dataset, over retraining from scratch. SISA training also provides a speed-up of 1.36x in retraining for complex learning tasks such as ImageNet classification; aided by transfer learning, this results in a small degradation in accuracy. Our work contributes to practical data governance in machine unlearning.

I. INTRODUCTION

Machine unlearning is motivated by privacy and data-erasure requirements, but stochastic, incremental ML training makes removing a point difficult. SISA training limits point influence through sharding and slicing, reducing unlearning time while trading off some accuracy.

  • Personal data used in ML may be sensitive, and regulations require organizations to take reasonable steps toward erasing it.Source: §I · p. 1
  • ML models may memorize training data, so deleting a data point requires removing its influence from trained models.Source: §I · p. 1
  • SISA training shards data, trains isolated models, slices shard data incrementally, and saves parameter states before each slice.Source: §I · p. 2
  • SISA training analytically addresses sequential and batched requests, and request-distribution priors can further reduce expected unlearning time.Source: §I · p. 2
  • 1.36× speed-up was observed for complex tasks, while transfer learning reduced the associated accuracy degradation.Source: §I · p. 2

III. DEFINING UNLEARNING

The paper defines unlearning as producing a model distribution indistinguishable from training without revoked data. It frames the challenge around unknown point influence, stochastic and incremental training, and the cost of retraining from scratch.

A. Why is Unlearning Challenging?

B. Formalizing the Problem of Unlearning

C. Goals of Unlearning

  • Retraining from scratch is a powerful baseline but becomes intractable for large datasets and frequent erasure requests.Source: C. Goals of Unlearning · p. 4

D. Strawman Solutions

The paper contrasts existing unlearning strategies with SISA, which limits each point’s influence through isolated shard models and sliced incremental training. This design enables retraining only affected constituents while aggregating their predictions.

  • SISA is proposed to overcome the computational inefficiency of retraining models from scratch after data erasure.Source: §IV · p. 5
  • SISA partitions data into disjoint shards, trains constituent models independently, and aggregates their predictions at inference.Constituents do not exchange gradients or other iterative updates.Source: A. The SISA training Approach to… · p. 5
  • Under uniform sharding, the proposal has an expected speed-up of S× over retraining from scratch when the deleted subset is much smaller than the full dataset.Source: B. Techniques · p. 6
  • A point’s influence is restricted to its shard’s constituent model, so unlearning requires retraining only affected models or slices.Source: B. Techniques · p. 6, A. The SISA training Approach to… · p. 6
  • Slicing trains each shard model incrementally on increasing subsets while saving parameter states before each new slice.After erasure, retraining can restart from the saved state preceding the affected slice.Source: A. The SISA training Approach to… · p. 6, B. Techniques · p. 7
  • Aggregation can average full prediction vectors rather than using only majority votes, preserving information about runner-up classes.Source: B. Techniques · p. 7

C. Challenges

SISA faces accuracy and modeling challenges because isolated constituent models train on smaller, potentially unrepresentative datasets. These effects are more pronounced for complex tasks and require aggregation or other adjustments.

  • SISA makes no assumptions about unlearning requests, training algorithms, or data distributions within shards and slices.Source: C. Challenges · p. 7

C. Challenges

  • Constituent models trained on small shards may become weak learners with lower accuracy than a model trained on the full dataset.Source: 1) Weak Learners · p. 7
  • Accuracy degradation is more pronounced for complex learning tasks than for simple tasks.Source: 1) Weak Learners · p. 7
  • Limited and non-prototypical shard data can cause high-capacity deep networks to overfit, especially when samples per class are scarce.Source: 1) Weak Learners · p. 8
  • Aggregation recovers some accuracy, but homogeneous architectures and shared hyperparameters may limit its benefits relative to heterogeneous ensembles.Source: 1) Weak Learners · p. 8

2) Hyperparameter Search:

The analysis measures retraining cost through sample counts and studies how sharding affects sequential and batched unlearning. Sharding helps most when requests are few relative to the dataset, while its gains diminish as requests accumulate.

A. Measuring time analytically

2) Hyperparameter Search:

C. Measuring Time for Slicing

Slicing reduces retraining by restarting from the earliest affected slice, but its benefit depends on the number of slices and unlearning requests. The analysis uses approximations and a batch-sampling assumption.

C. Measuring Time for Slicing

VI. IMPLEMENTATION DETAILS

The evaluation examines SISA across datasets, model complexities, shard and slice configurations, and unlearning-request regimes, comparing accuracy and retraining time with two baselines. SISA can improve retraining time while trading off accuracy, especially for complex tasks and excessive sharding.

Datasets

  • Experiments use MNIST, SVHN, Purchase, ImageNet, and Mini-ImageNet to cover simple and complex learning tasks.The datasets vary in sample counts, input dimensionality, and samples per class.Source: A. Datasets · p. 9

Sharding effects

  • More than 20 shards cause accuracy decreases greater than 5 percentage points on simple tasks, while more than 3S requests degrade retraining time to the batch K baseline.The accuracy decline is attributed to reduced data volumes per shard.Source: 1) Impact of Sharding · p. 11

Accuracy–time trade-off

  • SISA has lower accuracy than batch K but shorter retraining time, whereas the 1/S-fraction baseline has shorter retraining time but lower accuracy.The batch K comparison corresponds to using one shard and one slice, whereas the fraction baseline trains on less than the full dataset.Source: 1) Impact of Sharding · p. 11

Complex learning tasks

  • Complex tasks show larger accuracy degradation, but prediction-vector aggregation improves average top-1 accuracy by 1.68 percentage points and top-5 accuracy by 4.37 percentage points.The top-5 accuracy gap is reduced to 11.77 percentage points, and the same observations hold on Mini-ImageNet.Source: 1) Impact of Sharding · p. 11

2) Impact of Slicing:

Slicing can reduce retraining time without harming accuracy when training time is recalibrated, while combined sharding and slicing produces speed-ups whose benefits depend on request volume and shard count. Distributional knowledge can further guide partitioning, but grouping likely-to-unlearn users may harm fair predictions.

Impact of Slicing

  • Slicing does not reduce model accuracy when sliced and unsliced models receive the same training time through recalibrated epochs.Its retraining-time benefit requires accepting storage overhead linear in the number of slices.Source: 2) Impact of Slicing · p. 11

Combined sharding and slicing

Request-volume regime

  • The strongest retraining benefits occur when unlearning requests are below 0.075% of the dataset, with gains bounded to a narrower regime at higher request volumes.The reported gain regime is at most 0.003%, while practical request rates are described as being on the order of 10^-6.Source: B. Understanding the Regime · p. 12

Transfer learning

  • Transfer learning from ImageNet to CIFAR-100 is used to examine whether SISA causes lower accuracy degradation in a realistic complex-task setting.The setup uses an ImageNet-trained ResNet-50 base model and compares S > 1 against the S = 1 baseline.Source: C. Bridging the Accuracy Gap · p. 12, Figure 8 · p. 12

Distributional knowledge

  • Knowledge of request probabilities can support nonuniform partitioning, but grouping likely-to-unlearn users into small shards may harm fair predictions.The paper models each user’s erasure probability as p(u) and groups users with high probabilities to reduce retraining time.Source: §VIII · pp. 12–13

A. Realistic Scenario

The paper models unlearning requests with known, potentially nonuniform probabilities and uses distribution-aware sharding to reduce retraining overhead while managing accuracy trade-offs.

APPENDIX A. Simulation of SISA training Time Analysis

The appendix analyzes sequential unlearning costs by simulating requests across shards and slices, and examines how sharding and slicing affect retraining time as requests accumulate.

  • The simulation generates between 1 and 500 unlearning requests, computes retraining data under SISA, and repeats each experiment 100 times.Source: Appendix A · p. 16
  • The analysis expresses unlearning cost as a function of the number of requests, slices, and shards.Source: Appendix A · p. 16
  • Slicing trades additional disk storage for faster unlearning, motivated by lower storage costs than GPU accelerator costs.Source: C. Costs Associated With Storage · p. 16
  • For sequential requests, the retraining set depends on whether later requests affect previously affected shards and on the remaining points in those shards.Source: D. Sequential Time Analysis of Sharding · p. 16

E. Batched Time Analysis of Sharding

This section models batched unlearning by tracking which shards are affected and defines retraining cost as the total size of those affected shards.

F. Sequential Time Analysis of Slicing

The sequential slicing analysis derives retraining cost from the slice receiving an unlearning request and shows that increasing slices eventually produces diminishing speed-up.

H. Batched Time Analysis of Slicing

The batched analysis models which requests affect the lone training shard and computes the resulting retraining cost. It contrasts this baseline’s speed with SISA while preserving the accuracy trade-off.

  • The batched analysis retrains all slices from the earliest affected slice through the final slice after K requests.Source: H. Batched Time Analysis of Slicing · p. 18
  • A lone shard trains one model on a 1/S fraction of the dataset, leaving the remainder unused.Source: §I · p. 18
  • In a batch, each request either affects the sole shard or incurs zero retraining cost, with shard-hit probability approximately 1/S.Source: 1) Sequential Setting · p. 19
  • The lone shard baseline provides an S× speed-up over SISA training but performs poorly in accuracy on complex learning tasks.Source: 1) Sequential Setting · p. 19

2) Batched Setting:

The batched setting estimates retraining cost under multiple requests and examines how prediction aggregation and samples per class affect accuracy. SISA’s accuracy depends especially on task difficulty and effective class sample size.

  • For K ≪ N, the approximate SISA cost is N(1 − exp(−K/S))^-1, creating a regime that can be compared with the lone shard baseline.Source: 2) Batched Setting · p. 19
  • SISA requires aggregating predictions from different models, and the experiments compare two aggregation strategies across four datasets.Source: J. Impact of aggregation strategy · p. 19
  • On Purchase and SVHN, changing between label and prediction-vector aggregation does not significantly affect model performance.Source: Figure 13 · p. 19
  • On Mini-ImageNet and ImageNet, a suitable aggregation strategy helps recover more accuracy on difficult high-resolution image classification tasks.Source: Figure 14 · p. 19
  • As the average number of samples per class increases, test accuracy increases; increased sharding lowers this quantity for complex tasks.Source: Figure 15 · p. 19, J. Impact of aggregation strategy · p. 19

Related papers

Loading 1912.03817v3…