Certified Machine Unlearning via Noisy Stochastic Gradient Descent

We thank reviewer MVBT for their insightful comments and suggestions. We address the weaknesses and questions below.

W1: Is the unlearning privacy bound for strongly convex settings trivial? Are our results for convex settings vacuous?

Compare to retraining: We agree with reviewer MVBT that under strong convexity, the optimum is unique and SGD can approach that optimum exponentially fast. However, as we have discussed theoretically in lines 234-243 and demonstrated in experiments, our unlearning strategy does offer computational benefits compared to retraining when the initialization is not very close to the optimal solution. In Figure 3(a), we have shown that even unlearning with one epoch is sufficient to achieve good accuracy (utility) and a strong privacy guarantee ($\epsilon \approx 1$). In contrast, for a mini-batch size $b=128$, we need $20$ epochs to ensure the result converges reasonably well.

Convex only: There seems to be a misunderstanding regarding our convex result in Corollary 3.9. The bound is not vacuous when the training epoch $T$ is not too large so that $\frac{2\eta MT}{b} < 2R$. This condition can be met if the model learns reasonably well with moderate $T$ and the projection diameter $2R$ is not set to be extremely small. For example, with $2R = 10$, $b = 128$, $\eta = 1$, and $M = 1$, we can train for at most $639$ epochs while still holding $\frac{2\eta MT}{b} < 2R$. A smaller step size $\eta$ would allow for even more epochs. Under this scenario, our approach still provides computational benefits compared to retraining from scratch when the initialization is not close to every (each corresponding to an adjacent dataset) optimum solution (set). We will clarify this further in our revision.

Compare to noiseless fine-tuning: Instead of retraining from scratch to ensure exact unlearning, another potential approach would be running noiseless SGD and then applying output perturbation (i.e., publishing weights with additive noise) to mitigate privacy leakage, as done in prior work [9]. Note that such methods also require strong convexity for their privacy guarantees. However, there are several downsides to this strategy compared to unlearning with PNSGD (i.e., adding noise at every iteration, our approach). These include an inferior privacy-utility-complexity trade-off, as demonstrated by our experiments, and the issue of non-private hidden states discussed in Appendix N.

Q1: Question about mini-batch

Note that the mini-batches only contain indices, and the underlying dataset is different with adjacent datasets $\mathcal{D},\mathcal{D}^\prime$. Since we denote the replacement notion of dataset adjacency, the size of all considered datasets is always $n$ so that the mini-batch sequences can be the same. The main reason to keep it the same is for the analysis purpose, see also our response to DXXZ, Q1.

Q2: The output of Algorithm 1

We apologize for the confusion. The output is the last iterates of learning and unlearning processes, which are $x^0_T, y^0_K$ respectively. We will make it clear in our revision.

Q3: Meaning of Theorem 3.2

We apologize for the confusion. Theorem 3.2 indicates that the value $c$ is determined by the step size $\eta$ and the strong convexity parameter $\mu$, and it is used solely to determine the bound of $\varepsilon$. This has no bearing on the definition of $(\alpha,\varepsilon)$-RU. We will clarify this point in our revised manuscript to avoid any ambiguity.

Q4: $h_{\sharp} \mu$ is undefined.

We apologize for this oversight. For a function $h$ and a distribution $\mu$, $h_{\sharp} \mu$ denotes the pushforward operation. Essentially, it represents the distribution of $h(X)$, where the random variable/vector $X \sim \mu$. We will ensure this concept is properly defined and explained in the revision.

Q5: Question about $Z_{\mathcal{B}}$

We apologize for the confusion. The meaning of $Z_{\mathcal{B}}$ is explained in line 59, Figure 1, and its caption; it represents the upper bound of the $W_\infty$ distance between two adjacent learning processes. In Theorem 3.2, we provide an explicit formulation of $Z_{\mathcal{B}}$. We will ensure the meaning of $Z_{\mathcal{B}}$ is clear throughout our revised manuscript.

Q6: Why the name 'contractive noisy iteration'?

We followed the terminology used in prior work [15, 16, 20], where the authors introduced the key technical tool (Lemma 2.6) that we employ in our analysis. To give due credit to their contribution, we decided to retain the same name.

Q7: The role of projection and is it necessary?

We leverage the projection operation in multiple aspects of our analysis. Firstly, it is used to prove Theorem 3.1, which shows that the limiting distribution of the PNSGD learning process exists, is unique, and stationary. Secondly, we use it to bound the $W_\infty$ distance between the initial distribution and the target stationary distribution $\nu_{\mathcal{D}|\mathcal{B}}$. This bounding is crucial when applying our results without assuming that the learning process has attained its stationary distribution. This is precisely the aim of Theorem 3.2. If such an assumption is made, we can simplify the bound in Theorem 3.2, leading to Corollary 3.7. Note that the $Z_{\mathcal{B}}$ bound in Corollary 3.7 can always use the former term as an upper bound, rendering everything independent of $2R$, the projection diameter.

In summary, if we directly assume the existence of the stationary distribution of the PNSGD learning process and that it is attained after learning, the projection operation can be omitted. However, in the general case, the projection is essential for the rigor and completeness of our analysis.

We thank reviewer DXXZ for their positive and thoughtful comments. We address the weaknesses and questions below.

W1:Smoothness of the loss is required

We agree with reviewer DXXZ that smoothness assumptions can restrict the applicability of our approach, for which will also list it as a limitation in Appendix B in our revision. We are currently working on relaxing these assumptions in the follow-up works.

Q1: Is mini-batch sequence B to be fixed in Algorithm 1 necessary?

It is currently for analysis purposes, where similar limitations persist in the DP research of PNSGD [22]. We conjecture that one can randomly sample the mini-batch sequence at the beginning of each epoch. Our intuition is that instead of taking expectation with respect to $\mathcal{B}$ at the end of the (un)learning process, we can take the expectation for each epoch where the stationary property of the distribution remains. Nevertheless, the rigorous analysis in this direction is left as an interesting future work.

Q2: Question about a smaller batch size $b$ leading to a better privacy loss decaying rate.

There appears to be a misunderstanding here. We are not saying that a smaller batch size $b$ will lead to better privacy loss; instead, it will lead to a better privacy decaying rate. To clarify, let's examine the bounds presented in Corollary 3.7, where the privacy loss is determined by the initial distance $Z_{\mathcal{B}}$ and the privacy decaying factor $c^{2Kn/b} = (c^{2n/b})^K$ for $K$ unlearning epochs. Notably, a smaller $b$ will lead to a better privacy decaying rate $c^{2n/b}$ ($c < 1$), since we are running more contractive updates (see Figure 1, green part) per epoch.

However, as discussed in lines 234-243, an excessively small $b$ can increase the initial distance $Z_{\mathcal{B}}$. This is because $Z_{\mathcal{B}} = O(((1 - c^{n/b})b)^{-1})$, which is not monotonically decreasing with respect to $b$. Consequently, setting $b$ to its minimum value, such as $b = 1$, does not necessarily yield the optimal privacy guarantee. While smaller batch sizes improve the decaying rate, they can also adversely affect the initial privacy loss, necessitating a balanced choice of $b$, let alone its effect on the utility as discussed in line 230 and demonstrated in experiment section line 362.

We thank reviewer SMx2 for their careful reading, positive assessment, and thoughtful comments. We address the weaknesses and questions below.

W1: No utility bound.

We thank reviewer SMx2 for the thoughtful comments. We agree that utility is an important aspect of the unlearning problem, but we do not think a utility bound is always necessary for a literature on machine unlearning. While a privacy bound is crucial to prevent the worst-case scenario, it is common practice in the machine learning literature to empirically measure utility in an average or data-dependent manner by conducting extensive experiments (as seen in the seminal DP-SGD paper [13]). This is also true in previous unlearning literature [7,11].

However, we acknowledge that there are situations where a formal utility guarantee for the worst-case scenario is important. In such cases, the utility bound for noisy gradient descent is established in the differential privacy literature under strong convexity assumptions; see, for instance, Section 5 of [ref 1]. We will mention this point in our revision to provide clarity on when and how utility bounds can be applied.

Reference

[ref 1] Differential privacy dynamics of langevin diffusion and noisy gradient descent, Chourasia et al., NeurIPS 2021.

Q1: Justifying the assumption

While it is true that our set of assumptions—covering strong convexity, Lipschitz continuity or bounded gradient norm, and smoothness—appears restrictive, these assumptions hold significant practical relevance. They cannot be directly applied to the modern neural networks but they still encompass critical learning problems, including logistic regression, as empirically demonstrated in our experiments.

It is important to underscore that these assumptions are not unique to our work. They are foundational within the existing literature on machine unlearning [7-10] and are similarly necessary for studies related to the differential privacy (DP) guarantees and convergence of hidden-state PNSGD [15, 16, 22]. Specifically, the leading analytical approach for hidden-state PNSGD in privacy contexts—namely, the privacy amplification by iteration (or shifted divergence) analysis—relies on these assumptions. We acknowledge that relaxing these constraints represents a meaningful direction for future research. Indeed, prior works [15, 16, 22] identify this as an open problem, and we are actively conducting research to address these limitations.

Q2:Clarity of notations and typos

We thank reviewer SMx2 for their careful reading and suggestion. We will make sure all notations are defined and typos are corrected in our revision.

Q3:Questions about Theorem 3.2

Thanks for pointing out the issue regarding $\mathcal{Z}_{\mathcal{B}}$. Originally we derived a $\mathcal{B}$ dependent bound $\mathcal{Z}\_{\mathcal{B}}$ by Lemma 3.3. There we have $j_0$ that depends on when the differing index between $\mathcal{D},\mathcal{D}^\prime$ we encounter for a given mini-batch sequence $\mathcal{B}$. In the current Theorem 3.2, we directly choose the worst case $\mathcal{B}$, for which the bound is still valid (but loose). We will correct it in our revision and thank you again for spotting this issue.