From Adaptive Query Release to Machine Unlearning
Authors: Enayat Ullah
Raman Arora
Venue: Submitted to ICLR 2023 (2023)
Keywords: machine unlerarning
stochastic convex optimization

Abstract: We formalize the problem of machine unlearning as design of efficient unlearning algorithms corresponding to learning algorithms which perform a selection of adaptive queries from structured query classes. We give efficient unlearning algorithms for linear and prefix-sum query classes. As applications, we show that unlearning in many problems, in particular, stochastic convex optimization (SCO),  can be reduced to the above, yielding improved guarantees for the problem. In particular, for smooth Lipschitz losses and any $\rho>0$, our results yield an unlearning algorithm with excess population risk of $\tilde O\big(\frac{1}{\sqrt{n}}+\frac{\sqrt{d}}{n\rho}\big)$ with unlearning query (gradient) complexity $\tilde O(\rho \cdot \text{Retraining Complexity})$, where $d$ is the model dimensionality and $n$ is the initial number of samples. For non-smooth Lipschitz losses, we give an unlearning algorithm with excess population risk $\tilde O\big(\frac{1}{\sqrt{n}}+\big(\frac{\sqrt{d}}{n\rho}\big)^{1/2}\big)$ with the same unlearning query (gradient) complexity. Furthermore, in the special case of Generalized Linear Models (GLMs), such as those in linear and logistic regression, we get dimension-independent rates of $\tilde O\big(\frac{1}{\sqrt{n}} +\frac{1}{(n\rho)^{2/3}}\big)$ and $\tilde O\big(\frac{1}{\sqrt{n}} +\frac{1}{(n\rho)^{1/3}}\big)$ for smooth Lipschitz and non-smooth Lipschitz losses respectively. Finally, we give generalizations of the above from one unlearning request to dynamic streams consisting of insertions and deletions.

Under review as a conference paper at ICLR 2023
FROM ADAPTIVE QUERY RELEASE TO MACHINE UN- LEARNING
Anonymous authors Paper under double-blind review
ABSTRACT
We formalize the problem of machine unlcarning as design of efficient unlearning algorithms corresponding learning algorithms which perform selection of adap- tive queries from structured query classes. We give efficient unlearning algorithms for linear and prefix-sum query classes. As applications, we show that unlearning in many problems, in particular, stochastic convex optimization (SCO), can be reduced to the above, yielding improved guarantees for the problem. In particular, for smooth Lipschitz losses and any p > O, our results yield an unlearning algo- rithm with excess population risk of Ō 1 +
va) with unlearning query (gradient) vi npp
complexity Ö(p- Retraining Complexity), where is the model dimensionality and is the initial number of samples. For non-smooth Lipschitz losses, we give an unlearning algorithm with excess population risk Ö( 011 + (x²) 1/2) with the same unlearning query (gradient) complexity. Furthermore, in the special case of Generalized Linear Models (GLMs), such as those in linear and logistic regression, we get dimension-inneeeedeet rates of ( + (mp)a7s) ) and O V + (mo)tzs) for smooth Lipschitz and non-smooth Lipschitz losses respectively. Finally, we give generalizations of the above from one unlearning request to dynamic streams consisting of insertions and deletions.
INTRODUCTION
The problem of machine unlearning is concerned with updating trained machine learning models upon request of deletions the training dataset. This problem has recently gained attention owing various data privacy laws such as General Data Protection Regulation (GDPR), California Consumer Act (CCA) among others, which empower users make such requests the entity possessing user data, The entity is then required to update the state of the system such that it is indistinguishable to the state had the user data been absent to begin with. While as now, there is no universally accepted definition of cedistinguushibiliiy the unlearning criterion, in this work, we consider the most strict definition, called exact unlearning (see Definition for a formal definition).
Motivating Example: for unlearning such that it is more efficient than retraining, the naive baseline method. Towards this, we first discuss the example of unlearning for Gradient Descent (GD) method, which will highlight the key challenges as well as foreshadow the formal setup and techniques. GD and its variants are extremely popular optimization methods with numerous applications in machine learning and beyond.
The main objective of our work is to identify algorithmic design principles
machine learning context, is typically used to minimize the training loss, L(w; S) A Ei E(w; z4) where S = {= is the training dataset and w, the model. Starting from an initial model W1, in each iteration, the model is updated
Wt++ wt 1) VVL S) W:
Σ V((me)))))
After training, a data data-point, say 2n without loss of generality, is requested to unlearnt and so the updated training set is S' = { } We now need to apply an efficient unlearning algorithm such that its output is equal that of running GD on S'. Observe that the first iteration of GD is simple enough to be unlearnt efficiently by computing the new gradient Vi(w:; S') (nVinnii (.))))))) and updating w/ wi ,,Viiw,; However, in the second iteration (and

---

Under review as a conference paper at ICLR 2023
onwards), the gradient is computed on w² which can be different from W2 and the above adjustment can no longer be applied and one may need to retrain from here onwards. This captures the key challenge for unlearning in problems solved by simple iterative procedures such as GD adaptivity i.e,, the gradients (or more generally, the queries) computed in later iteration depend on the result of the previous iterations. We systematically formalize such procedures and design efficient unlearning algorithms for them. We summarize our key contributions below.
1.1 OUR RESULTS AND TECHNIQUES
Iterative procedures are an integral constituent of the algorithmic toolkit for solving machine learning problems and beyond. As in the case of GD above, these often consist of a sequence of simple but adaptive computations. The simple computations are often efficiently undo-able (as in the first iteration of GD) but its adaptive nature- change of result of one iteration changing the trajectory of the algorithm makes it difficult to undo computation, or unlearn, efficiently.
Cearning/Unlearning as Query Release:
As opposed to designing unlearning (and learning) algorithms for specific (machine learning) prob- lems, we study the design of unlearning algorithms corresponding (a class of) learning algorithms. We formalize this by considering learning algorithms which perform adaptive query release on datasets. Specifically, this consists of selection of adaptive queries from structured classes like linear and prefix-sum queries (see Section 3 for details). The above example of GD is an instance of linear query, since the query, which is the average gradient n En= Vl(ws; 2,), is linear in the data-points. With this view, we study how to design efficient unlearning algorithms for such methods.
We use efficiency in the sense of number of queries made (query complexity). ignoring the use of other resources, e.g., space, computation for selection of queries, etc. To elaborate on why this is interesting, firstly note that this does not make the problem trivial, in the sense that even with unlimited access to other resources, it is still challenging do design an unlearning algorithm with query complexity smaller than that of retraining (the naive baseline). Secondly, let us revisit the motivation from solving optimization problems. The standard model to measure computation in optimization is the number of gradient queries method makes for target accuracy, often abstracted in an oracle-based setup (Nemirovskij & Yudin, 1983). Importantly, this setup imposes no constraints on other resources, yet it witnesses the optimality of well-known simple procedures like (variants of) GD. We follow this paradigm, and as applications of our results to stochastic convex optimization (SCO), we make progress on the fundamental question of understanding the gradient complexity of unlearning in SCO. Interestingly, our proposed unlearning procedures are simple enough that the improvement over retraining in terms of query complexity also applies even with accounting for the (arithmetic) complexity of all other operations in the learning and unlearning methods.
Linear queries: The simplest query class we consider is that of linear queries (details deferred to Appendix B). Herein, we show that the prior work of Ullah et al. (2021), which focused on unlearning in SCO and was limited to the stochastic gradient method, can be easily extended to general linear queries. This simple observation yields unlearning algorithms for algorithms for federated optimization, k-means clustering, etc. Herein, we give a T-TVV stable (see Definition 2) learning procedure with T adaptive queries and a corresponding unlearning procedure with a OVVPp) relative unlearning complexity (the ratio of unlearning and retraining complexity; see Definition 4).
Prefix-sum queries: Our main contribution is the case when consider the class of prefix-sum queries. These are a sub-class of interval queries which have been extensively studied in differential privacy and are classically solved by the binary tree mechanism (Dwork al., 2010). We note in passing that for differential privacy, the purpose of the tree is to enable a tight privacy accounting and no explicit tree may be maintained. In contrast, for unlearning, we show that maintaining the binary tree data structure aids for efficient unlearning. We give a binary-tree based p~TV stable learning procedure and corresponding unlearning procedure with ((p) relative unlearning complexity.
Unlearning in Stochastic Convex Optimization (SCO): Our primary motivation for considering prefix-sum queries is its application to unlcarming in SCO (see Section 2 for preliminaries).
1. Smooth SCO: The problem of unlearning in smooth SCO studied in Ullah et al. (2021) which
2/3 where p is the relative
proposed algorithms with excess population risk of O
+
2

---

Under review as a conference paper at ICLR 2023
Problem
Base algorithm
Rate
Smooth, Lipschitz-SCO
Variance Reduced- -rankk Wolfe
vd
yn
d'74
Lipschitz SCO
Dual Averaging
+
yn
vip
Smooth, Lipschitz GLM
JL + Variance Reduced-Frain Wolfe
vn (mp)2/3
Lipschitz GLM
JL Dual Averaging
vn
(mp)
Table 1: Excess population risk guarantees for various problems well as the base algorithm; p: relative unlearning complexity (see Definition 4), JL: Johnson-Lindeestrauss transform.
unlearning complexity. We show that using variant of variance-reduced Frank-Wolfe (Zhang et al., 2020), which uses prefix-sum queries, yields improved excess population risk of O (
va
mp
2. Non-smooth SCO: In the non-smooth setting, both algorithms proposed in Ullah et al. (2021) have trivial guarantees. Instead we give an algorithm based on Dual Averaging (Nesterov, 2009), which again uses prefix-sum query access, and thus fits into the framework. This algorithm gives us an excess population risk of O V
d1/4
Vap
3. Generalized Linear Models (GLM)): Generalized linear models are one of most basic machine learning problems which include the squared loss (in linear regression), logistic loss (in logistic regression). hinge loss (support vector machines) etc. We study unlearning in two classes of GL.Ms (see below), for which we combine recently proposed techniques based on dimensionality reduction (Arora et al., 2022) with the above prefix-sum query algorithms to get the following dimension-indepeedent rates.
3(a). Smooth GLM: For the smooth GLM setting, we combine Johnson-Lindensttrnn transform
with variance reduced Frank- Wolfe to get O V (mp)273 excess population risk. Note that we get
no overhead in statistical rate even with very small relative unlearning complexity, p n -1/4, This
class of smooth GLMs contains the well-studied problem of logistic regression. Hence, our result demonstrates that it is possible to unlearn logistic regression with sub-linear (specifically, O(n3/4) unlearning complexity with no sacrifice in the statistical rate.
3(b). Lipschitz GLM: Similarly, for the Lipschitz convex GLM setting, we combine Johnson- Lindenstrauss transform with dual averaging yielding a rate of Ō + [3p)
Please see Table 1 for a summary of above results.
SCO in dynamic streams: Finally, we consider SCO in dynamic streams (details deferred to Appendix F) where observe sequence of insertions and deletions and are supposed to produce outputs after each time-point. In this case, we present two methods: one which satisfies the exact unlearning guarantee with worse update time, the other which satisfies weak unlearning (see Definition 9) with improved update time. The exact unlearning method is inspired from the work of Ullah et al. (2021) which dealt with insertions similar deletions. The weak unlearning method motivated from the observation that the above may be too pessimistic. To elaborate, inserting a new data item does not warrant a (unlearning) guarantee that the algorithm's 's state be indistinguishable the case the point was not inserted. Hence, insertions should require smaller (ideally, constant) update time which is indeed the case for our proposed methods.
1.2 RELATED WORK
Our work is direct follow up of Ullah al. (2021) which proposed the framework of Total Variation (TV) stability and maximal coupling for the exact machine unlearning problem. They applied this to unlearning in smooth stochastic convex optimization (SCO) and obtained a guarantee \ + va ap
on excess population risk, where n is the number of data samples, d, model dimensionality and the relative unlearning complexity (see Definition 4). We improve upon the results in that work in multiple ways as described in the preceding section. Furthermore, the exact unlearning problem has been studied for k-means clustering (Ginart et al., 2019) and random forests (Brophy & Lowd, 2021). The work of Bourtoule et al. (2021) proposes a general methodology for exact unlearning for deep learning methods but do not provide rigorous theoretical guarantees on accuracy, even in simple settings. Besides this, there are works which consider unlearning in SCO, however they use an approximate notion of unlearning inspired from differential privacy (Guo et al., 2019; Neel et al., 2021: Sekhari al., 2021; Gupta et al., 2021), and therefore are incomparable to work.
3

---

Under review as a conference paper at ICLR 2023
2 SETUP AND PRELIMINARIES
Let 2 be the data space, W be the model space and .M be the meta-data space, where meta-data is additional information learning algorithm may save to aid unlearning. We consider a learning algorithm as a map A Z + W M and an unlearning algorithm as a map U W x M Z + W x M. We use A and 24 to denote the first output (which belongs to W) of A and U respectively.
We recall the definition of exact unlearning from Ullah et al. (2021) which requires that the entire state after unlearning be indistinguishable from the state obtained if the learning algorithm were applicd to the datasct without the deleted point.
Definition (Exact unleaming). A procedure (A, U) satisfies exact unlearning if for all datasets S. all x E 2, for all events & W x M, we have, IP (S) E E) = P
2) E E)
Unlearning request:
We consider the setting where we start with a dataset of samples and observe one unlearning request. We assume that the choice of unlearning request is oblivious to the learning process. In Section F, we generalize our result to the streaming setting.
Total Variation stability, maximal coupling and efficient unlearning: The Total Variation (TV) distance between two probability distributions P and Q is TV(P, Q)
sup measureable g Next, we define Total Variation (TV) stability, which was introduced in Ullah et al. (2021) to motivate algorithmic techniques for efficient unlearning.
|P(E) Q(E)).
Definition 2. An algorithm A is said to be p Total Variation stable if for all datasets S and S differing in one point, i.e. |SAS|| = 1, the total variation distance, TV (A(S), S
Given two distributions P and Q, coupling is a joint distribution π with marginals P and Q. Furthermore, a maximal coupling is a coupling π such that the disagreement probability P(a.y)~ {a # y) TV(P, Q). In the unlearning context, P = A(S), the output on initial dataset, and Q A(S"), the output the updated dataset. Hence, the unlearning problem simply becomes about transporting P to Q with small computational cost, akin to optimal transport (Villani, 2009). Furthermore, when sampled from a maximal coupling between P and Q. by definition, we get the same sample for both and Q, expect with probability p. and yet satisfying the exact unlearning criterion. The main idea is that for certain learning algorithms of interest, during unlearming, we can efficiently construct a (near) maximal coupling of P and Q, and so the same model output from P suffices for Q, most of the times. partieular, the fraction of times that we need change the model is the TV-stability parameter p of the learning algorithm. The goal, therefore, is to design an (accurate) TV-stable learning algorithm and a corresponding efficient coopling-based unlearning algorithm. In this work, we use the technique of reflection coupling described below.
Reflection Coupling (Lindvall & Rogers, 1986): Reflection Coupling is a classical technique in probability maximally couple symmetric probability distributions. Consider two probability distributions P and Q with means u and w/ and let r be a sample from P. The process involves a rejection sampling step on the two distributions and sample r (see line 13 in in Algorithm 3). If it results in accept, we use the same r as the sample from Q, otherwise, we apply the following map: Reflect(u, u', r)
u' + r, which gives the sample from Q (see line 16 in Algorithm 3).
Our algorithmic techniques borrow tools from differential privacy (Dwork et al., 2014) such as its relationship with Total Variation stability; we describe these in Appendix A.
Stochastic Convex Optimization (SCO): SCO is the dominant framework for computationally- efficient machine learning. Consider a convex (constraint) set W and let D denote its diameter. Let e: W Z + IR be loss function, which is convex in its first parameter V/2 Z. Given n i.i.d. points from an unknown probability distribution D over Z, the goal is to devise an algorithm, the output of which has small population risk, defined as (ww; D)
E f(w: 2). The excess population 2CD
risk is then Lww; D) - Lww";2 D) where w" denotes a population risk minimizer over W.
Generalized Linear Models (GLM): Generalized Linear Models (GLMs) are loss functions typ- ically encountered in supervised learning problems, like linear and logistic regression. Herein, f(w; (x. v)) = Φy (ww,))), where dy IR- - R is some function. We use ||-e to denote the radius bound on data points, i.e. for x E X C Rd. |||||| < || In this case, consider the unconstrained rates for GLMs, similar to what happens under differential privacy (Jain& & Thakurta, 2014; Arora al., 2022).
setup ie. W Rd, as it allows to get camension-indepeniee
4

---

Under review as a conference paper at ICLR 2023
Algorithm I Template learning algorithm
Input: Dataset S, steps T, query functions { {ge())eeT where y E Q, a query class, update functions (U(O)er selector function S(.)
1: Initialize model w1 E W
2: for = 1 to T do
Query dataset u, = qi (wwidige:))
4: Update 11+1 = Up(Weitissn
5: end for
Output: @ S (fweles))
We introduce the Johnson-LLindenstraus property below which is crucial to our construction.
property). A random matrix & E Rexd satisfies (3.7)-JL property for any u, v E IR, with probability at least 1- 7 (1K Dv) (u, e) 2 $ |/ [|e|]) <.
Definition 3
There exists many efficient constructions of such random matrices (Nelson, 2011).
UNLEARNING FOR ADAPTIVE QUERY RELEASE
We now set up the framework of adaptive query release, which is lens view (existing) iterative learning procedures; this view is useful in our design of corresponding unlearning algorithms. Iterative procedures run datasets consist of sequence of interactions with the dataset; each interaction computes certain function, or query, on the dataset. The chosen query is typically adaptive. i.c., dependent on the prior query outputs. We consider iterative learning procedures which are composed of adaptive queries from a specified query class. Formally, consider query class Q WW x2"; herein, each query in Q is function of a sequence of [w;}.c (lypically, prior query outputs), and the dataset S, with output W. With this view, we give general template of learning procedure as Algorithm 1, where {Ut), and S are the update and selector functions internal to the algorithm.
We deseribe the query model which we measure computational complexity. Under the model, a query function q( ( SS) takes (S] unit computations (or queries, for brevity) for any q and {wi}.- In our applications SCO, this will correspond to the gradient oracle complexity.
Query Model:
Our algorithmic approach to unlearning rooted the relationship between TV stability and maximal couplings. With this view, for specified query class, we have the following requirements.
1. TV-stability: We want a p-TV stable "modification" (clarified later) of the learning Algorithm
2. Efficient unlearning algorithm: We measure efficiency as the average number of queries the unlearning algorithm makes relative to the learning algorithm (retraining), defined as follows.
Definition 4 (Relative Unlearning Complexity). The Relative Unlearning Complexity is defined as [A,, [Query complexity of unlearning algorithm U]
EA [Query complexity of learning algorithm A]
For p-TV stable learning algorithm, we want that the relative unlearning complexity is (close to) p. This because our proposed unlearning algorithm constructs a (near) maximal coupling the learning algorithm's output under the original and updated dataset. This means that unlearning algorithm changes the original output (under the original dataset) with probability at most p we want that in this case, the unlearning algorithm makes number of queries akin to retraining. We also want that in the other case when it does change the output, makes a small (ideally, constant) number of queries. We note that relative unlearning complexity, in itself, does not completely capture the unlearning algorithm is good, since it may be the case that the corresponding learning algorithm is computationally more expensive than other existing methods. However, in our applications to SCO (Section 5), all the learning algorithms are linear time, so the denominator in the definition above is small as it can be (asymptotically). i.c. ((2).
3. Accuracy: We will primarily be concerned with correctness of the unlearning algorithm and its efficiency. In the applications (Section 5), we will give accuracy guarantees for specific problems, where we will see (roughly) that if the learning algorithm is noise-tolerant, then the solution produced by the proposed TV stable modified algorithm are still accurate.
5

---

Under review as a conference paper at ICLR 2023
4 PREFIX SUM QUERIES
We now consider prefix-sum queries, which is the main contribution of this work. The reason for considering this query class is that two powerful algorithms for SCO, dual averaging and recursive variance reduction fit into this template. We start by defining a prefix-sum query.
Definition 5. A set of queries h4 where qr : W x z + W are called prefix-sum queries if q1 (w1, S) Pi (W1, and for all 1, go( (e(( Jic+ 5) q:-1 q1=(((;))ea + pe ((Willggr 2x) for some functions (pe)tg1 where ps : W x W.
Simply put, prefix-sum queries, sequentially query new data points and adds them to the previous accumulated query. A simple example is computing partial sums of data points (2), 21 + 22; 22....). Note that in the above definition, we can equivalently represent the prefix-sum queries using the sequence {e We also assume that the queries have bounded sensitivity, defined as follows.
Definition 6. query q W x -W B-sensitive if
sup sup |lq (fwi), .) q (fwi), S')ll S B. (w)), 8,8" |
We note that the bounded sensitivity condition is satisfied in variety of applications; see Section 5.
4.1 LEARNING WITH BINARY TREE RATA-STRUCTURE:
The learning algorithm, given as Algorithm 2, is based on answering the adaptive prefix-sum queries with the binary tree mechanism (Dwork et al., 2010). For n samples (assume is a power of two, otherwise we can append dummy "zero" samples without any change in asymptotic complexity), the binary tree mechanism constructs a complete binary tree ' with the leaf nodes corresponding to the data samples. The key idea in the binary tree mechanism is that instead of adding fresh independent noise to each prefix-sum query, it is better to add correlated noise, where the correlation structure is described by binary tree. For example, suppose want to release the seventh prefix-sum query, Ei=p Pi(((; ) 2i), then consider the dyadic decomposition of 7 as 4, 2 and 1, and release the sum (Eiz (
&1) (Ei=s (((w)))sss 2.) + 22) (pr((w,) Jgs 2:) + Es) where &, denote the added noise, which may have also been used in prior prefix-sum query responses. See Figure I for a simplified description of the process.
We index the nodes of the tree using using binary numbers == {0, 1] log(() which describes the path from the root. Let the tree T = [ub which denotes the contents stored by the learning algorithm. Herein, each node contains the tuple (u, r, w, =) where u E IRd is the query response, r E IRd is the noisy response, w E Rd model and z E Z a data point. In fact, only the leaf nodes store the model and data sample. Finally, define leaf [n]] - f0, 1] log(n) which gives the binary representation of the input leaf node.
This binary tree data structure supports the following operations:
1. (u, o; T): Add a query response u, perturbed by noise of variance 0², to T, which involves adding noisy u to uy for in the path from leaf to root.
2. GetPrefixSum(t; T), where & E N: Get the t-th noisy response from T.
3. Get(I; T) where E {0, 1} log(n); Get all items in the vertex of T indexed by b.
4. Set(bb v; T) where E (0, 1] log(n); Set the contents of vertex b the T as v.
Following Guha Thakurta & Smith (2013), we give pseudo-codes of the above operations in Section C, with minor modifications to aid the unlearning process.
4.2 UNLEARNING BY MAXIMALLY COUPLING BINARY TREES
The unlearning Algorithm 3 is based on constructing (near) maximal coupling of the binary trees under current and updated dataset. Let zj be the element to be deleted and let U, be the leaf node which contains žj (we use z in place of zj from here on, for simplicity). During unlearning, we simulate (roughly speaking) the dynamics of the learning algorithm if the deleted point was not present to begin with. In that case, in place of the deleted point, some other point would have been used. Now, since the dataset and thus we can use the point 2' in the last leaf node, say Ut in the tree this choice of the last point is important for unlearning efficiency. Firstly, the computations associated with the last point z' needs
randomly permuted, every point is equally likely to have been used,

---

Under review as a conference paper at ICLR 2023
G
E
VINC
PIENS
RS,
Figure I: A simplified schematic of the learning (left) and unlearning (right) procedures for prefix- sum queries. In the left, the leaves contain (noisy, if + prefix-sum queries applied on the randomly permuted data-point (2,'s) below it. The intermediate nodes with adds the not-noised values of its children, where others add noise to it. On the right, the deleted point is replaced with which amounts to adjusting the queries with -g + g' (see Algorithm 3 for details) and performing Rejection Sampling (abbreviated RS; where, indicates the order of occurrence) along the height of the tree.
Algorithm 2 TreeLearn (fv; T)
Input: Dataset S, steps T, B-sensitive prefix queries {pr).gr update functions (Ut).ST. o
1: if tu then Permute dataset and initialize T end if
2: (',,WWa:')
(et(lea((();; do
3: to to |||
4: dr p(((we)see ze)
5: Append(u,, T)
6: re = GetPrefixSum((; T)
7: W++1 = Uz ((wr)
8: Set(leaf(t), (ug Tey wes 7))
9: end for
Output: ã S (fwi))
to be undone - towards this, we update the contents of the nodes the path from node by to root (line 5), finally removing node 2, from the tree (line 6). Then, we need to replace all the computations which used the deleted point z with the same computation under z'. Since the learning algorithm was based on the binary tree mechanism, the point was only explicitly used in the nodes from leaf v, to the root (so, at most log (11 nodes). We say explicitly above because due to the adaptive nature of the process, in principle, all nodes after v, depend on it, in the sense that their contents would change the response in v, were to change. However, importantly, the binary search structure of our learning algorithm and our coupling technique (details below) would enable us to (mostly) only care about explicit computations.
We first compute two new queries, under the data point and 2', with responses g ( gs and o = Py (1 (w, (g =²) respectively (line 3). Starting with leaf node v., we update the original unperturbed prefix-sum query response under i.c. u to what would have been under data-point gf + (line 11). Further, since the training method adds noise (O, o²l) to u to
z': v' produce original noisy response r, we now need to produce sample from N/u', a to satisfy exact unlearning. Naively, we could simply get a fresh independent sample from N N(u,, II),, however, this would change the noisy response r, and hence require all subsequent computations to redone (the adaptive nature). So, ideally, we want to reuse the same r and yet generate a sample from ((u', II).. This is precisely the problem of constructing a maximal coupling, discussed in the Section 2, wherein we also discussed the method of reflection coupling to do it. This amounts to doing rejection sampling which (roughly) ascertains if response r is still sufficient under the new distribution N(u,, o²T). Specifically we compute the ratio of the probability densities at under the noise added and u', i.e. (rn
Px (r) and compare it against randomly sampled 1ni if it results in accept, we move to parent of the node U.. and repeat. If any step fails, we reflect which generates a different noisy response r', and continue retraining from the next leaf w.r.t. the post order traversal of the tree (the variable ct in Algorithm 3 keeps track of this next node). See Figure for simplified description of the process.
The main result of this section is follows.
Theorem 1. The following are true for Algorithms 2 and 3,
7

---

Under review as a conference paper at ICLR 2023
Algorithm 3 TreeUnlearn
Input: 2j; data point be deleted, internal tree data-structure saved during learning
1: = leaf(j) and Se))
2: (.,, (,,,,2)) = Get(s; 7) and ("'',,,))) 21) Get(l:T)
3: PP
2) and g' Py p 2¹)
4: Let path [1 + - root be the path from / to root.
5: for E path do uy 4b g end for
6: Remove node / from T.
7: Let b = and ct =
8: i [5] then let b end if
9: while b + do
(u, r.) Get(b; T)
11: w' ===---
g'
( then if Unif (0, S SNeW o
12:
13:
i = then Set (u' w. z');
else then Set (u', rr, T) end if
14:
else
Reflect(u, u', r))
16:
if 6 = then
Set(b; (u', 0') ;
18:
w' = -U, ((wg) 95b> GetPrefixSum
19:
Set(b, (u', r', w', :7)
20: else
21:
end Set(b, (u', r/. 0, ():)
22:
23:
TreeLearn(j ct; T) // Continue Retraining break
24:
25:
end if
26:
if is left sibling then ct = ct + 21-1116-11 end if
Set (new) b as binary representation parent of end while
28:
Update dataset S SS {zz}
Output: w {))
1. The learning Algorithm 2 with 0² (og) satisfies p-TV stability.
2. The corresponding unlearning Algorithm 3 satisfies exact unlearning.
3. The relative unlearning complexity is Ô (p)
As discussed in the preceding section, in the Theorem above, have all the properties needed with the unlearning process. We now move on to applications and give accuracy guarantees.
APPLICATIONS
In the following, we describe some problems and learning algorithms. The corresponding unlearning algorithms and its correctness simply follow application of the result of the preceding section, provided we show that uses a bounded sensitivity prefix-sum query. The only other thing to show is the accuracy guarantee of the TV stable modification of the learning algorithm (Algorithm 2).
We use runtime to mean gradient complexity as is standard in convex optimization (Nemirovskij Yudin, 1983). But, as pointed out before, our proposed unlearning algorithm yields similar improvements over retraining, even accounting for other operations in the method.
5.1 SMOOTH SCO WITH VARIANCE REDUCED FRANK- WOLFE
We assume that the loss function w + f(w; 2) H-smooth and G-Lipschitz for all z!. The algorithm use is variance reduced Frank-Woo method where the variance reduced gradient estimate u, is the Hybrid-SARAH estimate (Tran-Dinh et al., 2019) with 7/ I given as,
'A real valued function f(x) is G-Lipschitz and F/-moooth if f((1)) f(x1) s G || J2l an (ff(=)) H || mal respectively.
8

---

Under review as a conference paper at ICLR 2023
U = (1 - 7) (4--1 + V((W);2) - V((wp-1;2() + na Ve(m;;2))
V(((xx))) - (V((w;1122))
++1
We show that the above is a prefix sum query with sensitivity B = 2 + G), thus fits into our framework. The full pseudo-code is given Algorithm 12 in Appendix E. We state the main result below where the accuracy guarantee follows from modifications to the analysis in Zhang et al. (2020). Theorem 2. Let S 1 and & W x Z + R be an H -mooohh G-Lipschitz convex function convex W of diameter D. Algorithm 12, as the learning algorithm, run with o² 64(HD+G)) log")"""""too [m] t0 = and
E+I on a datasel S of iidd samples from 'D oulputs C, with excess population risk bounded as, E [L((;)) D) L(w"; ;D) ( ( Vd
++++
mp
Furthermore, the corresponding unlearning Algorithm 3 (with query and update functions as specified in the learning algorithm), satisfies exact unlearning with Ô (pn) expected runtime.
5.2 NON-SMOOTH SCO WITH DUAL AVERAGING
In this section, we only assume that loss function w + f(w; 2) is G-Lipschitz and convex V 2 Z. Herein, we use dual averaging method (Nesterov, 2009) where the model is updated as follows:
W++1 II Ww 7 Ei= Vi(w; where II denotes the Euclidean projection to the convex set W. The above again is a prefix-sum query with sensitivity G, thus fits into our framework. The full pseudo-code is given Algorithm 13 in Appendix E. The accuracy guarantee mainly follows from Kairouz et al. (2021).
Theorem 3. Let p S and é W x
be a G-Lipschitz convex convex function over a convex set
W of diameter D. Algorithu 13, as the learning algorithm, run with o² 641GPlog log" (n) to 1
p
and 1j 14 (ogla) on dataset S of samples, drawn ii.dd from D, oulputs w with excess (+
Gymp
Furthermore, the corresponding unlearning Algorithm 3 (with query and update functions as specified in the learning algorithm),, satisfies exact unlearning with O (pn) expected runtime.
population risk bounded as E ([((W;D) - L(w"; = [[w"
GD
+
vi
Vn
mp
5.3
CONVEX GLM WITH JL METHOD
Algorithm 4 JL. method
Input: Dataset S, loss function f, Algorithm A, JL matrix + E BRdx Noise variance d²
4 (1<x)) )
2: v = A(e, $S 2G
[| 2H 1x)
Output: T Φ
This JL method, proposed in Arora et al. (2022), a general technique to get dimension- iiieenssoon-nddeeeddenn rate for unconstrained convex GLMs from algorithms giving ciimension-dependee (general) convex losses. The method, described Algorithm 4, simply embeds the dataset into a low dimensional space, via JL matrix & and then runs base algorithm the low dimensional dataset.
rate for constrained
Smooth, Lipschitz GLMs: We assume that by + R is convex, H-smooth and G-Lipschitz for all E D. Using VR-Frank Wolfe as the base algorithm, we get a rate of relative unlearning efficiency of p see Theorem 5 for a precise statement.
[mp]373 with
Lipschitz GLMs: We assume that Φy IR - IR is convex and G-Lipschitz for all E V. We give the following result this case using Dual Averaging as the base algorithm. Using Dual Averaging
as the base algorithm, we get rate of O see Theorem for the precise statement.
vn + (mp)irs) ) with relative unlearning efficiency of

---

Under review as a conference paper at ICLR 2023
REFERENCES
Raman Arora, Racf Bassily, Cristöbal Guzmàn, Michael Menart, and Enayat Ullah. Differentially private generalized linear models revisited. arXiv preprint arXiv:2205.030) 03014, 2022.
Lucas Bourtoule, Varun Chandrasekaran, Christopher Choquette-Chune Choo, 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. IEFE, 2021.
Jean Bretagnolle and Catherine Huber. Estimation des densités: risque minimax. Zeitschrifi für Wadhsscheiniichkeissteerrr und verwandte Gehiete, 47(2): 1979.
Jonathan Brophy and Daniel Lowd. Machine unlearning for random forests. International Conference on Machine Leurning, pp. 1092-1104. PMLR, 2021.
Clément L Canonne. A short note on an inequality between kl and tv. arXiv preprint arXiv:2202.07198, 2022.
Cynthia Dwork, Moni Naor, Toniann Pitassi, and Guy N Rothblum. Differential privacy under continual observation. In Proceedings of the forty-second ACM symposium on Theory of computing, pp. 715-724, 2010.
Cynthia Dwork, Aaron Roth, et al. The algorithmic foundations of differential privacy. Found. Trends Theor Comput. Sci., (3-4))21114077 2014.
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.
Abhradeep Guha Thakurta and Adam Smith. (nearly) optimal algorithms for private online learning in iill-information and bandit settings. Advances Neural Information Processing Systems, 26, 2013.
Chuan Guo, Tom Goldstein, Awni Hannun, and Laurens Van Der Maaten. Certified data removal from machine learning models. arXiv preprint arXiv: 1,0 1,03030, 2019.
Varun Gupta, Christopher Jung, Seth Neel, Aaron Roth, Saeed Sharifi-Malvajiee Malvajerdi, and Chris Waites. Adaptive machine unlearning. Advances in Neural Information Processing Systems, 34, 2021.
Prateek Jain and Abhradeep Guha Thakurta. (near) dimension independent risk bounds for differen- tially private learning. In International Conference on Machine Learning, pp. 476-484. PMLR, 2014.
Peter Kairouz, Brendan McMahan, Shuang Song, Om Thakkar, Abhradeep Thakurta, and Zheng Xu. Practical and private (deep) learning without sampling or shuffling. International Conference on Machine Learning. pp. 5213-5225. PMLR, 2021.
Jakub Konecný, H Brendan McMahan, Felix X Yu, Peter Richtárik, Ananda Theertha Suresh, and Dave Bacon. Federated learning: Strategies for improving communication efficiency. arXiv preprint arXiv:1610.05490 2016.
Torgny Lindvall and L Cris G Rogers. Coupling of multidimensional diffusions by reflection. The Annals of Probability, pp. 860-877 660- 1986.
Brendan McMahan, Daniel Ramage, Kunal Talwar, and Li Zhang. Learning differentially private recurrent language models. arXiv preprint arXiv:/710.0694 2017.
Ilya Mironov. Rényi differential privacy. In 2017 IEEE 30th computer (CSF), pp. 263-275. IEEE, 2017.
symposium
Seth Neel, Aaron Roth, and Saeed Sharifi- Malviii-MMiajjjrdi... Descent-to-dellte: Gradient-based methods for machine unlearning. In Algorithnic Learning Theory, pp. 931-962. PMLR, 2021.
Jelani Jelani Osei Nelson. Sketching and streaming high-dimensional vectors. PhD thesis, Mas- sachusetts Institute of Technology, 2011.
10

---

Under review as a conference paper at ICLR 2023
Arkadij Semenovic Nemirovskij and David Borisovich Yudin. Problem complexity and method efficiency in optimization. 1983.
Yurii Nesterov. Primal-dual subgradient methods for convex problems. Mathematical programming, 120(1):221-259, 2009.
Francesco Orabona. A modern introduction online learning. arXiv preprint arXiv: arXiv:1912..00 1312.1313, 2019.
Ayush Sekhari, Jayadev Acharya, Gautam Kamath, and Ananda Theertha Suresh. Remember what you want to forget: Algorithms for machine unlearning. Advances Neural Information Processing Systems, 34, 2021.
Quoc Tran-Dinh, Nhan H Pham, Dzung T Phan, and Lam M Nguyen. Hybrid stochastic gradient descent algorithms for stochastic nonconvex optimization. arXiv preprint arXiv:1905.05920 0029990000090,,. 2019.
Enayat Ullah, Tung Mai, Anup Rao, Ryan A Rossi, and Raman Arora. Machine unlearning via algorithmic stability. Conference on Learning Theory, pp. 4126-4142. PMLR, 2021.
Tim Van Erven and Peter Harremos. Rényi divergence and kullback-leibler divergence. IEEE Transactions Information Theory, 60(7):3777-382)) 2014.
Cédric Villani. Optimal transport: old and new, volume 338. Springer, 2009.
Yu-Xiang Wang, Borja Balle, and Shiva Prasad Kasiviswanathan. Subsampled rényi differential privacy and analytical moments accountant. In The 22nd International Conference on Artificial Intelligence and Statistics, pp. 1226-1235. PMLR, 2019.
Mingrui Zhang, Zebang Shen, Aryan Mokhtari, Hamed Hassani, and Amin Karbasi. One sample stochastic Trank-wolfe. In International Conference Artificial Intelligence and Statistics, pp. 4012-4023. PMLR, 2020.

---

Under review as a conference paper at ICLR 2023
A ADDITIONAL PRELIMINARIES
We recall some concepts from differential privacy which will be useful in our algorithmic techniques.
Definition
An algorithm A satisfies (ax (o,,e((()Ree)) Rényi Differential Privacy (RDP), if for any two datasets S and S' which differ in one data point (ISAS' = = the a-Rényi Divergence between A(S) and A(S"), with probability densities ((S)) and & defined as follows:
Da (A(S)ILA(S)) = a a-1 In (Jamacccs ( 1- dx
is bounded as, Da(A(S))AA(S)) S E(a)).
RDP satisfies many desirable properties such as adaptive and parallel composition and amplification by sub-sampling (Mironov, 2017: Wang et al., 2019). Furthermore, we give the following lemma which relates TV stability RDP.
Lemma (RDP =
TV-stability). If an algorithm satisfies (a, ((a)))DDDP then it satisfies
(1 (1-exp( ---exp-lin all
e(a)))
-TV stability.
Proof of Lemma 1. From Theorem 4 in Van Erven & Harremos (2014), we have that limD..PPl9)) = ax
KL where (-Il-I-) denotes the Kullback-Leite tions. Finally, we relate the TV distance with the KL divergence using Bretagnolle-Huun HuleereHbrrr bound (Bretagnolle Huber, 1979; Canonne, 2022) which gives the claimed bound.
(KI.) divergence between the two distribu-
B UNLEARNING FOR LINEAR QUERIES
A basic form of query we consider is a linear query, defined as follows.
Definition 8. A query q: W n + W is a linear query if ((w));;)) Exes (fwi);:) ;2g) for some functions Pj W Z W.
We consider the class of B-sensitive linear queries. We give the TV stable modified learning procedure in Algorithm which basically releases the linear queries perturbed with Gaussian noise of appropriate variance.
Algorithm 5 LearnLinearuueries(t:: fo)
Input: Dataset S, initial iteration to, steps T. query functions (9(()) update functions
(U:()))TT. Selector function S(-), noise variance 1: Initialize model w1 E W
2: for = lo to T do
3: Query the dataset u, 9e (fu)lig::s).
4: Perturb:
+ E where ~ NO oTlaa
5: Update w++1 = U. Uu((urchgest))
6: Save (me, re, W++1)
7: end for
Output: To = ((wr)esT)
Note that the underlying probability distribution that the above learning algorithm samples from is Markov chain. The corresponding unlearning procedure, described in Algorithm 6, is based on constructing a coupling between the Markov chains for the current dataset and the dataset without the to-be-deleted point. In particular, results in acceptance, then we proceed to the second iteration and so on. some iteration results in rejection, then we do the reflection step, and continue retraining from there
start from the first iteration, perform rejection sampling, if it
12

---

Under review as a conference paper at ICLR 2023
Algorithm 6 Unlearning algorithm for linear queries
Input: Deleted point 2j.
1: for 1 to T" 1 do
2: (u,, we) Load ()
3: Compute ui
p² (fwslisezz)
A "Niur.0p)(1) (nc) then
4: if Unif (0, S oNief
5: Save (u{)
6:
else
7:
r = reflect(r',, ue, u4)
W++1 = U. ((us)ise>?) r4)
8:
9: SarnLinearQueries
10: break
11: end if
12:
end for
The above is basically the same unlearning algorithm as that of Ullah et al. (2021) but presented in the general context of linear queries. Therefore, it generalizes the framework of Ullah et al. (2021) which was limited to the Stochastic Gradient Descent algorithm. We also remark that linear queries can often be augmented with sub-sampling operator yielding amplified guarantees, as done in Ullah et al. (2021). However, we omit this extension for brevity. The main result of this section is as follows.
Theorem 4. The following are true for Algorithms and 6,
1. The learning algorithm, Algorithm with o² = 64m² nº satisfies p-TV stability.
2. The unlearning algorithm,, Algorithm 6, corresponding to Algorithm 5, satisfies exact unlearning.
3. The relative unlearning complexity is O (PVT).
Proof. This proof simply follows from the observation that the analysis of Ullah al. (2021) only uses the bounded sensitivity linear query structure of the stochastic gradient method for their TV stability bound as well as correctness and runtime of the unlearning procedure.
B. APPLICATIONS
This generalization yields the following applications.
B.2 FEDERATED UNLEARNING FOR FEDERATED AVERAGING
In the federated learning setting, we have C' clients (which typically correspond to user devices) with their own datasets and parameter server (aggregator). A typical, informal, goal is training single globally shared model using all the dataset with small communication between the clients and the server, and without moving any private data (explicitly) to the server. Federated Averaging (Koneený et al., 2016), described in Algorithm 7, is widely used method in federated learning, Note that in the every round of the method, the client outputs, {wf] Temi are aggregated using averaging operation:
C
1 We C
In Algorithm 7, ClientUpdate is function which runs on the client's 's data using the current model wi and problem pecciic-paramett P (such as number of steps, learning rate of some optimization routine). For brevity, we do not instantiate the ClientUpdate function, but usually some variant of stochastic gradient descent is used.
13

---

Under review as a conference paper at ICLR 2023
Algorithm 7 Federated Averaging (Server side)
Input: Number of clients C, number of rounds T. client-specific parameters
I: Initialize model w E W
2: for = 1 to 7 1 do
3: for c to C do
4: wi+1 = ClientUpdate (c, w P)
5: end for
6: W++1 = Ees wi+1
7:
end for
Output: @ = (fwelesr)
Federated Unlearning: In the federated unlearning problem, after model is trained, of the clients requests to remove themselves from the process. The parameter server then needs to update the model (and state) in such way that it is indistinguishable to the state if the client were absent. Hence, this is analogous to the standard unlearning problem with the client playing the role of data point. This analogy also occurs with private federated learning wherein the widely-used granularity of differential privacy is user-level differential privacy (McMahan et al., 2017). In this case, client (potentially containing multiple data items) plays the role of data item, the presence/absence of which is used in the differential privacy definition.
TV-stable learning and unlearning: The model aggregation step (line 6 in Algorithm 7) of the federated averaging method is linear query over the clients. Moreover, the clients output models that are bounded in norm, then it is bounded sensitivity linear query (typically enforced by clipping the updates). Hence, this fits into the template of linear query release method and thus can be modified, as in Algorithm 5 to be TV stable. The corresponding unlearning method is the one given in Algorithm 6.
B.3 LLOYD'S S ALGORITHM FOR M-MES CLUSTERING
In this section, we briefly discuss how an algorithm for k-means clustering fits into the linear query release framework. We remark that the prior work Ginart et al. (2019) gave an unlearning method for this problem based on randomized quantization, which can also be seen specific TV-stable algorithm followed by coupling based unlearning method.
Lloyd's algorithm is a widely used method for k-means clustering. Herein, starting with an arbitrary choice of centers, construct partition the dataset, which thereby gives a new set of centers. This process is repeated for a certain number of rounds. The method is described as Algorithm 8.
We notice again that the updates for every cluster, line 7 in Algorithm 8, is a linear query. hence it fits into the linear query release template and thus learning and unlearning algorithms based linear queries readily follow.
Algorithm 8 Lloyd's algorithm
Input: Number of clusters C, number of rounds T,, dataset S {
1: Initialize centers [we]e
2: for = 1 to T do
3: for c = to C do
21. 26.... 2[Sa1 } f. the set of data aata-points closest to we.
4: Compute S.
5: end for
6: forc- 1 to C do
7: Update w.
[5.
Σ 18,1
2i=1 :i
8: end for
9: end for
Output: CC
14

---

Under review as a conference paper at ICLR 2023
C MISSING DETAILS FROM SECTION 4
In this section, provide pseudo-code of the operations supported by the binary tree data structure.
Algorithm 9 Append(u, o; 7)
Input: Query response u, noise variance a, Tree T
Let be the first empty leaf index
2: path {s + root] be the path from to root.
3: Update Tree(u, path, 0; 7)
Algorithm 10 UpdateTTree(u, path, 0;; 7)
Input: Query response u, Set of nodes path, noise variance a, Tree T
1: for E path do
2: Wb ub +
3:
i is a left child or b is a leaf then
4:
{ ~ (0,00
5:
ub +
6: break
7: end if
8: end for
Algorithm 11 GetPrefixSum(t:7]
Input: E N, Tree T,
1: Initialize g E IRP to 0
2: s + (t)
3: Let path be the path from root.
4: while b + do
5: if b is leaf child b is leaf then
6:
9 y +
7: end if
8: end while
Output: g
D MISSING PROOFS FROM SECTION 4
Proof of Theorem I. The first part of the Theorem follows from Lemma 2 followed by post- processing to argue that the same TV stability parameter holds for the final iterate.
The second part, exact unlearning, follows from Lemma 5 wherein Q denotes the distribution of the algorithm's output run the dataset without the to-be-deleted point.
For the third part, note that the unlearning algorithm 3 makes two queries if no retraining is triggered. retraining triggered, the number of queries makes at most the query complexity of learning algorithm, T Finally, the probability of retraining, from Lemma 6 is at most log (n) p. Combining, this gives the stated bound on relative unlearning complexity.
D.I LEMMAS FOR UNLEARNING
Additional notation:
We first present some additional notation used in the statement and proof of the following lemmas. Let S and S' be datasets before and after the unlearning request. Let P and Q denote the probability measures over the range of tree data-structure, which is I (Rd Rd Rd [n])". induced by the output of learning algorithm S and S' respectively. We order the nodes of the binary tree w.r.t. the post-order traversal of tree. Hence, given two nodes e and o' or their binary representations and s', use & < s' w.r.t the above ordering. Given
15

---

Under review as a conference paper at ICLR 2023
node b, let Po (+ITgb) denote the conditional distribution of the nodes given the prefix nodes of the tree.
Let p be permutation over [n] and ps denote the index on the 6-th node, when b is leaf. Let μ denote the probability, and conditional probability, depending on context, of and Pb. under the random permutation model. Specifically, we use μ(P) and pu(p (Pga) denote the probability of the sequence p and conditional probability of given the previous values.
Let (1) denote the initial binary tree i.e. the one constructed after the algorithm is run on dataset S, and ( be the binary tree constructed after unlearning, Let PP and QP denote the conditional distributions for P and Q respectively given permutation p.
We factor the probability density of P as:
Φp (TO)
II
IT
(1) 2b
II BE
(1) m
(2)
(T
P
bE
Fixing the permutation sequence ()), denote and factor the conditional distribution as,
o (T(")- = II
246 166%% w w0 (T
(1) (1)
BEB
P.
Finally, define response trees 71) and ((2) which only contain the response variables (ro),- More-
over, define distributions P. Pb. PP, PP and Q, Qr. QP Q as before.
first show the the tree T produced by the learning algorithm TV-stable.
Lemma 2. Let 0 p 1, 0, E N. For B-sensitive prefix sum queries, setting a² (4 (n). the response tree data structure T is p-TV stable.
Proof. The proof of privacy of tree aggregation classical in differential privacy, see Guha Thakurta & Smith (2013) for example. The proof has three ingredients: Gaussian mechanism guarantee, parallel composition (to argue that accounting along the height of the tree suffices) and adaptive composition (for accounting along the height of the tree). Since the noise is Gaussian and these composition properties also holds under RDP (Mironov, 2017), therefore we can give an RDP guarantee of E(aa < lo) 64a ap². Finally, using Lemma and numerical simplification since S gives the claimed result.
Recall that is the index of the data item (after permutation) which is deleted. Without loss of generality, assume that the original index of the deleted data-point is n. We first argue the following about the distribution of (1) and p (2).
Lemma 3. For any set F. C [n]r and any set E' C |n - 1]m-1, we have
P Ppm
p
E = =mx(E)
P PP (p(2 ()
F = (n-1(E')
Proof. Since (1) and (2) are discrete distributions, it suffices to argue the above for the atoms.
Firstly, by construction, (1)) ~ and hence the first part is done, For the second part for any sequence h (h+) where h; E [n 1]. Let [h, jl denote the concatenation of and j (the deleted index). By symmetry, the probability
TP Pp (h) = + PaD (h,,)) = (m)
This completes the proof.
We now show transport of the conditional distribution by the unlearning operation.
Lemma 4. For any measurable event F. C R
P (2) E Elp (1) (p (2)
=QD (E).
16

---

Under review as a conference paper at ICLR 2023
Proof. The proof based on induction on the nodes of ((2) in the post-order traversal. Let (v!²))
and (1b be the nodes of the tree arranged in the post-order traversal order. Given j, index of the item deleted, let s = leaf(j). Define prefix(s) and suffix(s), as set of nodes before and after respectively in the < order.
Given an event E S (d and rib, define F as follows:
= where Rd denote the Cartesian product of IR of upto > b but smaller than or equal to [T(1) elements. Similarly, define E as, E = { (x20R") (rSs e) E E3}
fCE (CE : (x> e,
Finally, define Ecb as =zs= fer (x= Fe E (x2oR") : (e E E}
We now factorize the probability below
P ( E Elp(
.p())=
II beprefix(s)
P
rb
(2)
E
E
(2)
Pbb <bb
(2)
(2)
P
(2))
E E 1T pp())
II
I
(1)))
E
E
())
<b
(1)
<b
P
(
E
E
(2)
p (1) p(2)
bE prefixx((s)
II
Po
E
<b
Pb
7
E
p
p
(2)
bEprefix(s)
II bEprefix(s)
Qb
Ex
(2)
[Pb
(2)
P
T
E 23
2
P
(1) (2)
Qcs (BeAlDE
(2)
(2)
P
7
E
E T (1) (2)
(2)
where the second equality follows since (1) =
r =
cb and pb =
(2)
- p. for all b < by construction.
The third equality follows since ((") is distributed since conditioned on the permutation being the same, the prefix is also distributed as Q
Pg conditionally and fourth and final follows
We now start the induction: let (iindcction variable) be = 8 i.e the last item is deleted. In this case, the unlearning algorithm simply removes the s-th node of the tree and all we left with is the tree with prefix(s) (8) nodes, which as argued above is distributed as Q= Q.
For the case 1 = + 1: we simply focus on ( 7 = r Note that r! is distributed
as ( T²) and we want r. distributed as (2) o²I). The operation in the algorithm is basically one step reflection coupling which from Lemma in Ullah al. (2021) satisfies,
P
(2)
E
E
(1) p (2
Q (2)
E
Therefore,
P (T E (ppD),p()) = Ocs EEc (Ecc
(
(2)
@0
(3)
Fegg
(2)
=
=D(()
(F)
This finishes the base cases.
We now proceed to the induction step: suppose the following claim holds for nodes upto I = k - for any event E,, the marginal distribution
E
p()))
Qsh (F)
For node k 1, consider few cases:
17

---

Under review as a conference paper at ICLR 2023
1. A: All rejection sampling steps prior to node i resulted in accepts:
(a) AP: Node k + 1 lies in the path from the s to root.
i. APA: The rejection sampling at this node succeeds.
ii APR: The rejection sampling at this node fails i.e. reflection step is performed.
(b) AN: Node + 1 doesn't 't lie in the path from s root.
2. R: Some rejection sampling step resulted in rejection.
For case R, we have that r *+1 ~ Qx+1(-17 p p())). For the case AN, note that the random variable
1++1 = T k+1 hence,
(1)
P
E E K+1
IN,
(2) P p(2) -Pe+1
F PRt1
ck (2)
T = Qu+1
E
T(2)
<k
(2)
where the last equality follows since the dependence of (2)) is only on data points which are leaves of the sub-tree rooted at node k + 1. These, by assumption do not contain the data point 8, hence is identically distributed as PE+1-
For the event AP, we have,
P
(2) rk+1 E E APP, p (1) (2)
(2)) (00)
= P
(2)
E BRID
Sk
APAIAP, ,
+ P
1h41
(2)
E APRIAP, , 1,,2,,780
S*
= 0
E lp
(1)
.p (
(2) 7(22
where the last step follows from Lemma 1 in Ullah et al. (2021). Hence, combining AP and AN cases,
(2)
(2) E
P
(2)
E
AN, ()) (1) pp)) Qut1
E
ck (2)
We now combine all the cases: let df Sk @ Skk and R respectively. Let T
denote the conditional densities of 7:)) For any event F,
(R)
under events A
<k
"lp =P
(2)
E AA T2 Esa, Us,,p"),p))) IP
72) E E p(()
Sht+
Tk4l
+P
k+11
(2)
E E
E R, (2)
E Eca, ( (1).((2) P
( E Ess, R|p(),
1 (T E (ESS) (
( (2)
1 ( E EA)
(/4)) (T22)
[kt1
E Extl)
+ 1 (T E & (7
(((2) 7(2)
di ck dr dr
(k41
k+1
(2) (T
E 00)0gm0
(T:2) 2
(kt1 gk
dt
sk+1 (E)
where in the third equality, we use the induction hypothesis. This completes the proof of the lemma.
Lemma 5. For any measurable event C I (2) = Q(E).
18

---

Under review as a conference paper at ICLR 2023
Proof. This follows primarily from Lemma 4, and the fact that other elements in nodes of T, namely Wh and wh deterministic functions of the prefix vertices in the tree TT Consider decomposition of the event E' = En, x Er x Ew x Lz Now,
((( E. P. PP (T(2) E. Exp F.w x Eg(p!) (()) E Fs) IP (2) Fig)
P (T(0) E,ID (1) 1 p(2)) (n-1(E.)
Bpi Qol (E,) pn un-1
Bpa Qm() (Fn Fne Exy) 1n- (F2)
Q(F)
where the second and fourth equality follows since variables we and up are deterministic functions of the responses Tigh The second and third equality also uses Lemma 3 and Lemma 4 respectively. 0
Lemma 6. The probability of retraining at most log (n) p.
Proof. A retraining is triggered only when a rejection sampling step fails. Note that a rejection sampling step happens only when the node b belongs to the path from s to root, say path. Let Accept be the event when all rejection sampling steps succeed.
16b 1T
(
<b
I (Accept) ET T (ws)
II бεpath
ub
S
(T
p
(1017
Eaa p p())
II pEpath
I
Ub
S
(1601T())
pp(
(1)
((()T(()))
(pp020) (11 ar!")
P p(2))))))))
min
④ (p(2)
rb
бεpath
/Rd
E p)
II Dεpath
(1-TV TV
@5 .pp (T()
(2)
II (1 pb)
&gpath
Σ Pb БЕрpt
> log (n) max Pb
b
2 1lllog(1 (n: p
where the fourth equality follows from the definition of TV distance and in the last equality, Ps denotes the (conditional) TV distance of node The third to last inequality follows from Lemma and the second last inequality follows from Holder's inequality. For the last inequality, we simply upper bound Ps & since the algorithm is p-TV stable (Lemma 2). This completes the proof. [
Lemma 7. Let {a be real numbers such that a; E (0, for all i and Σ ag S 1. Then, I (1 a.) 2 Σb 0;
19

---

Under review as a conference paper at ICLR 2023
Proof. We prove this via induction on k. The base case lo 1 is immediate. For the induction step k. we have
k-1
k-1
II (1
a;)
II (1 az) (1 ax) 2
Σ
a3
(1
a&)
1=1
i=
i
Σ
=1
aj
i=1
b
2
1
44
1=1
This completes the proof.
E MISSING PROOFS FROM SECTION 5
E.1 VARIANCE-REDUCED FRANK WOLFE
Algorithm 12 Variance-reduced Frank Wolfe(to: T)
Input: Dataset S, loss function (w, 2) + L(w, 2). steps T, a. (
1: if ln = then Permute dataset, initialize T, set Wto = end if
2: for f = to T 1 do
3:
((i+ - 1) V((w;z)) (V((w:1;;2)
4: Append We: T)
5:
GetPrefixSum (t;
6: Ut = arg min w; Ft
t+1
7: W++1 = (1 - n) + 7722
8: Set(leaf(t), (u,, re, Wts ;T)
9: end for
Output: T WT
Proof Theorem 2. For the accuracy guarantee, we follow the proof of Theorem in Zhang et al.
(2020). Let de Ft. From smoothness, we have
[(wi-1; D) S L(w;; D) (VL(w;; D), we+1 ww) + H
2 | w
s L(w;; D) + 1 (VL(w,; D) - de, 1i - w() + (de; Us - -we) + m H22122
2
= Lww;; D) + Th ( L(w;; D) - de, Uz - ww) + (de; w0 - -wi) + n2
2
L(w;; D) 1/ L D), w² - wi) + The (de L((w,), w" -vz) 11. D2
2D
(LW 11? HD2
<1 ne) L(w;; D) ny L. ( ; ++1 ||d,
where the second inequality follows from the update and the fact that iterates lie in the set of diameter D. The third inequality follows from the optimality of v, in the update in Algorithm 12. Finally, the last inequality follows from convexity, Cauchy-Schwae Schwarz inequality and by substituting the step-size. We now take expectation, and use the bound on gradient estimation error in Lemma to get.
E[L(W(41;D) - L(w";
$ (1 -1-18 (1-m) [[[(w:; D) L(w": D)] +Ō (HD (
((HD+G)D
Vd (++ 1)3/2
o) (t + 1)²
(HD+ G)D
HD²
1)
20

---

Under review as a conference paper at ICLR 2023
The above recursion gives us,
T-1
[[L[wT: D) L(w"; D)] - (L(wi; - Iww))
(1 (-)))
Am1
Vd
HD
Σ
(HD+G)D
(8+1)3/2 (1+11p))
II (1-Th) mp) t=i41
(i+1)
HD²
T
1
vd
HD
1 T
E
0
(HD+G))
+
(i+1)
(i+1)p)
(i+1)
=
1
Vdl
HD2
<ō
(HD
+
VT
Tp
T
1
vd
áō (HD - G)D
Tp
where the second inequality follows from smoothness and substituting Substituting number of iterations T = completes the accuracy proof.
I 1/)) #
For the unlearning part, start by showing that the algorithm falls into the tem- plate bounded sensitivity prefix-sum query release. Recall that the update in = Ei ((i + VZ(w; vV((;;-;;2)).
The sensitivity is then bounded as,
[1((1 + Ve(w;; 2) [V((w; ((i+ V((wnze) ([V(:===))vV(((::::))))))) (V((u;-122))
< iH ||u - w/-il + 2G
< iHm-1 ||:-1-1 1 w;-1|| 2G
< (HD+G)
where the first inequality follows from smoothness and Lipschitzness of the loss. The second inequality follows from the update Algorithm and the last inequality follows from the fact that the iterates remain in the set of diameter D. Hence the correctness of the unlearning algorithm follows from Theorem 1. For runtime, the training time, in terms gradient computations is (()). Therefor, using the fact that the relative unlearning complexity, from Theorem 1, is Ö(p), we have (pm) bound expected unlearning runtime.
Lemma
8. The gradient
estimation
error
E
VL(w D)
2+1
δ ((ID+
(+tz (+1FF
Proof. Note that de = To
# comprises original gradient estimate from Zhang et al. (2020), say
de and the noise added by the binary tree mechanism, say ε.. Hence,
E ldd - V(ww,; D)
E
C - VL(w,; D)
+ +E |6
(HD+
log(n)
d
t+1
(t + 1)² p2
=ō
HHD G)2
t+1
(+ p²
where the first inequality follows from Lemma Zhang et al. (2020) with a 1, and the fact that in the binary tree mechanism add noise of variance most log (n) times; the factor 1/(t + 1)2
21

---

Under review as a conference paper at ICLR 2023
comes because the gradient estimate is r + 1) and is the binary tree response. The final equality follows by plugging in the value of a.
E.2 DUAL AVERAGING
Algorithm 13 Dual averaging(fo:
Input: Dataset S, loss function (w: 2) l(w, z), steps T, {mp }
1: if tu then Permute dataset, initialize T, set Wio 0 end if
2: for to T do
3:
- i= Vi(we; 24)
4: Append(u,.0g Uy:
5: GetPPefixSSmm (4; T)
6: Wi+1 = 1lw (wo - T(Ppt)
7: Set(leaf(t), (u,, Wt, 26); ;7)
8: end for
Output: u = wr
Proof of Theurem 3. The accuracy guarantee directly follows from Theorem 5.1
Kairouz al.
(1/5)² (2021), replacing c therein by p. To elaborate,
G
opposed to
δ (1o0))118) hence substituting it in the accuracy proof of Theorem 5.1 in Kairouz et (2021)
gives the claimed guarantee.
For the unlearning part, start by showing that the algorithm falls into the template of bounded sensitivity prefix query release.
Recall that the update in = Eizn Vilwi; 24). The sensitivity is simply bounded by Lipschitznes as,
Ve(wn; =) V((w; =')ll
Hence the correctness the unlearning algorithm follows from Theorem 1. For runtime, the training time, in terms of gradient computations is ((n). Therefor, using the fact that the relative unlearning complexity, from Theorem 1, is O(p,, we have Ö(p)) bound on expected unlearning runtime.
E.3 CONVEX GLMS WITH JL METHOD
Theorem 5. Let p S 1 and é W x X x x + R be an H H-smooth, G-Lipschitz convex GLM loss function. Algorithm 4 instantiated with Algorithm 12, the learning algorithm, with の²
Ō [H]] (HII)? [+(H)I))))))))) to = L, 7h-
#I and k =ō ( (( [[-II--
(
#|
2/3
(/1)2/3 2/3
on a dataset S of samples, drawn i..dd from D. outputs @ with excess population risk bounded as E [L((;;)) - L(w": Ö [|] ( [1)l""""""""" #1/3g2/8 ||00// | [x 2/14/3 +
(22))2/3
Furthermore, the corresponding unlearning Algorithm (with query and update functions as specified in the learning algorithm), satisfies exact unlearning with (pn) expected runtime.
Proof of Theorem 5. We start with the accuracy guarantee. Let a a parameter to be set later. From the JI. property, with & = O (log (n/ /a²), with probability at least 1 3,, the norm of all
data-points in S. |x,|| < (1 a)) |xx||| < 2| Hence, conditioned on the above event, the GLM loss function function is G = 2G |ipss--ipsschtzz and H 4H 2 Let 4D denote the push-forward measure of D under the map (z,y) + (#x, y). With probability at least 3, the excess risk is,
22

---

Under review as a conference paper at ICLR 2023
[[ D) L(w"; ; ;D) = E|L( w: D) - L(Ow": xD)] + L 2w DD) - L(w" :D)
E (w; DD) L( &D)] BlØ,, ( (@ow" fxx) By ((w ,))]]
G + 11 |w=ll) ||0*|1
1
+
vi
+
H
L ( Dw") (2, w w²
vii
np
2
G + H |w0 ||0*11
1
V
H 1w=
+
vn
np
k
a + H
[|wl])
||w*|
71/3 (np)2/3
1|0"
11//3
+
H7 1|2
n
where in the first inequality, smoothness of by together with the fact that w is globally optimal. The second inequality follows from JL property and the last inequality follows by the setting of k.
the accuracy guarantee of VR-Frank Wolfe (Theorem 2) and
For the in-expectation (over the JL matrix) bound, note that the worst-case, L(w; D) L(w"; S G' G ==1 ||. From boundedness of the range of (typical) JL maps, | w"1l = poly(n, d) w.p. 1. Hence, taking the failure probability 3 to be small enough suffices to be give an expectation bound which is same above upto polylogarithmic factors.
We now proceed to the unlearning guarantee. We first remark that the correctness of the unlearning algorithm (see Lemma 4) holds as long as the learning algorithm uses prefix-sum queries, even with unbounded sensitivity. Hence, the correctness follows. We now proceed to bound the unlearning runtime. We first bound the TV stability parameter of the learning algorithm using Lemma 9. The setting of noise variance a in Algorithm together with the stability guarantee of Theorem ensures that (H,, G) < 5. Hence the JL method satisfies p-TV stability. Now, Lemma gives us that the probability of retraining is most O(p). Since the training time, in terms of gradient computations is ((n), we have Öpp) bound on expected unlearning runtime.
Theorem Let p S and W x XXXXx R be a G-Lipschitz corvex GLM loss func- tion. Algorithm 4 with Algorithm 13 the sub-routine, as the learning algorithm, run with o² =0 sampled i..dd from D outputs w. with excess population risk bounded as, E [L(W; L(w";
- (G911211))
to = n = || jd' /log(n) and = npp on a dataset S of n samples
Furthermore, the corresponding unlearning Algorithm 3 (with query and update functions as specified in the learning algorithm),, satisfies exact unlearning with Ó (pr) expected runtime.
G G|
(/2
(1p))/3
Proof of Theorem 6. We start with the accuracy guarantee; let < 1 be parameter to be set later.
From the JL property, with & = (log (n/3) (8) //2). with probability at least 1 - 3, the norm of all
data-points S. [bx < (1+ a)) a)) |x,|| < 2 ||] Henee, conditioned on the above event, the GLM loss function function is = 2G Lipsssiips Let 4D denote the push-forward measure of D under the map (ar v) (oxr, y). With probability at least the excess risk is,
23

---

Under review as a conference paper at ICLR 2023
[[ D) L(w";
;1o0;2)] D)] = E| w; D) L( &D)] E +D) - L(w"; D)]
E[ (D)
L( DD)
B ($w"" (bx)) Q2 ((w xx)]
1
vk
G ||w0|l
+
V
GE
(Tx, vw") - (2, un)l
vn
np
1
vk
G |lw'll
G
||w'll
+
+
Vn
np
V
G
Vn +
(np)
1/3
where in the first inequality, Lipschitzness of Φy together. The second inequality follows from JL property and the last inequality follows by the setting of k. As in Theorem 5, the same bound above for in-expectation (over the JL matrix) holds follows by taking the failure probability / to be small enough.
the accuracy guarantee of Dual Averaging (Theorem 3) and
The correctness and runtime of the unlearning algorithm follows in the proof of Theorem
Lemma 9. Suppose A is algorithm which when run on H H-smooth and G-Lipschitz functions is 7H,, GV stable, then the JL method with with & O (log (2n/T)) and A input, run H-smooth and G-Lipschitz GLMs. satisfies 1 + 2G || 4H 11x1²) TTV stability.
Proof. Given dataset S let Gs be the uniform bound on Lipschitzness parameter of the class of loss functions {w + E(w; >es- We define Hg similarly. Let I be a parameter to be set later. From the JL property, with k O (log (n/B)), with probability at least 3, the norm of all data-points in S, || < 2 ||>''|| we denote this event as En.. Since the loss function is GLM, we have that conditioned on EJ,. the Lipschitzness and smoothness parameters Gs and Hs are bounded by 2G || and 2H || respectively. We therefore get a stability parameter 7 2G || 4/1 ||
We set p/2. We now incorporate the failure probability in the failure guarantee. Let Ps and Q+ denote the probability distributions of the output on datasets S and S'. By definition of TV distance,
TV(Pa, Q+) = sup P W (w E) -P Pwww (w E E)
sup P PWWN (w E P(E)) + PEUP (w E ((EE)))(C P(E
E
P Punq (w E E En) P( (E)) - P PwwQ (w E|E P(EL))((E))
sup P PPp (w E Fn.)
P w (w E E() P(E
E
sup
P P (w E E E - P Punq (w E E P(En))
E
<
sup P P (w E Fn.) P w (w F F() + p/2
E
<
3 + 0/2
which completes the proof.
F SCO IN DYNAMIC STREAMS
In this section, we extend our previous results to dynamic streams wherein we observe a sequence of insertions and deletions, starting with potentially data points. We assume that the number of
24

---

Under review as a conference paper at ICLR 2023
available points throughout is positive and the data points are i.id. from an unknown distribution as well as the unlearning requests are chosen independent of the algorithm.
To give simple and unified presentation, let the expected accuracy, say excess population risk, of the p-TV stable Algorithm 2 with a dataset S be a(I P; P) where P denotes problem specific parameters such as Lipschitzness, diameter etc.
We present two techniques for dynamic streams; the first one satisfies exact unlearning but has worse update time; this is similar to Ullah et al. (2021). The other satisfies weak unlearning (defined below) with better update time. A key component to both are anytime guarantees described below.
Anytime binary tree mechanism: In the previous section, the depth of the initialized tree and the noise variance a, both were chosen as function of the dataset size n. However, the tree can be easily built in an online manner as in prior work Guha Thakurta & Smith (2013). For setting the noise variance: for target p-TV stability, we distribute the noise budget exponentially along the height of the tree; specifically, the leaf node contribute to p/2 TV stability, the nodes above them p/ and so on, In this way, the final tree satisfies pVTV stability for any value of n.
Anytime accuracy: The other problem of changing data size is that the internal parameters of algorithm (step size, in our case) may be set as a function of n for desirable accuracy guarantees. Fortunately, the two algorithms that consider, VR-Frank Wolfe and Dual Averaging, have known hobizon-oblivious parameter settings Orabona (2019). Their JL counterparts on the other hand, require setting the embedding dimension as function of n, and thus not applicable unless we assume that the number of data points throughout the stream is (n))
F.1 WEAK UNLEARNING
We first define weak unlearning wherein only the model output and not the entire state is required to be indistinguishabl.
Definition 9 (Weak unlearning). A procedure (A, U) satisfies weak unlearning for all all datasets S, all 2 E 2, and for all events & C W x M, we have, P (5) (z)) E) = (A E E)
We now argue in what way insertions handled in Ullah al. (2021) is deficient. The main reason is that they require insertions to also satisfy the unlearning criterion: the state of the system upon insertion instinguishable to the state had the inserted point being present to begin with. However, this is an overkill; adding new points simply serve to yield improved statistical accuracy. Furthermore, methods which allow adding new points, abound, particularly in the stochastic optimization setting, popularly known as incremental or continual release methods. Importantly, the insertion time of these methods is constant (in n). Hence, a natural question is whether, for dynamic streams, can we design unlearning methods in which we pay for update time only in proportion to the number of deletions? Our result shows that we can, albeit under the weak unlearning (see Definition 9) guarantee.
Specifically, our procedure requires hiding the order in which data points are processed. Intuitively, an incremental method typically processes the newest data point the last. This ordering is problematic to the unlearning guarantee, since if some point is to deleted, then we can no longer replace it with the last point as that would result in a different order. Our main result is as follows.
Theorem 7. In the dynamic streaming setting with R requests, using anytime incremental learning and unlearning algorithuss, Algorithm 2 and 3, without permuting the dataset, the following are true.
1. It satisfies weak unlearning at every time point in the stream.
2. The accuracy of the output W; at time point with corresponding dataset Sy, is E[L( D)] min L(w; D) (S:::P)
3. The number of times retraining is triggered, for V unlearning requests is at most Ö(PV)
Importantly, in the above guarantee, we only pay for the number of unlearning requests V rather than the number of requests R.
Proof of Theorem 7. The first claim, weak unlearning guarantee of the unlearning algorithm, follows mainly from Lemma 4. Specifically, it shows that conditioned on the permutation of the dataset (in this case, since the dataset is not permuted, the permutation is simply identity), the distribution over
25

---

Under review as a conference paper at ICLR 2023
the responses (rb); in the tree after unlearning, is transported to the distribution of the output under S'. Since the model output is a deterministic function of the responses, (weak unlearning) correctness follows for one request. For the streaming setting, simply apply the above inductively over the requests.
The second claim follows since, every time point, the executed algorithm is indistinguishable from the base algorithm executed over the current dataset. Moreover, by assumption, the base algorithm, is anytime, i.e. no parameter is which depends on the size of the dataset. Hence, the accuracy guarantee follows. For the last claim about the number of retraining, firstly, as motivated, by the assumption that the algorithm is incremental, the insertions are handled in O(1) time. For the unlearning requests, note that from p-TV stability at every point, using Lemma 6, we have (p) probability of retraining. We now apply Proposition 8 from Ullah al. (2021) which converts this to a bound on the expected number of times a retraining is triggered. For unlearning requests, this gives us (pV)) bound on the number of retraining triggers.
F.2 EXACT UNLEARNING
Another way extend the results for one unlearning request to dynamic streams is to modify the definition of unlearning (Definition 1) to also hold for insertions, as done in Ullah et al. (2021). This allows us apply the same tree based unlearning technique when handing insertions. Specifically, upon inserting a new point, we randomly choose a leaf and replace the leaf with the inserted point, and then insert the chosen leaf the last leaf in the tree. We have the following guarantee for this method.
Theorem 8. In the dynamic streaming setting with R. requests, using anytime learning and unlearming algorithms, Algorithm and 3, the following are true.
1. Exact unlearning every time point in the stream.
2. The accuracy of the output W; at time point with corresponding dataset S,, is G[L(W;;D) min L(w; D) a(p, (S:]:
3. The total number of times, retraining is triggered, for R requests is most O(pR)
Proof. The arguments are similar to that of the proof of Theorem 7. The first part follows by applying the correctness of the unlearning algorithm, Theorem inductively over the stream. We remark that the handling the insertions the same way as deletions hardly changes anything in the proofs. The second claim follows from the anytime nature of the algorithm and by assumption the accuracy guarantee. Finally, using the probability of retraining in Lemma and Proposition in Ullah et al. (2021) gives the stated number of retraining triggers.
26


Reviews:
[{"review_id": "tFzdzqtZ0M", "reviewer": "Reviewer_44f4", "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 paper studies the problem of machine unlearning and improves oracle complexity for stochastic convex optimization (SCO) under both smooth and non-smooth setting. The key idea is a new prefix-sum unlearning sub-routine that enables one to use Variance reduction Frank-wolfe and dual averaging algorithm for SCO.\n\nResult. For smooth SCO, the paper gives an $O(\\frac{1}{\\sqrt{n}} + \\frac{\\sqrt{d}}{n\\rho})$ accuracy answer with expected runtime $O(\\rho n)$ per update using variance reduced Frank Wolfe. For non-smooth SCO, it gives $O(\\frac{1}{\\sqrt{n}}) + \\frac{d^{1/4}}{\\sqrt{n\\rho}})$ accurate answer with $O(\\rho n)$ per update, using dual averaging. Dimension independent results have also been obtained for the special case of generalized linear model.", "summary_of_the_review": "The paper gives improved rate for stochastic convex optimization of machine unlearning with some interesting ideas. I would vote for acceptance.\n\nQuestion for authors. Are there any lower bounds known for SCO of machine unlearning?\n\n\n-----------\n\nPost rebuttal\n\nI have read the rebuttal and my evaluation remains.", "strength_and_weaknesses": "Strength. The paper provide improved oracle complexity for stochastic convex optimization (SCO) of the machine unlearning task. The prefix-sum idea seems simple, but it is good enough for one to use powerful tool from SCO. Meanwhile, I expect the prefix-sum subroutine could be useful for other applications of machine unlearning\n\n\nWeakness. There is no major weakness. ", "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": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "h25M6593OyA", "reviewer": "Reviewer_qNGF", "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 paper provides a framework for efficient machine unlearning for stochastic convex optimization. In particular, the work builds upon the prior paper by Ullah et al. (2021) and generalize it to handle prefix sum queries. As for concrete applications, this enables machine unlearning for variance-reduced  stochastic convex optimization (SCO) methods and dual averaging schemes. ", "summary_of_the_review": "Given the quality of the presentation, I cannot recommend accept. However, I can see that the paper could be improved a lot if the author(s) put some efforts on writing during the rebuttal period.", "strength_and_weaknesses": "The paper claims a set of efficient algorithms for exact machine unlearning of SCO methods that are widely used in ML practice.  I believe this is a well-motivated question and the technical contributions here are novel and non-trivial. \n\nHowever, I am concerned about the technical clarity of the presentation. Overall, I find the paper lack of some conceptual exposition to be accessible to non-experts of the area. In fact, much of the materials rely upon using the prior work Ullah et al. (2021). I believe for those who are not familiar with Ullah et al. (2021), the technical sections of the paper would be hard to parse. \n\nMost importantly, the main algorithm from Section 4 (on prefix sum queries) is mostly described by the pseudocode. I find it hard to understand it at a conceptual level. Why and how does it perform unlearning? What does the noise-adding mechanisms do here? I think the issue stems from not having sufficient exposition on the coupling nature of the problem and the technique of reflection coupling.  (It appears that the techniques are borrowed from Ullah et al. (2021), which I have not read.)  I suggest the author(s) add a technical overview section earlier in the paper. \n\nThe paper does not give empirical validation of their methods, though I do not consider it a major weakness, as this work is theoretical in nature. \n\nSome other minor comments: \n---- \nIn what sense is “linear queries” (Definition 8) is “linear in the data-points”, as claimed in the introduction? In Definition 8, the function p_j can be non-linear in z_j. In fact, if p_j is the gradient of the loss function, it can easily be non-linear in z_j (for many ML models and choices of the loss function). \n\nAfter Definition 6 it should be mentioned that the bounded sensitivity condition is satisfied in variety of applications. \n\nI think Appendix B requires more exposition. What does Algorithm 6 do at an intuitive level?  What is the LearnLinearQueries function? In fact, I suggest the author(s) expand this section and put it into the main paper as a warm up before delving into the prefix sum queries. \n\nThe paper should also discuss related work in more detail. In addition to Ullah et al. (2021) that this work builds upon, there’s been a flurry of recent work on machine unlearning. This includes, for example, Descent-to-Delete: Gradient-Based Methods for Machine Unlearning by Seth Neel, Aaron Roth, Saeed Sharifi-Malvajerdi (ALT 21)\n\nMechanical suggestions\n---\n1. In the additional prelim section, I suggest the author(s) to elaborate on reflection coupling, especially its formal guarantees. (The original paper claims the result in the setting of Brownian motion, which seems different from what’s going on here.)\n2. End of page 2: Frank Wolfe -> “Frank-Wolfe”\n3. Section 5: “[...], and thus fits into the framework”\n4. Algorithm 6, the Load() function is undefined?\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": "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": "LvcwTeNQW2o", "reviewer": "Reviewer_VmwR", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The authors consider the problem of unlearning. The aim is to do more efficiently than retraining from scratch. The authors propose to construct a prefix-sum-like tree during learning/training to keep intermediate results. These results can then be queried to construct a model that will look like the one without a certain data point (i.e., the one that was requested to be deleted).", "summary_of_the_review": "I believe the paper is not ready to be published due to its presentation (the method description) and how it positions itself (i.e., is this exact unlearning, how it compares to retraining from scratch, how it compares to sharding approach by Bourtoule et al. It may be that in considers inly certain training tasks but it would be best to be clear about it.", "strength_and_weaknesses": "Strengths:\n- the problem of unlearning is really interesting and important\n- the authors aim to propose a method that is more efficient than training from scratch\n- the idea of decomposing into prefix-sum-like learning is nice\n\nWeaknesses:\n- the definition of exact unlearning used by authors is not common\n- the paper is extremely dense in notation and content\n- the method seems to work only for unlearning one point though the authors allude it may be extended\n- the method is expensive in terms of space as it seems one need store a model for every data point\n- no experimental results", "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": "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": "FU4tdMUZGEU", "reviewer": "Reviewer_NHVJ", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The authors propose a general framework for machine unlearning via (structured) adaptive algorithms. In machine unlearning, given a model trained via dataset S, one attempts to build algorithms which can efficiently remove any point z from the dataset post-training in such a way that the altered model is indistinguishable from training on $S \\setminus \\{z\\}$. The main goal is to build algorithms where the cost of unlearning is significantly less than the cost of simply retraining the model. The study of machine unlearning is practically motivated by data privacy laws and `the right to be forgotten,’ in particular the General Data Protection Regulation (GDPR), and California Consumer Privacy Act (CCPA), which require (in limited circumstances) that a company must delete stored personal data on request.\n\nIn this work, the authors generalize the prior techniques of Ullah et al. (COLT 2021) for machine unlearning via (noisy) SGD via total variation stability to hold for a general class of adaptive algorithms built on either \"linear\" or \"prefix-sum\" queries, two well-studied classes of algorithms within optimization and privacy. In particular, they show how to modify any such algorithm into one in which unlearning costs only a $\\rho$-fraction as many queries as retraining (for arbitrary $\\rho > 0$). The main contribution is the algorithm and analysis for prefix queries, which is roughly based on combining Ullah et al.’s TV-stability techniques with the binary tree mechanism of Dwork, Naor, Pitassi, and Rothblum (STOC 2010). The authors also study an extension of these methods to the streaming setting, where multiple insertions and deletions in such a manner in an online fashion.\n\nFinally, authors give a number of applications of this general framework based on known algorithms in the literature, namely for stochastic convex optimization (SCO) via Frank-Wolfe and Dual Averaging, and dimension-independent bounds for GLMs via the above and Johnson-Lindenstrauss (as in Arora et al. 2022). These techniques provide the best known unlearning algorithms for SCO, improving the known convergence rate from $\\frac{1}{\\sqrt{n}} + (\\frac{\\sqrt{d}}{n\\rho})^{2/3}$ to $\\frac{1}{\\sqrt{n}} + (\\frac{\\sqrt{d}}{n\\rho})$, thus showing unlearning has no asymptotic cost up to relative complexity $\\sqrt{d/n}$. The authors also give applications of the linear query method to federated learning and k-means.", "summary_of_the_review": "This is a nice follow up work to Ullah et al. 2021, the idea of building a general framework of machine unlearning for adaptive query algorithms is a good idea, and the authors give a number of applications. On the other hand, it is not clear that the model of unlearning (and complexity measure) the authors study is interesting or well-motivated, and at a technical level it is also not clear much additional insight is given over prior works. As it stands, I am not sure this work is quite above the bar of ICLR.\n\nEdits: See rebuttal and response, raising to above bar.", "strength_and_weaknesses": "Strengths:\n\n1. The authors introduce the first general framework for (exact) machine unlearning for adaptive algorithms using linear and prefix query algorithms\n2. They give improved minimax rates for unlearning in stochastic convex optimization, a ubiquitous paradigm.\n3. They give many applications (federated learning, k-means, various SCO settings…), and generalize to streaming setting\n4. The paper is generally well written (with some exceptions detailed below)\n\n\nWeaknesses\n\n1. While machine unlearning is motivated by data privacy/rights as a general concept, the exact model studied in this paper is not clearly well motivated. Approximate machine unlearning (or any say computationally indistinguishable method) seems substantially more useful. Furthermore, while the authors claim that GDPR and CCPA require companies to fully retrain models in this sense, as far as I can tell these laws say nothing of the sort, and only include vague instructions that personal data should be removed upon request. I find the introductory paragraph to be very misleading in this sense. This said, there is legal precedence for requiring model re-training in a 2021 Federal Trade Commission decision, but this is a specific instance and should be cited as such. It seems very plausible that approximate unlearning would be accepted in general.\n2. Many of the results seem to be straightforward generalizations or combinations of prior work and techniques, though proving the prefix query theorem does require some involved technical calculations. Furthermore, since no lower bounds are given in the paper it is hard to tell how substantial the rate improvements are.\n3. A more minor complaint is that the notion of relative unlearning complexity needs better motivation. Of course the idea of algorithms whose unlearning time is faster than retraining is natural, but it seems like the denominator comparison should maybe be to the best possible rate. For instance, one could have a very poor unlearning algorithm with very good relative complexity, where it would be better to just run a different method from scratch.\n4. No accuracy guarantee is given for the general framework, and has to be shown on a by-algorithm basis. The authors state informally that accuracy should be preserved for noise-tolerant algorithms, but if one is giving a general framework for application this should be formalized.\n5. While the level of detail given in the main body is ok for the short version, there needs to be additional background and exposition somewhere in the paper. It should not be necessary to be familiar with any specific prior work to understand the paper. I'd also recommend defining even very basic terms (at least briefly) such as query release, for non-familiar readers.\n\nTypos: \n\nPage 5: In 2. Efficient Unlearning Model should “does” be “doesn’t”?\n\nPage 7: Line 11 does not seem to be rejection sampling. Perhaps line 13?", "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": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Decision: Reject