Measuring Forgetting of Memorized Training Examples
Authors: Matthew Jagielski
Om Thakkar
Florian Tramer
Daphne Ippolito
Katherine Lee
Nicholas Carlini
Eric Wallace
Shuang Song
Abhradeep Guha Thakurta
Nicolas Papernot
Chiyuan Zhang
Venue: ICLR 2023 poster (2023)
Keywords: forgetting
memorization
membership inference
canary extraction
nondeterminism
convexity

Abstract: Machine learning models exhibit two seemingly contradictory phenomena: training data memorization and various forms of forgetting. In memorization, models overfit specific training examples and become susceptible to privacy attacks. In forgetting, examples which appeared early in training are forgotten by the end. In this work, we connect these phenomena.
We propose a technique to measure to what extent models ``forget'' the specifics of training examples, becoming less susceptible to privacy attacks on examples they have not seen recently.
We show that, while non-convexity can prevent forgetting from happening in the worst-case, standard image,speech, and language models empirically do forget examples over time.
We identify nondeterminism as a potential explanation, showing that deterministically trained models do not forget.
Our results suggest that examples seen early when training with extremely large datasets---for instance those examples used to pre-train a model---may observe privacy benefits at the expense of examples seen later.

Published as a conference paper at ICLR 2023
MEASURING FORGETTING OF MEMORIZED TRAINING EXAMPLES
Matthew Jagielski', Om Thakkar', Florian Tramer Daphne Ippolito Katherine Lee Nicholas Carlini', Eric Wallace', Shuang Song!
Abhradeep Thakurta', Nicolas Papernot Chiyuan Zhang' !Google, "ETH Zurich, SCarnegie Mellon University, 'Cornell University University of California, Berkeley, University of Toronto
ABSTRACT
Machine learning models exhibit two seemingly contradictory phenomena: training data memorization, and various forms of forgetting. In memorization, models overfit specific training examples and become susceptible to privacy attacks. In forgetting, examples which appeared early in training are forgotten by the end. this work, we connect these phenomena. We propose technique to measure to what extent models "forget" the specifics of training examples, becoming less susceptible to privacy attacks examples they have not seen recently. We show that, while non-convex models can memorize data forever in the worst-case, standard image, speech, and language models empirically do forget examples over time. We identify nondeterminism as a potential explanation, showing that deterministically trained models do not forget. Our results suggest that examples seen early when training with extremely large datasets-for instance those examples used to pre-train a model moy observe privacy benefits the expense of examples seen later.
INTRODUCTION
Machine learning models are capable of memorizing information contained in their training data (Shokri et al., [0177] Carlini et al., 2019). This is one of the reasons why models are vulnerable to privacy attacks such as membership inference (Homer et al. 2008 and training data extraction (Carlini et al. 2019). Resulting privacy concerns have led to a variety of techniques for private machine learning. including differentially private training (Abadi et al., 2016)] Paaeenot et al. 2016
2018b Ghazi et al. 2021 Malek et al. 202I), machine unicarning (Bourtoule et al. 2021 Neel al. 2021). and various heuristics like regularization (Nasr et al. 2018)
al. |
3) data
augmentation (Amid et al,, 2022) or gradient clipping (Carlini et al. 2019; Thakkar et al. 2020
HHang et al. 2022). These techniques all modify the learning procedure actively limit privacy leakage, including leakage that results from memorization. Instead, we observe that the training dynamics inherent learning algorithms such as stochastic gradient descent may passively afford some forms of privacy. Such dynamics include forgetting: during iterative training, as models see new training examples, they could lose track of the specifics of earlier examples- as seen in work on
catastrophic forgetting (French) 1999 McCloskey & Cohen 1989; Kemker et al. 2018).
In this paper, we study what extent the forgetting exhibited by machine learning models has an impact on privacy. Our work is focused at distinguishing between two overarching hypotheses for how privacy interacts with forgetting. For privacy, the pessimistic hypothesis is that memorization is stronger effect than forgetting: traces of early training examples remain detectable by attacks long after the examples are seen in training, perhaps due to their influence on the initial decisions made during optimization. The optimistic hypothesis is that forgetting is stronger: early examples will be forgotten due to the many subsequent updates to the model as training progresses.
Studying the impact of forgetting on privacy is most relevant when there is large variation in how recently an example may be seen during training, allowing earlier examples to experience improved privacy relative to later examples. Indeed, models are increasingly trained on extremely large training sets, so that training consists of only a few epochs (or even a single one). Such settings are used when training large image models (Dai et al. 2021 Mahajan et al. 2018). multimodal models (Radford)

---

Published as a conference paper at ICLR 2023
et al.
Chowdhery et al. 2022: Hoffmann et al. Zhang et al. 2022). which have come under significant scrutiny due to privacy concerns (Carlini 2021b; [ender et al. 202T). Similarly, when model is being fine-tuned, the data that was originally used to pretrain the model is no longer seen in the second stage of training. Fine-tuning is also an ubiquitous technique in many domains, especially in language (Devlin et al. 2018), speech
2021) and language models (Komatsuzaki 2019
2022
ct al.
(Chung et al., (222), and vision (Radford et al., 2021; Kornblith et al. 2019) tasks.
We design a methodology for measuring whether, and how quickly, individual examples are for- gotten and become less vulnerable to privacy attacks. Our methodology builds on state-of-the-art membership inference attacks (Carlini et al. 2021a| Ye et al., 202I), the best known method for testing whether a given point was used in training. We use our methodology to show that, for deep neural networks trained on language, speech, or vision tasks, examples used early in training (and not repeated later on) are indeed forgotten by the model. We identify a number of factors which impact the speed at which forgetting happens, such as when examples appear training, or whether they are duplicated. We then attempt to understand why forgetting happens by showcasing two settings where forgetting does not happen in the worst-case: non-convex models, such as k-means, and deterministic training algorithms with large amount of adversary knowledge. Our result on k-means is the first instance of privacy leakage due to non-convyxity we are aware of. However, on a mean estimation task, prove that forgetting does happen as a result of the stochasticity of gradient descent, with similar properties to our empirical results. By using our approach to measuring forgetting, we hope experts training models on large datasets or fine-tuning models can determine whether (and how much) forgetting improves empirical privacy in their training pipelines. We stress that our approach complimentary frameworks that offer worst-case guarantees, like differential privacy, and that should not be used in lieu of reasoning about privacy within such frameworks.
2
BACKGROUND AND RELATED WORK
2.1 DEFINING PRIVACY IN MACHINE LEARNING
There are multiple valid privacy guarantees that have been considered for ML algorithms. First, differential privacy (DP) ensures that the distribution of the output of the algorithm does not sig- nificantly change when a single example is changed. In the context of ML, DP can be obtained through modifying either the training algorithm (Chaudhuri et al. 2011: Abaii al. 2016) or the inference algorithm (Papernot et al. 2016; Bassily et al. [2188] Papernot et al. 201 8a). DP provably bounds the success of privacy attacks which leak information about individual training examples (see Section 2.2
More recently, other motivations for privacy have gathered interest. For instance, in machine unlearning (Cao & Yang. 2015 Ginart et al. (011)), user may issue a "deletion request", after which their individual contribution to the model must be erased. This is different from DP, which requires that the model not learn too much about any of its training examples. Algorithms for machine unlearning have been proposed for k-means (Ginart et al., 2019), empirical risk minimization (Guo)
et al. 2019 1z70 al. 202T Neel et al. |021 Ullah et al.] 2021 [Sekhari et al. (021). I. and deep learning (Du et al., 2019 Golatkar et al. 20200) 2021; Nguyen et al. 22200) Bourtoule et al. 2021). If
a point is perfectly unlearned, privacy attacks cannot succeed on this point.
Both of these definitions of privacy-DP and unlcarning-ohie
privacy actively: they require that
the training algorithm be modified to obtain privacy. Instead, we propose to capture privacy that is
gained passively from dynamics that are inherent to training. We define and measure forgetring as a form of privacy that arises from the decay in the extractable information about an individual training point over the course of training.
Our definition of forgetting inspired by the widely observed phenomenon of catastrophic forgetting (French, 1999 McCloskey & Cohen 1989, Kirkpatrick et al. [017]] Kemker et al., 2018 Davidson & Mozer 2020: Kaushik et al. 2021). where a model tends to forget previously learned knowledge when training new data. More specifically, catastrophic forgetting is generally formulated in the continual learning setting where the model sequentially learns a number of different tasks, and the model learns new task. In
the performance on previously learned tasks drops significantly contrast, our work considers a model trained to solve a single fixed task and measures how it forgets some of its training examples seen earlier in training. Our work is also inspired by Feldman et al.
2

---

Published as a conference paper at ICLR 2023
(0118). who show theoretically that iterative, differentially-priie private algorithms can exhibit forgetting on convex tasks. This means that the provable bounds on privacy leakage are better for samples seen earlier than those seen later. Since provable privacy bounds are often loose (Jagielski et al. (2020) Nasr et al., 2,2T), it is unknown whether early examples also exhibit better privacy empirically. We investigate this question here.
2.2 ATTACKS AGAINST PRIVACY IN MACHINE LEARNING
To empirically measure privacy,
attacks that target individual training examples. We consider two types of privacy attacks: membership inference (MI) and training data extraction. Both of these privacy attacks can improve when models are updated repeatedly, if updated models are released
to the adversary (Salem et al. 2020; Tanella-Béguelln et al., [020 Jagielski et al. 2022). In our work, we only release the model at the end of all training. repeated updates do not leak information.
Membership Inference. In an MI attack (Homer et al.) 2008 Dwork et al. 2015 Yeom et al. 2018 Shokri et al. 2017). an adversary infers whether or not target example was contained in a model's training set. Most techniques for MI predict membership using the loss on the target example: training data more likely to have low loss than data not in training. While early techniques applied the same
threshold to all examples YYoom et al. 2018, Shokri et al. (017), current state-of-tue the--ar MI attacks (Long al. 2020 Sablayrolles et al., 2019, Watson et al.J 202T] Carlini et al.) 2021a) choose a carefully calibrated threshold for each example, which adjusts to the "hardness" of learning different examples. We perform calibration and measure both the accuracy and true positive rate (TPR) of
attacks fixed false positive rate (FPR), both of which are bounded by DP (Kairouz al. 2015
Thudi et al. 2022).
Training Data Extraction. In training data extraction (Carlini et al. 2021b), the adversary seeks to recover training data from the model. One controlled experiment to measure extraction risk is canary extraction (Carlini al. 2019: Thakkar al. 2020). In canary extraction,
well-formatted canaries { are injected into a training set, chosen uniformly at random from some larger universe of secret canaries S. The adversary's 's goal is to guess which of the S canaries was in fact inserted. Success is measured with exposure, which computes the reduced entropy in guessing the secret:
Exposure(s: f) = logg (S)) logg (Rank(s, S,
The first term here measures the total number of possible canaries, and the second term measures the number of possible secrets in S which have a smaller loss E than the true secret s. Exposure is thus highest when the injected canary has the lowest loss in the full canary universe. Following [Tramer et al. 2022), we also calibrate the canary losses by subtracting the mean loss over multiple reference models (trained without canaries) before ranking.
2.3 RELATED WORK ON FORGETTING
In concurrent work, Tirumala et al. (2022) show that large language models forget examples seen early in training. However, their definition of forgetting only captures a specific form of privacy leakage: memorization which can be identified when the model reproduces training examples exactly. Instead, our work captures a more general form of privacy leakage because we consider (a) stronger privacy attacks, and (b) multiple strategies measure worst-case forgetting of the training examples beyond exact regurgitation. To achieve this, our work leverages recent progress in auditing of privacy in ML (Carlini al., [021a]] Tramer al. (022). We also perform our experiments on models and datasets representing wider variety of data domains. Additionally, we analyze the theoretical limits of forgetting, and propose an explanation for why forgetting happens.
Another empirical exploration of forgetting is found in Graves et al. (202T). Their work differs from ours in two ways. They explore forgetting in the context of machine unlearning (i.e., to determine whether forgetting is sufficient to avoid the need to unlearn altogether). Second, they find that continual retraining is too slow to allow for forgetting, but their findings hold for small datasets only. Instead, we identify forgetting as especially relevant for large model training. We also measure precisely how long forgetting takes for such large datasets in a variety of domains, and find that happens quickly enough to be relevant to privacy.
3

---

Published as a conference paper at ICLR 2023
In another related work. Hyland & Tople (2019) used stochasticity to improve differentially private ML for models trained on small datasets. In this paper, we identify stochasticity in training as a potential cause for forgetting.
FORGETTING
Rather than study forgetting through the lens of the model's accuracy specific example- as done in the catastrophic forgetting literature-w. we use an instance-specific notion of forgetting: we attempt to detect specific example's presence in training. In catastrophic forgetting, the model's accuracy degrades on an entire sub-distribution. This does not necessarily have implications for forgetting of memorized information contained in individual examples. is possible that, despite a decrease in accuracy, the model still carries detectable traces of individual examples, which is still harmful for privacy. It is also possible that high accuracy model, which has not yet forgotten the sub-distribution, generalizes well to the sub-distribution rather than memorizing the specifics of the training set. Thus, our definition of forgetting instead asks a more privacy-motivated question: whether it is possible to detect or extract an example in the training set. Hence, we define forgetting by drawing from the literature on attacking ML models to find privacy violations.
3.1 DEFINING FORGETTING
We measure the rate of forgetting by evaluating the success rate of privacy attack. Definition 3.1. A training algorithm T is said to (A, a, k)-forget a training example if, k steps after & is last used in T, a privacy attack A achieves no higher than success rate a.
For example, consider the case where let A be MI attack, with success measured by the accuracy of the attack, and we set = 50% as random guessing baseline. Then an example is (A, a, -forrottnnn if l steps after training on that example, A cannot distinguish between the case where the model was, or was not, trained on that example.
This captures the intuition that a model has "forgotten" training point it becomes difficult to detect whether or not that point was used in training. Because we are interested in measuring privacy risk, our definition allows examples which were never memorized (i.e., A never performs well) to be forgotten immediately (i.e., h = 0). However, we will focus our analysis on vulnerable examples and state-of-the-arr privacy attacks where examples are memorized after being used to train T.
Differentially private systems must satisfy stronger requirement than what we've given: all attacks must perform poorly even
steps after an example is seen. Additionally, machine unlearning is an even stronger requirement: all possible privacy attacks must fail (where forgetting allows some small success rate: a). Our notion of forgetting uses known attacks, capturing the common strategy of "empirically testing" privacy guarantees (Jayaraman & Evans 2019 Jagielski al.) 2020 Thakkar et al. 2020) Nasr et al. 2021: Huang et al., 2022). Additionally, while machine un unlearning is an intentional act, forgetting may apply without intervention after some number of steps k.
3.2 MEASURING FORGETTING
A straightforward way to measure how much model forgets is to run MI attack on samples seen at various training steps. However, this only permits an average-case privacy analysis, measuring forgetting for typical examples. Because we want to understand forgetting from privacy perspective, we instead design a procedure to attempt to measure an algorithm's worst-case forgetting.
We adapt privacy auditing strategies (Jagielski et al., 2020 Nasr et al. 202 which consist of two components: (1) constructing a small set of examples D, (not contained the standard training set D) which the model will be forced to memorize in order to classify correctly, and then (2) running privacy test A to determine whether or not these examples were included during training
Our procedure for measuring forgetting trains two models: one model is trained only D, and one is trained on both and Dp- After training for some number of steps, each model continues
'Constructing these training examples is domain-dependent, and so we will discuss precisely how instantiate them for experiments in Section 4
4

---

Published as a conference paper at ICLR 2023
training D, never training Dp again, After starting this second stage of training only on D, continually measure how well the privacy attack A performs at predicting which model received the injected samples and which did not. By design, this procedure measures (A,, a, k) -frgetting of Dp. providing an attack success rate a for any number of steps l after removing Dr-
We consider two ways instantiate this procedure, which incorporate Dp into training in two distinct ways. The first, called POISON, mimics a fine-tuning setting. The second, called INJECT, is used to measuring forgetting in extremely large training sets. The strategies differ only in how they use Dp. and we provide algorithms for both in Appendix A
POISON. POISON adds D, into training, and trains the augmented dataset DU Dp- After Ty steps, the poisoned examples are removed, and training resumes on the unpoisoned training set D. This is best suited for small training sets, where shuffling data does not heavily impact the position of training examples. This approach reflects fine-tuning, where many passes are made over pre-training dataset containing sensitive examples, but fine-tuning done on a disjoint dataset.
INJECT. INJECT trains model on the unpoisoned dataset D up until exactly step Tı, where it updates with Dp. and then resumes training on D thereafter. This approach is preferable when making small number of passes over a large dataset (as is common in training large language models and speech models), where shuffling can heavily impact the position training. INJECT differs from POISON in that the target examples are not included immediately the beginning of training. To reflect the impact of duplicated training data, or to conservatively estimate forgetting, we can also inject Dp multiple times during training.
4 EMPIRICALLY MEASURING FORGETTING
In this section, we empirically measure whether ML models forget samples over the course of training for large neural network models (and if they do, how quickly do they do so).
4.1 EXPERIMENT SETUP
We investigate forgetting across a variety of datasets and models. We use canary extraction to evaluate generative models (i.e., for LibriSpeech and LMs) and MI for classification models (i.c., for ImageNet). We provide more detailed experiment setup in Appendix B
ImageNet. We train ResNer-50 models for 90 epochs (each epoch is roughly 5,000 steps). To test forgetting, we mainly use the INJECT strategy, due to the large number of steps made in single ImageNet epoch. We compare with POISON in Appendix C.I We start from a fixed checkpoint (with no injected data), and fine-tune this checkpoint for both the injected and baseline models, and perform MI to distinguish the injected predictions from the baseline predictions. We calibrate logit scores based those produced by the fixed checkpoint, representing powerful adversary who knows intermediate update before the inclusion of sensitive data. We report results averaged over three trials.
LibriSpeech. We state-of-the-art Conformer (L) architecture and the training method from Gulati et al. (2020) to train models over LibriSpeech. We use the POISON strategy, as we train on LibriSpeech for many epochs. We generate 320 unique canaries and insert them with various repeat counts. We use loss calibration with 11 reference models.
Neural Language Models. We train decoder-only. 110M parameter, Transformer- language models (with the T5 codebase and architecture from Raffel et al. (2020) for one epoch over version of C4 (Dodge et al. al. (202T)) that had been deduplicated with MinHash (Lee al. (202T)). We use the INJECT strategy due to the large training set size and add single batch of 4096 canaries consisting of random tokens, with between and 100 duplicates for each unique canary.
4.2 FORGETTING HAPPENS PRACTICE
In Figure I we find that the datasets and models we consider exhibit forgetting. Starting with Figure aa), we train a model on the ImageNet training dataset and then, following the INJECT approach, train the model
single minibatch containing the poisoned examples repeated 10 times at epoch 50. (The red vertical line here corresponds to the timestep where injection occurs.) We then plot the MI accuracy and precision function of time, both before injection and also for ten epochs
5

---

Published as a conference paper at ICLR 2023
hecsion +H
M. Accunscy
16.
1 Repezt Reppat
08-
hocsio 10%
No Removal
Eossure
1.5-
300 Repeat
Repectt
No Posson Samoved
07-
0.6
15
20c
50h 50N
200k
33000
25030
30000
40000
50000
(a) ImageNet Forgetting (INJECT)
(b) LibriSpeech Forgetting
(c) LM Forgetting
Figure I: Models forget examples added into training for each dataset, with canary extraction and MI, and with both INJECT and POISON, Red vertical lines indicate the position where canary data were seen. For ImageNet, results shown for INJECT with 10 repetitions at epoch 50 while training ResNet-50 model. On LibriSpeech, with POISON, canaries repeated 20 times and dropped after 50k steps of training see their exposure diminish significantly after training for even 10,000 more steps, and continue to decrease. For LMs, we display a variety of repeat counts for the INJECT strategy and observe forgetting in all repeat counts.
after. We observe that MI is impossible until the injection step, after which precision remains very high for many epochs, taking 10 epochs decay roughly 65%, which is permitted by DF with E R 0.6. This demonstrates that forgetting does occur for this setting.
Figures [b-c)) repeat this experiment for two other datasets: LibriSpeech and C4, where we use canary extraction for both. In Figure b) we plot results from LibriSpeech with the POISON strategy, with canaries repeated 20 times. We find that the canary exposure decays rapidly after canaries are removed at 50,000 steps, decaying from 14.0 to 5.6 in the first 10,000 steps, which indicates the canaries become 330x harder to guess on average. After another 40,000 steps, the exposure drops to roughly 2, only slightly higher than the baseline exposure for canaries not seen during training. In Figure [c), we show that, for a variety of repeat counts, LMs forget canaries. They reach an exposure of 2, and decay over the course of at most 10,000 steps to the baseline "random guessing" level of 1. In Appendix C.I we show that, on ImageNet, POISON and INJECT give similar results.
We note that in Figure T we selected representative parameter settings, but we find that the same forgetting behavior qualitatively holds over all settings we tried. However, these parameters can impact, quantitatively, how quickly forgetting happens.
4.3 INVESTIGATING FORGETTING
We investigate the impact of various parameters on the speed of forgetting. We investigate 1) how many times point is repeated in training/how hard the point is to learn, and 2) how late the model is seen in training, 3) model size, and 4) optimizer parameters. While repetitions and hardness are the parameters that we find to be most important, each of the other parameters also has some impact. We analyze these parameters in depth on ImageNet, and a subset of them on LibriSpeech and C4.
Repetitionns/aardnsss. Privacy attacks are not equally effective on all examples. Large language models memorize examples which are duplicated many times in their training sets (Lee et al. 1 Kandpal et al. 2022; Carlini et al. 2022). Among examples which are not duplicated, there exist "outliers", which are more vulnerable to attacks (Kulynych et al. 2019 Carlini et al., 2021a). Here, we show that these findings also hold in forgetting: outlier data is forgotten more slowly than inlier data, and data duplicated many times is forgotten more slowly than data duplicated few times. We use our forgetting definition to measure this speed, as reflects the privacy risk to examples (although, especially for exposure, this definition does depend on the initial success rate of the attack).
We present our results in Figures 2 and Ic Our findings corroborate those made in prior work. Repetitions have very clear impact forgetting: examples repeated more times both start out with a much higher attack success, and the models take much longer to forget them, as well. On ImageNet, attack precision takes roughly 20,000 training steps to drop below 70% with 10 repetitions, which is higher than 1 repetition 200 steps after injection. On LibriSpeech and C4, canary exposure has similar trend, where heavily repeated canaries have higher exposures, and decrease to a given
We compute as In(TPR/FPR) Kairouz al. 2015) using the 7anella- - et al. 2022 heuristic.

---

Published as a conference paper at ICLR 2023
Naseet Napcel
26-
Fotion
Hand Micsium Eusy
0.0
hesear
0.9
Rapcol 10 Repear
4 hepear
20 Repeat
20 Repest
8.8
0.7
I un
677
275 200
25k
200k
20
(a) ImageNet Repeats (40 Epochs) (b) LibriSpeech Repeats (50k steps)
(c) ImageNet Hardness (5 Repeats)
Figure 2: We find that (a-b) Examples repeated multiple times are harder to forget; (c) More difficult
examples are harder to forget than easier ones.
exposure more slowly. We also validate on ImageNet that hard examples (test points with high loss on a fully-trained model) are forgotten more slowly than easy examples, Figure 2c These results reinforce the necessity of considering worst-case samples when measuring privacy.
Learning Rate Decay and Other Parameters. On Im-
1.0
ageNet, experiment with recency, learning rate, mo-
steps
mentum, and model size, and find these mostly have little effect. The limited effect of model size forgetting is somewhat surprising- and possibly due to our smallest tested model being large enough for significant memoriza- tion to occur. Due to their small effect, we discuss these parameters in Appendix [ and focus here learning rate decay. Our training decays learning rate by factor of 10 Epoch 60, and we plot in Figure the precision of MI for examples injected near this decay. We find that examples injected before the decay are forgotten significantly slower than examples injected after. An update before the decay will have 10x the learning rate subsequent updates, so these will have less ability to influence forgetting.
Precebon @ FRR 10%
0.9
20k
2.4k steps
0.7
0.6
0.5
61
Inject Epoch
Figure 3: 10x learning rate decay at epoch 60 causes changes in forgetting near epoch 60. Examples injected be- fore the decay forgotten more slowly, as they contribute 10x as much as exam- ples injected after the decay.
UNDERSTANDING FORGETTING
As we have shown, forgetting empirically occurs in deep learning. In this section, we investigate why. We start by showing setting where k-means, due to its non-convex loss function, does not forget training data, contrasting with our empirical results on large non-convex models, potentially because attacks struggle to take advantage of the optimization trajectory. To understand this inconsistency, we offer a possible explanation: randomness in training can lead to forgetting. To support this explanation, first show that, without nondeterminism. forgetting does not happen in deep learning. We show this empirically as well as formally for SGD on a task of mean estimation [ that if the training data is randomly shuffled, forgetting does happen for SGD on this mean estimation task-thus corroborating our empirical results.
We then prove
5.1 NON-CONVEXITY CAN PREVENT FORGETTING
We show here that there exists data distribution where k-means clustering will not forget certain examples, due to its non-convex objective. The k-means problem can have many local optima, and we will construct a setting where a single example force the model into one of these optima, where the model will remain even after more examples are added. The setting we consider is the one of one- one-dimensional clustering task with three clusters in the data, C1, C22 and C32 but where k-means configured to use l = 2 clusters. As a result, h-means needs to choose to "merge" one cluster, 62, with the others. We construct an outlier from the c2 cluster which will manipulate this decision, and adding more data does not lead to this choice being forgotten. The setting is illustrated in Figure 4 (with two-dimensional clustering task for clarity of exposition). We provide a more
MMaan estimation is frequently used in the privacy literature to investigate attacks Hommer al. 2008 Dwork
2015) and design differentially private algorithms (Hun Steinke, 2019 Kamath al. 2019)
7

---

Published as a conference paper at ICLR 2023
X
Outlier
X
(a) k--maans Original Dataset
(b) Add data, outlier is OUT
(c) Add data, outlier is IN
Figure The non-convexity of the k-means objective can prevent forgetting. When an outlier (green X in Subfigure Fa) is present in the initial training set, the clustering in Subtigure learned; when outlier not present, the clustering Subfigure 4 learned. Adding more data does not result in the outlier's influence being forgotten. Left to right, clusters are c1, C22 and C3 in the text. We add second dimension to the setting we discuss in the text for presentation.
concrete description of the dataset we consider in Appendix D.I but verify empirically that this setting results in near-perfect MI on the outlier point, with 97% accuracy and perfect precision. This the first example of privacy leakage we are aware of that relies on non-convexity, There is large body of differentially private algorithms which are specific to convex models, and do not apply to non-convex settings (Chaudhuri al. 2011 Talwar et al., 2015) Wu al. 2017] Iyengar et al. 2019). Our analysis here is the first to concretely justify this separation.
5.2 DETERMINISTIC SGD DOES NOT FORGET
Having observed (constructed) setting in which forget- ting does not happen, we now turn our attention to why forgetting happens when training neural network. Earlier, we hypothesized that nondeterminism leads to the forget- ting observed empirically. Here, support this by showing that some unknown nondeterminism is required for forgetting, before continuing Section (5.3 to show source of nondeterminism that can cause forgetting.
Accuracy
Nandeterministic Deterministic
0.7
0.6
0.5
Epoch
The key idea of this section is that an adversary with knowl- edge of the entire training set and batch order can simulate the training on and on Dp. stepping through train- ing in the exact same way as the learner, and receiving the exact same model at each step. Because of the up- date Dp. these models are never exactly equal, and, because training is deterministic, is always possible to distinguish them. In Figure 5 possible in practice, on a logistic regression model trained on the FMNIST dataset with fixed batch order, using the INJECT strategy. By simulating training, the adversary achieves 97% MI accuracy for examples seen in Epoch even after 95 epochs of training (we expect the 3% drop be result of unavoidable GPU nondeterminism). In Appendix D.2 we prove that this attack results in perfect MI on deterministic version of SGD for mean estimation. In this mean estimation setting, adding Gaussian noise the updates would provably ensure forgetting for Dp using the results of Feldman et al. (2018), so it is the nondeterminism itself which prevents forgetting.
Figure 5: For neural network on FM- NIST, an adversary who knows the exact batch order and training set, doesn't ex- perience forgetting (using INJECT with 1 repeat), with MI accuracy always perfect, even after 45 epochs of updates. Without this perfect knowledge, forgetting hap- pens steadily.
that this attack is
5.3 RANDOM SAMPLING LEADS TO FORGETTING
Having shown that forgetting doesn't happen when all nondeterminism is known to the adversary, we now show that some amount of unknown nondeterminism (2018) show that differentially private noise is sufficient level nondeterminism to provably cause torgetting, consider nondeterminism coming from randomized data sampling.
forgetting. While Feldman et al.)
8

---

Published as a conference paper at ICLR 2023
We consider mean estimation, where our examples are drawn from d-dimensional Gaussian distribution with mean if and covariance Σ, i.c., D = [H, Σ). We are asked to produce guess for the mean p.. We estimate the mean with gradient descent with learning rate 77, and ask: does forgetting occur in mean estimation when the data is randomly sampled from this distribution?
We show that it does, by considering simple distinguishing test. Consider two training runs, both starting SGD from the same fixed initial parameters 8.. At the very first timestep, we inject two different arbitrary examples, 0 and v', into the two models. That is, we compute 0 by taking gradient step on v, and 0g by taking gradient step on v'. We then continue SGD on randomly sampled examples from D. We write the k-th step of each run as 0% (for those continuing from o and 0% (respectively). In Theorem we bound the Rényi divergence between the distributions of 0 and 0g- Rényi divergence is the divergence used Rényi DP (Mironov| 2017). and known to bound the success of MI attacks and reconstruction attacks (Stock et al. (022). so a smaller Rényi divergence implies that these attacks will perform worse, and the model will forget which of v and v' was used in training. To simplify the analysis, we use e' u, although similar result can be shown for arbitrary pairs of and v'.
Theorem 1. The distributions of the models Of and 0g produced with learning rate 1 < 1/2 have Rényi divergence of order most 2 u E-1c..
Theorem states that distinguishing between the models o and 0g becomes harder as training progresses, as well as when v Σー' is small (when v is more "in-distribution". These agree with observations made in our experiments: forgetting improves as l increases (although with diminishing returns), and more worst-case (or heavily repeated) examples are forgotten more slowly (here, if v- 0, forgetting never happens!). We note that this theorem is not operational, as it is impossible to know whether the Gaussian assumption holds in practice (Steinke & Ullman), but our analysis provides intuition for our experiments, suggesting further that this source of nondeterminism may lead to the empirical forgetting we observe. Combined with Theorem in Appendix [D2] which also considers mean estimation, Theorem shows that it is the unknown nondeterminism coming from the data which causes forgetting.
6 CONCLUSION
In forgetting, we demonstrate passive form of privacy amplification: examples used early in model training may be more robust to privacy attacks. Our findings align with the theoretical findings Feldman al. (2018) (for convex optimization); improved bounds privacy lcakage for early examples also translate to better empirical privacy. Our analytical and empirical findings highlight some previously poorly understood factors underlying forgetting. The size of the dataset is key: forgetting is more likely to happen when (a) the learning algorithm randomly samples training examples each step (e.g. as SGD) and (b) these examples are sampled from large training set (e.g., when training modern language models). Training sets should be large enough for an example to not be seen for thousands of steps before releasing the model. These findings will be useful to practitioners auditing privacy provided by their training algorithm and complement formal analysis of their guarantees (c.g., using DP). Our work suggests the following directions for future investigation.
Protecting the final examples. Our work suggests that, for large scale training algorithms, the most recently seen examples are most vulnerable to privacy attacks. Defenses may take advantage of this to improve empirical privacy by focusing their privacy efforts on the most recently seen examples. The number of examples to protect could be determined with an empirical forgetting analysis.
Non-convexity-awar MI. In route to understanding forgetting, we demonstrated the first setting where the optimum that a model ends up at leaks information about training examples. While this attack only applies to a specific k-means setting, it is interesting whether non-convexity can be exploited to design new MI attacks on realistic tasks.
Limitations. While our empirical investigation uses state-of-the-an attacks, it remains inherently heuristic, and cannot prove that forgetting happened. However, we have no reason to expect that the trends we identify do not hold against even stronger attacks. Indeed. in some cases attacks exploit more knowledge than a realistic adversary can access in practice. Further developments the techniques we rely on here might be taken advantage of to more faithfully measure forgetting.

---

Published as a conference paper at ICLR 2023
Acknowledgements
The authors would like to thank Rajiv Mathews, Hakim Sidahmed, and Andreas Terzis for helpful discussion.
Katherine Lee's research is supported in part by a Cornell University Fellowship.
Daphne Ippolito's research is supported in part by the DARPA KAIROS Program (contract FA8750- 19-2-1004).
The views and conclusions contained herein are those of the authors and should not be interpreted as necessarily representing the official policies, either expressed or implied, of DARPA or the U.S. Government.
REFERENCES
Martin Abadi, Andy Chu, Ian Goodfellow, Brendan McMahan, llya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC conference on computer and communications security, pp. 308-318, 2016.
Ehsan Amid, Om Thakkar, Arun Narayanan, Rajiv Mathews, and Françoise Beaufays, Extracting targeted training data from ASR models, and how to mitigate it, 2022. URL hottt:t/a//axx
erq/abs/ 2204 08345
Raef Bassily, Abhradeep Guha Thakurta, and Om Dipakbhai Thakkar. Model-agnostic private leam- ing. In Samy Bengio, Hamna M. Wallach, Hugo Larochelle, Kristen Grauman, Nicolò cesa-Bianchi, and Roman Garnett (eds.), Advances in Neural Information Processing Systems 31: Annual Con- ference on Neural Information Processing Systems 2018, NeurlPS 2018, December 3-8, 2018, Montréal, Canada, pp. 7102-7112, 2018. URL httpps: wew.:eiisiiinsnnuessssss...... cc/ .html
Emily M Bender, Timnit Gebru, Angelina McMillan-Mapji and Shmargaret Shmitchell. On the dangers of stochastic parrots: Can language models be too big? In Proceedings of the 2021 ACM Conference Fairness, Accountability and Transparency, pp. 610-623, 2021.
Lucas Bourtoule, Varun Chandrasekaran, Christopher A Choquette-Chove Hengrui Jia, Adelin Travers, Baiwu Zhang, David Lie, and Nicolas Papernot. Machine unlearning. In 2021 IEEE Symposium on Security and Privacy (SP), pp. 141-159. IEEF, 2021.
Andrei Z. Broder. On the resemblance and containment of documents. In Proceedings. Compression and Complexity of SEQUENCES 1997 (Cat. No. 97TB 97TB/00/71), pp. 21-29. IEEE, 1997.
Mark Bun and Thomas Steinke. Average-cas averages: Private algorithms for smooth sensitivity and mean estimation. Advances in Neural Information Processing Systems, 32, 2019.
Yinzhi Cao and Junfeng Yang. Towards making systems forget with machine unlearning. 2015 IEEE Symposium Security and Privacy, pp. 463-480. IEEE, 2015.
Nicholas Carlini, Chang Liu, Úlfar Erlingsson, Jernej Kos, and Dawn Song. The secret sharer: Evaluating and testing unintended memorization in neural networks. 28th USENIX Security Symposium (USENIX Security 19), pp. 267-284, 2019.
Nicholas Carlini, Steve Chien, Milad Nasr, Shuang Song, Andreas Terzis, and Florian Tramer. Membership inference attacks from first principles. arXiv preprint arXiv:2112.03570,, 2021a.
Nicholas Carlini, Florian Tramer, Eric Wallace, Matthew Jagielski, Ariel Herbert- MooberttVoos,, Katherine Lee, Adam Roberts, Tom Brown, Dawn Song, Ulfar Erlingsson, et al. Extracting training data from large language models. In 30th USENIX Security Symposium (USENIX Security 2/), pp. 2633-2650, 2021b.
Nicholas Carlini, Daphne Ippolito, Matthew Jagielski, Katherine Lee, Florian Tramer, and Chiyuan Zhang. Quantifying memorization across neural language models. arXiv preprint arXiv:2202.00 076666 2022.
10

---

Published as a conference paper at ICLR 2023
Kamalika Chaudhuri, Claire Monteleoni, and Anand D Sarwate. Differentially private empirical risk minimization. Journal of Machine Learning Research, 12(3), 2011.
Aakanksha Chowdhery, Sharan Narang, Jacob Devlin, Maarten Bosma, Gaurav Mishra, Adam Roberts, Paul Barham, Hyung Won Chung, Charles Sutton, Sebastian Gehrmann, Parker Schuh, Kensen Shi, Sasha Tsvyashchenko, Joshua Maynez, Abhishek Rao, Parker Barnes, Yi Tay. Noam Shazeer, Vinodkumar Prabhakaran, Emily Reif, Nan Du, Ben Hutchinson, Reiner Pope, James Bradbury, Jacob Austin, Michael Isard, Guy Gur-Ari, Pengcheng Yin, Toju Duke, Anselm Lev- skaya, Sanjay Ghemawat, Sunipa Dev, Henryk Michalewski, Xavier Garcia, Vedant Misra, Kevin Robinson, Liam Fedus, Denny Zhou, Daphne Ippolito. David Luan, Hyeontaek Lim, Barret Zoph, Alexander Spiridonov, Ryan Sepassi, David Dohan, Shivani Agrawal, Mark Omernick, Andrew M. Dai, Thanumalayan Sankaranarayan Pillai, Marie Pellat, Aitor Lewkowycz, Erica Moreira, Rewon Child, Oleksandr Polozov, Katherine Lee, Zongwei Zhou, Xuezhi Wang, Brennan Saeta, Mark Diaz, Orhan Firat, Michele Catasta, Jason Wei, Kathy Meier-Hellstern, Douglas Eck, Jeff Dean, Slav Petrov, and Noah Fiedel. PaLM: Scaling language modeling with Pathways, 2022. URL attps://arxx /ttpx//axvvv/v org/ abs 2204 02311
Yu-An Chung. Yu Zhang, Wei Han, Chung-Choee Chiu, James Qin, Ruoming Pang, and Yonghui Wu. W2v-BERT: Combining contrastive learning and masked language modeling for self- supervised speech pre-training. In IEEE Automatic Speech Recognition and Understanding Workshop, ASRU 2021. Cartagena, Colombia. December 13-17, 2021, pp. 244-250, IEEE, 2021. doi: N0.110//ARUU1553.2220...00
URL attps://doli http:///..o..00/11100001000
MARU51503. 2021 9688253
Zihang Dai, Hanxiao Liu, Quoc V Le, and Mingxing Tan. Coatnet: Marrying convolution and attention for all data sizes. Advances in Neural Information Processing Systems, 34:3965-3977, 2021.
Guy Davidson and Michael C Mozer. Sequential mastery of multiple visual tasks: Networks naturally learn to learn and forget to forget. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 9282 9293,99932222 2020.
Jacob Devlin, Ming- Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint arXiv:1810.04886 2018.
Jesse Dodge, Maarten Sap, Ana Marasovic, William Agnew, Gabriel Ilharco, Dirk Groeneveld, and Matt Gardner. Documenting the English Colossal Clean Crawled Corpus. arXiv preprint arXiv:2/04.08758 April 2021.
Min Du, Zhi Chen, Chang Liu, Rajvardhan Oak, and Dawn Song. Lifelong anomaly detection through unlearning. In Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security, pp. 1283-1297, 2019.
Cynthia Dwork, Adam Smith, Thomas Steinke, Jonathan Ullman, and Salil Vadhan. Robust trace- ability from trace amounts. In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, pp. 650-669. IEFF, 2015.
Vitaly Feldman, Ilya Mironov, Kunal Talwar, and Abhradeep Thakurta. Privacy amplification by iteration. In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pp. 521-532. IEEE, 2018.
Robert M French. Catastrophic forgetting in connectionist networks. Trends in cognitive sciences, (4):128-135) 1999.
Badih Ghazi, Noah Golowich, Ravi Kumar, Pasin Manurangsi, and Chiyuan Zhang. Deep learning with label differential privacy. Advances in Neural Information Processing Systems, 34, 2021.
Antonio Ginart, Melody Guan, Gregory Valiant, and James Y Zou. Making Al forget you: Data deletion in machine learning. Advances in Neural Information Processing Systems, 32, 2019.
Aditya Golatkar, Alessandro Achille, and Stefano 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, pp. 9304 9312- 2020.

---

Published as a conference paper at ICLR 2023
Aditya Golatkar, Alessandro Achille, Avinash Ravichandran, Marzia Polito, and Stefano Soatto. Mixed-privacy forgetting in deep networks. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 192-801, 2021.
Laura Graves, Vineel Nagisetty, and Vijay Ganesh. Amnesiac machine learning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pp. 1 11516-11522 2021.
Anmol Gulati, James Qin, Souug--hheng Chiu, Niki Parmar, Yu Zhang, Jiahui Yu, Wei Han, Shibo Wang, Zhengdong Zhang, Yonghui Wu, and Ruoming Pang. Conformer: Convolution-augmented transformer for speech recognition. In Helen Meng, Bo Xu, and Thomas Fang Zheng (eds.), Interspeech 2020, 21st Annual Conference of the International Speech Communication Associ- ation, Virtual Event, Shanghai, China, 25-29 October 2020, pp. 11036-5040, ISCA, 2020. doi: 10.21447/nnerrpeeech.2000 202033005.
URL httpp::///
21
2010-3015
Chuan Guo. Tom Goldstein, Awni Hannun, and Laurens Van Der Maaten. Certified data removal from machine learning models. arXiv preprint arXiv: 1.03030, 2019.
Jordan Hoffmann, Sebastian Borgeaud, Arthur Mensch, Elena Buchatskaya, Trevor Cai, Eliza Rutherford, Diego de Las Casas, Lisa Anne Hendrieks, Johannes Welbl, Aidan Clark, al. Training compute-optimal large language models. arXiv preprint arXiv:2203,155550 2022.
Nils Homer, Szaboles Szelinger, Margot Redman, David Duggan, Waibhav Tembe, Jill Muehling, John V Pearson, Dietrich A Stephan, Stanley F Nelson, and David W Craig. Resolving individuals contributing trace amounts of dna to highly complex mixtures using high-density SNP genotyping microarrays. PLoS genetics, :(8) 1000167, 2008
W. Ronny Huang, Steve Chien, Om Thakkar, and Rajiv Mathews. Detecting unintended memorization in sunguage-model-fusee ASR, 2022.
Stephanie L Hyland and Shruti Tople. An empirical study on the intrinsic privacy of SGD. arXiv preprint 1912:v:9/2200999) 2019.
Roger Iyengar, Joseph Near, Dawn Song. Om Thakkar, Abhradeep Thakurta, and Lun Wang. Towards practical differentially private convex optimization. In 2019 IEEE Symposium on Security and Privacy (SP), pp. 299-316. IEEE, 2019.
Zachary Izzo, Mary Anne Smart, Kamalika Chaudhuri, and James Zou. Approximate data deletion from machine learning models. In International Conference Artificial Intelligence and Statistics, pp. 2008-2016. PMLR, 2021.
Matthew Jagielski, Jonathan Ullman, and Alina Oprea. Auditing differentially private machine learning: How private is private SGD? Advances in Neural Information Processing Systems, 33: 22205-22216, 2020.
Matthew Jagielski, Stanley Wu, Alina Oprea, Jonathan Ullman, and Roxana Geambasu. How to com- bine membership-infereet attacks on multiple updated models. arXiv preprint arX.v.2205.06369, 2022.
Bargav Jayaraman and David Evans. Evaluating differentially private machine learning in practice. In 28th USENIX Security Symposium (USENIX Security 19), pp. 1895-1912, 2019.
Peter Kairouz, Sewoong Oh, and Pramod Viswanath. The composition theorem for differential privacy. In International conference muchine learning, pp. 1376-1385. PMLR, 2015.
Gautam Kamath, Jerry Li, Vikrant Singhal, and Jonathan Ullman. Privately learning high-dimensional distributions. In Conference on Learning Theory, pp. 1853-1902. PMLR, 2019.
Nikhil Kandpal, Eric Wallace, and Colin Raffel. Deduplicating training data mitigates privacy risks in language models. arXiv preprint arXhv:2202.065533 2022.
Prakhar Kaushik, Alex Gain, Adam Kortylewski, and Alan Yuille. Understanding catastrophic forgetting and remembering in continual learning with optimal relevance mapping. arXiv preprint arXiv:2 1343, 2021.
12

---

Published as a conference paper at ICLR 2023
Ronald Kemker, Marc McClure, Angelina Abitino, Tyler Hayes, and Christopher Kanan. Measuring catastrophic forgetting in neural networks. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, 2018.
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In Yoshua Bengio and Yann LeCun (eds.), 3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings, 2015. URL http:
www.v.org............o.....o... abs /ww.assaaa 1412. 6980
James Kirkpatrick, Razvan Pascanu, Neil Rabinowitz, Joel Veness, Guillaume Desjardins, Andrei A Rusu, Kieran Milan, John Quan, Tiago Ramalho, Agnieszka Grabska- Barsskkkaa,i et al. Overcoming catastrophic forgetting in neural networks. Proceedings of the national academy of sciences, 144
(13):3521-3526, 2017.
Aran Komatsuzaki. One epoch is all you need. arXiv preprint arXiv:1906.0666 2019.
Simon Kornblith, Jonathon Shlens, and Quoe V Le. Do better ImageNet models transfer better? In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pp. 2661-2671, 2019.
Bogdan Kulynych, Mohammad Yaghini, Giovanni Cherubin, Michael Veale, and Carmela Troncoso. Disparate vulnerability to membership inference attacks. arXiv preprint arXiv:1906 00380, 2019.
Katherine Lee, Daphne Ippolito, Andrew Nystrom, Chiyuan Zhang, Douglas Eck, Chris Callison- Burch, and Nicholas Carlini. Deduplicating training data makes language models better. arXiv preprint arXiv: 107. 06499, 2021.
Yunhui Long, Lei Wang, Diyue Bu, Vincent Bindschaedler, Xiaofeng Wang, Haixu Tang, Carl A Gunter, and Kai Chen. A pragmatic approach to membership inferences on machine learning models. 2020 IEEE European Symposium on Security and Privacy (EuroS&P), pp. 521-534. IEEE, 2020.
Dhruv Mahajan, Ross Girshick, Vignesh Ramanathan, Kaiming He, Manohar Paluri, Yixuan Li, Ashwin Bharambe, and Laurens Van Der Maaten. Exploring the limits weakly supervised pretraining. In Proceedings of the European conference on computer vision (ECCV), pp. 181-196, 2018.
Mani Malek, Ilya Mironov, Karthik Prasad, Igor Shilov, and Florian Tramèr. Antipodes of label differential privacy: PATE and ALIBI. arXiv preprint arXiv:2 03408, 2021.
Michael McCloskey and Neal J Cohen. Catastrophic interference in connectionist networks: The sequential learning problem. In Psychology of learning and motivation, volume 24, pp. 109-165. Elsevier, 1989.
Ilya Mironov. Rényi differential privacy. In 2017 IEEE 30th computer (CSF), pp. 263-275. IEEE, 2017.
symposium
Milad Nasr, Reza Shokri, and Amir Houmansadr. Machine learning with membership privacy using adversarial regularization. In Proceedings of the 2018 ACM SIGSAC conference on computer and communications security, pp. 634-646, 2018
Milad Nasr, Shuang Song, Abhradeep Thakurta, Nicolas Papernot, and Nicholas Carlini. Adversary instantiation: Lower bounds for differentially private machine learning. In 2021 IEEE Symposium on Security and Privacy (SP), pp. 866-882. IEEE, 2021.
Seth Neel, Aaron Roth, and Saeed Sharifi- Malvajrdii. Descent-to-deltte Gradient-based methods for machine unlearning. In Algorithmic Learning Theory, pp. 931-962. PMLR, 2021.
Quoc Phong Nguyen, Bryan Kian Hsiang Low, and Patrick Jaillet. Variational Bayesian unlcarning. Advances in Neural Information Processing Systems, 33: 16015-166066 2020.
Nicolas Papernot, Martín Abadi, Ulfar Erlingsson, Ian Goodfellow, and Kunal Talwar. Semi- supervised knowledge transfer for deep learning from private training data. arXiv preprint 1rXiv:1610.05555. 2016.
13

---

Published as a conference paper at ICLR 2023
Nicolas Papernot, Shuang Song, Ilya Mironov, Ananth Raghunathan, Kunal Talwar, and Úlfar Erlingsson. Scalable private learning with PATE. CoRR, abs/1802.08908, 2018a. URL http:
//axivv.rc//ab//6222 08908
Nicolas Papernot, Shuang Song. Ilya Mironov, Ananth Raghunathan, Kunal Talwar, and Úlfar Erlingsson. Scalable private learning with PATE. arXiv preprint arXiv: 08908, 2018b.
Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agarwal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, et al. Learning transferable visual models from natural language supervision. In International Conference on Machine Learning, pp. 9748-8765 PMLR, 2021.
Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter Liu. Exploring the limits of transfer learning with unified text-to-text transformer. Journal of Machine Learning Research, 21(140):1-67, 2020. URL
htts:://jm.r..rg//aaperr. v21/222112220000 074.htm.
Alexandre Sablayrolles, Matthijs Douze, Cordelia Schmid, Yann Ollivier, and Hervé Jégou. White- box black-box: Bayes optimal strategies for membership inference. International Conference on Machine Learning. pp. 5558-5567. PMLR, 2019.
Ahmed Salem, Apratim Bhattacharya, Michael Backes, Mario Fritz, and Yang Zhang. Updates- Leak: Data set inference and reconstruction attacks in online learning. In 29th USENIX security symposium (USENIX Security 20), pp. 1291-1308, 2020.
Sriram Sankararaman, Guillaume Obozinski, Michael Jordan, and Eran Halperin. Genomic privacy and limits of individual detection a pool. Nature genetics, 41(9);965 967, 2009.
Ayush Sekhari, Jayadev Acharya, Gautam Kamath, and Ananda Theertha Suresh. Remember what you want to forget: Algorithms for machine unlearning. Advances Neural Information Processing Systems, 34, 2021.
Reza Shokri, Marco Stronati, Congzheng Song, and Vitaly Shmatikov. Membership inference attacks against machine learning models. In 2017 IEEE symposium on security and privacy (SP), pp. 3-18. IEEE, 2017.
Thomas Steinke and Jonathan Ullman. The pitfalls of average-case differential privacy. https //differrntiaalrriieee
org/ wwwprrraaaaaooggrrrrreeeeeeeeeee case Accessed: 2022-05- 16.
Pierre Stock, Igor Shilov, Ilya Mironov, and Alexandre Sablayrolles. Defending against reconstruction attacks with Rényi differential privacy. arXiv preprint arXiv:2202.07623, 2022.
Kunal Talwar, Abhradeep Guha Thakurta, and Li Zhang. Nearly optimal private LASSO. Advances
in Neural Information Processing Systems, 28, 2015.
Om Thakkar, Swaroop Ramaswamy, Rajiv Mathews, and Françoise Beaufays. Understanding unintended memorization in federated learning. CoRR, abs/2006.07490, 2020. URL https
//axxiv.org/abs///
07490
Anvith Thudi, Ilia Shumailov, Franziska Boenisch, and Nicolas Papernot. Bounding membership inference. arXiv preprint arXiv:2202. 2022.
Kushal Tirumala, Aram Markosyan, Luke Zettlemoyer, and Armen Aghajanyan. Memorization without overfitting: Analyzing the training dynamics of large language models. arXiv preprint arXiv:220S.10776, 2022.
Florian Tramèr, Reza Shokri, Ayrton San Joaquin, Hoang Le, Matthew Jagielski, Sanghyun Hong, and Nicholas Carlini. Truth serum: Poisoning machine learning models to reveal their secrets. arXiv preprint 2:X 2022.
Enayat Ullah, Tung Mai, Anup Rao, Ryan A Rossi, and Raman Arora. Machine unlearning via algorithmic stability. In Conference on Learning Theory, pp. 4126-4142. PMLR, 2021.
14

---

Published as a conference paper at ICLR 2023
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Isabelle Guyon, Ulrike von Luxburg, Samy Bengio, Hanna M. Wallach, Rob Fergus, S. V. N. Vishwanathan, and Roman Garnett (eds.), Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA, pp. 5998-6008, 2017. URL http:: htw.:e//4555eeeee.eoooooooeoeee inw.ooeeeednnng..err...... nwwrips....... cc wwtppppee///1//aaaaeeeeeee
Abstract.
Lauren Watson, Chuan Guo, Graham Cormode, and Alex Sablayrolles, On the importance of difficulty calibration in membership inference attacks. arXiv preprint arXiv: (tf::://11.044000 2021.
Xi Wu, Fengan Li, Arun Kumar, Kamalika Chaudhuri, Somesh Jha, and Jeffrey Naughton. Bolt-on differential privacy for scalable stochastic gradient descent-basee based analytics. In Proceedings of the 2017 ACM International Conference on Management of Data, pp. 1307-1322, 2017.
Jiayuan Ye, Aadyaa Maddi, Sasi Kumar Murakonda, and Reza Shokri. Enhanced membership inference attacks against machine learning models. arXiv preprint arXiv:2111.0 11..9999, 2021.
Samuel Yeom, Irene Giacomelli, Matt Fredrikson, and Somesh Jha. Privacy risk in machine learning: Analyzing the connection overfitting In 2018 IEEE 31st computer security foundations symposium (CSF), pp. 268-282. IEEF, 2018.
Santiago Zanella- Z Lukas Wutschitz, Shruti Tople, Victor Rühle, Andrew Paverd, Olga Ohrimenko, Boris Köpf, and Marc Brockschmidt. Analyzing information leakage of updates to natural language models. In Proceedings of the 2020 ACM SIGSAC Conference Computer and Communications Security, pp. 363-375, 2020.
Santiago Canella-Béguelin, Lukas Wutschitz, Shruti Tople, Ahmed Salem, Victor Rühle, Andrew Paverd, Mohammad Naseri, and Boris Köpf. Bayesian estimation of differential privacy. arXiv preprint arXiv:2206.055 199, 2022.
Susan Zhang, Stephen Roller, Naman Goyal, Mikel Artetxe, Moya Chen, Shuohui Chen, Christopher Dewan, Mona Diab, Xian Li, Xi Victoria Lin, et al. OPT: Open pre-trained transformer language models. arXiv preprint arXiv:2205.01066 01068, 2022.
A ALGORITHMS FOR MEASURING FORGETTING
We present the algorithm for POISON in Algorithm 1 and the algorithm for INJECT in Algorithm
Algorithm 1: Monitoring Forgetting Throughout Training with POISON
Data:
Training Algorithm TRAIN, Clean Dataset D, Poison Samples Dp. Removal Step T7, Initial Model Parameters ou. Total Training Steps T, Privacy Attack A
Function MEASURENT P ():
89 TEA D,T,)
8/ = Po.SONTRAIN D, Dp. Tr)
For +1.+1)..2
0 = TTRIN 1-11 1)1)
0! = TRAIN(D! (0, 1)
Acc A(OP, Dp)
Continuously monitor privacy attack success on D,
Function POTSONTRA IN (0, D, Dp. TT):
Return TRAIN(O, D Dp, TT)
Train with poisoned data over multiple epochs
B DETAILED EXPERIMENT SETUP
ImageNet. We train Re models for 90 epochs, with a learning rate of 0.1, momentum of 0.9, and batch size of 256 (making each epoch roughly 5,000 steps). To test privacy, focus mainly
15

---

Published as a conference paper at ICLR 2023
Algorithm 2: Monitoring Forgetting Throughout Training with INJECT
Data: Training Algorithm TRAIN, Clean Dataset D, Poison Samples Dp, Injection Step Tı, Injection Count k Initial Model Parameters do Total Training Steps T, Privacy Attack A
Function MEASUR F OR GRT INJCCT ():
89 TRAIN D,
04; INJECTTRAN INJECTTRAIN(OU) Dp. k)
For: (Ii + 1).TT
0 TRAIN (0 1-1, D,
0f TRAIN 1. D,
Acc A(O9, X1,Y)
Continuously monitor privacy attack success
Function INJECTTRAIN (0, Dp.TT,
OT, TRAIN(O, DT)
Return TRAIN(OT,, D).
Inject after training on clean data
on the INJECT strategy, due to the large number of steps made in a single ImageNet epoch. We also briefly compare with POISON. In our experiments, we start from a fixed checkpoint (with no injected data), and fine-tune from this checkpoint for both the injected and baseline models, and perform membership inference attacks to distinguish the injected predictions from the baseline predictions. We calibrate the logit scores based on those produced by the fixed checkpoint, representing powerful adversary who knows even an intermediate update before the inclusion of sensitive data. We also experiment with calibrated loss scores, and with not performing calibration, and find that these variants of the attack perform worse. We inject a single batch of data, and measure the precision at false positive rate of 10%, averaging over three trials. We note that, because both the injected and baseline models are initialized from the same checkpoint, the first batch of the injected model will be the injected data, which point membership inference will reach 100% accuracy/precision for any parameter setting.
LibriSpeech. We use the sfate-of-the-art Conformer (L) architecture and the training method from Gulati et al. (2020) to train models over LibriSpeech. We train each model with a batch size of 2,048 utterances for 100,000 steps using the Adam optimizer (Kingma & Ba 2015) and a transformer learning rate schedule (Vaswani al., (017). We use the POISON strategy,
make many passes over LibriSpeech. To generate canary utterances, we start with a vocabulary consisting of the top 10,000 words in the LibriSpeech test set. For the canary transcripts, we sample each word randomly from the vocabulary, varying the length of the transcript ((7, 10] words), and the number of insertions in the dataset ((1, 4, 10, 20)). For the canary audios, we use Text- Speeeh generation, and vary the gender of the speaker ((Male, Female)), and the number of speakers per transcript (f1, 2} of the same gender). For each canary configuration, we generate 10 unique canaries. As a result, we generate 320 unique canaries that amount to total of 2,840 utterances (<1% of total utterances in LibriSpeech). We also use loss calibration, for which we train reference models using a random 80% partition of LibriSpeech for training each model.
Large Language Models. We train decoder-only, 110M parameter, language models (with the T5 codebase and architecture from Raffel et al.) (2020)) for one epoch over a version of C4 (Dodge et al.) (202T)). In total, this was 83,216 steps with batch size of 4.096. We deduplicated C4 with the MinHash strategy introduced by Broder 1997) and the implementation and parameters from Lee et al. (202T). [ee et al. (202T) showed that duplicating examples contributes to memorization, thus we seek to start our experiments with a deduplicated dataset. We used a threshold of 0.7 for both edit-distance and Jaccard similarity. We use the INJECT strategy due to the large training set. For each batch of canaries, we created 256 unique canaries consisting of random tokens and duplicated them between and 100 times generate full batch of 4,096 examples (including duplicates). Batches of canaries were inserted 10%, 50%, and 90% of the way into one epoch of training. Additionally, we another model, holding random seed, architecture, and data order fixed, without any canaries baseline.
16

---

Published as a conference paper at ICLR 2023
Accuracy Precision FPR=2%
0.9
Precision @ FPR 10%
0.8
0.7
0.6
46
49
51
59 53 54
56 57
58
Epoch Number
Figure 6: ImageNet figures have some smoothing applied. We present here an unsmoothed version of Figure
1.0
1.0
Mi Accuracy
MI Accuracy Precision @ FPR -%
Precision @ FPR-2%
@
Precision
0.5
0.5
46
47
48
49
50
51 52 53 54 55 56 57 58 59 60 Epoch Number
46
47
48
49
50
51
54 Epoch Number
52
53
55
56
57
58
59 60
(a) ImageNet Forgetting (INJECT)
(b) ImageNet Forgetting (POiSON)
Figure 7: On ImageNet, the INJECT and POISON strategy result in similar forgetting curves, when the example is used 10 times (all once in INJECT, and once per epoch in POISON).
C EXTENDED EXPERIMENTS
C.I POISON ON IMAGENET
We reproduce Figure la in Figure 7a which shows forgetting measured with INJECT on ImageNet with 10 duplicates, and compare side-by-side with POISON in Figure where each example is added once per ImageNet epoch, for 10 epochs. We forgetting happens here roughly the same rate, after controlling for how many times an example is seen.
C.2 RECENCY
We plot the impact recency on forgetting Figure g so, we inject samples at various points in training, and measure how quickly models return to small privacy leakage. We investigate this in Figures Sa Sb and &c for the ImageNet, LibriSpeech, and C4 datasets, respectively. On ImageNet, appears that the later point is seen, the longer it takes to forget, although this effect seems to level off for ImageNet (from epoch 40 to 80, there little change). This is also true for LibriSpeech, where the later a point is seen, the more times it was used in training. However, there is no clear trend on the C4 dataset. Attacks which better exploit the optimization trajectory may find earlier examples to be forgotten more slowly, they may have longer impact on this trajectory. For now, privacy attacks appear to not be able to take advantage of the trajectory, and the optimization landscape appears to obfuscate rather than reveal memorized examples.
C.3 MODEL SIZE
We show the relationship between model size and forgetting in Figures 9a and 9b for hard test examples and medium hardness test examples, respectively. We evaluate forgetting for ResNet- 18, ResNet-34, ResNet-50, and ResNet-101 models. There seems be little difference between models
17

---

Published as a conference paper at ICLR 2023
Epo0h 26300
Epoch 40000
1.74-
Eporn 86/90
Surich
0.70
fossn
0.00
15x z5e 3bx abs
50s Thaniing stess
102k
Stegs witer wnpeittcciiinnno (x205)
Step Number
(a) Injection Time (5 Repeats)
(b) Removal Time (4 repeats)
(c) Injection Time Repeats)
Figure There is no consistent effect for injection/removal time. On ImageNet, injection Epoch 20 leads to earlier forgetting than later epochs. On LibriSpeech, later removal leads to slower forgetting. due to using the POISON strategy. For LMs, there is little difference in exposure between inserting 10% through training and 50%.
1.0
1.0
1.0
NeaMec--8
Nomenium
0.0
Precc ente 20%
0.9
Nomentari
Nomestum
0.6
8.6-
0.6
0.5
0.5
0.5
50
200
125
200
75
150
125
150
175
1.00 322
150
175
Soees after bLociin (6200)
5000s after mlucciin (.200)
Stess after luediio (1200)
(a) Model Size (Hard)
(b) Model Size (Medium)
(c) Momentum
Figure 9: Hard examples seem to forgotten more slowly by ResNet-101 models, but medium hardness examples are forgotten quickly by all models. Momentum does not appear to have significant impact on forgetting. Results on ImageNet.
1.0
1.0
Learning Rate 0.05
6k sleps
Predsion @ FPW-10% 10%
0.9
Predision @ FPM= 10%
0.9
steps
Learning Rate 0.2
14k stops
0.8
0.8
0.6
0.6
25
50
75
100
125
150
175
200
58
59
62
Steps after Injection (x200)
Inject Epoch
(a) Learning Rate, No Change
(b) Inject Near Epoch 60 Decay
Figure 10: Changing the global learning rate does not have significant impact on forgetting (left), except immediately before or after large learning rate changes (right). In this model, the learning rate decayed at Epoch 60. Forgetting happens less quickly Epoch 59, right before the decay (Epoch 59 injection still has high precision after 14k steps); forgetting happens much more quickly for data injected Epoch immediately after the learning rate decay.
18

---

Published as a conference paper at ICLR 2023
for medium hardness test examples, but ResNet-101 models seem to forget hard test examples more slowly. Prior work has found that larger models generally memorize more (Carlini et al. (022). making this effect natural, but it is interesting that there is little difference between most of these models. is possible that all ResNet models we consider are already highly over-parameterized, and forgetting has already nearly saturated.
C.4 OPTIMIZER PARAMETERS
On ImageNet, we vary the momentum and learning rate parameters see if these result in a significant change to forgetting. For example, it is possible that an increased momentum parameter would lead to less forgetting, find this to generally not be the case in our experiments on ImageNet: learning rate and momentum do not appear to have significant impact on forgetting (Figures 9 and 10al respectively). Learning rate likely does not have a large impact, as all examples have the same learning rate, and so the data nondeterninism is equally powerful at causing forgetting in each case. While is intuitive that larger momentum parameters would lead to longer forgetting, forgetting happens over long enough step counts for momentum to not impact significantly. However there is one exception: in our ImageNet training, 30 epochs (we reproduce Figure 3 in Figure [Tb] to discuss this effect more here). This has two drastic implications on forgetting: examples seen just before the decay forgotten much more slowly, and there is period directly after the decay where forgetting happens more quickly. The first phenomenon (seen in Epoch 58 and Epoch 59 in Figure TOb) is intuitive: the rate of forgetting depends on the other examples' contributions, and the point injected before the learning rate decay contributes 10x more than these later examples. The other phenomenon is more surprsiing and is likely due to the optimum being more "unstable" after a learning rate decay. This instability reduces over time, as we see in Figure 10b (at Epochs 60-62); forgetting has begun to increase to a normal rate two epochs after the learning rate decay, at Epoch 62.
causes a point's update contribute to every subsequent update. However, we
a learning rate decay which reduces learning rate by a factor of 10 every
C.5 COMPARISON WITH TRADITIONAL FORGETTING METRICS
We have argued that our approach is more relevant to privacy than traditional metrics for measuring forgetting, such as loss or accuracy (accuracy is standard in the catastrophic forgetting literature and was also used to measure forgetting in Tirumala et al. (2022). Here, we present additional experimental justification. First, we see in Figure I that accuracy is an overly optimistic metric from privacy perspective. For examples repeated 10 times, accuracy has stabilized by 100 x 200 20000 steps after injection, suggesting that they are completely forgotten. However, compared to Figure 2a these examples are still at 70% membership inference precision, not invulnerable from privacy attacks. Loss (in Figure 11b) takes longer to stabilize, providing more comparable forgetting speed to our approach. However, membership inference scores are still more easily interpreted than loss scores for quantifying privacy risk. We also note that, to make comparison casier, we have used hard examples to report results with repetitions, but existing work typically considers more average examples, as forgetting is traditionally used to measure average performance on subdistributions. For this reason, existing metrics are more similar to our experiments with medium hardness or easy examples in Figure TIc, where forgetting happens nearly immediately, while hard examples take significantly longer. Worst-case analysis is more relevant from a privacy perspective, justifying our approach.
D EXTENSION OF UNDERSTANDING FORGETTING, SECTION 5
D.1 CONCRETE K-MEANS DESCRIPTION
We reproduce here Figure 12 which offers intuition for our setting. Concretely, we consider a one-dimensional k-means task with I = 2, but where three clusters exist in the data, denoted by
Ci, C3. Samples from cluster e₁ are drawn from (V(1,, samples from cluster 02 are drawn from Nu, o²), and samples from cluster C3 are drawn from (1, o²)) Here, o² is some fixed variance parameter (we use o = 0.03), and μ > O controls the distance between C2 and the other two clusters, and crucially makes e2 slightly closer to e3 than to c₁ (we use μ 0.03). We consider a two-stage learning procedure, where some dataset Do is used to lear the clusters initially, and the model is then updated with some new dataset Dj. We fix Dj contain equal number n of
19

---

Published as a conference paper at ICLR 2023
Aapeat
Aacoogge Surch Lesa
Sacc Acounce 0.2-
Hand
Repsal
Dayy
Napsel
Napcol
(a) Repeats with Accuracy Baseline
(b) Repeats with Loss Baseline
(c) Hardness with Loss Baseline
Figure 11: Experiments on ImageNet with traditional forgetting metrics accuracy and loss on the injected batch.
Outlier
X
(a) k-means Do
(b) outlier is OUT
(c) outlier is IN
Figure 12:
The non-convexity of the k-means objective can prevent forgetting. When an outlier (green X in Subfigure 12a is present in the initial training the clustering in Subfigure 12c is learned; when the outlier is not present, the clustering in Subfigure 12b learned. Adding more data does not result in the outlier's influence being forgotten. Left to right, clusters are Cı, C22 and eg in the text. We add a second dimension to the setting we discuss in the text for presentation.
samples from each cluster. However, we consider two cases for Dp: (1) in the IN case, Do consists of m samples from 61, one "outlier" sample x (we use -0.01, slightly more than one standard deviation from the mean) from 62, and m samples from C3 and in the OUT case, Do consists of m samples from e and m samples from C3, without the "outlier". Samples from C2 are never included in Do. perhaps because they are from emergent subpopulation. The single "outlier" sample can result in drastically different clusters, difference which does not get forgotten by collecting more examples D1. We run experiment with this setup, using fresh samples from each cluster. Over these trials, membership inference accuracy for has 97% accuracy, but the attack also has perfect precision. That is, when is OUT, ea and 62 are far enough that they are never joined, and there are only examples where the randomness of the data causes 02 and c3 join despite the presence of æ. We note that differential privacy would prevent this attack, as it would randomize the clustering, preventing membership inference. Machine unlcarning algorithms designed for k- d-means (Ginart et al. 2019) would also retrain the entire model upon removing the outlier.
10, 100, and run 200 trials with
D.2 NONDETERMINISM IS REQUIRED
The analysis in the remainder of this section will use the mean estimation task, simple task which is frequently used in the theoretical privacy literature to understand the effectiveness of privacy attacks (Homer al. 2008 (Sankararaman et al. 2009 Dwork et al. 2015) or design differentially private algorithms (Bun & Steinke 2019 Kamath al. 2019). In mean estimation, learner wants to find the mean a dataset, which is the minimizer the squared Eg loss. To understand forgetting, consider algorithms which perform mean estimation by per-example gradient descent, iterating through samples r from the dataset and updating the model at iteration i, 0, by a gradient step on the squared & loss (8. x)? with learning rate 17.
To show that determinism prevents forgetting, we consider the deterministic version of per-example gradient descent in Algorithm which iterates through dataset in fixed order. In Theorem 2
20

---

Published as a conference paper at ICLR 2023
prove that this algorithm doesn't 't forget, by considering two datasets which differ in only row, and showing that the two datasets have perpetually different models, so that an adversary can distinguish between them if the adversary knows all other points. In the main body, we also experimentally verify this result, when logistic regression is trained by minimizing the standard cross-entropy loss with fixed-order SGD the FMNIST dataset.
Algorithm 3: Mean Estimation with Deterministic Ordering
Data: Dataset D {a; P initial parameters 8,, learning rate Function TR T AER.MAANDET..E
(D, 00:
For 1..m
0, = 01-1 - 2n(0,-1 -x4)
Return nn
Theorem 2. Consider the described algorithm Algorithm 3 with 0 <<n < 0.5. When run on any two distinct datasets Do and D1 differing only one row, have T(D)) + T(D1). regardless of which index Do and Dj differ in.
Proof. Consider the intermediate points 0 and 01, which represent the model at the ith step of training datasets Do and D1, respectively. Write j for the index where Do and Dj differ. To prove the theorem, we first note that 00-1 0 as the first j steps of training all use identical examples from Do, DT. Next, we show that 0f o 0j. and then that 0 + 0f for all i > j.
To that f9 + f). we write out the precise gradient updates:
0 - 0 = 03- 2n 23)) (0)-1 - 2m(0)_1 -23))= 2n(z² [1- xz)) + 0,
where the second step holds because 09-1 00-11- and the third holds because j is the index where Do and D differ.
Now, show that this implies that 0 + 0 for all function is one-to-one. That is, for all x. + 0', taking a gradient step on x still results in different models:
show that, for all x. the gradient update
0 0-2n(8 1:) 0(1 2n)
2q f 27y) 2n 0' 2 x))
From this, 0 + 0J implies that the models are different at step j + 1, which itself implies that the models are different at step j 2, and will be different for the entirety of training.
L
D.3 DATA RANDOMNESS CAN CAUSE FORGETTING
Here, we prove Theorem restated below.
Algorithm 4: Mean Estimation with Random Sampling and Injection
Data: Injection e, initial parameters d, training steps k, distribution D Nu, E), learning rate
7
Function TRA AMA.AAAAAPL..A........ (6o, v, D))
OJ 0o 20 v)
Update with +u Update with
0 A. (0) + v)
For = 1.....k
x -ı + -SAMPLE(D)
0+ 001 - 2n
0. = = 2n(0,_1 -2,
Return 05
Theorem 1 The distributions of the models 8 and 0% output by Algorithm 4 with learning rate 0 1) 1/2 have Rényi divergence of order a at most 20x T-11e.
21

---

Published as a conference paper at ICLR 2023
Proof. First, observe that the gradient update some 6g with example produces 81 0l 21100 - ro) = 8b(1 - 27)) + 2ng0. Another gradient update on 21 produces fg db(1 2n))
2m(1 2n) + 2- In general, we have
0, 0 2x)* 2 2n(1 2n) + + 2n(1 221) 21) .n-
k-
(1)
We write 0 = 0o - 2n) + 21ye (a gradient step on +D) and 0 = 0o - -2n) 2nyu (a gradient step on u). Then we analyze the distributions 0g and 0% Using Equation | replacing Og with 0g and 0 and using that each 2; sampled from (N, 2),, we obtain the distributions
++ + (0 -1)(1 -2n) + +N (0, -
0 - + (0 - -1 -2n)* + + (0, -اا Σ
Using that the Rényi divergence of order a between two multivariate Gaussians with means 140, and equal covariance E' is 2 (n0 mn) E' mn), compute the divergence for og and 0g as 8a 2(1 ()( (1 2
Σ U.
1- 2n)
It remains to bound the 7) term in this product. The function f()) v(1-n)(1-2n) 2k
1-(1-2n) has negative
derivative on the interval 17 < 1/2 for any k O. Then f() is maximized on 1 1/2 when 1) + 0: we can compute this limit with L L'Hospital's rule as 4k completing the proof. L
22


Reviews:
[{"review_id": "tHuzjpJhu-O", "reviewer": "Reviewer_hxrq", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This work aims to quantify how much models forget the training samples. To do so, the authors connect the forgetting and privacy, then utilize privacy-related algorithms to measure the forgetting. In addition, the authors claim that nondeterminism could be the potential explanation and conduct some experiments and calculations to support it.", "summary_of_the_review": "Surprisingly novel, but with limited reasonable support.", "strength_and_weaknesses": "Strength:\n- Exploring the forgetting phenomenon is a fundamental topic for the machine learning community, thus, the work is interesting and promising. \n- This work is inspiring, as connecting privacy and forgetting is novel to me. One interesting direction may be evaluating the effectiveness of DP algorithms using similar connections. \n- This work provides a novel measurement for modeling forgetting.\n- The paper is well-written and easy to follow.\n\nI do enjoy reading the paper, but several concerns make me give the current rating. I will raise the score if the authors can address my concerns.\n\nWeakness:\n- My main concern is about nondeterminism, i.e., Sec. 5. I think the experimental and theoretical analysis seem weak to support the perspective. Specifically,\n1) (Sec. 5.1) the authors claim that non-convexity can prevent forgetting, but the designed experiments are not good, where adding more samples when performing the k-means algorithm has little impact on forgetting samples.  I think the reason should be that the employed algorithm does not change the features of samples, thus, always remember the samples, which is different from the scenario of training DNNs, i.e., updating makes features change. Thus, remembering comes from unchanged features rather than nondeterminism.\n2) (Sec. 5.2) further experiments conducted to support the perspective are given in Sec. 5.2, which also seems not good enough. Specifically, the adversary holds the same data D, extra data D_p, and even the same batch order. This means that the adversary knows everything. I cannot understand why the adversary is interested in attacking the target because the adversary even knows exactly what the difference is from D_p.\n3) (Sec. 5.3) the authors draw a conclusion using the introduced example of mean estimation: introducing two different samples causes the difference between models, but the nondeterminism can cause forgetting, i.e., hard to distinguish the difference. However, the difficulty in distinguishing actually results from more training iterations, k in Theorem 1, rather than the nondeterminism.\nI hope the authors could clarify the above questions.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "kAk71bwIrhd", "reviewer": "Reviewer_Qkp9", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "In this work, the authors study the effect of the forgetting of machine learning models on privacy. To this end, they focus on validating the two hypothesis, including the pessimistic hypothesis and the optimistic hypothesis. Then, they design a method to measure the example forgetting in the training and show several analytic and empirical findings with this method. ", "summary_of_the_review": "In summary, this work is well motivated and easy to follow. Besides, the work provides in-depth understandings with empirical findings, which, I believe, can bring some new insights to inspire future research. However, the contribution of this work is still limited without theoretical results. I am not an expert in this area, so I give a weak accept for this work before the rebuttal.", "strength_and_weaknesses": "Strength:\n\n-  This work is well motivated. In this paper, the authors aim to study the connections between memorization and forgetting in the context of data privacy.\n- The paper writing is easy to follow. The authors give a clear definition of forgetting before introducing the measure method, which makes it much clear for the reader.\n- This work gives several interesting empirical findings and provides in-depth understandings. Specifically, the authors show the two cases for when the forgetting happens, which is useful for the future investigation.\n\nWeakness:\n\nThe contribution of this work is limited due to lack of theoretical guarantee. Although this work provides many empirical studies, it is not clear if the conclusions can extend to other settings, like different model architectures. It would be better if the authors can give any theoretical guarantee.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "aFOZ0Nrdxb3", "reviewer": "Reviewer_2BVh", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper empirically evaluates how machine learning models forget the training samples during the training process. The paper empirically demonstrates that machine learning models do memorize the training samples once it sees them, but tend to forget them gradually once the training proceeds without seeing them again. The paper claims that the non-determinism in the training process might be one possible reason, by showing that empirically and theoretically that forgetting does not happen in deterministic training, but could happen when non-determinism is introduced.", "summary_of_the_review": "\nAlthough the insights illustrated in the experiments are not surprising, having such a systematic empirical study is still useful to the community. The proposed metric can be useful for follow-up work. The hypothesis on the reason for forgetting can spur future research. ", "strength_and_weaknesses": "\n* The hypotheses on why forgetting happens in practice is interesting and could spur future research on this topic\n\nWeaknesses:\n\n* The empirical results on forgetting are not surprising. In fact, as discussed in Section 2.3, similar insights have already been discussed in prior work. (Although there is still value in demonstrating the empirical results).\n\n* Overall the paper is well-written. However, there are still some unclear points:\n    - Page 4: \"we instead design a procedure to measure an algorithm’s worst-case forgetting.\" How can this algorithm measure the *worst-case* forgetting?\n    - Figure 1a: the accuracy increases before the injection (the vertical line). How could that happen?\n    - Page 6: \"...by differential privacy with ε ≈ 0.6\". How do you get this epsilon? The detail is missing.\n    - The last paragraph of Section 4: \"We ﬁnd that examples injected before the decay are forgotten signiﬁcantly slower than examples injected after.\" I do not see how to draw this conclusion from Figure 3.\n    - Continuing the above question: figure 3 uses #steps to label the bars, but uses inject epoch as the x-axis. Without knowing the number of steps per epoch, it is unclear how to read this figure.\n    - The discussion in Section 5.1 is interesting. However, it slightly disconnects from the main story of the paper. While the non-convexity in the illustrated k-means example \"can prevent forgetting\", it does not give much insight into the neural networks, as the non-convexity in the two settings is very different. The story goes much better without Section 5.1.\n    - Section 6: \"We ﬁnd the size of the dataset is key\". Which results in the main text illustrate this?\n    - Section 6: \"forgetting is more likely to happen when ... these examples are sampled from a large training set (e.g., when training modern language models).\" Which results in the main text illustrate this?\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "XXoTiqpRjp", "reviewer": "Reviewer_TqY1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studies the connection between training data memorization and data forgetting. By measuring the forgetting with privacy attacks (member inference attack and data extraction attack), this paper shows that examples that are not observed by models in recent training iterations are more likely to be forgotten (i.e. more robust to privacy attack). In addition, this paper also conducts some studies to better understand forgetting and shows that the k-means algorithm does not experience a forgetting and non-deterministic (like random sampling) may be one of the reasons causing forgetting in the training.", "summary_of_the_review": "I thoroughly enjoyed reading this paper and thinking about how privacy risk is related to forgetting and memorization problems in deep learning. My major concern is that, as a novel method to measure forgetting, there may lack some evidence to show how the proposed method is better than existing methods. Besides, the reason behind the design of the measuring method is a bit unclear.", "strength_and_weaknesses": "Many thanks for the paper. I thoroughly enjoyed reading this paper and thinking about how privacy risk is related to forgetting and memorization problems in deep learning. I listed the strengths and some of my concerns of the paper as follow.\n\nStrength:\n+ The paper studies an interesting problem which is the connection between data forgetting and memorization.\n+ Different from current forgetting measuring for catastrophic forgetting, this paper proposes a novel method based on privacy attack: an example that is easier to be inferred by a privacy attack is less likely to be forgotten by models. The evaluation results show that, if examples have not been seen recently, they are less susceptible to privacy attacks.\n+ This paper also shows that the k-means method is resilient to forgetting and non-deterministic can be the reasons behind forgetting in training.\n+ The writing of the paper is clear and good to follow. \n\nWeakness:\n+ The paper proposes to use a privacy attack to evaluate the forgetting of examples in training, but I am not quite convinced why the proposed forgetting measure is better than the existing forgetting measuring method. Although section 3 talks about the difference, there is no empirical evaluation to compare this difference. What could be the connection between the privacy-based forgetting metric and the traditional forgetting metric (like accuracy or training loss)? If we use the traditional forgetting metric, can we get similar conclusions discussed in the paper? Like, if examples have not been seen recently, the examples are less likely to be forgotten?\n\n+ I am not sure if the proposed method indeed measures the forgetting of examples. By measuring by inference attack, it is more like measuring how much models memorize examples. Examples never learned by models have low privacy risks but should not be treated as forgotten examples. I feel that the proposed method measures the privacy risk, but not necessarily if models forget examples.\n\n+ Why do we need to “the worst-case” examples to measure forgetting? Is the proposed method a general method to measure forgetting of all training examples (i.e. “average-case” in the paper)?  \n\n+ One of the main arguments in this paper is that, if examples have not been seen recently, they are less susceptible to privacy attacks, which may not be so surprising. Privacy leakage on datasets usually comes from unwanted memorization of training data. Examples are expected to be less memorized if they have not been seen recently due to catastrophic forgetting features of deep learning models, which makes them less susceptible.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster