Remember What You Want to Forget: Algorithms for Machine Unlearning
Year: 2021

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 b w that performs well on unseen samples from the same distribution. However, at some point in the future, any training datapoint z 2 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/d1/4) samples, where d is the problem dimension. In comparison, in general, differentially private learning (which implies unlearning) only guarantees deletion of O(n/d1/2) samples. This demonstrates a novel separation between differential privacy and machine unlearning.

heading: 1 Introduction
text: Many organizations and companies employ user data to train machine learning models for a wide array of applications, ranging from movie recommendations to health care. While some of these 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 user 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 proposed Consumer Privacy Protection Act (CPPA).
There is some natural ambiguity present in these guidelines. Is it sufficient to simply delete the user’s data, or must one also take action on 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 et al. [2017], Carlini et al. [2019]). In a potentially landmark decision, the Federal Trade Commission recently ordered a 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 alphabetical order.
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
However, naïvely 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 unlearning. 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 naïve 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, it is computationally very expensive. Even iteration over the training data can be too costly, let alone training a new model on it. Second, preserving the entire training dataset consumes a significant amount of storage.2
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 a 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 to 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-efficient 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 unlearn 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 a strict separation between DP and machine unlearning. In particular, algorithms based on DP can delete at most e⇥(n/ p d) 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 eO(n/d1/4) samples, thus giving a quadratic improvement in terms of dependence of d over DP. Our results apply to both strongly convex and convex loss functions.

heading: 1.1 Related work
text: 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 a dataset after deleting a point, and if that point was never inserted. However, their
2Orthogonal to storage constraints, an additional issue is that government regulations may restrict the learner from storing raw user data for extended periods of time due to privacy concerns. However, we focus on storage as it captures undesirability of a wider range of unsatisfactory solutions.
algorithms are restricted to very structured problems only. Bourtoule et al. [2021] provide unlearning algorithms using a sharding-based strategy, though in a weaker unlearning model (requiring only that it be possible that the output may have arisen), and without error guarantees.
Ginart et al. [2019] introduced the probabilistic notion of unlearning, inspired by differential privacy [Dwork et al., 2006b,a]. Their definition requires the output 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 et 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 on the computational cost of unlearning, without concern for associated storage requirements. This has led to approaches which involve memory-intensive 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 is 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 [Cauwenberghs and Poggio, 2001, Tveit et al., 2003, Karasuyama and Takeuchi, 2010, Romero et 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 et al., 2020a,b, Nguyen et al., 2020].

heading: 2 Preliminaries
text: Let D be a distribution over an instance space Z and W ✓ Rd be the parameter space of a hypothesis class. Let f : W ⇥ Z ! R be a loss function. The goal is to minimize the test loss population risk (test loss), given by
F (w) := Ez⇠D[f(w, z)], (1)
where f(w, z) is the loss of the hypothesis corresponding to w 2 W on the instance z 2 Z . Let F ⇤ = minw2W 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 a small test loss model.
Given S = (z1, z2, . . . , zn), a set of n samples drawn independently from D, standard learning algorithms minimize the empirical loss given by
bFn(w) := 1
n
nX
i=1
f(w, zi). (2)

heading: 2.1 Learning
text: Let A : Zn !W be a learning algorithm that takes the dataset S and returns a hypothesis A(S) 2W . 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))] F ⇤, where the expectation is over the randomness in A and S. This gives a natural notion of sample complexity. Definition 1 (Sample complexity of learning). The -sample complexity of a problem is defined as
n := min{n | 9A s.t. ES⇠Dn [F (A(S))] F ⇤  for all D}, the fewest number of samples with which a -suboptimal 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 = 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,
n0.01 = O(1), (3)
where the hidden constant depends on the properties of f such as its Lipschitzness, but is independent of the dimension d of the parameter space W ✓ Rd.

heading: 2.2 Unlearning
text: Suppose a learning algorithm A over S outputs the model A(S). An unlearning algorithm Ā takes as input the model A(S) and a set U ⇢ S of data samples that are to be deleted, and is required to output a new model ew 2W . Besides the set U and the model A(S), the unlearning algorithm Ā can also access some additional data statistics T (S) 2 T . We emphasize that the unlearning algorithm does not have access to 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 unlearning. Thus, one of our goals is to minimize |T (S)|, in particular aiming for memory requirements which are independent of the training data size n. This precludes strategies which involve storing and reusing the entire training set, or aggressive model checkpointing. On the other hand, it permits storage of simple statistics such as 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 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), an unlearning algorithm is a mapping Ā : Zm ⇥W ⇥ T !W . To illustrate our unlearning setup, consider the following toy example: Suppose we train a model bw with four datapoints S = {[0.0, 0.1], [2.0, 2.3], [4.0, 0.5], [3.0, 1.3]}. After training the model, the learner only keeps bw 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 to 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 bw, 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 a notion of unlearning, which is motivated by the definition of differential privacy [Dwork et al., 2006a].
Definition 2 ((", )-unlearning). For all S of size n and delete requests U ✓ S such that |U |  m, and W ✓W , a learning algorithm A and an unlearning algorithm Ā is (", )-unlearning if
Pr Ā(U,A(S), T (S)) 2W  e" · Pr Ā(;, A(S \ U), T (S \ U)) 2W + ,
and
Pr Ā(;, A(S \ U), T (S \ U)) 2W  e" · Pr Ā(U,A(S), T (S)) 2W + ,
where ; denotes the empty set and T (S) 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 a 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 \U and no points are deleted thereafter by the unlearning algorithm (using statistics T (S \ U)). For simplicity, throughout the paper, we assume that "  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 m samples, to the output of the learning algorithm that only operates on S \ U . Due to this, they require the learning algorithm to be randomized, even in the situation when there would be no delete requests in the future. Thus, the output of the learning algorithm will suffer a 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], as we can simulate their comparison in our definition by considering the unlearning algorithms for which Ā simply adds noise to the output of A(S \ U) when U = ;. 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 ", 0. Let S be a dataset of size n drawn i.i.d. from D, and let f(w, z) be a loss function. For a pair of learning and unlearning algorithms A, Ā that are (", )-unlearning, the deletion capacity mA,Ā", (d, n) is defined as the maximum number of samples U that can be unlearnt, while still ensuring an excess population risk of 0.01. Specifically,
mA,Ā", (d, n) := max n m | E h max
U✓S:|U |m F (Ā(U,A(S), T (S))) F ⇤
i  0.01 o ,
where the expectation above is with respect to S ⇠ Dn 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 n (which can potentially be very large).

heading: 2.3 Unlearning via retraining from scratch
text: The most naïve yet natural baseline for unlearning is to simply retrain the model from scratch using the remaining data. That is, we let Ā(U,A(S), T (S)) = A(S \ U). However, the straightforward method to implement this approach would require us to set T (S) to contain the entire training dataset S, and thus |T (S)| 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.

heading: 3 Our results
text: Prior works consider unlearning from an optimization perspective, focusing on minimizing the empirical risk, and do not discuss the implications of unlearning on test loss. As we show in the next section, the two could significantly different objectives even for some of the simplest learning problems.

heading: 3.1 Population risk vs empirical training risk
text: 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, z) = (w z)2. The empirical risk of n points z1, z2, . . . , zn is minimized by the average 1n Pn i=1 zi. For this problem there is a simple unlearning algorithm that minimizes empirical risk and also unlearns U exactly. We store the average of the points w1 = Pn i=1 zi/n, and upon receiving a deletion request of a 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 = n
n m
⇣ w1 1
n
X z2U z ⌘ . (4)
The above update rule requires T (S) to be of size O(d) and completely deletes the samples U satisfying the unlearning guarantee with " = = 0. The returned solution w2 is the exact minimizer of the empirical loss on left over data points.
However, w2 may not perform well on fresh samples drawn from the test distribution. Consider the same setting as above, but where the points zi 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 a good algorithm, just providing guarantees on the training loss can be vacuous if we want the model to generalize to unseen test samples. Furthermore, focusing on the test loss inherently limits the deletion capacity as noted in example discussed above. We further formalize this intuition in Theorem 1 and show that even if the unlearning algorithm has access to all undeleted samples S \ U , there is a non-trivial limit on the deletion capacity. Theorem 1. Let  0.005 and " = 1. There exists a 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 \ U , the deletion capacity
mA,Ā", (d, n)  cn, where c depends on the properties of function f and is strictly less than 1.
Prior work [Shalev-Shwartz et al., 2009a, Feldman, 2016] suggests that even in 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 et al., 2021]. Our situation is worse, since the delete requests U can be adversarially chosen from S [Lai et al., 2016, Diakonikolas et al., 2019]. In fact, the proof of Theorem 1 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.1.

heading: 3.2 Strict separation between unlearning and differential privacy
text: Given the strong resemblance between differential privacy and our definition for unlearning, a natural approach would be to use tools from differential privacy (DP) for machine unlearning. The simplest way is to ignore the particular set 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,A(S), T (S)) = Ā(A(S)) and satisfies:
Pr Ā(A(S)) 2W  e"Pr Ā(A(S \ U)) 2W + ,
Pr Ā(A(S \ U)) 2W  e"Pr Ā(A(S)) 2W + .
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-free unlearning guarantee in Definition 2, and thus it 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 1 (Unlearning via DP). There exists a polynomial time learning algorithm A and unlearning algorithm Ā of the form Ā(U,A(S), T (S)) = A(S) such that the deletion capacity
mA,Ā", (d, n) e⌦ ⇣ n"p
d log(e"/ )
⌘ , (5)
where the constant in the ⌦-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 on the deletion capacity, and if 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 p d in the denominator of the deletion capacity bound in (5).
Lemma 2 (Bassily et al. [2019], Section C). For any learning algorithm A and an unlearning algorithm Ā that does not use U , i.e., Ā(U,A(S)) = Ā(A(S)), there exists a 1-strongly convex function and O(1)-Lipschitz loss function f , and a distribution D such that we can not unlearn even a single sample point, if
n  c · p d
" ,
where c depends on the properties of the function f .
Given that the p d dependence on dimension is unavoidable for algorithms that directly use DP, it is natural to wonder whether this factor may be bypassed using other techniques. Our main contribution in this work a 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/d1/4 sample points while still retaining the performance guarantee with respect to the test loss.

heading: 3.3 Unlearning for convex loss functions
text: In this section, we provide an unlearning algorithm Ā for convex losses that can delete more points than unlearning algorithms that simply use DP.
Theorem 2. There exists a learning algorithm A and an unlearning algorithm Ā such that for any convex (and hence strongly convex), L-Lipschitz, and M-Hessian-Lipschitz loss f and distribution D,
mA,Ā", (d, n) c · n p "
(d log(1/ ))1/4 ,
where the constant c depends on the Lipschitz constants L and M . Furthermore, for the unlearning algorithm Ā has running time O(d!) where ! 2 [2, 2.38] is the exponent of matrix multiplication, and space complexity for T (S) = O(d2).
Theorem 2 and Lemma 2 together show that there exist problem settings, where the deletion capacity in unlearning and DP is different by a multiplicative ⇥(d1/4). In particular, when learning with convex loss functions, we can delete O(n/d1/4) samples while still retaining good performance on the unseen test loss, whereas DP only guarantees deletion of ⇥(n/d1/2) samples. Hence, our algorithm is at least quadratically better in terms of dependence on d in deletion capacity that standard DP algorithms. Besides improving the dependence on d, our algorithm also enjoys better dependence on " and log(1/ ) in the deletion capacity, by at least a quadratic factor.
Our learning algorithm stores additional statistics of the dataset S in order to delete the set U in the unlearning algorithm. The extra memory we need for these statistics is independent of n. Furthermore, our algorithm uses the samples in U 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 to 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 if this dependence on d or n in the deletion capacity is tight or if it can be improved even further. Resolving this question would be a fascinating future research direction.

heading: 4 Unlearning algorithms
text: In the following, we provide learning and unlearning algorithms when the loss function f(·, z) is -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 z 2 Z , the function f(w, z) is -strongly convex, L-Lipschitz and M - Hessian Lipschitz with respect to w.
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 Asc computes the point bw by minimizing the empirical loss bFn(w), i.e.
bw argmin bFn(w) := 1
n
X z2S f(w, z). (6)
Asc then returns the point bw and the statistics T (S) := {r2 bF ( bw)} containing the Hessian of bF (w) evaluated at the output point bw. We provide the pseudocode for Asc in the appendix.
Unlearning algorithm. We denote our unlearning algorithm by Āsc and provide the pseudocode in Algorithm 1. Āsc receives as input the set of delete requests U , the point bw and the data statistics T (S). Using these inputs, Āsc first estimates the matrix bH that denotes the Hessian of the empirical function on the dataset S \ U when evaluated at the point bw. Then, Āsc computes the point w̄ by removing the contribution of the deleted points U from bw using the update in (8). Finally, Āsc perturbs w̄ with noise ⌫ drawn from N (0, 2Id) and returns the perturbed point ew.
Algorithm 1 Unlearning algorithm (Āsc) Input: Delete requests: U = {zj}mj=1 ✓ S, output of Asc(S): bw, additional statistic T (S) :
{r2 bF ( bw)}, loss function: f(w, z). 1: Set = 2Mm 2L2
3n2 , = "
p 2 ln(1.25/ ).
2: Compute
bH = 1 n m nr2 bF ( bw)
X z2U r2f( bw, z) . (7)
3: Define
w̄ = bw + 1 n m (
bH) 1 X
z2U rf( bw, u). (8)
4: Sample ⌫ 2 Rd from N (0, 2Id). 5: Return ew := w̄ + ⌫.
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 a precision of O(m2/n2) by the point w̄ computed in (8). This implies that we only need to add noise of the scale of / O(m2/n2) to get the desired unlearning guarantee. This noise is smaller than the amount of noise typically added for DP learning [Dwork and Roth, 2014] by a quadratic factor; hence giving us a quadratic improvement in the deletion capacity. Lemma 3. Suppose the loss function f satisfies Assumption 1. Let S ⇠ Dn be a set of n samples, and U ✓ S denote the set of m delete requests. Define the point bw0 as the empirical minimizer over S \ U , i.e. bw0 2 argminw P z2S\U f(w, z)/(n m). Then,
k bw0 w̄k  2ML 2m2
3n2 ,
where the point w̄ is defined in (8) in Algorithm 1.
The following theorem provides performance guarantees for the algorithms Asc and Āsc, and show that Asc and Āsc are (", )-unlearning. Theorem 3. Suppose the loss function f satisfy Assumption 1 and let the dataset S ⇠ Dn. Then,
(a) The point bw returned by running Asc on S satisfies
ES⇠Dn [F ( bw) min w2W
F (w)]  4L 2
n . (9)
(b) For any set U ✓ S of m delete requests, the point ew returned by Āsc satisfies
ES,⌫ [F ( ew) min w2W
F (w)] = O ⇣pdMm2L3
3n2"
q ln 1/ + 4mL2
n
⌘ . (10)
(c) The learning algorithm Asc and the unlearning algorithm Āsc are (", )-unlearning.
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 a lower bound on 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 Āsc in (10), we observe that we can delete
m c · n p "
(d log(1/ ))1/4 ,
samples from the set S (with size n) while still ensuring that an excess risk guarantee of = 0.01. Here, c depends on the constants M,K and for the function f . This proves Theorem 2 for strongly convex loss functions.
Memory. We do not need to store the entire dataset S for the unlearning algorithm Āsc. We note that the data statistic T (S) that is passed as an input to Āsc is given by T (S) = {r2 bF ( bw)}. Clearly, T (S) needs O(d2) 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, as we show in Appendix C.2, our theoretical guarantees hold even when the empirical minimizer is computed approximately up to a precision of O(1/n2). When the domain W is convex, such a minimizer can be efficiently computed using standard optimization algorithms like accelerated gradient descent, SGD, clipped-SGD, etc. For example, for the -strongly convex case, Nesterov’s accelerated GD algorithm can find a O(1/n2) approximate minimizer in time eO(nd/ p ) [Bubeck, 2014, Nemirovski and Yudin, 1983]. Furthermore, Asc takes O(nd2) time to compute T (S).
On the other hand, the running time for the unlearning algorithm Āsc scales as O(md2 + d!), the time taken to compute the matrix bH and to invert it. Here, ! 2 [2, 2.38]. Note that our unlearning time is independent of the (potentially large) dataset size n. Furthermore, for problems such as linear SVMs where the Hessian is a diagonal matrix, Asc takes time O(nd) and Āsc takes time O(d).
Comparison to retraining from scratch. Retaining from scratch requires access to the entire training dataset S during unlearning, and is thus not a feasible unlearning algorithm in the resource constrained setting that we 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(m5d2,m4+!) > 4n2", retraining from scratch by solving (6) using stochastic gradient descent is more efficient that computing the matrix bH and its inverse in Algorithm 1. On the other hand, for large datasets (when n d), we expect our algorithm to be computationally more efficient. We defer the exact characterization of memory / computation tradeoffs in machine unlearning for future work.
Algorithms for convex losses. Our unlearning algorithms when the loss function is convex are based on reductions to the strongly convex setting discussed above. Give the convex loss function f(·, z), we define the function ef(·, z) as
ef(w, z) = f(w, z) + 2 kwk2.
The key observation is that the function ef(w, z) is -strongly convex, (L+ kwk)-Lipschitz, (H+ )- smooth and M -Hessian Lipschitz, and thus we can run algorithms Asc and Āsc on ef . We defer the algorithmic implementation and theoretical analysis for the convex loss setting to Appendix D.

heading: 5 Conclusion
text: We initiated a new study on machine unlearning with a focus on population risk minimization, in comparison to previous works that focus on 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 a quadratic factor in d, than using an out of the box differentially private algorithm for unlearning. Proving a 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, we 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 we are excited to pursue in future research.

heading: Acknowledgements
text: We thank Robert Kleinberg, Mehryar Mohri, and Karthik Sridharan for helpful discussions. JA is supported in part by the grant NSF-CCF-1846300 (CAREER), NSF-CCF-1815893, 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-1846300 (CAREER), NSF-CCF-1815893, a Google Faculty Fellowship, an NSERC Discovery Grant, and a University of Waterloo startup grant.

Review summaries:
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.

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.

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. I 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.