1 Introduction↩︎

With recent demands for increased data privacy, owners of these machine learning models are responsible for fulfilling data removal requests from users. Certain laws are already in place guaranteeing the users’ “Right to be Forgotten”, including the European Union’s General Data Protection Regulation (GDPR), the California Consumer Privacy Act (CCPA), and the Canadian Consumer Privacy Protection Act (CPPA) [1]. Merely removing user data from the training data set is insufficient, as machine learning models are known to memorize training data information [2]. It is critical to also remove the information of user data subject to removal requests from the machine learning models. This consideration gave rise to an important research direction, referred to as machine unlearning [3].

Naively, one may retrain the model from scratch after every data removal request to ensure a “perfect” privacy guarantee. However, it is prohibitively expensive in practice when accommodating frequent removal requests. To avoid complete retraining, various machine unlearning methods have been proposed, including exact [4]–[6] as well as approximate approaches [1], [7]–[10]. Exact approaches ensure that the unlearned model would be identical to the retraining one in distribution. Approximate approaches, on the other hand, allow for slight misalignment between the unlearned model and the retraining one in distribution under a similar definition to Differential Privacy (DP) [11].

1.1 Our Contributions↩︎

Learning with noisy gradient methods, such as DP-SGD [13], is widely adopted for privatizing machine learning models with DP guarantee. Intuitively, a learning process with a stronger DP guarantee implies an “easier” unlearning problem as depicted in Figure 1. However, it is unclear if fine-tuning with it on the updated dataset subject to the unlearning request provides an approximate unlearning guarantee, how the DP learning guarantee affects unlearning, and computational benefit compared to retraining. In this work, we provide an affirmative answer for the empirical risk minimization problems with smooth objectives. We propose Langevin unlearning, an approximate unlearning framework based on projected noisy gradient descent (PNGD). Our core idea can be interpreted via a novel unified geometric view of the learning and unlearning processes in Figure 1, which naturally bridges DP and unlearning. Given sufficient learning iterations via the learning process \(\mathcal{M}\), we first show that PNGD converges to a unique stationary distribution \(\nu_{\mathcal{D}}\) for any dataset \(\mathcal{D}\) (Theorem 1). Comparing \(\nu_{\mathcal{D}}\) with the stationary distribution \(\nu_{\mathcal{D}^\prime}\) for any of its adjacent dataset \(\mathcal{D}^\prime\), the learning process shows Rényi DP with privacy loss¹ \(\varepsilon_0\). Given a particular unlearning request \(\mathcal{D} \rightarrow \mathcal{D}^\prime\), the unlearning process \(\mathcal{U}\) can be interpreted as moving from \(\nu_{\mathcal{D}}\) to \(\nu_{\mathcal{D}^\prime}\) from \(\varepsilon_0\)-close to \(\varepsilon\)-close. In practice, due to the unlearning process, the unlearning privacy loss \(\varepsilon\) can be set much smaller than \(\varepsilon_0\), while on the other hand, a stronger initial RDP guarantee, i.e., smaller \(\varepsilon_0\), allows for less unlearning iterations to achieve the desired \(\varepsilon\). Besides the above DP-unlearning bridge, this framework also brings many benefits including (1) a capability of dealing with non-convex problems in theory, which to the best of our knowledge, no previous approximate unlearning framework can tackle, (2) better privacy-utility trade-off in practice compared to state-of-the-art approximate unlearning approach [8] in strongly convex settings, (3) a provably computational benefit compared with model retraining, and (4) a friendly extension to sequential and batch settings with multiple unlearning requests.

We prove the intuition in Fig. 1 formally in Theorem 2. We show that \(K\) unlearning iterations lead to an exponentially fast privacy loss decay \(\varepsilon \leq \exp(-\frac{1}{\alpha}\sum_{k=0}^{K-1} R_k)\varepsilon_0\), where \(\alpha\) is the order of Rényi divergence and \(R_k\) is the strict privacy improving rate depends on the problem settings with an iteration independent strictly positive lower bound \(\bar{R}>0\). Our result is based on convergence analysis of Langevin dynamics [15]. The sampling essence of PNGD allows for a provable unlearning guarantee for non-convex problems [16], [17]. Our characterization of \(\varepsilon_0\) allows an extension of the recent results that PNGD learning satisfies Rényi DP for convex problems [12], [18], [19] to non-convex problems as summarized in Theorem 3. Our key technique is to carefully track the constant of log-Sobolev inequality [20] (LSI) along the learning and unlearning processes and leverage the boundedness property of the projection step via results of [21].

Regarding the computational benefit compared to model retraining, we show iteration complexity saving by comparing two Rényi differences, the one between initialization \(\nu_0\) and \(\nu_{\mathcal{D}^\prime}\), which is at least \(\Omega(1)\) in the worst case versus the other one between the learning convergent distribution \(\nu_{\mathcal{D}}\) and \(\nu_{\mathcal{D}^\prime}\), i.e., \(\varepsilon_0\) which is shown to be \(O(1/n^2)\) for a dataset of size \(n\). Such a gap demonstrates that Langevin unlearning is more efficient than retraining, especially for the dataset with large \(n\).

For sequential unlearning with multiple unlearning requests, we composite the privacy loss bound for single-step requests via the weak triangle inequality of Rényi divergence [22], which yields a sequential unlearning procedure that achieves privacy loss \(\varepsilon\) for each request (Corollary 1). For batch unlearning, \(\varepsilon_0\) is changed to incorporate the batch size (Theorem 3).

Beyond theoretical contributions, we also conduct empirical evaluation. Despite the provable order-wise improvement in \(n\) compared to re-training, our current theory has a limitation by relying on some constants that are undetermined or can be only loosely determined in the non-convex setting. Therefore, we focus on logistic regression tasks for empirical evaluation. Compared with the state-of-the-art gradient-based certified approximate unlearning solution [8] that requires strong convexity, we achieve a superior privacy-utility-complexity trade-off. Although success in the convex case may not directly imply success in non-convex settings, we leave tightening these constants as a future study. For this, we discuss potential alleviation and future direction in Appendix 6 and 5, respectively.

1.2 Related Works↩︎

Unlearning with privacy guarantees. Prior approximate unlearning works require (strong) convexity of the objective function [1], [7], [8]. Their analysis is based on the sensitivity analysis of the optimal parameter. Since the optimal parameter is not even unique in the non-convex setting, it is unclear how their analysis can be generalized beyond convexity. In contrast, we show that the law of our PNGD learning process admits a unique stationary distribution even for non-convex problems.Authors of [1], [7] leverage a second-order update which requires computing Hessian inverse and thus is not scalable for high-dimensional problems. While they only require one unlearning iteration, we show in our experiment that one PNGD unlearning iteration is sufficient for strongly convex loss to achieve satisfied privacy with comparable utility to retraining as well. Neel et al. [8] leverage PGD for learning and unlearning, and achieve the privacy guarantee via publishing the final parameters with additive Gaussian noise. We show in our experiment that our Langevin unlearning strategy provides a better privacy-utility-complexity trade-off compared to this approach. Ullah et al. [5] focus on exact unlearning by leveraging variants of noisy (S)GD. Their analysis is based on total variation stability which is different from our analysis based on Rényi divergence. Also, their analysis does not directly generalize to approximate unlearning. Several works focus on extending the unlearning problems for adaptive unlearning requests [6], [9], [23]. While we focus on the non-adaptive setting, it is possible to show that Langevin unlearning is also capable of adaptive unlearning requests as we do not keep any non-private internal state. We left a rigorous discussion on this as future work. Chourasia et al. [23] also leverage Langevin dynamic analysis in their work. However, their unlearning definition is different from the standard literature as ours².

Differential privacy of noisy gradient methods. A pioneer work [24] studied the DP properties of Langevin Monte Carlo methods. Yet, they do not propose using noisy GD for general machine learning problems. A recent line of work [12], [18], [25] shows that projected noisy (S)GD training exhibits DP guarantees based on the analysis of Langevin dynamics [15], [26] under the strong convexity assumption. In the meanwhile, Altschuler et al. [19] also provided the DP guarantees for projected noisy SGD training but with analysis based on Privacy Amplification by Iteration [27] under the convexity assumption. None of these works study how PNGD can be leveraged for machine unlearning or DP guarantees for non-convex problems.

Sampling literature. Non-asymptotic convergence analysis for Langevin Monte Carlo has a long history [28], [29]. The seminal works [15], [24] proved non-asymptotic convergence analysis in Rényi divergence under strong convexity. Many works improve upon them by either working with weaker isoperimetric inequalities or different notions of convergence [30], [31]. See [26] for a more thorough review along this direction. While these works mainly focus on convergence to the unbiased limit (i.e., the limiting distribution for an infinitesimal step size), we have biased limits (i.e., the limiting distribution for a constant step size, such as our \(\nu_{\mathcal{D}}\)) in machine unlearning problems. Recently Altschuler et al. [32] initiated the question of studying the properties and convergence to the biased limit. Our work provides a new important application, machine unlearning, for these astonishing theoretical results in the sampling literature.

The rest of the paper is organized as follows. In Section 2, we provide preliminaries and problem setup. The theoretical results of Langevin unlearning are in Section 3. We conclude with experiments in Section 4. Due to the space limit, all proofs and future directions are deferred to Appendices.

2 Preliminaries and Problem Setup↩︎

We consider the empirical risk minimization (ERM) problem. Let \(\mathcal{D}=\{\mathbf{d}_i\}_{i=1}^n\) be a training dataset with \(n\) data points \(\mathbf{d}_i\) taken from the universe \(\mathcal{X}\). Let \(f_{\mathcal{D}}(x) = \frac{1}{n}\sum_{i=1}^n f(x;\mathbf{d}_i)\) be the objective function. We aim to minimize with learnable parameter \(x\in \mathcal{C}_R\), where \(\mathcal{C}_R=\{x\in \mathbb{R}^d\;|\;\|x\|\leq R\}\) is a closed ball of radius \(R\). We denote \(\Pi_{\mathcal{C}_R}:\mathbb{R}^d\mapsto \mathcal{C}_R\) to be an orthogonal projection to \(\mathcal{C}_R\). The norm \(\|\cdot\|\) is standard Euclidean \(\ell_2\) norm if not specified. \(\mathcal{P}(\mathcal{C})\) is denoted as the set of all probability measures over a closed convex set \(\mathcal{C}\). Standard definitions such as convexity can be found in Appendix 8. Finally, we use \(x\sim \nu\) to denote that a random variable \(x\) follows the probability distribution \(\nu\). To control the convergence behavior of (P)NGD, it is standard to check an isoperimetric condition known as log-Sobolev inequality [20], described as follows.

2.1 Privacy Definition for Learning and Unlearning↩︎

We say two datasets \(\mathcal{D}=\{\mathbf{d}_i\}_{i=1}^n\) and \(\mathcal{D}^\prime=\{\mathbf{d}_i^\prime\}_{i=1}^n\) are adjacent if they “differ” only in one index \(i_0\in[n]\) so that \(\mathbf{d}_i = \mathbf{d}_i^\prime\) for all \(i\neq i_0\) unless otherwise specified. Furthermore, we say two datasets \(\mathcal{D}\) and \(\mathcal{D}^\prime\) are adjacent with a group size of \(S\geq 1\) if they differ in at most \(S\) indices. We next introduce a useful idea termed Rényi difference.

We are ready to introduce the formal definition of differential privacy and unlearning.

It is known to the literature that an \((\alpha,\varepsilon)\)-RDP guarantee can be converted to the popular \((\epsilon,\delta)\)-DP guarantee [11] relatively tight [22]. As a result, we will focus on establishing results with respect to \(\alpha\) Rényi difference (and equivalently \(\alpha\) Rényi divergence). Next, we introduce our formal privacy definition of unlearning.

Notably, our Definition 4 can be converted to the standard \((\epsilon,\delta)\)-unlearning definition [1], [7], [8], similar to RDP-DP conversion [22]. Since we work with the replacement definition of dataset adjacency, to “erase” a data point \(\mathbf{d}_i\) we can simply replace it with any data point \(\mathbf{d}_i^\prime\in \mathcal{X}\) for the updated dataset \(\mathcal{D}^\prime\) in practice.

3 Langevin Unlearning: Main Results↩︎

We propose to leverage projected noisy gradient descent for our learning and unlearning algorithm \(\mathcal{M}\) and \(\mathcal{U}\). For \(\mathcal{M}\), we propose to optimize the objective \(f_{\mathcal{D}}(x)\) with PNGD: \[\begin{align} \label{eq:GLD95learning} & x_{t+1} = \Pi_{\mathcal{C}_R}\left(x_t - \eta\nabla f_{\mathcal{D}}(x_t) + \sqrt{2\eta \sigma^2} W_t\right), \end{align}\tag{1}\] where \(W_t\stackrel{\text{iid}}{\sim}\mathcal{N}(0,I_d)\) and \(\eta,\sigma^2>0\) are hyperparameters of step size and noise variance respectively. The initialization \(x_0\) can be chosen arbitrarily in \(\mathcal{C}_R\) unless specified. We assume the learning procedure will train the model until convergence \(x_\infty = \mathcal{M}(\mathcal{D})\) for simplicity, where we prove in Theorem 1 that the law of this learning process 1 indeed converges to a unique stationary distribution when \(\nabla f_{\mathcal{D}}\) is continuous. A similar “well-trained” assumption has been also used in prior unlearning literature [1], [7] and we will discuss the case of insufficient training later. After we obtain a learned parameter \(\mathcal{M}(\mathcal{D})\), an unlearning request arrives so that the training dataset changes from \(\mathcal{D}\) to \(\mathcal{D}^\prime\). For the unlearning algorithm \(\mathcal{U}\), we propose to fine-tune the model parameters on the new objective \(f_{\mathcal{D}^\prime}(y)\) with \(K\) iterations of the same PNGD. \[\begin{align} \label{eq:GLD95unlearning} & y_{k+1} = \Pi_{\mathcal{C}_R}\left(y_k - \eta\nabla f_{\mathcal{D}^\prime}(y_k) + \sqrt{2\eta \sigma^2} \bar{W}_k\right), \end{align}\tag{2}\] where \(\bar{W}_k\stackrel{\text{iid}}{\sim}\mathcal{N}(0,I_d)\) and \(y_0 = x_\infty\), which starts from the convergent point of the learning procedure. Throughout our work, we assume \(f(x;\mathbf{d})\) is \(M\)-Lipschitz and \(L\)-smooth in \(x\) for any \(\mathbf{d}\in\mathcal{X}\). Nevertheless, one can apply per-sample gradient clipping in 1 and 2 so that the \(M\)-Lipschitz assumption can be dropped. In this case, our learning and unlearning processes admit the popular DP-SGD [13] without mini-batching. For the rest of the paper, we denote \(\nu_t,\rho_k\) as the laws of the processes \(x_t,y_k\) respectively. Recall that we also denote the limiting distribution of the learning process 1 as \(\nu_{\mathcal{D}}\) for training dataset \(\mathcal{D}\).

3.1 Limiting Distribution and General Idea↩︎

A key component of the Langevin unlearning is the existence, uniqueness, and stationarity of the limiting distribution \(\nu_{\mathcal{D}}\) of the training process. We start with proving that \(\nu_{\mathcal{D}}\) exists, is unique, and is a stationary distribution. Our proof is relegated to Appendix 11, which is based on showing the ergodicity of the process 1 by leveraging results in [33].

If \(\mathcal{M}\) is known to be \((\alpha,\varepsilon_0)\)-RDP for a \(\alpha>1\), by definition we know that for all adjacent dataset \(\mathcal{D},\mathcal{D}^\prime\), \(d_\alpha(\nu_{\mathcal{D}},\nu_{\mathcal{D}^\prime})\leq \varepsilon_0\). In the space of \(\mathcal{P}(\mathcal{C}_R)\), this RDP guarantee gives a “regular polyhedron”, where vertices are \(\nu_{\mathcal{D}},\nu_{\mathcal{D}^\prime}\) and all adjacent vertices are of “lengths” \(\varepsilon_0\) at most in Rényi difference. We caveat that Rényi difference is not a metric but the idea of the regular polyhedron is useful conceptually. As a result, the RDP guarantee of the learning process controls the “distance” between distribution induced from adjacent dataset \(\mathcal{D}\) and \(\mathcal{D}^\prime\). Once we finish the learning process, we receive an unlearning request so that our dataset changes from \(\mathcal{D}\) to an adjacent dataset \(\mathcal{D}^\prime\). We need to move from \(\nu_{\mathcal{D}}\) to \(\nu_{\mathcal{D}^\prime}\) at least \(\varepsilon\) close for a \((\alpha,\varepsilon)\)-RU guarantee. Intuitively, if the initial RDP guarantee is stronger (i.e., \(\varepsilon_0\) is smaller), unlearning becomes “easier” at the cost of larger noise. When \(\varepsilon_0=\varepsilon\), we automatically achieve \((\alpha,\varepsilon)\)-RU without any unlearning update. One of our main contributions is to characterize how many PNGD unlearning iteration is needed to reduce \(d_\alpha(\rho_k,\nu_{\mathcal{D}^\prime})\) from \(\varepsilon_0\) to \(\varepsilon\), where \(\rho_0 = \nu_{\mathcal{D}}\).

For the unlearning process, note that the initial Rényi difference between \(\rho_0,\nu_{\mathcal{D}^\prime}\) is provided by the RDP guarantees of the learning process. As a result, we are left to characterize the convergence of the process \(y_k\) to its stationary distribution \(\nu_{\mathcal{D}^\prime}\) in Rényi difference (Theorem 2). Since the privacy loss \(\varepsilon\) gradually decays with respect to unlearning iterations, we refer to this phenomenon as privacy recuperation. This is in contrast to the learning process, where prior work [12] has shown the worse privacy loss \(\varepsilon_0\) with respect to learning iterations and refers to that phenomenon as privacy erosion.

3.2 Unlearning Guarantees↩︎

Our first Theorem shows that \((\mathcal{M},\mathcal{U})\) achieves \((\alpha,\varepsilon)\)-RU, where \(\varepsilon\) decays monotonically in \(K\) unlearning iterations starting from \(\varepsilon_0\), condition on \(\mathcal{M}\) being \((\alpha,\varepsilon_0)\)-RDP. We provide the proof sketch in Appendix 12.1 and formal proofs are deferred to Appendix 12.2.

Note that \(R_k\) can be interpreted as the strict privacy improving rate at step \(k\) and \(C_k\) is the LSI constant upper bound of distribution of \(y_k\). The above theorem states that fine-tuning with PNGD can decrease the privacy loss \(d_{\alpha}(\rho_K,\nu_{\mathcal{D}^\prime})\) exponentially fast with the unlearning iteration \(K\). This is because \(R_k\) is lower bounded away from \(0\) by a constant, thanks to the iteration independent upper bound on \(C_k\). Stronger assumptions on the objective function \(f_{\mathcal{D}}\) lead to a better rate, which implies fewer unlearning iterations are needed to achieve the same RU guarantee. There are several remarks for our Theorem 2. First, note that the result is dimension-free, which is favorable for problems with many parameters to be learned. Second, note that the \(M\)-Lipschitzness assumption can be dropped by clipping the gradient to norm \(M\) in the PNGD update 1 and 2 instead. As a result, our Theorem 2 applies to neural networks with smooth activation functions in theory. Finally, our result gives an upper bound on the LSI constants along the unlearning process (i.e., \(C_k\)) which may be improved with more advanced analysis. We note that the exponential dependence in \(R\) for the bound of \(C_k\) can be loose. It is possible to have a better constant with either more structural assumptions or working with different isoperimetric inequalities such as (weak) Poicaré inequality [31]. A more detailed discussion is in Appendix 5.

Initial RDP guarantees and LSI constant. Since Theorem 2 relies on \(\mathcal{M}\) being \((\alpha,\varepsilon_0)\)-RDP and the \(\nu_{\mathcal{D}}\) satisfies LSI, the theorem below provides such results for the learning process, where the formal proof is relegated to Appendix 13.

Note that any initialization \(x_0\in \mathcal{C}_R\) can be viewed as sampling from \(\mathcal{N}(x_0,c I_d)\) with \(c\rightarrow 0\), which corresponds to \(C_{0}\)-LSI for any \(C_{0}>0\). By taking \(T\rightarrow \infty\), Theorem 3 provides the initial \((\alpha,\varepsilon_0)\)-RDP guarantee and the LSI constant needed in Theorem 2. Since there is an iteration-independent upper bound for \(C_{t,1}\), one can show that \(\varepsilon_0 \leq \frac{2\alpha\eta S^2 M^2}{\sigma^2 n^2 c}\) for some \(T\)-independent constant \(c\in (0,1)\) due to the finiteness of geometric series. Similar to our discussion for Theorem 2, the bound of \(C_t\) may be loose and it is possible to further improve the LSI constant analysis. The goal of our results is to demonstrate that it is possible to derive (finite) RDP and (arbitrarily small) RU guarantees even for general non-convex problems.

Nevertheless, for the \(m\)-strongly convex case we have \(\varepsilon_0^{(S)} \leq \frac{4\alpha S^2M^2}{m\sigma^2n^2}\) for all \(T>0\), including \(T\rightarrow \infty\). It shows that indeed the current learned distribution \(\nu_\mathcal{D}\) is close to the retraining distribution \(\nu_{\mathcal{D}^\prime}\) for \(n\) sufficiently large. This also leads to the computational benefit of Langevin unlearning compared to retraining from scratch, which we discuss below. On the other hand, we show by experiments in Section 4 that our results provide a superior privacy-utility-complexity trade-off for the strongly convex case compared to existing approximate unlearning approaches.

The computational benefit compared to retraining. While our Theorems 2 and 3 together provide the privacy guarantee of Langevin unlearning, it is critical to check if our approach provides a computational benefit compared to retraining from scratch as well. Let \(\nu_0\) be the (data-independent) initialization distribution of the learning process. Intuitively, starting with \(\nu_{\mathcal{D}}\) instead of \(\nu_0\) (i.e., retraining) should converge faster to \(\nu_{\mathcal{D}^\prime}\), since \(d_\alpha(\nu_{\mathcal{D}},\nu_{\mathcal{D}^\prime})\leq \varepsilon_0\) is likely to be much smaller than \(d_\alpha(\nu_{0},\nu_{\mathcal{D}^\prime})\). Thus, our Langevin unlearning needs less iterations than retraining for most cases, except for a corner case when \(\nu_0\) is already close to \(\nu_{\mathcal{D}}\). From Theorem 2 we know that the number of PNGD iterations we need to approach \(\varepsilon\)-close in \(d_\alpha\) to the target distribution \(\nu_{\mathcal{D}^\prime}\) is roughly \(O(\log(\frac{\varepsilon_I}{\varepsilon}))\), where \(\varepsilon_I\) is the Rényi difference between the initial distribution and the target distribution \(\nu_{\mathcal{D}^\prime}\). From Theorem 3, we know that the initial Rényi difference of Langevin unlearning is at most \(\varepsilon_0 = O(1/n^2)\) for any datasets \(\mathcal{D},\mathcal{D}^\prime\) and any smooth Lipchitz loss. In contrast, even if both the target distribution \(\nu_{\mathcal{D}^\prime}\) and the initialization of retraining \(\nu_0\) are Gaussian distributions with the same variance but mean difference \(\Omega(1)\), their Rényi difference is \(\Omega(1)\) [22]. As a result, computational saving offered by Langevin unlearning is significant for sufficiently large \(n\). A more thorough discussion is in Appendix 10.

3.3 Empirical Aspects of Langevin Unlearning↩︎

Insufficient training. While our theorem assumes the learning process runs until convergence, this assumption can be relaxed by the geometric view of Langevin unlearning. Assume the learning process \(\mathcal{M}(\mathcal{D})\sim \nu_T\) terminate with finite step \(T\) instead and we only have \(d_\alpha(\nu_T,\nu_{\mathcal{D}})\leq \varepsilon_T(\alpha)\) for all possible \(\mathcal{D}\in \mathcal{X}^n\). One can still apply the weak triangle inequality of Rényi divergence [22] twice to bound \(d_\alpha(\rho_k,\nu_{T}^\prime)\) with \(d_{4\alpha}(\rho_k,\nu_{\mathcal{D}^\prime})\), \(\varepsilon_T(2\alpha)\), and \(\varepsilon_T(4\alpha)\) with additional factors \((\alpha-0.5)/(\alpha-1)\) and \((2\alpha-0.5)/(2\alpha-1)\). In practice, it is reasonable to require the model parameters to be sufficiently trained so that \(\varepsilon_T\) is negligible and a tighter weak triangle inequality can be employed.

Sequential and batch unlearning. Langevin unlearning naturally supports sequential and batch unlearning for unlearning multiple data points thanks to our geometric view of the unlearning problem, see Figure 2 for a pictorial example. For sequential unlearning, we show that fine-tuning the current model parameters on the updated datasets for sequential \(S\geq 1\) unlearning requests can achieve \((\alpha,\varepsilon)\)-RU simultaneously. The formal proof is deferred to Appendix 14.

As a result, one can leverage Corollary 1 to recursively determine needed unlearning iterations for each sequential unlearning request. For the batch unlearning setting, it only affects the initial Rényi difference in Theorem 2. We can simply adopt Theorem 3 with a group size of \(S \geq 1\) for the RDP guarantees of the learning process \(\varepsilon_0^{(S)}\).

Utility-privacy-efficiency trade-off. An interesting aspect of the Langevin unlearning is its strong connection to the initial RDP guarantee. From Theorem 3, we know that increasing \(\sigma\) leads to smaller Rényi difference \(\varepsilon_0\) and thus better unlearning efficiency. However, this intuitively is at the cost of the utility of \(\nu_{\mathcal{D}}\), see for example the discussion in Section 5 of [12] under the strong convexity assumption. To achieve the same \((\alpha,\varepsilon)\)-RU guarantee, one can either ensure smaller \(\varepsilon_0\) at the cost of worst utility or run more unlearning iterations at the cost of unlearning efficiency. We investigate how utility trade-off with privacy and unlearning complexity empirically in Section 4.

4 Experiments↩︎

Benchmark datasets. We consider logistic regression with \(\ell_2\) regularization. We focus on this strongly convex setting since the non-convex unlearning bound in Theorem 2 currently is not tight enough to be applied in practice due to its exponential dependence on various hyperparameters. However, we emphasize its significant theoretical implication due to the lack of a certified non-convex approximate unlearning framework in previous studies. Meanwhile, the existing baseline approach [8] also only applies to strongly convex problems. We conduct experiments on MNIST [34] and CIFAR10 [35], which contain 11,982 and 50,000 training instances respectively. We follow the setting of [7] to distinguish digits \(3\) and \(8\) for MNIST so that the problem is a binary classification. For the CIFAR10 dataset, we use all classes and leverage the last layer of the public ResNet18 [36] embedding as the data features, which follows the public feature extractor setting of [7]. Experiments on additional datasets [37] are deferred to Appendix 18 and our code is publicly available³.

Baseline methods. Our baseline methods include Delete-to-Descent (D2D) [8], the state-of-the-art gradient-based approximate unlearning method, and retraining from scratch using PNGD. For D2D, we leverage Theorem 9 and 28 in [8] 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 [8] and our Langevin unlearning by default does not require it. We include those theorems for D2D and a detailed explanation of its possible non-privacy internal state in Appendix 19 for completeness. All experimental details can be found in Appendix 18, including how to convert \((\alpha,\varepsilon)\)-RU to the standard \((\epsilon,\delta)\)-unlearning guarantee. Throughout this section, we choose \(\delta = 1/n\) for each dataset and require all tested unlearning approaches to achieve \((\epsilon,\delta)\)-unlearning with different \(\epsilon\). We report test accuracy for all experiments as the utility metric. For the initialization, we sample from Gaussian distribution with mean \(1000\). This simulates the case that the initial distribution is in a reasonable distance away from the convergent distribution \(\nu_\mathcal{D}\). We set the learning iteration \(T=10,000\) to ensure all approaches converge. For Langevin unlearning, we leverage Theorems 2, 3 and Corollay 1 for privacy accounting under different settings. All results are averaged over \(100\) independent trials with standard deviation reported as shades in all figures.

Unlearning one data point with \(K=1\) iteration. We first consider the setting of unlearning one data point using only \(K=1\) unlearning iteration for both Langevin unlearning and D2D (Figure 3 (a)). Since D2D cannot achieve a privacy guarantee with only \(1\) unlearning iteration without a non-private internal state, we allow D2D to have it in this experiment. Even in this case, our Langevin unlearning significantly outperforms D2D in utility for \(\epsilon\) from \(0.1\) to \(5\) under the same unlearning complexity (\(K=1\)), but also achieves similar accuracy to retraining from scratch. Since retraining requires \(T=10,000\) PNGD iterations, Langevin unlearning is indeed much more efficient. We also show that D2D can achieve better utility at the cost of a larger unlearning iteration \(K=2,5\). Our Langevin unlearning exhibits both smaller unlearning complexity and better utility compared to D2D.

Unlearning multiple data points. We now consider the scenario of unlearning \(100\) data points, where the results are in Figure 3 (b). We let all methods achieve the same \((1,1/n)\)-unlearning guarantee for a fair comparison. Since D2D only supports sequential unlearning, we directly apply its sequential unlearning results [8]. Also, we do not allow D2D to have an internal non-private state in this experiment for a fair comparison. On the other hand, since Langevin unlearning supports both sequential and batch unlearning, we vary the number of points per unlearning request \(S=5,10,20\) and report the accumulated unlearning iterations for \(\sigma=0.03\). All methods achieve a similar utility, with an accuracy of roughly \(0.9\) and \(0.98\) for MNIST and CIFAR10 respectively. Langevine unlearning can achieve a significantly better unlearning complexity compared to D2D if one allows for a larger unlearning batch size. For instance, when we are allowed to unlearn \(S=20\) points at once, Langevine unlearning saves \(40\%\) unlearning iteration compared to D2D. Nevertheless, we note that due to the use of weak triangle inequality of Rényi divergence in our analysis, Langevin unlearning can be more expensive in complexity compared to D2D when one only allows for unlearning a small batch of points (i.e, \(S=5\)). We leave the improvement in this direction as the future work.

Privacy-utility-complexity trade-off. We further examine the inherent privacy-utility-complexity trade-off provided by our Langevin unlearning with two experiments. In the first experiment, we aim to achieve \((\epsilon,1/n)\)-unlearning guarantee with \(\epsilon=1\) for batch unlearning of \(100\) points. We vary the choice of \(\sigma\) from \(0.01\) to \(1.0\). A smaller \(\sigma\) leads to a worse initial \(\epsilon_0\) and thus requires more unlearning iteration \(K\) to recuperate it to \(\epsilon=1\). It is interesting to see that even if we choose a small \(\sigma\) so that the initial \((\epsilon_0,1/n)\)-DP guarantee is extremely weak (i.e, \(\epsilon_0\approx 100\) for \(\sigma=0.05\)), our unlearning iteration can recuperate \(\epsilon_0\) to \(\epsilon=1.0\) efficiently. On the other hand, a larger \(\sigma\) leads to a worse utility which is the inherent privacy-utility-complexity trade-off of Langevin unlearning. The results are illustrated in Figure 3 (c). Compared to retraining until convergence (\(T=10,000\)), we achieve a similar utility but with much lower unlearning complexity with \(K\) roughly up to \(2500\).

In the second experiment, we investigate the effect of the number of points to be unlearned \(S\) in the batch unlearning setting. In Figure 4, we can see that both larger \(S\) and smaller \(\epsilon\) will require more unlearning iterations \(K\). It is worth noting that the resulting utility does not change significantly, whereas Langevin unlearning always archives a similar utility compared to retraining (see Figure 13 (a) in Appendix 18). Retraining requires \(T=10,000\) PNGD iterations which is significantly larger than the required unlearning iteration \(K\) even for \(\epsilon=0.5\). We have shown that Langevin unlearning is a promising unlearning solution.

5 Conclusions and Future Directions↩︎

We propose Langevin unlearning based on noisy gradient descent with privacy guarantees for approximate unlearning problems. It unifies the DP learning process and the privacy-certified unlearning process with many algorithmic benefits such as applicability to non-convex problems and multiple unlearning requests. Below we discuss several future directions for Langevin unlearning.

Extension to projected noisy stochastic gradient descent. It is straightforward to extend our analysis to the projected noisy SGD case. There are two possibilities for the SGD setting: 1) randomly partition the indices \([n]\) into a sequence of mini-batches, then fix this sequence for all the learning and unlearning process [18]; 2) randomly draw a mini-batch for each update [19], [25]. The analysis of [18] can be combined with our LSI constant analysis for RU guarantees, similar to the proof of our Theorem 2. Unfortunately, the analysis [25] may lead to an extra large LSI constant in the intermediate step even if \(R\) is small. We refer interested readers to Appendix C of [18] for a detailed discussion. The technical difficulty here is to provide a tight analysis of the LSI constant for a mixture of distributions, where each of them corresponds to a possible choice of mini-batch. The analysis of [19] is based on privacy amplification by iteration, which does not directly generalize to the non-convex cases. In our companion work [38], we exploit it not only to establish a better unlearning result but also to enable the mini-batch setting under the convexity assumption. It is currently an open problem whether a matching result can be established via Langevin dynamic analysis as well.

Better convergence rate. While it is already exciting that Langevin dynamic analysis leads to formal unlearning algorithms and guarantees even for general non-convex problems in theory, the potential of this direction for a practical plug-and-play unlearning solution is even more interesting. Several promising future directions can significantly improve the convergence rate and the unlearning efficiency. Developing a better LSI constant bound under additional structural assumptions for the non-convex problems is the most straightforward one. Another direction is to work with (weak) Poincaré inequality instead. While a weaker tail assumption leads to slower convergence [31], the corresponding (weak) Poincaré constant may be more tightly tracked. Finally, while we only discuss the noisy GD which corresponds to Langevin Monte Carlo, some other advanced samplers are off-the-shelf including the Metropolis-Hastings filter [39] and Hamiltonian Monte Carlo [40]. We hope our work motivates further collaborations among the sampling and privacy communities and pushes the boundaries of learning and unlearning with privacy guarantees.

6 Limitations↩︎

While our Langevin unlearning provides the first approximate unlearning solution for non-convex problems, it is still not practical enough as we have stated in the main text. One limitation of our unlearning guarantees (Theorem 2) is that the privacy bound for non-convex problems is not tight and can potentially improved via advanced analysis, where some possible directions are discussed in the future directions below. Currently, it is still only applicable in practice for strongly convex problems as we have demonstrated in our experiment section if a privacy guarantee is required. Nevertheless, recent studies have shown that a \((\epsilon,\delta)\)-DP model provides strong empirical privacy against popular attacks such as membership inference attacks even if \(\epsilon\approx 10^8\) [41]. We conjecture a similar phenomenon exists for Langevin unlearning, which allows Langevin unlearning to defend against membership inference attacks for non-convex models as well in practice with a similar \(\epsilon\) scale. We leave this empirical study as our important future work.

7 Broader Impact↩︎

Our work study the theoretical unlearning guarantees of projected 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.

8 Standard Definitions↩︎

Let \(f:\mathbb{R}^d\mapsto \mathbb{R}\) be a mapping. We define smoothness, Lipschitzsness, and strong convexity as follows: \[\begin{align} & \text{L-smooth: }\forall~ x,y\in\mathbb{R}^d,\;\|\nabla f(x)-\nabla f(y)\| \leq L \|x-y\| \\ & \text{m-strongly convex: }\forall~ x,y\in\mathbb{R}^d,\;\left\langle x-y, \nabla f(x)-\nabla f(y) \right \rangle \geq m \|x-y\|^2\\ & \text{M-Lipschitzs: }\forall~ x,y\in\mathbb{R}^d,\;\|f(x)-f(y)\| \leq M \|x-y\|. \end{align}\] Furthermore, we say \(f\) is convex means it is \(0\)-strongly convex.

9 Additional Related Works↩︎

Bayesian Unlearning. Due to the relation between Langevin Monte Carlo and Bayes learning approaches, our Langevin unlearning is also loosely related to the Bayesian unlearning literature. See [42]–[44] for a series of empirical results. Along this line of work, [45] is the only one that provides a certain unlearning guarantee in terms of KL divergence. However, they only provide a bound for one direction of KL (similar to \(D_1(\rho_k||\nu_{\mathcal{D}}^\prime)\)) which makes it fail to be directly connected to the differential privacy. Note that it is crucial to ensure the bidirectional bound for KL or Rényi divergence for the purpose of privacy. Otherwise, we cannot ensure the sufficiently large type I and type II errors of the best possible attacker in membership inference attack [14]. Also, it is essential to have a (relatively) tight conversion to DP, where the general \(\alpha\) order in Rényi divergence is crucial.

10 Detailed Discussion on Computational Benefit Against Retraining↩︎

In this section, we provide a more detailed discussion of the computational benefit of Langevin unlearning against retraining from scratch. We start our discussion under strongly convex assumption and then explain the non-convex case. Let us consider the case \(f(x;\mathbf{d})\) is \(m\)-strongly convex, \(L\)-smooth and \(M\)-Lipschitz in \(x\) for all \(\mathbf{d}\in \mathcal{X}\). Also, assume the initialization distribution \(\nu_0=\mathcal{N}(\tilde{x}_0,\frac{2\sigma^2}{m} I_d)\) for some \(\tilde{x}_0\in \mathcal{C}_R\). In this case, from Theorem 2 we know that running \(T\) PNGD learning iteration 1 , we have \[\begin{align} d_{\alpha}(\nu_T,\nu_{\mathcal{D}^\prime})\leq \exp(-\frac{2\sigma^2 \eta T}{\alpha C_{\text{LSI}}}) d_{\alpha}(\nu_0,\nu_{\mathcal{D}^\prime}). \end{align}\] Note that by Theorem 3, we know that \(C_{\text{LSI}}=\frac{2\sigma^2}{m}\) by our choice of \(\nu_0\) for an appropriate step size \(\eta\leq \min(\frac{1}{m},\frac{1}{L})\). As a result, in order to be \(\varepsilon\) close to \(\nu_{\mathcal{D}^\prime}\), we need \(\frac{\alpha}{m\eta}\log(\frac{d_{\alpha}(\nu_0,\nu_{\mathcal{D}^\prime})}{\varepsilon})\) retraining iteration. On the other hand, for Langevin unlearning we need \(\frac{\alpha}{m\eta}\log(\frac{\varepsilon_0}{\varepsilon})\), where \(\varepsilon_0\leq \frac{4\alpha M^2}{m\sigma^2 n^2}\). As a result, Langevin unlearning the computational saving for Langevin unlearning against retraining is \[\begin{align} & \frac{\alpha}{m\eta}\log(\frac{d_{\alpha}(\nu_0,\nu_{\mathcal{D}^\prime})}{\varepsilon})-\frac{\alpha}{m\eta}\log(\frac{\varepsilon_0}{\varepsilon}) = \frac{\alpha}{m\eta}\log(\frac{d_{\alpha}(\nu_0,\nu_{\mathcal{D}^\prime})}{\varepsilon_0}) \geq \frac{\alpha}{m\eta}\log(\frac{m\sigma^2 n^2\times d_{\alpha}(\nu_0,\nu_{\mathcal{D}^\prime})}{4\alpha M^2}). \end{align}\] Clearly, this saving depends on \(\nu_{\mathcal{D}^\prime}\). In some rare cases, \(\nu_0\) might accidentally be close to \(\nu_{\mathcal{D}^\prime}\) so that retraining is more efficient. However, even if \(\nu_{\mathcal{D}^\prime} = \mathcal{N}(x^\star(\mathcal{D}^\prime),\frac{2\sigma^2}{m}I_d)\), we have \(d_\alpha(\nu_0,\nu_{\mathcal{D}^\prime}) = \frac{\alpha m \|\tilde{x}_0-x^\star(\mathcal{D}^\prime)\|}{4\sigma^2}\). That is, even if we know the target distribution is Gaussian and choose the initialization to have the same variance, the corresponding Rényi difference is \(\Omega(1)\) for \(\|\tilde{x}_0-x^\star(\mathcal{D}^\prime)\|=\Omega(1)\). As a result, if we uniformly at random sample \(\tilde{x}_0\) from \(\mathcal{C}_R\), we have \(\|\tilde{x}_0-x^\star(\mathcal{D}^\prime)\| \geq 1\) with probability at least \(1-\frac{1}{R^d}\). Plug this into the lower bound above we obtain a data-independent lower bound on the computational savings with probability at least \(1-\frac{1}{R^d}\) as follows \[\begin{align} & \frac{\alpha}{m\eta}\log(\frac{d_{\alpha}(\nu_0,\nu_{\mathcal{D}^\prime})}{\varepsilon})-\frac{\alpha}{m\eta}\log(\frac{\varepsilon_0}{\varepsilon})\geq \frac{\alpha}{m\eta}\log(\frac{m\sigma^2 n^2\times d_{\alpha}(\nu_0,\nu_{\mathcal{D}^\prime})}{4\alpha M^2}) \\ & = \frac{\alpha}{m\eta}\log(\frac{m^2 n^2 \|\tilde{x}_0-x^\star(\mathcal{D}^\prime)\|}{16 M^2}) \geq \frac{\alpha}{m\eta}\log(\frac{m^2 n^2}{16 M^2}). \end{align}\] Here we can see that for larger problem size \(n\), our computational benefit is more significant.

For the non-convex case, note that the convergence rate \(R_k\) in Theorem 2 will vary and depend on the LSI constant of \(\nu_0\) and \(\nu_{\mathcal{D}}\) in general. This makes it hard to have a direct characterization of the computational benefit against retraining. To simplify the situation, we assume the convergence rate \(R_k\) is a constant \(\bar{R}>0\) that is independent of \(n,k\). In this case, the computational saving can be characterized as \[\begin{align} \frac{\alpha}{\bar{R}}\log(\frac{d_{\alpha}(\nu_0,\nu_{\mathcal{D}^\prime})}{\varepsilon_0}). \end{align}\]

In this case, one can still leverage Theorem 3 to provide an upper bound on \(\varepsilon_0\), yet the obtained bound can be weak due to the inaccurate estimate of LSI constants for the non-convex case. Instead, we propose to use unbiased limits \(\tilde{\nu}_{\mathcal{D}}\) to approximate the biased limit \(\nu_{\mathcal{D}}\) for a rough estimate instead, since \(D_\alpha(\nu_{\mathcal{D}}||\tilde{\nu}_{\mathcal{D}})\rightarrow 0\) as \(\eta\rightarrow 0\) [26]. From standard sampling literature [15], we know that \(\tilde{\nu}_{\mathcal{D}}\propto \exp(-\frac{f_{\mathcal{D}}}{\sigma^2})\). We provide the following result for bounding \(d_\alpha(\tilde{\nu}_{\mathcal{D}},\tilde{\nu}_{\mathcal{D}^\prime})\).

As a result, we know that \(\varepsilon_0\) is roughly at most \(\frac{2F}{\sigma^2 n}\) when the step size \(\eta\) is sufficiently small. Thus when \(d_{\alpha}(\nu_0,\nu_{\mathcal{D}^\prime})=\Omega(1)\), we Langevin unlearning save \(\Omega(\log(n))\) PNGD iterations.

11 Proof of Theorem 1: Convergence of PNGD↩︎

In this section, we prove that the learning process 1 with general closed convex set \(\mathcal{C}\) that is restated as follows for the reader’s convenience, \[\begin{align} \label{eq:GLD95learning95appendix} & x_{t+1} = \Pi_{\mathcal{C}}\left(x_t - \eta\nabla f_{\mathcal{D}}(x_t) + \sqrt{2\eta \sigma^2} W_t\right), \end{align}\tag{3}\] will converge to an invariant probability measure. One observation is that 3 is a Markov chain and some ergodicity results can be applied.

12 Proof of Theorem 2↩︎

12.1 Proof Sketch of Theorem 2↩︎

Given \(\mathcal{M}\) is \((\alpha,\varepsilon_0)\)-RDP, we aim to show the upper bound of \(d_\alpha(\rho_k,\nu_{\mathcal{D}^\prime})\) decays in \(k\) starting from \(\varepsilon_0\) at \(k=0\). As a warm-up, we start with the strongly convex case. The analysis is inspired by [15] and [24] and formal proof can be found in Appendix 12.2. Roughly speaking, we characterize how both \(\alpha\) Rényi divergence \(D_\alpha(\rho_k||\nu_{\mathcal{D}^\prime})\) and \(D_\alpha(\nu_{\mathcal{D}^\prime}||\rho_k)\) decay, given \(\nu_{\mathcal{D}^\prime}\) and \(\rho_k\) satisfy LSI condition for some constants. Standard sampling literature only focuses on the part \(D_\alpha(\rho_k||\nu_{\mathcal{D}^\prime})\) (i.e., Lemma 8 in [15]), where \(\nu_{\mathcal{D}^\prime}\) satisfies LSI implies exponential decay in Rényi divergence. The other direction is necessary for meaningful privacy guarantee but more challenging as one to carefully track the LSI constant of \(\rho_k\) for all \(k\geq 0\). We prove the following lemma for such LSI constant characterization along the unlearning process, which specializes results of [26] to the PNGD update.

By leveraging Lemma 1, we can characterize the LSI constant for all \(\rho_k\). One key step is to characterize the Lipschitz constant of the gradient update \(h(x) = x - \eta \nabla f(x)\). From Lemma 2.2 in [32] we know if \(f\) is \(m\)-strongly convex, \(L\)-smooth and \(\eta \leq \frac{1}{L}\), then \(h\) is \((1-\eta m)\)-Lipschitz. Let \(\rho_k\) satisfy \(C_k\)-LSI, Lemma 1 leads to the recursion expression \(C_{k+1} \leq (1-\eta m)^2C_k + 2\eta\sigma^2,\;C_0=C_{\text{LSI}}.\) By choosing \(\eta\) satisfying \(0<\eta\leq \min(\frac{2}{m}(1-\frac{\sigma^2}{m C_{\text{LSI}}}),\frac{1}{L})\) and the assumption \(\frac{\sigma^2}{m} < C_{\text{LSI}}\), \(C_k\) is non-increasing and thus \(\rho_k\) is \(C_{\text{LSI}}\)-LSI for all \(k\geq 0\). As a result, the decay of both \(D_\alpha(\rho_k||\nu_{\mathcal{D}^\prime})\) and \(D_\alpha(\nu_{\mathcal{D}^\prime}||\rho_k)\) can be shown.

Beyond strong convexity. To extend beyond strong convexity, one may naively apply Lemma 1 for convex and non-convex settings. Unfortunately, both cases lead to monotonically increasing LSI constant \(C_k\). As a result, given an \(\varepsilon_0\), proving to achieve an arbitrarily small \(\varepsilon\) is challenging even with \(K\rightarrow \infty\) since the LSI constant may be unbounded. More specifically, if \(f\) is convex and \(\eta \leq \frac{2}{L}\), then \(h(x) = x - \eta \nabla f(x)\) is \(1\)-Lipschitz. If \(f\) is \(L\)-smooth only, the map \(h\) is \((1+\eta L)\)-Lipschitz. Applying Lemma 1 leads to the recursions on \(C_k\). For the convex case, we have \(C_{k+1} \leq C_k + 2\eta\sigma^2\). For the non-convex case, we have \(C_{k+1} \leq (1+\eta L)^2C_k + 2\eta\sigma^2.\)

One of our contributions is to demonstrate that \(C_k\) has a universal upper bound which is independent of the number of iterations. Hence, the exponential decay in Rényi difference still holds. The key is to leverage the geometry of \(\mathcal{C}_R\) to establish an LSI upper bound that is independent of \(k\) using the result of [21], which has not been explored in the prior privacy literature [12], [18], [25].

 [19] also leverage the geometry of \(\mathcal{C}_R\) for the DP guarantee of learning with projected noisy (S)GD, but their analysis follows privacy amplification by iteration [27] and still require convexity. Our result demonstrates the potential of Langevin dynamic analysis for unlearning guarantees of non-convex problems.

12.2 Formal Proof↩︎

We will start with the proof for the strongly convex case and then extend it for convex and non-convex cases. As indicated in our sketch of proof, there are two main parts of our proof. The first is to characterize the decay in Rényi divergence between two processes \(y_k,y_k^\prime\) under LSI conditions. The second is to track the LSI constant of \(y_k,y_k^\prime\) throughout the unlearning process. The analysis is a modification of the proof of Lemma 8 in [15].

We first define some useful quantities and list all technical lemmas that we need to proof. For \(\alpha>0\) and any two probability distribution \(\rho,\nu\) with the same support, define \[\begin{align} \label{eq:FnG} & F_{\alpha}(\rho;\nu) = \mathbb{E}_{\nu}[(\frac{\rho}{\nu})^\alpha]=\int \nu(x)(\frac{\rho}{\nu})^\alpha(x)\,dx.\\ & G_{\alpha}(\rho;\nu) = \mathbb{E}_{\nu}[(\frac{\rho}{\nu})^\alpha\|\nabla \log \frac{\rho}{\nu}\|^2] = \mathbb{E}_{\nu}[(\frac{\rho}{\nu})^{\alpha-2}\|\nabla \frac{\rho}{\nu}\|^2] = \frac{4}{\alpha^2} \mathbb{E}_{\nu}[\|\nabla (\frac{\rho}{\nu})^{\alpha/2}\|^2]. \end{align}\tag{4}\] Note that \(D_\alpha(\rho||\nu) = \frac{1}{\alpha-1}\log F_{\alpha}(\rho;\nu)\) by definition and \(G_{\alpha}(\rho;\nu)\) is known as the Rényi Information, where the limit \(\alpha = 1\) recovers the relative Fisher information [15]. Now we introduce all the technical lemmas we need. The first is data-processing inequality for Rényi divergence, which is the Lemma 2.6 in [32]. The second and third lemmas are based on results in [15]. We note again that we use the definition of LSI in [26], where the LSI constant is reciprocal to those defined in [15].

Now we are ready to prove Theorem 2 under strong convexity assumption.

The proof beyond strong convexity is similar, except the characterization of \(C_k\) is different. As we mentioned in the main text, without strong convexity we can only prove an upper bound of the LSI constant that grows monotonically with respect to the iterations. To prevent a diverging LSI constant, we leverage the boundedness of the projected set \(\mathcal{C}_R\) to establish an iteration-independent bound for the LSI constant. Below we give the proof of Theorem 2 without the strong convexity assumption.

13 Proof of Theorem 3↩︎

The proof is mainly modified from the analysis of [18] with our LSI constant analysis. First, we list the all needed notations and technical lemmas adopted from [18]. Let us start with the PNGD process with training dataset \(\mathcal{D}\) and \(\mathcal{D}^\prime\) as before \[\begin{align} & x_{t+1} = \Pi_{\mathcal{C}_R}\left(x_t - \eta\nabla f_{\mathcal{D}}(x_t) + \sqrt{2\eta \sigma^2} W_t\right),\\ & x_{t+1}^\prime = \Pi_{\mathcal{C}_R}\left(x_t^\prime - \eta\nabla f_{\mathcal{D}^\prime}(x_t^\prime) + \sqrt{2\eta \sigma^2} W_t\right),\;W_t\stackrel{\text{iid}}{\sim}\mathcal{N}(0,I_d), \end{align}\] For each iteration, the above update is equivalent to the following two steps: \[\begin{align} & x_{t,1} = x_t - \eta\nabla f_{\mathcal{D}}(x_t) + \sqrt{\eta \sigma^2} W_t,\;x_{t+1} = \Pi_{\mathcal{C}_R}\left(x_{t,1} + \sqrt{\eta \sigma^2} W_t\right). \end{align}\] That is, it can be decomposed into another noisy GD update followed by a small additive noise with projection. Let \(\nu_t, \nu_{t,1},\nu_t^\prime, \nu_{t,1}^\prime\) be the law of \(x_t,x_{t,1},x_t^\prime,x_{t,1}^\prime\) respectively. Finally, we introduce the following technical lemma from [18] specialized to PNGD case.

The proof is an application of Lemma 5 but with the integral involving time-dependent LSI constant. Now we are ready to prove our Theorem 3.

14 Proof of Corollary 1↩︎

While our main theorems only discuss one unlearning request, we can generalize it to address multiple unlearning requests. Consider the case where our learning process is trained with dataset \(\mathcal{D}\). At the unlearning phase, we receive a sequence of unlearning requests so that our dataset becomes \(\mathcal{D}_1,\mathcal{D}_2,\ldots,\mathcal{D}_S\), where each consecutive dataset \(\mathcal{D}_s,\mathcal{D}_{s+1}\) are adjacent (i.e., each unlearning request ask for unlearning one data point). Let us denote \(\nu_{\mathcal{D}_s}\) the output probability distribution of \(\mathcal{M}(\mathcal{D}_s)\) for \(s\geq 0\), where we set \(\mathcal{D}_0 = \mathcal{D}\). Sequential unlearning can be viewed as transferring along \(\nu_{\mathcal{D}_0}\rightarrow\nu_{\mathcal{D}_1}\cdots\rightarrow\nu_{\mathcal{D}_S}\), where for each request we will stop when we are “\(\varepsilon\)” away from the target distribution in terms of Rényi difference. As a result, our actual path is \(\nu_{\mathcal{D}_0}\rightarrow\bar{\nu}_{\mathcal{D}_1}\cdots\rightarrow\bar{\nu}_{\mathcal{D}_S}\) for some sequence of distribution \(\{\bar{\nu}_{\mathcal{D}_s}\}_{s=1}^S\) such that the \(\alpha\) Rényi difference \(d_\alpha(\nu_{\mathcal{D}_s},\bar{\nu}_{\mathcal{D}_s})\leq \varepsilon\). See Figure 2 for a pictorial example of the case \(S=2\). While we are unable to characterize the convergence along \(\bar{\nu}_{\mathcal{D}_s}\rightarrow \bar{\nu}_{\mathcal{D}_{s+1}}\) directly, we can leverage the weak triangle inequality of Rényi divergence to provide an upper bound of it.

Note that by choosing \(p=q=2\), we can also establish the weak triangle inequality for Rényi difference \(d_\alpha\) as follows \[\begin{align} & D_{\alpha}(P||R) \leq \frac{\alpha-\frac{1}{2}}{\alpha-1} D_{2\alpha}(P||Q) + D_{2\alpha-1}(Q||R) \\ & \stackrel{(a)}{\leq} \frac{\alpha-\frac{1}{2}}{\alpha-1} d_{2\alpha}(P,Q) + d_{2\alpha-1}(Q,R)\\ & \stackrel{(b)}{\leq} \frac{\alpha-\frac{1}{2}}{\alpha-1} d_{2\alpha}(P,Q) + d_{2\alpha}(Q,R) \\ & \stackrel{(c)}{\leq} \frac{\alpha-\frac{1}{2}}{\alpha-1} \left(d_{2\alpha}(P,Q) + d_{2\alpha}(Q,R)\right), \\ \end{align}\] where (a) is due to the definition of Rényi difference, (b) is due to the monotonicity of Rényi divergence in \(\alpha\) and (c) is due to the fact that for all \(\alpha>1\), \(\frac{\alpha-\frac{1}{2}}{\alpha-1}\geq 1\). Repeat the same analysis for \(D_{\alpha}(R||P)\) and combine with the bound above, one can show that \[\begin{align} & d_{\alpha}(P,R) \leq \frac{\alpha-\frac{1}{2}}{\alpha-1} \left(d_{2\alpha}(P,Q) + d_{2\alpha}(Q,R)\right). \end{align}\]

The main idea is illustrated in Figure 2 (a). We first leverage Theorem 2 to upper bound the Rényi difference \(d_\alpha(\bar{\nu}_{\mathcal{D}_2},\nu_{\mathcal{D}_2})\) in terms of the Rényi difference between \(d_\alpha(\bar{\nu}_{\mathcal{D}_1},\nu_{\mathcal{D}_2})\) (dash line) with a decaying factor. Then by weak triangle inequality of Rényi difference we derived above, we can further bound it with \(\varepsilon^{(1)}(2\alpha)\) (black line) and \(\varepsilon_0(2\alpha)\) (red line).

15 Proof of Lemma 1↩︎

16 Proof of Lemma 4↩︎

17 Proof of Proposition 4↩︎

The proof is a direct manipulation of the Rényi divergence. Due to symmetry, we will only show that \(D_\alpha(\tilde{\nu}_\mathcal{D},\tilde{\nu}_{\mathcal{D}^\prime})\leq \frac{2\alpha F}{(\alpha-1) n}\), as the proof for the bound of \(D_\alpha(\tilde{\nu}_{\mathcal{D}^\prime},\tilde{\nu}_{\mathcal{D}})\) is identical.

Define \(Z_{\mathcal{D}} = \int \exp(-f_{\mathcal{D}}(x)) dx\) be the normalizing constant. Then we have \[\begin{align} \label{eq:prop95eq1} & D_\alpha(\tilde{\nu}_\mathcal{D},\tilde{\nu}_{\mathcal{D}^\prime}) = \frac{1}{\alpha - 1}\log \mathbb{E}_{x\sim \tilde{\nu}_{\mathcal{D}^\prime}}\left(\frac{\tilde{\nu}_{\mathcal{D}}(x)}{\tilde{\nu}_{\mathcal{D}^\prime}(x)}\right)^\alpha= \frac{1}{\alpha - 1}\log \mathbb{E}_{x\sim \tilde{\nu}_{\mathcal{D}}}\left(\frac{\tilde{\nu}_{\mathcal{D}}(x)}{\tilde{\nu}_{\mathcal{D}^\prime}(x)}\right)^{\alpha-1}\\ & = \frac{1}{\alpha - 1}\log \left(\left(\frac{Z_{\mathcal{D}^\prime}}{Z_{\mathcal{D}}}\right)^{\alpha-1}\mathbb{E}_{x\sim \tilde{\nu}_{\mathcal{D}}}\left(\frac{\exp(-f_{\mathcal{D}}(x))}{\exp(-f_{\mathcal{D}^\prime}(x))}\right)^{\alpha-1}\right) \\ & = \log(\frac{Z_{\mathcal{D}^\prime}}{Z_{\mathcal{D}}}) + \frac{1}{\alpha-1}\log(\mathbb{E}_{x\sim \tilde{\nu}_{\mathcal{D}}}\left(\frac{\exp(-f_{\mathcal{D}}(x))}{\exp(-f_{\mathcal{D}^\prime}(x))}\right)^{\alpha-1}). \end{align}\tag{6}\] Recall that \(\mathcal{D}\) and \(\mathcal{D}^\prime\) are adjacent, thus they only differ in one index. Without loss of generality, assume the index is \(n\) so that \(\mathbf{d}_i=\mathbf{d}_i^\prime\) for all \(i<n\). By definition, \[\begin{align} & f_{\mathcal{D}^\prime}(x) = \frac{1}{n}\sum_{i=1}^{n-1} f(x;\mathbf{d}_i^\prime) + \frac{1}{n}f(x;\mathbf{d}_n^\prime)\\ & = \frac{1}{n}\sum_{i=1}^{n-1} f(x;\mathbf{d}_i^\prime) + \frac{1}{n}f(x;\mathbf{d}_n) + \frac{1}{n}f(x;\mathbf{d}_n^\prime)-\frac{1}{n}f(x;\mathbf{d}_n)\\ & = f_{\mathcal{D}}(x) + \frac{1}{n}(f(x;\mathbf{d}_n^\prime)-f(x;\mathbf{d}_n)). \end{align}\] As a result, the ratio of the normalizing constant can be bounded as \[\begin{align} & \frac{Z_{\mathcal{D}^\prime}}{Z_{\mathcal{D}}} = \frac{\int \exp(-f_{\mathcal{D}^\prime}(x)) dx}{Z_{\mathcal{D}}} = \frac{\int \exp(-f_{\mathcal{D}^\prime}(x)) dx}{Z_{\mathcal{D}}} = \frac{\int \exp(-f_{\mathcal{D}}(x)+\frac{f(x;\mathbf{d}_n^\prime)-f(x;\mathbf{d}_n)}{n}) dx}{Z_{\mathcal{D}}}\\ & \leq \frac{\int \exp(-f_{\mathcal{D}}(x)+\frac{|f(x;\mathbf{d}_n^\prime)-f(x;\mathbf{d}_n)|}{n}) dx}{Z_{\mathcal{D}}}\\ & \leq \frac{\int \exp(-f_{\mathcal{D}}(x)+\frac{F}{n}) dx}{Z_{\mathcal{D}}} = \frac{\exp(\frac{F}{n})\int \exp(-f_{\mathcal{D}}(x)) dx}{Z_{\mathcal{D}}}= \frac{\exp(\frac{F}{n})Z_{\mathcal{D}}}{Z_{\mathcal{D}}} = \exp(\frac{F}{n}). \end{align}\]

On the other hand, for the second term we have \[\begin{align} & \mathbb{E}_{x\sim \tilde{\nu}_{\mathcal{D}}}\left(\frac{\exp(-f_{\mathcal{D}}(x))}{\exp(-f_{\mathcal{D}^\prime}(x))}\right)^{\alpha-1} = \mathbb{E}_{x\sim \tilde{\nu}_{\mathcal{D}}} \exp(-(\alpha-1)(f_{\mathcal{D}}(x)-f_{\mathcal{D}^\prime}(x))) \\ & \leq \mathbb{E}_{x\sim \tilde{\nu}_{\mathcal{D}}} \exp((\alpha-1)(\frac{F}{n})) = \exp((\alpha-1)(\frac{F}{n})). \end{align}\] As a result, we can further simplify 6 as follows \[\begin{align} & D_\alpha(\tilde{\nu}_\mathcal{D},\tilde{\nu}_{\mathcal{D}^\prime}) = \log(\frac{Z_{\mathcal{D}^\prime}}{Z_{\mathcal{D}}}) + \frac{1}{\alpha-1}\log(\mathbb{E}_{x\sim \tilde{\nu}_{\mathcal{D}}}\left(\frac{\exp(-f_{\mathcal{D}}(x))}{\exp(-f_{\mathcal{D}^\prime}(x))}\right)^{\alpha-1})\\ & \leq \frac{F}{n} + \frac{(\alpha-1) F}{(\alpha-1)n} = \frac{2F}{n}. \end{align}\] Together we complete the proof.

18 Experiment Details↩︎

18.1 \((\alpha,\varepsilon)\)-RU to \((\epsilon,\delta)\)-Unlearning Conversion↩︎

Let us first state the definition of \((\epsilon,\delta)\)-unlearning from prior literature [1], [7], [8].

Following the same proof of RDP-DP conversion (Proposition 3 in [22]), we have the following \((\alpha,\varepsilon)\)-RU to \((\epsilon,\delta)\)-unlearning conversion as well.

18.2 Datasets↩︎

MNIST [34] contains the grey-scale image of number \(0\) to number \(9\), each with \(28 \times 28\) pixels. We follow [8] to take the images with the label \(3\) and \(8\) as the two classes for logistic regression. The training data contains \(11982\) instances in total and the testing data contains \(1984\) samples. We spread the image into an \(x \in \mathbb{R}^{d}, d = 724\) feature as the input of logistic regression.

CIFAR-10 [35] contains the RGB-scale image of ten classes for image classification, each with \(32 \times 32\) pixels. For CIFAR-10-binary, we also select class #3 (cat) and class #8 (ship) as the two classes for logistic regression. The training data contains \(10000\) instances and the testing data contains \(2000\) samples. As to CIFAR-10-multi-class, we include all the classes for multi-class logistic regression. The training data contains \(50000\) instances and the testing data contains \(10000\) 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 [36] from Torch-vision library [48], [49] as the input of our logistic regression. The compact feature encoding is \(x \in \mathbb{R}^{d}, d = 512\).

All the inputs from the datasets are normalized with the \(\ell_2\) norm of \(1\).

18.3 Experiment Settings↩︎

Hardware and Frameworks All the experiments run with PyTorch=2.1.2 [50] and numpy=1.24.3 [51]. 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 \(\mathcal{D} = \{\boldsymbol{x}_i \in \mathbb{R}^d, y_i \in \{-1, +1\}\}_{i=1}^n\), our goal is to obtain a set of parameters \(\boldsymbol{w}\) that optimizes the objective below: \[\label{equ:logistic95regression} \mathcal{L}(\boldsymbol{w}; \mathcal{D}) = \frac{1}{n} \sum_{i = 1}^n l(\boldsymbol{w}^\top \boldsymbol{x}_i, y_i) + \frac{\lambda}{2} || \boldsymbol{w} ||_2^2,\tag{7}\] where the objective consists of a standard logistic regression loss \(l(\boldsymbol{w}^\top x_i, y_i) = - \log \sigma (y_i \boldsymbol{w}^\top \boldsymbol{x}_i)\), where \(\sigma(t) = \frac{1}{1 + \exp(-t)}\) is the sigmoid function; and a \(\ell_2\) regularization term where \(\lambda\) is a hyper-parameter to control the regularization, and we set \(\lambda\) as \(10^{-6} \times n\) across all the experiments. By simple algebra one can show that [7]

\[\begin{align} & \nabla l(\boldsymbol{w}^\top \boldsymbol{x}_i, y_i) = (\sigma (y_i \boldsymbol{w}^\top \boldsymbol{x}_i )- 1) y_i \boldsymbol{x}_i + \lambda \boldsymbol{w},\\ & \nabla^2 l(\boldsymbol{w}^\top \boldsymbol{x}_i, y_i) = \sigma (y_i \boldsymbol{w}^\top \boldsymbol{x}_i ) (1-\sigma (y_i \boldsymbol{w}^\top \boldsymbol{x}_i ))\boldsymbol{x}_i\boldsymbol{x}_i^T + \lambda I_d. \end{align}\] Due to \(\sigma (y_i \boldsymbol{w}^\top \boldsymbol{x}_i)\in [0,1]\), it is not hard to see that we have smoothness \(L=1/4+\lambda\) and strong convexity \(\lambda\).

The per-sample gradient with clipping w.r.t. the weights \(\boldsymbol{w}\) of the logistic regression loss function is given as: \[\nabla_{clip} l(\boldsymbol{w}^\top \boldsymbol{x}_i, y_i) = \Pi_{\mathcal{C}_M}\left((\sigma (y_i \boldsymbol{w}^\top \boldsymbol{x}_i )- 1) y_i \boldsymbol{x}_i\right) + \lambda \boldsymbol{w},\] where \(\Pi_{\mathcal{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 [18], the per-sampling clipping operation still results in a \(L\)-smooth, \(m\)-strongly convex objective. The resulting Langevin learning/unlearning update on the full dataset is as follows: \[\frac{1}{n} \sum_{i=1}^n \nabla_{clip} l(\mathbf{w}^T\mathbf{x}_i,y_i),\]

Finally, 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 \(\|(\sigma (y_i \boldsymbol{w}^\top \boldsymbol{x}_i )- 1) y_i \boldsymbol{x}_i\| \leq 1\).

As to multi-class classification task \(\mathcal{D} = \{\boldsymbol{x}_i \in \mathbb{R}^d, y_i \in \{-1, +1\}^c\}_{i=1}^n\), the loss function is denoted as follows [18]:

\[\label{equ:logistic95regression95mult} \mathcal{L}(\boldsymbol{w}; \mathcal{D}) = \frac{1}{n} \sum_{i = 1}^n l(\boldsymbol{w}^\top \boldsymbol{x}_i, y_i) + \frac{\lambda}{2} || \boldsymbol{w} ||_2^2,\tag{8}\] where \[l(\boldsymbol{w}^\top \boldsymbol{x}_i, y_i) = -y^1 \log (\frac{e^{w_1^\top x_i}}{e^{w_1^\top x_i}+...+e^{w_c^\top x_i}}) - ... - y^c \log (\frac{e^{w_c^\top x_i}}{e^{w_1^\top x_i}+...+e^{w_c^\top x_i}}).\] After similar derivations, the aforementioned objective function can also yield an explicit expression for the gradient, as well as bounds for the constants.

The constant meta-data of the loss function in equation  7 and 8 above for the datasets is shown in the table below:

Learning from scratch set-up For the baselines and our Langevin unlearning framework, we all sample the initial weight \(\boldsymbol{w}\) randomly sampled from i.i.d Gaussian distribution \(\mathcal{N}(\mu_0, C_{\text{LSI}})\), where \(\mu_0\) is a hyper-parameter denoting the initialization mean and we set as \(1000\) to simulate the situation where the initial \(w\) has a long distance towards the optimum alike most situations in real-world applications. For the learning methods \(\mathcal{M}\), we set \(T=10,000\) for all the methods 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 \(\mathcal{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 [52], where they replace a point with a special null point \(\perp\).

General implementation of baseline D2D [8]

\(\bullet\) Across all of our experiments involved with D2D, we follow the original paper to set the step size as \(2 / (L + m)\).

\(\bullet\) For the experiments in Fig. 3 (a), we calculate the noise to add after gradient descent with the non-private bound as illustrated in Theorem. 9 (Theorem 9 in [8]); For experiments with sequential unlearning requests in Fig. 3 (b), we calculate the least step number and corresponding noise with the bound in Theorem. 10(Theorem 28 in [8]).

\(\bullet\) The implementation of D2D follows the pseudo code shown in Algorithm 1,2 in  [8] as follows:

The settings and the calculation of \(I, \sigma\) in Algorithm. 6 are discussed in the later part of this section and could be found in Section. 19.

General Implementation of Langevin Unlearning

\(\bullet\) We set the step size \(\eta\) for Langevin unlearning framework across all the experiments as \(1/L\).

\(\bullet\) The pseudo code for Langevin unlearning framework is as follows:

18.4 Implementation Details for Fig. 3 (a)↩︎

In this experiment, we first train the methods on the original dataset \(\mathcal{D}\) from scratch to obtain the initial weights \(\boldsymbol{w}_0\). Then we randomly remove a single data point (\(S=1\)) from the dataset to get the new dataset \(\mathcal{D}'\), and unlearn the methods from the initial weights \(\hat{\boldsymbol{w}}\) and test the accuracy on the testing set.

we set the target \(\hat{\epsilon}\) with \(6\) different values as \([0.05, 0.1, 0.5, 1, 2, 5]\). For each target \(\hat{\epsilon}\):

\(\bullet\) For D2D, we set three different unlearning gradient descent step budgets as \(I=1,2,5\), and calculate the corresponding noise to be added to the weight after gradient descent on \(\mathcal{D}\) according to Theorem. 9, where the detailed noise information is shown in the table below:

\(\bullet\) For the Langevin unlearning framework, we set the unlearning fine-tune step budget as \(\hat{K}=1\) only, and calculate the smallest \(\sigma\) that could satisfy the fine-tune step budget and target \(\hat{\epsilon}\) at the same time. The calculation follows the binary search algorithm as follows:

The \(\sigma\) found is reported in the table below:

18.5 Implementation Details for Fig. 3 (b)↩︎

In this experiment, we fix the target \(\hat{\epsilon} = 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 \(\boldsymbol{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.

\(\bullet\) For D2D, According to the original paper, only one data point could be removed a time. We calculate the least required steps and the noise to be added according to Theorem. 10.

\(\bullet\) For Langevin unlearning, we fix the \(\sigma = 0.03\), and we let the model unlearn \([5, 10, 20]\) per time thanks to our theory. We obtain the least required unlearning steps for each removal operation \(K_{\text{list}}\) following corollary. 1. The pseudo code is shown in Algorithm. 10.

18.6 Implementation Details for Fig. 3 (c)↩︎

In this study, we set the \(\sigma\) of the Langevin unlearning framework as \([0.05, 0.1, 0.2, 0.5, 1]\). For each \(\sigma\), we calculate the corresponding \(\epsilon_0\). We train the Langevin unlearning framework from scratch to get the initial weight \(\boldsymbol{w}_0\). Then we remove \(100\) data points from the dataset and unlearn the model. We here also call Algorithm. 9 to obtain the least required unlearning steps \(K\).

18.7 Implementation Details for Fig. 4↩︎

In this study, we set different target \(\hat{\epsilon}\) as \([0.5, 1, 2, 5]\) and set different number of data to remove \(S = [1, 50, 100]\). We train the Langevin unlearning framework from scratch to get the initial weight, then remove some data, unlearn the model and report the accuracy. We calculate the least required unlearning steps \(K\) by again calling Algorithm. 9.

18.8 Additional experiments↩︎

19 Unlearning Guarantee of Delete-to-Descent [8]↩︎

Note that the privacy guarantee of D2D [8] 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 9 and 10, one can show that a similar (but slightly worse) bound of the theorem above also holds for D2D [8]. For simplicity and fair comparison, we directly use the bound in Theorem 9 and 10 in our experiment. Note that [52] 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 9 and 10 is whether their unlearning process starts with the “clean” model parameter (Theorem 9) or the noisy model parameter (Theorem 10). Clearly, allowing the server to keep and leverage the non-private internal state provides a weaker notion of privacy [8]. In contrast, our Langevin 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 Langevin unlearning to D2D with Theorem 10 for a fair comparison.

NeurIPS Paper Checklist↩︎

1. Claims

2. Question: Do the main claims made in the abstract and introduction accurately reflect the paper’s contributions and scope?

3. Answer:

4. Justification: All claims are provided with corresponding theorems (i.e., Theorem 2 for unlearning guarantees) and we demonstrate superior privacy-utility-complexity tradeoff via experiments in Section 4.

5. Guidelines:

   • The answer NA means that the abstract and introduction do not include the claims made in the paper.

   • The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.

   • The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.

   • It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.

6. Limitations

7. Question: Does the paper discuss the limitations of the work performed by the authors?

8. Answer:

9. Justification: We provide a detailed discussion on the limitation of our work in Section 6.

10. Guidelines:

    • The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.

    • The authors are encouraged to create a separate "Limitations" section in their paper.

    • The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.

    • The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.

    • The authors should reflect on the factors that influence the performance of the approach. For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.

    • The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.

    • If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.

    • While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren’t acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.

11. Theory Assumptions and Proofs

12. Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?

13. Answer:

14. Justification: All assumptions are clearly stated in our theorems, see Theorem 2 and 3 for instance. The proofs for every theoretical statements are provided in Appendix 11 to 17.

15. Guidelines:

    • The answer NA means that the paper does not include theoretical results.

    • All the theorems, formulas, and proofs in the paper should be numbered and cross-referenced.

    • All assumptions should be clearly stated or referenced in the statement of any theorems.

    • The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition.

    • Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.

    • Theorems and Lemmas that the proof relies upon should be properly referenced.

16. Experimental Result Reproducibility

17. Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?

18. Answer:

19. Justification: We provide the experiment code in our supplementary materials and details about our settings in Section 18.

20. Guidelines:

    • The answer NA means that the paper does not include experiments.

    • If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.

    • If the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.

    • Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.

    • While NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example

      1. If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.

      2. If the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.

      3. If the contribution is a new model (e.g., a large language model), then there should either be a way to access this model for reproducing the results or a way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).

      4. We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.

21. Open access to data and code

22. Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material?

23. Answer:

24. Justification: We provide the experiment code in our supplementary materials and all data used in our experiments are cited with public access.

25. Guidelines:

    • The answer NA means that paper does not include experiments requiring code.

    • Please see the NeurIPS code and data submission guidelines (https://nips.cc/public/guides/CodeSubmissionPolicy) for more details.

    • While we encourage the release of code and data, we understand that this might not be possible, so “No” is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).

    • The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https://nips.cc/public/guides/CodeSubmissionPolicy) for more details.

    • The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.

    • The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only a subset of experiments are reproducible, they should state which ones are omitted from the script and why.

    • At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).

    • Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted.

26. Experimental Setting/Details

27. Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?

28. Answer:

29. Justification: All experimental details are included in Appendix 18.

30. Guidelines:

    • The answer NA means that the paper does not include experiments.

    • The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them.

    • The full details can be provided either with the code, in appendix, or as supplemental material.

31. Experiment Statistical Significance

32. Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?

33. Answer:

34. Justification: All results are provided with 1 standard deviation error bar, which is gathered over 100 independent trials.

35. Guidelines:

    • The answer NA means that the paper does not include experiments.

    • The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.

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

    • It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified.

    • For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).

    • If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.

36. Experiments Compute Resources

37. Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?

38. Answer:

39. Justification: The compute resources used for our experiments are detailed in Appendix 18.3.

40. Guidelines:

    • The answer NA means that the paper does not include experiments.

    • The paper should indicate the type of compute worker CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.

    • The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.

    • The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn’t make it into the paper).

41. Code Of Ethics

42. Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines?

43. Answer:

44. Justification: The authors have read the NeurIPS Code of Ethics and affirm that this work conforms with it in every respect.

45. Guidelines:

    • The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.

    • 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).

46. Broader Impacts

47. Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?

48. Answer:

49. Justification: We briefly discuss why our work does not have any negative societal impacts in 7.

50. 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).

51. Safeguards

52. 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)?

53. Answer:

54. Justification:

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

56. Licenses for existing assets

57. 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?

58. Answer:

59. Justification: All datasets used in our experiments are properly cited with proper open access license, see Section 4.

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

61. New Assets

62. Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?

63. Answer:

64. Justification:

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

66. Crowdsourcing and Research with Human Subjects

67. 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)?

68. Answer:

69. Justification:

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

71. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects

72. 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?

73. Answer:

74. Justification:

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

References↩︎

---

1. We refer privacy loss as two-sided Rényi divergence of two distributions, which is defined as Rényi difference in Definition 2. Note that it is standard to define privacy loss for unlearning as the two-sided Rényi divergence between the weight distribution of the unlearned model and the retrained model. Such a definition directly relates to the power of the strongest possible adversary for distinguishing these two cases [14].↩︎

2. Their unlearning privacy definition does not compare with retraining and they only discuss one-side Rényi divergence. As a result, their unlearning guarantee is less compatible with DP and cannot control both type I and II errors simultaneously against the best possible adversary [14].↩︎

3. https://github.com/Graph-COM/Langevin_unlearning↩︎