Source-linked AI summary
Machine Unlearning
Lucas Bourtoule, Varun Chandrasekaran, Christopher A. Choquette-Choo, Hengrui Jia, Adelin Travers, Baiwu Zhang, David Lie, Nicolas Papernot
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.
Problem
ML models may memorize sensitive training data, while stochastic, incremental training makes removing an individual point's influence difficult and costly.
Method
SISA training shards data, trains isolated constituent models, slices shard data incrementally with saved parameter states, and aggregates the models.
Results
SISA training improves time to unlearn across simple and complex tasks, with 4.63× and 2.45× speed-ups on Purchase and SVHN, and 1.36× on a complex task.
Takeaways & Limitations
SISA training supports practical data governance by enabling timely removal of users' data from models with limited accuracy loss in supported settings.
Takeaways & Limitations
The approach can create weak learners, hyperparameter-search overhead, and accuracy concerns when constituent models train on limited or non-prototypical data.
Abstract
from arXiv · showhide
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.
- ML models may memorize training data, so deleting a data point requires removing its influence from trained models.
- SISA training shards data, trains isolated models, slices shard data incrementally, and saves parameter states before each slice.
- SISA training analytically addresses sequential and batched requests, and request-distribution priors can further reduce expected unlearning time.
- 1.36× speed-up was observed for complex tasks, while transfer learning reduced the associated accuracy degradation.
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?: Unlearning is difficult because the influence of individual points on model parameters is poorly understood, while influence-function approaches require expensive second-order derivatives.
- A. Why is Unlearning Challenging?: Random batch sampling, changing batch order, and unsynchronized parallelism make training stochastic and nondeterministic.
- A. Why is Unlearning Challenging?: Incremental training causes later updates to depend implicitly on earlier updates involving the point to be unlearned.
- B. Formalizing the Problem of Unlearning: Unlearning requires producing a model that could plausibly have been trained without the revoked data and convincing the user of that property.
- B. Formalizing the Problem of Unlearning: The formal definition requires the distribution after unlearning to equal the distribution produced by training directly without the revoked point.
- C. Goals of Unlearning: Retraining from scratch is a powerful baseline but becomes intractable for large datasets and frequent erasure requests.
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.
- 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.
- 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.
- A point’s influence is restricted to its shard’s constituent model, so unlearning requires retraining only affected models or slices.
- 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.
- Aggregation can average full prediction vectors rather than using only majority votes, preserving information about runner-up classes.
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.
- C. Challenges: Constituent models trained on small shards may become weak learners with lower accuracy than a model trained on the full dataset.
- C. Challenges: Accuracy degradation is more pronounced for complex learning tasks than for simple tasks.
- C. Challenges: Limited and non-prototypical shard data can cause high-capacity deep networks to overfit, especially when samples per class are scarce.
- C. Challenges: Aggregation recovers some accuracy, but homogeneous architectures and shared hyperparameters may limit its benefits relative to heterogeneous ensembles.
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: SISA’s time analysis uses the validated linear relationship between training time and the number of samples retrained.Measurements use 10% dataset increments, repeated five times on SVHN and Purchase.
- 2) Hyperparameter Search:: Sequential processing retrains one constituent model per request, whereas batching can retrain multiple affected models.
- 2) Hyperparameter Search:: The analysis assumes uniformly shuffled data split across S shards, with each shard equally likely to receive an unlearning request.
- 2) Hyperparameter Search:: Doubling the number of shards halves the number of data points needing retraining under the stated small-request and large-dataset conditions.
- 2) Hyperparameter Search:: Sharding benefits are most noticeable when the number of unlearning requests K is much smaller than the dataset size N.
- 2) Hyperparameter Search:: Sharding’s asymptotic benefits diminish as the number of requests approaches the dataset size, when quadratic cost behavior becomes dominant.
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: Because later slices depend on earlier ones, an affected slice requires retraining through the final slice.
- C. Measuring Time for Slicing: The expected-cost bound assumes the number of points per slice remains constant during unlearning and is considered acceptable when K ≪N.
- C. Measuring Time for Slicing: With infinitely many slices, slicing reaches a maximum expected speed-up of 1.5× for a single unlearning request.
- C. Measuring Time for Slicing: With one slice, slicing provides no speed-up because the entire constituent model must be retrained.
- C. Measuring Time for Slicing: Batch analysis models requests as uniform draws with replacement, an assumption numerically verified not to significantly affect the estimate.
- C. Measuring Time for Slicing: For batches with K ≫R, slicing provides no speed-up, whereas small K ≪R can yield substantial speed-up.
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.
- 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.
- 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.
- 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.
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.
- Combined sharding and slicing: Speed-up grows rapidly with shard count for 0.003% unlearning requests, while increasing slices beyond a few provides marginal gains.The figure describes combined sharding and slicing in the batch setting.
- 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.
- 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.
- 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.
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.
- The method assigns users to shards so each shard's expected number of unlearning requests remains below a chosen constant C ≤ 1.
- Distribution-aware sharding assumes the request distribution is known precisely and relatively constant over a time interval.
- 19 shards yield about 94.4% aggregate prediction accuracy, compared with 95.7% for uniform sharding.
- Distribution-aware sharding decreases the expected number of points requiring retraining, but creates unequal shard sizes and an accuracy trade-off.
- SISA training is presented as a practical approach for timely data removal and broader model governance.
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.
- The analysis expresses unlearning cost as a function of the number of requests, slices, and shards.
- Slicing trades additional disk storage for faster unlearning, motivated by lower storage costs than GPU accelerator costs.
- For sequential requests, the retraining set depends on whether later requests affect previously affected shards and on the remaining points in those shards.
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.
- The batched analysis assumes each request independently impacts one of S shards.
- Indicator variables h_j record whether shard j is affected by at least one request.
- The total retraining cost is C = Σ_j h_j|D_j|, the sum of sizes of affected shards.
- The expected batched cost is derived using Bernoulli and binomial random-variable expectations and linearity of expectation.
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.
- Without slicing, training a shard of size D for e′ epochs processes a number of samples proportional to e′D.
- With slicing, a request hitting slice r requires retraining from slice r through the final slice.
- The slice index is modeled as uniformly distributed over {1, ..., R} when computing expected retraining cost.
- For R > 20, the speed-up starts to plateau, so additional slices provide no significant gain.
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.
- A lone shard trains one model on a 1/S fraction of the dataset, leaving the remainder unused.
- In a batch, each request either affects the sole shard or incurs zero retraining cost, with shard-hit probability approximately 1/S.
- The lone shard baseline provides an S× speed-up over SISA training but performs poorly in accuracy on complex learning tasks.
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.
- SISA requires aggregating predictions from different models, and the experiments compare two aggregation strategies across four datasets.
- On Purchase and SVHN, changing between label and prediction-vector aggregation does not significantly affect model performance.
- On Mini-ImageNet and ImageNet, a suitable aggregation strategy helps recover more accuracy on difficult high-resolution image classification tasks.
- As the average number of samples per class increases, test accuracy increases; increased sharding lowers this quantity for complex tasks.