Algorithms that Approximate Data Removal: New Results and Limitations
Authors: Vinith Menon Suriyakumar
Ashia Camage Wilson
Venue: NeurIPS 2022 Accept (2022)
Keywords: Online Algorithms
Data Deletion

Abstract: We study the problem of deleting user data from machine learning models trained using empirical risk minimization (ERM). Our focus is on learning algorithms which return the empirical risk minimizer and approximate unlearning algorithms that comply with deletion requests that come in an online manner. Leveraging the infintesimal jacknife, we develop an online unlearning algorithm that is both computationally and memory efficient. Unlike prior memory efficient unlearning algorithms, we target ERM trained models that minimize objectives with non-smooth regularizers, such as the commonly used $\ell_1$, elastic net, or nuclear norm penalties. We also provide generalization, deletion capacity, and unlearning guarantees that are consistent with state of the art methods. Across a variety of benchmark datasets, our algorithm empirically improves upon the runtime of prior methods while maintaining the same memory requirements and test accuracy. Finally, we open a new direction of inquiry by proving that all approximate unlearning algorithms introduced so far fail to unlearn in problem settings where common hyperparameter tuning methods, such as cross-validation, have been used to select models.

Algorithms that Approximate Data Removal: New Results and Limitations
Vinith M. Suriyakumar
Ashia C. Wilson MIT EECS ashia070mi edu
MIT EECS
vinithms@mit. edu
Abstract
We study the problem of deleting user data from machine learning models trained using empirical risk minimization (ERM). Our focus is on learning algorithms which return the empirical risk minimizer and approximate unlearning algorithms that comply with deletion requests that come in an online manner. Leveraging the infintesimal jacknife, we develop an online unlearning algorithm that is both computationally and memory efficient. Unlike prior memory efficient unlearning al- gorithms, we target ERM trained models that minimize objectives with non- -mothh regularizers, such as the commonly used f1, elastic net, or nuclear norm penalties. We also provide generalization, deletion capacity, and unlearning guarantees that are consistent with state of the art methods. Across variety of benchmark datasets, our algorithm empirically improves upon the runtime of prior methods while main- taining the same memory requirements and test accuracy. Finally, open new direction of inquiry by proving that all approximate unlearning algorithms intro- duced far fail to unlearn in problem settings where common hyperparameter tuning methods, such as cross-validation, have been used to select models.
Introduction
The right to be forgotten (RtbF) is considered fundamental human right in many legal systems [27, 21, 5]. The proliferation of techniques that employ user data to do things such as training and validating machine learning across variety of organizations has led reconsideration of how to interpret RtbF. The European Union's 's General Data Protection Regulation (GDPR), California's Consumer Privacy Act (CCPA), and Canada's proposed Consumer Privacy Protection Act (CPPA) are all examples of new pieces of legislation which attempt to codify the RtbF by requiring companies and organizations to delete user's data by request [34].
But what does it mean to delete a user's data? User data, for example, can be recovered from trained machine learning models [31] and hyperparameter tuning procedures [25]. This suggests that data deletion should require organizations to take action on the models and algorithms derived from the data well. This interpretation is consistent with the Federal Trade Commission's recent action ordering companies to delete the data from users who deleted their account as well as the models and algorithms derived from the users' data [7]. Forcing organizations comply with each deletion request by retraining, however, comes with potentially significant monetary and time costs. Thus, it worth asking if these costs can be managed while still maintaining model performance.
The cost concerns associated with RtbF compliance have prompted several recent works which formalize and study the problem of unlearning [6]. The aim of these works is to develop techniques which delete user data from models that are inexpensive in both computation and memory while maintaining reasonable performance. Most unlearning algorithms proposed far focus unlearning models obtained via empirical risk minimization [14, 28, 4, 23, 20). However, several of these methods are memory intensive [4, 15], requiring organizations store several states of the model
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

while training. We build on recent works [14, 28] which show that for models derived from minimizing convex and sufficiently smooth ERM objectives, a Newton update the current model can be applied in order to approximately unlearn in certain data directions. We show a different Newton estimate based on the classical infinitesimal jacknife developed in the robust statistics literature [17, 10] results in more computationally efficient unlearning algorithm in the online setting. While the current legislation only requires companies to satisfy delete requests in 30 days there are scenarios where immediate (online) delete requests are necessary such as the UK Biobank [12]. We also show how to utilize the proximal infinitesimal jackknife [35] to unlearn settings when the model was trained using ERM objective that is not smooth. Finally, we present an important and concerning failure mode of all approximate unlearning algorithms.
Our principal contributions are three-fold.
Computationally efficient online algorithm. We develop an online unlearning algorithm to unlearn a sequence of m datapoints from a model 0,, (A) that approximately minimizes a smooth and convex ERM objective that requires Odd)) storage and has running time (mmd). To unlearn m datapoints an online manner, the algorithms developed in prior works (e.g. [14, 28)) requires similar storage, but have a longer Omdd)) running time. By avoiding the cost of computing and inverting a different Hessian at each deletion request we improve on the computational requirements of previous memory efficient unlearning algorithms, while maintaining the same generalization, unlearning and deletion capacity guarantees. We empirically demonstrate significant computational savings without sacrificing test set accuracy on multiple datasets.
Accommodating non-smooth regularizers. We provide a generalization of our unlearning algo- rithm based on the proximal Newton method that can be used to efficiently delete data from models that minimize objective functions with non-smooth penalties. We provide state-of-the art unlearning, deletion capacity and generalization guarantees for our new unlearning method. We empirically demonstrate significant computational savings without sacrificing test set accuracy in predicting Warfarin dosages.
Failure modes. Most data processing pipelines are not as simple as writing down an objective function and running an algorithm out-of-the-box which returns the approximate empirical risk minimizer. A more common practice is to tune hyperparameters using techniques such as cross- validation. We reveal a fundamental limitation of all (approximate) data removal processes developed so far when hyperparameter tuning takes place.
2
Related Work
Given the increasing concerns around privacy of user data, recent research on machine unlearning studies how we can efficiently delete datapoints used to train models without retraining from scratch. This work was first initiated by Cao and Yang [6] whose definition requires the outputs of an unlearning algorithm to be identical to the outputs of the model produced by retraining. Since then, several works have provided different definitions of machine unlearning which can be separated as exact unlearning ([4, 32, 15, 11]) or approximate unlearning ([14, 28, 12, 231).
Our work is focused on satisfying approximate unlearning definitions inspired by differential pri- vacy [9] defined by [14] as (c, --eertifeeedd removal or by [28] as -unle--unl.m,nng. This definition requires the output distribution of the unlearning algorithm to be similar to that obtained by retraining from scratch using the original training set with the requested datapoints removed from it. We focus on this definition because algorithms for exact unlearning such as statistical query learning [6], SISA [4], and its adaptive variant [15] have high computational and memory cost.
Prior algorithms developed for approximate unlearning use a variety of techniques: perturbed gradient descent [23, 33], Newton style updates [14, 28], and projected residual updates [16]. The perturbed gradient descent and projected residual update methods provide theoretical error guarantees for the empirical training loss but fail to provide any generalization guarantees. In addition, while these methods reduce the computation burden associated with exact unlearning, their high memory costs still similar to exact unlearning methods.
Given these issues, Newton update unlearning algorithms were proposed to efficiently satisfy approx- imate unlearning. Our work is closest to [14, 28] who use Newton updates to efficiently delete data

---

for generalized linear models. Sekhari et al. [28] improve upon Guo et al. [14] in multiple ways: (i) by not requiring full access the training dataset, providing (ii) generalization guarantees, and (iii) removing the requirement for randomization in the learning algorithm itself (which often reduces utility). Yet the algorithm developed by [28] targets the batch setting which is unrealistic in practice and they provide no empirical results demonstrating the efficacy of their algorithm. If implemented in an online way, their algorithm would suffer a much larger computational cost given the requirement to compute and invert a new Hessian for each delete request. Finally, neither of these algorithms provide theoretical guarantees for the commonly used models that are obtained from objective functions with non-smooth penalties.
We address several of these issues using the (proximal) infinitesimal jacknife [13, 17, 10]. Our algorithm can handle online delete requests selected in an adaptively adversarial manner (a failure mode of many previous algorithms pointed out by Gupta et al. [15]) making it more practical for real world use. Furthermore, we provide generalization and deletion capacity guarantees similar to Sekhari et [28] for both smooth and non-smooth regularizers.
do so, we leverage similar guarantees found in approximate vols-valiittion literature [35]. Finally, inspired by recent working showing that hyperparameter tuning can leak user data [25] we demonstrate that all approximate unlearning algorithms introduced so far fail to unlearn in settings where hyperparameter tuning has taken place to choose a model.
3 Methods and Results
Learning Consider the objective function comprised of loss function regularizer and regularization parameter E A C [0, oo]. The goal of learning is to find parameter 0* (A) which minimizes the population risk
(2), A Exwp[e(z, 0)] (m(
Given the distribution D is often inaccessible, practitioners often instead find model (A) which (at least approximately) minimizes the empirical risk
Fz, 0, A Ei= ((2,,) 0) + Ar(
(1)
corresponding to given dataset S = (z1,...
Unlearning Having used dataset S to train and publish a model (A), a set of m users in the training set U S might request that their datapoints be deleted and that any models produced using their data be removed. To comply with this request, an organization might find the minimizer (A) of the leave-U-out objective
2 1 (sESs AT
While reoptiminzing the leave-one-oul objective from scratch constitutes baseline for the problem of unlearning, the computational cost makes complying with every data delete request this way undesirable. Training from scratch satisfies the notion of unlearning [28] formalized in Definition 1.
Definition 1 ((e, unnleannng [28]). Let S be a fixed training set and S 0 be an algorithm
that trains on S and outputs a model E O. For an > O and set of delete requests U C S. we say that a removal mechanism M is (c, -nnleernnn for learning algorithum A if C θ and 5 C 2, the following two conditions are satisfied:
PMM(U, A(S), E T SERM E ET) +6, and A(SO) E T) ((M E + +
Finally, we point out that like most previously proposed unlearning algorithms, we do not require T(S) contain the entire training set, but instead propose unlearning algorithms for which T(S) independent of n.
3

---

3.1 Unlearning models obtained via regularized empirical risk minimization
We recommend use of the following proximal operator to comply with delete requests (v) argmin ||0 0 + (T()),
prox #
(3)
PCR
which allows us to handle objective functions that incorporate non-smooth regularizers, such as the l,, elastic net or nuclear norm penalty, More specifically, having deleted the datapoints in the set U, we propose Algorithm 1 to delete the data of an additional user j.
Algorithm 1 Infinitesimal Jacknife (IJ) Online Unlearning Algorithm
Input: |0| = m, Hessian of loss or objective, -n 0N n.-U (A) On (A), and delete request j
Set: H, = Σー= Vz((zz,0,) 0m), H = 12 Vās(zz, On. A), ON (2) = o = 0n
If x is not smooth:
Compute:
8 (G) prox He (BN n (A) + 1 H 0., (2))
(4a)
c (m+1) 221n(1125/0
(4b)
Store: ON
(R.WOUBD) = ON (2) + 1 [((3 0,()
Else compute:
8 (0,((())))())) 8,,- U (A) 1 H V 8n (A))
(5a)
2
(2m+1) (2 M) In(1 25/8)
(5b)
Sample: ~ c00,cl)
Return: 0n (V.-(()()))))) = 0n, =0n- to
Guarantees While we give guarantees for functions that are strongly convex, we rely on standard reductions from the convex setting to the strongly convex setting (i.e. based on defining a objective function F(0)= F() + (1/2)]10012 when f is convex). Furthermore, similar to Guo et al. [14, 3.3] our methods can be used for unlearning in the non-convex setting when the deep learning model applies a simple convex model to a differentially private feature extractor [1].
Assumption (Smooth regularizer). For any 2 Z, the objective function F(0, 2, X) is p-stroonly convex and L- L-Lipschitz with M smooth Hessian. The loss has C-Lipschitz Hessians.
Assumption 2 "Non-smoote regularizer). For any Z, the loss function E(O, 2) u-strongly convex and L- L-Lipschitz with M-smooth and C-Lischiirz Hessians. The regularizer πt (6) is convex.
With either of these assumptions, it's possible to show that the denoised output of Algorithm is O(m²/1²² close to the exact unlearned model. We formalize this proximity result in the follow- ing Lemma
Lemma (Proximity to the baseline estimator). Suppose F' satisfies Assumption or Assumption 2. Let S be the dataset of size n sampled from D and U S S denote the set of m delete requests. Consider On,-u (A), i.e. the output of Algorithm I without noise term added and the model (A) obtained by minimizing the Seave-U-oul objective Fn,-U- Then,
(2) On)l1(A))12 <
ml jnn
and
(6a)
110,. -, (A)ll2 <
2m CL m m²ML" 1
(6b)
n²
Lemma implies adding the noise term x O(m² /n²) will result in the desired unlearning guarantee. The following Theorem I outlines this guarantee as well as the proximity of the unlearnt model to the test loss minimizer. The proof is contained in Appendix A.

---

= A(S) such that the Theorem (Unlearning and generalization guarantees). Suppose the loss function satisfies Assump- tion I or Assumption 2 and consider any learning algorithm that returns model O(1/n²) close to the empirical risk minimizer (2) trained on any dataset S ~ DD of size n. Then the output 0, (A) of Algorithm I, where [U] m, satisfies the test evror bound
B[F(On, F( (X))I So
VayIm(11/n)
1ma
pm
Furthermore, the unlearning Algorithm I results in (e, 8) Juulearnnn of Vz U.S.
3.1.1 Deletion Capacity
Sekhari et al. [28] introduce the notion of deletion capacity which formalizes how many samples can be deleted from a the model parameterized by the original empirical risk minimizer 6, (A) while maintaining reasonable guarantees the test loss. We restate the definition here.
Definition 2 (Deletion capacity [28]). Let c, 5, > O and S be a dataset of size n drawn i..d From D. and let F(0, 2, X) be an objective function. For a learning algorithm and removal mechanism M that satisfies (e, (4,8))nnleeaiing of all z E U, where U is the set of delete requests, the deletion capacity me,b.r (d,n) is defined as the maximum number of samples that be unlearned while still ensuring the excess population risk is 7. Specifically,
A.M m (d,n) n) A max {m [maxugs<U|sm S,), F(O()))))))))))) <>}
where the expectation is with respect S and output of the learning algorithm and removal mechanism M.
Sekhari et al. [28] provide both an upper bound and lower bound on the deletion capacity of unlearning algorithms. We recount both bounds and show our algorithm achieves the same bounds.
Theorem 2 (Deletion capacity upper bound (28]). Let 8 < 0.005 and = 1. There exists a 4-Lipschitz and I I-strongly convex loss function S. and distribution 'D such that for any learning algorithm A and removal mechanism M that satisfies (e, -)-ulleannnng and has access to all undeleted samples S SNU then the deletion capacity is:
A.M m me,,, (d, n) S en,
where the constant depends on the Lipschitz constants L, M, strongly convex constant ps, and boundedness constant C from Assumptions
and 1.
Theorem 3 (Deletion capacity lower bound [28]). Let e, 5 > 0 and 0.01, S be dataset of size drawn i..d from D, and F(0, ;0,,a, z, X) be an objective function satisfying Assumption or Assumptions Consider learning algorithm A that returns the empirical risk minimizer and unlearning algorithm M. Then the deletion capacity is:
A.M m e,6.0001 (d, n) c nyee
(dlog() (18))
where the constant e. depends on the Lipschitz constants L,, C, and M.
Theorem 4 (Deletion capacity from unlearning via DP [28]). There exists a polynomial time learning algorithu A and removal mechanism M of the form deletion capacity is:
A.M m c,600.01 (d, n)) >
//log(es/8)
where the constant in Q-notation depends on the properties of the loss function f.
As an extensions of result developed by Bassily al. [2. Section CJ, Sekhari et al. [28] show that any unlearning algorithm that ignores the samples U can't improve upon the DP lower bound. This motivates the study algorithms specifically designed for unlearning which leverage samples from U instead of algorithms based on DP. In Appendix B, we provide details showing that our Algorithm I achieves the lower bound (7), where the constant depends on the Lipschitz constants I., M, strongly convex constant μ4, and boundedness constant C.
5

---

Comparison to previous results We compare our method to Sekhari et al. [28] and Guo et al. [14] who propose optimizing a second-order Taylor approximation (TA) to the leave-U -out objective function (2) for batch removal of U. This results in the Newton-like removal mechanism (8).
= (A)
m-m ( n-m ( ExESRO V3F((, ΣxEU Ve(2,0n(()
(8)
Comparison of Assumptions. On the one hand, our Assumption 1 is slightly more restrictive than that of Sekhari et al. [28] given we require boundedness of the Hessian loss obtain unlearning, generalization and deletion capacity guarantees. Notably, this assumption does not rule out any of the most common convex objective functions (e.g. least squares, logistic, hinge, cross entropy loss functions). On the other hand, our technique allows for non-smooth regularizers which are common in modern machine learning pipelines.
Comparison of Computation. Algorithm 1 entails calculating and inverting the full Hessian H or Hig and storing (memory cost O(d²) and computation cost O(d))) It also entails storing the gradient of each point evaluated on the full data model (A), as well as the current model u In the setting where æ is not smooth, (A) must be stored. During runtime, Algorithm requires matrix-vector multiplication and vector addition (as well as proximal step in the non-smooth setting). For unlearning in settings where deletion requests come in a online manner, our technique is computationally more efficient. This is because removal mechanism (8) requires computing and inverting a different Hessian that depends on the user requesting the deletion. Therefore, outside simple settings, complying with such requests involves computational cost of (mdd)) to remove m datapoints.
Comparison of unlearning, generalization and deletion capacity. As summarized above, the general- ization, unlearning and deletion capacity results for our removal mechanism are essentially equivalent to the unlearning, generalization, and deletion capacity results of [28].
Remark 1 (Extending Sekhari et al. [28] to non-smooth regularizers). Following from the equivalence show between the batch and online setting in Appendix A.2, can extend
of the proximal operator to (8) which would extend the results of Sekhari et al. [28] to non-smooth regularizers. Similar unlearning, deletion capacity and generalization results are obtained. We provide details in Appendix C.
4 Experiments
In this section we will refer to retraining from scratch RT, the Algorithm (8) as TA and our Algorithm 1 as IJ. We empirically demonstrate the benefits of our algorithm over both RT and TA in three different settings: (i) smooth regularizers where we train a logistic regression model with an & penalty to predict between the digit 3 and 8 from the MNIST dataset [19], (ii) non- non-smooth regularizers where we train a logistic regression model with an & penalty to predict whether an individual was prescribed a Warfarin dosage of >> 30 mg/week from dataset released by the International Warfarin Pharmacogeneties Consortium [8], and (iii) non-convex training where we apply a logistic regression model with an & penalty to predict street digits signs 3 and 8 from SVHN [24] on representations extracted from a differentially private feature extractor with e = 0.1 (similar to the setup of Guo et al. [14]). For all algorithms, tune À over the set {10-3 10 - 10-5 5, 10 6 In the Appendix D, we provide further details about each dataset and the code to produce our models is attached separately.
We present results in the main paper for X = 1 and provide other results in Appendix E. All models are trained on single NVIDIA Tesla T4 GPU and 16 2.10HHz Xeon(R) Silver 4110 CPU cores. We focus our evaluation on total runtime in seconds and test set accuracy as the number of delete requests increases. Given that the current window for complying with delete requests for GDPR is one month, the runtime savings on our plots occur at month X where X is provided by the y-axis. We note that the "Right to Be Forgotten" " is much broader right and our experimental findings demonstrate that this can be satisfied much more efficiently for convex problems. For all results, we provide the average over three different runs and provide standard error bars.
Logistic Regression with Smooth Regularizers In this experiment we simulate an online data deletion setup using the MNIST dataset. For simplicity, we restrict the problem to binary classification by predicting between 3s and 8s. This is the same setup used by Guo et al. [14] evaluate their

---

2611x speed up
1.00
speed up
Test Set Acc
0.95
Runtime
4000
0.90
2000
0.85
0.80
2000 Delete Request Delete Request
2000
4000
4000
0
U
RT Method
TA
Random
Adaptive
RT & TA for smooth regularizers. Comparing both the runtime and test accuracy of the unlearned models &2 logistic regression setup for predicting 3's and 8's MNIST. For GDPR, the y-axis runtime graph denotes the runtime month under current one month delete request window.
Figure 1:
approximate unlearning algorithm. We flatten the MNIST image into 1-D vector and train an l2 regularized logistic regression model for each algorithm. sequence of 5000 datapoints (approximately 40% of the total dataset) both randomly and in an adaptively chosen manner. In these experiments we consider noise at c 0.01.
evaluate the impact of a deleting
On average. LJ was 261 Ix faster than RT and 2045x faster than TA (Figure 1). We find that this improvement in runtime comes at very minimal cost the test performance of the model returned by our algorithm compared to the test performance of TA (Figure 1). Furthermore, we observe that these results also hold when the delete requests are chosen adaptively (Figure 1). As discussed previously, the main savings in computation for our algorithm comes from only inverting the hessian once while TA requires hessian inversion for every delete request.
RT
30s
Runtime
0.6
500
RI
250 500
750
1000
Method
Delete Request
Random
Figure 2: vs. RT for non-smooth regularizers. Comparing both the runtime and test accuracy of the unlearned models our & logistic regression setup for predicting warfarin dosage. For GDPR, the y-axis of the runtime graph denotes the runtime at month X under the current one month delete request window.
Logistic Regression with Non-Smooth Regularizers This experiment showcases the performance of our proximal Newton algorithm on problem with non-smooth regularizer. We focus on predicting warfarin dosing from patient demographic and physiological data because it practical setting where regularization has been demonstrated to be preferred [30]. Given that TA does not naturally support non-smooth regularizers we only compare IJ to RT. In these experiments we consider a logistic regression objective, l regularizer, and noise level of 0.01. On average, IJ was 30x faster than RT (Figure 2). This improvement in runtime only comes at small cost to the test accuracy of the model returned by our algorithm compared to the test performance of TA (Figure 2).
Non-Convex: Logistic Regression with Differentially Private Feature Extractor We demon- strate the ability use our unlearning algorithm non-convex settings. Similar Guo et [14] we train differentially private feature extractor with c 0.1 on street digit signs from SVHN to extract representations which logistic regression model can be applied on top of. Similar to previous experiments, we pick digits and 8 for simplicity and observe significant speedups using IJ. On average, IJ was 15036x faster than RT and 17x faster than TA and these speedups come at marginal cost to the test accuracy of our algorithm even as the number of delete requests increase (Figure 3).

---

RT
TA
1.00
3000
0.95
Runtime
2000
1est
0.85
1000
0.80
10 Delete Request
20
RT Method
TA
Delete Request
Random
Adaptive
Figure 3: vs. TA and RT non-convex training. Comparing both runtime and test accuracy unlearned models in our DP feature extractor & logistic regression setup for predicting digits in photos of street signs from SVHN. For GDPR, the y-axis of the runtime graph denotes the runtime at month X under the current month delete request window.
5 Unlearning hyperparameter-tuned models
One of the most common techniques for hyperparameter tuning is cross-validation, Here datapoints used to validate and select models using the following cross-validation error objective
CV(A) = ((2,, (n,,)0n,<(\)))
Specifically, the model selection pipeline oftentimes entails selecting A that minimizes the CV error (9). Given each datapoint is used to select models, one might hope it is possible to unlearn models using Algorithm when CV is used select the model. However, the following proposition illustrates, the (c, - -unllarrnn guarantees of Theorem no longer apply when CV has taken place.
Proposition 1. Suppose cross-validation is used to select X E and the empirical risk minimizer (A) is returned. Consider a delete request by user i and the model returned by unlearning procedure (8) or (1), which we denote ( Then it is possible [|0m,-(AA) ((1))))00,;((1)) Ox))l(X))I o(1/n) where on,- is the model selected after deleting user and performing cross-validation again select X' E A before returning the empricial risk minizer.
Proof of Proposition 1. Suppose E(z,6) 0) ]= ())))(0))))))))))))))))))) 02 and oo). Note that (A) = 1+ where - = Σ'= is the sample average. Consider dataset consisting of n points (group A) with value 1 and a remaining point (group B) with value with n suppose the user in group B requests to delete their data. Performing cross-validation on this dataset will entail computing two kinds of sample averages, one where have deleted point from group A, Ž-ia = 1 n-2 + n2), and one where we have deleted the point from group B, Z-in
and
Recall the CV error
CV(A) = +eb E (2+ (A)) 2nd ( - (n 2=2) 122 + (n x2
When minimized over the set A xo oo is optimal for 2 2. This results in estimator (A) (xc) 0. The leave-one-out approximation is the same for estimators (1) and (8), given F(z, 0, I+x Subsequently, (A,-(()= (a((A) ( 2:) results in the approximation (oo) 0. On the other hand, having deleted the datapoint from group B, we have a new sample mean E = and CV error, given by
CV(A) = 2n Σn (A)= = (- 1
1212
minimized by À = 0. This results leave-one-out minimizer 0,, (0) 1
An implication of Proposition is that Algorithm as well as the algorithms proposed by [28, 14] do not unlearn models when cross-validation is used to selected hyperparameters. This because noise term Omm² //nn/))) is no longer sufficient to guarantee datapoint is unlearned. This means that organizations which train their models using cross-validation and use approximate unlearning algorithms could still be leaking information about the data which they delete.

---

Discussion
main contribution of our study is the development of an efficient online/batch data deletion algorithm for non-smooth problems. The only previous work proposing a low-memory online algorithm is Guo et al. [14]. However, Marchant et [20] show that this algorithm is susceptible to poisoning attacks rendering it highly inefficient. While exact unlearning algorithms such as SISA and retraining naturally work an online setting, our work is the first to make this work for approximate unlearning algorithms. Further development of data deletion algorithms should focus more minimizing computational cost on the streaming batch setting to ensure practical use. Also, while the current form of GDPR legislation allows quite a bit of time for companies to comply (30 days), we believe that showing a tool can provide the same empirical performance and theoretical guarantees with immediate deletion is beneficial toward encouraging companies to complying with GDPR requests more swiftly (and might encourage lawmakers to necessitate faster compliance). When individuals request delete their data, it is sometimes because they concerned about the risk of potential harm if their data remains available; this risk is potentially compounded the longer takes for the data to be deleted. By showing it can be done quickly, companies may be encouraged to act more expeditiously and less harm might occur.
The infinitesimal jacknife has been previously been used to perform cross-validation. We note deep connections between the approximate cross-validation algorithms and approximate machine unlearning algorithms. The algorithm developed by [28]. for example, can be viewed analog of the approximate vrossvvaldattion algorithm proposed by [3. 26]. Additionally, the model selection error bounds provided in the approximate cross-validation literature for example in [35] are very similar to the generalization guarantees proved in our work and [28] where we are concerned with the error introduced by approximation to the unlearning baseline. We believe further connections could be exploited to provide unlearning algorithms when hyperparameter tuning has taken place.
In this work and in several others we consider definition of data deletion that is parameterized by two values and As the case with differential privacy, is currently unclear what the impact of satisfying different levels of e means practically. Developing auditing algorithms [32] similar to those recently seen in the DP community [18, 22] can help provide more transparency on the meaning of the (e, 8) unllarniig guarantee.
Finally, we return to the broader question we posed at the beginning: what does mean to delete data from a machine learning pipeline? Most existing work focuses on data deletion in the model training process. Yet, the machine learning and data analysis pipeline is much broader than just model training. As evidenced in Section 5, the lack of research on data deletion in model selection could potentially result in information being leaked from previously proposed unlearning algorithms. Given this result, it is likely that all unlearning algorithms (both exact and inexact) still leak information about deleted data in other stages of the machine learning pipeline such as exploratory data analysis and feature selection. We encourage the community to explore definitions of data deletion which encompass the entire machine learning pipeline.
Acknowledgements
The authors would like thank the NeurlPS 2022 reviewers and area chair for their comments and feedback. The authors acknowledge the MIT SuperCloud and Lincoln Laboratory Supercomputing Center for providing (HPC, database, consultation) resources that have contributed the research results reported within this paper/report. VMS is supported by a Wellcome Trust Fellowship.

---

References
[1] Martin Abadi, Andy Chu, lan Goodfellow, H Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC conference on computer and communications security, pages 308-318, 2016.
[2] Raef Bassily, Vitaly Feldman, Kunal Talwar, and Abhradeep Guha Thakurta. Private stochastic convex optimization with optimal rates. Advances in Neural Information Processing Systems, 32, 2019.
[3] Ahmad Beirami, Meisam Razaviyayn, Shahin Shahrampour, and Vahid Tarokh. On optimal generalizability in parametric learning. In Advances in Neural Information Processing Systems, pages 1455-3465, 2017.
[4] Lucas Bourtoule, Varun Chandrasekaran, Christopher A Choquette- Choot, Hengrui Jia, Adelin Travers, Baiwu Zhang, David Lie, and Nicolas Papernot. Machine unlearning. In 2021 IEEE Symposium on Security and Privacy (SP), pages 141-159. IEEE, 2021.
[5] Lee A Bygrave. A right to be forgotten? Communications of the ACM, 58(1)335-37, 2014.
[6] Yinzhi Cao and Junfeng Yang. Towards making systems forget with machine unlearning. In 2015 IEEE Symposium Security and Privacy, pages 463 IEFF, 2015.
[7] Federal Trade Commission. California company settles fte allegations it deceived consumers about use of facial recognition in photo storage app.
[8] International Warfarin Pharmacogenetics Consortium. Estimation of the warfarin dose with clinical and pharmacogenetic data. New England Journal of Medicine, 360(5)7733)64 2009.
[9] Cynthia Dwork, Aaron Roth, et al. The algorithmic foundations of differential privacy. Found. Trends Theor. Comput. Sci., 9(3-4)221-400) 2014.
[10] Bradley Efron. The jackknife, the bootstrap and other resampling plans. SIAM, 1982.
[11] Sanjam Garg, Shafi Goldwasser, and Prashant Nalini Vasudevan. Formalizing data deletion in the context of the right be forgotten. Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 373-402. Springer, 2020.
[12] Antonio Ginart, Melody Guan, Gregory Valiant, and James Zou. Making ai forget you: Data deletion in machine learning. Advances Neural Information Processing Systems, 32, 2019.
[13] Ryan Giordano, William Stephenson, Runjing Liu, Michael Jordan, and Tamara Broderick. swiss army infinitesimal jackknife. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 1139-1147. PMLR, 2019.
[14] Chuan Guo, Tom Goldstein, Awni Hannun, and Laurens Van Der Maaten. Certified data removal from machine learning models. In International Conference on Machine Learning. pages 3832-3842. PMLR, 2020.
[15] Varun Gupta, Christopher Jung, Seth Neel, Aaron Roth, Saeed Sharifi-Malvajerdi and Chris Waites. Adaptive machine unlearning. Advances in Neural Information Processing Systems, 34, 2021.
[16] Zachary Izzo, Mary Anne Smart, Kamalika Chaudhuri, and James Zou. Approximate data deletion from machine learning models. In International Conference on Artificial Intelligence and Statistics, pages
PMLR, 2021.
[17] Jaeckel. The infinitesimal jackknife. memorandum. Technical report, MM 72- 12-1211- Bell Lab. Murray Hill, NJ, 1972.
[18] Matthew Jagielski, Jonathan Ullman, and Alina Oprea. Auditing differentially private machine learning: How private is private sgd? In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 22205-22216. Curran Associates, Inc., 2020. URI. https h/tp://pproooe ppwppeeeiiggss...m www.ssseerppecccm cc/ httee//DDD.iifffccccdssseseoreen
httpps://proceedingss -Ppeer pdf.
10

---

[19] Yann LeCun. The mnist database of handwritten digits. http://yann. lecun. com/exdb/nmist// 1998.
[20] Neil G Marchant, Benjamin IP Rubinstein, and Scott Alfeld. Hard forget: Poisoning attacks on certified machine unlearning. arXiv preprint arXiv:2109.08266, 2021.
[21] Dominic McGoldrick. Developments in the right to be forgotten. Human Rights Law Review, 13(4):761-77, 2013.
[22] Milad Nasr, Shuang Songi, Abhradeep Thakurta, Nicolas Papemoti, and Nicholas Carlin. Adversary instantiation: Lower bounds for differentially private machine learning. In 202/ IEEE Symposium on Security and Privacy (SP), pages 866-882. IEEE, 2021.
[23] Seth Neel, Aaron Roth, and Saeed Sharifi-Malvaeerdi.. Descent-to-delete: Gradient-based methods for machine unlearning. In Algorithmic Learning Theory, pages 931-962. PMLR, 2021.
[24] Yuval Netzer, Tao Wang, Adam Coates, Alessandro Bissacco, Bo Wu, and Andrew Y Ng. Reading digits in natural images with unsupervised feature learning. 2011.
[25] Nicolas Papernot and Thomas Steinke. Hyperparameter tuning with renyi differential privacy. arXiv preprint 1rXiv22100.03620 10.03620, 2021.
[26] Kamiar Rahnama Rad and Arian Maleki. A scalable estimate of the out-ol-sample prediction error via approximate leave-one-out, arXiv preprint arXiv:1801. 2019.
[27] Jeffrey Rosen. The right to forgotten. Stan. L. Rev. Online, 64:88, 2011.
[28] Ayush Sekhari, Jayadev Acharya, Gautam Kamath, and Ananda Theertha Suresh. Remember what you want to forget: Algorithms for machine unlearning. Advances in Neural Information Processing Systems, 34, 2021.
[29] Shai Shalev-Shwartz, Ohad Shamir, Nathan Srebro, and Karthik Sridharan. Stochastic convex optimization. In COLT, volume 2, page 5, 2009.
[30] Ashkan Sharabiani, Adam Bress, Elnaz Douzali, and Houshang Darabi. Revisiting warfarin dosing using machine learning techniques. Computational and mathematical methods in medicine, 2015, 2015.
[31] Reza Shokri, Marco Stronati, Congzheng Song, and Vitaly Shmatikov. Membership inference attacks against machine learning models. In 2017 IEEE symposium on security and privacy (SP), pages 3-18. IEEE, 2017.
[32] Anvith Thudi, Hengrui Jia, Ilia Shumailov, and Nicolas Papernot. On the necessity of auditable algorithmic definitions for machine unlearning. arXiv preprint 10.iv:2110.118890 2021.
[33] Enayat Ullah, Tung Mai, Anup Rao, Ryan A Rossi, and Raman Arora. Machine unlearning via algorithmic stability. Conference on Learning Theory, pages 4126-4142, PMLR, 2021.
[34] Paul Voigt and Axel Von dem Bussche. The eu general data protection regulation (gdpr). A Practical Guide, 1st Ed., Cham: Springer International Publishing, 1033152676;:0-5555 2017.
[35] Ashia Wilson, Maximilian Kasy, and Lester Mackey, Approximate cross-validation: Guarantees for model assessment and selection. In International Conference on Artificial Intelligence and Statistics, pages 4530-4540. PMLR, 2020.

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [Yes]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or as URL)? [Yes]
(b) Did you specify all the training details (e.g., data splits. hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g.. with respect the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (c.g., type of GPUs, internal cluster, or cloud provider)? [Yes]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [Yes]
(c) Did you include any new assets either the supplemental material or as URL? [No]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
12


Reviews:
[{"review_id": "SKIq5VqZ3fI", "reviewer": "Reviewer_p3VE", "summary": "The paper proposes an online approximate unlearning algorithm that is efficient in computation and memory. To begin with, the paper uses the infinitesimal jackknife to enable the proposed algorithm to delete data from models trained which is non-smooth regularized. Furthermore, the paper theoretically proves the generalization and deletion capacity of the proposed method. Finally, extensive experimental results demonstrate that the proposed method can exceed in retraining the model and the second-order Taylor Approximation[1]. \nFrom my point of view, this paper falls into several significant drawbacks and might be improved by addressing the following issues:\n1. It’s not clear how can the proposed method be effective in non-smooth regularized models. \n2. The proposed method only inverts the Hessian for one time, but how can it ensure the total error is tolerable. \n3. The supplementary lacks the comparison of runtime in different hyperparameter settings. \n4. The candidates of the hyperparameter \\lambda may be {10^{-3}, 10^{-4}, 10^{-5}, 10^{-6}} rather than {1^{-3}, 1^{-4}, 1^{-5}, 1^{-6}}. \n\n[1] Ayush Sekhari, Jayadev Acharya, Gautam Kamath, and Ananda Theertha Suresh. Remember what you want to forget: Algorithms for machine unlearning. Advances in Neural Information Processing Systems, 34, 2021.\n", "questions": "1. How can the proposed method be effective in non-smooth regularized models?", "limitations": "The paper has not addressed the limitations of their work. It states that the proposed method fails to run with hyperparameter tuning, which is a common issue existing in unlearning algorithms.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: \n1. The paper provides sufficient theoretical proof of the proposed method. \n2. According to the experimental results, the proposed method outperforms much better than the previously proposed unlearning algorithms. \nWeaknesses: \n1. The paper mainly enables the unlearning algorithm to be applied in non-smooth regularized models, but does not explain it specifically. \n2. Lacking the comparison of runtime in different hyperparameter settings.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "J1ylj7DYNWd", "reviewer": "Reviewer_EwhA", "summary": "In this paper, the authors study the data deletion problem under the online setting. For linear models, the authors propose a second order online data deletion algorithm that enjoy better theoretical guarantees than existing methods. The algorithm can also be extended to non-smooth regularization objectives through a proximal gradient variant. Empirical studies have also shown the proposed algorithm to significantly improve over the time complexity of existing baselines while sacrificing some test accuracy. In the end, the authors propose a simple cross validation setting where all existing algorithms fail to have any theoretical guarantees.", "questions": "1. Could you give a concrete example where online data deletion is necessary?\n2. Is there motivating examples of linear models of scale significant enough that retraining underperforms the proposed data deletion algorithm? Or alternatively, do the authors find the algorithm easily generalizable to neural networks?\n", "limitations": "I think the limitation of hyper-parameter tuning is very interesting.\n\nOn the other hand, please see the above questions regarding limitations of use cases of the proposed algorithm.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Overall, I find the paper to exhibit reasonable improvement over existing work. I also find the discussion in the end of the paper regarding model tuning to be valuable and a highlight of the paper.\n\nOn the other hand, I find the setting motivation to be relatively unsupported:\n1. The authors use data regulations for industrial sized models as motivation of the paper. However, most industrial models of the scale are deep neural networks. The study of only linear models seem ill-suited.\n2. The authors argue that the online setting is more practical. However, taking GDPR for example, the companies are obligated to delete user data only within a month instead of immediately. As a result, I find the batched setting to be more realistic where retraining could also be competitive.\n3. As a result of the above comment, is it fair to compare IJ against RT and TA in the online setting? I believe it is more reasonable compare against the methods for removing an entire batch.\n4. The proposed Algorithm 1 would benefit from more detailed description and intuition.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "6gPRjpakWh-", "reviewer": "Reviewer_K2o8", "summary": "The paper provides an algorithm for online data deletion. They consider unlearning with convex / strongly convex loss functions (with additional assumptions standard in the literature). The key improvement in the algorithm over prior works in [15, 29] is to provide an update step that does not require to recompute a new hessian inverse for every new deletion request (which they call infinitesimal Jacknife (IJ). Thus, they improve the running time from O(md^3) to O(md^2) where \\(m\\) is the number of deletions that can be handled. The authors provide extensions of this update step when the underlying regularization is not smooth (but the objective function is still smooth). This is obtained using a proximal update. Finally, the authors show an interesting limitation of unlearning for ERM based learning procedures. ", "questions": "Refer to above comments", "limitations": "I do not see any negative societal consequences. In fact, the paper is trying to develop solutions for the important issues of right to be forgotten. ", "rating": 7, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength: The topic of machine unlearning is new and upcoming. The paper addresses computational side of the problem in the online deletion setting which is an important problem. The paper is well written! \n\nWeaknesses: \n1. I feel the key technical improvement from prior works is to come up with update in 5a in which H_l^{-1} does not need to be updated after every deletion request. While being interesting, I feel jacknife, proximal updates, etc are all well established theoretical tools and there is not much that fundamentally new, which is why I am not giving this paper a strong accept. \n\n\n2.  I am a bit confused by the rationale to choose Definition 1 from [15] (instead of the smilar definition from [29]). In order for this definition to hold, one needs to randomize the out of the learning algorithm (which would decrease performance). In the corresponding definition in [29], one does not need the learning algorithm to be randomized. Furthermore, in your experiments where you report RT is this ERM + noise or just ERM ? (I feel there is a mismatch between the two sections). \n\n3. Suppose we restrict outselves to generalized linear models ? In this case, the hessian is the sum of rank-1 matrices (one corresponding to each data point), and online updating the hessian as in [15, 29] is easy to do. What are the benefits of your algorithm in that case? \n\n4. Do you have any suggessions from mitigating the reported issue in Section 5 for hyperparameter-tuned models ? \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept