Certified Machine Unlearning via Noisy Stochastic Gradient Descent

Summary

The paper studies a practically important problem of machine unlearning and provides rigorous statistical guarantees for unlearning using the tools from the differential privacy. More specifically, it is shown that, for strongly convex losses, running Projected SGD on the new (adjacent) dataset guarantees that the removed data point will be forgotten, that is the output of "unlearning" algorithm will be close to the output of the Projected SGD if data point on a new dataset.

Strengths

The algorithm is simple and easy to understand. The presentation is good with nice illustrations of the concepts. All necessary background is provided. The theoretical claims look sound to the best of my knowledge, apart from some technical remarks mentioned below.

Weaknesses

(Major) My main concern is very conceptual. Isn't it trivial that running SGD (unlearning part) on a strongly convex loss with updated dataset will eventually converge to the same unique optimum of the new loss as if we have started training from scratch. I want to highlight that in the strongly convex case, the optimum is unique. Moreover, the initial distance to the optimum is forgotten exponentially fast for constant step-size SGD. Therefore, I cannot understand why the derived result in this paper is not trivial. In my view, as expected, the authors face a difficulty in the convex case (getting only vacuous result Corollary 3.9). (Minor) 1. Why the same batches are used in the unlearning process, shouldn't batches be from the updated dataset? This is perhaphs just a notational issue. 2. It is unclear to me what is the output of Algorithm 1. 3. It is unclear what it means to satisfy $(\alpha, \varepsilon)$-RU **with $c = 1-\eta m$** in Theorem 3.2. There is no parameter $c$ in definition 2.3. 4. The quantity $h_{\#}\mu$ in Lemma F.2. is not defined. This lemma is used in Proposition F.3., which is one of the key tools in analysis. 5. $\mathcal Z_{\mathcal B}$ appearing first in Theorem 3.2 is not defined in the main part. I had to go to Appendix to understand what it is. 6. Figure 3 (c) is not informative. All lines and confidence intervals overlap. 7. Why the method is called "contractive noisy iteration"? A more conventional name like Projected SGD would be more appropriate. 8. It would be helpful to explain the role of the projection in the algorithm. Is it possible to employ it without projection? 9. In the abstract, "convexity assumption" should be changed to "strong convexity assumption" because the guarantees in the convex case are vacuous in this paper.

Questions

n/a

Rating

4

Confidence

2

Soundness

3

Presentation

3

Contribution

2

Limitations

The results are limited to strongly convex objectives. To make the problem not trivial, it is crucial to consider convex or PL losses.

Summary

The paper proposes an effective and efficient machine unlearning algorithm based on projected noisy gradient descent (PSGD). The proposed methods can be extended to handle multiple unlearning requests. The theoretical unlearning guarantee is established when the loss is assumed to be convex and smooth. Experiments verify the effectiveness of the proposed method.

Strengths

1. A simple unlearning algorithm is established by PSGD, whose effectiveness and efficiency is verified by experiments. Especially, the experiments show that the proposed algorithm outperforms the baseline with less gradient complexity. 2. Theoretical analysis of unlearning guarantee for the proposed algorithm is established for convex smooth losses, privacy-utility-complexity trade-off regarding the mini-batch size b for approximate unlearning is highlighted. 3, The paper is well-written and easy to follow.

Weaknesses

1. The smoothness of the loss is required, which might limit the algorithm's applicability. 2. In experiments, a logistic loss with $\ell_2$ regularization is considered. It would be better to provides some results on convex loss since the corresponding theory is given.

Questions

1. In algorithm, mini-batch sequence B is fixed. Is it reasonable in practice or analysis? 2. The paper states that "A smaller batch size b leads to a better privacy loss decaying rate". This seems counterintuitive. Could authors give some explanation?

Rating

7

Confidence

3

Soundness

4

Presentation

4

Contribution

3

Limitations

NA

Summary

The paper presents a simple scheme for machine unlearning. The algorithm has two parts: in the learning part, the models learns using the original dataset D, and in the second part it unlearns using a neighboring dataset D’. The algorithm uses 1) same batches at every epoch, and same batches for both learning and unlearning, 2) Gaussian noise for both learning and unlearning. Based on Renyi differential privacy and the relation between Renyi unlearning and (ε, δ)-unlearning, the paper shows that the privacy parameter ε drops exponentially with every epoch.

Strengths

Novel set of results

Weaknesses

My main concern is the lack of utility bounds. It’s not hard to design an algorithm which guarantees privacy: just don’t use the dataset at all. What is the utility your algorithm achieves after K iterations of unlearning?

Questions

The assumptions in Theorem 3.2 are rather strong. You assume bounded domain + smoothness + Lipschitzness + strong convexity. Please justify these assumptions. The notation is sometimes confusing. For example, there is notation \nu_{T | B} and there is notation \nu_{D | B}. Line 177: \nu_{D | B}^{0, ‘} is undefined. In Lemma F.2, notation # is undefined. Minor issues: -- Is line 173 the definition of \nu_{D | B}? Please make it clear. The wording sounds like this is already defined, and I spent quite some time trying to find the definition. -- Algorithm 1: please list algorithm’s parameters, such as η and σ -- Line 146: PABI was not defined -- Theorem 3.2: Z_B: you don’t actually use B -- Appendix D: Lipschitzness (no s after z) -- Line 548: “Proof” -> ”Proof of Theorem 3.2” -- I think the presentation could be simplified by focusing on some specific value of α -- C_R: Line 97 doesn’t match Line 169 -- Theorem 3.2: relationship between D’ and D is not mentioned.

Rating

6

Confidence

4

Soundness

3

Presentation

3

Contribution

3

Limitations

None