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 (e, 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 x2xx) - (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, -ddffferrenti 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- nax-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 Addisrr 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]A)
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 = o 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, -ddeletto 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": "F_hlloLLMnb", "reviewer": "Reviewer_jxp1", "summary": "This paper has showed an interesting solution to the data deletion problem. The method is novel. The authors have identified an important blindspot in the data deletion literature.  However, the experimental validation is weak. ", "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": "In this paper, the authors addressed the data deletion problem, which has become important in business scenarios. Existing methods rely on the implicit assumption that the deleted data points are independent of the randomness used to train the models. However, this assumption is too strong and is not practical in some scenarios. Indeed, the authors  proposed a more generalized scenario, which shows the blindspot in data deletion. Also, they provided a general method to reduce adaptive deletion guarantees. Comparing with the existing methods, the proposed model allows for the deletion of arbitrary sequences of adaptively chosen points while providing rigorous guarantees. While the paper has innovative ideas, it also has some limitations. First, the model is not clearly described. Second, the experimental results are not fully convincing. In the experiments, the authors showed that the deletion guarantees of algorithms in the SISA framework fail for adaptive deletion sequences, however  the effectiveness of the proposed model cannot be fully explained. Finally, the baselines are weak. The authors should compare their methods with the prior studies which do have deletion guarantees.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "1.\tThe model description is not clear.\n2.\tThe experimental results are not convincing.\n3.\tThis paper focuses on the data deletion algorithms and it gives 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. \n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "FZbLMEtw8xw", "reviewer": "Reviewer_6QGG", "summary": "This paper considers the problem of adaptive data deletion in model unlearning. Using the tools of differential privacy and its connection to max information, a general reduction from deletion guarantees against adaptive sequences to deletion guarantees against non-adaptive sequences is provided in Theorem 3.1. Combined with the ideas from prior work which give guarantees for non-adaptive deletion sequences, Theorem 3.1 leads to flexible algorithms, and gives strong provable deletion guarantees for adaptive deletion sequences. It is further shown in theory how prior work for non-convex models fails against adaptive deletion sequences, and a practical attack against the SISA algorithm of Bourtoule et al is prosed and tested on CIFAR-10, MNIST, Fashion-MNIST.", "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": "\nThis paper tries to resolve the adaptive unlearning problem defined in Definition 2.2. Based on my knowledge, the setting of such a problem is novel, but it is not clear to me how practical the main result (Theorem 3.1) is when we try to construct an adaptive unlearning algorithm with theoretical guarantee. \n\nTheorem 3.1 states that if we have a “good” unlearning algorithm in the oblivious setting, and the publishing function is differential private with respect to the internal randomness r, then the same unlearning algorithm is also “good” in the adaptive setting. To my understanding, such a result only provides the sufficient conditions for the same algorithm to work in the adaptive setting. I feel like the differential private assumption might be: 1) too strong, so that the same algorithm works for both oblivious and adaptive setting; 2) impractical, since in general we want the publishing function to be DP with respect to the training dataset. I was expecting a stronger result which tells us how to modify the existing algorithm with weaker assumptions. The authors should provide more discussions on why we should be satisfied with the current Theorem 3.1, and how we can use it to resolve the problem.\n\nThe organization of the paper can be improved. I did not fully understand the adaptive setting studied in the paper until I read section 5.1. I feel like this section should appear earlier in the paper, since it serves as a motivation of the adaptive unlearning problem. Moreover, I feel like the result in section 5.2 is not directly related to the analysis in the paper, it only shows the significance of the problem, but does not demonstrate how resolve the problem. Maybe some applications of the results in section 3 or 4 beyond the SISA framework are more informative and useful. \n\nMinor comments:\n1.\tIn line 112, The notation $\\mathcal{Z}^*$ and $\\Theta^*$ is used without definition.\n2.\tIn line 181, notation $m$ is used before definition, why m is important here?\n\n\nAfter rebuttal:\nThe response resolves some of my questions, and I would like to raise my score to 6, as the problem studied in the paper is quite novel and could lead to more discussion in the future.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I think the authors addressed the limitations and potential negative societal impact of their work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "30Aat_bP5Dg", "reviewer": "Reviewer_FL5i", "summary": "The paper considers the problem of machine unlearning. A general setting is explored, where initially a model is learned on some dataset, and some function of the model is published. Then in following rounds, either a data deletion or a data addition request is received, and its required to update the model in a way that the data request is respected. The authors formalize this in their proposed definition of (alpha, beta, gamma)-unlearning. \n\nContributions.\n1. A formalization of machine unlearning. The paper proposes Definition 2.3 to formally define what it means to do machine unlearning. The definition is fairly general, and bears some similarity to the definition of differential privacy. Though, here, there are two algorithms involved, a learning algorithm, and an unlearning or update algorithm.\n\n2. (Theorem 3.1) Showing that machine unlearning with adaptive data deletion requests (when the requests depend on what was previously published) can be reduced to machine unlearning with oblivious data deletion requests, provided that the publishing functions are differentially private with respect to the random bits used by the learning algorithm. \n\n3. (Theorem 4.1) The authors show how their generic reduction can be applied to obtain machine unlearning guarantees in a distributed learning setting. They compare this with a previously published mechanism (Bourtoule et al. 2021). Though, it's important to note that Algorithm 3 does retrain models from scratch. \n\n4. (Theorem 4.3) The authors instantiate the result in Theorem 4.1 when the publishing functions are private aggregations of predictions. \n\n5. Experiments suggesting that differential privacy can help provide data deletion guarantees on adaptively chosen sequences.\n", "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": " Establishing a connection between differential privacy and machine unlearning is novel in this work to the best of my knowledge. To obtain machine unlearning guarantees against adaptive deletion requests, the authors rely on differential privacy guarantees. While this shows sufficiency of differential privacy, is differentially privacy necessary to obtain such guarantees? This could further motivate the importance of machine unlearning if, for example, it turns out to be an “easier” problem than differential privacy.\n\nIn other words, is Definition 2.3 of (alpha, beta,gamma)-unlearning equivalent in some way to differential privacy? It would be good if the authors could further motivate why this is an appropriate notion of machine unlearning?\n\nIn the framework suggested, if what is being published is differentially private, then why are we looking for data deletion guarantees?\n\nThe paper is clear and easy to follow.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "In my opinion, the authors have adequately addressed the limitations of their work and negative societal impacts of their work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper revisits the problem of machine unlearning in a setting wherein the (training) data deletion requests can depend on the trained model. Authors give guarantees for this adaptive data deletion problem using a general reduction from the non-adaptive settings studied in prior work. A good paper, overall. 
Decision: Accept (Poster)