Adaptive Machine Unlearning
Authors: Varun Gupta
Christopher Jung
Seth Neel
Aaron Roth
Saeed Sharifi -Malvajerdi
Christopher Waites
Venue: NeurIPS 2021 Poster (2021)
Keywords: Machine Unlearning
Data Deletion
Differential Privacy
Max Information

Abstract: Data deletion algorithms aim to remove the influence of deleted data points from trained models at a cheaper computational cost than fully retraining those models. However, for sequences of deletions, most prior work in the non-convex setting gives valid guarantees only for sequences that are chosen independently of the models that are published. If people choose to delete their data as a function of the published models (because they don’t like what the models reveal about them, for example), then the update sequence is adaptive. In this paper, we give a general reduction from deletion guarantees against adaptive sequences to deletion guarantees against non-adaptive sequences, using differential privacy and its connection to max information. Combined with ideas from prior work which give guarantees for non-adaptive deletion sequences, this leads to extremely flexible algorithms able to handle arbitrary model classes and training methodologies, giving strong provable deletion guarantees for adaptive deletion sequences. We show in theory how prior work for non-convex models fails against adaptive deletion sequences, and use this intuition to design a practical attack against the SISA algorithm of Bourtoule et al. [2021] on CIFAR-10, MNIST, Fashion-MNIST.

Adaptive Machine Unlearning
Varun Gupta', Christopher Jung', Seth Neel?, Aaron Roth', Saced Sharifi-Malvajerdi and Chris Waites
University of Pennsylvania
Harvard University
3 Stanford University
Abstract
Data deletion algorithms aim to remove the influence of deleted data points from trained models at a cheaper computational cost than fully retraining those models. However, for sequences of deletions, most prior work in the non-convex setting gives valid guarantees only for sequences that are chosen independently of the models that are published. If people choose to delete their data as a function of the published models (because they don't like what the models reveal about them, for example), then the update sequence is adaptive. In this paper, we give a general reduction from deletion guarantees against adaptive sequences to deletion guarantees against non-adaptive sequences, using differential privacy and its connection to max information. Combined with ideas from prior work which give guarantees for non- non-adaptive deletion sequences, this leads to extremely flexible algorithms able to handle arbitrary model classes and training methodologics, giving strong provable deletion guarantees for adaptive deletion sequences. We show in theory how prior work for non-convex models fails against adaptive deletion sequences, and use this intuition to design practical attack against the SISA algorithm of Bourtoule et al. 2021 on CIFAR- 10, MNIST, Fashion-MNIST.
Introduction
Businesses like Facebook and Google depend on training sophisticated models on user data. Increasingly-in part because of regulations like the European Union's General Data Protection Act and the California Consumer Privacy Act-these organizations are receiving requests to delete the data of particular users. But what should that mean? It is straightforward from database and stop using it to train future models. But what about models that have already been trained using an individual's 's data? These are not necessarily safe; it is known that individual training data can be exfiltrated from models trained in standard ways via model inversion attacks [Shokri al. 2017 Veale al., 2018 Fredrikson al.) 20155.. Regulators are still grappling with when trained model should be considered to contain personal data of individuals in the training set and the potential legal implications. 2020 draft guidance, the U.K.'s Information Commissioner's Office addressed how to comply with data deletion requests as they pertain to ML models:
delete a customer's data
If the request is for rectification or erasure of the data, this may not be possible without re-training the model...or deleting the model altogether [CCO 2020).
Fully retraining the model every time a deletion request is received can prohibitive in terms of both time and cooney-especiin data deletion (also known as machine unlearning) is to find an algorithmic middle ground between the compliant but impractical baseline of retraining, and the potentially illegal standard of doing nothing. We iteratively update models as deletion requests come in, with the twin goals having
for large models and frequent deletion requests. The problem of
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

computational cost that is substantially less than the cost of full retraining, and the guarantee that the models we produce are (almost) indistinguishable from the models that would have resulted from full retraining.
After initial model is deployed deletion requests arrive over time users make decisions about whether to delete their data. It is easy to see how these decisions may be adaptive with respect to the models. For example, security researchers may publish a new model inversion attack that identifies specific subset of people in the training data, thus leading to increased deletion requests for people in that subset. In this paper we give the first machine unlearning algorithms that both have rigorous deletion guarantees against these kind of adaptive deletion sequence, and can accommodate arbitrary non-convex models like deep neural networks without requiring pretraining on non-user data.
1.1
Main Results
The deletion guarantees proven for several prior methods crucially rely on the implicit assumption that the points that are deleted are independent of the randomness used to train the models. However this assumption fails unless the sequence of deletion requests is chosen independently of the information that the model provider has made public. This is very strong assumption, because users may wish to delete their data exactly because of what deployed models reveal about them.
We give generic reduction. We show that if:
1. A data deletion algorithm RA for learning algorithm A has deletion guarantees for oblivious sequences of deletion requests (as those from past work do), and
2. Information about the internal randomness of R.A is revealed only in a manner that satisfies differential privacy, then
(A, R.A) also satisfies data deletion guarantees against an adaptive sequence of deletion requests, that can depend in arbitrary ways on the information that the model provider has made public.
In Section 3. we motivate our main result with theoretical example which illustrates that past method's lack of guarantees for adaptive sequences is not simply a failure of analysis, but an actual failure of these methods to satisfy deletion guarantees for adaptive deletion sequences. As exemplar, we use a variant of SISA from Bourtoule et al. [222]] that satisfies perfect deletion guarantees for non-adaptive deletion sequences and exhibit adaptive deletion sequences that strongly separate the resulting distribution on models compared to the retraining baseline.
The generic reduction found in Section 4 can be used to give adaptive data deletion mechanisms for wide variety of problems by leveraging past work on deletion algorithms for non- non-adaptive sequences, and line of work differentially private aggregation [Papernot al. 2018 Dwork and Feldman 2018). Since prior deletion algorithms themselves tend to use existing learning algorithms in a black-box way, the entire pipeline is modular and easy to bolt-on existing methods. In Section 5 we show how this can be accomplished by using a variant of the SISA framework of Bourtoule et al. [202I] together with differentially private aggregation method.
In Section 6. we complement our main result with a set of experimental results on CIFAR-10, 10, MNIST, and MNIIST that demonstrate differential privacy may be useful in giving adaptive guarantees beyond the statement of our theorems. Specifically we show that small amounts of noise addition (insufficient for our theorems apply) already serve break the adaptive deletion strategies that use to falsify the adaptive deletion guarantees in our experiments described in Section 3 and do so at minimal expense in model accuracy.
1.2 Related Work
Data deletion was introduced by Cao and Yang (0055]: we adopt the randomized formulation of Ginart et al. [2019]. Ginart et al. [2019] anticipate the problem of deletion requests that might be correlated with internal state of the algorithm, and define (and propose as a study for future work) robust data deletion which is a data deletion guarantee that holds for adversaries with knowledge of the internal state. Our insight is that we can provide deletion guarantees against adaptive sequences by instead obscuring the internal state of the algorithm using techniques from differential privacy.

---

We are the first to explicitly consider the problem of adaptive sequences of deletion requests, but some techniques from past work do have delction guarantees that extend adaptive sequences. Deterministic methods and methods that depend only on randomness that is sampled after the deletion request are already robust to adaptive deletion. This includes techniques that find an approximately optimal solution to a strongly convex problem and then perturb the solution to obscure the optimizer within a small radius e.g. Guo et al. 2019 Neel et al. [202]], [eehhaii et al. [202I]. It also includes the approach of Golatkar et al. 20200a bj which pre-trains nonconvex model on data that will never be deleted and then does convex fine-tuning on user data on top of that. Techniques whose deletion guarantees depend randomness sampled at training in general do not have guarantees against adaptive deletions. This includes algorithms given in Ginart et al. (2019), Bourtoule et al. (2021) Neel et al. [02T]- the SISA framework of Bourtoule et al. [2021 being of particular interest
is agnostic to the class of models and training methodology, and so is extremely flexible.
Differential privacy has been used as a mitigation for adaptivity since the work of Dwork et al. [2015c|a]. In machine learning, it has been used to mitigate the bias of adaptive data gathering strategies as used in bandit learning algorithms [Neel and Roth 2018). The application that is most similar to our work is Hassidim et al. 2020]. which uses differential privacy of the internal randomness of an algorithm (as we do) to reduce streaming algorithms with guarantees against adaptive adversarial streams to streaming algorithms with guarantees against oblivious adversaries. Our techniques differ; while Hassidim al.
[2020] reduce to the so-called "transfer theorem for linear and low sensitivity queries" developed over a series of works Dwork et al. [2015e], [asssly et al. (2021), Jung et al. [2020]. we use more general connection between differential privacy and "max- "max-information" established in Dwork et al. 2015b). Rogers et al. 2016).
2 Preliminaries
Let Z be the data domain. A dataset is a multi-set of elements from Z. We consider update requests of two types: deletion and addition. These update requests are formally defined below, similar how they are defined in (Neel et al. 202T).
Definition 2.1 (Update Operations and Sequences). An update is a pair (z. )) where 2 is datapoint and + E T = ('add', 'delete') } determines the type of the update. An update sequence U a sequence (u' u² ....) where u' E Z T for all Given a dataset D and an update u (z, )).
the update operation is defined as:
Dou [DU if 'add' (1)
if 'delete'
Given update sequence U = (u' u² ......) we have D U &
We use θ to denote the space of models. A learning or training algorithm is a mapping A: Z - -* that maps dataset D E 2 to a collection of models 0 O'. An unlearning or update algorithm for A is a mapping R.A 2" x (2 x T) x S + O" which takes in a data set D) E 2", an update request E 2 T, and some current state for the algorithms E S (the domain S can be arbitrary), and outputs an updated collection of models 0' E O'. In this paper we consider a setting in which a stream of update requests arrive in sequence. We note that in this sequential framework, the update algorithm RA also updates the state of the algorithm after each update request is processed; however, for notational economy, we do not explicitly write the updated state an output of the algorithm.
At each round, we provide access to the models through a mapping fpuMish : O* > that takes in the collection of models and outputs some object v E V. A published object s E Vv can, for instance, be the aggregate predictions of the learned models on data set, or, some aggregation of the models. To model adaptively chosen update sequences, we define an arbitrary "update requester" who interacts with the learning and unlearning algorithms (A, R through the publishing function Fpublish in rounds to generate a sequence of updates. The update requester is denoted by UpdReq and defined in Definition 2.2 and the interaction between the algorithms and the update requester is described in Algorithm
Throughout we will use u' to denote the update request at round 4. We will use De to denote the data set at round t: D is the initial training data set and for all 2 1, D D w!. We will use 0' to denote the learned models at round t: 8 is generated by the initial training algorithm A, and 0f for
3

---

Algorithm 1: Interaction between (A, RA) and UpdReq
1: Input: Data set D
2: Let D < D.
3: Train 0 +- A(D).
4: Publish v0 + Spablishh (0%).
5: Save the initial state s
6: for 2 = 1,2.... do
7: The update requester requests a new update, given the history of interaction:
8:
v' + UpdReq (v, u², wtt,, u² ...., 11 1))-1
9:
The algorithms update, given u²:
Update the models 0 R (D1-1, 81-1)
11:
Publish v0 + fuubissh (0*)
12: Save the updated state s
13:
Update the data set D +- D ou'
t 121 denotes the updated models at round generated by the update algorithm RA vpt denotes the published object round t: eb fpublish (0*).
Definition 2.2 (Update Requester (UpdReq)). The update sequence is generated by an update
requester which is modeled by (possibly randomized) mapping UpdReq: V x x2 - (2x that takes as input the history of interaction between herself and the algorithms, and outputs new update for the current round. Given update requester UpdReq, algorithms (A, R.A) and publishing functions Upubiich) ,t, the update sequence = =(u² }e can be written as
x² UpdReq (v²), 2² UpdReq (w) u²,, ........
-UpdReq (vo: u² "t......u...................." 1-1 11
....,,
We say an update requester UpdReq is nonadaptive it is independent of the published objects, i.e,, if there exists mapping UpaReq': (Z x T)* (2 T) such that for all 2 1,
ua u' UpdReq (v", 2 2b " ( UpdReq' (u' u² ut 1
This is equivalent to saying that the update sequence is fixed before the interaction occurs.
Following [Ginart et al. 2019 we propose the following definition for an unlearning algorithm in the sequential update setting ([Ginart al. 2019] gives definition for single deletion request, whereas here we define natural extension for an arbitrarily long sequence of deletions, as well as additions, that can chosen adaptively.). Informally, we require that every round, and for possible update requesters, with high probability over the draw of the update sequence, no subset of models resulting from deletion occurs with substantially higher probability than it would have under full retraining.
Definition 2.3 ((x,, 3, 3,,))-un -.nneannnni,, We say that R an (ax, 3, -nnllemrmnn algorithm for A, for all datasets D = D and all update requesters UpdReq, the following condition holds: For every update step 2 1, with probability at least - over the draw of the update sequence ust (u' ...., w²) from UpdReq.
O Pr E
E +
We say RA is nonadaptive -..u.ari-ull algorithm the above condition holds for any nonadaptive UpdReq.
Remark 2.1. Our definition of unlearning is reminiscent of differential privacy, but following (Ginart al. 2019) we ask only for a one-sided guarantee: that the probability of any event under the unlearning scheme is not too much larger than the probability of the same event under full retraining, but not vice versa. The reason is that we do not want there to be events that can substantially increase an observer's confidence that we did not engage in full retraining, but we do not object to observers who strongly update their beliefs that we did engage in full retraining. Our events are defined directly over the sets of models in O* ouiput by A and R note thut because of information processing inequalities, this is only stronger than defining events E. over the observable outcome space V.

---

2.1 Differential Privacy and Max- lax-Information
Differential privacy will be a key tool in our results. Let X' denote an arbitrary data domain. We use E X' to denote an individual element of X' and X E X to denote collection of elements from X' wwhich we call data set. We say two data sets X, X' E X' are neighboring they differ in most one element. We say an algorithm M x + O is differentially private if its output distributions on neighboring data sets are close, formalized below.
Definition 2.4 (Differential Privacy (DP) (Dwork al., 2006b a An algorithm M xm O is (e, -ddffferrenli private, if for every neighboring X and and for every O C O, we have Pr (M(X) E 0) S e Pr (X' E 0 +
We remark at the outset that the "datasets" to which we will eventually ask for differential privacy with respect to will not be the datasets on which our learning algorithms are trained, but will instead be collections of random bits parameterizing our randomized algorithms.
Differentially private algorithms are robust to data-independent post-priee processing:
Lemma 2.1 (Post-processing preserves DP (Dwork et al., 2006b)). M xm - O is (c. differentially private, then for all f O + R, we have J M 2Thh >> RR defined by f M (X) (X) is (c, diffferrrrel private.
The max- max-information between two jointly distributed random variables measures how close their joint distribution is to the product of their corresponding marginal distributions.
Definition 2.5 (Max-Informatie [Dwork et al., 20155)). Let and be jointly distributed random variables over the domain (X, y). The 3-approximate max-information between X and Y is:
E B
12 (X:Y) log
sup PEXR
Pr[ YY)
where (X @ Y) represents the product distribution of X and
The max-information of an algorithm M that takes dataset X input and outputs (X), ), is defined as the max- max-informttion between X and (X) for the worst case product distribution over X:
Definition 2.6 (Max-Information of an Algorithm (Dwork et al. (0T5h)). Let M xm + O be an Algorithm. We say M has B-approximate max-information of k. written (M,, m) I k, ifr every distribution P over X, we have 1 (X; MX)) S k when X ~ pm
In this paper, we will use the fact that differentially private algorithms have bounded max-information:
Theorem 2.1 (DP implies bounded max- -ax-information [Rogers et al. 2016). Let M : xm - O be an (c, diiffferrrtll private algorithmm for 0 < 1/2 and < < O (em m mo/e for B = = + O oo/e
Then, I (M, (M,m) m)
Falsifying Unlearning Guarantees with Adaptivity
In this section we demonstrate that the deletion guarantees of algorithms in the SISA framework [Bourtoule et al. [021] fail for adaptive deletion sequences. We give a clean toy construction which shows algorithms in the SISA framework fail have nontrivial adaptive deletion guarantees even in the black-box setting when the models within each shard are not made public, only aggregations of their classification outputs. In the Appendix we experimentally evaluate a more realistic instantiation of this construction.
The setting we consider directly corresponds to the setting in which our final algorithms operate: what is made public is the aggregate predictions of the ensemble of models, but not the models themselves. For non-adaptive sequences of deletions, distributed algorithms of the sort described in Section 5 have perfect deletion guarantees. We demonstrate via a simple example that these guarantees dramatically fail for adaptive deletion sequences.
Suppose we have a dataset consisting of real-valued points with binary labels ((1,, ye) 2m By E Rdd Y {0, 1} in which there are exactly two copies of each distinct training example. Consider
5

---

simplistic classification model, resembling a lookup table, which given point 2; predicts the label y if the model has been trained on (z,, yi) and a dummy prediction value "1" "tthewise::
g/i [
if (24, (4) D,
fD((,))
otherwise
Consider what happens when the training algorithm randomly partitions this dataset into three pieces and trains such a model on each partition. This constructs ensemble which, at query time, predicts the class with the majority vote. On this dataset, the ensemble will predict the labels of roughly 2/3 of the training points correctly- distinct partitions, so that the ensemble gets the majority vote right.
is, exactly those points for which the duplicates have fallen into
We construct an adaptive adversary who chooses to delete exactly those training points that the ensemble correctly classifies (which are those points for whom the duplicates have fallen into distinct shards). The result is that the model resulting from this deletion sequence will misclassify every remaining training point. Full retraining (because it would rerandomize the partition) would again lead to training accuracy of approximately 2/3. Recalling that our deletion notion requires that the probability of any event under the unlearning scheme is not much larger than the probability of the same event under full retraining, this demonstrates that there are algorithms in the SISA framework even the models are not directly exposed- - that do not satisfy (a, B, 7 guarantees for any nontrivial value of a. We formalize this below:
Theorem 3.1. There are learning and unlearning algorithms in the SISA framework (A, RA) such that for any o, and any B, 1/4, R is not an (a, B, -mllleaannn algorithm for A.
proof of this theorem can be found in the appendix.
A Reduction from Adaptive to Nonadaptive Update Requesters
In our analysis we imagine without loss of generality that the learning algorithm A draws an i.i.d. sequence of random variables r ~ p (that encodes all the randomness to used over the course of the updates) from some distribution P, and passes it to the unlearning algorithm RAA Note is drawn once the initial training, and given r, A and RA become deterministic mappings. We can also view the state sf deterministic mapping of r, the update requests so far u = (u²,.... ...., ...,,, u²),
and the original data set D We write s' = =g'(D) uS r) for some deterministic mapping g¹. We can therefore summarize the trajectory of the algorithms (AA, Ra) follows.
L 0: draw r ~ pm, let 0 = A(D) = A(D;r), and 60t = Spubiich (0")
f 1: = , 11 where s = g (DO, st-1 r). and rift = ft pablish (0').
In this view, the randomness r used by the learning algorithm A and the subsequent invocations of the unlearning algorithm R is represented as part of the internal state. Past analyses of unlcarning algorithms have crucially assumed that is statistically independent of the updates (u², uu....) (which is the case for non-adaptive update requesters, but not for adaptive update requesters). In the following general theorem, we show that if learning/unleamnnng pair satisfies unlearning guarantees against non-adaptive update requesters, and the publishing function is differentially private in the internal randommess r, then the resulting algorithms also satisfy unlearning guarantees against adaptive update requesters. Note that what is important is that the publishing algorithms are differentially private in the internal randomness r, not in the datapoints used for training.
Theorem 4.1 (A General Theorem). Fix a pair of learning and unlearning algorithms (A.RA) and the publishing functions (fmmicae Suppose for every round t, the sequence of publishing functions
A Jpunusr de St is (e, diiffeerentill private in r ~ pm for 0 < S 1/2 and 0 < 8 < E. Suppose RA is a non con-adaptive (a, (,,7),))mma -uullerannn algorithm for A. Then RA is an (a', "'),""""""uleeeeel" >-m-llrrrnn algorithm for A a' = a + 6,,8' = Bee + Vo.7' = 7 + V8 where e' O (e2m+me + mm/of and 8' -mm +0 (mvo
The proof can be found in the Appendix, but at an intuitive level, it proceeds as follows. Because does not change the joint distribution update requests and internal state, we can imagine in our

---

Algorithm 2: Adisu; Distributed Learning Algorithm
Input: dataset D = D of size
Draw the shards: D = Sampler( er p). for every i E [k]-
Train the models: 0g Asinglo (D.), for every i [k].
Save the state: 8 = )E( (() // to be used for the 1st update.
Output: HEjj
analysis that is redrawn after each update request from its conditional distribution, conditioned on the observed update sequence so far. Because the publishing function is differentially private in r, by the fact that post post-procsssing preserves differential privacy (Lemma 2.1). so is the update sequence. We may therefore apply the max-information bound (Theorem 2.1b. which allows us to relate the conditional distribution on r to its original (prior) distribution p But resampling from pm removes the dependence between and the update sequence, which places in the non non-adaptive case, and allows us to apply the hypothesized unlearning guarantees for nonadaptive update requesters.
5 Distributed Algorithms
In this section, we describe general family of distributed learning and unlearning algorithms that are in the spirit of the "SISA" framework of Bourtoule et al. [2021] (with one crucial modification). At a high level, the SISA framework operates by first randomly dividing the data into & "shards", and separately training model on each shard. When new point is deleted, it is removed from shards that contained it, and only the models corresponding to those shards are retrained. The flexibility of this methodology is that the models and training procedures used in each shard can be arbitrary, as can the aggregation done at the end to convert the resulting ensemble into predictions: however these choices are instantiated, this framework gives (0, O, 0) uullearnnin algorithm against any non-adaptive update requester (Lemma 5.T). Here we show that if the shards are selected independently of one another, then we can apply reduction given in the previous section with m and obtain algorithms that satisfy deletion guarantees against adaptive update requesters.
A distributed learning algorithm Adistrr 2 + O* is described by single-shard learning algorithm Asingle Z > O and routine Sampler, used to select the points in a shard. Sampler, given [0, 1], includes each element of D in the shard with probability
dataset D and some probability
Distributed learning algorithm Addistr creates independent shards from the dataset D of size by running Sampler times and training a model with single on each shard i [k] to form an ensemble of k models. To emphasize that the randomness across shards independent, we will instantiate independent samplers Sampler er, and training algorithms A, Asingle for each shard E [4.]. We formally describe Adistr in Algorithm 2
The state s of the unlearning algorithm AaAu records the l shards (D:); and the ensemble of models {0,}: Thus S = { x @+_ As an update request u is received, the update function removes the data point from every shard that contains it (for deletion) or adds the new point to each shard with probability p (for addition). In either case, only the models corresponding to shards that have been updated are retrained using Asingl We formally describe R in Algorithm 3
First, we show that the update requester is non non- aon-adaptive, R (0, O, 0) unleammnng algorithm:
Lemma 5.1. RA is a non-adaptive (0, 0, 0) umleernnnn algorithm for Adistr
Now, by combining Lemma 5.1 and our general Theorem 4.1 we can show the following:
Theorem 5.1 (Unlearning Guarantees). If for every round the sequence of publishing functions (Spusssh Je is (e, didifffernttilllyyy private in the random seeds r phe of the algorithms for 0 < e < 1/2 and 0 < 8 < e, then R is an (a, B, (. unnulernni algorithm for Alistr where
(Ve-ek Ve-ck++V58/
a -= o (2kkbVo6l)
3 ==x=0
Next, we bound the time complexity of our algorithms:
7

---

Algorithm 3: Rum=: Distributed Unlearning Algorithm: t'th round of unlearning
Input: dataset D update v' = (z* "), state s = ((D) "eeta (0; if = 'delete'' then
he(a)
S {i E [k] 2t E D } // the shards zt belongs to. else
S = {i E [k:] Sampler, ((=*) }.') p)
# ()) // the shards 2t will be added to. i
D D o n
Update the shards: D =
for every i E [k].
DJ-1
otherwise
Update the models: 0-- Asingle (D))
if
for every E [k].
00-1
otherwise"
Update the state: sf = (1 10) he(H) // to be used for the next update. Output: {0] [i]
Theorem 5.2 (Run-time Guarantees). Let p L/ki Suppose the publishing functions satisfy the differential privacy requirement of Theorem 5.1 Let N' denote the number of times Re calls Asingle at round I. We have that N = k; and every round I, 2 1: 1) if the update requester is non non-adaptive, for every &, with probability at least - E. N < + /2log (1/E). 2) if the update requester is adaptive, for every &, with probability at least 1 - &. N S 1 / log ((n + ()/E). Furthermore, for & >> 8', with probability at least 1 - -,, we have
No S 1 + min { 222lo (2(n + 1)/(5 - (8)),, v 22' + 2 2og (2/(E - -8))
where 6' = -0 (2 kv/lc) and 8' = = +0 15/6)
The proof can be found in the appendix, but at a high level it proceeds as follows. For a deletion request, we must retrain every shard that contains the point to be deleted. For non-adaptive deletion request, we retrain one shard in expectation and we can obtain a high probability upper bound by using a Hoeffding bound. In the adaptive case, this may longer be true, but there are ways to obtain upper bounds that correspond to the two bounds in our Theorem. We can provide worst-case upper bound on the number of shards that any of the data points belongs to, which incurs cost of order Vlog n. Alternately, we can apply nax-information bounds to reduce to the non-adaptive case, using an argument that similar our reduction for deletion guarantees.
Remark 5.1. We note that there is alternative algorithm that one might consider, resulting from group differential privacy. If a learning algorithm satisfies =ddifferential privacy, a valid unlearning procedure is to do nothing for k updates and then fully retrain on the (k: + 1yth update. This follows from the e-differential privacy guarantee the algorithm will have for groups of size k. Our algorithm substantially outperforms this alternative algorithum as well, namely because our privacy parameter degrades much slower than in this group privacy baseline. Our analysis leverages adaptive composition of privacy across the publishing functions which means that privacy degrades with the square root of the number of updates, while it degrades linearly with group privacy. Consequently the group privacy baseline would require full retraining every k updates, but our algorithm requires a full retraining only every 222 updates.
5.1 Private Aggregation
We briefly describe how we serve prediction requests by privately aggregating the output of the ensemble of models such that the published predictions are differentially private the random seeds At each round f, while Rdiar is waiting for the next update request ='-!, we receive prediction requests and serve predictions ÿ. For each prediction request, we privately aggregate the predictions made by the ensemble of models (0)): Dwork and Feldman (018)) show several ways to privately aggregate predictions (one simple technique is to use the exponential mechanism to approximate the majority vote). Suppose we aggregate the predictions made by the ensemble of models using PrivatePredict' : @ x + ), which takes in an ensemble of & models and a data point, aggregates predictions from the ensemble models, and outputs a label that is é' eddifferentially private
8

---

in the models. If we receive 1' many prediction requests (af....,,z)) 2/.) before our next update request w-11, we can write (if,...., oi.e) = fuuhiish ((0[)) where 1jj Pri PrivatePredict (.. x²)).
Theorem 5.1 tells us that desired unlearning parameters (a, 3, 7) can be obtained by guaranteeing that the sequence of predictions is (c, 6) differentially private in the models (and hence r), for target parameters c, 6. As we serve prediction requests using PrivatePredictt" our privacy loss will accumulate and eventually exhaust our budget of (c, (c.5)-difffrentia privacy. Hence we must track our accumulated privacy loss in the state of our unlearning algorithm, and when it is exhausted, fully retrain using Adistr This resamples r and hence resets our privacy budget. Standard composition theo- rems (see Dwork and Roth 2 show that we exhaust our privacy budget (and need to fully retrain)
every time the number of prediction requests made since the last full retraining exceeds
8(e (n())
We formally describe this process denoted as appendix and state its unlearning guarantee in Theorem 5.3
e, k) in the
Theorem 5.3. The models {[ in Piivaterredcciio/nnerrcciiii (a, B, 7) unlearning guarantee for Adiarr where a = oeek+ and 3,7 =
k) satisfy
( Ve-ek 2k + kkooT) if0 < 100< and <ôcE.
Evaluation of Unlearning Guarantees
In this section we consider the white-box setting in which the models in each shard are made public. SISA continues to have perfect deletion guarantees against non- adaativee deletion sequences in this set- ting. Experimental results on CIFAR-10 Krizhevsky and Hinton] 2009). MNIST (Lecun et al. [998). and Fashion-MNIST [Xiao et al. 2017] show both the failure of SISA to satisfy adaptive deletion guar- antees, and give evidence that differential privacy can mitigate this problem well beyond the setting of our theorems while achieving accuracy only modestly worse than SISA. The code for our experiments can be found at httts:
cwm/ Chr www.tteeaaaatttiitseee wwwpaaapptteaaaeieeeeeeeeee machine- wnl marneng
We train SISA with an ensemble of convolutional neural networks on several datasets of points with categorical labels. Given new point at query time, each model in the ensemble votes the most likely label and aggregates their votes. The models are exposed publicly. This scheme has perfect non-adaptive deletion guarantees.
To construct an adaptive deletion sequence to falsify the hypothesis that the scheme has adaptive deletion guarantees, we exploit the observation that neural networks are often overconfident in the correct label for points on which they have been trained. For each training point, we guess that falls into the shard corresponding to the model that has the highest confidence for the correct label. We then delete points for which we guess that they fall into the first k/2 of the shards, and do not delete any others. After deleting the targeted points, we compute test statistic: the indicator of whether the average accuracy of the models from the targeted shards is lower than the average accuracy of the models from the non-targeted shards. Under full retraining, by the symmetry of the random partition, the expectation of this test statistic is 0.5. Thus under the null hypothesis that the deletion algorithm satisfies perfect deletion guarantees, the test statistic also has expectation 0.5. Therefore, to the extent that the expectation of the indicator differs from 0.5, we falsify the null hypothesis that SISA has adaptive data deletion guarantees, and larger deviations from 0.5 falsify weaker deletion guarantees.
We run this experiment on three datasets (CIFAR- 10, MNIST, and Fashion-MNISTT), and plot the results in Figure ! We then repeat the experiment by adding various amounts of noise to the gradients in the model training process to guarantce finite levels of differential privacy (though much weaker privacy guarantees than would be needed to invoke our theorems). We observe that on each dataset, modest amounts of noise are sufficient to break our attack (i.e. 95% confidence intervals for the expectation of our indicator include 0.5, and hence fail to falsify the null hypothesis) while still approaching the accuracy of our models trained without differential privacy. This is also plotted in Figure This gives evidence that differential privacy can improve deletion guarantees in the presence of adaptivity even in regimes beyond which our theory gives nontrivial guarantees.
Full experimental details can be found in the appendix.

---

Ensemble Test Accurac
0.53
0.86
0.0
Ensemble Test Accuracy
0.98
0.51
0.85
0.4
0.49
0.22
0.84
0.94
0.6
0.47
0.3
Ersemble
0.82
0.93
0.25
0.89
0.5
0..7
0.8.3
1.0
0.5
0.67
0.83
1.0
01.5
0.67
0.83
1.0
Expoctation Indicator
Expectation of Indicator
Expoctation Indicator
(a) CIFAR-100
(b) Fashion-MNIST
(c) MNIST
Ensemble Test Accuracy
0.48
Ensemble Test Accuracy
0.84
Ensemble Test Accuracy
0.97
0.0
0.46
0.82
0.96
0.8
0.44
0.2
0.8
0.7
0.96
0.25
0.42
0.95
0.3
1.0
0.39
0.76
0.95
0.37
0.74
0.94
0.5
0.67
0.83
1.0
0.67
0.83
0.67
0.53
1.0
Expectation of Indicator
Expectation indicator
Expectation Indicator
(d)
CIFAR-1O
(e) Fashion-MNIST km
MNIST 2
Figure 1: The top row and bottom row show experiments with k: = 6 and k = shards respectively. The 3 columns report on 3 datasets. The æ axis denotes estimated expectation of our test statistic (the null hypothesis is expectation 0.5). The y axis denotes the accuracy of the ensemble after deletion. Each point is annotated with the noise multiplier used in DP-SGD, the standard deviation of Gaussian noise applied to gradients during training. A label of 0.0 for point represents the baseline case of no noise (original SISA algorithm). Points are affixed with 95% confidence intervals along both axes (over the randomness of repeating the training/deletion experiment). Horizontal confidence intervals that overlap the line denoting expectation 0.5 fail to reject the null hypothesis that the algorithm has adaptive data deletion guarantees p 0.05. We get to this point with level of noise addition that results in only a modest degradation in ensemble performance compared to SISA.
7 Conclusion and Discussion
We identify an important blindspot in the data deletion literature (the tenuous implicit assumption that deletion requests are independent previously released models), and provide very general methodology to reduce adaptive deletion guarantees to oblivious deletion guarantees. Through this reduction we get the first model and training algorithm agnostic methodology that allows for deletion of arbitrary sequences of adaptively chosen points while giving rigorous guarantees. The constants that our theorems inherit from the max information bounds Rogers et al. [2016] are such that in most realistic settings they will not give useful parameters. But hope that these constants will be improved future work, and we give empirical evidence that differential privacy mitigates adaptive deletion "attacks" at very practical levels, beyond the promises of our theoretical results. We note that like for differential privacy, the (a, 3, -ddeletio guarantees we give in this paper are parameterized, and are not meaningful absent specification of those parameters. There is risk with such technologies that they will be used with large values of the parameters that give only very weak guarantees, but will be described publicly in way that glosses over this issue. We therefore recommend that if adopted in deployed products, deletion guarantees always be discussed in public in way that is precise about what they promise, including the relevant parameter settings.
Acknowledgements
V.G., C.J., A.R., and S.S. were supported part by NSF grants and AF-1763307, and grant from the Simons Foundation.
10

---

References
Raef Bassily, Kobbi Nissim, Adam Smith, Thomas Steinke, Uri Stemmer, and Jonathan Ullman. Algorithmic stability for adaptive data analysis. SIAM Journal on Computing, (0):STOC16-377, 2021.
Lucas Bourtoule, Varun Chandrasekaran, Christopher Choquette-Chon Hengrui Jia, Adelin Travers, Baiwu Zhang, David Lie, and Nicolas Papernot. Machine unlearning. In Proceedings of the 42nd IEEE Symposium on Security and Privacy, San Francisco, CA., 2021.
James Bradbury, Roy Frostig. Peter Hawkins, Matthew James Johnson, Chris Leary, Dougal Maclaurin, George Necula, Adam Paszke, Jake VanderPlas, Skye Wanderman-MMihe and
Qiao Zhang. JAX: composable transformations of Python+NumPy programs, 2018. URL
http://githut: com/ coon/google/jar
Yinzhi Cao and Junfeng Yang. Towards making systems forget with machine unlearning. In 2015
IEEE Symposium on Security and Privacy, pages 463-480. IEEE, 2015.
Cynthia Dwork and Vitaly Feldman. diwacc-preservvin prediction. CoRR, abs/1803. 2018.
URL http://arxiv. org/ abs////////1/// 10266
Cynthia Dwork and Aaron Roth. The algorithmic foundations of differential privacy. Foundations and Trends in Theoretical Computer Science, 9(3-4):211 100-2111,77,, 2014.
Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, Iya Mironov, and Moni Naor. Our data, ourselves: Privacy via distributed noise generation. Annual International Conference on the Theory and Applications Cryptographic Techniques, pages 486-503. Springer, 2006a.
Cynthia Dwork, Frank McSherry. Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Theory of cryptography conference, pages 265-284. Springer, 2006b.
Cynthia Dwork, Vitaly Feldman, Moritz Hardt, Toniann Pitassi, Omer Reingold. and Aaron Roth. The reusable holdout: Preserving validity in adaptive data analysis. Science, 349(6248))636-6338 2015a.
Cynthia Dwork, Vitaly Feldman, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Aaron Roth. Generalization in adaptive data analysis and holdout reuse. In Proceedings of the 28th International Conference on Neural Information Processing Systems- 2, pages 2358- 2015b.
Cynthia Dwork, Vitaly Feldman, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Aaron Leon Roth. Preserving statistical validity in adaptive data analysis. In Proceedings of the forty-seventh annual ACM symposium Theory of computing, pages 117-126, 2015c.
Matt Fredrikson, Somesh Jha, and Thomas Ristenpart. Model inversion attacks that exploit confidence information and basic countermeasures. In Indrajit Ray, Ninghui Li, and Christopher Kruegel, editors, Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security, Denver, CO, USA, October 12-16, 2015, pages 1322-1333. ACM, 2015. doi: 10. 145/ 0510103.2813677 URL http:/tttt://ooo org/ 10. 1145/ 2813677
Antonio Ginart, Melody Y. Guan, Gregory Valiant, and James Zou. Making Al forget you: Data deletion in machine learning. CoRR, abs/1907.05012, 2019. URL httt:://arxii org/abs. /bs/
1907. 05012
Aditya Golatkar, Alessandro Achille, Avinash Ravichandran. Marzia Polito, and Stefano Soatto. Mixed-privacy forgetting in deep networks, arXiv preprint arXiv:2012.13411, 2020a.
Aditya Golatkar, Alessandro Achille, and Stefano Soatto. Forgetting outside the box: Scrubbing deep networks of information accessible from input-output observations. In European Conference on Computer Vision, pages 383-398. Springer, 2020b.
Chuan Guo, Tom Goldstein, Awni Hannun, and Laurens van der Maaten. Certified data removal from machine learning models. arXiv preprint arXiv:1911.03030 2019.
11

---

Avinatan Hassidim, Haim Kaplan, Yishay Mansour, Yossi Matias, and Uri Stemmer. Adversarially robust streaming algorithms via differential privacy. In Hugo Larochelle, Marc' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tiee Lin, editors, Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, neeurinuipp httppaprr/220//aah////0 http:///000000000023000666666660 Abstrratt.....toaoo html.
NeurlPS 2020, December 6-12, 2020, virtual, 2020. URL htt.htttt/::ppoceeeeee
The U.K. Information Commissioner's Office ICO. Guidance on the ai auditing framework. Draft Consultation, 2020. URL https://ico
the htt.://www...................oo.
Christopher Jung, Katrina Ligett, Seth Neel, Aaron Roth, Saeed Sharifi-Malvajerd,, and Moshe Shenfeld. A new analysis of differential privacy's generalization guarantees. In 1/th Innovations in Theoretical Computer Science Conference (ITCS 2020), volume 151, page 31. Schloss Dagstuhl- Leibniz-Zentrum fuer Informatik, 2020.
Alex Krizhevsky and Geoffrey Hinton. Learning multiple layers of features from tiny images. 2009.
Yann Lecun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. In Proceedings of the IEEE, pages 2278-2324, 1998.
Seth Neel and Aaron Roth. Mitigating bias in adaptive data gathering via differential privacy. In International Conference on Machine Learning, pages 3720-3729. PMLR, 2018.
Seth Neel, Aaron Roth, and Saeed Sharifi-Malvaeedii Descent-to-delete: Gradient-based methods for machine unlearning. In Algorithmic Learning Theory, pages 931-962. PMLR, 2021.
Nicolas Papernot, Shuang Song, Ilya Mironov, Ananth Raghunathan, Kunal Talwar, and Úlfar Erlingsson. Scalable private learning with pate, 2018.
Nicolas Papernot, Abhradeep Thakurta, Shuang Song, Steve Chien, and Ulfar Erlingsson. Tempered sigmoid activations for deep learning with differential privacy. The 35th AAAI Conference Artificial Intelligence, 2021.
Ryan Rogers, Aaron Roth, Adam Smith, and Om Thakkar. Max-information, differential privacy, and post-selection hypothesis testing. In 2016 IEEE 57th Annual Symposium Foundations of Computer Science (FOCS), pages 487-494. IEEE, 2016.
Ayush Sekhari, Jayadev Acharya, Gautam Kamath, and Ananda Theertha Suresh. Remember what you want forget: Algorithms for machine unlearning. arXiv preprint arXiv:2103.03279, 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), pages 3-18. IEEE, 2017.
Michael Veale, Reuben Binns, and Lilian Edwards. Algorithms that remember: Model inversion attacks and data protection law. CoRR, abs/ abs//180.0444 807.04644,, 2018. httpbbttpp///axxw..rrgg / 1807.04644
Han Xiao, Kashif Rasul, and Roland Vollgraf. Pashion-mnist: a novel image dataset for benchmarking machine learning algorithms. 2017.
12


Reviews:
[{"review_id": "p3VjAZHOFH", "reviewer": "Reviewer_bzCs", "summary": "This paper studies data deletion algorithms in an adaptive updating scenario.\n\nFirstly, the authors define (adaptive) ($\\alpha$,$\\beta$,$\\gamma$)-unlearning guarantee as well as its non-adaptive version for data deletion algorithms. With the techniques borrowed from differential privacy, the authors prove that an algorithm with the non-adaptive unlearning guarantee can be reduced to an algorithm with the adaptive unlearning guarantee.\n\nSecondly, the authors apply the theoretical results to SISA unlearning algorithm. Specifically, an updating algorithm for SISA is proposed, which satisfies the adaptive unlearning guarantee. The authors also give an example showing that there exists updating algorithms that do not satisfy the adaptive unlearning guarantee.", "questions": "", "limitations": "", "rating": 7, "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": "This paper tackles a very important problem, unlearning problem, and the authors do a good job of solving it in the context of adaptive (un)learning. The authors perfectly apply adaptive differential privacy into the field of machine unlearning, and are the first that formalize and solve the adaptive unlearning problem.\n\nI only have one question remained: can the authors estimate the $\\alpha$, $\\beta$, and $\\gamma$ parameters in the adaptive unlearning guarantee?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "This paper does not have any potential negative societal impact.", "review_text": "", "extra_scores": {"ethical_concerns": "None.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "jR-ii3-EQf", "reviewer": "Reviewer_cu9f", "summary": " considers the problem of machine unlearning against an adaptively generated sequence of unlearning requests. The authors work with the SISA framework (Bourtoule et. al.) for machine unlearning where the key idea is as follows: Divide the data into k shards, train separate models on each shard and then aggregate their prediction to get the final output on a test sample. During unlearning, figure out the shard that contains the point that wants to be deleted and then retrain the model on that shard and aggregate, keeping the rest of the models unchanged. \n\nThe goal of this unlearning framework is that the output model after unlearning is similar (in a probabilistic sense) to the model that we get after retrained from scratch on the left over data points, and at the same time ensure that the unlearning mechanism is computationally more efficient as compared to retraining from scratch. One benefit of the provided SISA mechanism is that it achieves both of these goals for arbitrary learning algorithms and for convex / non-convex models. \n\nThe main contributions of the paper are as follows: \n(a) They show that the SISA algorithm from Bourtoule et. al. fails to provide good performance guaranteed when used for unlearning adaptively generated delete requests. \n\n(b) They provide a general reduction using differential privacy to get unlearning algorithms that work for adaptive delete requests from unlearning algorithms that guarantee success with oblivious delete requests only. This reduction is based on using differential privacy to constraint the adversary from generative adaptive unlearning samples. \n\n(c) They use this general framework to get a SISA algorithm for adaptive unlearning requests. They show experiments comparing their algorithm to standard-SISA.\n", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "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": "I found the paper somewhat unsatisfactory. My main reasons are:\n(a) An important baseline algorithm to compare to is the one based on simple group DP. The algorithm is as follows: \n\nLearning phase (L):\n- Train a learning algorithm A^{single} on the entire dataset D. \n- Make it (\\eps, \\delta)-group DP by adding noise to the output / while training, so that the learnt model is private w.r.t. datasets differing in m points.  \n\nUnlearning phase (UL):\n- Do not do anything except for the following restarts. \n- On every (m + 1)-th request, retrain the model from scratch on left over data points using the learning procedure L. \n\nIn the above, the unlearning phase simply does not do anything,  except for at every (m+1)-th request when it retrains from scratch on the left over datasets (and adds noise again to get (\\eps, \\delta) group DP w.r.t. m points). The group DP guarantees should ensure that we unlearn against adaptive adversaries.  \n\nDiscussion of the above algorithm w.r.t. the algorithm provided in the paper: \n- The algorithm in the paper also adds noise for the prediction after every step. Is there any difference in the scale of the noise that is added in the provided algorithm and the one needed to get group DP (above). \n- As shown in Algorithm 4 in the appendix, the algorithm ini the paper also retrains from scratch after a certain privacy threshold is attained. \n- Under observation 1 and 2, the algorithm provided in the paper seems to be very similar to the one I described above. What are the differences? I think it is important to verify, at least experimentally, whether the provided algorithm is better than the above simple DP based algorithm in terms of performance. \n- The above mentioned algorithm does nothing during unlearning and is thus computationally better than the proposed algorithm in the paper which retrains on the relevant shared after every delete requests. \n\n(b) There is a small issue with the illustrative example given in Section 4.1. Here, the behavior of the model output by retraining algorithm is slightly different that what was stated. According to the setup, every data point has exactly two copies. Once we delete the samples that are in different shards, we are left with at most one copy of those data points in the dataset. Thus, no matter how we split the dataset during retraining, the aggregating algorithm will fail to perform well on these points. Thus the performance of the retraining from scratch is smaller than ⅔ (as stated in the paper). \n\nFurthermore, it seems that in order to show a meaningful separation, the unlearning algorithm needs to delete a constant fraction of the dataset. If the unlearning requests leave spare any points which were in different shards in the first split, then with constant probability they can go to the same shard in the second split. This would further diminish the gap between the performance of the unlearnt model and the model that retrains from scratch. I should also mention that it has been observed in some other works (e.g. Theorem 2 in Sekhari et. al. 2021): That paper seems to show that there exists some problems where it is impossible to delete a constant fraction of the dataset while still retaining test performance. Is there any deeper connection between the two examples that would suggest limits on unlearning? \n\nCan we show that there are problems where the model after unlearning and retraining from scratch are significantly different after unlearning m points adaptively, where m = o(n) (little O). \n\n(c) Definition 2.3 requires the base algorithm A to be randomized. This seems unnecessary - why add any noise to the base algorithm when there are no unlearning requests yet. The added noise can hurt the test performance. \n\n(d) As shown in the experiments, the performance for even simple problems like CIFAR-10 and MNIST degrade for the provided algorithm (0.5-0.6 for CIFAR 10 and 0.9 for MNIST). Is that necessary? What would be the performance of the algorithm that just adds noise to ensure DP (or group DP) and then does nothing for unlearning? \n\nI think that it is important to compare the performance of the provided model against vanilla DP to say that the unlearning algorithm is doing anything better. As of now, it seems that in terms of both final accuracy and running time, group DP based simple approaches may be better. \n\nPaper writing: \nIt is a well written paper. In order to improve clarity, it might be useful to make explicit what the different functions and operators are for the illustrated examples. \n\n\nI would be happy to change my score depending on the answers to my questions above. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "10-14 hours"}, "extra_text": {}}, {"review_id": "h4iNfnGfWTO", "reviewer": "Reviewer_QxA8", "summary": "The paper highlights an important problem in machine unlearning in which privacy can be lost between deletion requests if the deletion requests are chosen based on the published intermediate models (e.g. model predictions, the models themselves, etc.), even if the unlearning mechanism guarantees exact deletion for non-adaptive deletion sequences (e.g. the SISA framework).\n\nThe paper then shows that if an unlearning approach provides guarantees against non-adaptive deletion sequences, and differential privacy can be used to obfuscate the internal randomness of the intermediate models, then that unlearning approach satisfies data deletion guarantees against an adaptive sequence of deletions.", "questions": "", "limitations": "", "rating": 7, "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": "Strengths\n\nAs far as I know, this is original work on addressing an important problem of possible privacy leakage via the intermediate publishing of models between machine unlearning updates in response to deletion requests. It combines well-established methods of machine unlearning and differential privacy to provide a framework for developing new machine-unlearning algorithms with adaptive data deletion guarantees.\n\nThe theorems in the paper are supported by proofs in the supplemental materials that appear to be technically sound.\n\nI think this is a relatively new and under-explored topic in the burgeoning field of machine unlearning, one that may be very important for any parties interested in adhering to legislation surrounding the \"Right to be Forgotten.\"\n\n\nWeaknesses\n\nThe paper is organized well and follows a logical order; however, I think the paper could benefit from some simple examples early in the paper to enhance the understandability of the topic, especially the difference between non-adaptive and adaptive deletion sequences.\n\nI think there could be a clearer discussion or perhaps definition about how some currently existing machine unlearning approaches already satisfy adaptive deletion guarantees while others do not.\n\nThe work seems to be mainly based on the SISA unlearning framework; can this methodology be adapted to other machine unlearning approaches / frameworks?\n\nDoes the proposed approach of making a non-adaptive unlearner into an adaptive unlearner incur any deletion efficiency costs? Or does the cost mainly affect predictive performance?\n\nThe amount of added noise needed to reject the null hypothesis (Figure 1) actually seems to cause a significant degradation in predictive performance; most notably for Fashion-MNIST (k=2 and k=6) and MNIST (k=6).\n\nMinor Weaknesses\n\nFigure 1(f - bottom) has duplicate numbers on the y-axis.\n\nHow much privacy is lost when using an adaptive deletion sequence over a non-adaptive deletion sequence?\n\nHow would a machine-learning practitioner go about selecting values for the hyperparameters: alpha, beta, and gamma?\n\n\n===========POST-REBUTTAL RESPONSE============\n\nI thank the authors for their detailed and thorough response. I think the authors do a solid job of highlighting a new under-explored problem in machine unlearning, and propose a solution that adapts a popular method of machine unlearning to the adaptive deletion case; thus, I have increased my score to 7 (good paper; accept). In the next revision, I encourage the authors to provide clear illustrative examples of adaptive deletion early in the paper to more cleanly delineate between adaptive and non-adaptive deletion sequences. I also think a more thorough discussion that describes what existing unlearning approaches already satisfy the adaptive deletion case could be beneficial.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5.5"}, "extra_text": {}}, {"review_id": "0S907g8FmO6", "reviewer": "Reviewer_bBvQ", "summary": "The paper considers the task of machine unlearning with the modification that the deletion requests are adaptive i.e. they are a function of the random outputs (published model/predictions). The authors propose a generic reduction to convert oblivious unlearning methods to adaptive unlearning methods with small degradation in unlearning criteria.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "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": "Briefly, the machine unlearning problem is as follows: after model is trained on a dataset, there is request to delete a point from the training dataset. The goal is to design an efficient (faster than retraining) method such that its output is nearly indistinguishable from what we would have obtained had we trained on the dataset without the point. \nThe paper considers an interesting and important modification to the above setup: what if the choice of points to be deleted are *adaptive* i.e. they are selected as a function of the previous random output --  they motivate it by saying that users may choose to delete their data based on what the model reveals about them. While the problem of machine unlearning is in general important and has gained considerable attention recently, the modification is also well-motivated and interesting. One thing to note is that adaptivity considered in the paper is only with respect to *published* models and not the entire random state; however, this is reasonable too.\n\n**General applicability of the reduction**: The paper makes a general sounding claim: a reduction to make (many?) oblivious unlearning methods adaptive. But I am not sure if there are many (known) methods where the reduction can be applied. The key idea is to make the published outputs differentially private - however the input (using which DP is defined) is not the dataset but $m$ i.i.d. bits used to generate the published output. Are there many methods which sample $m$ i.i.d values to generate the published state? It seems to me that the natural (and perhaps only?) candidates are aggregation/bagging based methods, where the each i.i.d. random variable corresponds to a bag. That authors instantiate their reduction using a known method SISA (Machine Unlearning, 2020. Bourtoule et al.), which is indeed of this nature. A few examples (other than aggregation) would help access the generality of the claim.\n\n**No accuracy guarantees**: My major complaint is that, even though the authors present the result as a general reduction which hopefully can be applied to many existing methods, when they instantiate it with SISA , they provide no accuracy guarantees, even in say, convex learning settings. I don't know whether there exist no known accuracy guarantees for SISA, or the authors skipped this on purpose. But without accuracy guarantees, it is hard to evaluate if the proposed methods have overall non-trivial guarantees. From a theoretical viewpoint, I can simply take a constant function as my learning algorithm, it has has no accuracy guarantees, but it is trivial to unlearn, even with adaptive updates. I hope that the authors present rigorous accuracy analysis to identify regimes of accuracy where this method is provably *better* than deterministic retraining.\n\n**Unlearning runtime guarantees**:\nSince there are no accuracy guarantees, one avenue to access improvement is to consider the unlearning runtime of the proposed method against original (non-adaptive) method on adaptive edits.\nIf we do (non-adaptive) SISA training, then w.h.p. the worst data point can at most be in $\\log n $ shards, so we retrain $\\log n$ times and have **perfect** unlearning against adaptive updates.\nIs the goal to shave this $\\log n$ factor? \nThe authors proposal gives an approximate unlearning method (rather than perfect unlearning), and we replace this $\\log n$ with a function of unlearning parameters. So, at best the result is a trade-off -- however, the choice of unlearning parameters with a *hand-wavy* accuracy analysis makes me doubt if this trade-off is good (see \"Unlearning parameters\" below)\n\n**No $\\log n$ and modified SISA**:\nThe authors consider SISA wherein they do sampling with replacing to construct the shards. Instead, if we do sampling without replacement, or if the dataset is i.i.d, as is typical in ML, we can just consider any deterministic partitioning. Then, unlearning time, with SISA, is constant, even for adaptive requests. In fact, in the original paper (Machine Unleraning, 2020), the authors say in Section B.1 \"Sharding\" -- *\"By dividing the data into disjoint fragments and ...\"*. Further discussion in this paragraph also points to a partitioning, even if randomized. Please answer if/how the above reasoning is incorrect, and if it is indeed correct, then why did the authors not mention this crucial change to the SISA method?\n\n**Unlearning parameters**:\nIn differential privacy, it is standard to consider $\\epsilon< $ \"small constant\" say two for reasonable privacy properties, and the same reasoning can be imported to the unlearning probabilities. In theorem 4.1, the parameter $\\alpha = O(\\epsilon^2 k)$ roughly, so for meaningful unlearning guarantees, we want $\\epsilon = 1/\\sqrt{k}$ -- this is a rather strong privacy guarantee.\nNote that, if aggregation releases an averaged model, then the error due to privacy,\nscales like $O(1/m\\epsilon)$ where $m$ is the number of data points: here $m=k$, so error is $1/\\sqrt{k}$. Thus, to get a good aggregation accuracy, we need large $k$, but then we would suffer in the error of each model in the shard since it is only trained on $n/k$ data points. \nPerhaps we can do better if we only output private predictions than a model. \nA formal accuracy analysis would explain these tradeoffs carefully and show if there is a setting with interesting guarantees.\n\n**Confusion in experiment section**: The authors in line 342 say *`` .. adding various amounts of noise to the gradients in the model to satisfy finite levels of differential privacy (though much weaker privacy guarantees than would be needed to invoke our theorem)\"*.\nIt seems that adding noise to gradients will produce a (standard) DP model output. However, the notion of DP to invoke their theorem is with respect to random bits  parametrizing the state, and is done by randomizing aggregation of predictions/model. Hence, I am confused by this comment, please explain.\n\n**Missing reference to related work**:  A related paper Ullah et al. \"Machine unlearning via algorithmic stability\", 2021, is missing from related work. \nI think (correct me if wrong) this work supports adaptive edits, perhaps with a (similar) logarithmic overhead in unlearning runtime.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No direct societal impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper identifies a new concern in machine unlearning, the role of adaptivity in the request sequence. Specifically, if removal requests may be adaptive, then the unlearning guarantees may be violated. The authors also give a differential privacy based method to mitigate this issue. This is an interesting new phenomenon, and the paper should be accepted.

The authors are suggested to pay attention to the presentation comments made by the reviewers: as machine unlearning is a relatively new field, it is important to make the early papers as well written as possible. 

(As one minor personal comment, I disagree with the authors' response that a drop from 97% to 91% accuracy (MNIST k=6) is relatively small, I would say this is significant when the error rate is so small.)
Decision: Accept (Poster)