Certified Minimax Unlearning with Generalization Rates and Deletion Capacity

Summary

This paper proposes using hessian-based updates to solve the unlearning problem for strongly-convex-strongly-concave minimax learners. They also provide theoretical analyses of the error of such an unlearning algorithm as well as its sensitivity to deleted data.

Strengths

1. This paper is well-written and structured. The narrative is very easy to follow, and the analysis is strong. 2. The unlearning update is simple. 3. While in a restricted setting, the analysis is coherent. 4. Motivation is obviously, well done, given the connections to privacy. This paper operates in a restricted setting with some small issues with the presentation. The issues with presentation are fixable, and I expect the authors will go through and better annotate their notation for the camera-ready version. Moreover, the setting is restricted and not practical for unlearning in modern settings. However, this paper achieves its goal and is a good step in the right direction. I, therefore, advocate for this paper's acceptance.

Weaknesses

1. There is a notational mistake for Equation (5). You are missing a closing parenthesis. 2. In equation 6, you should specify that $m$ is the size of $U$. 3. You miswrote Assumption 2 in Lemma 2. 4. I feel some work is needed on the motivation of the setting of this paper. I will discuss more of this in limitations. However, this paper seems only to work when the loss is strongly-convex-strongly-concave loss functions (or suffers bad constants for transforming in the c,c case). However, unlearning is meant to be a more practical tool for modern learning, where this condition rarely holds.

Questions

1. What is $\mathcal{T}$? I understand that it is the set of memory variables, but that should be more formally defined, and I don't find that it is formally defined elsewhere in the paper. 2. It seems that most of the variables in the statement of Lemma 2 are difficult to understand. It is only after going through the proof that I am able to understand. This should be made more clear. For example, what is $\rho$ or $l$ here? This suggestion follows for correcting Theorem 5. 3. I would be interested if the authors of this paper have thought about weakening the strongly-convex-strongly-concave conditions instead assuming gradient-dominance holds (see "Solving Robust MDPs through No Regret Dynamics" or "Global Optimality Guarantees For Policy Gradient Methods" for examples). 4. Have this paper's authors considered including some small toy experiments to verify their theoretical results? It would be interesting to see if they can achieve strong unlearning for linear classifiers with regularization under this unlearning framework. I also believe this paper is missing a relevant citation: "Accelerated Perceptrons and Beyond" analyzes the generalization/margin of minimax learners in linear or convex-concave settings. This, however, will not impact my score.

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

4 excellent

Presentation

3 good

Contribution

3 good

Limitations

Yes, they have sufficiently addressed the limitations of their works.

Summary

Machine unlearning is a privacy-inspired area to remove certain training samples of users’ data from well-trained model making those samples uninfluential while the unlearning approach does not cause the model to be retrained from scratch (not cause comprehensive computational cost) to achieve the baseline relied on the rest of datasets. The conventional machine unlearning usually applies for standard statistical learning models with one variable, but there is limited work for minimax models. Borrowing from Gaussian mechanism of differential privacy, this work also focuses on epsilon-delta certification of machine unlearning. Moreover, generalization rates and deletion capacity (number of deleted samples) are also very crucial to study in this framework.

Strengths

1. Machine unlearning is a quite new field for privacy of machine learning. This work smoothly introduces the field with related work (a lot of citations) and preliminaries. Also it well states the reason minimax model is important for machine unlearning. 2. Certified minimax unlearning can be well extended to more general loss functions with reasonable generalization rates and deletion capacity results. 3. This work supports successive and online deletion requests, which is computationally efficient for unlearning phase with its minimax unlearning update.

Weaknesses

1. Although this work focuses more on theoretical part of unlearning, it is still better to provide some preliminary results on some datasets. At least in one paragraph of intro or conclusion, authors can discuss scenarios or applications how to make the certified minimax unlearning practical. 2. This work does not discuss the relationships of certified unlearning between STL model and minimax model theoretically (How are they different).

Questions

1. Compared to other approaches for privacy of machine learning like differential privacy, what is the advantage of machine unlearning for the privacy? Since this work focuses on minimax model, the question could narrow down the specific model. 2. On Line 98, is it intentionally “extract” or should it be “exact”?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

4 excellent

Contribution

3 good

Limitations

1. As weakness 1, authors can consider some implications for the applications by adding a paragraph. Like in the beginning of the introduction, how does this work help GAN, ARL or RL? 2. As weakness 2, this work emphasizes how important the certified unlearning for minimax model, but this work does not talk too much about the connection to unlearning for STL models. 3. Instead of putting every proof in the appendix, it is better to add one or two sentences for each theorem or lemma about the clue to prove (what methods will you use? How will you prove?) to convince readers who are interested in the topic but not familiar.

Summary

The papers proposes a Newton-based differentially private algorithm for stochastic minimax problems and analyse the generalization rate and deletion capacity for the algorithms. They analyse the generalization bound for weak primal-dual risk in SC-SC, C-SC and SC-C cases. Also the deletion capacity they derive is $O(n/d^{1/4})$, which is better than the baseline result $O(n/d^{1/2})$. The results of generalization bound and deletion capacity match the bound in the pure minimazation case.

Strengths

The paper is the first one analysing certified machine unlearning for minimax problems and provide certain generalization and deletion capacity guarantee.

Weaknesses

There are several weaknesses and issues: 1. The reviewer is not convinced that weak primal-dual risk is enough to capture the behavior of generalization for minimax problems. In recent literature, people begin to study the strong primal-dual risk for minimax problems even without strong convexity. For example, the authors in ``What is a Good Metric to Study Generalization of Minimax Learners'' derive the result for generalization of strong primal dual risk in convex-concave setting. Therefore, the reviewer thinks the paper can be improved if the authors can extend their result to strong PD risk. 2. Suggestions for writing: The certified machine unlearning and deletion capacity might not be well-known to general audiums. However, in the abstract and begining of the paper, the authors use too many specific terminology for machine unlearning, deletion, etc. It is not friendly to the audiums. The reviewer suggests the authors can discuss more motivation for this paper and give more explanations for the intuition of these terminologies. 3. Missing reference: ''Uniform convergence and generalization for nonconvex stochastic minimax problems'', ''What is a Good Metric to Study Generalization of Minimax Learners''.

Questions

None

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

2 fair

Contribution

2 fair

Limitations

None

Summary

This paper studies the problem of machine learning for the minimax model. By using Newton's step update with the Hessian information of the leftover data and Gaussian Mechanism, the proposed method improves the deletion capacity from $O(n/d^{1/2})$ to $O(n/d^{1/4})$.

Strengths

- Given the rise of GAN and the increasing concern for the privacy of participants in datasets used by GAN/ML models, minimax unlearning is an important problem to study and understand. - The proposed algorithm shows improvement in both strongly convex-strongly convex and the more general convex-concave settings. - The improvement of the deletion capacity from $O(n/d^{1/2})$ to $O(n/d^{1/4})$ could be quite significant for practical problems with high-dimensional features. - The efficient algorithm that dispenses the need for recomputing some of the Hessian information is a nice touch since computing the Hessian matrix can be very computationally expensive. - The paper is well-written overall.

Weaknesses

- Some of the technical details are used before being defined properly. For example, in equation (7), $\kappa$ is defined as $\kappa = l/\mu$ even though $l$ and $\mu$ haven't been defined yet. These quantities are later mentioned in section 4 but it would be better for the readers if those quantities are defined right away.

Questions

- I'm a bit confused about the intuition part where $\nu^\star_{S\}- \nu^\star \approx -\partial_{\nu\nu}^{-1}F_{S\}(w_S^\star,\nu_S^\star)\dot\partial_{\nu w}^{-1}F_{S\}(w_S^\star,\nu_S^\star)(w^\star_{S\}- w^\star)$. Can the author explain how we can use linear approximation and the implicit function theorem to get this result? Also why do we want to leave out the second term in eq. 60? - Is there any benefit in doing the update in Algorithm 2 compared to Algorithm 3? As the authors have shown in the proofs of Lemma 1 and Lemma 19, the analyses are basically identical so I'm just curious if there's any good thing about the update of Algorithm 1 and why we want to do it in the first place? - Seems like there's no improvement in the result in SC-SC case compared to C-C case. Is this the artifact of the algorithm or is this something that usually happens in minimax learning?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

N/A

Summary

The paper studies approximate unlearning for minimax problems. They design learning and unlearning procedures and provide bounds on deletion capacity in terms of generalization performance (weak gap). Akin to minimization (statistical learning), the deletion capacity for strongly convex-strongly concave setting, is shown to be, $n/d^{1/4}$, where $n$ is the number of samples and $d$, dimension. The authors also provide extensions to non strongly convex/concave settings and efficient updates.

Strengths

The problem of machine unlearning has gathered a lot of interest recently, owing to various privacy regulations. Further, the minimax formulation, is widely applicable, especially in robust adversarial learning and reinforcement learning. The paper is the first to study unlearning for minimax settings. Therefore, the topic of the work is natural and timely.

Weaknesses

1. The paper very closely follows the outline and techniques in prior work of Sekhari et. al. The extensions, to non-strongly convex settings (via regularization) and efficient updates also use techniques directly from prior work. If there are additional challenges due to the minimax (as opposed to min) structure, then I don't think they are communicated well in the write-up. The only relevant section is Section 4.1 "Intuition for Minimax Unlearning Update", however, I found it too raw to convey the intuition -- for instance, how does Eqn. 10 follow? In the current state of the write-up, it is difficult to evaluate if there are significant challenges overcome in relation to prior works. 2. Comparison between Section 4.3 and 5.2: It seems to me that both are in the same setting, and achieve the same guarantees, yet Section 5.2 provides a more efficient update. If indeed Section 5.2 is a strict improvement over 4.3, then what is the point of devoting considerable space to the weaker result in Section 4.3. The authors should re-organize and present the strongest result in the main paper. The space should be used to explain the challenges compared to the minimization setting. If this is not the case, then please explain the differences. 3. Strong gap vs weak gap: The generalization performance considered in the paper is the weak primal-dual gap. In the non-private setting, "strong" primal-dual gap (as opposed to weak) is what is typically considered. Further, as explained in Bassily et al. 2023, the strong gap criterion has game-theoretic interpretation and motivation, and moreover, the weak and strong gaps may be arbitrarily apart. Seemingly, the consideration of the weak gap in the paper primarily stems from challenges of studying strong gap under privacy settings, until recently. However, given that the work Bassily et al. 2023 has established optimal rates for strong gap under privacy, can the authors, perhaps borrowing techniques from the aforementioned work, also provide guarantees in terms of the strong gap?

Questions

1. Please answer the question posed in weakness 1. 2. Please answer the question posed in weakness 2. 3. Please answer the question posed in weakness 3.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

2 fair

Presentation

3 good

Contribution

2 fair

Limitations

1 The work is limited to the approximate unlearning setting, as opposed to exact unlearning. 2. The authors study generalization performance in terms of weak gap as opposed to strong gap.

Thank you for your rebuttal

I appreciate the author's rebuttal. I maintain my score and vote to accept.

Thanks!

I thank the authors for their detailed response, and in particular their derivation of guarantee on strong gap. I encourage the authors to include this, and the other parts of their response, to the revised paper. I increase my score to 6.