Forget Unlearning: Towards True Data-Deletion in Machine Learning
Authors: Rishav Chourasia
Neil Shah
Reza Shokri
Venue: Submitted to ICLR 2023 (2023)
Keywords: Unlearning
Differential Privacy
Data Deletion
Noisy Gradient Descent

Abstract: Unlearning has emerged as a technique to efficiently erase information of deleted records from learned models. We show, however, that the influence created by the original presence of a data point in the training set can still be detected after running certified unlearning algorithms (which can result in its reconstruction by an adversary). Thus, under realistic assumptions about the dynamics of model releases over time and in the presence of adaptive adversaries, we show that unlearning is not equivalent to data deletion and does not guarantee the "right to be forgotten." We then propose a more robust data-deletion guarantee and show that it is necessary to satisfy differential privacy to ensure true data deletion. Under our notion, we propose an accurate, computationally efficient, and secure data-deletion machine learning algorithm in the online setting based on noisy gradient descent algorithm.

Under review as a conference paper at ICLR 2023
FORGET UNLEARNING: TOWARDS TRUE DATA-DELETION IN MACHINE LEARNING
Anonymous authors Paper under double-bling review
ABSTRACT
Unlearning has emerged as a technique to efficiently crase information of deleted records from learned models. We show, however, that the influence created by the original presence of a data point in the training set can still be detected after running certified unlearning algorithms (which can result in its reconstruction by an adversary). Thus, under realistic assumptions about the dynamics of model releases over time and in the presence of adaptive adversaries, we show that unlearning not equivalent to data deletion and does not guarantee the "right to be forgotten." We then propose more robust data-deletion guarantee and show that it is necessary to satisfy differential privacy to ensure true data deletion. Under our notion, we propose an accurate, computationally efficient, and secure data-deletion machine learning algorithm in the online setting based on noisy gradient descent algorithm.
INTRODUCTION
Many corporations today collect their customers' private information to train Machine Learning (ML) models that power variety of services, encompassing recommendations, searches, targeted ads, and more. To prevent any unintended use of personal data, privacy policies, such as the General Data Protection Regulation (GDPR) and the California Consumer Privacy Act (CCPA), require that these corporations provide the "right to be forgotten" (RTBF) to their data subjects- if a user wishes to revoke access their data, an organization must comply by erasing all information about the user without undue delay (which is typically a month). This includes MI. models trained in standard ways as model inversion (Fredrikson et al., 2015) and membership inference attacks (Shokri al. 2017] Carlini et al. 2019) demonstrate that individual training data can be exfiltrated from these models.
Periodic retraining of models after excluding deleted users can be costly. So, there is a growing alternative to
interest in designing computationally cheap Machine Unlearning algorithms retraining for erasing the influence of deleted data from (and registering the influence added data to) trained models. Since it is generally difficult tell how specific data point affeets a model, Ginart et al. (2019) propose quantifying the worst-case information leakage from an unlearned model through unlearning guarantee the mechanism, defined differential privacy (DP) like (c, 6) (i))--ndistingushabbilte
between its output and that of retraining on the updated database. With some minor variations in this definition, several mechanisms have been proposed and certified as unlearning algorithms in literature (Ginart et al. 2019 Izzo et al. 2021 Sekhari et al. 2021 Neel
al. 202
Guo et al. 2019; Ullah et al. 2001).
However, is indistinguishabiiity to retraining a sufficient guarantee of data deletion? We argue that it not. In the real world, user's decision to remove his information is often affected by what deployed model reveals about him. The same revealed information may also affect other users' decisions. Such adaptive requests make the records in a database interdependent, causing retrained model to contain influences of record even if the record is no longer in the training set. We demonstrate on a certified unlearning mechanism that if an adversary is allowed to design an adaptive requester that interactively generates database edit requests as a function of published models, she can re- re-encode a target record in the curator's s database before its deletion. We argue that under adaptive requests, measuring data-deletion via indistinguishabiiity
retraining (as proposed by Gupta et al.) al. (202T) is fundamentally flawed because it does not capture the influence a record might have previously had on the rest of the database. Our example shows clear violation of the

---

Under review as a conference paper at ICLR 2023
RTBF since even after retraining the database with the original record removed, a model can reveal substantial information about the deleted record due to the possibility of re-encodings.
Is unlearning guarantee sound and complete measure of data deletion when requests are non-adaptive? Again, we argue that it is neither. A sound data-dclction guarantee must ensure the non-recovery of deleted records from an infinite number of model releases after deletion. However, approximate indistinguishability to retraining implies an inability to accurately recover deleted data from a singular unlearned model only, which we argue is not sufficient. We show that certain algorithms can satisfy an unlearning guarantee yet blatantly reveal the deleted data eventually over multiple releases. The vulnerability arises in algorithms that maintain partial computations in internal data structures for speeding up subsequent deletions. These internal states can retain information even after record deletion and influence multiple future releases, making the myopie unlearning guarantee unreliable in an online setting. Several proposed unlearning algorithms in literature (Ginart al. 2019 Neel et al. 202T) are stateful (rely on internal states) and, therefore, cannot be trusted. Secondly, unlearning is incomplete notion of data deletion as it excludes valid data-deletion mechanisms that do not imitate retraining. For instance, a (useless) mechanism that outputs fixed untrained model any request is valid deletion algorithm. However, since its output is easily distinguishable from retraining, it fails to satisfy any meaningful unlearning guarantees.
This paper proposes sound definition of data deletion that does not suffer from the abovementioned shortcomings. According to our notion, a data-deletion mechanism is reliable if A) it is stateless (i.e., it maintains internal data structures), and B) generates models that are indistinguishable from some random variable that is independent of the deleted records. Statelessness thwarts the danger of sustained information leakage through internal data structures after deletion. Moreover, by defining data deletion as indistinguishabiiiy with any deleted-record independent random variable as oppsed to the output of retraining, we ensure reliability in presence of adaptive requests that create dependence between current and deleted records in the database.
In general, we show that data-deletion mechanisms must be differentially private with respect to the remaining records to be reliable when requests are adaptive. DP also protects against membership inference attacks that extract deleted records by looking at models before and after deletion (Chen) al., 2021). We emphasize that we are not advocating for doing data deletion through differentially- private mechanisms simply because it caps the information content of all records equally, deleted or otherwise. Instead, data-deletion mechanisms should provide two differing information reattainment bounds; one for records currently in the database in the form of a differential privacy guarantee and the other for records previously deleted in the form of a data-deletion guarantee. We also provide a reduction theorem that if a mechanism is differentially private with respect to the remaining records and satisfies data-deletion guarantee under non-adaptive edit requests, then it also satisfies data-deletion guarantee under adaptive requests. Based on this reduction, we redefine the problem of data-deletion as designing mechanism that (1.) satisfies a data-deletion guarantee against non- adaptive deletion requests, (2.) is differentially private for remaining records, and (3.) has the same utility guarantee as retraining under identical differential privacy constraints. We judge the usefulness of data-deletion mechanism based on its computational savings over retraining.
For our refined problem formulation, we provide data-deletion solution based on Noisy Gradient Descent (Noisy-GD), popular differentially private learning algorithm (Bassily et al. 2014] Abadi ct al. 2016 Chourasia et al. 202I). Our solution demonstrates a powerful synergy between data deletion and differential privacy as the same noise needed for the privacy of records in the database also rapidly erases information regarding records deleted from the database. We provide a data- deletion guarantee for Noisy-GD in terms of Rényi divergence (Rényi et al. 1961) bound (which implies (s, "o--iiistinguushablitt [Mironov 2017 For convex and smooth losses, we certify that under a (g, ead) dda--Rénii data-deletion and (g, Edp) (..Epp)-RRe Rényi DP constraint, our Noisy-GD based deletion mechanism for d-dimensional models over nisized databases under adaptive edit requests that modify qd
no more than r records can maintain optimal excess empirical risk of the order O
while saving
Edp
(n log(min f. n. known lower bound on private empirical risk minimization under same privacy budget (Bassily et al.) 2014h. We also provide data-deletion guarantee in the non-convex setting under the assumption that loss function is bounded and smooth, and show a computational saving of ((nn log @ in gradient
Edd }) computations in gradient complexity. Our utility guarantee matches the qd
complexity while maintaining an excess risk of Ô gd
Cap
Edp
2

---

Under review as a conference paper at ICLR 2023
2 MODEL AND PRELIMINARIES
2.1
INDISTINGUUSHAABLIIT NOTIONS AND DIFFERENTIAL PRIVACY
We provide the basics of indistinguishabiiity of random variables (with more details in Appendix D
Let O' be two random variables in space O with probability densities v, v respectively.
Definition 2.1 inf.--)idisiinuushablllyy (Dwork al. 2014)). We say O and &' are (c,
e.6 if. for all CO
indistinguishable and write
PP P OJ S e T
( 00 + and PIo's p
(1)
Definition 2.2 (Rényi divergence (Rényi et al. 1961)). Rényi divergence of v w.r.t. v' of onder q > 1 is defined as
4
R2 (vll>)
log E. (vll>), where Eg (vllv)= = E
(2)
B
v
when v is absolutely continuous w.r.t. v' (denoted as v & v') If * v', we'll say Rg (vllv) = co.
Remark 1. Rényi divergence is assymetric (i.e. Rg (vllv)) + R2 (Vllv)) and implies indistin- guishability only in one direction. Mironov (2017 Proposition 3) show that Rg (yllv') S Eu implies
P 0J S (P' O] + å with Eo + log 1/5 and any 8 < 1.
q
Definition 2.3 (Differential Privacy (Dwork et al.
2014
Mironov 2017); ). A randomized mechanism
M X + O is (e, 8) -differentially private if
M(D)
& M(D') for all neighbouring databases
D, D' E 2 Similarly, M is (g, R)-ééyi differentially private R, (M(D))[M(D')) S..
2.2 LEARNING FRAMEWORK: ERM
Let D be database of ordered records taken from data universe X' and let O be the space of learnable parameters and any associated auxiliary metadata (what constitutes a metadata is clarified later). Let x(0:x) O x X + IR be loss function of parameter 0 E O for record x X. In this paper, we consider the problem of empirical risk minimization (ERM) of the average E(0; x) over Sllll i.e., the minimization objective
records in the database DD under 1.2 regularization r(0) 2 (D) = ExED E(0: x) + r(f). The excess empirical risk of model θ for D by is defined as err(O: D) = (e) (0b)), where 0x arg min (0) and expectation taken over O.
AEO
We build popular DP-ERM algorithm called Noisy-GD (Abadi et al. 2016 described in Algorithm below, and provide Rényi DP guarantees on it in Appendix G.3
Algorithm Noisy-GD: Noisy Gradient Descent
Require: Database D E X"", start model Ou O, number of steps K E N. 1: for == 0. 0, 1,.....
do
2: (LD(O,)))
Σxe XXE ve(O,A:: vr(O 3: 1n = Oyp V/V V2TN (0, oaTaa
4: Output θnK
2.3 ONLINE EDIT REQUESTS AND MACHINE UNLEARNING
Suppose that any database D E x can be modified by edit requests that replaces r distinct records Definition 2.4 (Edit request). A replacement operation (ind,y) E [n] X database
D D=(X1, ... (x)) performs the following modification:
Do (ind, y) (xi,... Xmnd11, Xind11, X.n)
(3)
Let r S and 4r = [n] x X". An edit request = {(ind,,y)). (ind,. vr)) E Ur on D is defined as batch of replacement operations modifying distinct indices atomically, i.e.
D D (ind1, y1)
(ind,; Yr), where ind, + ind, for all + j.
(4)
We consider replacement instead of separate additionn/deletonn ensure that database size doesn't change.
3

---

Under review as a conference paper at ICLR 2023
Let O denote the space of model parameters plus any state variables or strutstrussures that may be leveraged for processing edit requests and Φ be the space of publishable outcomes such as sanitized models or predictions. For initial database Do E X and an unbounded sequence of edit requests (u))21, the job of data curator is train model Ô; O with small empirical risk for each database D; = Do .... o and use it to release corresponding publishable outcome, 6; E Φ For this task, the trivial approach of retraining from scractch by executing learning algorithm on each D; could be computationally expensive. This initiated the study of machine unlearning algorithms (Cao & Yang, 2015 Ginart al. 2019 Guo et al. 2019 Izzo et al. 202T) that avoid the cost of retraining by instead fine-tuning an already trained model 0 to cheaply erase (introduce) the influence of deleted (added) records in edit request u, to D;-1 for producing the next model θ,
In this paper, adopt the machine unlearning formulation of Gupta et al., (2021) and Neel et al. (2021) described as follows. The curator comprises of three mechanisms: a learning algorithm A 2m O, data-deletion or unlearning algorithm À 2 x UU x O - O, and a publish function Spub. : : - Φ. To generate the initial model with accompanying state metadata θ, O on the initial database Do E A²" the curator executes the learning algorithm A(D)). Thereafter, to process an incoming edit request u, E U" at any step > 1, the curator executes data-deletion algorithm (D; u, ④x-1) that maps the current database D;-1. the edit request u, and the current model with metadata Õ,-1 to the next model with metadata Ô; E O. While all the generated models and corresponding metadata is kept secret, the curator uses the publish function to generate the publishable outcome Φ; fuub (θ,) every step i 0.
Gupta et al. (202T) note that edit requests in real world could often be adaptive, i.e., a request ú; may depend (a subset of) the history of prior published outcomes Φc. (Ø1,-.. , ②.). For instance, a voter may decide to change his inclination after seeing pre-election results. They model such an intearctive environment through an adaptive requester defined as follows.
Definition 2.5 (Update requester (Gupta et al. 2021)). A p-adaptive r-requester is a mapping Q : Φ 2 + UI that takes as input maximum of p of the published outcomes generated by the curator at arbitrary edit steps $1 < < .... < Sp- and the entire history of previously generated edit requests to generate the next edit request. For a p-adaptive r-requester Q. the edit request u, at any step 2 1 can be writlen as
U Q(ds Psgi" Dsyj 12, (1g-1);
(5)
such that 8 < é. We refer to O-adaptive requesters as non con-adaptive. And, by co-adaptive requesters, mean requesters that huve access to the entire history of interaction transcript (Øei; uez))
Since, unlike retraining, an unlearning algorithm fine-tunes a model containing the information of records to be deleted, we need statistical guarantees on the worst-case amount of information that might still remain in the unlearned model. Ginart et al. (2019) and Guo et al. (2019) propose quantifying data-deletion ability of an algorithm A based on its (E, >i-ndistinguishablliy w.r.t. the fresh-retraining algorithm A, calling it an unlearning guarantee (more details in Appendix E. 1p. In
this paper, we mainly consider the extension of unlearning definitions by Neel al. (2021) and Gupta et al. (2021) to the online setting of arbitrarily long and adaptive edit sequences
Definition 2.6 ((E, -unllarnng NNell al. 2021 Gupta al. 2021I). We say that A is an (e, ()-
unlcarming algorithm for A under publish function Foub. for all initial databases Do E x and all non- non-adaptive 1 1-requesters Q, the following condition holds. For every edit step i 2 1, and for all def
generated edit sequences ugi (u1,".. u:).
5.6 fpub (A(D,-1, us 0.-1) 2 (A(.)).
(6)
If the same condition holds for all co-adaptive 1-requesters Q. we say that A is an (e, addptivee unlearning algorithm for A.
Definition 2.6 stronger than the adaptive unlearning definition of Gupta et al. 2021) since theirs require satisfying only one-sided indistinguishability with at-least (1 - 7) prohability over generated edit requests ugi
4

---

Under review as a conference paper at ICLR 2023
3 EXISTING UNLEARNING GUARANTEES ARE UNSOUND AND INCOMPLETE
Data deletion under the law of "right to be forgotten" (RTBF) is an obligation permanently erase all information about an individual upon a verified request. In order to comply, a corporation's 's actions must not reveal any information identifiable or linkable deleted user in the future. In this section, we argue that unlearning guarantee in Definition 2.6 is neither a sound nor a complete measure of data-deletion from ML models that RTBF enforces.
Threat model. Suppose. for an arbitrary step i 2 1, an adversary is interested in finding out the identity of record in the database D;-1 that was deleted by the edit request ug. Since RTBF violated only when the curator reveals information after the deletion request, we assume that the adversary only has access to the post-deletion releases by the curator, i.e., she observes Φi, Øi+1," ... ... Additionally, we also assume that the adversary knows how users might react to a published outcome. That is to say, our adversary knows some dependence relationship between random variables øo, ... Φi- and W1,'.., W but does not explicitly observe these random variables. For instance, an adversary might know that if the outcome d1 predicts that "Donald Trump is winning the election," then some democratic users might delete their data while some new republican users might contribute their data to the curator. So, even though the adversary does not observe the actual outcome Φ) or the ensuing edit request u2, and so on, she can still exploit knowledge about this dependence a-posteriori infer the identity of a deleted record. To capture the worst-case knowledge about the dependence between unobserved outcomes and unobserved edit requests, we model our adversary to have the power to design an adaptive requester Q that interacts with the curator in the first i 1 steps. However, the adversary does not observe the interaction transcript (du. U1, 01 ... 1; 1) of Q.
Unsoundness due to secret states. The unlearning Definition 2.6 is a bound on information leakage about deleted record through a single released outcome. However, our adversary can observe multiple (potentially infinite) releases after deletion. We argue that algorithms satisfying Definition 2.6 can lead to blatant non-privacy of deleted record under our threat model, even for a weaker adversary that cannot design adaptive requester (i.e., knows nothing about the dependence between unobserved outcomes and edit requests). The vulnerability arises as Definition 2.6 permits algorithms to maintain secret states while using publishing function fpub for releases. These internal states may propagate encoded information about records even after their deletion from the database. So, every subsequent release by unlearning algorithm can reveal new information about a record that was purportedly erased multiple edits earlier. We demonstrate in the following theorem that a certified unlearning algorithm can reveal a limited amount of information about a deleted record per release so as not to break the unlearning certification, yet eventually reveal everything about the record to an adversary that observes enough future releases.
Theorem 1. For every > O, there exists a pair (A, A) of algorithms that satisfy (c. O)-unlaarning under publish function fpub such for all non adn-tide 1-requesters Q, their exists an adversary that can correctly infer the identity of a record deleted at any arbitrary edit step Z 1 by observing only the post-edit releases oz: = (0:, ".+)
Unsoundness due to adaptivity. For an adversary that knows some dependence relationship between the unobserved outcomes and edit requests, much more severe violation of RTBF may occur, even when an unlcarning algorithm does not maintain secret internal states and perfectly imitates retraining (i.e., satisfy a (0, -daadptivve unlearning guarantee for identity publish function fout = 0). This vulnerability arises because the indistinguisaabiiiy in Definition p.ojprttscts the privacy of deleted records but not that of records currently present. A certified adaptive unlearning algorithm is allowed to reveal unbounded information about target record before its deletion. This revealed information can have a major influence on the subsequent edit requests in the worst case, potentially causing the curator's s database to have patterns specific to the identity of the target record even after its deletion. An adversary knowing the possible patterns and their causes (i.c., the dependence relationship between unobserved outcomes and requests) can therefore infer the target records's 's identity from post-deletion releases. We concretize this vulnerability in the following theorem.
Theorem 2.
There exists a pair (A, A) of algorithms that satisfy (0, a--aaaptive-umleane an identity publish function fp) = 0 such that by designing 1-adaptive 1-requester Q. an adversary, even with no access to Q's interaction transcript, can infer the identity of a record deleted at any arbitrary edit step i 3 with probability at-least 1 (1/ /2)--3 from the post-edit release dh-
for
5

---

Under review as a conference paper at ICLR 2023
Incompleteness. Another issue with unlearning guarantees is that valid data-deletion algorithms may fail to satisfy it. As per Definition 2.6] the publishable outcome generated by a data-deletion mech- anism must imitate that of retraining algorithm for satisfying unlearning guarantee. However, imitating retraining is not necessary for data deletion. For instance, consider a (useless) mechanism A that outputs fixed untrained model in O regardless of its inputs. This A would be an unac- ceptable unlearning algorithm for most re- re-training algorithms A under an identity publish function fpub (0) 0. However, (pub(A(-) (A(+) contains information about the deleted records and should be acceptable under the data-deletion paradigm.
Remark 2. Several prior works on machine unlearning propose data-deletion definitions similar to Definition 2.6 but without an explicit fpub and for the offline setting of single-stage deletion to remove many records from a learned model Ginart el al.] 2019: Guo el al. 2019; (Sekhari et al. 2027). In Appendix E we show that these offline unlearning defiiitios are also unreliable when deletion requests adaptive. In light of our demonstration of unsoundness of these data-deletion guarantees, we remark that several certified unlearning algorithms in literature should not be trusted
ensure RTBF.
4 REDEFINING DATA-DELETION IN MACHINE LEARNING
In this section, we redefine data deletion in Machine Learning to address the problems with the notion of unlearning that we demonstrate in the preceding section. The first change we propose is to rule out the possibility of information leakage through internal data structures (as shown in Theorem I by requiring delction mechanisms to be stateless. That is, the models produced by learning or the data-deletion algorithm directly released without applying any publish funetion fpub.
Secondly, the following definition data-deletion guarantee fixes the security blind spot of an adaptive unlearning guarantee. As demonstrated in Theorem 2] adaptive requester can encode patterns specific to a target record in the database by making edit decisions in response to the observed outcomes. Thus, being indistinguishable from retraining on the edited database does not guarantee data deletion, as the target's 's information remains extractable even after the target record's 's deletion, potentially revealing its identity. In our definition, we account for an adaptive adversary's 's influence by measuring the indistinguishability of data-deletion mechanism's 's output from some random variable that is independent of the deleted record.
Definition 4.1 ((g, datta--delltto under p-adaptive r-requesters). Let q > 1, s 2 0, and p. r E N. We say that algorithm pair (A, A) satisfies (q, ddata)ddeeeiiiiion under p-adaptive r-requesters if the following condition holds for all p-adaptive r-requester Q. For every step 2 1, there exists randomized mapping π.. X O such that for all initial databases Do X
R2 (A(D.-1, θ 1/ (DD (ind, y)), S, for all u, E U" and all (ind, y) E us. (7)
We argue that the above definition is a sound guarantee on data-deletion. Suppose that an adversary is interested in identifying a record at index 'ind' in Do that is being replaced with record 'y' by one of the replacement operations in edit request E 2t", The inequality (7) above implies that even with the power of designing an adaptive requester Q, no adversary observing the unlearned model A(D;-1: u, 1) can be too confident that the observation was not from π. (Do o (ind, y)), distribution that contains no information about the target record D/ [ind] by construction. More formally, we provide the following soundness guarantee for Definition 4.1
Theorem 3 (Data-delction Definition 4.1 is sound). If the algorithm pair (A, satisfies (g. E)- data-deletion guarantee under all p-adaptive r-requesters, then even with the power of designing an p-adaptive r-requester Q that interacts with the curator before deletion of a target record at any step i 2 1. any adversary observing only the post-deletion releases (Ô,, O.41....) has its membership inference udvantage for inferring a deleted target bounded as
Adv(MI) < geela-11/9
[2(g- - 19
(8)
9-1
Note that the bound in approaches 0 as q + 00 and - implying Definition 4.1 is sound.

---

Under review as a conference paper at ICLR 2023
Remark 3. A non-adaptive requester Q is equivalent to fixing the request sequence (u4)121 a-priori. Hence, given a non con-adaptive Q. the database Dr o (ind. y) is a deterministic function of the database Do o (ind, y) for any 2 L, thanks to the commutattivty of 'a'. Since (ind. y) ug we remark that for a non-adaptive requester Q the random variable T. (Do (ind. y)) in (7) can be the output ((D;) of any randomized map πI: X -> O, including the learning algorithm A.
Connection with DP. We highlight that our data-deletion guarantee on pair (A, A) is an information bound on the records that were deleted, while the standard DP guarantee on A and A is an information bound on the records currently present in the database. In the following theorem, we show that DP with respect to existing records is a necessary condition for (A, A) to satisfy adaptive data-deletion.
Theorem (DP is necessary for adaptive data-deletion). If learning algorithm A : X O is not (0, 6D-DP with respect to the replacement of single record and deletion algorithm A : X xxxxxxx - O is not (0, -DP with respect to the replacement of a single record that is not being deleted, then the pair (A, A) cannot satisfy (q, 8* /2) (2)-data-deletion deletion under 1-adaptive 1 1-requester for any > 1.
Additionally, if A and A does satisfy DP with respect to existing records then a data-deletion bound under non- -daaaivee requesters reduces to data-deletion bound under adaptive requesters.
Theorem (Non- adaptive data-deletion with Rényi DP implies adaptive data-deletion). If an algo- rithm pair (A, A) satisfies (q, Saa 5aa) -dataddeletion under all non-adaptive r-requesters and (g, Edp)- Rényi DP, then it also satisfies (g, Saa + pp --dat--deeettiiii under all p-adaptive r-requesters.
We provide additional discussion on this reduction theorem in Appendix F.I By virtue of our reduction Theorem we reformulate the data deletion problem in ML as follows.
Problem Definition, Let constants q > 1, < Ead S Edp. and >> 0. The goal is to design learning mechanism A X + O and deletion mechanisms A X x U" x O - O such that
(1.) both A and A satisfy (g, (dpp) DP with respect to records in the input database,
(2.) pair (A, satisfies (q. (ataaddddddaaddlle guarantee for all non-adaptive r-requesters Q
(3.) and, all models (6,) produced by (A, A, Q) on any Do E X have
S a.
We judge the benefit of data deletion based on the computation saving that A offers over A per request. That is, if we want err((), D.) S how large is Cost(A) A) compared to Cost(A). Note that a should ideally be the optimal excess risk attainable under the (g, )-DD constraint. We remark that one may use any reasonable measure of utility in the third constraint, such as population risk instead of excess empirical risk.
for all i > O, where θ; is trained from scratch by A(D,),
DATA DELETION USING NOISY GRADIENT DESCENT
This section proposes a simple and effective data-deletion solution based on Noisy-GD Algorithm Our proposed approach falls under the Descent- Deleee framework proposed by Neel et al. (202)
wherein, after each deletion request u; we run Noisy-GD starting from the previous model θ and perform a small number of gradient descent steps over records in the modified database D,
D o us sufficient to ensure that the information about the deleted records is reduced within desired bound in the subsequent model é, Formally, our data-deletion solution is defined as follows. Definition 5.1 delat-ee based on Noisy-GDi GDD). Let space of model parameters be O = Rd. Our learning algorithm Ao (Dn) = Noisy-GD(DA, Oo, Kx) runs Noisy-GD algorithm for KA iterations to generate the first learned model θ, on the input database Do E X", with Oo sampled from weight initialization distribution P. Our data-deletion algorithm AD Ug ②;-1) Moisy-GD((,,111 u, ④, KX) processes edit request i, E uu by running K3 iterations of Noisy-Gi algorithm on the updated database D; = D;-1 o U, to generate the updated model θ from the current model θ E IRd.
For this setup, (ANoisy-GD, AN)) satisfies objectives (1.), (2.), and (3.) as stated in the problem definition above and analyze the computational savings of using ANoccy- GD over A GD in terms of the gradient complexity n A Kx).
objective is to provide conditions under which the algorithm pair
7

---

Under review as a conference paper at ICLR 2023
5.1
AND ACCURACY GUARANTEES UNDER CONVEXITY
We give the following guarantee for pair (ANoisy-GD, ANoisy-GD) under convexity of loss E(0; x). Theorem (Accuracy, privacy, deletion, and computation tradeoffs). Let constants X, B, L > Let the loss function L(0; be twice
> 1, and 0 < Edd Σ Edp- Define constant K X differentiable, convex, L-Lipschitz, and B-smooth, the regularizer be r(0) 3/2 |101 If the learning 4gL2
A+8
rate be 1 2(2+3)' the gradient noise variance is o² Xeagna and the weight initialization distribution is = N (0. X(1-nA/211a) then
(1.) both A Noisy. GD and À GD Edp PoPPe for any KA K 2 20,
(2.) pair ( (ANoisy GD, AN) satisfies (g, Eda) daad-ddaa-deletioo all non-adaptive r-requesters
Edp
if KA 2 4n:oo
(9)
Edd
(3.) and all models in (0i)s20 produced by (ANoisy-GD. Got Q) on any Du Xm, where any r-requester, have an excess empirical risk err( D;) O Edp
"dppn
and Kx 2 4n log max 5N,, Sedp r2
if KA 2 4o
qdl S (10)
4qd
Proof of Theorem 6 can be found in Appendix G,4
Our utility upper bound for data-deletion matches the theoretical lower bound of 57 (1, उमय in BBsssily al. (2144) for the best attainable utility of (s, -DP algorithms on Lipschitz, smooth, strongly-convex loss functions Thus, our data-deletion algorithm, ANoisy-GD- incurs no additional cost in utility but saves substantial computation costs. Our data-deletion algorithm offers
putation saving of Q(n log ( "iiin( "V Edd }) per request while guaranteeing privacy, deletion, and optimal utility and without unsafe internal data structures. This saving better than all existing unlearning algorithms literature that know of, and present detailed comparison in Table
Also, observe that for satisfying (g. -RDD and (g, (d)aaaaadatteeeele -data-deletion for non-adaptive r- requesters, the number of iterations K needed is independent of the size, r, of the deletion batch, depending solely on the ratio Sud, However, the number of iterations required for ensuring optimal utility with differential privacy grows with As such, we highlight that when deletion batches are sufficiently large, i.e., 2 data-deletion for free, thus demonstrating synergy between privacy and data deletion.
Exp
gd
ensuring optimal utility under (q, Rap) results in (g. Saa)-
Eaa
5.2 PATA-DELETION AND UTILITY GUARANTEES UNDER NON-CONVEXITY
We give the following guarantee for pair (ANoixy-GD. ANoisy-GD) under non-convexity of loss ((f:x). Theorem 7 (Accuracy, privacy, deletion, and computation tradeoffs). Let constants X, 3, L, 02, > q, B > and 0 Edd S Edp < d. Let the loss function L(0; x) be x² B))(B) -bounded, L-Lipschitz and B-smooth, the regularizer be r(0) = |101 and the weight initialization distribution be N (1a). Then,
(1.) both A Noisy-Gr GD and A Go (4, (dpp RRDP
P for any 1j 2 0 and any KA K2 2 if
qI2
max KA, Kx),
(11)
Edp??
'Recall from Remark I that (g. Sap]-RDP implies (s, -DP for q log(1/6) and Eap e/2. When
O(log(1/8)) evaluate that 9 O log (/6)/1))
Edp
8

---

Under review as a conference paper at ICLR 2023
Table Comparison of the computation savings in gradient complexity per edit request along with requirement of secret states with prior unlearning algorithms. For a fair comparison, we require that each of them satisfy an (e, d)daaa--delliio guarantee (ignoring the statelessness requirement) and have the same excess empirical risk bound. Edit requests are non-adaptive and modify n-sized databases. The models' dimension is d. We assume loss E(O; x) to be convex, 1-Lipschitz, and -sm)osh, and L2 regularization constant to be (1)..
record
Requires secret states?
Compute savings for ith edit
Unlearning Algorithm
Noisy-m-A-SGD [Thm. UUlah et al.
2021 ]
No
Perturbed-GD [Thm. 9,
Neel et al.
2021
Yes
Ω
log
va
Perturbed-GDD [Thm. 28, Neel et al.
2021
No
Ω
log
en
Top (id)
No [Thm. 6 Ours]
No
Ω
log min
n1, En
Vd
(2.) pair Go A Noksy-GD satisfy (g, (aaaa-ata--dlleee under all non-adaptive r-requesters for any 0² 0, if learning rate is 17 S
dead
and number of iterations satisfy
B144B(
2B Xm
[glog(B) Edd
2B xn
log(B) (B)
KA Z
log
KA 2 KA
log
(12)
( + T log (B(
(3.) and all models sequence (0,)220 output by (ANoisy-OD: Nooyy-GD: 2) on any Do X",
where Q is an r-requester, satisfy er(@@; Ō in and are equalities.
dg
gead when inequalities
Edp
Eáp
Proof of Theorem 7 can be found in Appendix G.5
The Rényi DP result in (1.) is restatement
of Abadi et al. 20166, Theorem 1) (discussed further in Appendix G.3 We prove the deletion and utility results in (2.) and (3.) by building recent rapid convergence results for Noisy-GD by /eempala & Wibisono (2019): Chewi et al. (021). Specifically, we show bounds on Rényi divergence of generated models O w.r.t. Gibbs distribution r((;;) xx exp( (op(-L) for all 2 0.
Under non-convexity, all prior works deletion have focused on empirical analysis for utility. As far as we know, we are the first to provide utility guarantees in this setting. Moreover, our non-convex utility bound exceeds the optimal prreacypreserving utility under convexity by only factor of (
gEad
which becomes small for large databases or small deletion to privacy budget ratio.
Edp
Also, observe a strict computational benefit in using ANoisy-GD whenever the fraction of edited records in single update request satisfies S 1/2 -iid In the deletion regime where Ead log /44 relying on ANDisyCUD rather than retraining with ANoisy-UD is 2(dn log ") cheaper.
Remark 4. The assumption that E(0; x) is L-Lipschitz in both Theorems 0 7 can be removed if gradients Ve(e, xx: computed in step 2 of Algorithm Mare clipped to L (discussed in Appendix C
6 CONCLUSIONS
We showed that unlearning guarantees are an unsuitable data deletion measure in the online setting of adaptive edit requests and proposed a proper notion data deletion in line with the "right to be forgotten." We also showed that differential privacy is necessary for data deletion when requests are adaptive and proved a reduction from secure deletion under non-adaptive requests to adaptive requests under DP. Our theoretical results on Noisy-GD based data-deletion, for both convex and non-convex losses, show a substantial computation saving over retraining with a reliable deletion guarantee and no additional cost in utility.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Martin Abadi, Andy Chu, lan Goodfellow, Brendan McMahan, llya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC conference on computer and communications security, pp. 308-318, 2016.
Dominique Bakry, Ivan Gentil, Michel Ledoux, et al. Analysis and geometry of Markov diffusion operators, volume 103. Springer, 2014.
Raef Bassily, Adam Smith, and Abhradeep Thakurta. Private empirical risk minimization: Efficient algorithms and tight error bounds. In 2014 IEEE 55th Annual Symposium on Foundations of Computer Science, pp. 464-473. IEEE, 2014.
Sergey G Bobkov. On isoperimetric constants for log-coneave probability distributions. In Geometric aspects of functional analysis, pp. 81-88. Springer, 2007.
Lucas Bourtoule, Varun Chandrasekaran, Christopher A Choquette-Chov Hengrui Jia, Adelin Travers, Baiwu Zhang, David Lie, and Nicolas Papernot. Machine unlearning. In 2021 IEEE Symposium on Security and Privacy (SP), pp. 141-159. IEEE, 2021.
California Consumer Privacy Act. Title 1.81.5, california consumer privacy act of 2018 [1798.100-
199.1090.. 2018.
Yinzhi Cao and Junfeng Yang. Towards making systems forget with machine unlearning. In 2015 IEEE Symposium Security and Privacy, pp. 463-480. IEEE, 2015.
Nicholas Carlini, Chang Liu, Úlfar Erlingsson, Jernej Kos, and Dawn Song. The secret sharer: Evaluating and testing unintended memorization in neural networks. In 28th USENIX Security Symposium (USENIX Security 19). pp. 267-284, 2019.
Min Chen, Zhikun Zhang, Tianhao Wang, Michael Backes, Mathias Humbert, and Yang Zhang. When machine unlearning jeopardizes privacy. In Proceedings the 2021 ACM SIGSAC Conference Computer and Communications Security, pp. 896-911 2021.
Sinho Chewi, Murat A Erdogdu, Mufan Bill Li, Ruoqi Shen, and Matthew Zhang. Analysis of langevin monte carlo from poincar'," log-sobolev. arXiv preprint arXiv:2112.1266: 2021.
Rishay Chourasia, Jiayuan Ye, and Reza Shokri. Differential privacy dynamics of langevin diffusion and noisy gradient descent. Advances in Neural Information Processing Systems, 34, 2021.
Monroe D Donsker and SR Srinivasa Varadhan. Asymptotic evaluation of certain markov process expectations for large time. Communications on pure and applied mathematics, 36(2):183-212. 1983.
Cynthia Dwork, Aaron Roth, et al. The algorithmic foundations of differential privacy. Found. Trends Theor: Comput. Sci., 9(3-4):211 1-707, 2014.
Matt Fredrikson, Somesh Jha, and Thomas Ristenpart. Model inversion attacks that exploit confidence information and basic countermeasures. In Proceedings of the 22nd ACM SIGSAC conference on computer and communications security, pp. 1322-1333, 2015.
General Data Protection Regulation. Regulation (EU) 201 2016/679 the European parliament and of the council of 27 April 2016, 2016.
Antonio Ginart, Melody Guan, Gregory Valiant, and James Y Zou. Making ai forget you: Data deletion in machine learning. Advances in Neural Information Processing Systems, 32, 2019.
Leonard Gross. Logarithmic sobolev inequalities. American Journal of Mathematics, 97(4):0061- 1083, 1975.
Chuan Guo, Tom Goldstein, Awni Hannun, and Laurens Van Der Maaten. Certified data removal from machine learning models. arXiv preprint 1rXiv:191 1,03030, 2019.
Varun Gupta, Christopher Jung, Seth Neel, Aaron Roth, Saced Sharifi- Malifi--alvjjjrddi, and Chris Waites. Adaptive machine unlearning. Advances in Neural Information Processing Systems, 34, 2021.
10

---

Under review as a conference paper at ICLR 2023
Richard Holley and Daniel W Stroock. Logarithmic sobolev inequalities and stochastic ising models. 1986.
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, pp. 2008-2016. PMLR. 2021.
Solomon Kullback and Richard A Leibler. On information and sufficiency. The annals of mathemati- cal statisties, 22(1):79--)) 86, 1951.
Michel Ledoux. The concentration of measure phenomenon. Number 89, American Mathematical Soc., 2001.
Ilya Mironov. Rényi differential privacy. In 2017 IEEE 30th computer foundationn symposium (CSF), pp. 263-275. IEEE, 2017.
Seth Neel, Aaron Roth, and Saeed Sharifi-Malvajert Descent-to-delete: Gradient- methods for machine unlearning. In Algorithmic Learning Theory, pp. 931-962. PMLR, 2021.
Aleš Nekvinda and Luděk Zajiček. A simple proof of the rademacher theorem. Časopis pro pēstování matematiky, 13344)3337-31, 1988.
Yurii Nesterov. Introductory lectures on convex optimization: A basic course, volume 87. Springer Science & Business Media, 2003.
Felix Otto and Cédric Villani. Generalization of an inequality by talagrand and links with the logarithmic sobolev inequality. Journal of Functional Analysis, 173(2)361-4400, 2000.
Alfréd Rényi et al. On measures of entropy and information. In Proceedings of the fourth Berkeley symposium on mathematical statistics and prohability, volume 1. Berkeley, California, USA, 1961.
Gareth Roberts and Richard L Tweedie. Exponential convergence langevin distributions and their discrete approximations. Bernoulli, pp. 341-3633 1996.
Ayush Sekhari, Jayadev Acharya, Gautam Kamath, and Ananda Theertha Suresh. Remember what you want to forget: Algorithms for machine unlearning. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan (eds.). Advances in Neural Information Processing Systems, volume 34, pp. 18075-18086. Curran Associates, Inc., 2021.
Reza Shokri, Marco Stronati, Congzheng Song, and Vitaly Shmatikov. Membership inference attacks against machine learning models. In 2017 IEEE symposium on security and privacy (SP), pp. 3-18. IEEE, 2017.
Enayat Ullah, Tung Mai, Anup Rao, Ryan A Rossi, and Raman Arora. Machine unlearning via algorithmic stability. In Conference on Learning Theory, pp. 4126-4142. PMLR, 2021.
Tim Van Erven and Peter Harremos. Rényi divergence and kullback-leibler divergence. IEEE Transactions on Information Theory, 6077):377--3800, 2014.
Leonid Nisonovich Vaserstein. Markov processes over denumerable products of spaces, describing large systems of automata. Problemy Peredachi Informatsii, 5(3):64-72, 1969.
Santosh Vempala and Andre Wibisono. Rapid convergence of the unadjusted langevin algorithm: Isoperimetry suffices. Advances in neural information processing systems, 32, 2019.
Yu-Xiang Wang, Stephen Fienberg, and Alex Smola. Privacy for free: Posterior sampling and stochastic gradient monte carlo. In International Conference on Machine Learning, pp. 2493-2502. PMLR, 2015.
11

---

Under review as a conference paper at ICLR 2023
Appendix
Table of Contents
Table of Notations
13
B Calculus Refresher
14
Loss Function Properties
14
Divergence measures and their properties
E Proofs for Section
17
E.1 Unsoundness and Incompleteness of Otfline Unlearning Definitions
19
F Proofs for Section
20
F.1 Contrasting Our Reduction Theorem S
with Gupta et al. (2021) Results
23
Additional Preliminaries and Proofs for Section
24
Langevin Diffusion Markov Semigroups
24
Isoperimerric Inequalities and Their Properties
25
G.3
(Rényi) Differential Privacy Guarantees Noisy-Gi)
26
G
4
Proots for Subsection 5.1
27
G.5
Proofs for Subsection
36
12

---

Under review as a conference paper at ICLR 2023
A
TABLE OF NOTATIONS
Table Symbol reference
Symbol
Meaning
O
Arbitrary model parameter space,
Space of publishable outcomes.
d
Dimension of model parameters.
Rd
Space of d-dimensional model parameters.
n
Database size.
Data universe and Domain of all datasets of size n.
V,,,
Arbitrary distributions on O or on R4 An edit requester.
Q
r.p
Number of records replaced per edit and number of releases observable by requester. Space of singular and batched replacement edits in [n] x X.
u,
U4 Us
Arbitrary edit request, jth edit request Li" and its random variable.
D,D,
An example database and database after jth update. Singular data records from universe A' Step size learning rate in Noisy-GD.
x,y
Variance scaling used in weight initialization distribution gradient noise. Twice continuously differentiable loss function on models in Rd
x(0;x)
r(0)
L2 regularizer X ||01|/ /011//2.
((0), (0)
Arbitrary optimization objective and an r(0) regularized objective on D over E(0; x). Excess empirical risk of random model @ over objective LD.
@r)(
T(D)
An mapping from X to distributions on Rd, sometimes distributions are Gibbs.
AD
Normalization constant of the Gibbs distribution T(D).
T
A distribution independent of record deleted by request on database D;-1-
Tr
A map over Rd.
P
Weight initialization distribution for Noisy-GD.
v'
Vector fields d
D. 0b.
Risk minimizer for Lo and LD.- Order of Rényi divergence.
g
Edp: Edd
Differential privacy budget and data-deletion budget in q-Rényi divergence.
8
Parameters for DP-like indistinguishabiiity.
A, GN
Learning algorithm and Noisy-GD based learning algorithm respectively.
A, ANoisy-GD
Data-deletion algorithm and Noisy-GD based data-deletion algorithm respectively. Number of learning and data-deletion iterations in Noisy-GD. Index of a Noisy-GD iteration and continuous time variable for tracing diffusions. Random variables representing the iteration k parameter distribution in Noisy-GD.
KA. K
k
Onk O
O, O
Random variables representing the time distribution of tracing diffusion for Noisy-GD. Probability density for θ, Ø,. d-dimensional identity matrix.
La
Z, Zk. Z%
Random variables taken from N (0, Tz)- Two independent Weiner process. L2 regularizer constant and smoothness, boundedness, and Lipschitzness constants. Operator that clips vectors in Rd to magnitude of Rényi divergence of distribution of w.r.t'v
dZ,, dZ,
2,8, B.
constttn
C-ipz())
(vllv))
Eg (vllv))
9 moment of likelihood ratio r.v. between v and v'.
I(v[lv) (vllv)
Fisher and RéRény Information of distribution of w.r.t v'. Wasserstein distance between distribution v and v'. Kullback Leibler divergence of distribution w.r.t. v
We (v.
KL (vllv))))
P*
Markov semigroup, its infintesimal generator, and its Fokker-Plande operator. Entropy of function f² under any arbitrary distribution π.
(ft)
H(.)
Differential entropy
distribution.
LS(C)
Log-sobolev inequality with constant c.
proxg
Proxmial mapping for objective L.
13

---

Under review as a conference paper at ICLR 2023
B CALCULUS REFRESHER
Given a twice continuously differentiable function : - IR, where is a closed subset of R2 its gradient VL: O IR is the vector of partial derivatives
aC(0)
VL(0)
(13)
00,
002
Its Hessian 22c: Rdxd is the matrix of second partial derivatives
88 (()
V2C(0)=
(14)
00,0,
15i.gd
Its Laplacian : - R is the trace of its Hessian L i.e.,
AC = Tr (v2 ((0))
(15)
Given differentiable vector field (V1, va) 0 - R.d its divergence div (v) :0 + is
div (V) dv;(6)
(16)
00,
Some identities that would rely on:
1. Divergence of gradient is the Laplacian, i.e.,
div (V) = 0 AC 00?
(17)
2. For any function f: + R and a vector field v O - Rd with sufficiently fast decay at the border of O,
1 (v(0), ((()) = - (dv (v))())d
(18)
3. For any two functions f.g O + R. out of which atleast for one the gradient decays sufficinetly fast at the border of O, the following also holds.
1. f(0)
(V)()), Vg(()) do / ((0))f(0)d).
(19)
4. Based on Young's inequality, for two vector fields v1, V2 O + Rd, and any a, b e R such that ab 1, the following inequality holds.
1
(V1, v2) (0) - 2a
10)10)) + 26 (0))
(20)
Wherever it is clear, we would drop (0) for brevity. For example, would represent div (v) (0) as only div (v).
C LOSS FUNCTION PROPERTIES
In this section, we provide the formal definition of various properties that we assume in the paper. Let e(0) Rdd x X IR be loss function on Rd for any record x E X.
Definition C.1 (Lipschitzness). A function E(0; x) is said to be L Lipschitz continuous if all 0, 0' E Rd and any X.
[(0;x) e(0'; x) < L10 0'112-
(21)
[(0xx) is differentiable, then it is T--lipschizz if and only if (((0;) S for all 0 Rd.
14

---

Under review as a conference paper at ICLR 2023
Definition C.2 (Boundedness). A function E(0:x) is said to be B-bounded if for all x E X, its output takes values in range [-B,B) Bl.
Definition C.3 (Convexity). A continuous differential function E(0; x) is said to be convex for all 0, 0,0'= E Rd and x E X, 2(0';x)= 2 R(0;x) (Ve(0:)) 0),
(22)
and is said be X-strongly convex if
x0) 2 [(0:x) + (V((0:)), 0' -) + 110 - -
(23)
Theorem 8 ([Nesterov)
Theorem 2.1.4)). A twice continuously differentiable function L(O: x) is convex if and only for all B R and x X, its hessian matrix (2; x) is positive semidefinite, Le., V=e x) & 0 and is X-strongly convex if its hessian matrix satisfies e x) i Alla-
2003
Definition C.4 (Smoothness). A continuously differentiable fanction E(0; x) is said to be 3-Smooth for all 0 8' E Rd and x E X.
[V((0;x) Ve(0';x))l S -311--0'11-
(24)
Theorem 9 (Nesteroy 2003
Theorem 2.1.6)). A hvice continuously differentiable convex function x(0:x) is 3-smooth if and only for all f E Hd and x E X,
v²((0:x) $ Bld-
(25)
C.O.1 EFFECT OF GRADIENT CLIPPING
First order optimization methods on continuously differentiable loss function e(0; x) over a database D E X with gradient clipping Clip,, (v) = v/ max (1.
livllz] is equivalent to optimizing
L
(0) = D
Σ {(0;x) + r(0), XED
(26)
where x() is surrogate loss function that satisfies vi(0;x) loss function inherits convexity, boundedness, and smoothness properties of E(O; x), as shown below. Lemma 10 (Gradient clipping retains convexity). (f;; x) is twice continuously differentiable convex function for every x E Red, then surrogate loss (0;; x) resulting from gradient clipping is also convex for every x E Rdd
This surrogate
Proof. Note that the clip operation Clip,, (v) is a closed-fore forsed--ormmo solution of the orthogonal projection onto closed ball of radius L and centered around origin, i.c.
Clip (v) arg min v'll2.
(27)
||v'
By properties of orthogonal projections on closed convex sets, for every v, v' E Id, if and only if || S L.
(v' Clip - S Therefore, for any E Rd, and x E X, we have
(28)
Vē(0 + hv: ve(0: ve(0:x) vē(0:x)) 0. VV((0x) ve( x); Ve(0 + hv; Vē(0 hv; x)) < 0,
(29)
(30)
for all unit vectors v E Rd and magnitude h > For the directional derivative of vector field Vi(0;x)
along v, defined as V. V,(0; x) = lim /E(++Avx)) V[(0xx) the above two inequalities imply
V V((0x)) vl(0:)) vl(0:x)) O,
(31)
for all Therefore, when Vε(0;x) # V x)), we must have <2((0;x) = -.. And, when Ve(0: x) = vē(0: x), gradients aren't clipped, which implies the rate of change of e(0; x) along any direction
Vē(0 + hv;x) - ve(l:
V. vl(0;x) = lim
h
V v2e(0:x)V 3h > S.t. ve(0 + hV;x) ve(o + +hv;x) 0.
0
otherwise
15

---

Under review as a conference paper at ICLR 2023
Lemma 11 (Gradient clipping retains boundedness). If ((0:x) is continuously differentiable and B B-bounded function for every x E X. then the surrogate loss E(O; x) resulting from gradient clipping is also B-bounded.
Proof. Since L(0:x) is continuously differentiable, its B-boundedness implies path integral of Vε(0; x) along any curve between 8, 8' E R is less than 2B. Since Clip, (-) operation clips the gradient magnitude, the path integral of Vε(0;x) is also less than 2B. That is, the maximum and minimum values that E(0; x) takes differ no more than 2B. By adjusting the constant of path integral, we can always ensure E(0; x) takes values in range [- B, B] without affecting first order optimization algorithms.
Q
Lemma 12 (Gradient clipping retains smoothness). E(O; x) is a continuously differentiable and 3-smooth function for every E RR, then surrogate loss L x) resulting from gradient clipping is also B-smooth for every x E Rdd
Proof. Note that the gradient clipping operation is equivalent to orthogonal projection opera- tion into a ball of radius L, i.e. (V)p)(v) = arg min,, illv' vvllz v E R || S L}. Since orthogonal projection onto a closed convex set is a 1-Lipschitz operation, for any 0, 8' E R
vē(0;x) vē(0', x))22 [Ve(0; x) v 3 110 0
(32)
Additionally, the surrogate loss L(0; x) is twice differentiable almost everywhere if ((0;x) is smooth, which follows from the following Rademacher's Theorem.
Theorem 13 (Rademacher's Theorem (Nekvinda & Zajiček 1988)) If R" - R Lipschitz continuous, then is differentiable almost everywhere in I
All our results in Section 5 rely on the above four properties on losses and therefore apply with gradient clipping instead of the Lipschitzness assumption.
D DIVERGENCE MEASURES AND THEIR PROPERTIES
Let θ, O' E O be two random variables with probability measures v. respectively. We abuse the notataions to denote respective probability densities with v, v' as well. We say that is absolutely continuous with respect to y' (denoted by v < v') if for all measurable sets O C O, v(O) 0 whenever vO) = 0.
Definition D.1 ((e, iiniiiiiiiitiinuuhabbllyyy indistinguishable for all O C O,
Dwork al. 2014)). We say v and v' are (s,
O E 0 < E P O E 0 and @'~xx'
P
O
E
S ef P 10 0
(33)
In this paper, we measure indistinguishabiliyy in terms of Rényi divergence.
Definition D.2 (Rényi divergence (Rényi et al. 1961)). Rényi divergence of v w.r.. v' of order q > 1 is defined as
[
v(0)
Ry (vllv')
q q-1 log Eg (vllv), where Eg (vllv)) = E BaY (()))
(34)
when v is absolutely continuous w.r.. v' (denoted as v < v'). If & we'll say Rg (vllv) = We abuse the notation R. (0llO') to denote divergence R. (vlly') between the measures of 0,
bound on Rényi divergence implies a one-directional (c. iiiiiiiistinnussaabllttyy as described below.
Theorem 14 (Conversion theorem of Rényi divergence (Mironov) 2017]] Proposition 3)), Let q > 1 and & > O. If distributions v' satisfy R. (vl[v') < Co. then for any O C O,
IP @wy
10 E 0 S e IP @
10' E #/0 +
(35)
for Eo
log 1/8 q and any 0 <8<1
16

---

Under review as a conference paper at ICLR 2023
We the following properties of Rényi divergence in some of our proofs.
Theorem 15 (Mononicity of Rényi divergence (Mironov 2017
Proposition 9)), For 1 S and arbitrary probability measures and v' over Rgo [v]''' I Rg (vllv'.
Theorem 16 (Rényi composition (Mironov 2017 Proposition 1)). A1. .A are randomized
algorithms satisfying, respectively, (q,E1)-RDr :g. - then their composed mechanism A (D)) (g,8)
defined as (A1(D):
+ex)-RDP. Moreover, ith algorithm can be chosen
on the basis of the oulputs of algorithms
Proposition 12)). For Theorem 17 (Weak triangle inequality of Rényi divergence (Mironoy 2017
any distribution on O, the Rényi divergence of w.r.t. v sattifies the following weak triangle inequality:
R2 (v/lv') S R, (vllp) Roc (pllv))
(36)
Another popular notion of information divergence is the Leibler divergence.
Definition D.3 (Kullback-eiilee divergence (Kullback & Leibler 1951)). Kullback-Leibler (KL)
divergence KL (vllv') of w.r.t. v' is defined as
Y(0) v(())
KL = E log
(37)
Rényi divergence generalizes Kullback-Leibler divergence (Van Erven & Harremos) 2014) as lim Rg (vllv') = KL (vllv').
Some other divergence notions that we rely on are the following.
Definition D.4 (Wasserstein distance |aaserstein
1969
Wasserstein distance between v and v is
Wa (v, v = inf E 0,8'111
|| - 0'12
(38)
where 11 is any joint distribution on O x O with and v' as its marginal distributions.
Definition D.5 (Relative Fisher information (Otto Villani 2000)). If < and y is differen- tiable, then relative Fisher information of with respect v defined
v(O) !
T [(vllv) = E
V log
(39)
Definition D.6 (Relative Rényi information (Vempala & Wibisono 2019)). Let petg>i 1. If < v and b is differentiable, then relative Rényi information of with respect v' defined as
(vllv)
4 g2 Bmrc
E
v(0) (
9/2 27
[ Y())
9-2 (())
4
v()
(40)
Anvv
v(0)
E PROOFS FOR SECTION 3
Theorem For every > O, there exists a pair (A, A) of algorithms that satisfy (s. 0)-unlearning under publish function foub such that for all non-adaptive 1-requesters Q, their exists an adversary that can correctly infer the identity of record deleted at any arbitrary edit step 2 1 by observing only the post-edit releases oz = (0:. ...)
Proof. For query h X + {0. 1}, consider the task of learning the count over database that is being edited online by a non- non-adaptive 1-requester Q. Since Q is non-adaptive by assumption, is equivalent the entire edit. sequence {2 being fixed before interaction. We design algorithm pair (A, A) for this task with secret model space being O = N and published outcome space being Φ = R, with the publish function being faub((a, b, c)) = a-b/c- - (2) (with the convention that 0). any step 0. our internal model é; = (cnt,, del,, i) encodes the current count of h on database D,, the count of on records previously deleted by ugi, and the current step index i. Our learning algorithm initializes the secret model as é, A(Do) (ExeP, 1xx),, 0, 0).
b/c = 0 b
17

---

Under review as a conference paper at ICLR 2023
and, for an edit request i, {(idd y:) our algorithm À updates the secret model θ;- - A following the rule
; ADi Us θ,11) (cnt,, del;, i) where cnt; cnt,-1 h(y;) h(D,-1(ind,)),
del; del, + (ind)](ind))).
Note that Vi 2 1, A, def del.// / E [0, 1]. Therefore, from properties of Laplace mechanism (Dwork et al. 2014), it is straightforward to see that for all 2 1,
Jpab(A(D (.1),,,)))
Σ M(x) +
Lap
xED.
s.0
Σ
h(x)
Lap (1)
Spub Spub(A(22 (A(D.)).
XED,
Hence, A is an (e,0)unneaamiin algorithm for A under fpub.
To show that an adversary can still infer the identity of record deleted by update u, (ind,, )). consider database Di_, that differs from D:-1 only at index ind, such that Let random variable sequences Φ2: and o'y, denote the releases by A in the scenarios that the (i - 1)th database was D; and D respectively. The divergence between these two random variable sequences reflect the capacity of any adversary to infer the record deleted by u4. Since, we have identical databases after и,, i.e. Dj-1 u Dj-1 my for all 1 j 2 i, note that both 6, and df are independent Laplace distributions with shift of exactly j units. Therefore.
h(D [ind,]) # h(D,-1(ind))
IP [0 EO]
plos [O]]
max log O
max log Ck
log e/ 00.
P 10 O,] ==i
P
0 EO
Theorem 2 There exists pair (A, A) of algorithms that satisfy (0, ceaadaptive-unleaniiti for an identity publish function (f) = 0 such that by designing a 1-adaptive 1-requester Q. an adversary, even with no access Q's interaction transcript, can infer the identity of record deleted at any arbitrary edit step i 3 with probability at-least (1/2)² " from the post-edit release di.
Proof. Let data universe be X, the internal state space O, and publishable outcome space t be IR. Consider the task releasing a sequence of medians using function med R - E in the online setting when the initial database Do E X is being modified by some adaptive requester Q. Given a database D E X"m, our learning algorithm is defined as A(D) = med(D). For an arbitrary edit request L",, unlearning algorithm is defined A(D, u. .) med(D u). Let the publish function frub O + be an identity function, i.e. fpuh (f)
For any initial database Dn E Xn and adaptive sequence (u))21 generated by any oc-adaptive 1-requester Q, note that
(A u, )) fmmb for all i i 1 and any E O.
(41)
Therefore, A is (0, adddappivee unlearning algorithm for under fpub-
Now suppose that is odd and Do consists of unique entries. W.I.O.G. assume that the median record med(Do) is at index ind and its owner will be delcting it at step i by sending a non-adaptive edit request u4 { {(ind". y) } such that y * med(Do). We design the following 1-adaptive 1-requester Q that sends edit requests in the first 1 steps to ensure with high probability that the published outcome step i remains the deleted record, i.e., med(D.) med(Do):
( U1, U2 ... ,....,,g-.. .)--)) (ind, do)} V <j<í,
(42)
where ind, is randomly sampled from [n] \ (ind) ... ind,-1) without replacement. Note that by the end of interaction, Q replaces le-lt 2 unique records in Dp with Φo med(Do). If one of
18

---

Under review as a conference paper at ICLR 2023
those original records larger than med(Do) and another was smaller than (ed, then it is guaranteed that (e,) = med(Do). Therefore, (De) = me)(Do)) is at-least
P Bind', ind" {indl, .ind,-1) } s.t. Do [ind'] < Do [indd" Dolind"]]
[m1/2) i-22 (1-²² 2 1
1 2
2 1 1 2
E.1 UNSOUNDNESS AND INCOMPLETENES, OF OFFLINE UNLEARNING DEFINITIONS
In this subsection, we show that our criticisms on both soundness and completeness of unlearning notions in Section 3 also apply to the one-stage unlearning definitions of Guo et al. (2019); Sekhari ct al. (021); Ginart et al. (2019).
Definition E.1 ((E, 8) certiffed removal (Guo et al., 2019)). A removal mechanism A performs
(e, 5) certified removal for learning algorithm A if for all databases 'D C X and deletion subset
A(D, S. A(D))
A(D S).
(43)
Definition F,2 ((e, 8) unleerning (Sekhari al. 2021)). For all DD X of size and deletion subset S C. DD such that [S| I m, a learning algorithm A and an unlearning algorithm A is (e, -unleerrnng if
2.6 A(T(D) (5),
A(T(D).
(44)
where Ø denotes the empty set and T(D) denotes the data statistics available to A regarding D. Definition E.3 (Data Deletion Operation Ginart al. (2019)). Fix any dataset D X and learning
algorithm A. Operation A is a deletion operation for A A(D, A(D \ S) for any set S C D selected independently of AD).
Unsoundness. Definitions E.I and B.2 make no assumptions about dependence between the deletion request S and the learned model ADD So, request S can depend on A(D). This dependence is common in the real world; for example, user deletes her information if she doesn' like what model A(D) reveals about her. We present the following construction along the same lines as our proof in Theorem to show that Definitions
F.1 and F.2 are unsound.
For the universe of records X' algorithms:
(-2, 1,,,,), consider the following learning and unlearning
A(D) Σ x, and A(D,S,A(D)
Σ x.
(45)
XED
X
Note that for any D C and any S C D. the above algorithm pair (A, A) satisfies Defini- tions E. E.2 and E.3
for = 8 = 0 and T(D) = D. Suppose the adversary is aware that the following dependence holds between the learned model A(D) and deletion request
S= {x < 0 Vx EX
if A(D) < O, otherwise.
(46)
(x 0: Vx E 2)
Consider two neighbouring databases D_1 (-2.-1 and D1 (-2, (f-,1,22, above dependence, an adversary can determine whether D = DD1 or D = D2 by looking only A(D, S, (D)). This because if D = DD11, then the observation after unlearning
Knowing the
2, and D= D1, the observation after unlearning is 22. So, even though (A,A) satisfies the guarantees of
Guo et al. (2019) and (Sekhari et al. (2021). , blatantly reveals the identity (-1 or 1) of a deleted record to adversary observing only the post-deletion release.
Note that Definition B3 assumes that the requests S is selected independently of the learned model their definition is sound. We remark, however, that algorithms satisfying their definitions cannot be trusted in settings where we expect some dependence between deletion requests and the learned models.
A(D). So, construction does not apply, keeping the possibility that
19

---

Under review as a conference paper at ICLR 2023
Incompleteness. Definitions E.1 E.2 and E.3 also incomplete. Consider unlearning algorithm A that outputs a fixed output X1 E if the deletion request = Ø and outputs another fixed output X2 E X' if the deletion request S * Ø. It is easy to that A is valid deletion algorithm as its output does not depend on the input database DD or the learned model A (D). However, note that A does not satisfy the unlearning Definition [F.2] for any learning algorithm A. And, for a learning algorithm (D) ExED X, one can also verify that the pair (A, A) does not satisfy Definitions E.1
and either.
F PROOFS FOR SECTION 4
Theorem (Data-deletion Definition 4.1 is sound). If the algorithm pair A) satisfies (g, e)- data-deletion guarantee under all p-adaptive r-requesters, then even with the power of designing an p-adaptive r-requester that interacts with the curator before deletion of a target record at any step i L, any adversary observing only the post-deletion releases (9,, O.t1,"... has its membership inference advantage for inferring a deleted target bounded as
Adv(MI) < -ee 13/9
q [2(g 1)1
(47)
Proof. For an arbitrary step 2 1, suppose one of the replacement operations in the edit request u, Lt replaces record at index 'ind' from the database D,-1 with 'y'. In the worst case, this record [ind[in]] might have been there from the start, i.e. [ndind] = Do [ind], and influenced all the decisions of the adaptive requester Q in the edit steps 1, 1,..,, ; 1. To prove soundness, we need to show that if (A, A) satisfies (g, daddtda-dllenion then even in this worst-case scenario, no adaptive adversary can design a membership inference test MI(O), ..+1....) E {0, 1} that x) from the alternate x'} for any x, x' E X. That is, the advantage of any test MI, defined
can distinguish with high probability the null hypothesis Hg = (Do hypothesis H1 [Do [ind]
as
Adv def MI ...1.....) = 1 H - P [ 0:41,
.. = 1|H
(48)
must be small. Since after processing edit request u, the databases D;, Di+1. ... no longer contain the deleted record [ind] the data-processing inequality implies that future models θ i.2,,... cannot have more information about D Di-i that what is present in Ô, Therefore, any test MI(ê,, ...),...) has smaller advantage than the optimal test MI' E {0, J that only uses Ô,
Also, since (A, A) satisfy (g. daaat---elliio for any p-adaptive r-requester Q, we know from Definition 4.1 that there exists a mapping πíद such that for all D, E Xt,, the model Ô, generated by the interaction between (A, A, Q) on Do after ith edit satisfies R.g [f. (Do a (ind, y)) S c. As y) is identical under both hypothesis Hn and H1, we have R. ( ()) S
the database
for b E {0, 1}, where Ô क. (Do (ind, y)). From Rényi divergence to ( -n-iiiistinnuushhablliy conversion described in Remark [ we get
P MI (θ,) Ho
I <0'( MM 1] + 5, and
(49)
MI (θ) = 0] + 8, P MI (ê,) = 0 I c
(50)
where e'(8)= = log 1/6 for any 0 < 5 < 1. On adding the two inequalities, we get: 9-1
Adv(MII= S Adv(Mr') IP MI' (6.) 1|H1|] [MI = 1|H11
min b c-
+ 26
(e-
12(g - 1))²/0 -1
20

---

Under review as a conference paper at ICLR 2023
Theorem (DP is necessary for data-deletion). If learning algoritium A X - O is not (0. 60.6)-DP with respect to the replacement of a single record and deletion algorithm A X xu x O - O is not (0, DDPP with respect to the replacement of a single record that is not being deleted. then the pair (A, A) cannot satisfy (q, 6* (2)-data-deeletion under 1-adaptive 1-requester for any q > 1.
Proof. If A is not (0, 6)-DP with respect to replacement of a single record, then there exists pair of neighbouring databases D, D' such that
TV (A(D) = sup [P(A(D) E P PIA(D) 0) > 6. OEO
(51)
Similarly, if A is not (0, 6D-DP with respect to replacement of single record that is not being deleted, then there exists pair of databases D, D' and an edit request ù E Ut such that D o and D' ū are neighbouring and for all 0 E O, TV (A u, 0); A(D', à. 0))
sup IP [A(D, 0. E 0 - [A(D' 0, E EO] 8. (52)
OEO
Since TV distance is bounded from below in both cases, there exists tests Test, Test: O - {0, {0,1} such that
Test D,D') def P [Test(A(D)) 1] P (Test(A(D')) = 1] 8,
(53)
and for all 0 E O,
Adv Test; D, 4)
Test(A(D, a, 0)) = =1] -P Test(A A. 0)) 1 > 8.
(54)
Assume W.L.O.G. that ū replaces at index n and the edited databases D o u, D' u still differs at index Also assume that D. D' differs at index n.
Recall from Definition 4.1 that satisfying (q, 5% ddata-deeletio under 1-adaptive 1-requesters requires existence of a map oh X + O for each Q such that for all Do E X
Ry (A(Dn- Una θn- 1 (Do un)) s
8
(55)
2
To prove the theorem statement, we show that for a starting database Dp E (D, and an edit request u., that deletes the differing record in choices of Do at edit step n, there exists 1-adaptive 1-requester Q that sends adaptive edit requests "1,"." 1un11 in the first n - steps such that no map πT, exists that satisfies (55) for both choices of Do-
Consider the following construction of l-adaptive 1-requester Q that only observes the first model Ô, = ADo) and generates the edit requests (U1,".,,,,,) as follows:
(i, D(i)) Test((o)) = 1,
( u1, U2 ".. .4-1) =
(56)
(i, D'il)) otherwise.
This requester Q transforms any initial database Do to Dn D if the outcome Test(@p) = 1, otherwise to Dn-1 = D'. Consider an adversary that does not observe the interaction transcript (DeniMen)) but is interested in identifying whether Do was D or D'. The adversary gets to observe only the output é, = A(Dr-1, un. ó,-1) generated after processing the edit request un a. On this observation, the adversary runs the membership inference test MI(ê..) Test((,)). The membership inference advantage of MI is
Adv(MI: D. D') def TP [MI(Ó..) = 1.D D| -P [MI( 1/Do D
Σ P
@e.) 1/Test(@o) b] x P @est((O)= =b/Du D]
be be(0,1)
Σ P Te))(( = (o) b) x P Tes((Oo) b.D = DD]
bE(0.1)
(P |ess (...) = 1/D DJ Test O.,) = 1 D,, = D')) Adv(Test: D,D')
Ade(Test; D, ū) Adv(Test: D,D') 8²
21

---

Under review as a conference paper at ICLR 2023
So, it must be true that the total variation distance between On given Do D and Do- = DD is lower bounded as
TV (6n DO On 0x 6².
(57)
From triangle inequality of total variation distance, Pinsker's inequality, and monotonicity of Rényi divergence w.n.t. order 9, note that for random variable è O with any arbitrary distribution,
8² TV DAlpo-D;Onlan
S TV (OuIDo=D;0) 0) + TV (OnIDo-Di;
V KI. (0 ((0) + V 2
KL. (Omloo (6))
max Ruy (Oxlz0=Dr ()) R. (OaID0=D [6)}
This implies that for all random variables G, and q > 1,
max {Ry (A(D.-1. unn @ 6) Rg (A(Di-1, Un b, @o)) |
5t
(58)
2
But, to satisfy (g. - ddaataddelltio under 1-adaptive 1-requesters, there must exist mapping nh for which (55) must hold for both choices of Do D'). Since the random variable n. (Do u, is
identically distributed in our construction for both choices of Do E (D,D"), from (58 we have that no such map x can exist.
Theorem 5 (Reduction from Adaptive to Non-adaptive Data Deletion). an algorithm pair (A, A) satisfy (g. Ead)-dataaadee -ata-deeetioo under all non-adaptive r-requesters and (g. Edp)))RRenn -Rényi differential privacy, then it also satisfies (g. Ead + pEda) daae)ddda--eeetiii for all p-adaptive r-requesters.
Proof. To prove this theorem, we need show that for any p-adaptive r-requester Q, there exists construction for a map πT, xm O such that for all Do X², the sequence of model (θ:):20 generated by the interaction between (Q. A, A) on Du satisfies the following inequaltiy for all 2 1:
Rgg (A(D. un, 6._1) (D o find S Edd + pEdps for all us E lt and (ind, y) E u4.
(59)
Fix a database Dp E x2 and an edit request u, E L/". Let D/ E X" be a neighbouring database defined to be DD= Dn (ind, for an arbitrary replacement operation (ind, y) E 14. Given any p-adaptive r-requester Q. let (O,)zzu and (U:)221 be the sequence of released model and edit request random variables generated Q's interaction with (A, A) with inital database Dg. Similarly, let (0));20 and (U()221 be the corresponding sequences generated due to the interaction among (2, A, A) on D--
Since (A, is assumed to satisfy (q, Eda) (aad-data-dedle delat-de guarantee under non-adpative r-requesters. recall from Remark 3 that there exists mapping π x O such that for any fixed edit sequence def
(ui, U2, ".)),
Ry (
(DDo o usi)) s Ead
(60)
R (A(D) o Uzi us U.)lue ((D o U2r o u.)l $ Ead.
(61)
Note that since the replacement operation (ind, y) is part of the edit request u, have Do U' ii = D 0U u, Moreover, since the sequence U': of edit requests is generated by the interaction of (2, A, A) on D/- = Do (ind, u) and the ith edit request u; is fixed beforehand, we can define a valid construction of map π.? : x + O as per Definition 4.1 as follows:
T (Do (ind, y\) =((D' U' o u.)
(62)
22

---

Under review as a conference paper at ICLR 2023
For brevitly, let ④. ADo Uca u4 ④,-1), and @%, = nz (Du y)). For this construction, we prove the requisite bound in (59) as follows.
R4 (oul6)) s R2 (( U<>) (6 U22))
(Data processing inequality (Van Erven & Harremos 2014 Theorem 1)) Σ 8 vei
J(0, ues)² d0
log
J'(O, (,,,ucc))-10
(J & J' are joint PDFs of (Ó., U2{) & (6,,, U2)))
P PUCt = uzil"
Pê. Pê,lUc,=ue: (0)9
log
Pérl0',,uc (0) d8
P
[U< uci 9-1
P PlUct = u<r] 1
< log
9-6 exp((( 1)sda)
(From (61)
P 1U'z ucc
uci
Ead + R₂ (U's)
(0)t) ),.)) (8's,...,,8,,
S Ead + R2
(If Q sees outputs steps s sP)
Sdd + pd
(Via Rényi composition)
F.1 CONTRASTING OUR REDUCTION THEOREM 5 WITH GUPTA ET AL.. (2021)sS RESULTS
The recent work of Gupta et al. 2021), also studies adaptive data deletion and proves a reduction from adaptive unlearning guarantee non-adaptive unlearning guarantee in Definition 2.6 under differential privacy. We remark that the reduction Theorem 3.1 by Gupta et al. (2021) relies on DP with regards to a change in the description of learning/unleaniing algorithm' 's coins and not with regards to the standard replacement of records. In contrast, our Theorem 5 presents a reduction from adaptive to non-adaptive data-deletion guarantee under DP with respect to the standard replacement of records. We emphasize that these two Theorems are fundamentally different.
The adaptive unlearning definition of Gupta et al. (021)) is designed to ensure with a high prob- ability that no adaptive requester Q can force the output distribution of the unlearning algorithm A A(Di-1, uy i)) to diverge substantially from that of retraining algorithm A(D:). Such attack is possible stateful unlearning algorithms that rely on persistent structures that are only randomized once during initialization, for example, the initial partitioning of start database Do in Bouutoule et al.) (202I'ss ' SISA algorithm. Guppt et al.] (202T) show in their Theorem 5.1 that an adaptive update requester Q can interactively send deletion requests U1 ... 44 to SISA that the partitioning of remaining records in D; = Do o U1 ... .. follows a pattern that is unlikely to occur on repartitioning of D; when executing A A(D.). As proved in their reduction in Theorem 3. straightforward way to prevent this is by ensuring that the uncertainty regarding the persistent structures remains private for long periods of time to an adversary observing the unlearned model. Hence the proof of their reduction from adaptive unlearning guarantee to non-adaptive unlearning guarantee relies on DP with regards to the coins of the unlearning algorithm.
Our work shows that satisfying adaptive unlearning definition of Gupta et al. 2021 still does not guarantee data deletion. Theorem [] we demonstrate that there exists an al algorithm pair (A, A) satisfying (a strictly stronger version) of adaptive unlearning (Gupta et al.) 2021 Definition 2.3). but still causes blatant non-privacy of deleted records in post-deletion release. The vulnerability we identify occurs because an adaptive requester can learn the identity of any target record before it is deleted and re-encode it back in the curator's database by sending edit requests. Because of this, adversary (who knows how the adaptive requester works but does not have access to the requester's 's interaction transcript) can extract the identity of the target record from the model released after processing the deletion request. In our work, we argue that a reliable (and necessary) way to
23

---

Under review as a conference paper at ICLR 2023
prevent this attack is to make sure that adaptive requester ever learns the identity of target record from the p pre-deletion model releases has access to. Consequently, our reduction in Theorem [ from adaptive to adaptive requests relies differential privacy with respect to the replacement of records instead.
G ADDITIONAL PRELIMINARIES AND PROOFS FOR SECTION 5
G.1 LANGEVIN DIFFUSION AND MARKOV SEMIGROUPS
Langevin diffusion process on Rd with noise variance a² under the influence of a potential C: Rd R is characterized by the Stochastic Differential Equation (SDE)
do, = dt + 22
(63)
where dz, Ze Z. VLN (0, La) is the d-dimensional Weiner process.
We present some preliminary knowledge the diffusion theory used in our analysis. Let (f0. 0,) denote the probability density function describing the distribution of O, on starting from O2 = 0g at time O. For SDE (3). the associated Markov Semigroup P. is defined as a family of operators (Pt) such that an operator Pt sends any vealevalued bounded measurable function f IR IR to
P.f(Os)= = ([ = =bo] = / f f(0))p: 0,)
(64)
The infentisimal generator G def lim, [Po+s - Pa] for this diffusion Semigroup is
gf =f= (VC, Vf).
(65)
This generator when applied on a function f(0.), gives the infentisimal change in the value of function f when 0e undergoes diffusion as per 63 for dt time. That is,
/ (.pe((o,,0))) (.) f 0.(00,0.)0000..al
0, O.Prf(0u)= =
(66)
The dual operator of G is the Fokker-Planck operator G which is defined the adjoint of generator G, in the sense that
f f 96 gdg
| [[g gdo =
(67)
for all real- valued bounded measurable functions f.g. Rd + R. Note from (66) that, this operator provides an alternative way to represent the rate of change function f at time
a.P:((0)) = = 1(0.))"PP) (: 0.)d0,
(68)
To put it simply, Pokker-Plance operator gives the infentesimal change in the distribution of O with respect to time. For the Langevin diffusion SDE (63). the Fokker- Planck operator is the following:
(.)((0) G (0) div (p)(0)V((()) + (O).
(69)
From this Bokker-Placntl equation, one can verify that the stationary or invariant distribution π of Langevin diffusion, which is the solution of 0,p; 0, follows the Gibbs distribution
T()) C(9)/?
(70)
Since श is the stationary distribution, note that for any measurable bounded function f Rd + IR,
I3 G = f9 md0 7do
0.
(71)
24

---

Under review as a conference paper at ICLR 2023
G.2 ISOPERIMETRIC INEQUALITIES AND THEIR PROPERTIES
Convergence properties of various diffusion semigroups have been extensively analyzed in literature under certain isoperimetric assumptions on the stationary distribution (Bakry al. 2014). One
such property of interest is the logarithmic Sobolev (LS) inequality (Gross 1975), which we define next.
The carré du champ operator I of diffusion semigroup with invariant measure I is defined using its infintesimal generator
T(J. 9) = (9(5g) 19g 19g--999111 g9
(72)
for every f.g E (n). Carre du champ operator represent fundamental properties of a Markov semigroup that affect convergence behaviour. One can verify that Langevin diffusion semigroup's carre du champ operator (on differentiable f, is
((f.)) = o² (VI.Vg)
(73)
We use shorthand notation ((f)==((ff)=ooff IV
Definition G.1 (Logarithmic Sobolev Inequality (see Bakry et al. (2014) p. 24))). A distribution with probability density π is said to satisfy a logarithmic Sobolev inequality (LS(c)) (with respect to I' in 13 if for all functions f E (H)(H) with continuous derivatives f.
Ent ( 2c /
I(f) f2
20² c
/
Tdl
| f1 Td0,
(74)
where entropy Enta is defined as
Eft =E
f log fa|
E [ log E [
(75)
Logarithmic Sobolev inequality is a very non-restrictive assumption and is satisfied by large class of distributions. The following well-known result show that Gaussians satisfy LS inequality.
Lemma 18 (LS inequality of Gaussian distributions (see Bakry et al. (2014) p. 258))). Let p be a Gaussian distribution on IRd with covariance o² //> (i.e., the Gibbs distribution (70) with ((-) being
the L2 regularizer r(0) = 전タ 1012) Then p satisfies LS(A) tightly (with respect to 77)) L.e.
20²
ʃ |V pdo.
(nt,
(76)
Additionally, if μ. is a distribution on R.d that satisfy LS(c), then the convolution μ1 (L p. defined as the distribution of θ + Z where θ ~ and Z ~ satisfies LS inequality with constant ( + ))
Bobkov ( show that like Gaussians, all strongly log concave distributions (or more generally, log- concave distributions with finite second order moments) satisfy LS inequality (e.g. Gibbs distribution with any strongly convex L). LS inequality is also satisfied under non-log-concavity too. For example, T.S inequality stable under Lipschitz maps, although such maps can destroy log-concavity.
Lemma 19 (L.S inequality under Lipschitz maps (see Ledoux (2001)). 1f a distribution on Red that satisfies T.S(c), then for any T.-lipschitz map T : T. + RR. the pushforward distribution Tyn. representing the distribution of T(9) when θ ~ π,, satisfies LS(c)L²).
LS inequality is also stable under bounded perturbations to the distribution, as shown in the following lemma by Holley & Stroock (1986).
Lemma 20 (LS inequality under bounded perturbations (see Holley & Stroock (1986))- If a is the probability density of a distribution that satisfies LS(c), then any proability distribution with density nt' such that VB
x((e) vB everywhere in Rd for some constant B > satisfies LS(c/ B).
(()
Logarithmic Sobolev inequality is of interest to us due to its equivalence to the following inequalities on Kullback-Leibe and Rényi divergence.
25

---

Under review as a conference paper at ICLR 2023
Lemma 21 (LS inequality in terms of KL divergence (Vempala & Wibisono 2019 ). The distribution
7 satisfies LS(c) inequality (with respect to I' in (73) and only for all distributions I on Ie such
that (7t with continuous derivatives V
0²
KL (u|l
(ullT).
(77)
2c
Proof. Set 1
74 to
obtain
77
Alternatively, set μ
fr -
in (77 obtain 74
Lemma 22 (Wasserstein distance bound under LS inequality (Otoo & Villani 2000, Theorem 1)). distribution π satisfies (S(c) inequality (with respect to (3)) then for all distributions y on IR
20
W2 Tt)
KL. (u/lT).
(78)
Lemma 23 (LS inequality in terms of Rényi Divergence (Vempala & Wibisono 2019)). The distri- bution g satisfies LS(c) inequality (with respect to D in (7)) if and only for all distributions on Rd such that E (rt) with continuous derivatives V and any q 1,
π
q²a² 1 (H|(Tt
Rg (H|lTZ) Q(q - 1,0,RR (H|[TT)
(79)
2c Eg [u] TT)
Proof. For brevity, let the functions R(g) Rg (u|llt), E(q) Eg (1|l and [(g) Ig (u|| Let function (²) = मकত Then,
E
[ = E ( = E(g),
(From 34
and,
f log 12] = EE (H) log
4 97 = 2
[/
(
μ
(
97
log
dg
= q
(())
π
π
(From Lebniz rule and (34)
Moreover,
d2 ((g)
|IV 2
E
(From 40
4
On substituting (4h with the above equalities, we get:
202
Ent (f2) < E |
0² 1(9)
(0, El(g) log (l()) -
2c
0²02 T(q)
- q0, log E(g) - log E(q) 2
2c E(g)
+ q0, ((q - -))((g)) - (q - 1)g(() < 0²2 I(g)
(From 34
2c F(g)
< o0² I(g)
+ R(g) +
2c E(q)
G.3 (RÉNYI) DIFFERENTIAL PRIVACY GUARANTEES NOISY-GD
In this section, we recap the differential privacy bounds in literature for Noisy-GD Algorithm Theorem 24 (Rényi DP guarantee for Noisy-GD Algorithm D. If [(0; is L-lipschitz, then Noisy-
|
GD satisfies (g, RDDP with नل nnK
9L2
26

---

Under review as a conference paper at ICLR 2023
The 122 sensitivity of gradient VLD(0) def + of Algorithm for neighboring databases in A that differ in a single record is 2h since E(0; x) is L- L-Lipschitz.
Proof.
EXED Vε(0;x) + Vr(0) computed step
Conditioned on observing the intermediate model On = 0x at step k, the next model (n(k+11 after the noisy gradient update is Gaussian mechanism with noise variance 20 /n. So, for neighboring databases D, D' E X we have from the Rényi DP bound of Gaussian mechanisms proposed by Mironov 2017 Proposition 7) that
79 n2o22
Ry (0n(+))) 10 ( lec,
(80)
where (Onk)ogask and (0 (0 JogKEK are intermediate parameters in Algorithm databases D and D' respectively. Finally, from Rényi composition Mironov we have
when run on
2017 Proposition 1),
R2 (Onk|10nR)) S R2 (10o, On Onk (1%, O'p O 6xxx)
k
Σ
Rg (On(41)) 10 0 0 (((+)))) 10g
k=
n202 n'K.
Remark 5. Different papers discussing Noisy-GD variants adopt different notational conventions for the total noise added to the gradients. The noise variance in our Algorithm [ is 2nj²; but L² in the full-batch setting of DP-SGD by Abadi et al. (0016). To translate the bound in n²
Theorem 24 one can simply rescale a across different conventtons to have the same noise variance, 122212
i.., 2no²
Our Theorem 24 is somewhat identical to Abadi et al. (016))* 's (s. 8)-DP bound. To verify this, note from Rényi divergece to (e, iiiiiiidiitinnushhablllyy conversion discussed Remark [ that (1 + ? log 8: { Réééyi DP implies (c, 6)-D. So, setting the bound in Theorem 24 be smaller than and substituting 1 + 2 log J. we get
V K(s + 2 1
E 2 1
L
E K
=
S 6.
2
For E < 2 2og 1 DP-SGD algorithm.
5, we get the same noise bound as in Abadi et al. (0016 Theorem 1) for their (ull-bbtch)
Next, we recap the tighter Rényi DP guarantee of Chourasia et al. on the loss function.
2021 under stronger assumptions
Theorem 25 (Rényi DP guarantee for Noisy-GD Algorithm Chourasia et al. 2021 If E(;;x) is convex, T--iipschitz and 3-smooth and r(f) is the 1.2 regularizer with constant X, then Noisy-GD with learning rate n
3+X satisfies (g, RDDD with
1
Agh2 x0 (1 -inK/22))
G.4 PROOFS FOR SUBSECTION 5.1
In this appendix, we provide proof of our Theorem which applies to convex losses e(O; x) under L2 regularizer r0)) Let Do E n be any arbitrary database, and Q be any non-adaptive r-requester.
Our first goal this section is to prove pair (ANoisy-OD. ANoisy-GD) (in Definition 5.1 under Q. That is, (2))2u is the sequence of models produced by the interaction between (ANoisy-GD. ANoisy-DD, Q) on Do. we need to show that their exists a mapping πτ. such that for all > 1 and any u; EU"
guarantees on our proposed algorithm
R₂ A(D Us. θ . 1 o (indy>)) S saa for all (ind, y) E us.
(81)
27

---

Under review as a conference paper at ICLR 2023
For an arbitrary replacement operation (ind, y) in us we define map ... (Doo (ind, y)) 6/ where the model sequence (0():20 is produced by the interaction of between (ANoisy- ANoisy-GD, 2 on Do (ind, y). Since non-adaptive requester Q is equivalent to fixing the edit sequence (u, :21 a-priori, note that showing the data-deletion guarantee reduces to proving the following DP- like bound
R2 (A() u4, 6 ( 6/_1) S Eads
(82)
for for all ugzi and for all neighbouring databases Do, D/ s.t. D/= Do (ind,y) with (ind, M4
Note from our Definition 5.1 that the sequence of models (fo.... Q,) can be seen being generated from continuous run of Noisy-GD, where:
1. for iterations 0 S k < KA, the loss function is LD.,
2. for the iterations KA + (j 1)K A S < KA + jK any S j S <i- i- 1, the loss function LD and
3. for the iterations KA + (i - A I k < KA + iKA, the loss function is LD, 10us Let
be the sequence representing the intermediate parameters of this extended Noisy- Boy run. Similarly, let (6', )22 be the parameter sequence corresponding the extended run on the neighbouring database Dy- Since (ind, y) E th, note from the construction that Dj u, = Di-1 o u4 meaning that the loss functions while processing request u; is identical for the two processes, i.e. Lp: = Lp; 1ou4 For brevity, we refer to the database seen iteration of the 194;
two respective extended runs as D(k) and (k)) respectively. In short, these two discrete processes induced by Noisy-GD follow the following update rule for any 0 < k KA + iKK
10((x+1= yy 77 (D + 22no Zu O (x((+1)) 6',, v/ (O") + 221ooZZ
where Zμ Z ~ (0,
(83)
and Og and 0 are sampled from same the weight initialization distribution p. To prove the bound in (82). we follow the approach proposed in Chourasia et al. (20T)) of interpolating the two discrete stochastic process of Noisy-GD with two piecewise-continuuu continuous tracing diffusions O and θ in the duration spt < I n + 1). defined as follows.
θ () - (b-nk) V (CDrx) - (o)(k(((n))) + 2222 Znkt),
(84)
0 (e))) + (b-nk) (O'())(())))) (or()((()))) + (20 -Znr):
where Z, Zi are two independent Weiner processes, and T3 map on Rd defined
T = Ia ! (LD(H) + LD(()))
(85)
Note that equation (84) identical (83 when 17(k + 1), and can be expressed by the following stochastic differential equations (SDEs):
[do, = gi (O )t + d2.
where (+)
- [E(0) [(())(())(nd) {(9) D' (k) [ind]]
de + gg (O', dt + 22
2n
(86)
and initial condition lim θ, = T3 (+,k). lim, 0 Ti (e',), These two SDEs can be equivalently described by the following pair of Pokker-Planck equations.
Lemma 26 (Fokker-Planck equation for SDE (6)). Fokker-Planck equation for SDE in 86 at time nk < t () + 1), is
(etu = div [H)( g (mmx)(@ =0) + +02An((0), (0))((0) = div (1((0)) (- (O' (0))) -000000 01) + o (H))))(0),
(87)
g+
where He and un are the densities of θ and O2 respectively.
28

---

Under review as a conference paper at ICLR 2023
160
1)(++1
(b)
TR#P
(a)
T Tuwaka
16 1000+1)
(a)
(b)
Mo
Ro0
91.2
R441
Rs
RR
Ri
Rx
Ric =
(b)
1oo
(a)
T Tk#
Hnj
Thwm,
(b)
1)
(II) Phase II: Processing request i... KA + (i 1)Kx S KA iKx.
Use
(I) Phase Processing requests uei, i.e.
0 k < K 1
Here Hoyk and Myyk' represent the kth itcration parameter distribution of Oy and O respectively. We interpolate the two discrete processes in two steps: (a) an identical transformation Tr (as defined in (85). and (b) a diffusion process. If divergence before descent step is R₂ Rg (Hip (4/zz) the stochastic mapping Ti in (a) doesn't t increase the divergence, while the diffusion (b) either increases upto an asymptotic constant phase or decreases exponentially in phase II.
Figure 1: Diagram illustrating the technical overview of Theorem
31
Proof. Conditioned on observing parameter O, = 6yk. the process (O is Langevin diffusion along constant Vector field (i.e. conditioning, get Langevin SDE (63) with VC(() = g& (0,k)) for all A E IRd). Therefore as per (69), the conditional probability density He Heint (-10 ) of O₂ given Onyk follows the following Pokker-Planch equation:
OeHelpa (0sk) = div (Hejne (- 10pk)) (fn,:)) + o² + Apoin (-10pt)
(88)
Taking expectation Myj which is the distribution of Onp..
0.)4(()) (nn(( div (Helnk (-10 (110m))))))))) yg (0nk)) + =2AAHein + (-10nz) d0np
div (f Onx )d0 + +02AH(())
div (H(()) { gA (0 (0 -)d0m) 1) + +o²AHul
div
(H.())B(s:(GG) = +
where My is the conditional density of O, given θ,, Proof for second fokker-planck equation is similar.
We provide an overview of how we bound equation in Figure Basically, our analysis has two phases; in phase (I) provide bound on Rg ( 6 that holds for any choice of number of iterations KA and Kx, and in phase (II) we prove an exponential contraction in the divergence R2 [ (A(D,-1, u4 θ A(P) 6(_.)) with number iterations Kx-
We first introduce a few lemmas that will be used in both phases. The first set of following lemmas show that the transformation 0 6',, - Ta (2 (0,,) preserves the Rényi divergence. To prove this property, we show that Ti differentiable bijective map in Lemma 28 and apply the following Lemma from Vempala & Wibisono (2019).
Lemma 27 (Vempala & Wibisono 2019 Lemma 15)). IfT Rdd + Rd a difserentiable bijective map. then for any random variables θ O' IRd, and for all 0.
Ry (T(O))[T((') R. ()]
(89)
29

---

Under review as a conference paper at ICLR 2023
Lemma 28. If [[((:x) x) is twice continuously differentiable, convex, and 3-smooth loss function and
regularizer r(0) | then the map T'. defined in 85 is:
1. a differentiable bijection for any <
X+B. and
1
2. (1 - -1)))--ippschitrr for any vj S 2X+3
Proof. Differentiable bijection. To see that TІ is injective, assume Tx(O) = Tx((") for some 8, 8' E R.. Then, by (3 + sossmohthssss of def (LD(M) + (xi(2))
110 0 [T + CV) (x'(0))) - -n ///VV(()) VL(00)l
I 7(( B) ||0 6 112
Since 7 < 1/(A + B), we must have 110 0'1,2 For showing Ti surjective, consider the proximal mapping
1 011 nC(()).
(0) = arg min
(90)
d'ERd
2
Note that p-)x is strongly convex for X+. Therefore, from KKT conditions, we have 0 c - (V (prox, (0)). Differentiability of T3 follows from the twice continuously differentiable assumption on 2(0;x).
Lipschitzness. Let C def (CD(k) + (2) For any 0, E Rd,
(T((0) - ( ||0 -)) 8' +n)
|00 0/11 + 1/2 [|V CC0)' 2n (0-00, - VL(0').
We define a function g = C()) - スे2 ||0|| 1 which is convex and f-smooth. By co-coercivity property of convex and B-smooth functions, we have
00 - 0', (g( V)(()) > Vv((0) 2
1 ( [VC(0)- - VZV21)) 0'112 = (0 0', VC - VC(O') - 110 01122 2 1/
22 - 0² V2(0) - -Q((0')
= (0 - 0', VC VL(O') 2 VL V2(0')1 + A( 3)
10 0013
2A + 3
2X B
Substituting this in the above inequality, and noting that 1) S
2x+3 get
2nA(A 8)
27
(0) (0)1
110 011 +
17²
|VL(0) VL(0)
2A + 3
3 2X
2nA(A + 3)
2n12
<
110 0 +
110 - 110-0'112
2 + B
3 + 2A
(1 2 110 8
The second set of lemmas presented below describe how R, (θ, |e)) evolves with time in both phases and II. Central to our analysis is the following lemma which bounds the rate change of Rényi divergence for any pair of diffusion process characterized by their Fokker- equations.
30

---

Under review as a conference paper at ICLR 2023
Lemma 29 (Rate of change of Rényi divergence (Chourasia et al. 2021
Let V1, Vi
R - R be
s L for all f E For diffusion process (0r)r20 and (0/)120 defined by the Fokker- Planck equations
two time dependent vector field such that max [[V[()) - (b]l
R and 2
{
[auu = div (H, + o² d²) and (e))((0) div (1) + (
(91)
respectively, where ph and th are the densities of O and 0r the rate of change of Rényi divergence between the two at any 2 O is upper bounded as
9L2 q0² In (Hrllu4)
Bg (Hellu4) S
(92)
20 2 Eg (Hellu4)
We will apply the above lemma to the Fokker-Plane equation (87) of our pair of tracing diffusion
SDE (84) and solve the resulting differential inequality prove the bound in (82). To assist our proof,
we rely on the following lemma showing that our two tracing diffusion satisfy the LS incquality
described in Definition G.I which enables the use the inequality (79) in Lemma 23
Lemma 30. If loss x) is convex and 3-smooth, regularizer is r(0) 2े 1101 and learning rate 2 S 2x43. then the tracing diffusion (0t)ostSn(Kxxtik, and (K defined in (84)
with Oo 0/ ~ p= N (0, x11-11/2 Ta satisfy LS inequality with constant X(1 n//2)).
o²
Proof. For any iteration 0 S k: < KA + iK in the extended run of Noisy-GD, and any 8 S 7
let's 's's define two functions L., f., R2d + IK as follows:
1+ CD(K) + 2
1 1+ CDr(K)- 1 1 8/n CD(()) and -2= - 1-8/n CD(M) +
C.
(93)
2
2
2
Since r(-) is the L2(A) regularizer and E(O; x) convex and 8-smoothness, both C, and C¹ are strongly convex and (X+ B) -mmooth for all 0 S S and any k. We define maps T,, T2 R2 - Rd
as
(0) = - -, (0), and ()) = 0 (.).
(94)
From a similar argument as in Lemma 28 both TN and TV are (1 T)A)- for learning rate
7) S 2
Note that the densities of θ and O of the tracing diffusion for t = ryle + s can be respectively expressed as
He Tag (HnR) @ N (0, (0,2so and 14 Ty (1/aa) @ N (o, 2s)
(95)
where Hyys and 1'e represent the distributions of θ,,, and O We prove the lemma via induction.
Base step: Since Oo 0/ are both Gaussian distributed with variance X(1 they satisfy LS inequality with constant A(1 - 7)/2)..
o² nA/2) from Lemma 18
Induction step: Suppose Hyy and U²S satisfy LS inequality with constant X(1 1/\/2). Since
equation (95) shows that Hr uy are both gaussian convolution on a pushforward distribution of
Myyk: HIg respectively over a Lipschitz function, from Lemma 18 and Lemma 19 both μe, 14 satisfy
LS inequality with constant
(1-mA)²
(1- n))²
-1 222" X(1 n//2) [1- An) -)>)
28 X(1 n//22
(96)
for all y/t S < 17(ks + 1).
We are now ready to prove the data-deletion bound in (2
Theorem 31 (Data-Deletion guarantee on (ANaisy ANoisy-GD) under convexity). Let the weight initialization distribution be = N (0, x11 ) the loss function E(0; x) be convex, 3-smooth,
31

---

Under review as a conference paper at ICLR 2023
and L-Lipschitz, the regularizer be r(0) 110 and learning rate be n x+B- Then Algorithu pair (A, A) satisfies a (g, Eaa) noise variance o² 0 and kA 2 0
guarantee under all non-adaptive r-requesters for any
2 nd
4qT. \Edao222
Kx
log
(97)
Proof. Following the preceding discussion, to prove this theorem, it suffices to show that the in- equality (82) holds under the stated conditions. Consider the Fokker-Planck equation described in
Lemma for the pair of tracing diffusions SDEs in (86): at any time t in duration ryk < t S 1y(k: + 1)
for any ileration 0 S k < KA + +iK
(0) = div (H: BA (0n = =0) + (0²AH((0),
(98)
(0H4(() = div (1((0) -8 0 = 01) + o²A
where He and ut are the distribution of θ, and Ø₁ Since e(0; x) is L-Lipschitz and for any KA + (i (2-11 K3 S k < KA + iKa we have [ind = D' (k) /ind], note from the definition of gx(0) (0) in (86) that
E (e = 0] ge (9' (0)) = =0l1
21 n
i < KA + 1)K
$
(99)
0
otherwise
Therefore, applying Lemma 29 to the above pair of Fokker-Plamne equations gives that for any in duration n/lc S nl + 1).
2
go² I, (Hellu()
Bg [1() s o²n² 1 st + (i 1)K,)}
(100)
2 Eg (He lu()
Equation (T00) suggests a phase change in the dynamics at iteration == Kv + (i 1)K In phase I. the divergence bound increases with time due to the effect of the differing record in database pairs (Py.D))ose Dossssi--. In phase II however, the update request u, makes D o i = D o ug and so doing gradient descent rapidly shrinks the divergence bound. This phase change illustrated in the Figure
For brevity, we denote R(q,t) Ry (Helll)). Since 17 < X+B
1
2メ+Ø from Lemma 30 the
distribution un satisfies LS inequality with constant X(1 - -nn/2). So, we can apply Lemma 23 to simplify the above partial differential inequality as follows.
R(g.t) + (q - (o--)),
29L2
0, + X(1 X(1-An/2)
(t S M(KA + (i 1).
o2n²
(101)
For brevity, let constant C1 Then,
X(1 Xn/2) and constant
C2
21 o
We define u(g,t)
R(g.))
2
[((,,)
0. + c1
+ ( 1)0,1),, s c2g x 1 1st + 1))K))
= -,ugg, + ei t) + 01 1)0, 1) S C2 S22 1 (t (KA + (i 1)Kx)}
For some constant q > 1, let (ss) (q 1) exp (e (s - (K + +k} + and ((x)) = 8. Note that do(s) ca (g(s) 1) and dr(s) = 1. Therefore, for any 7/th < s - 7 + 1), the differential
ds
inequality followed along the path u(s) u(g(s))t(s)) is
du(ss
+ cc((s)
S C2 x (t n + (i- ((-1)Kx)]
(102)
ds
d
[ < 1 (t < (KA (i-1)Kx)}
(103)
ds
Since the map Tx(:) in 85 is differentiable bijection for y < X+ per Lemma 28 note that Lemma 27 implies that lim +gght u(s) u(nkk). Therefore, we directly integrate in the duration
1
32

---

Under review as a conference paper at ICLR 2023
0 S t (KA x) to get
(c0) & (
" ds
e Dulnk + -KK)))u((0
2 61
(an
- u(n((A + +kx)) v 2 e -inKa
(Since w(0) - ()/(() - 0.)
Noting that q(0) 2 1, on reverting the substitution, we get
27L²
Ry (H((KA+((()) (((KAtiK)))
exp exp(-nA n\/2))
A02
m2//2)
4qT.²
1/
exp Ao2n2
(Since v x+x)
Recall from construction that +ik)) and H M are the distributions of A(D;-1, uh, Ô.-1) and ADD) U, G;_,) respectively. Therefore, choosing K₃ specified in the theorem statement concludes the proof.
Our next goal in this section is to provide utility guarantees for the algorithm pair (A (ANoisy-Gn) GD, ANoisy GD) in form of excess empirical risk bounds. For that, we introduce some ad- ditional auxiliary results first. The following Lemma shows that excess empirical risks does not increase too much on replacing r records in a database, and Lemma 33 provides a convergence guarantee the excess empirical risk of Noisy-GD algorithm under convexity.
Lemma 32. Suppose the loss function E(0; x) is convex, L-Lipschitz, and B-smooth, and the regular- izer is r(0)- = 2/2 |0| Then, the excess empirical risk of any randomly distributed parameter for any database D X" after applying any edit request E U that modifes more than records is bounded as
orr(O:Dom) S 1+ 2 2 er) +
16r
(104)
AnZ
Proof. Let 8% and Dow be the minimizers of objectives LD(-) and LDou(.) as defined in (??). From X-strong convexity of the LD.
(D LD 2 X 11 0b112
(105)
2
From optimality of Dou and L-Lipschitzness of E(0; x), we have
(D((Doo)) LDo. (0Do))
Σe(0 ((00ooix)
Σ
e(ODowix)
xED
xEDou
I (Dou(05) +
Σ
E(0touit0
Σ e(0Dowix))
XED
XEDou
1 Σ (f(0 -1(0g; x)) + n
(o0())) +
Σ (E(0f:))
-R(Opoui x))
7
xED
xEDou
Lr
S (0)))
110 0% l
n
Combining the two inequalities give
4rL
10 - -88112 -
(106)
An
33

---

Under review as a conference paper at ICLR 2023
Therefore, from (A + smoothhess of Lo and X-strong convexity of Lp. have
err(@; D o u) = E [C (+) Do Dow)
A + 8
E
|1@ Dou [1
2
$ (A + 8)
|10 0 1/ + +100 0
$ 1 + $)
1,2
2 (LD(() - CD((%)) +
dn?
Lemma 33 (Accuracy of Noisy-Gii (Disy-GD). For convex, L-Lipschitz, and, 8-smooth loss function x(0;x) and regularizer r(0) |10122 if learning rate n < xtg the excess empirical risk of ,₂ = NDi Oo K) for any D E x" bounded as
err(O D) S err((); ()e + (1-5) 2 do?
(107)
Proof. Let Oyyk denote the kth iteration parameter of Noisy-GD run. Recall that k + 1th noisy gradient update step is
O ((++) = - VVV + 22n00
-
(108)
From (B + A)- A)-sooothsssss of LD, we have
LD (D(()((+1) - LD(( (VLL 0 Opp 8+ A - = - // + 2n12 (V LDD (O Zk)
||0 - 0
+ (B + A)
2 VQp 2 + A) /
2
" 2no + X) (VDD Zu}
On taking expectation over the joint distribution O (1( Zg. the above simplifies to 7/ 7 3)
E (CD(Om(H+))) < ([()(O,)))) (1
E (O 122] +ndo (109)
Let 0g. arg min (0). From x-strong convexity of LD, for any 0 E Rd, we have BERd
|V))(0)) > 2X(Lx(0) (D))))
(110)
Let = Xn - 7)({+ B)). Plugging this in the above inequality, and substracting (0())) on both
sides, for < x.g. we get
E [CD - Co < (1 (11-))((co(R)) Co(b)) + + A)
$ (1 - 7) h+ (DD())) Lo(1')) rdll 2(3 A) + ..... + (1 (1- -))
S -e (e<(4+11/28(C0(000 Co(0%)] ndo (B X)
7
For X note that 7 2 A1, and
err(O,x: D) S err(Ou; D)e -) Ann/22 + (1
8 (11=1))
do²
(111)
X
34

---

Under review as a conference paper at ICLR 2023
Finally, ready to prove main Theorem 6 Showing that algorithm pair (ANoisy-GiD Nossy-GDD solves the data-deletion problem as described in Section [4] We basically combine the RDP guarantee in Theorem 25 non-adaptive data-deletion guarantee in Theorem 31 and prove excess empirical risk bound using Lemma 33 and Lemma 32
Theorem 6 (Accuracy, privacy, deletion, and computation tradeoffs). Let constants X, A, L x+ Let the loss function {(0;x) be twice differentiable, convex, L-Lipschitz, and B-smooth, the regularizer be r(0) = 110 If the learning 4gL? rate 1 - 2(*33) the gradient noise variance is o² Xeapn? and the weight initialization distribution is p= N (0. (111-1/2]1)) then
q ?>> and 0 < Edd Σ Edp- Define constant -
o²
(1.) both Go and GD are (4, -Rp)-RDP for any KA, K
(2.) pair (ANoisy ANOLy-CDD satisfies (g. -aaaaaataa-aeee data-deletion all non-adaptive r-requesters
Edp
if K 2 4m log Edd
(112)
(3.) and all models in (Qi)i20 produced by (ANoisy. GD. Noisy Q) any Do X", where qd
is any r-requester, have excess empirical risk err(O,; D,) O Edp
"dppn 4qd
SEap 2
if 2 4x 4ogog
and Kx 2 4k log max 5
(113)
qd
Proof. (1.) Privacy. By Theorem 25
the Noisy-GD with K iterations will be (g, Edp) RDDP for the
49 stated choice of loss function, regularizer, and learning rate as long as o² Xeap (1 A2. Therefore, if we set 6²
Xeap Noisy-GD is (g, (a,eap)-RDP for any K. For the same o², both
AgL2
Go and À Noisy GD are also (g: Cap)-DDDD for any K^ and K3 as they run Noisy-GD on respective databases for generating the output.
(2.) Deletion. By Theorem 31 for the stated choice of loss function, regularizer, learning rate,
and weight initialization distribution, the algorithm pair (ANoisy-GD, ANoisy-GD) satisfies (g, Saa)- data-deletion under all non-adaptive r-requesters Q if K5
2 log
\ By plugging in
4gL2
4gl.2 2² Aeap and 2(*+3) this constraint simplifies to K 2 4x log Ead"
Sde.
(3.) Accuracy, We prove the induction hypothesis that under the conditions stated in the theorem, err( (.)
10xqdL" for all i 2 0. Aea
Base case: The minimizer 8r of LD, satisfies
L Σ ve(02,;))) 10% =0 - 110 112 -
(114)
=x
xEDo
As result, the excess empirical risk of initialization weights O, ~ =N (0, bounded as
o²
on Lr
X(1-0\/211
err(On) Do) [CD, LD, (0%
() 9)
||0, 1/]
(From (A + -mmoothnsssss of L
2
(A+ + 9)
|18:0 112 + 110012
2E [00 [o)o]
2
L2
o²d
1 + X
+
(From 114 and E [z d if N (0.
2X
2 - An
1
+ 2
2X
35

---

Under review as a conference paper at ICLR 2023
Since
θg
ADoisy-D(DD)) (Do) = Noisy-GD(Do, Gu KA),
by
Lemma
33
running
Edpn" 4qd
KA 2x log
iterations gives
err(@0; Do) - err(@): Dole AnKa/2 + kdo
+ do²
An/K/22 + kdo²
2X
kL?
SnqdLL
2A
c
+
Xedp??
(On substituting σ²
Aean
4g
10ngdT.
(Cap" 4gd
(Since Kλ 2 4x log
AEdp??
Induction step: Assume that err err(0,11; D v 10mgdL2 Azdpa
Since θ ANoisy-GD (Di-1, Us: ,,-1)
(Disy-GD(D, Ô K2), by Lemma 33 and Lemma 32 running Ky 2 2x log max iterations gives
5M,
8r2
qd
16
err(O,; D.) S
2er((0--1:D--i))
AnK ndo?
dn²
20rqdL2
26 e-2222/2 + 4nqdL² dEdp??
$ k
(Substituting o²)
XEdp??
dn?
16kr L²
A2 + SkgdLL
<
(Since Kx 2 4kc log()))))
dnZ
< 10xqdI.2
(Since K 2 4k 4x Seap qd
XEap??
G.5 PROOFS FOR SUBSECTION 5.2
In this Appendix, provide proof of data-deletion and utility guarantee in Theorem which applies to non-convex but bounded losses L(O; x) under L2 regularizer r(0). Suppose Do E X is an arbitrary database, Q is any non-adaptive r-requester, and (0,)220 o is the model sequence generated by the interaction of (ANossyGD- ANoisy Q). Our first goal will be to prove (g. Eda) -dat deletion guarantee on (ANoisy-GD, ANoisy-GD) and we will later use it for arguing utility as well. Recall from Definition 4.1 that to prove (q, (d. datta-deletion we need to construct map ग.. X + O such that for all and any u, u",
R2 (A(D.-1, ui, θ nT (Do (Do (ind, Eaa for all (ind,y) ug.
(115)
Our construction of πi! for this proof is completely different from the one described in Appendix G.4 As discussed in Remark 3 since @ non-adaptive, it suffices to show that there exists a map
T: N - O such that for all 2 1,
Rg A(DD.1, u4 ②.-1) (T())))) < Edd,
(116)
for all Do E d and all edit sequences (w))21 from 2!"
Our mapping of choice for the purpose is the Gibbs distribution with the following density:
T (0) & Coo(////
(117)
The high-level intuition for this construction is that Noisy-GD can be interpreted as Unadjusted
Langevin Algorithm (ULA) (Roberts & Tweedie 1996). which is discretization of the Langevin dif- fusion (described in eqn. (63)) that eventually converges to this Gibbs distribution (see Appendix G. for quick refresher)). However, showing a convergence for ULA (in indistinguishability notions like Rényí divergence) this Gibbs distribution, especially in form of non-asymptotic bounds the
36

---

Under review as a conference paper at ICLR 2023
mixing time and discretization error has been a long-standing open problem. Recent breakthrough results by Vempala & Wibisono| (2019) followed by [hewi et al. (2021) resolved this problem with an elegant argument, relying solely on isoperimetric assumptions over (177) that hold for non-convex losses. Our data-deletion argument leverages this rapid convergence result to basically show that once Noisy-GI reaches taa-indistinguiihablltyy to its Gibbs mixing distribution, maintaining indis- tinguishability to subsequent Gibbs distribution corresponding to database edits require much fewer Noisy-GD iterations than fresh retraining (i.e. data deletion is faster than retraining).
We start by presenting Chewi et al. (20T) 's convegence argument adapted to our Noisy-GD for- mulation, with a slighlty tighter analysis that results in log(g) improvement in the discretization eπror over the original. Consider the discrete stochastic process (0nk (o induced by parameter update step in Noisy-GID algorithm when run for K iterations on a database DD with an arbitrary start distribution Og Ho. We interpolate each discrete update from O, to ② (n(+++)) via diffusion process . defined over time nk < t S t7(k + 1) as
O Onk (t - V + 2202 Zyk))
(118)
where Z, is a Weiner process. Note that if Oypk models the parameter distribution after the t update, then mn++1) models the parameter distribution after the k + 1th update. On repeating this construction for all k = 0, K, we get a tracing diffusion {0r120 for Noisy-GD (which is different from (84). We denote the distribution of random variable O, with n.. The tracing diffusion during the duration splc & t S n + 1) is characterized by the following vokker-Plande equation.
Lemma 34 (Proposition 14 (Chewi et al.) 2021)). For tracing diffusion O defined in equivalent Fokker-Planck equation in the interval ny - t S ny(k + 1) is
118 the
(0) = div -dix<(fEEEEea (EEIVCO(OM)) (LVTCo()))-VGo(0)00000=- 0)+ + - log (0) } (D)( S me(0)). (119)
where TD) is the Gibbs distribution defined in 117
Proof.
Conditioned on observing parameter O,y = 0yk, the process (9t) geg((++))((++ is a Langevin diffusion along a constant Vector field (Onx)) Therefore, the conditional probability density Hy mn (100)))) of O given Oyk follows the following Fokker-Planck equation.
o Hr nt (+10gx) = A2A + div (H nh (+10)t) (DD
(120)
Taking expectation over Oypks we have
0-p((-)) = / Unn fo² A (-10 + div (10m))
d0,p
+ div (m(() (VCD(())) ( VVCo--)Llllll-- (1)) Id0m)))))))))))))))))))))
= =o2Apr()) + div
(+))) = [u(.) log TT()()) + div (EIVLD(Onk)) VLD()) = = -l(()))
where Ut is the conditional density of On given O₁, For the last equality, we have used the fact that VLD = - log T(D) from (177).
The following lemma provides a partial differential inequality that bounds the rate of change in Rényi divergence R.y (HellT(D)) using Fokker-Plann equation (199) of Noisy GD's tracing diffusion.
Lemma 35 (Proposition 15 (Chewi et al. 2021)). ). Let Pt H4/ (z/T(D) where T(D) is the Gibbs distribution defined in (177) and th == P EEg (p (P))) The rate of change in Ry (H)) along racing diffusion in time n/ < t < (7k
+ 1) is bounded as
R,R, (H+|lT(D)) S 3qo² I, (He / (())
+
VLD(O.) (121)
4 E,g (Hell [(())
o²
37

---

Under review as a conference paper at ICLR 2023
Proof. For brevity, let A+(+) E (V VCD(O.) in context of this proof. From Lebinz integral rule, we have
Oy [u]l]((D)) = (q E) (He (m)))((D)) /
H4 )²1 deprd
T(D)
g (q 1) E) (H4 ((())
90 -iv (f4r + o V pa) H.) do (From 119
(q F) (H [T[l(T(())
/ (v(p)-1) A 2 logg
log p.)) ued0
Ey (14 (H]])((()) / 07-2 (V,,, A, 0² Pc
Vp:
4.d0
(Hel|TT)
2
19/2211 2-
11)1
Eg (141l (H+|l((D))
Pt
M
(From 440
Note that the expectation in Ar(-) is over the conditional distribution HugAie while the expectation in Fi is over He. Therefore, we can combine the two get an expectation over the unconditional joint distribution over , and On as follows.
P 19/2-1(0))
v (p. (0.),
[VCD(O,)- -(CO((,)))
Fii
E Oemue
E
Onk
E
p /2 (0.)
(0.)) (v (0) (0t), VLD(O.) VLDD(0mx))
E
Pr (0.)
(2 (0.)
q
p
(0.) (0.) (VL[ VLn, (0,
2q
20
y0²
144
(pellu))
+ _
E o3 (0,) [[, VL (+,x))
(From 440)
8
20
Substituting it in the preceding inequality proves the proposition.
We need to solve the PDI [21 to get a convergence bound for Noisy-GD, To help in that, we first introduce the change of measure inequalities shown in Chewi et al. (2021).
Lemma 36 (Change of measure inequality (Chewi al. 2021 ). If x) B-smooth, and regular- izer is r(0)= = A |0 then for any probability density μ on Rd.
2
E
[
2
40
E x(D)
V
2d + A); (
(122)
where T((D is the Gibbs distribution defined in 117
over the potential LD. The Proof. Consider the Langevin diffusion (63) described in Appendix G.1
Gibbs distribution T(D) is its stationary distribution, and the diffusion's 's infintesimal generator g applied on the Co gives
GLD ALD ||V LD
(123)
38

---

Under review as a conference paper at ICLR 2023
Therefore,
E [VDll = [AD) E [GGD
(From 123
S (3 + X) / GLD
T(() -1 1 x(()dd
1
(From B-smoothness and 71
= -330 +1)+ +)+ + / |IVCCol2 - d2ocol (++²) - r(D)do
d3o2 (1++)+++++)) |V62112 - (D)))
+0² / (VCD. - (( -1) x(D)
(From (19)
-d30² +11)+ / /V x(D))00 0² / (VLO,-
VLD
-² x²
(H (H- (U-TT(D))d0
+0² / /VLL.. V 4 ((D)
/
(Since VT(D) "Lpn(D)
T(D)
/v/ (V=TT))
d300 + +1) +0+ 20
H T(D)
VLD, V
H TT()
x(D)d0
|
s d3o A)
E
|VLxo|]]
+ 20t E T(D)
μ T()
2H
(From
(20 with a 20
Another change in measure inequality needed for the proof is the Donkser- variational principle.
Lemma 37 (Donsker- Vardhan Variational principle (Donsker & Varadhan 1983). two distributions on Rd such that v < v', then for all functions :R + R,
If and v' are
[f(0)] < KL (vilv') + log E k~v
E
[ex)( g/
(124)
We are now ready to prove the rate of convergence guarantee for Noisy-GD following Chewi et al. (202T)ss 's method, but with more refined analysis that leads to improvement of log q factor in the discretization error (compared to the original (Chewi et al. 2021 Theorem 4)).
Theorem 38 (Convergence of Noisy-GD in Rényi divergence). Let constants 3, > 0 and B))((B/4))-bundd)))) -/-boudded and 3-smooth, and regularizer is r(()) 말े |101žž- If step size is S 63 then for any database 'D E X and any weight inirialization distribution Ho for Oo. the Rényi divergence of distribution Hyj of output model 0n = Noisy-GD(D, Oo, K) with respect to the Gibbs distribution T(D) defined in (17) shrinks as follows:
B > Suppose the loss function {(; x) is (o" log B)/
X
(-
Dank 2B
Ry (HollT(D)) + 32dng x)2
Rg (Hnx|] S gexp
(125)
Proof. From (B + A) smoothness loss Lo we have that for any nk St S 17(k 1),
(V VCD(O.))l < (8 + 2)² 0 0.11
(8 + 2)² (L- - 12(l - nk) 2 Z
(From [18
< 2 (C< 4n 2 2)2 ||
$ ( (LD
1Z 4 X)² 12x
39

---

Under review as a conference paper at ICLR 2023
Let Pr == Me and use it to get the following bound on the discretization error in 121
x[D) and di p: (pell<(D)) If 2v²((+2)'
rearrange get the following
E (,,( V B. (0)) VLD(0,)1
(x(Ot) (VLD T - 81
F
+ 32n0 (B A) (O.) | 11 /4
Hence, for solving the PDI 121 have to bound the three expectations Fi and F2.
1. Bounding Fi. Note that E
[+,) (O)) Egipe [m))) (() d0
42
So, (0) dh u, is probablitly density function on Rd. On applying the measure change Lemma 36 on it, we get
F = E | 14p
S 40
E T(D)
V V
Vete TT(D)
+ 22 A)
(From (
P. 2
4 E
2do A)
(()
Fig (Hz [D])
1 Ig (HIl)((D)) + 2d + A
(From (40
F.g (H]])((D))
2. Bounding F2. Since the valid density on Rd, the joint density = 2) == (0) where He, is the joint density of θ and Z₁ is also valid density. Note that the F2 an expectation on ZR 1/ taken over the joint density teeHe. We can perform measure change operation using Donsker-Vardhan principle to get
F2
7
1 /4] S KT (1M44::2111 + log
[exp( Z
112 /4)]
where we simplified the second term using the fact that the marginal μą of H4, is a standard normal Gaussian. The random variable ||Zx1|2 is distributed according to the Chi-squared distribution x3 with d degrees of freedom. Since the moment generating function of Chi-squared distribution is Mx²(1) = E
[exp(LX)] = (1 21) -d/2 for < 2. we can X~xa
simplify the second term in F2 as
(
dlog
log us
exp((I /4)]
log M
(126)
2
The KI. divergence term can be simplified as follows.
= / VeHHe. log the (0.) d0,,2
KL (drHee,lllH))))
= f Wettee log
pt p
d0,
(On marginalization of z)
F.g [4ll|T((2) (D)
/ Her'ee log
log E, (H.I d0,
Eg (H4 [T())
- 1
(KL (Hr))ll(((D) - R. (Hel)T(D)))
< KL (He)))l<((()
(Since Ry (H4 (HillT(D)) 0)
40

---

Under review as a conference paper at ICLR 2023
Note that under the assumptions of the Theorem, ((D) satisfies log-Sobolev inequality 74 with constant A/B (i.e. satisfies LS()/))). To see this, recall from Lemma 18 that the
Gaussian distribution p(0) N (0, ll)) satisfies LS(A) inequality. Since loss e(1; x) is (o"
the density ratio I(D(
E
+ VB
The claim therefore
p(0)
VB
follows from Lemma 20
Using this inequality, from Lemma 21
we
have
o²
/
1/ TT
2
KL (Hebbll
(D)) -
He
V log
d0.
2A
o²B
V log p.) (p)) (D))
2x
Eyg (14 (T())
20
Eg (Hell((D)) / [(op |1 (D))
q²0² B Ty (He (T()))
2A Eg (He (T()))
On combining all the two bounds on F1 and Fg and rearranging, we have
s 8m1 0 (3 + A)² 1a (MellT((D) Egg (Hell ((D)
2B n
E (b:) [Q (LD((
A
+ 16ndo + ^)² (n(3 + X) + log 2)
Let step size be n S min
2B Ax (2+2))
Then, the first term above is bounded as
1g [Hell [T( (D)
Lg (H IT(D)) 2B X 2 E,g (14 [T()))
8ng20 + ))²
+
(127)
E, (1, (x))
Let 1) S 4[#4a]: Then, in the third term, (r1(3 + A) + log 2) S 1. Plugging the bound on discretiza- tion error back in the PDI (121), we get
R, (H (x(D) s go² Lg (T)
4 Eg (H, (D) + 16ndg(3 + x)2.
(128)
Since m(D) satisfies (AS B) inequality, from Lemma
23 this PDI reduces to
Bg (H4 [T[))) + A
Rg (He (H))))(D)) + ( R, (Hell S 16ddgg(3 + A)2. (129)
2B
q
2B A and 02 = 16dn(3 + X)2. Additionally, let u(g.t) Ra(He In(()), Then,
Let
R2 (Hrll + (u 1),8, (He (H1|l S 02q
a,R, (4: (DD) +
9 Rg (H4 (T())
0. (Hr)lt(()) + c
Bg (He (T(D)) Ry (Hr [T(()) 02
+ ca 1)
9
q²
O-ulg, t) + clu(q,t) + ei (q 1)0,u(g,, S c2.
For some constant q 2 1, let q(s) ( 1) exp(ci (s nK) + 1, and t(s) Note that dg(s) de = (g((()) 1) and dr(s)
ds 1. Therefore, for any 0 < t nK. the PDI above implies the following differential incquality is followed along the path u(s) t(s(s),t(s)).
du(s) ds
d u(s)} S a
+ cc((s) S = de fe (
n
-e (e>s"()))??" u(s) - 30
ds
= eann u =(()= < C2(ecink -1)
C
= u(nk) Se .nnk u00) + c2
e (1 E -lnn))
41

---

Under review as a conference paper at ICLR 2023
On reversing the parameterization of q and t, we get
Ry(nK) (Hn(lI<(D) v g(nk) - Ry(o) (Holla(D)) + - g((
<(0)
CI
{))
Ank
B2 + x)2
(()) exp
Ry(o) (Holl +
((nK).
2B
A
Since g(0) > 1 and q = ((nk) ) > (0), from monotonicity of Rényi divergence in we get
Ank
Rg (Holl + 32dnq + A)2
Rg (Hnx]|T(D) S @exp
(130)
2B
X
Finally, noting that for constants
B.g q
and B, (B+A2 completes the proof.
0,
step
size
1 7 S min!, 2v2(8+x) 4G4AA) X (487
2B
We will use Theorem We need the following result that shows that Gibbs distributions enjoy strong indistinguishabiliyy on bounded perturbations its potential function (which is basically why the exponential mechanism satisfies (E, D)-DP (Wang et al. 2015 Dwork et al. 2014)).
38 for proving the data-deletion and utility gaurantee on (ANoisy-GD) GD, ADD)
Lemma 39 (Indistinguishability under bounded perturbations). For two t potential functions L, L' _d + R and some constant o², let v & e-//²² and v' x -0' be the respective Gibbs distributions. If [()) (')) S cfrr all TR., then Rg (vllv') S az for all >
Proof. The Gibbs distributions v have density
1 2(0)/0" and v(0) 1 C'
v(0)
A
A'
where A, are the respective normalization constants. If for all 0 E RR, the potential difference [C(0) - (0) S c, then
1
v y'g-I
R2 (vllv)
log
d0
log /
A1'
9-1
4 1-1
(E'(() C(01)
exp
x v(0)a0
1
A'
c(q (q-11)
/ vdl
(q 1) log
+
cxp
1
A
σ²
I
/exp
((0) o²
C(0) (0)
0²
d8
c(g 1)
(q - log
f eex
(())
d0
o²
2c
0²
show that (ANoisy-GD: A ANosy-GD) solves the data-deletion problem described in Section 4 even for non-convex losses. Our proof uses the convergence Theorem 38 and indistin- guishability for bounded perturbation Lemma 39 show that the data-deletion algorithm ANoisy-GD can consistently produce models indistinguishable to the corresponding Gibbs distribution (117) in
In Theorem 7
the online setting at fraction of computation cost of ANoisy -D- As discussed Remark 3 such an indistinguishability is sufficient for ensuring data-deletion for non-adaptive requests. As for adaptive requests, the well-known RDP guarantee of Abadi et al. (2016) combined with our reduction Theorem 5 offerss data-deletion guarantee for (ANoisy-GD- ANowy-GDD under adaptivity.
Our proof of accuracy for the data-deleted models leverages the fact that Gibbs distribution 117 is an almost excess risk minimizer shown in the following Theorem 40 Since our data-deletion guarantee is based on near-indis iaa-iiiiinnnuusabblltyy to (117). this property also ensures near-optimal excess risk of data-deleted models.
42

---

Under review as a conference paper at ICLR 2023
Theorem 40 (Near optimality of Gibbs sampling). If the loss function L(0;x) is o² log lBg(B)/4-
bounded and B-smooth, the regularizer r(0) 0|0 then the excess empirical risk for a model ④ sampled from the Gibbs distribution T(D) x e Lp/a² is
err(O; (CD(()) - 2
B + log
vB)
(131)
A
Proof. We simplify expected loss as
E [CD(O)] ( - -log(
(132)
where
{ Co/oo
Coco2
H(T(D)) = =- T()) log T(D) 1-
log
d8
(133)
Ap
Ap
the differential entropy of TD)). and AD = f -- Loooo d0 is the normalization constant. Since the potential function Lo is (A + B) -smooth, we have
-o² log(Ar) -0² log
e e-oolo d0
CD((%) - 0² log
(CCo(0))
S LD(()) o² log f 1-(0+>110-0311/22> do
da²
1nT²²
CD(())
log
2
X +
Since e(0: x) is 2 (B)/////4ududd,, note that for the Gaussian distribution p ~ N (0, gT).. the
density ratio lies m(D)(0)
+
B for 0 E RR.. We decompose entropy H(T(DD) into
p(0)
E
VB
cross-entropy and KL divergence get
H(π(D)) / TDD log pd0 KL (π(D))lp)
d/2
/ TT(D) log
<
20
d0
(Since KT. (T) 2 0)
2TT
2mo²
log
|101 (D))(O)
20
2
AVB
log
|10112 p(0)do
(Since
((Di(0) p(0)
VB vB
202
2
d/B
log
On combining the bounds, we get
D) - -) < do² ( 3 B+1 + VB)
log
(134)
2 A
Theorem 7 (Accuracy, privacy, deletion, and computation tradeoffs). Let constants X, 3, 02, > q, B > 1. and 0 < Edd I Eap < d. Let the loss function E(0; x) be a² log( B) -bounded, L-Lipschitz and B-smooth, the regularizer be r(0) = |10112- and the weight initialization distribution be N (1a). Then,
43

---

Under review as a conference paper at ICLR 2023
(1.) both GD and CDD are Eqp -RDP for any n 2 0 and any KA. K3 2 Of
qI.²
a²
" "nmax KA Kx),
(135)
Edp??
(2.) pair (ANoiry GD, ANoisy satisfy (g. (-ai---aa--deeeee under all non-adaptive r-requesters and number of iterations satisfy
for any o² O, if learning rate is 1] S B4dg
Aead
2B KA Z Xr
g (
2B An
log(B) (Ead + + log(B))
log
KA 2 KA
log
(136)
Edd
(3.) and all models in sequence (o:) output by (ANoasy ANsss- 2) on any Do X where Q is r-requester, satisfy err err(O,; D,) Ô
dg
gead Edp
when inequalities
Edp
n
in 136 and 135 are equalities.
Proof. (1.) Privacy. By Theorem 24 Noisy-GD with K iterations on an I.-Lipschitz loss function _g.²
satisfies (q, - for any initial weight distribution p and learning rate 2 0f x²
E .
Since, both AND and NNoiy-GD run Noisy-GD for KA and K iterations respectively, setting the noise variance given in the Theorem statement ensures (g, Edp Edp) J-RDP for both.
(2.) Deletion. For showing data-deletion under non-adaptive requests, recall that it is sufficient to show that there exists map X O such that for all >
Ry (A, O.-1) ((())) I Edd,
(137)
for all edit sequences (u:)221 from 21", where (θ,)s20 is the sequence of models generated by the interaction of (ANoisy-GD: ANoisy-GD, Q) on any database Dy X". For all > let ú; denote the distribution Ô; We prove (37) via induction.
Base step: Note that the initial weight distribution p = N L/ has density proportional to
e- == and the distribution r(Do) has density proportional to Cro (0)/a² Since both of these are Gibbs distributions with their potential difference [CD, (0) - r(0) < a² lo/(B)/4 all Re due to boundedness assumption on E(0; x), we have from Lemma 39 that
x 2 o² log(B) log(B) σ2
Ry (pll
(138)
Under the stated assumptions on loss x(0;x) and learning rate note that the convergence Theo- rem 38 holds. Since Ô, = ANoisy-GD (Do) Noisy-GD(Po, Oo, KA), where On p. we have
A
3(dngB(B X)2
Rg (Ho)))((Do) S exx
Rg (Pll)T(Do))
2B
X
$ exp
A
(oog( B)
Ead 2
Aead (Since n S 61dgB(2+2)²
2B
2
(Since KA 2 2B log (lg(BB)
S Ead
An
ead
Induction step: Suppose Rg (|==-| S Ead- Again, from boundedness of E(0; x), we have ra² log for all 0 E Idd. Therefore, from Lemma we have for all q > 2n
[LD,,, - Lp, (f)l s
that
Ry (T((;:))) r Flog B)
(139)
n
So from the weak triangle inequality Theorem 17 of Rényí divergence,
Rg ((.,)l(a(D.)) < Rg (A{=)| + Reo (T(D)=>)(T((.)) s Ead r rlog(B)
(140)
n
44

---

Under review as a conference paper at ICLR 2023
Note
that
K
2 K
28 log Anj
B 2(Eda log (og(B)
log
29(cau log(B))
Since
Xry
6dd
6 = ANoss- GD (Di-1: u1, ②i-1) Noisy-GD(C) 0 Kx), from convergence Theorem
38 we
have
AnKA
32 + X)²
Rg (H:lI((D)) gexp
Rg ((/=1|[<(D)))
2B
A
A A
rlog(B)
Edd
S gexp
Edd +
2B
n
(From (140) and constraint S ((44)(0+X)*
Aead
S sdd-
(Since Ka
28 log An)
24(Eaa Bog( 6dd
Hence, by induction, Rg ((:)) & Ead holds for all i2 0.
(3.) Accuracy. Let 0.. = arg min LD, (f), and θ ~ r(D;). We decompose the excess empirical risk Noisy-GD as follows:
BER*
err ar; D.) Co. + (O.) LD, (6%
(141)
The second term is the suboptimality of Gibbs distribution and by Theorem 40 it is bounded as
E (O,) Lp. (05,)] do²
8 +
log
VB
(142)
Due to I-LLischitzness and (A + smmoothness of LD.,, for any coupling IT of Ô and G; the first term is bounded as
-o, < (VLD ( (O.), 6.)
A+
6 0. 0.13]]
IE (0.)
2
o. 6, 6.1[]
X B
6 +
$ L
E
2
2
(From Jensen's 's inequality)
Recall that the distribution r(D) satisfies LS(A/ B) inequality. On choosing the coupling II to be the infimum, we get the following bound on Wasserstein's 's distance from Lemma 22
|| [ 6, W2 (0., S
2Bo² KL (n. [[((( S
28 Bo²
inf 1I1
A
(143)
The last inequality above follows from monotonicity of Rényi divergence and the fact that = KL (vllv'). Therefore, combining all the bounds get
-im 1 R2 (vllv')
2Eaa
+ Eda Bo B) do2 log
3+
( D) s Lo
VB = = + do?). =oo
A
A
(144)
Note that if the constraints on KA and K3 in (36) and on (35) are equalities instead, we have
BT² X2dp
q glog( B)
o²
log
(145)
Ead
Edpp?
where Ō(-) hides logarithmic factors. Therefore, the excess empirical risk has an order
err(O; D) =
gaad + dg
(146)
nz Edp
Eap
45


Reviews:
[{"review_id": "adWB_e2ID8w", "reviewer": "Reviewer_vRVP", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The authors consider the definition of unlearning developed in previous work. The paper claims that these definitions do not satisfy the true meaning of unlearning as data could be added back in at later points in time. To this end, the propose that the new definition should be stateless and algorithms for deletion and training should satisfy DP-like guarantees.", "summary_of_the_review": "The paper makes an observation that some of the existing unlearning definitions may not capture all properties one needs from unlearning. This is an important observation. It suggests a new definition. However, without clear threat model and attack capabilities it is difficult to evaluate whether it is the definition that fails or the assumptions on the attacker that fail. The method and the paper could also be presented in a clearer way (e.g., with counter-examples that follow previous definitions an show how they fail).", "strength_and_weaknesses": "Strengths:\n- the problem of unlearning is important\n- observation that the data maybe added later on is an important one\n\nWeaknesses:\n- missing threat model\n- the definition requiring an algorithm to be stateless does not seem to be intuitive (see below)\n- the adaptive vs non-adaptive aspect is confusing\n- summary of where and which previous definitions fail is missing\n\n\nObservation: this paper provides a theoretical result.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "T_TMcq4uMo", "reviewer": "Reviewer_JXqD", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "", "summary_of_the_paper": "The paper looks at the problem of ensuring the right-to-be-forgotten (RTBF), under multiple adaptive edit requests to the dataset. The paper has three main contributions (a) they show that the machine unlearning definitions used in the prior works are not sufficient to ensure RTBF, especially when the edit requests are adaptive (they show that it is neither sound nor complete), (b) They provide a new definition for data deletion, (c) They provide an analysis of noisy-SGD algorithm under this new definition. This is a completely theoretical paper and there are no experiments. \n\n", "summary_of_the_review": "As the paper stands, I recommend rejecting it. I feel that the authors are trying to create a wrong impression of the current machine-unlearning literature, which is my primary reason for rejection.  I also feel that the paper is incomplete (as discussed more in the weaknesses). In particular, it is not clear whether DP is actually necessary for deletion in the adaptive setting (as claimed by the authors), and whether their new definition is sound or complete. ", "strength_and_weaknesses": "Strengths: The paper considers the important question of properly defining data deletion and gives algorithms for data deletion, in the adaptive and online unlearning setting. The paper provides a rigorous theoretical exploration of issues of a prior definition, and a fix to it. \n\nWeaknesses: \n1. I think the paper creates a misleading impression of the prior works, as:  \n  - They only consider the setting of iterative unlearning (multiple {adaptive or non-adaptive} unlearning requests) which, in my opinion, does not comprise the fundamental deletion setting. In particular, the two-stage setting that consists of a single learning state, and a single unlearning stage (to unlearn K many points) has been completely ignored in the paper. All their constructions to invalidate the soundness of machine unlearning definition completely breaks down in this setting. \n\n \n  - They only consider the indistinguishability definition of Neel et. al. 2021, Gupta et. al. 2021, and extrapolate the failure of these definitions under adaptive queries to argue that all prior machine unlearning works are wrong/incomplete. Contrary to how they pose the prior works, there already exist definitions in the literature that are both sound and complete. Consider the definition of Sekhari et. al. 2021 - It is sound as there is no f_publish and only two stages of interaction, and complete since it only compares the output after the unlearning state (on both original and updated datasets) and hence, an unlearning algorithm that outputs a fixed untrained model is a valid unlearning algorithm. \n\n\n\n\n2. Following up on the above comment, Theorem 3 only holds when there is a separate f_publish, but not all unlearning definitions distinguish f_publish and algorithms output (e.g. Sekhari et. al. 2021, Ginart et. al. 2019). \n\n3. The authors claim in the abstract, and in various places in the paper, that it is necessary to satisfy DP to ensure true data deletion. I do not see any formal claim anywhere arguing that DP is necessary. From the definitions and results, it seems to be a sufficient condition rather than a necessary one. Please elaborate. \n\n4. What are the DP guarantees for the noisy SGD algorithm in Algorithm 1. Is it the exact same noise as DP-SGD? Are the authors essentially running a pure DP algorithm, and then just arguing in hindsight that it is also unlearning? \n\n5. In the analysis for noisy SGD, the authors only consider empirical risk guarantees. Do the benefits over retraining (reported in Table 1) also hold when we care about test loss performance? \n\n6. Do the authors have any proof that their definition of data deletion is sound or complete? \n\n7. The risk of adaptive unlearning requests was also previously explored by Gupta et. al.\n\n8. Minor issues and typos:\n   - Definition 2.5, eqn 8 is not clear. I feel it will help to elaborate a bit more on what it means. \n   - Definition 4.1 has a typo “all edit requests u = … \\in U^{i}” instead of U^1. \n   - Independence is defined for two random variables (and not two distributions).  Please fix the paper to not use phrases like “there exists a distribution \\pi_i^u that is independent of the record being deleted” (e.g. in defn 4.1). This is not mathematically consistent. \n   - Change the notation R to denote the unlearning algorithm (it is confusing as R should ideally be used to denote the retraining algorithm). \n\nI would be happy to engage further with the authors on any of the above comments. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "RbY89eRsFzI", "reviewer": "Reviewer_hke4", "summary": "", "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": "", "summary_of_the_paper": "The paper challenges the unlearning criterion used in prior works, indistinguishibility to retraining, for ensuring the right to be forgotten guideline. They argue that this criterion itself is neither complete nor sound. The authors then propose a new unlearning criterion and design learning and unlearning algorithms for the problem of optimizing smooth convex and non-convex losses.", "summary_of_the_review": "Overall, I think that this paper rigorously challenges the existing formulation of a problem which has been used in multiple prior works and thus is important. The paper is well-written and I enjoyed reading the paper. I have some concerns and suggestions about some technical details of their claims (see above), and I hope that the authors response would help towards addressing these.\n\n-----\nUpdate: Score changed from 8 to 6 owing to potentially significant update to the paper post release of first set of reviews.", "strength_and_weaknesses": "Strengths\n\n1. The problem and the message of the paper is definitely interesting and important especially since the area of machine unlearning is up and coming. It rightly distinguishes between the unlearning criterion used in prior works (indistinguishibility to retraining) and the informal goal of implementing the right to be forgotten guideline.\n\n2. The paper is well-written and presents a systematic investigation of deficiencies in prior abstraction of the problem. Furthermore, it contributes new and compelling language to capture various important entities and their interaction in unlearning properties and to imbibe desirable properties towards a definition. \n\nWeaknesses and questions:\n\nAdmittedly, some of the weaknesses I list below may stem from my potentially incorrect understanding, so I would be grateful if the authors can correct me if I am missing something.\n\n**Proposed definition**: The authors show that the prior definition of unlearning is neither complete nor sound. To remedy this, the authors propose a new definition. However, it seems that the authors do not show that this new definition satisfies (some degree of) soundness and completeness, apart from informal justifications. Is there a rigorous argument here? If yes, please point me to it in case I missed it.\n\n**Problem with internal data strucutres**: One of the key requirements that the authors posit in desirable unlearning algorithms is that they don't maintain any internal data-structure. Their key argument towards this are Thms 3 and 4 wherein they construct problems and a valid learning/unlearning pair with internal state such that after some updates, an adversary can infer a deleted record. However, it seems to me that this is possible even with no internal state. Consider the problem of mean (or sum, for simplicity) estimation and the perfect learning/unlearning pair for it. For all 1-non-adaptive requester, an adversary can completely recover its data record by subtracting the updated estimate from the original estimate, right? \nIf the above reasoning is correct, then there is something missing in the deduction of the stateless requirements from Thm3/4.\nWhat am I missing here?\n\nRelatedly, I don't understand what *unsafe* means in the context of internal data-structures? For example, in Table 1, the authors correctly list that the prior work of Ullah et al. maintain internal data-structure, but therin, the unlearning being indistinguishable to retraining criterion is applied not just to the model output but the internal data structure as well. In that case, is this still considered unsafe? If yes, then can the authors provide a rigorous definition of safety here?\n\n\n**Reduction from adaptive to non-adaptive updates**: The recent work of Gupta et al. 2021 also studied machine unlearning against adaptive updates and similarly proved  reductions (as the authors do) using differential privacy. However, a key difference is that Gupta et al. required DP to hold with with regard to a change of description of internal randomness as opposed to standard data item replacement. I understand that the notion of unlearning is different in both papers, but I wonder if there is something more which allows the authors to use standard DP?\nIn any case, the authors should provide a discussion on differences with the result in the aforementioned work, which is currently missing.\n\n**New definition but similar algorithmic techniques**:\nAs an example, authors study the design of learning and unlearning algorithms for smooth convex empirical risk minimization under their proposed unlearning criterion.\n The authors' proposed method is based on Noisy gradient descent from the differential privacy literature. This (or its variants) is the method used in many prior works on unlearning (albeit some are stateful, which the authors discard owing \"safety\" issues). I wonder therefore if it is possible to a-posteriori reason about their unlearning properties (with possibly worse parameters) in the language proposed by the authors. Or is there something fundamental in the algorithmic differences of the authors proposed method?\n\n**Computational savings in Noisy GD**:\n The authors argue that their unlearning method based on Noisy GD demonstrates non-trivial savings of computation compared to retraining with their learning algorithm (Noisy GD).\nHowever, noisy \"full\" gradient descent is an inefficient (in the sense of gradient complexity) method for the problem of (privately) optimizing smooth convex losses -- it seems that the gradient complexity is $O(\\kappa n)$ whereas there exists private methods based on SVRG with $O(n+\\kappa)$ gradient complexity or even better.\nNow, if retraining were a viable unlearning method, the this computational savings of retraining over a slow learning method may be problematic. \nIn any case, ideally, we would want unlearning methods for fast learning methods for the problem.\nSo, it would be good if the authors can expand on if there is something important about the structure of Noisy GD updates, or is it possible to obtain the same results via a faster but (a somewhat) black-box DP optimization routine.\n\n\n**Elaboration of proof techniques**:\nThe authors mention that \"...techniques we develop for analyzing data deletion differ tremendously from those used to argue differential privacy\". It would have been useful if the authors could include some more details on this claim (maybe some key lemmas) in the main text itself.\n\nMinor:\n\nIn the conclusion, the authors state that \"we showed that differential privacy is necessary for data deletion when requests are adaptive\". I did not see such a strong claim formally in the paper.\n\nTypo? -- In page 2, the authors say \"B) generates models that are indistinguishable from any distribution independent of the deleted records\". Based on their definition 4, shouldn't it be \"from some distribution independent of the deleted record\"? \n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "KFJqE-GvyQq", "reviewer": "Reviewer_4yeU", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper investigates whether the existing definitions for machine unlearning are ‘complete’. Prior works on machine unlearning defined ‘certified unlearning’ (at a high level) as indistinguishability from retrained models. This paper argues that this is incomplete, and demonstrate two vulnerabilities (Theorems 3 and 4) such  that a majority of existing unlearning guarantees suffer from one of them. Then, the paper proposes a stronger definition of unlearning, and uses it to propose objectives for data deletion. Finally, the paper analyzes convex and non-convex loss functions to that DP-GD (noisy GD) satisfies the proposed objectives. ", "summary_of_the_review": "The paper asks important questions about machine unlearning, and shows some interesting results. However, the presentation can be significantly improved, and some details need to be added. ", "strength_and_weaknesses": "**Strengths:**\n1. The problem of machine unlearning (data deletion) is practically relevant and technically challenging. It is important to analyze current methods and develop new definitions of data deletion in ML.\n\n**Weaknesses:**\n1. The paper does not provide sufficient details on how the compute savings are calculated. Data deletion method proposed in Def. 5.1 is essentially retraining the model using noisy-GD (DP-GD). Since it also performs retraining (but with noisy-GD, it is not clear how the compute savings in Table 1 are calculated. It is important to add more details on this.\n\n2. The paper does not discuss how the reduction result in Theorem 5 relates to the reduction result in [Gupta et al. 2021]. It would be helpful to give more details. \n\n3. The paper does not present any empirical results to support the theory. In contrast, many prior works including [Gupta et al. 2021] present some empirical results to corroborate the theory.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Decision: Reject