Machine Unlearning

Lucas BourtouleVarun ChandrasekaranChristopher A. Choquette-ChooHengrui JiaAdelin TraversBaiwu ZhangDavid LieNicolas Papernot

article2019IEEE Symposium on Security and Privacy1,632 citations

Introduces the SISA framework to efficiently remove user data from trained machine learning models by strategically partitioning datasets and saving intermediate model states, drastically cutting the computational cost of complete retraining to support practical data deletion rights.

Listen

Modern privacy regulations, such as the European Union's General Data Protection Regulation and the California Consumer Privacy Act, legally mandate a "right to be forgotten," requiring organizations to completely erase personal data upon request. Standard machine learning models, especially deep neural networks, inherently memorize training data, leaving organizations vulnerable to privacy attacks if sensitive information remains embedded in model parameters. Provably removing a user's data requires "machine unlearning," ensuring the final model is statistically indistinguishable from a model never trained on that data. Traditionally, this demands retraining entire models from scratch, which creates prohibitive computational costs and operational delays for large-scale production pipelines.

The article introduces and evaluates "SISA training" (Sharded, Isolated, Sliced, and Aggregated), a practical framework designed to dramatically accelerate machine unlearning for stateful learning algorithms like deep neural networks without sacrificing strong, verifiable privacy guarantees.

The framework partitions a training dataset into multiple disjoint, isolated shards and trains separate constituent sub-models on each shard without exchanging parameter updates. Each shard is further divided into incremental slices, with model parameter checkpoints saved sequentially after training on each additional slice. When an unlearning request arrives, only the sub-model containing the target data point must be retrained, beginning directly from the last checkpoint saved before the target data slice was introduced. The outputs of all sub-models are combined during inference via aggregation strategies such as majority voting or prediction vector averaging. The authors evaluate this approach analytically and empirically across simple and complex datasets (including MNIST, Purchase, SVHN, CIFAR-100, and ImageNet) under both sequential and batched deletion scenarios, comparing it against naive retraining from scratch and fractional data baselines.

The evaluation reveals several core findings. First, SISA training provides substantial speed-ups over retraining from scratch: for simple tasks, it achieves a 4.63x retraining speed-up on the Purchase dataset and 2.45x on SVHN (configured with 20 shards and 50 slices) while incurring a negligible accuracy degradation of less than 2 percentage points. Second, the computational speed-up over the baseline is maintained as long as the number of deletion requests remains below three times the number of shards, meaning it operates effectively in realistic request regimes. Third, for complex tasks like ImageNet classification, pure sharding degrades top-5 accuracy by roughly 12 to 19.5 percentage points because sub-models lack sufficient training examples per class; however, applying transfer learning from pre-trained base models recovers this gap, reducing the accuracy loss to under 1 percentage point for top-5 accuracy while preserving retraining speed-ups. Finally, if an organization has prior knowledge of user deletion distributions across jurisdictions, distribution-aware sharding further reduces the expected volume of data requiring retraining with minimal impact on aggregate predictive performance.

These findings demonstrate that organizations can achieve strict, certifiable compliance with data erasure laws at a fraction of standard retraining costs. Rather than maintaining massive, monolithic models that require complete recomputation upon every deletion request, organizations can deploy isolated sub-models to trade modest additional storage for significant computational efficiency and operational scalability. While slicing requires additional disk storage to save intermediate parameter states, this trade-off is highly cost-effective given the comparatively low cost of storage relative to graphics processor compute time.

Organizations handling personal data in machine learning pipelines should adopt SISA training to satisfy data governance and legal erasure requirements. For complex models, engineering teams should combine SISA partitioning with transfer learning and prediction vector aggregation to mitigate potential accuracy loss. When operating across international regions with disparate privacy request rates, teams should implement distribution-aware sharding to group high-probability deletion requests into smaller, dedicated shards.

Confidence in these findings is high for standard iterative gradient descent models, though certain boundary conditions apply. Slicing benefits are restricted to stateful algorithms and do not apply to greedy non-stateful algorithms like decision trees. Furthermore, if the volume of simultaneous unlearning requests vastly exceeds the number of shards, the computational performance of SISA training naturally degrades back to that of full retraining from scratch.

University of Toronto University of Wisconsin Madison Vector Institute classification data governance individual privacy Machine Unlearning SISA training data erasure

arXiv: 1912.03817 cleverhans-lab/machine-unlearning

Paper: Membership Inference Attacks Against Machine Learning Models, Reza Shokri et al. (2016). This seminal paper introduces membership inference attacks, establishing the core privacy risk of model memorization that machine unlearning seeks to mitigate.
Paper: A Closer Look at Memorization in Deep Networks, Devansh Arpit et al. (2017). This work analyzes how deep neural networks prioritize patterns versus memorizing individual training examples, providing foundational context on why data influence persists in trained weights.
Paper: Deep Learning with Differential Privacy, Martín Abadi et al. (2016). This foundational paper develops differentially private stochastic gradient descent to bound the influence of individual training points, serving as a primary theoretical baseline for data-privacy guarantees in machine learning.
Paper: Exploiting Unintended Feature Leakage in Collaborative Learning, Luca Melis et al. (2018). This study demonstrates how intermediate training updates leak specific training samples and unintended features, underscoring the necessity of strict data partitioning and unlearning protocols.

Paper: Extracting Training Data from Large Language Models, Nicholas Carlini et al. (2020). This paper demonstrates practical verbatim training data extraction from large language models, illustrating the high-stakes memorization vulnerabilities that downstream machine unlearning methods must confront.

Abstract

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.

Topics

classification data governance individual privacy purchase stochastic stochastic gradient descent training sample transfer learning data points deep learning

Keywords

Machine Unlearning SISA training data erasure SQ learning stochastic gradient descent deep neural networks ML ensembles transfer learning

I Introduction
II Background on Machine learning
III Defining Unlearning
III-A Why is Unlearning Challenging?
III-B Formalizing the Problem of Unlearning
III-C Goals of Unlearning
III-D Strawman Solutions
IV The SISA training Approach
IV-A The SISA training Approach to Training
IV-B Techniques
IV-C Challenges
IV-C1 Weak Learners
IV-C2 Hyperparameter Search
V Measuring Time
V-A Measuring time analytically
V-B Measuring Time for Sharding
V-C Measuring Time for Slicing
VI Implementation Details
VI-A Datasets
VI-B Models & Experimental Setup
VII Evaluation
VII-A The Big Picture
VII-A1 Impact of Sharding
VII-A2 Impact of Slicing
VII-A3 Combination of Sharding and Slicing
VII-B Understanding the Regime
VII-C Bridging the Accuracy Gap
VIII Distributional Knowledge
VIII-A Realistic Scenario
VIII-B Distribution-Aware Sharding
IX Discussion
X Conclusions
References
-A Simulation of SISA training Time Analysis
-B Individual Contributions due to Slicing and Sharding
-C Costs Associated With Storage
-D Sequential Time Analysis of Sharding
-E Batched Time Analysis of Sharding
-F Sequential Time Analysis of Slicing
-G Moments of the Minimum of Draws from a Uniform Distribution
-H Batched Time Analysis of Slicing
-I Lone Shard Baseline Time Analysis
-I1 Sequential Setting
-I2 Batched Setting
-J Impact of aggregation strategy
-K Impact of number of samples per class on learnability

Knowls

Knowl 1 — Exact Machine Unlearning Guarantee
definition
Let $\mathcal{D} = \{d_i : i \in \mathcal{U}\}$ denote a training dataset collected from a user population $\mathcal{U}$ . Let $\mathcal{D}' = \mathcal{D} \cup \{d_u\}$ , where $d_u$ represents data associated with a revoking user $u$ .

Let $\mathcal{D}_{\mathcal{M}}$ denote the probability distribution of models produced by an unlearning mechanism $\mathcal{M}$ when trained on $\mathcal{D}'$ and subsequently subjected to an unlearning request for $d_u$ .

Let $\mathcal{D}_{\text{real}}$ denote the probability distribution of models produced by training directly on $\mathcal{D}$ using $\mathcal{M}$ without $d_u$ ever being present.

The mechanism $\mathcal{M}$ facilitates exact unlearning if and only if: $\mathcal{D}_{\mathcal{M}} = \mathcal{D}_{\text{real}}$

This definition accounts for stochasticity in training: two trained models having differing parameter weights does not imply different training sets, provided they are drawn from the identical hypothesis distribution that training on $\mathcal{D}$ produces. Furthermore, it strictly requires zero residual contribution from $d_u$ , distinguishing unlearning from differential privacy, which permits bounded non-zero contributions $\varepsilon > 0$ .
Knowl 2 — SISA Training Framework
model/method
SISA (Sharded, Isolated, Sliced, Aggregated) training is an unlearning framework designed for stateful iterative algorithms such as stochastic gradient descent for deep neural networks:
1. Sharding: The training set $\mathcal{D}$ of size $N$ is partitioned into $S$ disjoint shards $\mathcal{D}_1, \dots, \mathcal{D}_S$ such that $\bigcap_{k=1}^S \mathcal{D}_k = \emptyset$ and $\bigcup_{k=1}^S \mathcal{D}_k = \mathcal{D}$ .
2. Isolation: A constituent model $M_k$ is trained on each shard $\mathcal{D}_k$ completely in isolation. No gradients, activations, or parameter updates are communicated across constituents, strictly confining the influence of any data point $d_u \in \mathcal{D}_k$ to model $M_k$ .
3. Slicing: Each shard $\mathcal{D}_k$ is further partitioned into $R$ disjoint slices $\mathcal{D}_{k,1}, \dots, \mathcal{D}_{k,R}$ . Training proceeds incrementally: step 1 trains $M_{k,1}$ on $\mathcal{D}_{k,1}$ from random initialization; step $r \in \{2, \dots, R\}$ initializes from the saved checkpoint of $M_{k,r-1}$ and trains on $\bigcup_{i=1}^r \mathcal{D}_{k,i}$ , saving checkpoints before introducing each subsequent slice.
4. Unlearning: When a point $d_u \in \mathcal{D}_{k,r}$ is revoked, only constituent $M_k$ is retrained. Retraining begins directly from the parameter checkpoint saved at the end of slice $r-1$ , using updated slice $\mathcal{D}_{k,r} \setminus \{d_u\}$ and continuing through slice $R$ .
5. Aggregation: At inference time, inputs are evaluated across all $S$ constituent models, and their predictions are aggregated (via majority voting or prediction vector averaging).
Knowl 3 — Epoch Recalibration for Sliced Model Training
equation
To equalize computational training time between standard training on a shard of size $D = N/S$ for $e'$ epochs and sliced training with $R$ equal-sized slices, the total number of epochs $e = \sum_{i=1}^R e_i$ across all slices is adjusted.

Assuming each incremental slicing step $i \in \{1, \dots, R\}$ trains on $i D / R$ samples for $e_i = e / R$ epochs, equating the total sample presentations $e' D$ to the sliced sample presentations yields: $e' D = \sum_{i=1}^R e_i \frac{i D}{R} = \frac{e D}{R^2} \sum_{i=1}^R i = \frac{e D}{R^2} \frac{R(R+1)}{2} = \frac{R+1}{2R} e D$

Solving for $e$ yields the recalibration formula: $e = \frac{2R}{R + 1} e'$ where $e'$ is the baseline number of epochs without slicing, $R$ is the number of slices per shard, and $e$ is the cumulative number of epochs allocated across the $R$ slicing stages.
Knowl 4 — Expected Sample Retraining Cost of Data Sharding
theoretical result
Let a dataset of $N$ points be partitioned uniformly into $S$ shards. Let unlearning requests arrive uniformly at random across the dataset. Retraining cost $C$ represents the total number of sample passes required during retraining.
1. Sequential Setting ( $K$ requests processed one by one): Accounting for the reduction in shard sizes as points are deleted, the expected total retraining cost across $K$ unlearning requests is: $\mathbb{E}[C] = \left(\frac{N}{S} + \frac{1}{2S} - 1\right) K - \frac{K^2}{2S}$ When $K \ll N$ and $N/S \gg 1$ , this cost is bounded above by $\frac{N}{S} K$ , providing an expected $S\times$ speed-up over full dataset retraining for a single request ( $K=1$ ).
2. Batched Setting ( $K$ requests processed in a single batch): Let $h_j \in \{0, 1\}$ indicate whether shard $j \in \{1, \dots, S\}$ contains at least one deletion request, with $P(h_j = 0) = (1 - 1/S)^K$ , and let $u_j \sim \text{Binomial}(K, 1/S)$ denote the number of deletions in shard $j$ . The expected total retraining cost across all affected shards is: $\mathbb{E}[C] = N \left(1 - \left(1 - \frac{1}{S}\right)^K\right) - K$ Asymptotically, for $K \to 0$ , $\mathbb{E}[C] \sim N \left(1 - \exp\left(-\frac{K}{\tau}\right)\right)$ where $\tau = \left(-\ln(1 - 1/S)\right)^{-1}$ , and for $K \to \infty$ , $\mathbb{E}[C] \to N - K$ .
Knowl 5 — Expected Sample Retraining Cost of Slicing
theoretical result
Let a shard of size $D$ be divided into $R$ uniform slices, calibrated to baseline training epochs $e'$ . Retraining restarts from slice index $r \in \{1, \dots, R\}$ , the earliest slice containing an unlearned point.
1. Sequential Setting ( $K=1$ request): Assuming the deletion request hits slice index $r \sim \text{Uniform}(\{1, \dots, R\})$ : $\mathbb{E}[C] = e' D \left(\frac{2}{3} + \frac{1}{3R}\right)$ where $C$ is the number of sample-epoch presentations during retraining. For $R=1$ , $\mathbb{E}[C] = e' D$ (no speed-up). As $R \to \infty$ , $\mathbb{E}[C] \to \frac{2}{3} e' D$ , giving a maximum asymptotic speed-up of $1.5\times$ from slicing alone. Combined with $S$ shards, the single-request best-case speed-up is $\frac{S(R+1)}{2}\times$ .
2. Batched Setting ( $K$ requests): Retraining restarts from slice index $r_{\min} = \min_{i \in \{1, \dots, K\}} r_i$ , where $r_i \sim \text{Uniform}(\{1, \dots, R\})$ i.i.d. The expected cost is: $\mathbb{E}[C] = \frac{2 e' D}{R(R+1)} \left( \frac{R(R+1)}{2} - \frac{1}{2} \left( 1 + \frac{2(R-1)}{K+1} \frac{(K+1)+R}{K+2} - \frac{K+R}{K+1} \right) \right)$ For $K \ll R$ , slicing achieves a significant speed-up, decreasing with $1/K^2$ as $K \to 0$ . When $K \gg R$ , $\mathbb{E}[C] \sim e' D$ , matching unsliced retraining without degradation.
Knowl 6 — Distribution-Aware Data Sharding
algorithm
When individual erasure probabilities $p(u)$ are known a priori, distribution-aware sharding aggregates points with high deletion probabilities into fewer, smaller shards to minimize the expected retraining workload.
Input: Dataset $\mathcal{D}$ , threshold constant $C \le 1$ , per-user erasure probabilities $\{p(u) : u \in \mathcal{U}\}$
Output: Partition of shards $\mathcal{D}_0, \mathcal{D}_1, \dots, \mathcal{D}_m$
procedure ShardData( $\mathcal{D}$ , $C$ )
    sort $\{d_u\}_{u=1}^{|\mathcal{D}|}$ in ascending order by $p(u)$
     $i \leftarrow 0$
     $\mathcal{D}_i \leftarrow \emptyset$
    for each $d_u \in \mathcal{D}$ in sorted order do
         $\mathcal{D}_i \leftarrow \mathcal{D}_i \cup \{d_u\}$
        compute expected unlearning requests $\mathbb{E}[\chi_i] \leftarrow \sum_{v: d_v \in \mathcal{D}_i} p(v)$
        if $\mathbb{E}[\chi_i] \ge C$ then
             $\mathcal{D}_i \leftarrow \mathcal{D}_i \setminus \{d_u\}$
             $i \leftarrow i + 1$
             $\mathcal{D}_i \leftarrow \{d_u\}$
        end if
    end for
    return $\mathcal{D}_0, \dots, \mathcal{D}_i$
end procedure
The sum of independent Bernoulli erasure trials $\chi_i$ in shard $\mathcal{D}_i$ follows a Poisson binomial distribution with expectation $\mathbb{E}[\chi_i] = \sum_{u: d_u \in \mathcal{D}_i} p(u)$ . By enforcing $\mathbb{E}[\chi_i] < C$ with $C \le 1$ , the procedure ensures that large shards containing privacy-insensitive data have a low probability of requiring retraining, while unlearning events concentrate in a few small shards.
Knowl 7 — SISA Unlearning Efficiency on Simple Classification Tasks
empirical result
Under uniform unlearning request distributions, SISA training was evaluated on three simple classification benchmarks: MNIST ( $28 \times 28$ grayscale images, 10 classes, 60,000 samples, 2 convolutional + 2 fully connected layers), Purchase (600 features, 2 classes, 250,000 samples, 2 fully connected layers), and SVHN ( $32 \times 32 \times 3$ images, 10 classes, 604,833 samples, Wide ResNet-1-1).

Using a configuration of $S=20$ shards and $R=50$ slices in the batch setting:
- On the Purchase dataset, SISA achieved a $4.63\times$ speed-up in retraining time compared to full retraining from scratch for a batch of $K=8$ unlearning requests, with less than a 2 percentage point (PP) degradation in classification accuracy.
- On the SVHN dataset, SISA achieved a $2.45\times$ speed-up over full retraining for $K=18$ unlearning requests, also maintaining accuracy within 2 PP of the full-dataset baseline.
- Increasing the number of shards beyond $S=20$ resulted in accuracy degradation exceeding 5 PP due to insufficient sample volume per class per shard.
Knowl 8 — Mitigating Weak-Learner Degradation in Complex Tasks via Soft Aggregation and Transfer Learning
empirical result
For complex learning tasks with high input dimensionality and large class sets (ImageNet: 1,000 classes, 1.28M samples; Mini-ImageNet: 100 classes, 128k samples), training constituent ResNet-50 models on individual shards causes them to act as weak learners due to reduced samples per class per shard:
- Hard Label Aggregation: Using standard majority voting on ImageNet, SISA with ResNet-50 suffered an average top-5 accuracy degradation of 16.14 percentage points (PP) and top-1 degradation of 18.76 PP compared to full-dataset training (baseline top-5: 92.87%, top-1: 76.15%), while delivering a $1.36\times$ retraining speed-up for $K=39$ unlearning requests.
- Prediction Vector Aggregation: Averaging post-softmax confidence vectors across constituents instead of hard label votes improved accuracy on ImageNet by an average of 1.68 PP top-1 and 4.37 PP top-5 (lowering top-5 degradation to 11.77 PP).
- Transfer Learning: Pretraining ResNet-50 on ImageNet and applying SISA fine-tuning on CIFAR-100 ( $32 \times 32 \times 3$ , 100 classes, 60,000 samples) across $S=10$ shards reduced top-1 accuracy degradation to $\sim 4$ PP and top-5 accuracy degradation to $< 1$ PP relative to the $S=1$ baseline, preserving unlearning speed-up without requiring heterogeneous architectures or per-shard hyperparameter tuning.
Knowl 9 — Retraining Point Reductions via Distribution-Aware Sharding Under Multi-Jurisdiction Request Rates
empirical result
Distribution-aware sharding was evaluated in a multi-jurisdiction setup modeling GDPR data erasure request rates across $N=3$ countries:
- Country $c_1$ : $77.17\%$ of total data $|D|$ , erasure probability $p_{c_1} = 3 \times 10^{-6}$ .
- Country $c_2$ : $10.01\%$ of total data $|D|$ , erasure probability $p_{c_2} = 3 \times 10^{-5}$ .
- Country $c_3$ : $12.82\%$ of total data $|D|$ , erasure probability $p_{c_3} = 6 \times 10^{-6}$ .
When applied to the SVHN dataset with threshold $C=1$ , the algorithm generated 19 unequal shards. Compared to uniform sharding:
- Distribution-aware sharding significantly reduced the expected number of samples requiring retraining as the number of unlearning requests increased from 1 to 20, because high-erasure users were concentrated into smaller shards.
- The ensemble achieved an aggregate test accuracy of $94.4\%$ in the evaluated request regime, compared to $95.7\%$ for uniform sharding, trading 1.3 percentage points of accuracy for substantial computational unlearning savings.
Knowl 10 — Operational Regime Bounds for SISA Unlearning Benefits
limitation
SISA training provides computational speed-ups over naive retraining from scratch only within bounded regimes of unlearning request volume:
1. Sharding Batch Bound: Retraining speed-up from sharding exists only when the batch size of unlearning requests $K$ satisfies $K < 3S$ , where $S$ is the number of shards. When $K \ge 3S$ , the probability that all shards contain at least one affected sample approaches 1, causing retraining cost to converge to that of retraining from scratch.
2. Dataset Fraction Thresholds:
  - For sharding ( $S=20$ ), speed-ups are maintained only when unlearning requests represent less than $0.075\%$ of the total dataset size.
  - For slicing ( $S=20, R=50$ ), speed-ups are maintained only when unlearning requests represent less than $0.003\%$ of the total dataset size, as higher request counts frequently invalidate the earliest slices and necessitate retraining the entire shard.
When unlearning request rates exceed these thresholds, SISA computational performance gracefully degrades to match full-dataset retraining without imposing additional asymptotic overhead.

Coverage note — No substantial contributed material was omitted; the knowls cover the exact unlearning definition, the SISA framework and its analytical cost formulations, the distribution-aware sharding algorithm, empirical evaluations across simple and complex datasets, transfer learning mitigations, and operating regime limitations.

References

1.Y. Liu, K. K. Gadepalli, M. Norouzi, G. Dahl, T. Kohlberger, S. Venugopalan, A. S. Boyko, A. Timofeev, P. Q. Nelson, G. Corrado, J. Hipp, L. Peng, and M. Stumpe, “Detecting cancer metastases on gigapixel pathology images,” arXiv, Tech. Rep., 2017. [Online]. Available: https://arxiv.org/abs/1703.02442
2.M. X. Chen, B. N. Lee, G. Bansal, Y. Cao, S. Zhang, J. Lu, J. Tsay, Y. Wang, A. M. Dai, Z. Chen et al., “Gmail smart compose: Real-time assisted writing,” arXiv preprint arXiv:1906.00080, 2019.
3.X. He, J. Pan, O. Jin, T. Xu, B. Liu, T. Xu, Y. Shi, A. Atallah, R. Herbrich, S. Bowers et al., “Practical lessons from predicting clicks on ads at facebook,” in Proceedings of the Eighth International Workshop on Data Mining for Online Advertising. ACM, 2014, pp. 1–9.
4.S. Shalev-Shwartz et al., “Online learning and online convex optimization,” Foundations and Trends® in Machine Learning, vol. 4, no. 2, pp. 107–194, 2012.
5.A. Mantelero, “The eu proposal for a general data protection regulation and the roots of the ‘right to be forgotten’,” Computer Law & Security Review, vol. 29, no. 3, pp. 229–235, 2013.
6.“Bill text,” https://leginfo.legislature.ca.gov/faces/billTextClient.xhtml?bill id=201720180AB375.
7.O. of the Privacy Commissioner of Canada, “Announcement: Privacy commissioner seeks federal court determination on key issue for canadians’ online reputation,” https://www.priv.gc.ca/en/opc-news/news-and-announcements/2018/an 181010/, Oct 2018.
8.S. Shastri, M. Wasserman, and V. Chidambaram, “The seven sins of personal-data processing systems under gdpr,” USENIX HotCloud, 2019.
9.“Lex access to european union law,” https://eur-lex.europa.eu/eli/reg/2016/679/2016-05-04.
10.M. Fredrikson, S. Jha, and T. Ristenpart, “Model inversion attacks that exploit confidence information and basic countermeasures,” in Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security. ACM, 2015, pp. 1322–1333.
11.N. Carlini, C. Liu, U. Erlingsson, J. Kos, and D. Song, “The secret sharer: Evaluating and testing unintended memorization in neural networks,” in Proceedings of the 28th USENIX Conference on Security Symposium. USENIX Association, 2019.
12.C. Dwork, A. Roth et al., “The algorithmic foundations of differential privacy,” Foundations and Trends® in Theoretical Computer Science, vol. 9, no. 3–4, pp. 211–407, 2014.
13.K. Chaudhuri, C. Monteleoni, and A. D. Sarwate, “Differentially private empirical risk minimization,” Journal of Machine Learning Research, vol. 12, no. Mar, pp. 1069–1109, 2011.
14.M. Abadi, A. Chu, I. Goodfellow, H. B. McMahan, I. Mironov, K. Talwar, and L. Zhang, “Deep learning with differential privacy,” in Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security. ACM, 2016, pp. 308–318.
15.Y. Cao and J. Yang, “Towards making systems forget with machine unlearning,” in 2015 IEEE Symposium on Security and Privacy. IEEE, 2015, pp. 463–480. [Online]. Available: https://ieeexplore.ieee.org/document/7163042/
16.M. Kearns, “Efficient noise-tolerant learning from statistical queries,” Journal of the ACM (JACM), vol. 45, no. 6, pp. 983–1006, 1998.
17.B. Nelson, M. Barreno, F. J. Chi, A. D. Joseph et al., “Exploiting machine learning to subvert your spam filter,” in Proceedings of the 1st Usenix Workshop on Large-Scale Exploits and Emergent Threats. USENIX Association, 2008.
18.B. I. Rubinstein, B. Nelson, L. Huang, A. D. Joseph, S.-h. Lau, S. Rao, N. Taft, and J. D. Tygar, “Antidote: Understanding and defending against poisoning of anomaly detectors,” in Proceedings of the 9th ACM SIGCOMM Conference on Internet Measurement, 2009.
19.B. Biggio, B. Nelson, and P. Laskov, “Poisoning attacks against support vector machines,” arXiv preprint arXiv:1206.6389, 2012.
20.M. Kearns, “Thoughts on hypothesis boosting,” Unpublished manuscript, vol. 45, p. 105, 1988.
21.T. Bertram, E. Bursztein, S. Caro, H. Chao, R. C. Feman et al., “Five years of the right to be forgotten,” in Proceedings of the Conference on Computer and Communications Security, 2019.
22.A. Krizhevsky, I. Sutskever, and G. E. Hinton, “Imagenet classification with deep convolutional neural networks,” in Advances in neural information processing systems, 2012, pp. 1097–1105.
23.N. P. Jouppi, C. Young, N. Patil, D. Patterson, G. Agrawal, R. Bajwa, S. Bates, S. Bhatia, N. Boden, A. Borchers et al., “In-datacenter performance analysis of a tensor processing unit,” in 2017 ACM/IEEE 44th Annual International Symposium on Computer Architecture (ISCA). IEEE, 2017, pp. 1–12.
24.S. Shalev-Shwartz and S. Ben-David, Understanding machine learning: From theory to algorithms. Cambridge university press, 2014.
25.L. G. Valiant, “A theory of the learnable,” in Proceedings of the sixteenth annual ACM symposium on Theory of computing. ACM, 1984, pp. 436–445.
26.Y. LeCun, Y. Bengio, and G. Hinton, “Deep learning,” nature, vol. 521, no. 7553, pp. 436–444, 2015.
27.D. E. Rumelhart, G. E. Hinton, and R. J. Williams, “Learning representations by back-propagating errors,” nature, vol. 323, no. 6088, pp. 533–536, 1986.
28.R. D. Cook and S. Weisberg, “Characterizations of an empirical influence function for detecting influential cases in regression,” Technometrics, vol. 22, no. 4, pp. 495–508, 1980.
29.P. W. Koh and P. Liang, “Understanding black-box predictions via influence functions,” in Proceedings of the 34th International Conference on Machine Learning-Volume 70. JMLR. org, 2017, pp. 1885–1894.
30.B. Kim, C. Rudin, and J. A. Shah, “The bayesian case model: A generative approach for case-based reasoning and prototype classification,” in Advances in Neural Information Processing Systems, 2014.
31.J. H. Saltzer and M. D. Schroeder, “The protection of information in computer systems,” Proceedings of the IEEE, vol. 63, no. 9, pp. 1278–1308, 1975.
32.C. Dwork, “Differential privacy,” Encyclopedia of Cryptography and Security, pp. 338–340, 2011.
33.K. Chaudhuri and C. Monteleoni, “Privacy-preserving logistic regression,” in Advances in neural information processing systems, 2009, pp. 289–296.
34.C. Guo, T. Goldstein, A. Hannun, and L. van der Maaten, “Certified data removal from machine learning models,” arXiv preprint arXiv:1911.03030, 2019.
35.A. Golatkar, A. Achille, and S. Soatto, “Eternal sunshine of the spotless net: Selective forgetting in deep networks,” in Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, 2020, pp. 9304–9312.
36.A. Ginart, M. Y. Guan, G. Valiant, and J. Zou, “Making AI forget you: Data deletion in machine learning,” CoRR, vol. abs/1907.05012, 2019. [Online]. Available: http://arxiv.org/abs/1907.05012
37.J. Dean, G. Corrado, R. Monga, K. Chen, M. Devin, M. Mao, M. Ranzato, A. Senior et al., “Large scale distributed deep networks,” in Advances in neural information processing systems, 2012.
38.T. Ben-Nun and T. Hoefler, “Demystifying parallel and distributed deep learning: An in-depth concurrency analysis,” ACM Computing Surveys (CSUR), vol. 52, no. 4, p. 65, 2019.
39.T. G. Dietterich, “Ensemble methods in machine learning,” in International workshop on multiple classifier systems. Springer, 2000, pp. 1–15.
40.S. Shalev-Shwartz, Y. Singer, N. Srebro, and A. Cotter, “Pegasos: Primal estimated sub-gradient solver for svm,” Mathematical programming, vol. 127, no. 1, pp. 3–30, 2011.
41.N. Shazeer, A. Mirhoseini, K. Maziarz, A. Davis, Q. Le, G. Hinton, and J. Dean, “Outrageously large neural networks: The sparsely-gated mixture-of-experts layer,” arXiv preprint arXiv:1701.06538, 2017.
42.J. Snell, K. Swersky, and R. Zemel, “Prototypical networks for few-shot learning,” in Advances in neural information processing systems, 2017, pp. 4077–4087.
43.Y. Lecun, L. Bottou, Y. Bengio, and P. Haffner, “Gradient-based learning applied to document recognition,” Proceedings of the IEEE, vol. 86, pp. 2278 – 2324, 12 1998.
44.J. Deng, W. Dong, R. Socher, L.-J. Li, K. Li, and L. Fei-Fei, “ImageNet: A Large-Scale Hierarchical Image Database,” in CVPR09, 2009.
45.Y. Freund and R. E. Schapire, “A decision-theoretic generalization of on-line learning and an application to boosting,” Journal of computer and system sciences, vol. 55, no. 1, pp. 119–139, 1997.
46.D. Opitz and R. Maclin, “Popular ensemble methods: An empirical study,” Journal of artificial intelligence research, vol. 11, pp. 169–198, 1999.
47.R. Shokri, M. Stronati, C. Song, and V. Shmatikov, “Membership inference attacks against machine learning models,” in 2017 IEEE Symposium on Security and Privacy (SP). IEEE, 2017, pp. 3–18.
48.O. Vinyals, C. Blundell, T. Lillicrap, D. Wierstra et al., “Matching networks for one shot learning,” in Advances in neural information processing systems, 2016, pp. 3630–3638.
49.C. O. Sakar, S. O. Polat, M. Katircioglu, and Y. Kastro, “Real-time prediction of online shoppers’ purchasing intention using multilayer perceptron and lstm recurrent neural networks,” Neural Computing and Applications, vol. 31, no. 10, pp. 6893–6908, 2019.
50.Y. Netzer, T. Wang, A. Coates, A. Bissacco, B. Wu, and A. Ng, “Reading digits in natural images with unsupervised feature learning,” NIPS, 01 2011.
51.A. Krizhevsky, “Learning multiple layers of features from tiny images,” 2009.
52.R. E. Schapire, “A brief introduction to boosting,” in Ijcai, vol. 99, 1999, pp. 1401–1406.
53.H. Schwenk and Y. Bengio, “Boosting neural networks,” Neural computation, vol. 12, no. 8, pp. 1869–1887, 2000.
54.B. Settles, “Active learning literature survey,” University of Wisconsin-Madison Department of Computer Sciences, Tech. Rep., 2009.
55.S.-J. Huang, R. Jin, and Z.-H. Zhou, “Active learning by querying informative and representative examples,” in Advances in neural information processing systems, 2010, pp. 892–900.
56.C. Baykal, L. Liebenwein, I. Gilitschenski, D. Feldman, and D. Rus, “Data-dependent coresets for compressing neural networks with applications to generalization bounds,” CoRR, vol. abs/1804.05345, 2018. [Online]. Available: http://arxiv.org/abs/1804.05345
57.O. Sener and S. Savarese, “Active learning for convolutional neural networks: A core-set approach,” arXiv preprint arXiv:1708.00489, 2017.
58.C. Tan, L. Yu, J. B. Leners, and M. Walfish, “The efficient server audit problem, deduplicated re-execution, and the web,” in Proceedings of the 26th Symposium on Operating Systems Principles. ACM, 2017, pp. 546–564.
59.R. S. Wahby, Y. Ji, A. J. Blumberg, A. Shelat, J. Thaler, M. Walfish, and T. Wies, “Full accounting for verifiable outsourcing,” in Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security. ACM, 2017, pp. 2071–2086.
60.S. T. Setty, R. McPherson, A. J. Blumberg, and M. Walfish, “Making argument systems for outsourced computation practical (sometimes).” in NDSS, vol. 1, no. 9, 2012, p. 17.
61.https://math.stackexchange.com/questions/786392/expectation-of-minimum-of-n-i-i-d-uniform-random-variables.

Citation

MLA

Bourtoule, L., et al. “Machine Unlearning”. arXiv, 2019, http://arxiv.org/abs/1912.03817v3.

APA

Bourtoule, L., Chandrasekaran, V., Choquette-Choo, C. A., Jia, H., Travers, A., Zhang, B., Lie, D., & Papernot, N. (2019). Machine Unlearning. arXiv. http://arxiv.org/abs/1912.03817v3

Chicago

Bourtoule, L., V. Chandrasekaran, C. A. Choquette-Choo, et al. 2019. “Machine Unlearning”. arXiv. http://arxiv.org/abs/1912.03817v3.

Harvard

Bourtoule, L. et al. (2019) “Machine Unlearning”, arXiv [Preprint]. Available at: http://arxiv.org/abs/1912.03817v3.

Vancouver

1. Bourtoule L, Chandrasekaran V, Choquette-Choo CA, Jia H, Travers A, Zhang B, Lie D, Papernot N (2019) Machine Unlearning. arXiv

BibTeX

@article{bourtoule2019machine,
  title = {Machine Unlearning},
  author = {Bourtoule, Lucas and Chandrasekaran, Varun and Choquette-Choo, Christopher A. and Jia, Hengrui and Travers, Adelin and Zhang, Baiwu and Lie, David and Papernot, Nicolas},
  year = {2019},
  journal = {arXiv},
  url = {http://arxiv.org/abs/1912.03817v3},
  eprint = {1912.03817}
}

Metadata:arXiv

Source Code

This paper has an official code repository available. Click below to access the source code.

View Repository

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF

Machine Unlearning

Abstract

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — Exact Machine Unlearning Guarantee

Knowl 2 — SISA Training Framework

Knowl 3 — Epoch Recalibration for Sliced Model Training

Knowl 4 — Expected Sample Retraining Cost of Data Sharding

Knowl 5 — Expected Sample Retraining Cost of Slicing

Knowl 6 — Distribution-Aware Data Sharding

Knowl 7 — SISA Unlearning Efficiency on Simple Classification Tasks

Knowl 8 — Mitigating Weak-Learner Degradation in Complex Tasks via Soft Aggregation and Transfer Learning

Knowl 9 — Retraining Point Reductions via Distribution-Aware Sharding Under Multi-Jurisdiction Request Rates

Knowl 10 — Operational Regime Bounds for SISA Unlearning Benefits

References

Citation

BibTeX

Source Code

Access the Paper