Remember What You Want to Forget: Algorithms for Machine Unlearning
Authors: Ayush Sekhari
Jayadev Acharya
Gautam Kamath
Ananda Theertha Suresh
Venue: NeurIPS 2021 Poster (2021)
Keywords: Machine unlearning
theory
differential privacy
generalization guarantee
right to be forgotten

Abstract: We study the problem of unlearning datapoints from a learnt model. The learner first receives a dataset $S$ drawn i.i.d. from an unknown distribution, and outputs a model $\widehat{w}$ that performs well on  unseen samples from the same distribution. However, at some point in the future, any training datapoint $z \in S$ can request to be unlearned, thus prompting the learner to modify its output model while still ensuring the same accuracy guarantees.  We initiate a rigorous study of generalization in machine unlearning, where the goal is to perform well on previously unseen datapoints. Our focus is on both computational and storage complexity. 

For the setting of convex losses, we provide an unlearning algorithm that can unlearn up to $O(n/d^{1/4})$ samples, where $d$ is the problem dimension. In comparison, in general, differentially private learning (which implies unlearning) only guarantees deletion of $O(n/d^{1/2})$ samples. This demonstrates a novel separation between differential privacy and machine unlearning. 

Remember What You Want to Forget:
Algorithms for Machine Unlearning
Ayush Sekhari Cornell University as36630corme11. edu
Jayadev Acharya' Cornell University acharya@cornell..o edu
Gautam Kamath University of Waterloo gocsail mii.. edu
Ananda Theertha Suresh" Google Research, NY cheertha@google.com com
Abstract
We study the problem of unlearning datapoints from a learnt model. The learner first receives dataset S drawn i..dd from an unknown distribution, and outputs model w that performs well on unseen samples from the same distribution. However, at some point in the future, any training datapoint thus prompting the learner to modify its output model while still ensuring the same accuracy guarantees. We initiate a rigorous study of generalization in machine unlearning, where the goal is to perform well on previously unseen datapoints. Our focus is on both computational and storage complexity.
can request to unlearned,
For the setting of convex losses, we provide an unlearning algorithm that can unlearn up to On /d//t) samples, where d the problem dimension. In compar- ison, in general, differentially private learning (which implies unlearning) only guarantees deletion of (nn/d1/2) samples. This demonstrates a novel separation between differential privacy and machine unlearning.
Introduction
Many organizations and companies employ user data to train machine learning models for wide array of applications, ranging from movie recommendations health care. While organizations allow users to withdraw their consent from their data being used (at which point the organization will delete the user's data), less savory businesses might covertly retain data. Given the potential for misuse, legislators worldwide have wisely introduced laws that mandate user data deletion upon request. These include the European Union's General Data Protection Regulation (GDPR), the California Consumer Privacy Act (CCPA), and Canada's 's proposed Consumer Privacy Protection Act (CPPA).
of these
There is some natural ambiguity present these guidelines. Is it sufficient to simply delete the user's data, must one also take action machine learning systems that used this data for training? Indeed, by now, privacy researchers are well-aware that user data may be extracted from trained machine learning models (e.g., Shokri al. [2017], Carlini al. [2019]). In potentially landmark decision, the Federal Trade Commission recently ordered company to delete not only data from users who deleted their accounts. but also models and algorithms derived from this data [Federal Trade Commission, 2021]. This suggests that organizations have an obligation to retrain any machine learning models after excluding users whose data has been deleted.
Authors in alphahetical order.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

However, naively retraining models after every deletion request would be prohibitively expensive: training modern machine learning models may take weeks, and use resources of value in the millions. One could instead imagine more careful methods, which attempt to excise the required datapoints from the model: crucially, without incurring the cost of retraining from scratch. This notion is called machine wnlearning. The goal would be to obtain a model which is identical to the alternative model that would be obtained when trained on the dataset after removing the points that need to be forgotten. This requirement is rather strong: Ginart et al. [2019] proposed a relaxed notion of deletion, in which the model must only be close to the alternative, where closeness is defined in a way reminiscent of differential privacy [Dwork et al., 2006a,b] (our variant of this notion is described in Definition 2). This relaxation has inspired the design of several efficient algorithms for data deletion from machine learning models [Guo et al., 2020, Izzo et al., 2021, Neel et al., 2021, Ullah et al., 2021].
As mentioned before, one naive strategy involves retraining the model from scratch, sans the deleted datapoints. When the training dataset is large, this approach is undesirable for several reasons. First, is computationally very expensive. Even iteration over the training data can be too costly, let alone training new model on it. Second, preserving the entire training dataset consumes a significant amount of storage."
Another straightforward approach involves model checkpointing, in which the learner preemptively stores backup models in which certain points have been excluded. While this strategy makes it easy to quickly return an appropriate backup model upon receiving a deletion request, the downside is that one typically has to store number of additional models which scales with the training data size, which may be prohibitively large. As we can see from these examples, computational and storage complexity are two vital metrics when designing a machine unlearning algorithm.
Finally, while there has recently been a wealth of results in machine unlearning, all of it has focused on the core problem of empirical risk minimization, where the goal is minimize the training loss. However, to fulfil the promise of machine learning, we desire algorithms that can generalize to previously unseen test data. Motivated simultaneously by all of these concerns, our goal is to address the following question:
How do we design resource-eficient machine unlearning algorithms which generalize?
Our contributions. We initiate a new line of inquiry in machine unlearning:
We investigate generalization properties of unlearning algorithms, in particular asking: how many samples can we unleam while still ensuring good performance on unseen test data? In comparison, prior work focused on the empirical training loss only.
We consider machine unlearning simultaneously under storage constraints as well as the previously studied computation constraints. Unlike prior work, our algorithms do not require the training data to be available to the unlearning algorithm when deleting samples.
A clean approach for unlearning is to ignore which particular samples are being unlearnt and directly apply known algorithms and guarantees from differential privacy (DP). We show strict separation between DP and machine unlearning.
In particular, algorithms based on DP can delete at most ((n/vd) samples while still retaining test loss performance, where d denotes the dimension of the problem. On the other hand, we provide efficient unlearning algorithms that take into account the particular samples to be unlearnt and show that we can delete up to ((n/d/// samples, thus giving quadratic improvement in terms of dependence of over DP. Our results apply to both strongly convex and convex loss functions.
1.1 Related work
Cao and Yang [2015] introduced the term "machine unlearning." and gave efficient deterministic algorithms for exact unlearning in certain settings. This definition requires an algorithm to have identical outputs on dataset after deleting point, and if that point was never inserted. However, their
FOrthogonal to storage constraints, an additional issue is that govermment regulations may restrict the learner from storing raw user data for extended periods of time due to privacy concerns. However, we focus on storage it captures undesirability of wider range of unsatisfactory solutions.

---

algorithms are restricted to very structured problems only. Bourtoule et al. [2021] provide unlearning algorithms using a sharding- thareing-bbseed based strategy, though weaker unlearning model (requiring only that it be possible that the output may have arisen), and without error guarantees.
Ginart al. [2019] introduced the probabilistic notion of unlearning, inspired by differential privacy [Dwork et al., 2006b.a]. Their definition requires the oulput distribution of the unlearning algorithm to be similar to the output distribution obtained by running the learning algorithm on the dataset without the deleted points. Several recent works [Guo et al., 2020, Izzo et al., 2021, Neel et al., 2021, Ullah al., 2021] provide theoretical error guarantees for various problem settings under this probabilistic notion of unlearning. While our unlearning setup is closely related to that of Ginart et al. [2019] and in the related works, there are two major differences.
First, the prior work focuses on empirical risk minimization [Guo et al., 2020, Izzo et al., 2021, Neel et al., 2021, Ullah et al., 2021]. In their setup, the goal of the unlearning algorithm is to find approximate minimizers of the empirical loss on the remaining training dataset after deleting samples. In comparison, our focus in this paper is on the test loss, and we wish to understand how many samples can be deleted from a learnt model while still ensuring that the updated model performs well on unseen examples (i.e., the generalization error). As we discuss in Section 3.1, the goal of minimizing the training loss is qualitatively different from that of minimizing the test loss.
Second, the prior work focuses exclusively the computational cost of unlearning, without concern for associated storage requirements. This has led to approaches which involve veemory-intensvee checkpointing data structures, which enables fast processing of deletion requests, but consumes potentially impractical amounts of storage. In contrast, we are additionally concerned with memory usage, which highlights the drawbacks of such approaches. Unlike prior work, our algorithms do not require the training data to be available to the unlearning algorithm when deleting samples, and only rely on some cheap-to-store data statistics.
The most closely related work to ours the certified data removal framework of Guo et al. [2020] which provides efficient data deletion algorithms for generalized linear models (linear and logistic regression). While our deletion algorithm is similar to the Newton update removal mechanism considered in their work, there are some important technical differences. First, their unlearning setup requires access to the entire training dataset for deleting samples; we do not require this. Second, they provide theoretical guarantees in terms of the norm of the empirical gradient being small after data removal. In comparison, our guarantees are for the test loss. Third, their unlearning definition requires the learning algorithm to be randomized, and this leads to worse performance guarantees due to added noise. In comparison, we do not need to randomize the learning algorithm. Finally, our guarantees hold for arbitrary convex loss functions and are thus broader in scope.
Several other models of unlearning have been considered. Garg et al. [2020] give an alternative perspective on machine unlearning, grounded in cryptography. Other works in this space focus on exploring privacy risks [Chen et al., 2020] and verification [Sommer et al., 2020] in machine unlearning settings. For specific learning models like SVMs, exact unlearning has been considered under the framework of decremental learning [Cauwenherghs and Poggio, 2001, Tveit et al., 2003, Karasuyama and Takeuchi, 2010, Romero al., 2007]. However, the primary motivation in these works is to use the framework of decremental learning to estimate the leave-one-out error in order to provide generalization guarantees for the learnt model. Finally, there has also been recent empirical and theoretical work in developing definitions and algorithms for machine unlearning with deep neural networks for application domains in computer vision [Du et al., 2019, Golatkar al., 2020a,b, Nguyen et al., 2020].
2 Preliminaries
Let D be a distribution over an instance space 2 and W C Rd be the parameter space of hypothesis class. Let f: W x 2 + R be loss function. The goal is to minimize the test loss population risk (test loss), given by
F(w) En-D[f(w, =)],
where [w, 2) is the loss of the hypothesis corresponding to E W on the instance E Z. Let F' = min F(w) be the value of this minimum and w² be a corresponding minimizer. Since the distribution D is often unknown, we are restricted to rely on samples to find small test loss model.
3

---

Given S = (21, 22...., set of n samples drawn independently from D, standard learning algorithms minimize the empirical loss given by
Fa (ww))= == Σ
[10 zi)-
(2)
1=1
2.1 Learning
Let A g" -> W be learning algorithm that takes the dataset S and returns hypothesis A(S) W. The quality of A is measured in terms of the difference between the population risk of the hypothesis A(S) and the risk of the best hypothesis w" in W, i.e., the excess risk
E[F(A(S)) - FF,
where the expectation over the randomness in and S. This gives natural notion of sample complexity.
Definition (Sample complexity of learning). The y-sample complexity of a problem is defined as ny m n 3A s.t. Eg-D= Eg-D= (F(A(S)) F S7 for all D),
the fewest number of samples with which a y--uuoopimmll minimizer of the population loss F(w) can be achieved for any distribution over the data samples.
For comparing different algorithms throughout the paper, we set y = 0.01 (or any other small arbitrary constant), and require that the provided learning algorithms learn with population risk sub-optimality of at most 0.01. Standard results in learning theory [Bubeck, 2014, Theorem 6.1] show that for convex and strongly convex losses,
110001 = O(1,
(3)
where the hidden constant depends the properties of such as its Lipschitzness, but is independent of the dimension d of the parameter space W C Rd.
2.2 Unlearning
Suppose learning algorithm A over S outputs the model A(S). An unlearning algorithm Á takes as input the model A(S) and a set U C S of data samples that are to be deleted, and is required to output new model w E W. Besides the set U and the model A(S), the unlearning algorithm A can also access some additional data statistics T(S) E TT We emphasize that the unlearning algorithm does have access the entire original dataset S in this resource-constrained setting and hence cannot retrain from scratch.
This set of statistics T(S) captures the additional storage required by the algorithm to support learning. Thus, one of our goals is to minimize [T))), in particular aiming for memory requirements which are independent of the training data size This precludes strategies which involve storing and reusing the entire training set, or aggressive model checkpointing. On the other hand, it permits stor- age of simple statisties such the empirical mean or average gradient of training data points, which may prove useful when unlearning. At the same time, we are still concerned with our unlearning algorithm's 's time complexity. This goes hand in hand with the storage complexity: for most natural algorithms, the two are likely to be polynomially related, Augmented by this set of data statistics T(S), unlearning algorithm is mapping Á n W x
W.
To illustrate our unlearning setup, consider the following toy example: Suppose we train model w with four datapoints S {00.0, 0.1], [2.0, 2.3), [4.0, 0.5), [3.0. 1.3] After training the model, the learner only keeps and a cheap-to-store sufficient statistic T(S). and deletes the dataset S from the memory. At this point the learner does not have access any datapoints from S anymore. Now, when a delete request comes, the request contains just the sample U to be deleted e.g. [4.0, 0.5]. The unlearning algorithm at this point will unlearn this sample, using the information w. T(S), and U = [4.0, 0.5] only. Here, note that the data sample [4.0, 0.5] is provided to the unlearning algorithm by the user who owns this data and requests for its deletion.
We now define notion of unlearning, which motivated by the definition of differential pri- vacy [Dwork et al., 2006a].

---

Definition 2 ((E, unllearnn, For all S of size and delete requests U C S such that [0| S m, and W C W, a learning algorithm A and an unlearning algorithm Á is (e, -unlearning if
PT(A(U,A()),T(S)) E W) c PP X)) E W) +
and
Pr(A(0, A(S US, U)) (U) w) S Pr(A(U, S W) 8,
where 0 denotes the empty set and TS) denotes the data statistics available to A.
The above states that with high probability, an observer cannot differentiate between the two cases (i) the model is trained on the set S and then set U of m points are deleted by the unlearning algorithm using statistics T(S) and (ii) the model is trained on the set S S\ U and no points are deleted thereafter by the unlearning algorithm (using statisties T(S \ U)). For simplicity, throughout the paper, assume that e < 1.
While being similar, the above notion of unlearning is slightly different from the one considered in Ginart et al. [2019]. Specifically, their definition compares the output of the unlearning algorithm after deleting samples, to the output of the learning algorithm that only operates on S \ U. Due to this, they require the learning algorithm to randomized, even in the situation when there would be no delete requests in the future. Thus, the output of the learning algorithm will suffer degradation in its performance guarantees due to this added noise. On the other hand, our definition does not require the learning algorithm to be randomized since we only compare the output of the unlearning algorithms in the two scenarios- with and without the delete requests. Furthermore, our definition is more general than that of Ginart et al. [2019], by considering the unlearning algorithms for which simply adds noise to the output of A(S U) when U 0.
simulate their comparison in our definition
Our definition of unlearning leads to the following natural definition of the deletion capacity that formalizes how many samples can be deleted while still ensuring good test loss guarantees.
Definition 3 (Deletion capacity). Let e, 2 O. Let S be dataset of size drawn i..dd from 'D and let I (w, 2) be a loss function. For a pair of learning and unlearning algorithms A, A that are (e, 8) -nnlluunr,, the deletion capacity m.. A.A
(d,n) n.) is defined as the maximum number of samples U that can be unlearni, while still ensuring an excess population risk of 0.01. Specifically.
A.A m².5 (d, = max{m m
- -F < 0.001.
max LUSS:UUIS
where the expectation above is with respect to S ~ DD" and output of the algorithms A and A.
We are primarily interested in unlearning algorithms for which T(S) is small, and in particular does not grow with the dataset size (which can potentially be very large).
2.3 Unlearning via retraining from scratch
The most naive yet natural baseline for unlearning is to simply retrain the model from scratch using the remaining data. That is, we let A(S), T(S)) = A(S \. U). However, the straightforward method to implement this approach would require to set T(S) to contain the entire training dataset S. and thus [T(S) 2 n. However, recall that, we aim to provide unlearning algorithms for which T(S) is independent of n. Furthermore, retraining from scratch is computationally expensive merely reading all the data takes Ω(n m) time, not accounting for the cost of actually running the algorithm. These drawbacks lead one to explore more efficient methods for unlearning.
3 Our results
Prior works consider unlearning from an optimization perspective, focusing on minimizing the empirical risk, and do not discuss the implications of unleamnnn on test loss. As we show in the next section, the two could significantly different objectives even for some of the simplest learning problems.
5

---

3.1 Population risk vs empirical training risk
We first provide a simple example motivating our study of population risk over empirical risk, quantified rigorously in Theorem 1. Consider the following mean estimation problem. Let d = 1, Z R. and the loss function f(w, 2) (w - z)². The empirical risk of n points 21, 22...... 2n is minimized by the average Li=1 Zi- For this problem there is simple unlearning algorithm that minimizes empirical risk and also unlearns U exactly. We store the average of the points w11 >i= z/n, and upon receiving deletion request of set U of m samples, subtract those samples and renormalize to compute the minimizer of the empirical loss on the remaining training samples, i.e., we output
W2
8
Σ SEU
(4)
m
The above update rule requires T(S) to be of size (dd) and completely deletes the samples U satisfying the unlearning guarantee with ε = 8 = 0. The returned solution W2 is the exact minimizer of the empirical loss on left over data points.
However, W2 may perform well fresh samples drawn from the test distribution. Consider the same setting as above, but where the points z; are drawn i.i.d. from Bernoulli(1/2), Thus, the optimal parameter w" that minimizes the test loss is given by 1/2. However, consider the scenario where all of the m delete requests correspond to points with value 1. In this case, the minimizer of the updated empirical loss would be smaller by an additive factor of m/n than the previous estimate, and would thus have worse test loss.
In other words, in the unlearning framework, while minimizing training loss might be good algorithm, just providing guarantees on the training loss can be vacuous if we want the model to generalize unseen test samples. Furthermore, focusing the test loss inherently limits the deletion capacity as noted in example discussed above. We further formalize this intuition in Theorem I and show that even if the unlearning algorithm has access to all undeleted samples S \ U, there is non-trivial limit on the deletion capacity.
Theorem 1. Let 8 < 0.005 and E 1. There exists 4-Lipschitz 1-strongly convex function f and distribution D, such that for any learning algorithm A and unlearning algorithm A, which even has access to undeleted samples S 3 U, the deletion capacity
A.A [d, S cn, m
where с depends on the properties of function f and is strictly less than 1.
Prior work Schalev-Shwards et al., 2009a, Feldman, 2016] suggests that even the learning setting there are problems for which empirical risk minimizer solution fails to perform well on fresh samples, and regularization does not help [Kale al., 2021]. Our situation is worse, since the delete requests U can be ad adversarially chosen from S [Lai et al., 2016, Diakonikolas et al., 2019], In fact, the proof of Theorem relies on showing the existence of an adversary that can only delete points and can change the empirical loss considerably. We defer full details to Appendix B.
3.2 Strict separation between unlearning and differential privacy
Given the strong resemblance between differential privacy and our definition for unlearning, natural approach would be to use tools from differential privacy (DP) for machine unlearning. The simplest way ignore the particular of delete requests U and construct an unlearning algorithm A that only depends on the learning algorithm A(S). More formally, such an unlearning algorithm is of the form A(U, T(S) A(A(S)) and satisfies:
Pr(A(A(S) E W) S E PP((AAASS) U)) E W) 6
Pr(A(A(S \ U)) E W) < ()((A((())) E W) + 8.
Note that any such pair of algorithms would be differentially private with respect to the original dataset S, where the notion of neighboring datasets is for datasets with edit distance of m. The above guarantee is stronger than the distribution-fie unlearning guarantee Definition 2, and thus suffices to satisfy it. The key observation is that any DP algorithm A, which is private for datasets with edit distance m, automatically unlearns any m data samples. Thus, the standard performance guarantees for DP learning yields the following bound on deletion capacity:

---

Lemma (Unlearning via DP), There exists a polynomial time learning algorithm A and unlearning algorithm A of the form A(U, A(S), ((S) A() such that the deletion capacity
A.A m2, (d. (d.
52
ThE
(5)
/lloge=/6)
where the constant the Q-notation above depends on the properties of the loss function f.
The above result raises an immediate question of whether this particular dependence on d and n is necessary the deletion capacity, and it can be improved further. The following lemma shows that there exist problem instances for which any unlearning algorithm that ignores the samples U, can not improve over the factor of vd in the denominator of the deletion capacity bound in (5).
Lemma 2 (Bassily et al. [2019], Section C). For any learning algorithm A and unlearning algorithm that does not use U, i.c., A(U,A(S)) = A(A(S)), there exists a 1-strongly convex function and -L)-sLipth loss function f. and distribution D such that we can not unlearn even a single sample point, if
vd
where с depends on the properties of the function f.
Given that the vd dependence on dimension is unavoidable for algorithms that directly use DP, it is natural to wonder whether this factor may bypassed using other techniques. Our main contribution in this work positive answer in this direction. As we show in the next section, when the loss function is convex, there exist unlearning algorithms which can delete up to n/d sample points while still retaining the performance guarantee with respect to the test loss.
3.3 Unlearning for convex loss functions
In this section, provide an unlearning algorithm À for convex losses that delete points than unlearning algorithms that simply use DP.
Theorem 2. There exists learning algorithm A and an unlearming algorithm A such that for any convex (and hence strongly convex), L-Lipschitz, and M-Hessian -eessian-Lipschitz loss f and distribution D,
n/e
A.A A.A m (d,
(dlog(1/6)))/4
where the constant depends on the Lipschitz constants L and M. Furthermore, for the unlearning algorithm has running time (dd*) where E [2, 2.38) the exponent of matrix multiplication, and space complexity for T(S) = O
Theorem 2 and Lemma together show that there exist problem settings, where the deletion capacity in unlearning and DP is different by multiplicative ((dl/4). In particular, when learning with convex loss functions, we can delete Onn/dl/4) samples while still retaining good performance on the unseen test loss, whereas DP only guarantees deletion of @(n/ (+/2) samples. Hence, our algorithm least quadratically better in terms of dependence DP algorithms. Besides improving the dependence on d, our algorithm also enjoys better dependence on E and (1/8) in the deletion capacity, by at least quadratic factor.
in deletion capacity that standard
Our learning algorithm stores additional statistics of the dataset S in order to delete the set U in the unlearning algorithm. The extra memory need for these statistics is independent of n. Furthermore, our algorithm uses the samples in during the unlearning phase. This paradox of storing and using information in order to delete it, motivates the name of the paper: Remember what you want forget.
Characterizing the entire set of problems for which unlearning and differential privacy are different remains an interesting open question. Theorem 2 yields an improved upper bound, but it is not clear this dependence on n in the deletion capacity tight if it can improved even further. Resolving this question would be fascinating future research direction.
7

---

Unlearning algorithms
In the following, we provide learning and unlcarning algorithms when the loss function f(, is A-strongly convex. The unlearning algorithms for convex losses follows by appealing to the strongly convex case after adding regularization. We defer the algorithms and proofs for the convex case to Appendix D. Throughout this section, we make the following assumption:
Assumption 1. For any E 2, the function f(w, z) is X-strongly convex, L-Lipschitz and M- Hessian Lipschitz with respect to
Learning algorithm. We denote our learning algorithm by Asc- When given a dataset S of n points sampled i.i.d. from some distribution D, the algorithm Ase computes the point it by minimizing the empirical loss F, (w(w),
T - argmin Pa(w)= == Σ
s(w z).
(6)
T1 =ES
Asc then returns the point w and the statistics T(S) = 1 ( containing the Hessian of F(w) evaluated at the output point W. We provide the pseudocode for Ase in the appendix.
Unlearning algorithm. We denote our unlearning algorithm by A,C and provide the pseudocode in Algorithm 1. Ase receives as input the set of delete requests U, the point w and the data statistics T(S). Using these inputs, Age first estimates the matrix H that denotes the Hessian of the empirical function on the dataset \ U when evaluated the point w. Then, Age computes the point w by removing the contribution of the deleted points U from w using the update in (8). Finally, Asc perturbs w with noise v drawn from N o
22a)) and returns the perturbed point w.
Algorithm Unlearning algorithm (Asc)
Input: Delete requests: U { C output of Asr(S): S additional statistic T(S)
( (V [w))), loss function: f(w, 2Mm²ra 1: Set 7 x o = / (1.225/0))
2: Compute
(nV2F(0) - Σ v))(ūz)).
(7)
11 m
=EU
3: Define
1
( Σ
f u).
(8)
11 m
ZEU
4: &Sample E Rd from (0, r21.).
5: Return / == v + v.
Our main technical insight that leads to improvements in deletion capacity over differential privacy is the following observation. For loss functions that satisfy Assumption 1, when deleting m samples, we can approximate the empirical minimizer on the dataset S \ U up to precision of O(m² /n²) by the point w computed (8). This implies that we only need to add noise of the scale of a x O(m² /n²) to get the desired unlearning guarantee. This noise is smaller than the amount of noise typically added for DP learning [Dwork and Roth, 2014 4] by quadratic factor; hence giving us quadratic improvement in the deletion capacity.
Lemma 3. Suppose the loss function / satisfies Assumption 1. Let 5 ~ D be a set of n samples, and U S denote the set of m delete requests. Define the point w' as the empirical minimizer over S U, i.e. W E argmin,,, Eseryo (w, z)) m). Then,
2MI.m²²
where the point to is defined in (8) in Algorithm 1.

---

The following theorem provides performance guarantees for the algorithms Age and Age, and show that Ase and Age. are (e.6)-unlearning
Theorem 3. Suppose the loss function f satisfy Assumption and let the dataset S Dr, Then,
(a) The point t returned by running Ase on S satisfies
4L2
ES [F(w)
min wEW
F(w)] S
(9)
An
(b) For any set U S of delete requests, the point w returned by Age satisfies
F(w)] = =0 VdMm²L' L3 WEW
Vin(1/0)
4mL2
[F min
(10)
Xan2E
An
(c) The learning algorithu Agc and the unlearning algorithm Age are (e. 8)-umlearnin
Note that our guarantees in the above theorem are in terms of the test loss performance, while our algorithms compute minimizers of the training loss. We defer the proof to the Appendix C.2. This gives lower bound the number of samples m that can be deleted while still ensuring the desired excess risk guarantee (deletion capacity). Specifically, from the performance guarantee for Ase in (10), we observe that we can delete
c
(dlog(1/8))
samples from the set (with size n) while still ensuring that an excess risk guarantee of = 0.01. Here, e depends on the constants M, K and for the function f. This proves Theorem 2 for strongly convex loss functions.
Memory. We do need store the entire dataset S for the unlearning algorithm Ase. We note that the data statistic T(S) that is passed as an input to A.e given by T(S) = (V (()). Clearly, T(S) needs (dd)) memory and thus [T(S] is independent of n or m.
Computation. For the sake of exposition above, our learning algorithm Asc computes the exact minimizer for the empirical loss in (6). However, we show in Appendix C.2, our theoretical guarantees hold even when the empirical minimizer is computed approximately up to precision of O(1nn²). When the domain W is convex, such minimizer can be efficiently computed using stan- dard optimization algorithms like accelerated gradient descent, SGD, clipped-SGD. etc. For example, for the X-strongly convex case, Nesterov's 's accelerated GD algorithm can find ((1nn²) approximate minimizer time (ndd / /X) [Bubeck, 2014, Nemirovski and Yudin, 1983]. Furthermore, Ase takes O(nd²) time to compute TSS).
On the other hand, the running time for the unlearning algorithm Age scales as O(md² + d=), the time taken to compute the matrix A and invert it. Here, w E [2, 2.38). Note that our unlearning time is independent of the (potentially large) dataset size Furthermore, for problems such as linear SVMs where the Hessian is diagonal matrix, Ase takes time (md) and Age takes time O(d).
Comparison to retraining from scratch. Retaining from scratch requires access the entire training dataset S during unlearning, and thus not a feasible unlearning algorithm the resource constrained setting that consider in this work where the size of the data statistics T(S) should not scale with the size of S. However, ignoring the memory issues, there are regimes for the value of m for which retraining from scratch is computationally more efficient that implementing Algorithm 1, and the returned solution enjoys the same test loss performance guarantee. In particular, when max(m) d² m²-=w)= 2nn retraining from scratch by solving (6) using stochastic gradient descent is more efficient that computing the matrix Ā and its inverse in Algorithm 1. On the other hand, for large datasets (when >> d), we expect our algorithm to be computationally more efficient. We defer the exact characterization of memory computation tradeoffs machine unlearning for future work.

---

Algorithms for convex losses. Our unlearning algorithms when the loss function is convex are based on reductions the strongly convex setting discussed above. Give the convex loss function f(; 2), we define the function f(;,2) as
f(w,2) 2) fwu, 2) + |
The key observation that the function f(w, 2) is X-strongly convex, (L+ + >/ w/l ( Liipschi,,, (H X)- smooth and M- M-Hessian Lipschitz, and thus we can run algorithms Ase and Asc on f. We defer the algorithmic implementation and theoretical analysis for the convex loss setting to Appendix D.
5
Conclusion
We initiated a new study on machine unlearning with a focus on population risk minimization, in comparison to previous works that focus empirical risk minimization. For the case of convex loss functions, we provide a new unlearning algorithm that improves over the deletion capacity, by at least quadratic factor in d, than using out of the box differentially private algorithm for unlearning. Proving dimension dependent information theoretic lower bound on the deletion capacity is an interesting future research direction. Another exciting direction of future research is to provide efficient unlearning algorithms for finite / discrete hypothesis class, and for non-convex loss functions. Finally, in this work, considered the problem of batch deletion where the delete request U all arrive at the same time; Extending our algorithms for the online case is another interesting research direction that excited to pursue in future research.
Acknowledgements
We thank Robert Kleinberg, Mehryar Mohri, and Karthik Sridharan for helpful discussions. JA is supported in part by the grant NSF-CCF- 184630 (CAREER), NSF-CCF-18 1815933, and a Google Faculty Fellowship. GK is supported by an NSERC Discovery Grant and a University of Waterloo startup grant.
Funding Transparency Statement
Funding in direct support of this work: NSF-CCF-184600 (CAREER), NSF-CCF-1815888 Google Faculty Fellowship, an NSERC Discovery Grant, and University Waterloo startup grant.
References
General Data Protection Regulation. Regulation (EU) 2016/679 of the European parliament and of the council of 27 April 2016, 2016.
Reza Shokri, Marco Stronati, Congzheng Song. and Vitaly Shmatikov. Membership inference attacks against machine learning models. In Proceedings of the 38th IEEE Symposium on Security and Privacy, SP 17, pages 3-18, Washington, DC, USA, 2017. IEEE Computer Society.
Nicholas Carlini, Chang Liu, Úlfar Frlingsson, Jernej Kos, and Dawn Song. The secret sharer: Evaluating and testing unintended memorization in neural networks. 28th USENIX Security Symposium, USENIX Security '1,, pages 267-284. USENIX Association, 2019.
Federal Trade Commission. California company settles allegations deceived consumers about use of facial recognition in photo storage app, January 2021.
Antonio Ginart, Melody Guan, Gregory Valiant, and James Y Zou. Making Al forget you: Data deletion in machine learning. In Advances in Neural Information Processing Systems 32, NeurlPS '19, pages 3518-3531.
Curran Associates, Inc., 2019.
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Proceedings of the 3rd Conference on Theory of Cryptography, TCC '06, pages 265-284, Berlin, Heidelberg, 2006a. Springer.
Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, Ilya Mironov, and Moni Naor. Our data, ourselves: Privacy via distributed noise generation. In Proceedings of the 24th Annual International
10

---

Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT '06, pages 486-503, Berlin, Heidelberg, 2006b. Springer.
Chuan Guo, Tom Goldstein, Awni Hannun, and Laurens Van Der Maaten. Certified data removal from machine learning models. In Proceedings of the 37th International Conference on Machine Learning, ICML '20, pages 3832-3842. JMLR, Inc., 2020.
Zachary Izzo, Mary Anne Smart, Kamalika Chaudhuri, and James Zou. Approximate data deletion from machine learning models: Algorithms and evaluation. In Proceedings of the 24th International Conference on Artificial Intelligence and Statistics, AISTATS '21. JMLR, Inc., 2021.
Seth Neel, Aaron Roth, and Saeed Sharifi-Malvajjer Descent-to-deltte Gradient- methods for machine unlearning. Proceedings of the 32nd International Conference on Algorithmic Learning Theory, ALT '21. JMLR, Inc., 2021.
Enayat Ullah, Tung Mai, Anup Rao, Ryan Rossi, and Raman Arora. Machine unleariing via algorithmic stability. arXiv preprint arXiv:2102.13179, 2021.
Yinzhi Cao and Junfeng Yang. Towards making systems forget with machine unlearning. In Proceedings of the 36th IEEE Symposium on Security and Privacy, SP '15, pages 463-480, Washington, DC, USA, 2015. IEEE Computer Society.
Lucas Bourtoule, Varun Chandrasekaran, Christopher A Choquette-Chone Choo, Hengrui Jia, Adelin Travers, Baiwu Zhang, David Lie, and Nicolas Papernot. Machine unlearning. proceedings of the 42nd IEEE Symposium on Security and Privacy, SP 221, Washington, DC, USA, 2021. IEEE Computer Society.
Sanjam Garg, Shafi Goldwasser, and Prashant Nalini Vasudevan. Formalizing data deletion in the context of the right be forgotten. Proceedings of the 39th Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT '20, pages 373 Berlin, Heidelberg, 2020. Springer.
Min Chen, Zhikun Zhang, Tianhao Wang, Michael Backes, Mathias Humbert, and Yang Zhang.
When machine unlearning jeopardizes privacy. arXiv preprint arXiv:2005.0222 2020.
David Marco Sommer, Liwei Song, Sameer Wagh, and Prateck Mittal. Towards probabilistic verification of machine unlearning. arXiv preprint arXiv:2003.0422 2020.
Gert Cauwenberghs and Tomaso Poggio. Incremental and decremental support vector machine learning. Advances neural information processing systems, pages 409 415, 2001.
Amund Tveit, Magnus Lie Hetland, and Håavard Engum. Incremental and decremental proximal support vector classification using decay coefficients. In International Conference on Data Warehousing and Knowledge Discovery, pages 422-429, Springer, 2003.
Masayuki Karasuyama and Ichiro Takeuchi. Multiple incremental decremental learning of support vector machines. IEEE Transactions on Neural Networks, 21 104100088999 2010.
Enrique Romero, Ignacio Barrio, and Lluís Belanche. Incremental and decremental learning for linear support vector machines. In International Conference on Artificial Neural Networks, pages 209-218. Springer, 2007.
Min Du Zhi Chen, Chang Liu, Rajvardhan Oak, and Dawn Song. Lifelong anomaly detection through unlearning. In Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security, pages 1283-1297, 2019.
Aditya Golatkar, Alessandro Achille, and Stefano Soatto. Eternal sunshine of the spotless net: Selective forgetting in deep networks. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 9304 9912, 2020a.
Aditya Golatkar, Alessandro Achille, Avinash Ravichandran. Marzia Polito, and Stefano Soatto. Mixed-privacy forgetting in deep networks. arXiv preprint arXiv:2012.1343/ 2020b.
Quoc Phong Nguyen, Bryan Kian Hsiang Low, and Patrick Jaillet. Variational bayesian unlearning. Advances in Neural Information Processing Systems, 33, 2020.

---

Sébastien Bubeck. Convex optimization: Algorithms and complexity. arXiv preprint arXiv: arXiv: 1405,4980, 2014.
Shai Shalev- Shaaev-Shwartz, Ohad Shamir, Nathan Srebro, and Karthik Sridharan. optimization. In COLT, 2009a.
Stochastic convex
Vitaly Feldman. Generalization of erm in stochastic convex optimization: The dimension strikes back. arXiv preprint arXiv: 04008. 2016.
Satyen Kale, Ayush Sekhari. and Karthik Sridharan. Sgd: The role of implicit regularization, batch-size and multiple-epochs. arXiv preprint arXiv:2107.0507. 2021.
Kevin A Lai, Anup B Rao, and Santosh Vempala. Agnostic estimation of mean and covariance. In 2016 IEEE 57th Annual Symposium Foundations of Computer Science (FOCS), pages 665-674. IEEE, 2016.
Ilias Diakonikolas, Gautam Kamath, Daniel Kane, Jerry Li, Ankur Moitra, and Alistair Stewart. Robust estimators in high- -ineesinnsssons without the computational intractability. SIAM Journal on Computing, 48(2):742-8644 2019.
Raef Bassily, Vitaly Feldman, Kunal Talwar, and Abhradeep Guha Thakurta. Private stochastic convex optimization with optimal rates. In Advances Neural Information Processing Systems 32, NeurIPS 19, pages 11222-1122 129... Curran Associates, Inc., 2019.
Cynthia Dwork and Aaron Roth. The algorithmic foundations of differential privacy. Foundations and Trends@ in Theoretical Computer Science, 9(3-4):21 000:11--07,, 2014.
Arkadij Semenovič Nemirovski and David Borisovich Yudin. Problem complexity and method efficiency in optimization. 1983.
Shai Shalev-Shwartz and Shai Ben-David. Understanding machine learning: From theory to algorithms. Cambridge university press, 2014.
Salil Vadhan. The complexity of differential privacy. In Tutorials on the Foundations Cryptography. pages 347-450. Springer, 2017.
Shai Shalev-Shwarde Ohad Shamir, Nathan Srebro, and Karthik Sridharan. Stochastic convex optimization. In COLT, 2009b.
12


Reviews:
[{"review_id": "j9POb7JNYsi", "reviewer": "Reviewer_yPiR", "summary": "The paper considers the problem of machine unlearning: after a model is trained on a dataset, there is a request to delete a point from the dataset. The goal is to design an *efficient* method to update the trained model such that is nearly indistinguishable from what we would have obtained had we trained on the dataset without the point. The authors use differential privacy as the unlearning criteria and look at unlearning in convex learning problems. The give a method which can *unlearn more points* that DP-training with small runtime and storage complexity.", "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": "The paper contributes novel definitions and terminology to the budding unlearning literature. To give an example: the viewpoint of deletion capacity is interesting.\nThe paper is well-written, the proofs are natural and well-presented.\n\n**Confusion with the subtlety in the definition of unlearning**: The authors claim that their definition of $(\\epsilon, \\delta)$ unlearning is more general than previous work because it allows the learning algorithms to be deterministic. But I feel that this is an dubious claim from a practical viewpoint basically because any deterministic output is useless to begin with. The promise of unlearning is that the updated model is indistinguishable from what is obtained from training on the dataset with the deleted points. If the model in use is the deterministic one, then the company/service is not compliant  with the unlearning promise to begin with, and hence the deterministic output serves no purpose. The only situation where the deterministic output is thus useful is, when we know there are no unlearning requests to address  -- no reason to believe why we know this a-priori.\n\n**Separation between DP and unlearning**:\nA key contribution in the paper is a separation of DP and unlearning. It should be noted though that unlearning algorithms operate under more information than DP (they have knowledge of the deletion requests), therefore a smaller accuracy is reasonable to expect -- showing this formally is a good contribution. However, upon thinking about it a little more, it semms to me that it is possible to show much stronger results (see later half of \"population risk minimization and non i.i.d. points\" paragraph).\n\n**Population risk minimization and non i.i.d. points**:\nThis paper, in contrast to most previous work, considers excess population risk (rather than excess empirical risk) as the measure of performance. The authors motivate this via an example of mean estimation where it is straightforward to unlearn with best empirical risk performance. However, the authors show that there exists a sequence of deletions such that the corresponding population risk deteriorates. Interestingly, the deletion sequence is \"adversarial\", in the sense that the data points are no longer i.i.d., and thus (at a high-level) the empirical minimizer fails. My first impression upon reading this was that this is a challenging problem, since if we allow such \"adversarial\" updates, then we need to devise learning algorithms for datasets which are not i.i.d. anymore. But (if my understanding is correct) initial i.i.d. points and stability properties of ERM allows them to tackle it. My understanding is as follows: the initial dataset is i.i.d. and we have a model (empirical minimizer) $w_1$ which has small population risk. After deletions, we have to output $w_2$, the new empirical minimizer. It can be shown that $\\Vert w_1-w_2 \\Vert \\leq \\alpha$, so with the DP-like unlearning guarantee, we can add noise $\\propto \\alpha$, but this leads to worse accuracy. Instead, is there a point $w_3$, which is *closer* to $w_2$ but still has good population risk performance (guaranteed if it is close to $w_1$) -- the proposed unlearning algorithm gives such a point *efficiently*. \nThe two factors described above gives the two terms in the accuracy guarantee.\nNow, ignoring the computational cost of unlearning, I think that there are *even better* models, ones which optimize the aforementioned trade-off optimally. Consider a model $w_4$: let $a:=\\Vert w_1 - w_4\\Vert $ and $b:=\\Vert w_2 - w_4\\Vert $.  Let $c:=\\Vert w_1 - w_2\\Vert \\leq \\frac{m}{\\lambda n}$. If $w_1, w_2$ and $w_4$ are co-linear, then $a+b=c$. Adding noise of variance (roughly) $b^2/\\epsilon$ suffices for the unlearning guarantee. Plugging this in the proof of Lemma $9$, this gives an excess risk of $a + \\sqrt{d}b/\\epsilon + \\frac{1}{\\lambda n}$, the trade-off between the first two is optimized when $a = \\frac{\\sqrt{d}}{\\epsilon+\\sqrt{d}}c \\leq c$. This gives an excess risk of $\\frac{m}{\\lambda n}$.\nNote that this is as good (in terms of upper bounds) as using $w_2$ with no noise.\nIt is unclear if we can find this $w_4$ efficiently, but the above argument (if correct) is sufficient to establish a much stronger separation between unlearning and DP. Please correct if I made any mistake in the above reasoning.\n\n**Population risk vs ERM**: While the authors make a big deal about the fact that unlike prior work, they consider the population risk problem, in their problem (strongly convex learning), simply outputting (approximate) ERM gives smaller or (at worst) equal excess population risk than than authors'. Importantly, this is the method and proof technique used by the authors.\n\n**Some confusion on storage**:\nA key criteria in the paper is to also minimize storage complexity.\nThe authors want that storage complexity be independent of $n$, and moreover, the dataset is not stored/accessible. My confusion is, when getting a point $z$ to deleted, do we get (a). an id of the point or (b). full description of the point. If it is (a), then we indeed need to store the whole dataset, since we don't know the incoming requests. If it is (b), then the storage is indeed independent of $n$, but then what are we even \"remembering\" (which motivates the paper title). In general, the phrase \"remember what you want to forget\" is confusing to me -- why is it fine to assume we know what we want to forget a-priori?\n\n**Unlearning runtime**:\nThe authors say that their unlearning runtime is $O(d^\\omega)$, however, they should also consider the time it takes to compute the hessian and gradient on the deleted data points -- the sum of Hessians overl all data-points can be be pre-computed, but not the individual terms: this gives additional runtime of $\\Omega(md^2)$.\n\n**Comparison with retraining**:\nA natural baseline in unlearning papers is comparison with retraining.\nWith the constraints put on storage, the authors specifically removed retraining as a valid method.\nHowever, I find this limiting since in such a new and unexplored problem as unlearning, having multiple criteria of performance (unlearning runtime, storage..)  inhibits a deep understanding of any of the aspects. Furthermore, if we remove the only known (and trivial) method, then how to do we if the guarantees are indeed *interesting* (perhaps the trivial method retraining takes space but has much *smaller* runtime?). \nThus, due to personal curiosity, I tried to (roughly) calculate how it performs against retraining.\nDue to the population risk minimization criteria and non-i.i.d. points, I first thought that this does not apply.\nHowever, due to the stability properties of ERM (the approach via which this paper gave risk bounds), the ERM output after $m$ deletions can be shown to have excess risk $\\frac{m}{\\lambda n}$ -- the authors' upper bound is, at best, this term. Similarly, an $\\alpha$ approximate ERM can be shown to have excess population risk of $\\sqrt{\\frac{\\alpha}{\\lambda}} + \\frac{m}{\\lambda n}$.\nThe authors achieve excess population risk of $\\frac{\\sqrt{d}m^2}{\\lambda^3 n^2 \\epsilon}$ (disregarding other terms) with run-time $md^2 + d^\\omega$. To achieve the same error on $n-m = \\Omega(n)$ points, the total gradient complexity (using SGD) is $\\frac{\\lambda^4 n^4 \\epsilon^2}{d m^4}$. Hence, the prposed method is more efficient than retraining if (roughly) $\\max(md^2, d^{\\omega}) < \\frac{\\lambda^4 n^4 \\epsilon^2}{d m^4} \\iff \\epsilon > \\frac{m^2}{\\lambda^2n^2}  \\max \\left( \\sqrt{m}d^{3/2}, d^{(1+\\omega)/2}\\right)$. For reasonable unlearning guarantee, we want $\\epsilon$ to be a small constant, say $1$. This would give (reasonable?) upper bounds on $m$ and/or $d$ in terms of number of data points $n$ and $\\lambda$. \nAgain, I think such an exercise as above is required to assess if the guarantees are indeed non-trivial.\n\n**Incorrect description of previous work:** The authors mention \"Ullah et al. 2021, Machine Unlearning via Algorithmic Stability\" in context of methods which use an approximate unlearning criteria (i.e. differential privacy). However, this is incorrect: Ullah et al. 2021 give methods which guarantee **exact** unlearning.\n", "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": {}}, {"review_id": "d3ebKrLq9N0", "reviewer": "Reviewer_FKp5", "summary": "The paper proposes a new unlearning algorithm that is provably memory and sample efficient in some cases. The paper provides sample complexity upper and lower bounds for test error given access to second order information of loss function.\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": "Strength: - Nicely written, with detailed related work section. Theorems and definitions are well motivated and each of them is intuitively explained for readers not so familiar with the problem of machine unlearning and the general area. The paper adopts standard Mathematical notations which is nice, and they are consistently followed throughout the paper as well. \n- Application of ideas from DP for unlearning is intuitive and interesting. The main idea is that if the future delete requests are manageable, then a deterministic procedure like the one proposed maybe sufficient under some technical conditions on the loss function of the learning algorithm. The separation result in terms of sample complexity between DP and unlearning is technically interesting.\n\nWeakness:- For a paper that presents a machine (un)learning _algorithm_ as its main contribution, it does not contain any experiments, not even simulation. It seems like the algorithm could be implemented for reasonable size datasets since it only requires hessian-vector product -- this package comes to mind https://github.com/amirgholami/pyhessian \n- Again, for a theory paper like this, I consider it a lost opportunity to give no intuition at all about the proofs. I believe readers would be able to appreciate the paper even more if some proof sketches are provided. The examples are nice but they are almost trivial, and they don't necessarily convey the challenge . The proofs contain some minor typos and quantities (D^*) undefined. The proofs appear to be technically correct and utilize tools from convex optimization and results from differential privacy literature. \n\nJustification: The paper seems to have some interesting ideas that are not fully formed i.e., pieces of the paper sometimes felt disjoint without one full coherent story. For example, the introduction section is only slightly related to the rest of the paper -- discussion about regulations is totally forgotten. A similar statement could be made for the related work section, wherein it seems none of the ideas are used in this paper. Incorporating some elements of the proofs in the main paper might make it more readable from the technical perspective.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Have addressed appropriately.", "review_text": "", "extra_scores": {"ethical_concerns": "NA", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "Pv8cTUbmepa", "reviewer": "Reviewer_AJse", "summary": "Machine unlearning is new and hot topic. This paper makes several interesting contributions. The idea that the unlearning operation can only access a summary of the entire dataset is a great conceptual innovation since many deployment environments are memory-constrained compared to the training environment. The main contributions of this paper lean theoretical. I did not closely check all the details in the math, but it seems correct at a high-level. I consider the theoretical contributions interesting and strong.", "questions": "", "limitations": "", "rating": 7, "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": "Contributions:\n - Study trade-off between generalization loss and unlearning with memory constraints\n - Propose an unlearning technique and show it results in asymptotic improvements over DP-based unlearning methods\n\nOverall, I am enthusiastic about this paper. I am tentatively voting a 7.\n\nSuggestions/Concerns:\n\n- One of the key, interesting findings of this paper is the strict separation between DP and removal in the setting of choice. I suggest the authors add more intuition and description so that the readers can easily digest this finding. \n\n- The deletion notion in Ginart 2019 does not require randomness, contrary to the claims in this paper. In that work, the learning algorithm could just deterministically output the database in the clear and the unlearning operation need just remove the target row from the database. Even simpler, all learning algorithms could just deterministically output \"0\" and the unlearning operation doesn't need to do anything. The only differences I can see with respect to the definition in Ginart 2019 are that: (1) this definition explicitly supports batch deletions, (2) this definition is two-sided, meaning that unlearned models must be indistinguishable from models trained on the subset  & (3) this definition limits access to the dataset via the summary structure T.\n\n- Consider letting the magic constant (0.01) be an arbitrary gamma. For some applications 0.01 is too small and for others it might be too large. This is a stylistic recommendation and does not need to be addressed in rebuttal.\n\n- While this paper clearly leans towards the theoretical, it would be good to include simple experiments to illustrate the points made in the paper. For example, a simple linear or logistic regression setting should satisfy the theoretical criteria and is not a hard implementation. It is nice to actually compute and tell the reader what the actual improvement in deletion capacity ends up being, especially if non-vacuous metrics can be achieved in practice.\n\n- At the end of Section 4, the subsection titled \"Algorithms for convex loss functions\" is elementary and should be moved to the appendix. It is standard knowledge that adding regularization to the loss function yields strong convexity and this does not need an entire subsection to explain (it can be stated in 1 or 2 sentences as above, if mentioned at all).\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes, they address social impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "Ilm7GoMKJG", "reviewer": "Reviewer_vRcu", "summary": "This paper studies the problem of unlearning: given a model M trained on a set of examples S, and a subset T of S, the goal is to generate a model M’ that does not rely on any of the samples in T. The authors in particular aim to minimize the test error (rather than the training errors is done in previous approaches), while keeping speed and space constraints low. Their main contributions are a comparison with differential privacy (DP) algorithms, and showing theoretically that unlearning and DP are two separate problems, as well as presenting an unlearning algorithm which can unlearn asymptotically more examples the DP.\nI will say upfront that I am not an expert on this topic, but to the best of my judgement the paper seems interesting and solid.\n", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "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": "The paper provides a thorough background and is generally clear. The contributions seem novel, though I am not intimately familiar with the topic.\n\nQuestions:\n1. The authors attribute some of the limitations of previous approaches to their usage of randomness (#176), and later say explicitly that “(their) definition does not require the learning algorithm to be randomized”. However, as stated in #301 and Algorithm 1, their model in fact does add noise to w. \n2. The authors discuss one of the benefits of their approach in not needing to save the entire training set. However, a reasonable assumption is that you don’t know in advance which samples are going to be deleted, so it seems like one would need to save the entire training set anyhow, plus a mapping from each author to their samples, which makes this constraint not a particularly useful one.\n\nMinor: \n#189: grown -> grow\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The paper tries to make models adhere to privacy requirements such as deletion of personal data, which makes it seem like it could have a positive societal impact.\n", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper considers the problem of machine unlearning: after a model is trained on a dataset, there is a request to delete a point from the dataset. The goal is to design an efficient method to update the trained model s.t. is nearly indistinguishable from what we would have obtained had we trained on the dataset without the point. One baseline from prior work is to use DP. The authors give a method that can efficiently unlearn more points that DP-training in the context of in convex learning problems. The reviewers agree that this is an interesting paper with solid contribution, and all of them support acceptance.
Decision: Accept (Poster)