Certified Machine Unlearning via Noisy Stochastic Gradient Descent

Authors: eli  chien
haoyu  wang
ziang  chen
pan  li
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-13 16:53:25

Abstract: ``The right to be forgotten'' ensured by laws for user data privacy becomes increasingly important. Machine unlearning aims to efficiently remove the effect of certain data points on the trained model parameters so that it can be approximately the same as if one retrains the model from scratch. We propose to leverage projected noisy stochastic gradient descent for unlearning and establish its first approximate unlearning guarantee under the convexity assumption. Our approach exhibits several benefits, including provable complexity saving compared to retraining, and supporting sequential and batch unlearning. Both of these benefits are closely related to our new results on the infinite Wasserstein distance tracking of the adjacent (un)learning processes. Extensive experiments show that our approach achieves a similar utility under the same privacy constraint while using $2\%$ and $10\%$ of the gradient computations compared with the state-of-the-art gradient-based approximate unlearning methods for mini-batch and full-batch settings, respectively.

Main paper: 
 introduction: 
 Machine learning models usually learn from user data where data privacy has to be respected. Certain laws, such as European Union's General Data Protection Regulation (GDPR), are in place to ensure "the right to be forgotten", which requires corporations to erase all information pertaining to a user if they request to remove their data. It is insufficient to comply with such privacy regulation by only removing user data from the dataset, as machine learning models can memorize training data information and risk information leakage [1, 2] . A naive approach to adhere to this privacy regulation is to retrain the model from scratch after every data removal request. Apparently, this approach is prohibitively expensive in practice for frequent data removal requests and the goal of machine unlearning is to perform efficient model updates so that the resulting model is (approximately) the same as retraining statistically. Various machine unlearning strategies have been proposed, including exact [3] [4] [5] [6] and approximate approaches [7] [8] [9] [10] [11] . The later approaches allow a slight misalignment between the unlearned model and the retraining one in distribution under a notion similar to Differential Privacy (DP) [12] .The most popular approach for privatizing machine learning models with DP guarantee is arguably noisy stochastic gradient methods including the celebrated DP-SGD [13] . Mini-batch training is one of its critical components, which not only benefits privacy through the effect of privacy amplification by subsampling [14] but also provides improved convergence of the underlying optimization process. Several recent works [9, 11] based on full-batch (noisy) gradient methods may achieve certified approximate unlearning. Unfortunately, their analysis is restricted to the full-batch setting and it is non-trivial to extend these works to the mini-batch setting with tight approximate unlearning guarantees. The main challenge is to incorporate the randomness in the mini-batch sampling into the sensitivity-based analysis [9] or the Langevin-dynamics-based [11] analysis.We aim to study mini-batch noisy gradient methods for certified approximate unlearning. The highlevel idea of our unlearning framework is illustrated in Figure 1 . Given a training dataset D and a fixed mini-batch sequence B, the model first learns and then unlearns given unlearning requests, both via the projected noisy stochastic gradient descent (PNSGD). For sufficient learning epochs, we prove that the law of the PNSGD learning process converges to a unique stationary distribution ν D|B (Theorem 3.1). When an unlearning request arrives, we update D to an adjacent dataset D ′ so that the data point subject to such request is removed. The approximate unlearning problem can then be viewed as moving from the current distribution ν D|B to the target distribution ν D ′ |B until ε-close in Rényi divergence for the desired privacy loss ε1 .Our key observation is that the results of Altschuler and Talwar [15, 16] , which study the convergence of PNSGD under the (strong) convexity assumption, can be leveraged after we formulate the approximate unlearning as above. They show that the Rényi divergence of two PNSGD processes with the same dataset but different initial distributions decays at a geometric rate, starting from the infinite Wasserstein distance (W ∞ ) of initial distributions (Figure 1 , step 3). As a result, if the initial W ∞ distance can be properly characterized, we achieve the corresponding approximate unlearning guarantee by further taking the randomness of the mini-batches B into account (Figure 1 , step 4). Therefore, the key step to establish the PNSGD-based unlearning guarantee is to characterize the initial W ∞ distance of the unlearning process tightly.The projection set diameter 2R for this W ∞ distance adopted in [15] for DP analysis, unfortunately, leads to a vacuous unlearning guarantee, which cannot illustrate the computational advantage over the retraining from scratch. To alleviate this issue, we perform a careful W ∞ distance tracking analysis along the adjacent PNSGD learning processes (Lemma 3.3), which leads to a much better bound W ∞ (ν D|B , ν D ′ |B ) ≤ Z B ≈ O(ηM/b) (Figure 1 , step 2) for bounded gradient norm M , mini-batch size b and step size η. This ultimately leads to our unlearning guarantee ε = O(Z 2 B c 2Kn/b ) for K unlearning epochs and some rate c < 1. The computational benefit compared to the retraining from scratch naturally emerges by comparing two W ∞ distances, O(R) for the retraining from scratch and O(ηM/b) for our unlearning framework.Our approach also naturally extends to multiple unlearning requests, including sequential and batch unlearning settings (Theorem 3.11 and Corollary J.1), by extending the W ∞ -tracking analysis (Lemma 3.4). Here, we may use the triangle inequality of W ∞ distance, which leads to a tigher privacy loss bound (growing linearly to the number of unlearning requests) than that in the Langevin-dynamicsbased analysis [11] via weak triangle inequality of Rényi divergence (growing exponentially).Our results highlight the insights into privacy-utility-complexity trade-off regarding the mini-batch size b for approximate unlearning. A smaller batch size b leads to a better privacy loss decaying rate O(c 2Kn/b ). However, an extremely small b may degrade the model utility and incur instability. It also leads to a worse bound Z B ≈ O(ηM/b), which degrades the computational benefits compared to retraining. We demonstrate such trade-off of our PNSGD unlearning results via experiments against the state-of-the-art full-batch (b = n) gradient-based approximate unlearning solutions [9, 11] . Our analysis provides a significantly better privacy-utility-complexity trade-off even when we restrict ourselves to b = n, and further improves the results by adopting mini-batches. Under the same We provide an upper bound Z B for the infinite Wasserstein distance W ∞ (ν D|B , ν D|B ′ ), which is crucial for non-vacuous unlearning guarantees. Results of [16] allow us to convert the initial W ∞ bound to Rényi difference bound d B α , and apply joint convexity of KL divergence to obtain the final privacy loss ε, which also take the randomness of B into account. privacy constraint, our approach achieves similar utility while merely requiring 10%, 2% of gradient computations compared to baselines for full and mini-batch settings respectively.Machine unlearning with privacy guarantees. The concept of approximate unlearning uses a probabilistic definition of (ϵ, δ)-unlearning motivated by differential privacy [12] , which is studied by [7, 8, 10] . Notably, the unlearning approach of these works involved Hessian inverse computation which can be computationally prohibitive in practice for high dimensional problems. Ullah et al. [5] focus on exact unlearning via a sophisticated version of noisy SGD. Their analysis is based on total variation stability which is not directly applicable to approximate unlearning settings and different from our analysis focusing on Rényi divergence. Neel et al. [9] leverage full-batch PGD for (un)learning and achieve approximate unlearning by publishing the final parameters with additive noise. Chien et al. [11] utilize full-batch PNGD for approximate unlearning with the analysis of Langevin dynamics. The adaptive unlearning requests setting is studied in [6, 17, 18] , where the unlearning request may depend on the previous (un)learning results. It is possible to show that our framework is also capable of this adaptive setting since we do not keep any non-private internal states, though we only focus on non-adaptive settings in this work. We left a rigorous discussion for this as future work. 
preliminaries: 
 We consider the empirical risk minimization (ERM) problem. Let D = {d i } n i=1 be a training dataset with n data point d i taken from the universe X . Let f D (x) = 1 n n i=1 f (x; d i ) be the objective function that we aim to minimize with learnable parameter x ∈ C R , whereC R = {x ∈ R d | ∥x∥ ≤ R} is a closed ball of radius R. We denote Π C R : R d → C R to be an orthogonal projection to C R .The norm ∥ • ∥ is standard Euclidean ℓ 2 norm. P(C) is denoted as the set of all probability measures over a closed convex set C. Standard definitions such as convexity are in Appendix D. We use x ∼ ν to denote that a random variable x follows the probability distribution ν. We say two datasets D and D ′ are adjacent if they "differ" in only one data point. More specifically, we can obtain D ′ from D by replacing one data point. We next introduce a useful idea which we term as Rényi difference. Definition 2.1 (Rényi difference). Let α > 1. For a pair of probability measures ν, ν ′ with the same support, the α Rényi difference for iteration j = 0, . . . , n/b -1 do 6: for iteration j = 0, . . . , n/b -1 do 13: We are ready to introduce the formal definition of differential privacy and unlearning. Definition 2.2 (Rényi Differential Privacy (RDP) [19] ). Let α > 1. A randomized algorithm M :d α (ν, ν ′ ) is defined as d α (ν, ν ′ ) = max (D α (ν||ν ′ ), D α (ν ′ ||ν)) , where D α (ν||ν ′ ) is the α Rényi divergence defined as D α (ν||ν ′ ) = 1 α-1 log E x∼ν ′ ( ν(x) ν ′ (x) ) α .x j+1 t = Π C R x j t -ηg(x j t , B j ) + 2ησ 2 W j t , where g(x j t , B j ) = 1 b i∈B j ∇f (x j t ; d i ) and W j t iid ∼ N (0, I d ).y j+1 k = Π C R y j k -ηg(y j k , B j ) + 2ησ 2 W j k , where g(y j k , B j ) = 1 b i∈B j ∇f (y j k ; d ′ i ) and W j k iid ∼ N (0, I d ).X n → R d satisfies (α, ε)-RDP if for any adjacent dataset pair D, D ′ ∈ X n , the α Rényi difference d α (ν, ν ′ ) ≤ ε, where M(D) ∼ ν and M(D ′ ) ∼ ν ′ .It is known to the literature that an (α, ε)-RDP guarantee can be converted to the popular (ϵ, δ)-DP guarantee [12] relatively tight [19] . As a result, we will focus on establishing results with respect to α Rényi difference (and equivalently α Rényi difference). Next, we introduce our formal definition of unlearning based on α Rényi difference as well. Definition 2.3 (Rényi Unlearning (RU)). Consider a randomized learning algorithm M : X n → R d and a randomized unlearning algorithm U : R d × X n × X n → R d . We say (M, U) achieves (α, ε)-RU if for any α > 1 and any adjacent datasets D, D ′ , the α Rényi differenced α (ρ, ν ′ ) ≤ ε, where U(M(D), D ′ ) ∼ ρ and M(D ′ ) ∼ ν ′ .Our Definition 2.3 can be converted to the standard (ϵ, δ)-unlearning definition defined in [7] [8] [9] , similar to RDP to DP conversion (see Appendix N). Since we work with the replacement definition of dataset adjacency, to unlearn a data point d i we can simply replace it with any data point d ′ i ∈ X for the updated dataset D ′ in practice. One may also repeat the entire analysis with the objective function being the summation of individual loss for the standard add/remove notion of dataset adjacency. Finally, we will also leverage the infinite Wasserstein distance in our analysis. Definition 2.4 (W ∞ distance). The ∞-Wasserstein distance between distributions µ and ν on a Banach space (R d , ∥ • ∥) is defined as W ∞ (µ, ν) = inf γ∈Γ(µ,ν) ess sup (x,y)∼γ ∥x -y∥, where (x, y) ∼ γ means that the essential supremum is taken relative to measure γ over R d ×R d parametrized by (x, y). Γ(µ, ν) is the collection of couplings of µ and ν.An important component of our analysis is to leverage the result of [16] , which is based on the celebrated privacy amplification by iteration analysis originally proposed in [20] and also utilized for DP guarantees of PNSGD in [15] . The goal of [16] is to analyze the mixing time of the PNSGD process, which can be viewed as the contractive noisy iterations due to the contractiveness of the gradient update under strong convexity assumption.. Given an initial distribution µ 0 ∈ P(R d ), a sequence of (random) c-contractive (equivalently, c-Lipschitz) functions ψ k : R d → R d , and a sequence of noise distributions ζ k , we define the c-Contractive Noisy Iteration (c-CNI) by the update rule X k+1 = ψ k+1 (X k ) + W k+1 , where W k+1 ∼ ζ k independently and X 0 ∼ µ 0 . We denote the law of the final iterate X K by CNI c (µ 0 , {ψ k }, {ζ k }). Lemma 2.6 (Metric-aware privacy amplification by iteration bound [20] , simplified by [16] in Proposition 2.10). SupposeX K ∼ CNI c (µ 0 , {ψ k }, {ζ k }) and X ′ K ∼ CNI c (µ ′ 0 , {ψ k }, {ζ k })where the initial distribution satisfy W ∞ (µ 0 , µ ′ 0 ) ≤ Z, the update function ψ k are c-contractive, and the noise distributionsEQUATIONRoughly speaking, Lemma 2.6 shows that if we have the W ∞ distance of initial distributions of two PNSGD processes on the same dataset, we have the corresponding Rényi difference bound after K iterations. The projection set diameter 2R is a default upper bound for W ∞ distance if we do not care about the initial distributions as the case studied in [16] for mixing time analysis. In the unlearning scenario, the initial distributions of the unlearning processes, denoted by ν D|B , ν D ′ |B , are much more relevant. We can show a much tighter bound by analyzing W ∞ (ν D|B , ν D ′ |B ) along the adjacent PNSGD learning processes. 
certified unlearning guaranatee for pnsgd: 
 We start with introducing the (un)learning process with PNSGD with a cyclic mini-batch strategy (Algorithm 1). Note that this mini-batch strategy is not only commonly used for practical DP-SGD implementations in privacy libraries [21] , but also in theoretical analysis for DP guarantees [22] .For the learning mechanism M, we optimize the objective function with PNSGD on dataset D (line 3-8 in Algorithm 1). η, σ2 > 0 are hyperparameters of step size and noise variance respectively. The initialization ν 0 is an arbitrary distribution supported on C R if not specified. For the unlearning mechanism U, we fine-tune the current parameter with PNSGD on the updated dataset D ′ subject to the unlearning request (line 10-15 in Algorithm 1) with y 0 0 = x 0 T = M(D). For the rest of the paper, we denote ν j t , ρ j k as the probability density of x j t , y j k respectively. Furthermore, we denote B = {B j } n/b-1 j=0 the minibatch sequence described in Algorithm 1, where b is the step size and we assume n is divided by b throughout the paper for simplicity 2 . We use ν •|B to denote the conditional distribution of ν • given B.Now we introduce the certified unlearning guarantees for PNSGD and the corresponding analysis illustrated in Figure 1 . We first prove that for any fixed mini-batch sequence B, the limiting distribution ν D|B of the learning process exists, is unique, and stationery. The proof is deferred to Appendix E and is based on applying the results in [23] to establish the ergodicity of the learning process x 0 t . Theorem 3.1. Suppose that the closed convex set C ⊂ R d is bounded with C having a positive Lebesgue measure and that ∇f (•;d i ) : C → R d is continuous for all i ∈ [n].The Markov chain {x t := x 0 t } in Algorithm 1 for any fixed mini-batch sequence B admits a unique invariant probability measure ν D|B on the Borel σ-algebra of C. Furthermore, for any x ∈ C, the distribution of x t conditioned on x 0 = x converges weakly to ν D|B as t → ∞, where ν D|B is the conditional distribution of ν D given B.Suppose the training epoch T is large enough so that the model is well-trained for now, which means M(D) ∼ ν D|B = ρ 0 0|B and our target "retraining distribution" is ν D ′ |B . Our goal is then to upper bound the Rényi difference d α (ρ 0 K|B , ν D ′ |B ) after K unlearning epochs. In the case of insufficient training, the privacy loss is d α (ρ 0 K|B , ν = x 0 T = M(D).Given any fixed mini-batch sequence B, for any α > 1, let η ≤ 1 L , the output of the K th unlearning iteration satisfies (α, ε)-RU for any adjacent dataset D, D ′ , whereEQUATION,and c = 1 -ηm.As we explained earlier, we need non-trivial W ∞ bounds for adjacent PNSGD processes to obtain better unlearning guarantees when applying Lemma 2.6. We provide such results below and the proofs are deferred to Appendix L and M respectively. W ∞ (ν 0 T |B , ν 0,′ T |B ) ≤ min 1 -c T n/b 1 -c n/b c n/b-j0-1 2ηM b , 2R .Lemma 3.4 (W ∞ between PNSGD learning process to its stationary distribution). Following the same setting as in Theorem 3.2 and denote the initial distribution of the unlearning process as ν 0 0 . Then we haveW ∞ (ν 0 T |B , ν D|B ) ≤ (1 -ηm) T n/b W ∞ (ν 0 0 , ν D|B ). Remark 3.5.In [15] , the authors used the default projection set diameter 2R as the W ∞ distance upper bound for their DP results, see equations (3.5) and (5.2) therein. However, it yields a vacuous bound as an unlearning guarantee compared to retraining from scratch. Note that our tighter bound for W ∞ distance is also useful for deriving later sequential unlearning guarantees compared to the prior work based on the analysis of Langevein dynamics [11] . Interestingly, this improved result can also be utilized for tightening the DP guarantee in [15] and make it more practically useful, as 2R can be very large in practice, which may be of independent interest. We are ready to provide the sketch of proof for Theorem 3.2. Sketch of proof. First note that the PNSGD update leads to a (1 -ηm)-CNI process when η ≤ 1/L for any mini-batch sequence. Recall that y j k is the unlearning process at epoch k at iteration j, starting from y 0 0 = x 0 T = M(D). Consider the "adjacent" process y j,′ k starting from y 0,′ 0 = x 0,′ T = M(D ′ ) but still fine-tune on D ′ so that y j k , y j,′ k only differ in their initialization. Now, consider three distributions: ν D|B , ν 0 T |B , ρ 0 K|B are the stationary distribution for the learning processes, learning process at epoch T and unlearning process at epoch K respectively. Similarly, consider the "adjacent" processes that learn on D ′ and still unlearn on D ′ (see Figure 1 for the illustration). Denote distributions ν D ′ |B , ν 0,′ T |B , ρ 0,′ K|B for these processes similarly. Note that our goal is to bound d α (ρ 0 K|B , ν 0,′ T |B ) for the RU guarantee. By weak triangle inequality [19] , we can upper bound it in terms of d 2α (ρ 0 K|B , ν D ′ |B ) and d 2α (ν D ′ |B , ν 0,′ T |B ), which are the ε 2 and ε 1 terms in Theorem 3.2 respectively. For d α (ν D ′ |B , ν 0,′ T |B ), we leverage the naive 2R bound for the W ∞ distance between ν D ′ |B , ν 0,′ 0|B and applying Lemma 2.6 leads to the desired result. For d α (ρ 0 K|B , ν D ′ |B ), by triangle inequality of W ∞ and Lemma 3.3, 3.4 one can show that the W ∞ between ρ 0 0|B , ν D ′ |B is bounded by Z B in Theorem 3.2. Further applying Lemma 2.6 again completes the proof. Remark 3.6. Our proof only relies on the bounded gradient difference ∥∇f (x; d)-∇f (x; d ′ )∥ ≤ 2M ∀x ∈ R d and ∀d, d ′ ∈ X hence M -Lipchitz assumption can be replaced. In practice, we can leverage the gradient clipping along with a ℓ 2 regularization for the convex objective function [22] .The convergent case. In practice, one often requires the model to be "well-trained", where a similar assumption is made in the prior unlearning literature [7, 8] . Under this assumption, we can further simplify Theorem 3.2 into the following corollary. Corollary 3.7. Under the same setting as of Theorem 3.2. When we additionally assume T is sufficiently large so that y 0 0 = M (D) ∼ ν D|B . Then for any α > 1 and η ≤ 1 L , the output of the K th unlearning iteration satisfies (α, ε)-RU with c = 1 -ηm, whereε ≤ αZ 2 B 2ησ 2 c 2Kn/b , Z B = min 1 1 -c n/b 2ηM b , 2R .For simplicity, the rest of the discussion on our PNSGD unlearning will based on the well-trained assumption. From Corollary 3.7 one can observe that a smaller b leads to a better decaying rate (c 2Kn/b ) but also a potentially worse initial distance Z B = O(1/((1 -c n/b )b)). InZ B = O(ηM/((1 -c n/b )b)) of such initial W ∞ distance in Lemma 3.3.On the other hand, even if both ν 0 , ν D are both Gaussian with identical various and mean difference norm of Ω(1), we have W ∞ (ν 0 , ν D ′ |B ) = Ω(1) for retraining from scratch. Our results show that a larger mini-batch size b leads to more significant complexity savings compared to retraining. As we discussed above, one should choose a moderate size b to balance between privacy and utility. In our experiment, we show that for commonly used mini-batch sizes (i.e., b ≥ 32), our PNSGD unlearning is still much more efficient in complexity compared to retraining.Improved bound with randomized B. So far our results are based on a fixed (worst-case) mini-batch sequence B. One can improve the privacy bound in Corollary 3.7 by taking the randomness of B into account under a non-adaptive unlearning setting. That is, the unlearning request is independent of the mini-batch sequence B. See also our discussion in the related work. By taking the average of the bound in Corollary 3.7 in conjunction with an application of joint convexity of KL divergence [22] , we can derive an improved guarantee beyond the worst-case of B. Corollary 3.8. Under the same setting as of Theorem 3.2 but with random mini-batch sequences described in Algorithm 1. Then for any α > 1, and η ≤ 1 L , the output of the K th unlearning iteration satisfies (α, ε)-RU with c = 1 -ηm, where ε≤ 1 α-1 log E B exp α(α-1)Z 2 B 2ησ 2 c 2Kn/band Z B is the bound described in Lemma 3.3.Different mini-batch sampling strategies. We remark that our analysis can be extended to other mini-batch sampling strategies, such as sampling without replacement for each iteration. However, this strategy leads to a worse Z B in our analysis of Lemma 3.3, which may seem counter-intuitive at first glance. This is due to the nature of the essential supremum taken in W ∞ . Although sampling without replacement leads to a smaller probability of sampling the index that gets modified due to the unlearning request, it is still non-zero for each iteration. Thus the worst-case difference 2ηM/b between two adjacent learning processes in the mini-batch gradient update occurs at each iteration, which degrades the factor 1/(1 -c n/b ) to 1/(1 -c) in Lemma 3.3. As a result, we choose to adopt the cyclic mini-batch strategy so that such a difference is guaranteed to occur only once per epoch and thus a better bound on W ∞ .Discussion on utility bound. One can leverage the utility analysis in section 5 of [24] to derive the utility guarantee for the full batch setting b = n. We relegate the proof to Appendix K. Proposition 3.9. Under the same setting as Corollary 3.7 with b = n, η ≤ m 2L 2 and assume the minimizer of any f D is in the relative interior of C R ⊆ R d , for any given adjacent dataset pair D, D ′ the output of the K th unlearning iteration y 0 K satisfiesEQUATIONNote that a similar analysis applies to both the mini-batch (i.e., b ≤ n) and non-convergent case (i.e., Theorem 3.2) but the result is more complicated. We leave the rigorous analysis as future work. An important remark is that the second term 2Ldσ 2 m is the excess risk of ν D ′ , which is controlled by the noise scale σ. This presents the privacy-utility trade-off as demonstrated in the DP scenario in [24] .Without strong convexity. Since Lemma 2.6 also applies to the convex-only case (i.e., m = 0 so that c = 1), repeating the same analysis leads to the following extension. Corollary 3.10. Under the same setting as of Theorem 3.2 but without strong convexity (i.e., m = 0). When we additionally assume T is sufficiently large so that y 0 0 = M (D) ∼ ν D|B . Then for any α > 1, and η ≤ 1 L , the output of the K th unlearning iteration satisfies (α, ε)-RU, whereε ≤ αZ 2 B 2ησ 2 b Kn , Z B = min 2ηM T b , 2R .There are several remarks for Corollary 3.10. First, the privacy loss now only decays linearly instead of exponentially as opposed to the strongly convex case. Second, Z B now can grow linearly in training epoch T . As a result, the computational benefit of our approach compared to retraining may vanish for large T such that 2ηM T b ≥ 2R. Nevertheless, the computational benefit against retraining persists for moderate T such that 2ηM T b < 2R. This condition can be met if the model learns reasonably well with moderate T and the projection diameter 2R is not set to be extremely small. For example, with 2R = 10, b = 128, η = 1 and M = 1, any training epoch T < 640 will lead to 2ηM T b < 2R. Still, we conjecture a better analysis is needed beyond strong convexity.So far we have focused on one unlearning request and unlearning one point. In practice, multiple unlearning requests can arrive sequentially (sequential unlearning) and each unlearning request may require unlearning multiple points (batch unlearning). Below we demonstrate that our PNSGD unlearning naturally supports sequential and batch unlearning as well.Sequential unlearning. As long as we can characterize the initial W ∞ distance for any mini-batch sequences, we have the corresponding (α, ε)-RU guarantee due to Corollary 3.7. Thanks to our geometric view of the unlearning problem (Figure 2 ) and W ∞ is indeed a metric, applying triangle inequality naturally leads to an upper bound on the initial W ∞ distance. By combining Lemma 3.3 and Lemma 3.4, we have the following sequential unlearning guarantee. Theorem 3.11 (W ∞ bound for sequential unlearning). Under the same assumptions as in Corollary 3.7. Assume the unlearning requests arrive sequentially such that our dataset changes from D = D 0 → D 1 → . . . → D S , where D s , D s+1 are adjacent. Let y j,(s) k be the unlearned parameters for the s th unlearning request at k th unlearning epoch and j th iteration following Algorithm (1) on D s and y 0,(s+1) 0 = y 0,(s) Ks ∼ νDs|B , where y 0,(0) 0 = x ∞ and K s is the unlearning steps for the s th unlearning request. For any s ∈EQUATIONB = Z B , Z B and c are described in Corollary 3.7. By combining Corollary 3.7 and Theorem 3.11, we can establish the least unlearning iterations of each unlearning request {K s } S s=1 to achieve (α, ε)-RU simultaneously. Notably, our sequential unlearning bound is much better than the one in [11] , especially when the number of unlearning requests is large. The key difference is that [11] have to leverage weak triangle inequality for Rényi divergence, which double the Rényi divergence order α for each sequential unlearning request. In contrast, since our analysis only requires tracking the initial Unlearning 100 points sequentially versus baseline. For LU, since their unlearning complexity only stays in a reasonable range when combined with batch unlearning of size S sufficiently large, we report such a result only. (c,d) Noise-accuracy-complexity trade-off of PNSGD for unlearning 100 points sequentially with various mini-batch sizes b, where all methods achieve (ϵ, 1/n)-unlearning guarantee with ϵ = 0.01. We also report the required accumulated epochs for retraining for each b. W ∞ distance, where the standard triangle inequality can be applied. As a result, our analysis can better handle the sequential unlearning case. We also demonstrate in Section 4 that the benefit offered by our results is significant in practice.𝜈̅ 𝒟 |ℬ 𝑍 ℬ ( ) = 𝑍 ℬ 𝜈 𝒟|ℬ (a) 𝑍 ℬ ( ) (b) Unlearning process 𝒰 𝑍 ℬ 𝑍 ℬ ( ) 𝑍 ℬ ( ) ≤ 𝑐 𝑍 ℬ ( ) + 𝑍 ℬ (Triangle inequality) 𝑐 ≤ 1 𝑍 ℬ 𝑑 ℬ 𝑑 ℬ 𝜈 𝒟 |ℬ 𝜈 𝒟 |ℬ 𝜈̅ 𝒟 |ℬ 𝜈 𝒟|ℬ 𝜈 𝒟 |ℬ 𝜈 𝒟 |ℬBatch unlearning. We can extend Lemma 3.3 to the case that adjacent dataset D, D ′ can differ in S ≥ 1 points, which further leads to batch unlearning guarantee. We relegate the result in Appendix J. 
experiments: 
 Benchmark datasets. We consider binary logistic regression with ℓ 2 regularization. We conduct experiments on MNIST [25] and CIFAR10 [26] , which contain 11,982 and 10,000 training instances respectively. We follow the setting of [7, 11] to distinguish digits 3 and 8 for MNIST so that the problem is a binary classification. For the CIFAR10 dataset, we distinguish labels 3 (cat) and 8 (ship) and leverage the last layer of the public ResNet18 [27] embedding as the data features, which follows the setting of [7] with public feature extractor.Baseline methods. Our baseline methods include Delete-to-Descent (D2D) [9] and Langevin Unlearning (LU) [11] , which are the state-of-the-art full-batch gradient-based approximate unlearning methods. Note that when our PNSGD unlearning chooses b = n (i.e., full batch), the learning and unlearning iterations become PNGD which is identical to LU. Nevertheless, the corresponding privacy bound is still different as we leverage the analysis different from those based on Langevin dynamics in [11] . Hence, we still treat these two methods differently in our experiment. For D2D, we leverage Theorem 9 and 28 in [9] for privacy accounting depending on whether we allow D2D to have an internal non-private state. Note that allowing an internal non-private state provides a weaker notion of privacy guarantee [9] and both PNSGD and LU by default do not require it. We include those theorems for D2D and a detailed explanation of its possible non-privacy internal state in Appendix O. For LU, we leverage their Theorem 3.2, and 3.3 for privacy accounting [11] , which are included in Appendix P.All experimental details can be found in Appendix N, including how to convert (α, ε)-RU to the standard (ϵ, δ)-unlearning guarantee. Our code is publicly available 3 . We choose δ = 1/n for each dataset and require all tested unlearning approaches to achieve (ϵ, δ)-unlearning with different ϵ. We report test accuracy for all experiments as the utility metric. We set the learning iteration T = 10, 20, 50, 1000 to ensure PNSGD converges for mini-batch size b = 32, 128, 512, n respectively. All results are averaged over 100 independent trials with standard deviation reported as shades in figures.Unlearning one data point with K = 1 epoch. We first consider the setting of unlearning one data point using only one unlearning epoch (Figure 3a ). For both LU and PNSGD, we use only K = 1 unlearning epoch. Since D2D cannot achieve a privacy guarantee with only limited (i.e., less than 10) unlearning epoch without a non-private internal state, we allow D2D to have it and set K = 1, 5 in this experiment. Even in this case, PNSGD still outperforms D2D in both utility and unlearning complexity. Compared to LU, our mini-batch setting either outperforms or is on par with it. Interestingly, we find that LU gives a better privacy bound compared to full-batch PNSGD (b = n) and thus achieves better utility under the same privacy constraint, see Appendix P for the detailed comparisons. Nevertheless, due to the use of weak triangle inequality in LU analysis, we will see that our PNSGD can outperform LU significantly for multiple unlearning requests.Unlearning multiple data points. Let us consider the case of multiple (100) unlearning requests (Figure 3b ). We let all methods achieve the same (1, 1/n)-unlearning guarantee for a fair comparison. We do not allow D2D to have an internal non-private state anymore in this experiment for a fair comparison. Since the privacy bound of LU only gives reasonable unlearning complexity with a limited number of sequential unlearning updates [11] , we allow it to unlearn S = 10 points at once. We observe that PNSGD requires roughly 10% and 2% of unlearning epochs compared to D2D and LU for b = n and b = 128 respectively, where all methods exhibit similar utility (0.9 and 0.98 for MNIST and CIFAR10 respectively). It shows that PNSGD is much more efficient compared to D2D and LU. Notably, while both PNSGD with b = n and LU (un)learn with PNGD iterations, the resulting privacy bound based on our PABI-based analysis is superior to the one pertaining to Langevin-dynamic-based analysis in [11] . See our discussion in Section 3.2 for the full details.Privacy-utility-complexity trade-off. We now investigate the inherent utility-complexity trade-off regarding noise standard deviation σ and mini-batch size b for PNSGD under the same privacy constraint, where we require all methods to achieve (0.01, 1/n)-unlearning guarantee for 100 sequential unlearning requests (Figure 3c and 3d ). We can see that smaller σ leads to a better utility, yet more unlearning epochs are needed for PNSGD to achieve ϵ = 0.01. On the other hand, smaller mini-batch size b requires fewer unlearning epochs K as shown in Figure 3d , since more unlearning iterations are performed per epoch. Nevertheless, we remark that choosing b too small may lead to degradation of model utility or instability. Decreasing the mini-batch size b from 32 to 1 reduces the average accuracy of training from scratch from 0.87 to 0.64 and 0.97 to 0.81 on MNIST and CIFAR10 respectively for σ = 0.03. In practice, one should choose a moderate mini-batch size b to ensure both good model utility and unlearning complexity. Finally, we also note that PNSGD achieves a similar utility while much better complexity compared to retraining from scratch, where PNSGD requires at most 1, 5 unlearning epochs per unlearning request for b = 32, 512 respectively. 
limitations and conclusion: 
 Limitation. Since our analysis is built on the works of [15, 16] , we share the same limitation that the (strong) convexity assumption is required. It is an open problem on how to extend such analysis beyond convexity assumption as stated in [15, 16] . While we resolve this open problem for establishing DP properties of PNSGD in our recent work [28] , it is still unclear whether the same success can be generalized to the unlearning problem. One interesting direction is to leverage the Langevin dynamic analysis [29] instead as in [11] , which can deal with non-convex problems in theory yet we conjecture the resulting bounds can be loose, and more complicated. 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA]Justification: [NA] Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?Answer: [Yes] Justification: All used datasets are provided with citations to the original authors and works, where all of them have proper open access license.Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.• If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. • If this information is not available online, the authors are encouraged to reach out to the asset's creators. 
new assets: 
 Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?Answer: [NA]Justification: [NA] Guidelines:• The answer NA means that the paper does not release new assets.• Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc. • The paper should discuss whether and how consent was obtained from people whose asset is used. • At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file. 
crowdsourcing and research with human subjects: 
 Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?Answer: [NA]Justification: [NA] Guidelines:• The answer NA means that the paper does not involve crowdsourcing nor research with human subjects. • Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper. • According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector. 
institutional review board (irb) approvals or equivalent for research with human subjects: 
 Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?Answer: [NA]Justification: [NA] Guidelines:• The answer NA means that the paper does not involve crowdsourcing nor research with human subjects. • Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.• We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution. • For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review. 
 
 Appendix: We propose to leverage projected noisy stochastic gradient descent (PNSGD) for machine unlearning problem. We provide its unlearning guarantees as well as many other algorithmic benefits of PNSGD for unlearning under the convexity assumption. Our results are closely related to our new results on infinite Wasserstein distance tracking of the adjacent (un)learning processes, which is also leveraged in our concurrent work for studying DP-PageRank algorithms [30] . Extensive experiments show that our approach achieves a similar utility under the same privacy constraint while using 2% and 10% of the gradient computations compared with the state-of-the-art gradient-based approximate unlearning methods for mini-batch and full-batch settings, respectively.Differential privacy of noisy gradient methods. DP-SGD [13] is arguably the most popular method for ensuring a DP guarantee for machine learning models. Since it leverages the DP composition theorem and thus the privacy loss will diverge for infinite training epochs. Recently, researchers have found that if we only release the last step of the trained model, then we can do much better than applying the composition theorem. A pioneer work [31] studied the DP properties of Langevin Monte Carlo methods. Yet, they do not propose to use noisy GD for general machine learning problems. A recent line of work [22, 32] shows that PNSGD training can not only provide DP guarantees, but also the privacy loss is at most a finite value even if we train with an infinite number of iterations. The main analysis therein is based on the analysis of Langevin Monte Carlo [29, 33] . In the meanwhile, [15] also provided the DP guarantees for PNSGD training but with analysis based on privacy amplification by iteration [20] . None of these works study how PNSGD can also be leveraged for machine unlearning.Since our analysis is built on the works of [15, 16] , we share the same limitation that the (strong) convexity assumption is required. It is an open problem on how to extend such analysis beyond convexity assumption as stated in [15, 16] . While we resolve this open problem for the DP properties of PNSGD in our recent work [28] , it is still unclear whether the same success can be generalized to the unlearning problem. One interesting direction is to leverage the Langevin dynamic analysis [29] instead as in [11] , which can deal with non-convex problems in theory yet we conjecture the resulting bounds can be loose, and more complicated.Our work study the theoretical unlearning guarantees of projected stochastic noisy gradient descent algorithm for convex problems. We believe our work is a foundational research and does not have a direct path to any negative applications.Let f : R d → R be a mapping. We define smoothness, Lipschitzness, and strong convexity as follows:EQUATIONm-strongly convex:EQUATIONEQUATIONFurthermore, we say f is convex means it is 0-strongly convex.Theorem. Suppose that the closed convex set C ⊂ R d is bounded with C having a positive Lebesgue measure and that ∇f (•;d i ) : C → R d is continuous for all i ∈ [n]. The Markov chain {x t := x 0 t } in Algorithm 1 for any fixed mini-batch sequence B = {B j } n/b-1 j=1admits a unique invariant probability measure ν D|B on the Borel σ-algebra of C. Furthermore, for any x ∈ C, the distribution of x t conditioned on x 0 = x converges weakly to ν D|B as t → ∞.The proof is almost identical to the proof of Theorem 3.1 in [11] and we include it for completeness. We start by proving that the process {x t := x 0 t } admits a unique invariant measure (Proposition E.1) and then show that the process converges to such measure which is in fact a probability measure (Theorem E.2). Combining these two results completes the proof of Theorem 3. admits a unique invariant measure (up to constant multiples) on B(C) that is the Borel σ-algebra of C.Proof. This proposition is a direct application of results from [23] . According to Proposition 10.4.2 in [23] , it suffices to verify that {x t } is recurrent and strongly aperiodic.1. Recurrency. Thanks to the Gaussian noise W t , {x t } is Leb-irreducible, i.e., it holds for any x ∈ C and any A ∈ B(C) with Leb(A) > 0 thatL(x, A) := P(τ A < +∞ | x 0 = x) > 0,where τ A = inf{t ≥ 0 : x t ∈ A} is the stopping time. Therefore, there exists a Borel probability measure ψ such that that {x t } is ψ-irreducible and ψ is maximal in the sense of Proposition 4.2.2 in [23] . Consider anyA ∈ B(C) with ψ(A) > 0. Since {x t } is ψ-irreducible, one has L(x, A) = P(τ A < +∞ | x 0 = x) > 0 for all x ∈ C.This implies that there exists T ≥ 0, δ > 0, and B ∈ B(C) with Leb(B) > 0, such thatP(x T ∈ A | x 0 = x) ≥ δ, ∀ x ∈ B. Therefore, one can conclude for any x ∈ C that U (x, A) := ∞ t=0 P(x t ∈ A | x 0 = x) ≥ ∞ t=1 P(x t+T ∈ A | x t ∈ B, x 0 = x) • P(x t ∈ B | x 0 = x) ≥ ∞ t=1 δ • inf y∈C P(x t ∈ B | x t-1 = y) = + ∞,where we used the fact that inf y∈C P( x t ∈ B | x t-1 = y) = inf y∈C P(x 1 ∈ B | x 0 = y) > 0 thatP(x 1 ∈ A | x 0 = x) ≥ ν 1 (A), ∀ x ∈ C, A ∈ B(C).Then {x t } is strongly aperiodic by the equation above and ν 1 (C) > 0 (see Section 5.4.3 in [23] for definition).The proof is hence completed.Theorem E.2. Under the same assumptions as in Proposition E.1, the Markov chain {x t } admits a unique invariant probability measure ν D|B on B(C). Furthermore, for any x ∈ C, the distribution of x t = x 0 t generated by the learning process in Algorithm 1 conditioned on x 0 = x converges weakly to ν D|B as t → ∞.Proof. It has been proved in Proposition E.1 that {x t } is strongly aperiodic and recurrent with an invariant measure. Consider any A ∈ B(C) with ψ(A) > 0 and use the same settings and notations as in the proof of Proposition E.1. There exists T ≥ 0, δ > 0, and B ∈ B(C) with Leb(B) > 0, such that P(x T ∈ A | x 0 = x) ≥ δ, ∀ x ∈ B. This implies that for any t ≥ 0 and any x ∈ C,P(x t+T +1 ∈ A | x t = x) = P(x T +1 ∈ A | x 0 = x) ≥ P(x T +1 ∈ A | x 1 ∈ B, x 0 = x) • P(x 1 ∈ B | x 0 = x) ≥ ϵ, where ϵ = δ • inf y∈C P(x 1 ∈ B | x 0 = y) > 0,which then leads to Q(x, A) := P(x t ∈ A, infinitely often) = +∞. This verifies that the chain {x t } is Harris recurrent (see Section 9 in [23] for definition). It can be further derived that for any x ∈ C,E(τ A | x 0 = x) = ∞ t=1 P(τ A ≥ t | x 0 = x) ≤ (T + 1) ∞ k=0 P(τ A > (T + 1)k | x 0 = x) ≤ (T + 1) ∞ k=1 (1 -ϵ) k < +∞.The bound above is uniform for all x ∈ C and this implies that C is a regular set of {x t } (see Section 11 in [23] for definition). Finally, one can apply Theorem 13.0.1 in [23] to conclude that there exists a unique invariant probability measure ν D on B(C) and that the distribution of x t converges weakly to ν D|B conditioned on x 0 = x for any x ∈ C.Theorem (RU guarantee of PNSGD unlearning, fixed B). Assume ∀d ∈ X , f (x; d) is L-smooth, M -Lipchitz and m-strongly convex in x. Let the learning and unlearning processes follow Algorithm 1 with y 0 0 = x 0 T = M(D). Given any fixed mini-batch sequence B, for any α > 1, let η ≤ 1 L , the output of the K th unlearning iteration satisfies (α, ε)-RU with c = 1 -ηm, whereε ≤ α -1/2 α -1 (ε 1 (2α) + ε 2 (2α)) , ε 1 (α) = α(2R) 2 2ησ 2 c 2T n/b , ε 2 (α) = αZ 2 B 2ησ 2 c 2Kn/b , Z B = 2Rc T n/b + min 1 -c T n/b 1 -c n/b 2ηM b , 2R .We first introduce an additional definition and a lemma needed for the our analysis. Definition F.1 (Shifted Rényi divergence). Let µ and ν be distributions defined on a Banach space (R d , ∥ • ∥). For parameters z ≥ 0 and α ≥ 1, the z-shifted Rényi divergence between µ and ν is defined asEQUATIONLemma F.2 (Data-processing inequality for Rényi divergence, Lemma 2.6 in [16] ). For any α ≥ 1, any (random) map h : R d → R d and any distribution µ, ν with support on R d ,EQUATIONwhere h # µ denotes the pushforward operation for a function h and distribution µ. Proposition F.3 (Weak Triangle Inequality of Rényi divergence, Corollary 4 in [19] ). For any α > 1, p, q > 1 satisfying 1/p + 1/q = 1 and distributions P, Q, R with the same support:D α (P ||R) ≤ α -1 p α -1 D pα (P ||Q) + D q(α-1/p) (Q||R).Proof. Recall that from the sketch of proof of Theorem 3.2, we have defined the six distributions: ν D|B , ν 0 T |B , ρ 0 K|B are the stationary distribution of the learning process, distribution at epoch T of the learning process and distribution at epoch K of the unlearning process. Note that we learn on dataset D and fine-tune on D ′ . On the other hand, the corresponding distributions of "adjacent" processes that learn on D ′ and still unlearn on D ′ are denoted as ν D ′ |B , ν 0,′ T |B , ρ 0,′ K|B similarly. Note that ν 0,′ T |B is the distribution of retraining from scratch on D ′ , and we aim to bound d α (ρ 0 K|B , ν 0,′ T |B ) for all possible D, D ′ pairs. By Proposition F.3, we know that for any α > 1, by choosing p = q = 2, we haveEQUATIONRecall the Definition 2.1 that d α (P, Q) = max(D α (P ||Q), D α (Q||P )) for distributions P, Q. The above inequality is correct since consider any distributions P, Q, R, by Proposition F.3 we haveEQUATIONEQUATIONEQUATIONwhere (a) is due to the definition of Rényi difference, (b) is due to the monotonicity of Rényi divergence in α, and (c) is due to the fact that for all α > 1,EQUATIONCombining these two bounds leads to the weak triangle inequality for Rényi difference.Now we establish the upper bound of d α (ν D ′ |B , ν 0,′ T |B ), which we denoted as ε 1 (α) in Theorem 3.2. We first note that due to the projection operator Π C R , we trivially have W ∞ (ν D ′ |B , ν 0 0 ) ≤ 2R. On the other hand, note that ν 0,′ T |B is the distribution of the learning process at epoch T with respect to dataset D ′ , where ν D ′ |B is the corresponding stationary distribution. Let us "unroll" iterations so that v = t n b + j. We apply Lemma 2.6 for these two processes, where the initial distribution are µ 0 = ν 0 0 and µ′ 0 = ν D ′ |B . The updates ψ v (x) = Π C (x) -η b i∈B j ∇f (Π C (x); d ′ i )are with respect to the dataset D ′ , and ζ v = N (0, ησ 2 I d ). First, note that we have ησ 2 instead of σ 2 as in the Lemma 2.6, hence we need to apply a change of variable. The only thing we are left to prove is that ψ v is c-contractive for c = 1 -ηm and any t, j. This is because for any mini-batch B j and any data point d ′ i ∈ X , i ∈ B j of size b, we haveEQUATIONEQUATIONEQUATIONFinally, due to data-processing inequality for Rényi divergence (Lemma F.2), applying the final projection step does not increase the corresponding Rényi divergence. As a result, by Lemma 2.6 we haveEQUATIONwhere the last inequality is due to our naive bound on W ∞ (ν D ′ |B , ν 0 0 ). One can repeat the same analysis for the direction D α (ν 0,′ T |B ||ν D ′ |B ), which leads to the same bound by symmetry of Lemma 2.6. Together we have shown thatEQUATIONNow we focus on bounding the term d α (ν D ′ |B , ρ 0 K|B ). We once again note that ν D ′ |B is the stationary distribution of the process ρ 0 K|B , since we fine-tune with respect to the dataset D ′ for the unlearning process. As a result, the same analysis above can be applied, where the only difference is the initialEQUATIONWe are left with establish an upper bound of W ∞ (ν D ′ |B , ρ 0 0|B ). Note that since W ∞ is indeed a metric, we can apply triangle inequality which leads to the following upper bound.EQUATIONFrom Lemma 3.3, we have thatEQUATIONwhere the last inequality is simply due to the fact that c < 1. Since the upper bound is independent of T , by letting T → ∞, and the definition that ν D|B , ν D ′ |B are the limiting distribution of ν 0 T |B , ν 0,′ T |B respectively, we haveEQUATIONOn the other hand, note that by definition we know that ρ 0 0|B = ν 0 T |B . Thus by Lemma 3.4 we haveEQUATIONwhere the last inequality is again due to the naive bound induced by the projection to C R for W ∞ (ν 0 0 , ν D|B ). Together we have thatEQUATIONCombining things we complete the proof.Theorem. Under the same assumptions as in Corollary 3. W ∞ (ν Ds-1|B , ν Ds|B ) ≤ Z (s) B ,whereEQUATIONB = Z B , Z B is described in Corollary 3.7 and c = 1 -ηm.The proof is a direct application of triangle inequality, Lemma 3.4 and 3.3. We will prove it by induction. For the base case s = 1 it trivial, since νD0 = ν D0 as we choose y 0,(0) 0 = x 0 ∞ . Thus by our definition that Z B is the upper bound of W ∞ (ν D|B , ν D ′ |B ) for any adjacent dataset D, D ′ . Apparently, we also haveW ∞ (ν D0|B , ν D1|B ) = W ∞ (ν D0|B , ν D1|B ) ≤ Z B = Z (1) B (27)For the induction step, suppose our hypothesis is true until s step. Then for the s + 1 step we haveEQUATIONEQUATIONEQUATIONwhere (a) is due to triangle inequality as W ∞ is a metric. (b) is due to Corollary 3.7, where Z B is an upper bound of W ∞ distance between any two adjacent stationary distributions. (c) is due to Lemma 3.4 and (d) is due to our hypothesis. Finally, note that 2R is a natural universal upper bound due to our projection on C R , which has diameter 2R. Together we complete the proof.Note that under the training convergent assumption, the target retraining distribution is directly ν D ′ |B so that we do not need the weak triangle inequality for Rényi difference. Similarly, we do not need the triangle inequality for the term Z B . Directly using ε 2 (α) with Z B = min Corollary. Under the same setting as of Theorem 3.2 but with random mini-batch sequences described in Algorithm 1. Then for any α > 1, and η ≤ 1 L , the output of the K th unlearning iteration satisfies (α, ε)-RU with c = 1 -ηm, whereε ≤ 1 α -1 log E B exp α(α -1)Z 2 B 2ησ 2 c 2Kn/b ,where Z B is the bound described in Lemma 3.3.We first restate the lemma in [22] , which is an application of the joint convexity of KL divergence. EQUATIONEQUATION)The proof of Corollary 3.8 directly follows by repeating the proof of Lemma 3.7 but with the B dependent Z B described in Lemma 3.3. Then leverage Lemma I.1 leads to the result.J W ∞ bound for batch unlearning W ∞ (ν 0 T |B , ν 0,′ T |B ) ≤ min 1 -c T 1 -c G-1 g=0 c n/b-jg-1 2ηM S jg b , 2R .Proof. The proof is a direct generalization of Lemma 3.3. Recall that for the per-iteration bound within an epoch, there are two possible cases: 1) we encounter the mini-batch B j that contains indices of replaced points 2) or not. This is equivalently to 1) j ∈ {j g } G-1 g=0 or 2) j / ∈ {j g } G-1 g=0 . Let us assume that case 1) happens and j = j g for g ∈ {0, . . . , G -1}. Also, let us denote the set of those indices as S jg with a slight abuse of notation. By the same analysis, we know thatEQUATION)For the first term, note that the gradient mapping (with respect to the same data point) is contractive with constant (1 -ηm) for η ≤ 1 L , thus we haveEQUATION)For the second term, by triangle inequality and the M -Lipschitzness of f we haveEQUATIONNote that there are S jg terms above. Combining things together, we haveEQUATIONIterate this bound over all n/b iterations within this epoch, we haveEQUATION)The rest analysis is the same as those in Lemma 3.3, where we iterate over T epochs, infimum over all possible coupling, and then simplify the expression using geometric series. Thus we complete the proof.K Proof of Proposition 3.9Proposition. Under the same setting as Corollary 3.7 with b = n, η ≤ m 2L 2 and assume the minimizer of any f D is in the relative interior of C R ⊆ R d , for any given adjacent dataset pair D, D ′ the output of the K th unlearning iteration y 0 K satisfiesEQUATION)The proof is based on the following key lemma from [24] . Lemma K.1. For M -Lipschitz, m-strongly convex and L-smooth loss function f D (x) over the closed bounded convex set C R ⊆ R d with radius R, step size η ≤ m 2L 2 and initial parameter x 0 ∼ ν 0 , the excess empirical risk of the learning process of Algorithm 1 for T epoch is bounded byEQUATION)where x ⋆ is the minimizer of f D (x) in the relative interior of C R and d is the dimension of parameter.Lemma (W ∞ between adjacent PNSGD learning processes). Consider the learning process in Algorithm 1 on adjacent dataset D and D ′ and a fixed mini-batch sequence B. Assume ∀d ∈ X , f (x; d) is L-smooth, M -Lipschitz and m-strongly convex in x. Let the index of different data point between D, D ′ belongs to mini-batch B j0 . Then for η ≤ 1 L and let c = (1 -ηm), we haveW ∞ (ν 0 T |B , ν 0,′ T |B ) ≤ min 1 -c T n/b 1 -c n/b c n/b-j0-1 2ηM b , 2R .Proof. We prove the bound of one iteration and iterate over that result under a specific coupling of the adjacent PNSGD learning processes, which is by definition an upper bound for taking infimum over all possible coupling. Given an mini-batch sequence B, assume the adjacent dataset D, D ′ differ at index i 0 ∈ [n] and i 0 belongs to j th 0 mini-batch (i.e., i 0 ∈ B j0 . For simplicity, we drop the condition on B for all quantities in the proof as long as it is clear that we always condition on a fixed B. Let us denote ψ j (x) = x -η b i∈B j ∇f (x; d ′ i ) and similar for ψ ′ j on D ′ . Note that for some coupling of ν j t , ν j,′ t denoted asEQUATION)Now, note that by definition the noise W j t is independent of x j t , we can simply choose the coupling γ so that W j t = W j,′ t for all t, j and x 0 0 = x 0,′ 0 due to the same initialization distribution. So the last term is 0. For the first term, there are two possible cases: 1) j = j 0 and 2) j ̸ = j 0 . For case 1), we haveEQUATION)For the first term, note that the gradient mapping (with respect to the same data point) is contractive with constant (1 -ηm) for η ≤ 1 L , thus we haveEQUATION)For the second term, by triangle inequality and the M -Lipschitzness of f we haveEQUATION)Combining things together, we haveEQUATION)On the other hand, for case 2) we can simply use the contrativity of the gradient update for all b terms, which leads toEQUATION)Combining these two cases, we haveEQUATIONwhere 1[j = j 0 ] is the indicator function of the event j = j 0 . Now we iterate this bound within the epoch t, which leads to an epoch-wise boundEQUATIONWe can further iterate this bound over all iterations T , which leads toEQUATIONwhere the last equality follows by our choice of coupling γ such that x 0 0 = x 0,′ 0 due to the same initialization distribution. Now by taking the infimum overall possible coupling γ and simply the expression, we haveEQUATIONFinally, note that there is also a naive bound W ∞ (ν 0 T |B , ν 0,′ T |B ) ≤ 2R due to the projection Π C R . Combine these two we complete the proof.Lemma (W ∞ between PNSGD learning process to its stationary distribution). Following the same setting as in Theorem 3.2 and denote the initial distribution of the unlearning process as ν 0 0 . Then we haveW ∞ (ν 0 T |B , ν D|B ) ≤ (1 -ηm) T n/b W ∞ (ν 0 0 , ν D|B ).Proof. We follow a similar analysis as in Lemma 3.3 but with two key differences: 1) our initial W ∞ distance is not zero and 2) we are applying the same c-CNI. Let us slightly abuse the notation to denote the process x j,′ t ∼ ν j,′ t be the process of learning on D as well but starting with ν 0,′ 0 = ν D|B . As before, we first establish one iteration bound with epoch t, then iterate over n/b iterations, and then iterate over T to complete the proof. Consider the two CNI processes x j t , x j,′ t with the same update ψ j (x) = x -η b i∈B j ∇f (x; d i ), where x 0 0 ∼ ν 0 0 and x 0,′ 0 ∼ ν D|B . We will use the similar coupling construction as in the proof of Lemma 3.3 (i.e., W j t = W j,′ t ). However, note that we will not restrict the coupling between the two initial distributions ν 0 0 = ν 0|B and ν 0,′ 0 = ν D|B . Let us denote the coupling for W as γ W and the coupling for the initial distributions ν 0 0 = ν 0|B and ν 0,′ 0 = ν D|B as γ I . We denote the overall coupling as γ = (γ I , γ W ). For our specific choice of coupling γ W , we haveEQUATIONwhere (a) is due to the fact that projection Π C R is 1-contractive, (b) is due to our coupling choice on the noise distribution, and (c) is due to the fact that ψ j is (1 -ηm) contractive and the coupling choice on the mini-batch. Now we iterate the bound above within the epoch and then over T epoch similar as before, which leads to the per epoch bound as followsEQUATIONNote that this holds for all coupling γ I for initial distributions. Let us now choose a specific (tie break arbitrary) γ I so that the W ∞ (ν 0|B , ν D|B ) = esssup γ I ∥x 0 0 -x 0,′ 0 ∥ is attained. For this specific coupling γ I , we haveEQUATIONFinally, by the definition of infimum and observe that x 0,′ T ∼ ν D|B due to the stationary property of ν D|B (which is independent of our choice of coupling), we haveEQUATIONHence we complete the proof.N.1 (α, ε)-RU to (ϵ, δ)-Unlearning ConversionLet us first state the definition of (ϵ, δ)-unlearning from prior literature [7] [8] [9] . Definition N.1. Consider a randomized learning algorithm M : X n → R d and a randomized unlearning algorithm U : R d × X n × X n → R d . We say (M, U) achieves (ϵ, δ)-unlearning if for any adjacent datasets D, D ′ and any event E, we haveEQUATIONEQUATIONFollowing the same proof of RDP-DP conversion (Proposition 3 in [19] ), we have the following (α, ε)-RU to (ϵ, δ)-unlearning conversion as well.Proposition N.2. If (M, U) achieves (α, ε)-RU, it satisfies (ϵ, δ)-unlearning as well, whereEQUATIONMNIST [25] contains the grey-scale image of number 0 to number 9, each with 28 × 28 pixels. We follow [9] to take the images with the label 3 and 8 as the two classes for logistic regression. The training data contains 11264 instances in total and the testing data contains 1984 samples. We spread the image into an x ∈ R d , d = 724 feature as the input of logistic regression.[26] contains the RGB-scale image of ten classes for image classification, each with 32 × 32 pixels. We also select class #3 (cat) and class #8 (ship) as the two classes for logistic regression. The training data contains 9728 instances and the testing data contains 2000 samples. We apply data pre-processing on CIFAR-10 by extracting the compact feature encoding from the last layer before pooling of an off-the-shelf pre-trained ResNet18 model [27] from Torch-vision library [34, 35] as the input of our logistic regression. The compact feature encoding isx ∈ R d , d = 512.All the inputs from the datasets are normalized with the ℓ 2 norm of 1. Note that We drop some date points compared with [11] to make the number of training data an integer multiple of the maximum batch size in our experiment, which is 512.Hardware and Frameworks All the experiments run with PyTorch=2.1.2 [36] and numpy=1.24.3 [37] . The codes run on a server with a single NVIDIA RTX 6000 GPU with AMD EPYC 7763 64-Core Processor.Problem Formulation Given a binary classification task D = {x i ∈ R d , y i ∈ {-1, +1}} n i=1 , our goal is to obtain a set of parameters w that optimizes the objective below:EQUATIONwhere the objective consists of a standard logistic regression loss l(w ⊤ x i , y i ) = -log σ(y i w ⊤ x i ), where σ(t) = 1 1+exp(-t) is the sigmoid function; and a ℓ 2 regularization term where λ is a hyperparameter to control the regularization, and we set λ as 10 -6 × n across all the experiments. By simple algebra one can show that [7] EQUATIONEQUATIONDue to σ(y i w ⊤ x i ) ∈ [0, 1], it is not hard to see that we have smoothness L = 1/4 + λ and strong convexity λ. The constant meta-data of the loss function in equation ( 88) above for the two datasets is shown in the table below: The per-sample gradient with clipping w.r.t. the weights w of the logistic regression loss function is given as:EQUATIONwhere Π C M denotes the gradient clipping projection into the Euclidean ball with the radius of M , to satisfy the Lipschitz constant bound. According to Proposition 5.2 of [22] , the per-sampling clipping operation still results in a L-smooth, m-strongly convex objective. The resulting stochastic gradient update on the full dataset is as follows:EQUATIONFinally, we remark that in our specific case since we have normalized the features of all data points (i.e., ∥x∥ = 1), by the explicit gradient formula we know that ∥(σ(y i w ⊤ x i ) -1)y i x i ∥ ≤ 1.Learning from scratch set-up For the baselines and our PNSGD unlearning framework, we all sample the initial weight w randomly sampled from i.i.d Gaussian distribution N (µ 0 , 2σ 2 m ), where µ 0 is a hyper-parameter denoting the initialization mean and we set as 0. For the PNSGD unlearning method, the burn-in steps T w.r.t. different batch sizes are listed in Table . 2. we follow [11] and set T = 10, 000 for the baselines (D2D and Langevin unlearning) to converge. Unlearning request implementation. In our experiment, for an unlearning request of removing data point i, we replace its feature with random features drawn from N (0, I d ) and its label with a random label drawn uniformly at random drawn from all possible classes. This is similar to the DP replacement definition defined in [38] , where they replace a point with a special null point ⊥.General implementation of baselines D2D [9] :• Across all of our experiments involved with D2D, we follow the original paper to set the step size as 2/(L + m).• For the experiments in Fig. 3a , we calculate the noise to add after gradient descent with the nonprivate bound as illustrated in Theorem. O.1 (Theorem 9 in [9] ); For experiments with sequential unlearning requests in Fig. 3b , we calculate the least step number and corresponding noise with the bound in Theorem. O.2(Theorem 28 in [9] ).• The implementation of D2D follows the pseudo code shown in Algorithm 1,2 in [9] as follows:Algorithm 2 D2D: learning from scratch w t = w t-1 -2 L+m × 1 n n i=1 (∇ clip l(w T t-1 x i , y i )) 5: end for 6: Output: ŵ = w T Algorithm 3 D2D: unlearning 1: Input: dataset D i-1 , update u i ; model w i 2: Update dataset D i = D i-1 • u i 3: Initialize w ′ 0 = w i 4: for t = 1, . . . , I do 5: w ′ t = w ′ t-1 -2 L+m × 1 n n i=1 ∇ clip l((w ′ t-1 ) T x i , y i )) 6: end for 7: Calculate γ = L-m L+m 8: Draw Z ∼ N (0, σ 2 I d ) 9: Output ŵi = w ′ Ti + ZThe settings and the calculation of I, σ in Algorithm. 3 are discussed in the later part of this section and could be found in Section. O.Langevin unlearning [11] We follow exactly the experiment details described in [11] .General Implementation of PNSGD Unlearning (ours)• We set the step size η for the PNSGD unlearning framework across all the experiments as 1/L.• The pseudo-code for PNSGD unlearning framework is shown in Algorithm. 1.In this experiment, we first train the methods on the original dataset D from scratch to obtain the initial weights w 0 . Then we randomly remove a single data point (S = 1) from the dataset to get the new dataset D ′ , and unlearn the methods from the initial weights ŵ and test the accuracy on the testing set. We follow [11] and set the target ε with 6 different values as [0.05, 0.1, 0.5, 1, 2, 5]. For each target ε:• For D2D, we set two different unlearning gradient descent step budgets as I = 1, 5, and calculate the corresponding noise to be added to the weight after gradient descent on D according to Theorem. O.1.• For the Langevin unlearning framework [11] , we set the unlearning fine-tune step budget as K = 1 only, and calculate the smallest σ that could satisfy the fine-tune step budget and target ε at the same time. The calculation follows the binary search algorithm described in the original paper.• For the stochastic gradient descent langevin unlearning framework, we also set the unlearning fine-tune step budget as K = 1, and calculate the smallest σ that could satisfy the fine-tune step budget and target ε at the same time. The calculation follows the binary search algorithm as follows:Algorithm 4 PNSGD Unlearning: binary search σ that satisfy K and target ε budget EQUATIONK = K + 1 11: end while 12: Return K We set the projection radius as R = 100, and the σ found is listed in Table . 3. 3b In this experiment, we fix the target ε = 1, we set the total number of data removal as 100. We show the accumulated unlearning steps w.r.t. the number of data removed. We first train the methods from scratch to get the initial weight w 0 , and sequentially remove data step by step until all the data points are removed. We count the accumulated unlearning steps K needed in the process.• For D2D, According to the original paper, only one data point could be removed at a time. We calculate the least required steps and the noise to be added according to Theorem. O.2.• For Langevin unlearning, we fix the σ = 0.03, and we let the model unlearn [5, 10, 20] per time. The least required unlearning steps are obtained following [11] .• For Stochastic gradient descent langevin unlearning, we replace a single point per request and unlearn for 100 requests. We obtain the least required unlearning step K following Corollary 3.7. The pseudo-code is shown in Algorithm. 6.Algorithm 6 PNSGD Unlearning: find the least unlearn step K in sequential settings 1: Input:target ε, σ, total removal S 2: K list = [] 3: for i in range(S) do 4:Initialize K list [i -1] = 1, ϵ > ε 5:while ϵ > ε do6: ϵ = min α>1 [ε(α, σ, b, K list [i -1]) + log(1/δ) α-1 ] 7: K list [i -1] = K list [i -1] + 1 8:end while 9: end for 10: Return K list O Unlearning Guarantee of Delete-to-Descent [9] The discussion is similar to those in [11] , we include them for completeness.Theorem O.1 (Theorem 9 in [9] , with internal non-private state). Assume for all d ∈ X , f (x; d) is m-strongly convex, M -Lipschitz and L-smooth in x. Define γ = L-m L+m and η = 2 L+m . Let the learning iteration T ≥ I + log( 2Rmn 2M )/ log(1/γ) for PGD (Algorithm 1 in [9] ) and the unlearning algorithm (Algorithm 2 in [9] , PGD fine-tuning on learned parameters before adding Gaussian noise) run with I iterations. Assume ϵ = O(log(1/δ)), let the standard deviation of the output perturbation gaussian noise σ to beEQUATION)Then it achieves (ϵ, δ)-unlearning for add/remove dataset adjacency.Theorem O.2 (Theorem 28 in [9] , without internal non-private state). Assume for all d ∈ X , f (x; d) is m-strongly convex, M -Lipschitz and L-smooth in x. Define γ = L-m L+m and η = 2 L+m . Let the learning iteration T ≥ I + log( 2Rmn 2M )/ log(1/γ) for PGD (Algorithm 1 in [9] ) and the unlearning algorithm (Algorithm 2 in [9] , PGD fine-tuning on learned parameters after adding Gaussian noise) run with I + log(log(4di/δ))/ log(1/γ) iterations for the i th sequential unlearning request, where I satisfiesEQUATION)Assume ϵ = O(log(1/δ)), let the standard deviation of the output perturbation gaussian noise σ to beEQUATION)Then it achieves (ϵ, δ)-unlearning for add/remove dataset adjacency.Note that the privacy guarantee of D2D [9] is with respect to add/remove dataset adjacency and ours is the replacement dataset adjacency. However, by a slight modification of the proof of Theorem O.1 and O.2, one can show that a similar (but slightly worse) bound of the theorem above also holds for D2D [9] . For simplicity and fair comparison, we directly use the bound in Theorem O.1 and O.2 in our experiment. Note that [38] also compares a special replacement DP with standard add/remove DP, where a data point can only be replaced with a null element in their definition. In contrast, our replacement data adjacency allows arbitrary replacement which intuitively provides a stronger privacy notion.The non-private internal state of D2D. There are two different versions of the D2D algorithm depending on whether one allows the server (model holder) to save and leverage the model parameter before adding Gaussian noise. The main difference between Theorem O.1 and O.2 is whether their unlearning process starts with the "clean" model parameter (Theorem O.1) or the noisy model parameter (Theorem O.2). Clearly, allowing the server to keep and leverage the non-private internal state provides a weaker notion of privacy [9] . In contrast, our PNSGD unlearning approach by default only keeps the noisy parameter so that we do not save any non-private internal state. As a result, one should compare the PNSGD unlearning to D2D with Theorem O.2 for a fair comparison.P Unlearning Guarantees of Langevin Unlearning [11] In this section, we restate the main results of Langevin unlearning [11] and provide a detailed comparison and discussion for the case of strongly convex objective functions. Theorem P.1 (RU guarantee of PNGD unlearning, strong convexity). Assume for all D ∈ X n , f D is L-smooth, M -Lipschitz, m-strongly convex and ν D satisfies C LSI -LSI. Let the learning process follow the PNGD update and choose σ 2 m < C LSI and η ≤ min( 2 m (1 -σ 2 mCLSI ), 1 L ). Given M is (α, ε 0 )-RDP and y 0 = x ∞ = M(D), for α > 1, the output of the K th PNGD unlearning iteration achieves (α, ε)-RU, whereEQUATION)Theorem P.2 (RDP guarantee of PNGD learning, strong convexity). Assume f (•; d) be L-smooth, M -Lipschitz and m-strongly convex for all d ∈ X . Also, assume that the initialization of PNGD satisfies 2σ 2 m -LSI. Then by choosing 0 < η ≤ 1 L with a constant, the PNGD learning process is (α, ε (S) 0 )-RDP of group size S ≥ 1 at T th iteration withEQUATIONFurthermore, the law of the PNGD learning process is 2σ 2 m -LSI for any time step.Combining these two results, the (α, ε)-RU guarantee for Langevin unlearning isEQUATION)On the other hand, combining our Theorem 3.2, 3.3 and using the worst case bound on Z B along with some simplification, we haveEQUATION)To make an easier comparison, we further simplify the above bound with b = n and 1 -x < exp(-x) which holds for all x > 0:EQUATIONNow we compare the bound (98) obtained by Langevin dynamic in [11] and our bound (100) based on PABI analysis. First notice that the "initial distance" in (100) has an additional factor 1/(2mη). When we choose the largest possible step size η = 1 L , then this factor is L 2m which is most likely greater than 1 in a real-world scenario unless the objective function is very close to a quadratic function. As a result, when K is sufficiently small (i.e., K = 1), possible that the bound (98) results in a better privacy guarantee when unlearning one data point. This is observed in our experiment, Figure 3a . Nevertheless, note that the decaying rate of (100) is independent of the Rényi divergence order α, which actually leads to a much better rate in practice. More specifically, for the case n = 10 4 (which is roughly our experiment setting). To achieve (1, 1/n)-unlearning guarantee the corresponding α is roughly at scale α ≈ 10, since log(n)/(α -1) needs to be less than 1 in the (α, ε)-RU to (ϵ, δ)-unlearning conversion (Proposition N.2). As a result, the decaying rate of (100) obtained by PABI analysis is superior by a factor of 2α, which implies a roughly 20x saving in complexity for K large enough.Comparing sequential unlearning. Notably, another important benefit of our bound obtained by PABI analysis is that it is significantly better in the scenario of sequential unlearning. Since we only need standard triangle inequality for the upper bound Z(s+1) B = min(c Ksn/b Z (s) B + Z B , 2R) of the (s + 1) th unlearning request, only the "initial distance" is affected and it grows at most linearly in s (i.e., for the convex only case). In contrast, since Langevin dynamic analysis in [11] requires the use of weak triangle inequality of Rényi divergence, the α in their bound will roughly grow at scale 2 s which not only affects the initial distance but also the decaying rate. As pointed out in our experiment and by the author [11] themselves, their result does not support many sequential unlearning requests. This is yet another important benefit of our analysis based on PABI for unlearning.• The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions). • The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.) • The assumptions made should be given (e.g., Normally distributed errors). • It should be clear whether the error bar is the standard deviation or the standard error of the mean. • If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 10. Broader Impacts Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed? Answer: [Yes] Justification: We briefly discuss why our work does not have any negative societal impact in Section C Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations. • The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).38th Conference on Neural Information Processing Systems (NeurIPS 2024).We refer privacy loss as two-sided Rényi divergence of two distributions, which we defined as Rényi difference in Definition2.1.When n is not divided by b, we can simply drop the last n -⌊n/b⌋b points.https://github.com/Graph-COM/SGD_unlearning 


Decision: The paper considers the problem of machine unlearning and proposes to use a projected noisy stochastic gradient descent algorithm (PNSGD). This algorithm is shown to achieve unlearning for convex and strongly convex functions. While the results are mainly theoretical in nature, the authors complement their theoretical results with a small set of proof of concept experiments. The topic is interesting and relevant, however reviewers raise a few concerns. These concerns include the strong convexity assumption and authors rebut that many prior theoretical papers do make this assumption. Another big concern is the lack of utility bound. The authors argue that the utility bounds can largely be derived from the work of Chourasia et al. (2021), a point I concur with.

I strongly encourage authors to address reviewer comments in the final version of the paper. In particular, kindly add the utility bound and compare it with some of the prior works with the same set of assumptions e.g., Sekhari et al., 2021.

Reviews: review: paper_summary: paper_summary: The paper presents a simple scheme for machine unlearning. The algorithm has two parts: in the learning part, the models learns using the original dataset D, and in the second part it unlearns using a neighboring dataset D’. The algorithm uses 1) same batches at every epoch, and same batches for both learning and unlearning, 2) Gaussian noise for both learning and unlearning. Based on Renyi differential privacy and the relation between Renyi unlearning and (ε, δ)-unlearning, the paper shows that the privacy parameter ε drops exponentially with every epoch.
strength_weakness: strength_weakness: My main concern is the lack of utility bounds. It’s not hard to design an algorithm which guarantees privacy: just don’t use the dataset at all. What is the utility your algorithm achieves after K iterations of unlearning?
questions: questions: The assumptions in Theorem 3.2 are rather strong. You assume bounded domain + smoothness + Lipschitzness + strong convexity. Please justify these assumptions.

The notation is sometimes confusing. For example, there is notation \nu_{T | B} and there is notation \nu_{D | B}. Line 177: \nu_{D | B}^{0, ‘} is undefined. In Lemma F.2, notation # is undefined.

Minor issues:
-- Is line 173 the definition of \nu_{D | B}? Please make it clear. The wording sounds like this is already defined, and I spent quite some time trying to find the definition.

-- Algorithm 1: please list algorithm’s parameters, such as η and σ 

-- Line 146: PABI was not defined

-- Theorem 3.2: Z_B: you don’t actually use B

-- Appendix D: Lipschitzness (no s after z)

-- Line 548: “Proof” -> ”Proof of Theorem 3.2”

-- I think the presentation could be simplified by focusing on some specific value of α

-- C_R: Line 97 doesn’t match Line 169

-- Theorem 3.2: relationship between D’ and D is not mentioned.
limitations: limitations: None
paper_summary: paper_summary: The paper proposes an effective and efficient machine unlearning algorithm based on projected noisy gradient descent (PSGD). The proposed methods can be extended to handle multiple unlearning requests.   The theoretical unlearning guarantee is established when the loss is assumed to be convex and smooth. Experiments verify the effectiveness of the proposed method.
strength_weakness: strength_weakness: 1. The smoothness of the loss is required, which might limit the algorithm's applicability.

2. In experiments, a logistic loss with $\ell_2$ regularization is considered. It would be better to provides some results on convex loss since the corresponding theory is given.
questions: questions: 1. In algorithm, mini-batch sequence B is fixed. Is it reasonable in practice or analysis? 

2. The paper states that "A smaller batch size b leads to a better privacy loss decaying rate". This seems counterintuitive. Could authors give some explanation?
limitations: limitations: NA
paper_summary: paper_summary: The paper studies a practically important problem of machine unlearning and provides rigorous statistical guarantees for unlearning using the tools from the differential privacy. More specifically, it is shown that, for strongly convex losses, running Projected SGD on the new (adjacent) dataset guarantees that the removed data point will be forgotten, that is the output of "unlearning" algorithm will be close to the output of the Projected SGD if data point on a new dataset.
strength_weakness: strength_weakness: (Major)

My main concern is very conceptual. Isn't it trivial that running SGD (unlearning part) on a strongly convex loss with updated dataset will eventually converge to the same unique optimum of the new loss as if we have started training from scratch. I want to highlight that in the strongly convex case, the optimum is unique. Moreover, the initial distance to the optimum is forgotten exponentially fast for constant step-size SGD. Therefore, I cannot understand why the derived result in this paper is not trivial. In my view, as expected, the authors face a difficulty in the convex case (getting only vacuous result Corollary 3.9). 

(Minor)

1. Why the same batches are used in the unlearning process, shouldn't batches be from the updated dataset? This is perhaphs just a notational issue. 
2. It is unclear to me what is the output of Algorithm 1.
3. It is unclear what it means to satisfy $(\alpha, \varepsilon)$-RU **with $c = 1-\eta m$** in Theorem 3.2. There is no parameter $c$ in definition 2.3. 
4. The quantity $h_{\#}\mu$ in Lemma F.2. is not defined. This lemma is used in Proposition F.3., which is one of the key tools in analysis. 
5. $\mathcal Z_{\mathcal B}$ appearing first in Theorem 3.2 is not defined in the main part. I had to go to Appendix to understand what it is. 
6. Figure 3 (c) is not informative. All lines and confidence intervals overlap. 
7. Why the method is called "contractive noisy iteration"? A more conventional name like Projected SGD would be more appropriate. 
8. It would be helpful to explain the role of the projection in the algorithm. Is it possible to employ it without projection? 
9. In the abstract, "convexity assumption" should be changed to "strong convexity assumption" because the guarantees in the convex case are vacuous in this paper.
questions: questions: n/a
limitations: limitations: The results are limited to strongly convex objectives. To make the problem not trivial, it is crucial to consider convex or PL losses.