Certified Minimax Unlearning with Generalization Rates and Deletion Capacity
Authors: Jiaqi Liu
Jian Lou
Zhan Qin
Kui Ren
Venue: NeurIPS 2023 poster (2023)
Keywords: machine unlearning
machin learning privacy
minimax learning
certified removal
TL;DR: We provide certified unlearning algorithms for the minimax model with generalization rates  and deletion capacity.

Abstract: We study the problem of $(\epsilon,\delta)$-certified machine unlearning for minimax models. Most of the existing works focus on unlearning from standard statistical learning models that have a single variable and their unlearning steps hinge on the direct Hessian-based conventional Newton update. We develop a new $(\epsilon,\delta)$-certified machine unlearning algorithm for minimax models. It proposes a minimax unlearning step consisting of a total Hessian-based complete Newton update and the Gaussian mechanism borrowed from differential privacy. To obtain the unlearning certification, our method injects calibrated Gaussian noises by carefully analyzing the ''sensitivity'' of the minimax unlearning step (i.e., the closeness between the minimax unlearning variables and the retraining-from-scratch variables). We derive the generalization rates in terms of population strong and weak primal-dual risk for three different cases of loss functions, i.e., (strongly-)convex-(strongly-)concave losses. We also provide the deletion capacity to guarantee that a desired population risk can be maintained as long as the number of deleted samples does not exceed the derived amount. With training samples $n$ and model dimension $d$, it yields the order $\mathcal O(n/d^{1/4})$, which shows a strict gap over the baseline method of differentially private minimax learning that has $\mathcal O(n/d^{1/2})$. In addition, our rates of generalization and deletion capacity match the state-of-the-art rates derived previously for standard statistical learning models.

Certified Minimax Unlearning with Generalization Rates and Deletion Capacity
Jiaqi Liu', Jian 12,, Zhan Qin Kui Ren'
'Zhejiang University
"ZJU-Hangzhow Global Scientific and Technological Innovation Center fjiaqi.ling jian. lou, qinzhan, kuiren]@zju. eew.eeuneeeeeu......... edu. en *Corresponding authors
Abstract
We study the problem of (c, -)-cetiffied machine unlearning for minimax models. Most of the existing works foeus on unlearning from standard statistical learning models that have single variable and their unlearning steps hinge on the direct Hessian-based conventional Newton update. We develop a new (e, -ceertiide machine unlearning algorithm for minimax models. It proposes minimax un- learning step consisting total Hessian- based complete Newton update and the Gaussian mechanism borrowed from differential privacy. To obtain the unlearning certification, our method injects calibrated Gaussian noises by carefully analyzing the "sensitivity" of the minimax unlearning step (i.e., the closeness between the variables). We derive
minimax unlearning variables and the the generalization rates in terms of population strong and weak primal-dual risk for three different cases loss functions, i.e., (strongly-)convex-ee losses. We also provide the deletion capacity guarantee that desired popula- tion risk can be maintained as long as the number of deleted samples does not exceed the derived amount. With training samples and model dimension d, it yields the order (n/d//1), which shows strict gap over the baseline method of differentially private minimax learning that has O(n/dl /22) In addition, rates generalization and deletion capacity match the state-of-the-an results derived previously for standard statistical learning models.
concave
Introduction
Minimax models have been widely applied in a variety of machine learning applications, including generative adversarial networks Goodffllow et al., [014]]Aroovss et al. [017]] adversarially robust learning Madry et al. 2018 [Sinha al.) 2018). and reinforcement learning (Du al. 2017 Dai et al. 2018). This is largely credited to the two-variable (i.e., primal and dual variables) model structure of minimax models, which is versatile enough to accommodate such diverse instantiations. As is common in machine learning practice, training successful minimax model relies crucially on a potentially large corpus of training samples that are contributed by users. This raises privacy concerns for minimax models. Unlike standard statistical learning (STL) models, the privacy studies for minimax models are relatively newer. Most the existing studies focus on privacy protection during the training phase under the differential privacy (DP) notion (Dwork et al. (0066] and federated minimax learning settings [Sharma et al., 2022). Recent works in this direction have successfully achieved several optimal generalization performances measured in terms of the population primal-
37th Conference on Neural Information Processing Systems (NeurIPS 2023).

---

Table 1: Summary of Results. Here (S)C means (strongly- Joonvex loss function, and (S)C-(SJC means (strongly- jconvex-(stronlyy Jooonn/ loss function, PD means Primal- Daaal. nu is the number of training samples and d is the model dimension.
Model
Unlearning Algorithm
Setting
Generalization Mcasure
Delction Capacity
DP-based
C
Population Excess Risk
((n/d//2)
STL
Bassily et al.
2019
[Sekhari et al. 2021
Sekhari et al.
2021
(S)C
O(n///4)
DP-based
SC-SC
Zhang et al.
2022a
Population Strong
(n//d//2)
Minimax
DP-bbaeed
PD Risk
C-C
Learning
Bassily et al.
2023
Population Weak or Strong PD Risk
Our Work
(S)C-(S)C
O(n/d2/4)
dual (PD) risk for DP minimax models specifically YYang et al. 2022 Zhang et al. 2022a Bassily
et al. 2023 Boob and Guzmán 2023].
Machine unlearning is an emerging privacy-respecting problem concerning Already-trainee models
(i.c.. during the post-training phase) [Cao and Yang. 2015 Guo et al., 20200 /Sekhari et al. 2021
Graves et al. 2021 Bourtoule et al. 202 Li et al. 202 Shibata al.) 202 Wu et al. 2022
Cheng et al. 2023 Chen et al., [223 Tarun et al. 2023 Wu et al. 2023 Ghazi et al. 2023
Wang
al. 2023b That is, it removes certain training samples from the trained model upon their users'
data deletion requests. It is driven by the right to be forgotten, which is mandated by a growing number of user data protection legislations enacted in recent years. Prominent examples include the
European Union's General Data Protection Regulation (GDPR) [Mantelero] [013), 2013)) the California Consumer Privacy Act (CCPA), and Canada's 's proposed Consumer Privacy Protection Act (CPPA). Machine unlearning comes with several desiderata. Besides sufficiently removing the influence of the data being deleted, it should be efficient and avoid the prohibitive computational cost of the baseline method to fully retrain the model the remaining dataset from scratch. To guarantee the sufficiency of data removal, there are exact machine unlearning methods (Cao and Yang [0113] Ginart
et al. 2019 Brophy and Lowd 2021 Bourtoule et al.
et al. [222]] [Schelter et al. [2021 Xia et al. 2023] and approximate machine
Chen et al.
2022b a Yan et al. |002 Di et al. [2023
unlearning methods Golatkar et al. 2020al Wu et al.
2020 Golatkar et al., 2020b Nguyen et al.
2020
Neel et al. 2021 Peste et al. 2021
Golatkar et al.
2021
Warnecke et [023 Izzo et al.
2021
Mahadevan and Mathioudakis]
2021
Mehta al.
2022
Zhang et al.) 2022c Wang al.
2023a
Chien et al.) 2023a Lin et al.
2023
(some can ofter the rigorous (c, 0) -certification [Guo
al.
2020, Sekhari et al.
2021 Suriyakumar and Wilson 2022 Chien al. 2023b inspired by
differential privacy). In addition, recent studies also point out the importance of understanding the relationship between the generalization performance and the amount of deleted samples [[eekhari]
ct al. 1 Suriyakumar and Wilson| 2022]. In particular, they introduce the definition of deletion capacity to formally quantify the number of samples that can be deleted for the after-unlearning model to maintain designated population risk. However, most existing works so far have focused on machine unlearning for standard statistical learning models with one variable, which leaves unknown how to design minimax unlearning method to meet all the desiderata above.
Machine unlearning for minimax models becomes a pressing problem because the trained minimax models also have a heavy reliance on the training data, while the users contributing data are granted the right to be forgotten. In this paper, we study the machine unlearning problem for minimax models under the (e, ---ertfie machine unlearning framework. We collect in Table I the results in this paper and comparisons with baseline methods that are adapted from previous papers to (e, 8) -eertified machine unlearning.
Our main contributions can be summarized as follows.
Certified minimax unlearning algorithm: We develop (c, d)-ceriffied minimax unlearning algorithm under the setting of the strongly-convex--sronyyyy -conccyooooo loss function. To sufficiently remove the data influence, the algorithm introduces the total Hessian consisting of both direct Hessian and indirect Hessian, where the latter is crucial to account for the inter-dependence between the primal and dual variables in minimax models, It leads to the complete Newton- based minimax

---

unlearning update. Subsequently, we introduce the Gaussian mechanism from DP to achieve the (c, 6)-minimax unlearning certification, which requires careful analysis for the closeness between the complete Newton updated variables and the retraining-from-seratce from-scratch variables.
Generalization: We provide generalization results for our certified minimax unlearning algorithm in terms of the population weak and strong primal-dual risk, which is a common generalization measure for minimax models.
Deletion capacity: We establish the deletion capacity result, which guarantees that our unlearning algorithm can retain the generalization rates for up to (n/dd//4) deleted samples. It matches the state-of fofte-oo-thh--ae ahe result under the STL unlearning setting that can be regarded special case of our minimax setting.
We extend the certified minimax unlearning to more general loss functions, including convex-coneawe losses, and provide the corresponding (c, 6) certifiicat, population primal-dual risk, and deletion capacity results.
Extension to more general losses:
waanngllycovex--ooneeee and convex-strongly-conece
Extension with better efficiency; We develop more computationally efficient extension, which can also support successive and online deletion requests. It saves the re-computation of the total Hessian matrix during the unlearning phase, where the minimax unlearning update can be regarded as a total Hessian based infinitesimal jackknife. It also comes with slightly smaller population primal-dual risk though the overall rates of the risk and deletion capacity remain the same.
2 Related work
Machine unlearning receives increasing research attention in recent years, mainly due to the growing concerns about the privacy of user data that are utilized for machine learning model training. Since the earliest work by Cao and Yang] (2015). a variety of machine unlearning methods have been proposed, which can be roughly divided into two categories: exact unlearning and approximate unlearning.
Exact machine unlearning. Methods for exact machine unlearning aim to produce models that perform identically the models retrained from scratch. Some exact unlearning methods are designed for specific machine learning models like k-means clustering Ginart et al. 2019] and random forests (Brophy and Lowd, 202T). SISA [Bourtoule et al., [021] proposes general exact unlearning framework based on sharding and slicing the training data into multiple non-overe non-overlapping shards and
training independently on each shard. During unlearning, SISA retrains only on the shards containing
the data to be removed. GraphEraser [Chen et al. 20226) and RecEraser (Chen et al.] 2022a further extend SISA to unlearning for graph neural networks and recommendation systems, respectively.
Approximate machine unlearning. Approximate machine unlearning methods propose to make tradeoff between the exactness in data removal and computationna//memrry efficiency. Prior works propose diverse ways to update the model parameter and offer different types of unlearning certification. When it comes to the unlearning update, many existing works consider the Newton update-related unlearning step where the Hessian matrix of the loss function plays a key role [uoo
al. 2020 Golatkar et al. 2020a Peste et al., 2021 Sekhari et al. 2021 Golatkar et al., 202
Mahadevan and Mathioudakis 2021
Suriyakumar and Wilson 2022 Mehta et al. 2022 Chien et al.
2023b]. This unlearning update is motivated by influence functions Koh and Liang] 2017 J. order
to alleviate the computation of the Hessian, Golatkar et al. [2020a] and Peste et al. [2021] utilize
Fisher Information Matrix to approximate the Hessian, mitigating its expensive computation and inversion. Mehta et al. [2022) provide a variant of conditional independence coefficient to select sufficient sets for unlcarning, avoiding the need to invert the entire Hessian matrix. ML-forgetting [Golatkar et al.) 202 trains a linear weights set the core dataset which would not change by standard training and a linear weights set on the user dataset containing data to be forgotten. They use an optimization problem to approximate the forgetting Newton update. [Suriyakumar and Wilson [002] leverage the proximal infinitesimal jackknife as the unlearning step in order to be applied to nonsmooth loss functions. In addition, they can achieve better computational efficiency and are capable of dealing with online delete requests. There are also many other designs achieving different degrees of speedup (Wu et al. 2020 Nguyen al. 2020 Neel et al. 2021 Zhang et al. 2022c
Apart from the various designs for the unlearning update, there are also different definitions of certified machine unlearning. Early works like Guo et al. [2000] introduce certified data-removal
3

---

mechanism that adds random perturbations to the loss function at training time. Golatkar et al. [020a] introduce an information-ther theoretic-basee certified unlearning notion and also add random noise to ensure the certification, which is specific to the Fisher Information Matrix and not general enough. More recently, Sekhari et al. [022]] propose the (e, 6) -certified machine unlearning definition that does not require introducing additional randomization during training. More essential, [Sekhari] ct al. [221]] points out the importance of providing the generalization performance after machine unlearning. Sekhari et al. 2.21], Suriyakumar and Wilson] [0022] establish the generalization result in terms of the population risk and derive the deletion capacity guarantee.
However, most of existing works only consider machine unlearning for STL models that minimize a single variable. None of the prior works provide certified machine unlearning pertaining to minimax models, for which the generalization and deletion capacity guarantees are still unknown.
3 Preliminaries and Baseline Solution
3.1 Minimax Learning
The goal of minimax learning is to optimize the population loss F(W, given by
min max F(w, v) [E, wEW WEV
(1)
where f: x R is the loss function, E E is a data instance from the distribution D, W C Rdi and V C TR are closed convex domains with regard to primal and dual variables, respectively. Since the data distribution 'D is unknown in practice, minimax learning turns to optimize the empirical loss Fs(ws (w,, v), given by.
min max Fs(w, v) = Σ (ww.v:2) 1=1
NEW NEV
where S (21, 3 is the training dataset with 2; D.
We will consider L-Lipschitz, Ê-smooth and pw -u--stronglycooveex stsrree----stongyy-oooooe loss functions, which are described in Assumption [xriioonneeeWeo and more details can be found in Appendix A
Assumption 1. For any 2 E 2, the function fw,, v) is L--Lipschitz and with E-Lipschitz gradients and p-Lipschitz Hessians the closed convex domain W x V. Moreover, f(w, (w: is convex W for any V E V and concave on V for any w E W.
Assumption 2. For any z E Z, the function f(w,v; satisfies Assumtion [nd f(w, 11; 2) is Mw stronnyy convex on W for any v E V and fu-Strongly concave on V for any w E W.
Denote randomized minimax learning algorithm by A 2n W x V and its trained variables by A(S) = (Aw (S), (S)) E W x V. The generalization performance is a top concern of the trained model variables (S), (8)) (Thekumparampil et al. 2019 Zhang et al. 2020 Lei et al. 2021 Farnia and Ozdaglar 2021 ZZhang et al. 2021] 2022b Ozdaglar el al.) 2022]. which can be measured by population weak primal-dual (PD) risk or population strong PD risk, as formalized below.
Definition 1 (Population Primal-Dual (PD) Risk). The population weak PD) risk of A(S),
A (Aw(()) (S)) and the population strong PD risk of A(S), (Aw AS)) are defined as w) min E(F (S))).
A A (A,(S), = max wEV
weW
(3)
A (S). E|max F (S), min F(w, Av()) wEW
Notations. We introduce the following notations that will be used in the sequel. For a twice differentiable function with the arguments w W and v E V. we use V and V, denote the direct gradient of f w.r.t. w and v, respectively and denote its Jacobian matrix as vf= [V Vurfl. We use Oww.f. f. Owerf f. Our.f denote the second order partial derivatives w.r.t. w and v, correspondingly and denote its Hessian matrix as 2 = 18ww Owuf: the total Hessian of the function ʃ w.r.t. w and D: Dww. := Oww! Dwvl -0. 00ww and D := Ovvl- Oewl 0mbl Sww.s where 0yrl and 0-1 are the shorthand of (8vv)(-))- and (Sww (Oww/()) respectively, when J and aww/ ʃ are invertible. We also use the shorthand notation V Vwf fw pi 2) = Vwf(w, 21, 2l Ww
We define

---

3.2 (c, (e.e)-Cet Machine Unlearning
An unlearning algorithm A for minimax models receives the output of minimax learning algorithm A(S), the set of delete requests U _ S and some additional memory variables T(S) E T as input (U, T(S)), AU, A(S), T())) E W V. aiming to remove the influence of U. For the memory variables in (SS). it will not contain the entire training set, but instead its size [7(5) is independent of the training data size n. The mapping of an unlearning algorithm can be formulated as A 2 x W x V x T + W x V. We now give the notion of (c. (..)) 5)-cetiff unlearning introduced by Sekhari et al. 2021 which inspired by the definition of differential privacy (Dwork et al. 2006].
and returns an updated model (w" 1/
Definition 2 ((e, 8--Cetiff Unlearning (Sekhari et al. 2021 )) Let θ be the domain of W x V. For all S of size set of delete requests U C such that [0T S m, the pair of learning algorithu A and unlearning algorithm A is (c,6) -ceetiffe unlearning, i0 C O and c, 8 > 0, the following two conditions are satisfied:
E Pr[A(U, A(S), T(S)) EO) e Pr[A(0, A(S T(SU)) +
(4)
Pr[A(0, UU) ((SUU) E 5 Pr[A(U, A(S), E E 6,
(5)
where 9 denotes the empty set and (S) denotes the memory variables available to A.
The above definition ensures the indistinguishability between the output distribution of (i) the model trained on the set and then unlearned with delete requests U and (ii) the model trained on the set S and then unlcarned with an empty set. Specifically, the unlearning algorithm simply adds perturbations to the output of US)) when the set of delete requests is empty.
Deletion Capacity Under the definition of certified unlearning, Sekhari et al. 2021 introduce the definition of deletion capacity, which formalizes how many samples can be deleted while still maintaining good guarantees on test loss. Here, we utilize the population primal-dual risk defined in Definition ! jinstead of the excess population risk utilized for STL models.
Definition 3 (Deletion capacity, (Sekhari et al. 2021J. Let E, > and S be a dataset of size drawn ii.d from the data distribution D. Let Flw,, v) be a minimax model and U be the set of deletion requests. For a pair of minimax learning algorithm A and minimax unlearning algorithm A that satisfies (c, 6uunleannnng,, the deletion capacity m (d1, d2, n) is defined as the maximum number of samples U that can be unlearned while still ensuring the population primal-duct (weak PD or strong PD) risk is at most 7, Let the expectation [E[-] takes over ~ Dn and the outputs of the algorithmss A and A. Let di denotes the dimension of domain W and d2 denotes the dimension of domain V. specifically,
A.A me,b,, (di, d2, n) == max {m/4 (U,) A(S) T(S)) S7),
(6)
where the ouputs (U, ((S)(()) and A, AUS), of the minimax unlearning algorithm À refer to parameter w and v, respectively. A (U, T(S)), (U,A(()) T(S)) could be the population weak PD risk or population strong PD risk of A(U, A(S),T(S))
We set = 0.01 (or any other small arbitrary constant) throughout the paper.
3.3 Baseline Solution: Certified Minimax Unlearning via Differential Privacy
Since Definition 2 is motivated by differential privacy (DP), it is natural way to tools from DP for machine unlearning. For a differentially private learning algorithm with edit distance m in neighboring datasets, the unlearning algorithm A simply returns its output A(S) without any changes and is independent of the delete requests U as well as the memory variables T(S), i.e., A(S).
A(U, A(S),
number of differentially private minimax learning algorithms can be applied, e.g., Zhang al.) [2022a] Yang et al. [2022), Bassily et al. [2023). For instance, we can obtain the output A(S) (S), Ap (S)) by calling Algorithm 3 Zhang et (2022a). Under Assumption 2 we then
get the population strong PD risk based on [hhang et al. 2022a Theorem 4.3] and the group privacy
property DP |Vadhan 2017 Lemma 7.2.2], as follows.
?
m2 nx2x dlloolgmm
(S) A)()) = -
+
(7)
un²e2
5

---

where we let μ min(pes Hyn K = e/p, d = max fd1. d2), and m be the edit distance between datasets (i.e., the original dataset and the remaining dataset after removing samples be forgotten).
The algorithm A satisfies (c, for any set U C SSo of size m. that is,
Pr[A(S) E 0] $ e² Pr(A(SUU) E
and Pr(A(S(U) E cO Pr(A(S) E O]+ + 6.
Since we have A(S) = A(U, A(S), and A(SAU) = A(O, A(S(U),T(SVU)) the above privacy guarantee can be converted to the minimax unlearning guarantee in Definition 2 implying that the pair (A, A) is (e, -eertifee minimax unlearning. According to Definition the population strong PD risk in eq. 7 yields the following bound deletion capacity.
Theorem 1 (Deletion capacity of unlearning via DP (Sekhari et al., 2021]. Denote d =
max(ds (d1, dz). There exists polynomial time learning algorithm and unlearning algorithm A for minimax problem of the form A(S) A(S) such that the deletion capacity is:
m A.A (, d2, n) 2 Ω
TE
(8)
Vdlog(es/0
where the constant in I-notation depends on the properties of the loss function f (e.g., strongly convexity and strongly concavity parameters, Lipchitz continuity and smoothness parameters).
However, this DP minimax learning baseline approach provides inferior deletion capacity. In the following sections, we show that the d'/2 in the denominator of eq. can be further reduced to d'/4,
4 Certified Minimax Unlearning
In this section, we focus on the setting of the brrongly-conveexstrrnn--oooo provide the intuition for the design of the minimax unlearning step in Sec|4.1. then provide the formal algorithm in Sec (.2 and a more efficient extension in Sec Sec 4.3 with analysis of minimax unlearning certification, generalization result, and deletion capacity in See 4.4 We will provide extensions to more general loss settings in S The proofs for the theorems presented in this and the next sections
loss function. We first
can be found in Appendix B and respectively.
4.1 Intuition for Minimax Unlearning Update
To begin with, we provide an informal derivation for minimax unlearning update to illustrate its design intuition. Given the training set of size and the deletion subset S S of size m, the aim is to approximate the optimal solution (wis (x) of the loss Esx (w, v) on the remaining dataset S \ U, given by.
(W V == arg min max F (w. = 1
Σ f(w.v;2)). BESIU
(9)
WEW wey
m
Meanwhile, we have the optimal solution (ws. vz) to the original loss Fs(w, v) after mini- max learning. Taking unlearning for instance, by using first-order Taylor expansion for V Vw FuFFs(Wsr = around (w'. vz), we have
Fs (w5, v8)) + Swn Fst (w., (w5) -w²) + Fur (w', (3) - -V3) =0
(10)
Since wis is a minimizer of Fs(w, from the first-order optimality condition, we can get Vw (Wg vz) - n-m Enso [wl( uš: z.). Now given an auxiliary function Vsn (w) =
Aigmaxyev Fs (w,v) (more best response auxiliary functions are introduced in Appendix A Defi- nition 8) we have V Vev (Vi(w))) ). We further get
v = [Vsi (w)r: )- - Vs (w3g) + (w3z - nÿ]
@ Vsi (w+)) - V. (w3z) (6) dVs>> (w)
)=wm) ) (w/z) - w
dw
(11)
(mi) - F' (W3z vz)) Bew Esy (wis, vz) (w) wW²),

---

where the approximate equation (i) leaving out the term [V (w3) Sšl which is bounded in Appendix A Lemma 2 and does not affect the overall unlearning guarantee. The approximate
equation (it) is the linear approximation step and is the response Jacobian of the auxiliary function Vs (w). The approximate equation (iii) is due to the implicit function theorem. This gives that
Fww (w') (w)( -w3) + Fsi (w3, (V)) - = = Dww Fsy (W3, (w) -W3), (12)
which implies the following approximation of wgy
wis R w/s
1 m Dwwwf (w's v3)!
Σ
Vuf(w,
(13)
2.EU
The above informal derivation indicates that the minimax unlcarning update relies on the total
Hessian to sufficiently remove the data influence (Liu et al. 2023 Zhang ct al.] 2023 rather than
the conventional Hessian that appears in standard statistical unlearning [uo et al. 2020 Sekhari et al. 2021 Suriyakumar and Wilson 2022 Mehta et al., 2022] The update in eq. eq. has close relation to the complete Newton step in the second-order minimax optimization literature (Zhag al. 2020], which motivates the complete Newton-based minimax unlearning. However, due to the various approximations in the above informal derivation, we cannot have certified minimax unlearning guarantee. Below, will formally derive the upper bound for these approximations in the closeness upper bound analysis. Based on the closeness upper bound, we will introduce the Gaussian mechanism to yield distribution indistinguishably result in the sense of (e, 6) -eertifie minimax unlearning
4.2 Proposed Certified Minimax Unlearning
We first provide algorithms under the setting of the smooth and stonglyyconvar--tonoyyyooone (SC-SC) loss function as described in Assumptions 2
Algorithm Minimax Learning Algorithm (Asc-sc) sc)
Input:
Dataset : f2 ~ D", , loss function: f(w, 2;2).
I: Compute
(w's, v/) +- arg min max Fs(ww v) f(w, v2)
(14)
v
Output:
(w's, vz. Dwo Fs(ww; vis,, Dew Fis (w).vz))
Algorithm 2 Certified Minimax Unlearning for Strongly-Convex Convex- Convex-Stronglly Attongly-Conceet Loss (Asc-se)
Input: Delete requests U : { C S, output of Asc-ec (S): (w3, vš), memory variables T(S):
[Dww Fs(wss U3),, Duu Fs (wog v/s) loss function: f(w, v;; 2), noise parametens: a1, 02
I: Compute
Dww Fsr (wbs =
nDwu Fs(ws,
Σ 21EV
Duwf
(15)
n m
D Dyu Fsi (3s((s.)3) m
Fs Σ
Dowf (w3
(16)
z.EU
2: Define
Wg +
Dww Fs: v$)
Vwf v3:2))
(17)
m
D = Vš
Dev Fst (wā) =3))
Σ
Ves(ws, uš: 2))
(18)
n m
2.EU
3: w 3 Ei, where &1 ~ (N(0,021a,) and nd D Ez, where &, AN
Output: ".")

---

Minimax Learning algorithm. We denote our learning algorithm by Asc-sc and the pseudocode shown in Algorithm I Given a dataset S = {2]]== of size n drawn independently from some distribution D, algorithm Ase-se computes the optimal solution V²) to the empirical risk Fs Fs(w, v). Ase-se se then outputs the point (wi. v5) as well as the additional memory variables T(S) := Fsw's, v²), Dav (s v5)}, which computes and stores the total Hessian of Fs(w, v) at (3).
Minimax Unlearning Algorithm We denote the proposed certified minimax unlearning algorithm by Asc-se and present its pseudocode in Algorithm 2 Algorithm Ase-se takes the following inputs: the set of delete requests U {2 of size m, the trained minimax model (w3, P3), and the memory variables T(S). To have the certified minimax unlearning for w, eq. 15) computes the - Exeu / s =z), where the
total Hessian of Fs (W3, UŠ) by - (ws V3)) a-m
former term can be retrieved from the memory set and the latter is computed on the samples to be deleted; eq. 17) computes the intermediate @ by the complete Newton step based on the total Hessian Duw Fs. (W'. Vÿ)); Line 3 injects calibrated Gaussian noise & to ensure (c, 6) -certiffed minimax unlearning. The certified minimax unlearning for v is symmetric. We provide detailed analysis for Algorithm 2 including minimax unlearning certification, generalization results, and deletion capacity
in Appendix B.I
4.3 Certified Minimax Unlearning without Total Hessian Re-computation
We extend Algorithm 2 and propose Algorithm 3 to reduce the computational cost of Algorithm
2) The complete Newton steps in eq. and eq. 20) utilize the total Hessian I's M/3) and Fsw's s: vs) that are directly retrieved from the memory, rather than the updated total Hessian Duw Fss (ws. vS)) and Dup (wg. v/)) used in Algorithm 2 The form in eq.(19) and eq. (20) can also be regarded as the total Hessian extension of the infinitesimal jackknife. In this way, it gets rid of the computationally demanding part of rv-elaluating the total Hessian for samples to be deleted. which significantly reduces the computational cost. It turns out to be the same computational complexity as the state-of-the-arr certified unlearning method developed for STL models (Suriyakuuaa and Wilson 3 can be more appealing for the successive data deletion setting.
2022). Moreover, Algorithm
Algorithm 3 Efficient Certified Minimax Unlearning (Aetricient)
Input: Delete requests U : [ S S. output of AS)= (wi. v$)), memory variables T(S): (Dww (s(ws; Dou Iis (wog, }. loss function: S(w, v; 2), noise parameters: 0i, 02.
I: Compute
ت w +
Fwf(wss
(19)
Dov Fsl w$))
Σ
V.f(ws, uš: 2))
(20)
ZEE
2: 86 = #+ + E1. where & ~ o10, and D= = =D+ Ez. where & ~ (((0,
Output: (w0 ).").
4.4 Analysis for Algorithm
3
(e, 8)- -Crrtifficated Unlearning Guarantee. The intermediate variables (ū3 D) are distinguishable in distribution from the retraining-from-sereee from-scratch variables (w s)) because they are deterministic and the Taylor expansion introduces a certain amount of approximation. The following lemma quantifies the closeness between (w, D) and (w3r, M')), which can be regarded as the "sensitivity" when applying the Gaussian mechanism.
Lemma 1 (Closeness Upper Bound). Suppose the loss function f satisfies Assumption 7 Hand 2
m3)]] 2 plv. Let μ = min (pw Pv. Huow Pvvi Then, we have the closeness bound between (w, in Line of Algorithm 3 and (wg Vggi
[|Dww Fs(w", v/3)l 2 Pow and
v/g in eq.
(8V512 p/1/ +2 22/2L22 2222L2/12))m
flw 1w -11 <
(21)
n²
8

---

Equipped with Lemmall 1 we have the following certified unlearning guarantee by adding Gaussian noise calibrated according the above closeness result. Due to the minimax structure, our analysis is more involved than the STL case [Sekhari et al. 2021 Suriyakumar and Wilson 2022].
Theorem 2 ((e, Minimmxx Unlearning Certification). Under the same settings of Lemmal our
minimax learning algorithm Asc-ec and unlearning algorithm Actficient is (c, -ccettffe minimax unlearning if we choose
01 and 02 2(8v212 p/10 + 1222Le/u2) V2log(2.5/6)
(22)
n²e
Generalization Guarantee. Theorem 3 below provides the generalization result in terms of the population PD risk for the minimax unlearning algorithm Aetticient.
Theorem 3 (Population Primal-Dual Risk). Under the same settings of Lemma | and denote d = max d1, d2 the population weak and strong PD risk for the certified minimax unlearning
variables (w ( returned by Algorithm 3 3are
A"("""EE") "O0,,""'-0
(L p/u +132/17)
m² (dlog(1/0)
mL.² 2 um
n²c
(23)
A A'(W",D")) =0 (1'EPplu /2²)
m² v dlog(1/8)
mLL 2
L
n²e
pm p1
Deletion Capacity. The population weak and strong PD risk given in Theorem unlearning algorithms provides the following bound on deletion capacity.
3 for the output of
Theorem 4 (Deletion Capacity). Under the same settings of Lemma 1 and denote d = max(d1, d2). the deletion capacity of Algorithm iis
nye
A.A m me,5. (d1,d2.n) n) 2 c.
(24)
(dlog(L/0)))/4'
where the constant depends L,I, p. and a of the loss function f.
5 Certified Minimax Unlearning for Convex-Concave Loss Function
We further extend the certified minimax unlearning for the convex-conent loss function. addition, Appendix [ will provide the extension to convex-strongly-come -onccvvee and strongly-convex, convex-concave loss functions. Give the convex conexee loss function f(w, v: 2). similar to the unlearning for
STL models [Sekhari et al. 2021). we define the regularized function as f(,,v;:) = f(w, v;
1 - 11 Suppose the function / satisfies Assumption | then the function i' X-strongly convex in w, >-strongly concave in v, (2L+ ||||||||| + + and p-Hessian Lipschitz. It suffices to apply the minimax learning and unlearning algorithms in Sec to the regularized loss function with a properly chosen X. We denote the learning and unlearning algorithms for convex-concave losses as Ac-c and Ac-c- Their implementation details are given in Appendix C We suppose the SC-SC regularization parameter À satisfies < f. Theorem below summarizes guarantees of (e, -eertifie unlearning and population primal-dual risk (weak and strong) for Algorithm Ac-c-
V2(26+ A) -gradient Lipsehitz
Theorem 5. Let Assumption holld and d = maxfd1, d2}. Suppose the parameter spaces W and V are bounded so that maxwew |اه|| < Bu and maxvev ||||| S By. We have,
(a) (e. 8)-Minimax Unlearning Certification: Our minimax learning algorithm Ac-o and unlearn- ing algorithm A is (cer)-cet minimax unlearning.
(w",v") (b) Population Weak PD Risk: The population weak PD risk for (w v²)) by algorithm Ac-e is
AW ,²)) S o ( 128/22). m² /d2o/log(1/8) mI?
An + x(B2 + +B²) (25)
n?e
In particular, by setting X below
A max
L
T
[.2 m² / (1/0
1/4 E pmi /dlog(1/0)
1/7
(26)
VBL + BB
(B2 + B2)
(B2 BB nr²

---

we have the following population weak PD risk,
m Th + oz (1) 1/8 (000))0((()) (V
m Vn cal ( ( yu (27)
("w""v")
n
where 01, C22 C3 are constants that depend only on L, 1. p, Bu and By
(c) Population Strong PD Risk: The population strong PD risk for (w" (w", ) by algorithm Ac-c is
v""""""") 2 (L' (
m² /
mL2 LL A(B + -B ) (28)
n²t
An
Nan
In particular, by setting À below
A max
m7
L (B2
BB)m )
112mm² vdlog(1/8)
v VB + BU
(B2 + BB)m²e
(29)
L pm /dlog(1//)
1/7
(B + BB
we have the following population strong PD risk,
A' v" S 100((0))) c
(log(110))
1/8
m
+ cs /dlog(1/0)
)07
1/7 m y2/7
+ cc
Vn +
cs
22
V
(30)
where C12 C22 C32 C4 are constants that depend only on L, L p. Bw and Bu.
(d) Deletion Capacity: The deletion capacity of Algorithm Ac-c is
myeE (dlog(1/0))//4>
A.A me,6 (d1, d2, n) 2 c.
(31)
where the constant e depends on the constants L, 1, Bw and By,
6 Conclusion
In this paper, we have studied the certified machine unlearning for minimax models with a focus on the generalization rates and deletion capacity, while existing works in this area largely focus standard statistical learning models. We have provided a new minimax unlcarning algorithm composed of the total Hessian- complete Newton update and the Gaussian mechanism-based perturbation, which comes with rigorous (c, -unlearnnn certification. We have established generalization results in terms of the population weak and strong primal-dual risk and the correspondingly defined deletion loss functions, both which match the
capacity results for the strongly-conve wetell--oovex-stronsnee state-of-te the-art results obtained for standard statistical learning models. We have also provided extensions to other loss types like the convex-concave loss function. In addition, we have provided a more computationally efficient extension by getting rid of the total Hessian re-computation during the minimax unlearning phase, which can be more appealing for the successive data deletion setting. Although our bound for deletion capacity is better than that of DP by an order of d and matches the state-of-the-an result established for unlearning under the STL setting, it remains unclear whether this bound is tight or not. In future work, we plan to extend to more general settings like the nonconvex-nonconeanv loss function setting.
Acknowledgments and Disclosure of Funding
We would like to thank Gautam Kamath for his valuable comments on the presentation of the results in the previous version of the paper. Additionally, we extend our thanks to the reviewers and area chair of NeurlPS 2023 for their constructive comments and feedback. This work was supported in part by the National Natural Science Foundation of China (62072395, 62206207, 78) and the National Key Research and Development Program of China (2020AAA0107700, 202 YFB3 100300).
10

---

References
Martin Arjovsky, Soumith Chintala, and Léon Bottou. Wasserstein generative adversarial networks. In International conference machine learning, volume 70, pages 214-223. PMLR, 2017.
Raef Bassily, Vitaly Feldman, Kunal Talwar, and Abhradeep Guha Thakurta. Private stochastic convex optimization with optimal rates. Advances Neural Information Processing Systems, volume 32, pages 11279-1 128,, 2019.
Raef Bassily, Cristóbal Guzmán, and Michael Menart. Differentially private algorithms for the stochastic saddle point problem with optimal rates for the strong gap. In Conference on Learning Theory, volume 195, pages 2482-2508. PMLR, 2023.
Digvijay Boob and Cristóbal Guzmán. Optimal algorithms for differentially private stochastic monotone variational inequalities and saddle-point problems. Mathematical Programming, pages 1-43, 2023.
Lucas Bourtoule, Varun Chandrasekaran, Christopherr A Progueette-hhoo Hengrui Jia, Adelin Travers, Baiwu Zhang. David Lie, and Nicolas Papernot. Machine unlearning. 2021 IEEE Symposium on Security and Privacy, pages 141-159. IEEE, 2021.
Jonathan Brophy and Daniel Lowd. Machine unlearning for random forests. In International Conference on Machine Learning, volume 139, pages 1092-1104. PMLR, 2021.
Yinzhi Cao and Junfeng Yang. Towards making systems forget with machine unlearning. In 2015 IEEE symposium on security and privacy, pages 463-480. IEEE, 2015.
Chong Chen, Fei Sun, Min Zhang, and Bolin Ding. Recommendation unlearning. In Proceedings of the ACM Web Conference 2022, pages 2768-2777. ACM, 2022a.
Min Chen, Zhikun Zhang, Tianhao Wang, Michael Backes, Mathias Humbert, and Yang Zhang. Graph unlearning. In Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Securit, pages 499-513. ACM, 2022b.
Min Chen, Weizhuo Gao, Gaoyang Liu, Kai Peng, and Chen Wang. Boundary unlearning: Rapid forgetting deep networks via shifting the decision boundary. In Proceedings of the IÉEE/CVF Conference on Computer Vision and Patlern Recognition, pages 7766-7775. IEEE, 2023.
Jiali Cheng, George Dasoulas, Huan He, Chirag Agarwal, and Marinka Zitnik. Gnndelete: A general strategy for unlearning in graph neural networks. In The Eleventh International Conference on Learning Representations. OpenReview.net, 2023.
Eli Chien, Chao Pan, and Olgica Milenkovic. Efficient model updates for approximate unlearning of graph-structured data. In The Eleventh International Conference on Learning Representations. OpenReview.net, 2023a.
Eli Chien, Chao Pan, and Olgica Milenkovic. Efficient model updates for approximate unlearning of graph-structured data. In The Eleventh International Conference on Learning Representations. OpenReview.net, 2023b.
Bo Dai, Albert Shaw, Lihong Li, Lin Xiao, Niao He, Zhen Liu, Jianshu Chen, and Le Song. Sbeed: Convergent reinforcement learning with nonlinear function approximation. International Conference Machine Learning, volume 80, pages 1125- 1134. PMLR, 2018.
Jimmy Z. Di, Jack Douglas, Jayadev Acharya, Gautam Kamath, and Ayush Sekhari. Hidden poison: Machine unlearning enables camouflaged poisoning attacks. In Advances in Neural Information Processing Systems, volume 37, 2023.
Simon S Du, Jianshu Chen, Lihong Li, Lin Xiao, and Dengyong Zhou. Stochastic variance reduction methods for policy evaluation. In International Conference on Machine Learning, volume 70, pages 1049-1058. PMLR, 2017.
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Third Theory of Cryptography Conference, volume 3876, pages 265-284. Springer, 2006.
11

---

Cynthia Dwork, Aaron Roth, et al. The algorithmic foundations of differential privacy. Foundations and Trends Theoretical Computer Science, 9:211-407, 2014.
Farzan Farnia and Asuman Ozdaglar. Train simultaneously, generalize better: Stability of gradient- based minimax learners. In International Conference on Machine Learning, volume 139, pages 3174-3185, PMLR, 2021.
Badih Ghazi, Pritish Kamath, Ravi Kumar, Pasin Manurangsi, Ayush Sekhari, and Chiyuan Zhang. Ticketed
schemes. In The Thirty Sixth Annual Conference on Learning Theory, pages 51 0139. PMLR, 2023.
Antonio Ginart, Melody Guan, Gregory Valiant, and James Y Zou. Making ai forget you: Data deletion in machine learning. In Advances in neurul information processing systems, volume 32, pages 3513-3526, 2019.
Aditya Golatkar, Alessandro Achille, and Stefano Soatto. Eternal sunshine of the spotless net: Selective forgetting deep networks. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pullern Recognition, pages 9304-9312, 2020a.
Aditya Golatkar, Alessandro Achille, and Stefano Soatto. Forgetting outside the box: Scrubbing deep networks of information accessible from input-output observations. In Computer Vision-ECCV 2020: 16th European Conference, volume 12374, pages 383-398. Springer, 2020b.
Aditya Golatkar, Alessandro Achille, Avinash Ravichandran, Marzia Polito, and Stefano Soatto. Mixed-privacy forgetting in deep networks. In Proceedingy of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 792-801. IEEE, 2021.
Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville. and Yoshua Bengio. Generative adversarial nets. In Advances in Neural Information Processing Systems, volume 27, pages 2672-2680, 2014.
Laura Graves, Vineel Nagisetty, and Vijay Ganesh. Amnesiac machine learning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 11516-11524, AAAI Press, 2021.
Chuan Guo, Tom Goldstein, Awni Hannun, and Laurens Van Der Maaten. Certified data removal from machine learning models. In International Conference on Machine Learning, volume I 119, pages 3832-3842. PMLR, 2020.
Zachary Izzo, Mary Anne Smart, Kamalika Chaudhuri, and James Zou. Approximate data deletion from machine learning models. In International Conference on Artificial intelligence and Statistics, volume 130, pages 2008-2016. PMLR, 2021.
Pang Wei Koh and Percy Liang, Understanding black-box predictions via influence functions. In International Conference on Machine Learning, volume 70, pages 1885-1894. PMLR, 2017.
Yunwen Lei, Zhenhuan Yang, Tianbao Yang, and Yiming Ying. Stability and generalization of stochastic gradient methods for minimax problems. In International Conference on Machine Learning, volume 139, pages 6175-616 6186. PMLR, 2021.
Yuantong Li. Chi-Hua Wang, and Guang Cheng. Online forgetting process for linear regression models. In International Conference on Artificial Intelligence and Statistics, pages 217-225. PMLR, 2021.
Shen Lin, Xiaoyu Zhang, Chenyang Chen, Xiaofeng Chen, and Willy Susilo. Erm-ktp: Knowledge- level machine unlearning via knowledge transfer. In Proceedings of the IEEE/CVE Conference on Computer Vision and Patlern Recognition, pages 20147-20155, 2023.
Tianyi Lin, Chi Jin, and Michael Jordan. On gradient descent ascent for nonconvex-concave minimax problems. In International Conference on Machine Learning, volume 119, pages 6083-6093. PMLR, 2020.
Junxu Liu, Mingsheng Xue, Jian Lou, Xiaoyu Zhang, Li Xiong, and Zhan Qin. Muter: Machine unlearning on adversarially trained models. Proceedings of the IEFF/CVE International Conference Computer Vision, pages 4892-4902, 2023.
12

---

Luo Luo, Yujun Li, and Cheng Chen. Finding second-ords stationary points in nonconvex sonconyex--tronnlyy concave minimax optimization. Advances Neural Information Processing Systems, volume 35, pages 36667-36679, 2022.
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. In The Sixth International Conference on Learning Representations. OpenReview.net, 2018.
Ananth Mahadevan and Michael Mathioudakis. Certifiable machine unlearning for linear models. arXiv preprini arXiv: 2066. 5093, 2021.
Alessandro Mantelero. The eu proposal for a general data protection regulation and the roots of the "right to be forgotten'. Computer Law & Security Review, 29(3):229-233 2013.
Ronak Mehta, Sourav Pal, Vikas Singh, and Sathya N Ravi. Deep unlearning via randomized conditionally independent hessians. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 10422-10431. IEEE, 2022.
Seth Neel, Aaron Roth, and Saeed Sharifi Malliii-ia.jjrrdi.. Descent-to-delete Gradient-based methods for machine unlearning. In Algorithmic Learning Theory, volume 132, pages 931-962. PMLR, 2021.
Yurii Nesterov and Boris T Polyak. Cubic regularization of newton method and its global performance. Mathematical Programming. 108(():177-205, 2006.
Quoc Phong Nguyen, Bryan Kian Hsiang Low, and Patrick Jaillet. Variational bayesian unlearning. 2020.
In Advances Neural Information Processing Systems, volume 33, pages
Asuman E. Ozdaglar, Sarath Pattathil, Jiawei Zhang, and Kaiqing Zhang. What is a good metric to study generalization of minimax learners? In Advances in Neural Information Processing Systems, volume 35, pages 38190-38203, 2022.
Alexandra Peste, Dan Alistarh, and Christoph H Lampert. SSSE: efficiently erasing samples from trained machine learning models. arXiv preprint arXiv:2107.0388 2021.
Sebastian Schelter, Stefan Grafberger, and Ted Dunning. Hedgecut: Maintaining randomised trees for low-latency machine unlearning. In International Conference on Management of Data, pages 1545-1557, ACM, 2021.
Ayush Sekhari, Jayadev Acharya, Gautam Kamath, and Ananda Theertha Suresh. Remember what you want to forget: Algorithms for machine unlearning. In Advances in Neural Information Processing Systems, volume 34, pages 18075-18086, 2021.
Pranay Sharma, Rohan Panda, Gauri Joshi, and Pramod Varshney. Federated minimax optimization: Improved convergence analyses and algorithms. In International Conference on Machine Learning, volume 162, pages 19683-19730 PMLR, 2022.
Takashi Shibata, Go Irie, Daiki Ikami, and Yu Mitsuzumi. Learning with selective forgetting. In Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, pages 989-996 ijcai.org, 2021.
Aman Sinha, Hongseok Namkoong, and John Duchi. Certifying some distributional robustness with principled adversarial training. The Sixth International Conference on Learning Representations. OpenReview.net, 2018
Vinith Suriyakumar and Ashia C Wilson. Algorithms that approximate data removal: New results and limitations. In Advances in Neural Information Processing Systems, volume 35, pages 18892- 18903, 2022.
Ayush K Tarun, Vikram S Chundawat, Murari Mandal, and Mohan Kankanhalli. Fast yet effective machine unlearning. IEEE Transactions on Neural Networks and Learning Systems, 2023.
Kiran K Thekumparampil, Prateek Jain, Praneeth Netrapalli, and Sewoong Oh. Efficient algorithms for smooth minimax optimization. In Advances in Neural Information Processing Systems, volume 32, pages 12659-12670, 2019.
13

---

Enayat Ullah, Tung Mai, Anup Rao, Ryan A Rossi, and Raman Arora. Machine unlearning via algorithmic stability. In Conference on Learning Theory, volume 134, pages 4126-4142. PMLR, 2021.
Salil Vadhan. The complexity of differential privacy. Tutorials on the Foundations of Cryptography: Dedicated to Oded Goldreich, pages 347-450, 2017.
Cheng-Long Wang, Mengdi Huai, and Di Wang. Inductive graph unlearning. In 32nd USENIX
Security Symposium, pages 3205-3223 USENIX Association, 2023a.
Weiqi Wang, Zhiyi Tian, Chenhan Zhang, An Liu, and Shui Yu. Bfu: Bayesian federated unlearning with parameter self-sharing. In Proceedings of the 2023 ACM Asia Conference on Computer and Communications Security, pages 567-578. ACM, 2023b.
Alexander Warnecke, Lukas Pirch, Christian Wressnegger, and Konrad Rieck. Machine unlearning of features and labels. In 30th Annual Network and Distributed System Security Symposium. The Internet Society, 2023.
Ga Wu, Masoud Hashemi, and Christopher Srinivasa. Puma: Performance unchanged model augmentation for training data removal. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36. pages 8675-8682 2022.
Yinjun Wu, Edgar Dobriban, and Susan Davidson. Deltagrad: Rapid retraining of machine learning models. In International Conference on Machine Leurning, volume 119, pages 10355-10366. PMLR, 2020.
Zhaomin Wu, Junhui Zhu, Qinbin Li, and Bingsheng He. Deltaboost: Gradient boosting decision trees with efficient machine unlearning. Proceedings of the ACM on Management of Data, 1(2): 1-26, 2023.
Haocheng Xia, Jinfei Liu, Jian Lou, Zhan Qin, Kui Ren, Yang Cao, and Li Xiong. Equitable data valuation meets the right to be forgotten in model markets. Proceedings of the VLDB Endowment, 2023.
Haonan Yan, Xiaoguang Li, Ziyao Guo, Hui Li, Fenghua Li, and Xiaodong Lin. Arcane: An efficient architecture for exact machine unlearning. In Proceedings of the Thirty-Firss International Joint Conference on Artificial Intelligence, pages 4006-4013, ijcai.org, 2022.
Zhenhuan Yang, Shu Hu, Yunwen Lei, Kush R Vashney, Siwei Lyu, and Yiming Ying. Differentially private sgda for minimax problems. In Uncertainty Artificial Intelligence, volume 180, pages 2192-2202. PMLR, 2022.
Guojun Zhang, Kaiwen Wu, Pascal Poupart, and Yaoliang Yu. Newton-type methods for minimax optimization. arXiv preprint arXiv:2006. /4592, 2020.
Junyu Zhang, Mingyi Hong, Mengdi Wang, and Shuzhong Zhang. Generalization bounds for stochastic saddle point problems. In International Conference on Artificial Intelligence and Statistics, volume 130, pages 368-57.. PMLR, 2021.
Liang Zhang, Kiran K Thekumparampil, Sewoong Oh, and Niao He. Bring your own algorithm for optimal differentially private stochastic minimax optimization. In Advances in Neural Information Processing Systems, volume 35, pages 35174-35187, 2022a.
Shuijing Zhang, Jian Lou, Li Xiong, Xiaoyu Zhang, and Jing Liu. Closed-form machine unlearning for matrix factorization. In Proceedings of the 32nd ACM International Conference on Information and Knowledge Management, pages 3278-3287, 2023.
Siqi Zhang, Yifan Hu, Liang Zhang, and Niao He. Uniform convergence and generalization for nonconvex stochastic minimax problems. In OPT 2022: Optimization for Machine Learning (NeurIPS 2022 Workshop), 2022b.
Zijie Zhang, Yang Zhou, Xin Zhao, Tianshi Che, and Lingjuan Lyu. Prompt certified machine un- learning with randomized gradient smoothing and quantization. In Advances in Neural Information Processing Systems, volume 35, pages 13433-13455, 2022c.
14

---

A Additional Definitions and Supporting Lemmas
In this section, we provide additional definitions and supporting lemmas. In the next two sections, Sec contains missing proof' in Sec and setting. Sec PeecCiioniin missing proofs in Seol] as well as detailed algorithm descriptions for the general convex-concave loss function setting.
and the online extension to support successive unlearning
A.1 Additional Definitions
We first recall the following standard definitions for the loss function [ww,2;3 from optimization literature.
Definition 4 (Function Lipschitz Continuity). The function f(w, v;2) L-Lipschitz, i.e., there exists a constant L, >> O such that for all w, w² E W, v,v' E and 2, it holds that
[ 2; - f(w', v²;2)]] (2 w'11++11u 1
(32)
Definition 5 (Gradient Lipschitz Continuity). The function fw. v:)) has E-Lipschitz gradients, i.e., there exists a constant i such that for all w. w' E,W, V. E and Z. holds that
IVf 2; v f(w,, w/:
:2)1 & w'll + 11 - 2'1)3, 1-11-(1))3)
(33)
where recall that VlW,, Vuf(w, Vuf(w,);2)
Definition (Hessian Lipsehitz Continuity). The function f'w,, vz ) has p-Lipschitz Hessian, iee, there exists constant O such that for all w, w E W, v, v' E V and E 2, it holds that
[V s(w', v²: 2)12)
p2(1w w'll |1 111,),
(34)
Tww (wo, viz)
O v;=)
where recall that 4 v2
Ovw (w,
f v;2)
Definition 7
Objective Function). The function f(w, v; p -strongly convex on W and pa -sstronggly concave on V. i.e. there exist constants p > 0 and Ne >> O such that for all w, w' W, v.v' V and E Z, it holds that
(Ww, 2 f(w', 2; + (Wll(w, v;z), w w²) Me - - [(w,,3)) S [[w, v';2) v/; -
(35)
Definition 8 (Best Response Auxiliary Functions). We introduce auxiliary functions Vs(w) and Vis (w), given by
Vs(w)= == argmax Fs(w, v), wEV
Ss (w) == argmax Fsy Fsy(w, (W.
(36)
DEY
We can similarly introduce Ws(v) and Wgy (v) as and we have V/ Vs(w'z) and Vss Vsi(w(s))
Ws(v)= argmin Fs(w, v), Ws argmin Fsx (w,
(37)
wEW
wEW
and we have w's = (s( and w'y = (sr( by this definition.
In addition, we define the primal function P(w)= == max Fs(w,, v) = Fs(w, Vs(w)), which has gradient P(w)) V.- -VFFs(.VVsw)) Vs(w)) and Hessian V2 P(w) Dww Fs(w. Vslw)) (ie. the total Hessian of Fs). The dual function, its gradient, and Hessian can be similarly defined, e.g. D(v) := min Fss (ss(w,)) Fs(Ws(()).))
A.2 Supporting Lemmas
The following lemma provides the distance between Vs(w3) and V (w3). Similar result can be derived for the distance between Ws(zz) and Ws (vz).
Lemma 2. Under Assumption 7 and Assumption 2 the variables V (w6z) and vš (ie.. V vs(w)))
defined in Algorithm satisfy the following distance bound
2Tm
| - Vg (w))l) - (n - m)
(38)
15

---

Proof. We observe that
(n (F (w3, Vov (w5)) Fs: (w': vz))
Σ Vys (w))izz)
Σ (WS
&ESQU
Σ f(w3, Vs (w3):)) - Σ F:88
f(wš, (si(w3):22) -
Σ
flw3..33
E(w3s vz3
REU
FES
Z:EU
(n(Fsw Vs (w/)) - Fsswsss..s. v$)) + Σ
f(wss Uzizi)
Σ
f(w3, Visi (w})i
#EU
:.EU
(5)) S mblluz - Vss (wو)س,
Σ MwW vsi - Σ 2.EU
Mw'. Vsv (w));
+EU
(39)
where the inequality (1) follows from that v3 is the maximizer of the function Fs(w, v), thus (WS, Vis (w²) Fs v5) O. The inequality (ii) is due to the fact that the function is L-Lipschitz. Also note that the function P' (w, v) is By -Stonngy concave, thus we have
Fsn (w3, sy (wz)) Fsv Fs (w3, v2)) z Hy 112 Vis (w
(40)
2
Eq.391 and eq. (40 together give that
Nv (n m)
|1/3 Vgv (w3))l S mLlliz - Vis (w3)ll+
(41)
2
which implies that ||a/ - Vss (w33)
S (u mm)
2Lm
The following lemma provides the distance between (w V's)) and (wi,, Uz)-
Lemma 3. Under Assumption
7 and Assumption 2 the variables (wgy Vzs)) defined in eq. 9 and
vz) defined in Algorithm
satisfy the following guarantees
2Lm
2Lm
وw wاll -
Mw and
| - -všll S
(42)
Pl
Proof.
We begin with the w-part,
n(FFs(wgr v - Fs(wws; v)
EWw (5(iz)) Σ [w3s (2))
Z,ES
- flW5) (2) + Σ f(wisr (5):2))
Σ (W53) Σ
f(wss :2)
&EE
AESIU
S.EU
-(n (inmm] F)) (w (W'), - (s: 51 Σ Iww Sy: Ugrizz) - --E I(w USiiz))
2.EU
ZEU
(
(H)
Σ f(W5), Vg)izi) - Σ UEEU
f(w's Ug
< mL [ - -wEll
ZEEU'
(43)
where the inequality (i) holds because wis is the minimizer of the function Fsx (w, v), thus Fsy (wog vg Fs (w3, vig)) I O, and the inequality (ii) follows from the fact that the function f is L-Lipschitz. Since the function Fs(w,1) v) is pa -strongyy convex, we further get
Fs(w v3 Fs(ws, v5)) 2 Me Iw's w3
(44)
Eq. (43 and eq. together gives that
Mw?
- will s mL - wzlll-
(45)
2
16

---

Thus, we get |w'ss -w'll I For the v-part, we similarly have
2Lm
Mwn
vz) - (s(Wwi:
= =[sw Ug:
(w
Σ
2,63
Σ f(Wg) v3:2))
+
Σ
f(w vz:24)
Σ f(w U5siz))
Σ
f(w U3):22)
UESIU
ZIESQU
AEE
-(n m) (s:
(W's,, 2
Fs (w
st v3))++
Σ
flw
(W Uziz2) - Σ
&EU
B.EU
(
(1)
Σ MWWS), Us; - Σ ZEU
Mww Ug(
S Usss - Vigill 1l,
ZEEU
(46)
where the inequality (i) follows from that V is the maximizer of the function (s 12, thus Fs (w5)))3) - Fs (W (()) s 0. The inequality (ii) is due to the fact that the function f is L-Lipschitz. In addition, by the strongly-concave assumption of Fs(w, v) is pe, we have
Fs(w sy, vs) - Fs(W VSS) 2
Hy | - 2
(47)
2
By (4) and eq. 47 we get that
Py
| vill S mLLlv/ - v/glll l1.
(48)
2
Thus, we have ||
w/ll
x
20m Mun
In the following, we recall several lemmas (i.e., Lemma to Lemma g) from existing minimax optimization literature for completeness.
Lemma 4 ((iin et al. 2020 Lemma 4.3]). Under Assumption 7 and Assumption 2 for any E W. the function Vs(w) is
(t/p2) Lippshhr....
Proof. By the optimality condition of the function Vs(w),, we have
(VuPs(wi, (), Vs(w2)) Vs(ww)) S 0,
Vu Vs(wz)), Vs(wi)) - Vs((u2)) I 0.
Summing the two inequalities above yields
(s Vs(w1)) Fu Vs(w2)), Vs(w2)) vs(wi)) S O. Since the function Fs(w, v) is -tronnlly concave in u, we have
(49)
(s (s( Fs (w), (s(w))) Vs( Vs(w1)) + (wllVs((2)) (s(wi)112 S0.0 (50)
By eq. 49) and eq. 500) with the é-Lipschitz continuity of V Fs v), we further get
No (w))) Vs (w(w))) )1 < (V.Fs V=((2)) (w), Vs (w2)), Vs(wa) vs(wi)) (51)
s El|W> - will [[V)(w2)) - V (w(
Consequently, we have
[[Vs(2)) vs(wi)ll S f _ will-
(52)
ulv
Remark 1. The above lemma can be similarly derived for Ws to obtain that the best response auxiliary function Wy(v) is -lipshiit In the next three lemmas, we focus on the w-part and omit the v-part.
17

---

Lemma ([Luo et al.
2022 Lemma 3]), Denote Ky = f/pv.. Under Assumption 7 and Assumption
2 for any w, W. we have
IPww Fs(w, Vs((w)) Dww Fs(w", Vs(w))) & 4V 4V2x w'l.
(53)
Lemma 6 ( Nesterov and Polyak 2006 Lemma IJ). Denote L/ e/pu. Under Assumption 7 Land
Assumption 2 for any w. W, we have
M || w'l?, (54)
[VF.sW.ss(()) V Fs((',Vs(W')) Dww Fs(w')) - -w'll s 2
where M 4V2
Proof. Recall the definition of the primal function P(w) == maxvev Fs(w, v) and its gradient P(ww) Fsw,, (s(w)) Due the optimality of Vs we have
Fsw, Vs(w)) O.
(55)
By taking the total derivative with respect to w, get
(w()) + FswFs(w, Vs(w)) VVs()) = O.
(56)
Taking the total derivative of again (((w), we further have
P(w(() =d (s(w, Vs((w) + aw Fsw VV(w)))Vs((W)
=ww (w Vss(w)) Own Fs(w. Vs Vs(w))) Fs(w, Vs(w))Ouw Pslw, Vs(w)) (57)
PswlP Vs(w)).
Based on the equality of 2 ((W) and Dwn Fs( Vs(w)) above and Lemma 5 we have
[ww Vs(w)) - Fs Vsslw') ('''l'sw''le w'lll
V((w) P(ww') V ((w')(w w'lll
(58)
M || ww112
2
Lemma 7. Under Assumption and Assumption for all W and v V. we have 5
Proof. By the definition of the total Hessian, we have [Dww 2;2)
1ww f (w, 2;2) vw) 2).
Bawa I (w, u; 212 + 1w 2
2) 1 2) Sow vw (59)
5 2 + l. 2 1
where the inequality (i) uses the triangle inequality and the inequality (ii) is due the function
has Ê-Lipschitz gradients and f is mu -t-stnongly concave in v, thus we have [10ww f(w, w;2))l < B [|@we/ (w v; =)l S f, [10 v: 2)ll S & and l|0m. (w, v; 2)ll S 14
Hand Lemma 8 (Zhang et al. 2022a Lemma 4.4)). Under Assumption and Assumption 2 the population weak PD risk for the minimax learning variables (w)., v'g) returned by Algorithum has
21212
(w
(60)
um
Lemma ([Zhang et al. 2021 Theorem 2])- Under Assumption 7 Mand Assumption strong PD risk for the minimax learning variables (wsz, v3) returned by Algorithm has
the population
2/2L2
( 1w
(1+
8L28
(' 1z)
+1
(61)
Mwlti
Pvv
2m
18

---

B Detailed Algorithm Analysis and Missing Proofs in Section 4
B.1 Analysis for Algorithm 2
In the following, we provide the analysis for Algorithm 2 in terms of guarantees of (c, ---etifie unlearning, population primal-dual risk, and deletion capacity and the corresponding proofs.
Lemma 10 (Closeness Upper Bound), Suppose the loss function f satisfies Assumption L Land 2
min minn plu Huow Pvv Then, we have the closeness bound between (w, D) in Line of Algorithm 2 2and (w's.//)) in eq.
[DwwFFsWW3 v/3) 2 Pow and (ww3s, 2/3) Z Mun. Let μ
(8v2L' p/ n. + 8LL2 /.LE2/1²)mm ym²
[llwar 1P
D1)
(62)
n(um (L + 82 //)mm)
Proof. Recall that the empirical loss functions Fsy (w, v) and Fs(w, v) are
Eg (w, v) =
Σ
f(w,v:2)), and Fs(w, == 1 Σ f(w,w;2)). (63)
2:E8
We focus on the key term Fs (WS) (s(ws)) - Fs U2} - Dwow Fs (w5, 13) wW3). which has the following conversions
V Sy (W Vs(wS))) )) V. (W': Uz) Dwn s: (w (w/) - wا'سll
n
Fw Vs (w() Fs Uz} Dwn Fs (wS w5)]
n m
Σ VWl(WS V Vs(Ws:): ) /wl Uš:
n m 2,EU
Σ
+ n1 m E,EU
(64)
V.FFswsg. Vs(wg)) )) VWFs(Ws, vz)) - Dww Fs vS) wz)ll
n1 m
Σ |WJl(W 2z) (ws
+ n ZIEU
1
Σ Dwwf 21) wz)1l
+ n
We denote Nov f/wu.. For the first term on the right-hand side of the inequality in eq. 644. we have
VV Vs(wgg)) ) VuFF(W's v²))
Dww Fs( -w3)ll
n m
(
2/ will (st) 8V222 8V22L220mm
(65)
nn m) n*n(n - m)
m
where the inequality (i) by Lemma 6 and the inequality (ii) by Lemma 3
For the second term on the right-hand side of the inequality in cq.664) we have
Σ
V f(w Vs(wg)):)) 2,) V W ugi =I
71 T UUU
(4)
me / |w w3l 22 V[((wg)) Vs(
n1 m
(66)
(11)
ml
[W3. w//l2 12 N:31 1: w/'12
11
(st)) 2Llm² /1
11++ K < ( m)
2 2
2/2112m²
um m)
p22n(n m))
where the inequality (i) follows by the fact that the function V.l(,,) is f-Lipschitz continuous and V/ Vs(ws)). The inequality (ii) holds because Lemma
and the inequality (ii)) is by Lemma 3
19

---

right-hand For the third term on the right- hand side of the inequality in eq. 64
we have
Σ
Dww!
I (w]s U3: (W)s))
wلYll
2.UU
(67)
2Lm²
4LL
(l +
Puntin m) 12n(n m)
where the first inequality by Lemma further get
Plugging eq.(65). eq. (66) and eq. eq.667 into eq. we
m² \ (W5y vs(w))) V W' (w3,
Dww Iw f's (W)) w3)l
(68)
<(8V212@0/1 SLC /n²) n(n 1
The above derivation yields upper bound result. In the following, derive lower bound result. Let x be the vector satisfying the following relation,
's = wws
1
www Fsy (.w..ys))
Σ REU
Vwf +x.
(69)
Since we have V Fs (w3, v2) m-m BEE o (w U3: 2,) and V Fs (wos vs(ws)))
0 due the optimality of wi.. plugging eq. 69) into eq. eq.68 we get that
| Fs (WS, x|| S (8V2L 8LE
m
(70)
nnn m)
For the left-hand side of eq. 770 70 with |www (w) w3)1| Mmw we have
|Dow Fsx (w v33 x
Σ Dww / [w]. (W: us: x||
n1
Duns (w's v3z;2))
Σ
Dun flws: 21)) x||
n m
2:EU
|InD F's (w' v3)1l -11 Σ Dww fWW ugg
||x||
n m
2.EU/
(Mww
(1+ 6 Me )m)
(um
(e (e= (2-
|x|||
|x|||
n
m71
(71)
where the second inequality is by Lemma] vector ||x||, we get that
Combining eq. 77 eq. 6g. 3 and the definition of the
(8V2L2 p/p² 8LE pm
=
| <
(72)
n(um (2+12/m)m)))
Symmetrically, we can get that
||
n(pn (u)m)
Theorem 6 ((c, Mi-imma Unlearning Certification). Under the same settings of Lemma 10 our minimax leurning algorithm Asc-se and unlearning algorithm A so is (e, 5) -certifie minimux unlearning if we choose
2(8/212 p/10" + 8LP 1p2mm /2log(2.5/6).
01 and 02 n(pn - (e + (/p)mme
(73)
Proof. Our proof for (c, minnimxx unlearning certification is similar to the one used for the differential privacy guarantee of the Gaussian mechanism (Dwork et al., 2014).
Let vz) be the output of the learning algorithm Asc-se trained on dataset S and (w" (w",v") be the output of the unlearning algorithm Asc-sc running with delete requests U, the learned
20

---

model (w3, 25), and the memory variables T(S). Then we have (w3. (S) and (w", (²)) = Asc-so(U, (S), ((5)) We also denote the intermediate variables before adding noise in algorithm Asc-sc as (w., p), and we have w ت + & and n*
E2.
Smilarly, let (wiy (3)) be the output of the learning algorithm Asc-sc trained on dataset 5 \ U and (wix, ( be the output of the unlearning algorithm A running with delete requests 0. the learned model (w's) Vsy), J and the memory variables T(S \U). Then we have (wgr, Vg)) = We also denote the intermediate variables before adding noise in algorithm Asc-se sc as (mg), Ds ), and we have w =gg + E1 and V Dg + &z. Note that Wو = Wgg and Ug V/gi
(.5's(s ( U) and (w gt: pS)) = Asc-sc (0, US))
We sample the noise & ~ NV o1Id, and &2 ~ (0, )2Ld,) with the scale:
{
(log((255/0)
||0g] - [ (2.3/288/
σ1 = Iw :||
c/2
c/2
(74)
(2.(//)/)) 10 il|
2 log (2.5//)
02 = | أ
c/2
c/2
where w [|| and w W are given in Lemma 10
Then, following the same proof as Dwork
cct al. [2014 Theorem A.I] together with the compositron property of DP [Vadhan 2017
Lemma
7.2.3], we get that, for any set O S θ where θ == W V.
Pr[ D) 0) S e pr(( Dy E O + 5, and Pr((@st D)s)) E 0 s e Pr(((,,)) D) E
c + 6.
(75)
which implies that the algorithm pair Asc-se sc and Asc-se is (c, 8) certtifee minimax unlearning.
L
Theorem 7 (Population Primal-Dual Risk). Under the same settings of Lemma T0 and denote
d maxfdj, d2). the population weak and strong PD risk for the certified minimax unlearning
variables (w" ,U") returned by Algorithm Pare
! (w0 22) =0 -11 p/ 1128/10)- m² /dloo(1/8)
mL2
n²e
um
(76)
1 \'(=", (1220110 + 12E2112 -0020000)0
m² /d n²c
mI.
1.2
+
un
p²n
Proof. We begin with the population weak PD risk for the certified minimax unlearning variable (w","") which has the following conversions,
A"" v²)
max E[F(W", [D] min B[F (w v² "
weW
-max E FWW" .v) -F(w', 1) + F(W m)]
min B[F(w, - F(w, + F(w.vz) wEW
$ max E F(W""", v) - -F(w v) + max De
[ ]]]
WEV
miin B[ n²) - F(w, [(w,v3)] wEW
min B[F wg)
WEW
max E[F("" v) F(W3, m/ + max 1E(
(E((= F)) (ws, w²th (-F)
PEV
wEW
+ max [[F v)] min NEW
B[F vš)l
NEV
(3)
[ wt wلlll + E[L wšl + v3)
(8) < [E[L|[""-'h
20212
+ E|L 13lll +
um
(77)
where the inequality (i) holds because the population loss function F) = Eff(w, v; z)] is L-Lipschitz continuous. The inequality (ii) is by Lemma
By recalling the unlearning update step in Algorithm
2 we have
1
Wh = w's m
Dww Fsy (W's D3)]]
Vullwj, 23;21) + E1,
(78)
E
21

---

where the vector E E Rd is drawn independently from (N of ). From the relation in eq. 78.) we further get
B|||w"
-
wlll
=B
1 m
www Fsi (wS. 21)1
Σ
(wf +
#EE
(ww E's (wS. v²)]
[wf Uš: zi)
+ +
71
1
Z:EU
(41)
11 m
E
+ [ 12]
(um- {(1 + f/
2.EU
(16
1
E
Σ
Vuf(W3,
+ +/110
(um E(1 + mm
AEE
(50) (um E(1 p/p)m)
mL.
+ vdioi.
(79)
where the inequality (t) is by the triangle inequality and the inequality (it) follows from the relation in eq. 7 together with the Jensen's s inequality to bound E Bills The equality (iti) holds because
the vector Ç ~ NO, IfI and thus have [E[|E, [l]] d1of. Furthermore, the inequality (iv) is due to the fact that f(w, vz 2) is I--Lipshitz continuous.
Symmetrically, we have
mL
E Blll""
všlll
S
(pn - {(1 + f/ + Vdzaz.
(80)
Plugging eq. 79 and eq. 80 into eq. 77 with d max (d1, d2) get
2mL2
2V2L2
(w"
+ Volai + 02) +
(81)
(am - ((1 + l/1)m)
1u
With the noise scale o and 02 being equal to (ISV2L2Epie + our generalization guarantee with population weak PD risk:
+BLE /22 mmn
12ei222lg00 /2oog(2.5/8) we can get
A th (w" D²) -o 1/3 + 1283/13) m² m /dlog(1/8)
m..²2
(82)
nie
pm
For the population strong PD risk A (' D²), similarly, we have E/max F(w", v) min ((W."")
DEV
WEW
=E/max (F(w", v) F( + F(wss v)) - min (F(w,z") F(w, vz)) + F(w, v3))
NEV
WEW
-Emmax( F(w", v) F(Wss F(Wws, D))] E wEW
min (F(w, F(we, v32 + F(w, v/3
WEV
<E|max( F(w"" v) - F(Wss 1)) + max F F(W3. ]] WEV
VEV
EE min (F(w, 1²) - F(W,v/3) + min F(w, v3)
WEW
wEW
[Flmax(F(u") v) F( 1 WEV
E
max F (w v)]
DEY
E min (F(w.v") - F(w, v/ri
E
min F(w, v3²]
WEW
wEW
(Flmax(F(w')) v) F(w's, D)) )} + |m
((FF) v²) (-F)(w,
NEV
NEW
+ Emmax F(w3. v) min F(w,)3)] WEV
wEW
W' - willl
- - + A 1 (w Uz$)
(10
2ml²
8128
+ Vd(ai + L +
(um {(1 + f/1]m)
12n"
(83)
22

---

where inequality (i) is due to the fact that the population loss function F(w. v) := Eff 2)] is L-Lipschitz continuous. The inequality (it) uses eq. (9). eq. (8) and Lemma 9 With the same noise scale above, we can get the generalization guarantee in terms of strong PD risk below,
A'(w", v")=, (1 11² m² /olog(1/0)
mT?
1.2g
(84)
n²c
pm
p
Theorem 8 (Deletion Capacity). Under the same settings of Lemma 10 and denote d = max d1, d2}. the deletion capacity of Algorithm 2 is
n
A.A m me,b,- (d1, (d1,,d,1)) n) 2 c.
(85)
(dlog(1/))) 1/41
where the constant e depends on L,I, and μ. of the loss function f.
Proof. By the definition of deletion capacity, in order to ensure the population PD risk derived in Theorem is bounded by y, it suffices to let:
nye
A.À m 2,,,7 (d1, d2, n) c (dlog(1/6))/44
where the constant e depends on the properties of the loss function f(w, 2).
B.2
Missing Proofs of Sec
B.2.1 Proof of Lemmal I (Closeness Upper Bound)
Proof.
By the definition of the functions Fs(w, v) and Fs (w, v), we have
Fs (w Vs(W)))) Fs (W/s vs)) n
m Dww Fs (w 13) - -33)
Vw Vo Vs(WW()) V Vu Vz} D Fs Fs(ws, (w) -w3) n
Σ VvvlWu Vs - Val V Ugj 2;]]
SEUU
( n
(86)
-
I Fs(w V Vs(wg))) ))
V Fs v//) Dww Fs(ws: (w) - -w3i
n m
Σ n m
|wLs Vs(wg)): 2:) VwI 21)1
B.EU
(10) 8 (2
2/2LI'
n m)
1 m))
where the inequality (i) holds because the triangle inequality and the inequality (ii) uses the results in eq. (65) and eq. 1666 Now let x be the vector satisfying the following relation,
wigh w n
1
Daw
Σ
(87)
AEEU
Since we have V Fs (Wg, vz) -يبييب Σ eU Vwf 23)2) and V (w (r Vs(w)))) =
0 due to the optimality of s plugging the above relation into eq. 866) we get
12 Dww Fs (swws, 2 S (8V2L2 + 2L 122)
m
(88)
n(n m)
With Dww Fs (s) 2 pow, we also have
Duww Fs(wss U3 |
> Mw n2
||| > pn |
(89)
m Combining 1q. eq. 88 and the definition of the vector
||||| we get that
(8V212 p/ + 2222L22 / mm²
wi ااهl = ||||| <
(90)
2 42/21 (8./112 p/1 p / pm
Symmetrically, get || ž <
23

---

B.2.2 Proof of Theorem ((c, ((cc,))-Mnnnn M)Miniia Unlearning Certification)
Proof. With the closeness upper bound in Lemma and the given noise scales in eq 22 the proof is identical that of Theorem
B.2.3 Proof of Theorem (Population Primal-Dual Risk)
Proof. We start with the population weak PD risk. By eq. we have
th ( 1n) - "| w/ || + ELLIE" nilll 2V2L2
(91)
By recalling the unlearning step Algorithm we have
ThMh W mDw Fs(ws; -3)l=
Σ
Vuf(ws u5; + E1,
(92)
2,EU
where the vector EΙ E Rdd is drawn independently from (00 of From the relation in eq. we further get
78)
B|||@" will =E
Dww (ws vz)
V Sw]lws US: 2i) + E
E
Dww Fs (s(W5))))))
+ B V fWS: V 24)
71
(93)
(04)
EE
V Vul(wss pšiz)
+ E 1
F.EU
(168)
E
(ul Ugi Ugi
+ Vdiai
(4r) mL Vdio,,
pm
pn
2.EU
where the inequality (1) uses the triangle inequality and the inequality (ii) follows by the relation
Dww Fs 2 Haw 2 nu, together with the Jensen's inequality to bound B|] The equality
(iii) holds because the vector & ~ NN0, La, and thus we have [| dio And the
inequality (iv) is due the fact that f(w, V; 2) is L-Lipshitz continuous. Symmetrically, have
mL u'll
E[||
Vilaz-
(94)
pm
Plugging eq.
93 and eq. 94 into eq. 91) with max (d1, d2) we get lq.
2mL² Vd(o, + σ2) 2/212
A Dd)
(95)
un
pn
With the noise scale o, and 02 being equal to 2(SVIL' -2 -2 /m" get our generalization guarantee in terms of population weak PD risk:
(2log().5/)), we can
A nd D4) O (I
p/p0 p/p0
138//28) m² "
/doog(1/8)
mL²
(96)
n²e
un
For the population strong PD risk, using application of eq. and the noise scales given in Theorem 2 we can get
83) with Lemma
eq. 93. eq.
94
A 1'(0",""" = (1EEDI++LE1))
( +227/13) /llog(1/0) m²
+ mI? +
I?2
(97)
noe
um
p2n
B.2.4 Proof of Theorem (Deletion Capacity)
Proof. By the definition of deletion capacity, order to ensure the population weak or strong PD
risk derived in Lemma is bounded by it suffices to let m m, (d1, d2, n)) 2 c. (1)0)(1/8))744
A.A
nye
0

---

B.3 Efficient Online Unlearning Algorithm
To support successive unlearning requests, similar to the STL case Suriyakumar and Wilson [2022].
we further provide an efficient and online minimax unlearning algorithm (denoted by Aouline). ) The pseudocode of Aouline given in Algorithm 4 Its certified minimax unlearning guarantee, generalization, and deletion capacity can be identically yielded as Algorithm 3 which are omitted here.
Algorithm 4 Efficient Online Certified Minimax Unlearning (Aontine)
Input:
Delete request 26 S. early delete requests : {2y 12 S S. output ASc: (we, Mš).
memory variables T(S): (Pww (s(ws, vš), Dan Fs(ws, wS)), early unlearning variables: (wi Dij ) loss function: f(w, 2) 2), noise parameters: d1, 02-
1: Set We w/s and Vg = V/.
2:
Compute
1
Wouth) = wv + PswFs(wws US)] V V. / uss
(98)
nt
MDU(N) vo + Duv F's (Ws. V (wws u/: zx).
(99)
3: (b()) Wool + E1, where &1 N1 and (i( Del(e + + where Es ~ NN
Output: (Düu(k)) (.))
25

---

C Detailed Algorithm Descriptions and Missing Proofs in Section 5
C.1 Minimax Unlearning Algorithm for Smooth Convex-Concave Loss Function
In this section, we provide minimax learning and minimax unlearning algorithms for smooth convex- concave loss functions based on the counterpart algorithms for the SC-SC setting. Given the convex-concave loss function f(w,, =). we define the regularized loss function as f(w, v;
f() + ||| 2 || Suppose the function f satisfies Assumption then the function X-strongly convex in w. X-strongly concave in v, (2I- + |||w|| + X >|[ell)-Lipschitz, /2(2l + X)- gradient Lipschitz and p-Hessian Lipschitz. Thus, can apply the minimax learning in Algorithm T and unlearning in Algorithm@tt the regularized loss function with a properly chosen A. We denote our learning algorithm by Ac-o and unlearning algorithm by Ac-c- The pseudocode is provided in Algorithm 5 and Algorithm respectively. Additionally, we denote the regularized population loss as F(w. V) = R2-D [E-D[s(w.)) v;z)
=)] and regularized empirical loss as Fs(w, v) = 1 - f(u, 2;)).
Algorithm 5 Mimimax Learning Algorithm (Ac-e)
Input: Dataset S {=))=1 D", loss function: f(w, v; 2) regularization parameter: A.
I:
Define
f(w,u;)) v; 2) = f(w, us + 1|wl1* 2
>
(100)
2: Run the algorithm Asc- on the dataset S with loss function J. Output: (w's v/s. Dww (ww vš), Deo Fs (w3.. v²)) & A (s
Algorithm 6 Certified Minimax Unlearning for Convex-Conean Loss (Ac-c)
Input: Delete requests U f S S, output of Ac-e(S): (w vš), memory variables T(S):
(Dww (s uš), Duu (wog, v8)), loss function: l(w, 2); regularization parameter: A, noise pa-
rameters: dı, d2.
I: Define
2 11
=( f(w, + ||س1
(101)
2: Run the algorithm Asc-sc with delete requests U, learning variables (w vš). memory variables T(S), loss function f and noise parameters aı and 02. Output: (w",v") 1² Le (wS, (5),
C.2
Supporting Lemma
Lemma 11. Suppose the function f(w, v) L-Lipschitr continuuus Define the function f(wo v;=) as
f(w (2) (w,, X 11w012--111
2 1112
(102)
Given dataset S { and denote (w5, arg min max (FF (F
Th J(, Then, the variables (wis, vz) satisfy ||w S T./> and || S T./.
Proof. Due the optimality of wt. we have
F=FF(ws.
Σ VWf(ws (W: = TI 2.ES
(103)
Plugging in the definition of the function i in the above, get that
1
Σ Vo Vof(wš, 21) + Aw 0.
(104)
26

---

Then, using the triangle inequality, we have
Aلw'll - - n
Σ F
1 Σ 2.ES
[W US: S L,
(105)
where the last inequality holds because the function is L-Lipschitz continuous. Thus we have |w/||| S L/X. Similarly, we can get || S L/A.
Lemma 11 implies that the empirical optimizer (w3.23 returned by A satisfies ||w| S L/A and T - L/X. Thus our domain of interest are W == {w ||اا|||| & L/A} and V == { |||| S
L/A}. Over the set W x V, the function f(w, 2;2) 2) is 4L-Lipschitz continuous. Also, with À L.
f(w, 2) has /22--ippshitz gradients.
C.3 Proof of Theorem 5 (Certified Minimax Unlearning for Convex-Concave Loss Funcion)
Denote L = 4L and i = 3/22,, then the function f is L-Lipschitz continuous and has é-Lipschitz gradients. Let (wis) uS)) be the optimal solution of the loss function Fsx (w, v) on the remaining dataset, i.e.,
(W5r) V = arg min (F (w,
1
Σ
f(w.p;a))
(106)
WEW WED
ZESVU
Additionally, we have [|Duw (sw 23)1 2 X and |D Fs v3)) 2 X.
Lemma 12. Under the settings of Theorem for any X > the population weak and strong PD risk for the minimax learning variables (wis, V')) returned by Algorithun are
32v2L2
X
max E E[F(Ws vil - min E (w, 5
+
(B2 + B3),
DEV
WEW
An
2
(107)
384 2
Elmax F(w's min F(w, F(w,)$}] WEV
+
7 + B²)
WEW
X
2
Proof. For the function F(w, v), application of Lemma 8 gives that
max B B[F vi] min E[F(W,, vz) 32V2L2 WEW
(108)
NEV
By the assumption of bounded parameter spaces W and V so that max ||w|| S B and maxvev || < Bu, we have the following derivations for the population weak PD risk,
max E. F FW v)]
min FFF vr)) WEW
PEV
max R. weV
F(W3,V) - ||ا0g|1
X 1
min E wEW
F(w, vz)
A
A
||
2
+ + [11111]
< max E NEV
min E WEW
F(w, v²))
(109)
2
X
< max R.. [(w's - min E. [w uz)] NeW
+ max E
+ max R
w||
NEV
NEV
2
wEW
2
32/2112
N BB2 B
An
Similarly, application of Lemma gives that
128/21.2222 + x)
E mmax F(W3, v) min Flw, [[w) < WEV
(110)
weW
27

---

And we can get the population strong PD risk with the following conversions,
E
Elmax
V)
min ((w.23).
WEV
wEW
=E
max VEV
F(W3,
X
||w3s12 +
+2 [111113)
-
min WEW
A Flw,, vz)
2 [1w11
+ 2 (113312))
2
F)w3 + A
2 |11111
F(w) vz) ?/1
2 21(0112)
S
max NEV
min WEW
-E
max WEV
F(w3g v) + X
2 ||
- E
min WEW
F(w.Pz)
2 ||w1
A
<
max NEV
F(W5, 1) + max vEV
|| + 18 max NEW
- (w, 123) ) + max
wEW 2 1w'l
2
min F(w, + E. E[max X wEW
-Flmax F(Wg. v) NEV
||1111]
+
mmmax wEW
||01|
'VEV 2
128 (28+ + A)
X
3
X
(B + BB) 5
[ + BB).
X²n
2
2²n
2
(1I1)
Lemma 13 (Closeness Upper Bound). Under the settings of Theorem S we have the closeness
bound between the intermediate variables (ūo, 1) in Algorithm 6 and (w V's)) in eq. e0.1
(8 X ST. />² ymmm²
(lwwar -61, 11/5
1
(112)
n(An (e + 22 (2/)mm
Proof. Since we now run the algorithms Acc-sc and À scc-sc with the regularized loss function j. the
proof is identical to that of Lemma 10
Equipped with the supporting lemmas above, the proof of Theorem can be separated into the proof's of the following three lemmas.
Lemma 14 (Minimax Unlearning Certification). Under the settings of Theorem 5 our minimax
learning algorithm Ac-c and unlearning algorithm Ac-o is (e, 8)-ceriffeed minimax unlearning if we choose
2(8v2I pf 25 + SLE )m?)m² logg(/////).
01 and 02 n(An (e (2/A)m)e
(113)
Proof. With the closeness upper bound in Lemma 13 and the given noise scales in eq. 113), the proof is identical to that of Theorem G
L
Lemma 15 (Population Primal-Dual Risk). Under the settings of Theorem B the population weak and strong PD risk for (w" v²) returned by Algorithm o gare
m² //lo((1/0)
mL2
A A" v²) 50 (130p/X0 + +220/23)
X(B2 + BB)))
n²e
An
m² Vdlogg(1 138/223. (1)))) NWW", D¹) (0 p/2 +
mI?
T.2e
An +
+BB2 + BB))
nee
X2n
(114)
Proof. For the population weak PD risk, an application of eq.
together with Lemma 12 gives that
A (w" vn) < B[[.|[ w []] E[L][| rill 32/2L2
X B BE)
(115)
An
According to Algarithm 6. we have the unlearning update step
"t = w/s m
1
Dww Fs (w's: 2ン)
Σ
DW; +
(116)
E,EU
28

---

where Fss (w/z. v3) == 1 EnEsio v(,, From the relation above, we further get
El Bl|l"" wwlll
=E
Dww Fs (wss. v3)]]=
fw U3: 24) + &1
m
2,EU
E
(wwwFis Fs (Wg. v3)]=1
V f( Uziz))
+ +Bill
71
2,E0
(86)
12
E
(w) U3: 2i)
+ +VE/l
11 m
(An {(1 + e/D)m)
(117)
B.EU
(184)
1
E
Vo fwws Mz322) zi)
+ Vdio
(An Ê(1 + 2/mm
ZEEU
(iv)
1
E
+1 All231l
Vdiai
(An {(1 E/
LEE
3mL
+ Vdiai,
(An - E(1 + E/A)m)
where the inequality (i) uses the triangle inequality and the inequality (it) follows from an application of eq. 71). together with the Jensen's 's inequality to bound B|ll@ The equality (Hii holds because the vector & ~ oL,, and thus we have ||||@|| = díoî. The inequality (iv) uses the
definition of the function and the triangle inequality. The inequality (v1) is due to the fact that f(w, 2) is L-Lipshitz continuous and Lemmal 11 Symmetrically, we have
3mL
B Blil"" w/ll]
v d202-
(118)
(An E(1 + f/A)m)
Plugging eq.4117 and eq. (18) into eq. (15 with noise scales given in Lemma 14 can get our generalization guarantee in terms population weak PD risk:
eq.
m² lolg(1)/)) A"(w",n") ( (
mL?
128/22)
+
ABB + BB)
(119)
n²e
An
Similarly, using an application of (83 together with Lemma we can get the following population strong PD risk:
Lemma eq.
and eq 118
v2) s =0 ( (0(
m² (dlog(1/8)
mL2 I An
+ +X(B2+BB) (120)
n²e
X2n
Lemma 16 (Deletion Capacity). Under the settings of Theorem
5 the deletion capacity of Algorithm
is
ne
A.A m (d1, d2, n) 2 (dlog(1/8)))44
(121)
where the constant e depends on L, p. Bus and By.
Proof. By the definition delction capacity, in order to ensure the population PD risk derived in A,Á Lemma 15 is bounded by 7, it suffices to let m m, (d), d2, 2 c (dlog(1/6])777
n.e
C.4 Minimax Unlearning Algorithm for Smooth Convex-Strongyy-Concre Loss Function
In this section, we briefly discuss the extension to the smooth C-SC setting. The SC-C setting symmetric and thus omitted here.
29

---

Given the loss function v2 that satisfies Assumption I with p concavity in v, we define the regularized function v(,,,;;) f(w, v; 3 ||w||? Our minimax learning and minimax unlearning algorithms for C-SC loss function f denoted by Ac-se and Ac-sc are given in Algorithm and Algorithm respectively. Additionnlly, we denote the regularized population loss by
F(w,v) v) == (g, v; 2] and regularized empirical loss by Fs(w,D) := = > f(w, Mi zi).
Algorithm 7 Mimimax Learning Algorithm (Ac-so)
Input: Dataset S: {2i)e= ~ D", loss function: f(w, ki 2), regularization parameter: X.
1: Define
((,, v;2) = [[w, v: + 1 |||l
(122)
2: Run the algorithm Asc-se on the dataset S with loss function J. Output: (WS, Vš, Dww (wss, vš), Den vz)) f Asc- (S,
Algorithm 8 Certified Minimax Unlearning for Convex-Strone Convex-StroglyyConnawee Loss (Ac-se)
Input: Delete requests U : {2 E S. output of As): (w3 v$), memory variables T(S):
(Daw Fislss U&), Duu Fa (wog, v&)), loss function: f(w, z). regularization parameter: A, noise pa-
rameters: 0T, 022
I: Define
i(w v12) u:)) |wwl
(123)
2: Run the algorithm Acc-sc with delete requests U, learning variables (w),2)) memory variables T(S), loss function J and noise parameters an and Output: vw")v"") + (U, v5), f(S),
Note that the function F(w. 2/ 2) is A-strongly convex in w, -t-sonyggly concave in v, (L 2L + |lisssii,,,,h,t, (E = /2(22 + ())-gradient Lipschitz and p-Hessian Lipschitz. We also have ||Dww Fs(wig || 2 x. Let (w vs)) be the optimal solution of the loss function Fsx (w v) on the remaining dataset, i.e.,
(werr V/+)== = arg min max wEW NEV
(w. (F
1
Σ f(w.
(124)
m B,ESIU
An application of Lemma 11 implies that the empirical optimizer (w3. vz) returned by Algorithm 8 satisfies ||تو||| < L/A. Thus our domain of interest are W = ااا|اا < L/A]. Over the set
W. the function f(w, v; 2) is 3L 3L-Lipschitz continuous. Suppose the strongly- regularization parameter À satisfies X < e, then f(w, 2) has /2-Lipsshhizz gradients.
The corresponding theoretical results are given below.
Lemma 17 (Closeness Upper Bound). Let Assumption hoold. Assume the function f(w, v) is Ny strosrrygly concave in u and Fs =g 2 Hyv. Let = min( ).y). }. Then, we have the closeness bound between the intermediate variables (ās D) in Algorithm 8 and (w ww.... in
eq. 124
|w - -611 <
18V2LPP x
8L2
m n( (1+22 /p)m)² Au
(125)
1 T11 <
+
8i.2
m2
App
Tijan (C+27/2)m)
Proof. Since we now run the algorithms Asc-sc sc and Asc-so with the regularized loss function f. the proof is identical to that of Lemma 10
Lemma 18 (Minimax Unlearning Certification). Under the settings of Lemmal 17 our minimax learning algorithm Ac-se and unlearning algorithu Ac-ac is (e, -certifie minimax unlearning if
30

---

we choose
SLP
2m" (2.(2))/
01
Au
a(An-
(6+.) /u]mie" 22ogg(25/0
(126)
8LF
2m
0
Proof. With the closeness upper bound in Lemma is identical to that of Theorem G
17 and the given noise scales in eq. 126). the proof
Lemma 19 (Population Weak PD Risk). Under the same settings of Lemma 17 suppose the parameter space W bounded so that max |W||| I Bu. the population weak PD risk for the certified minimax unlearning variables (w" v²) returned by Algorithm 8 is
(0(
1 13
L3G2
L2
m² /llog1//))
mL?
mL?
(" V") S
+XBB) (127)
D21
An2
i2e
pn
where d = max(d1, d2). In particular, by setting the regularization parameter as:
L m Lem
dlog(1/6) 1/22 E22 /dlog(1/))
1/3
À max
Bw V Buum
B Ba
(128)
1 pm? (olo((1/5) 1/1 nLe
we have the following population weak PD risk:
A (w 24) 24)
C1
m
C2
c3
dlog(1/6) (1/) 1/2 )
n
(129)
dlog(1/0)
/5)
(
1/3
2/3
dlog(1/0)
1/4
m
cs
where C1, C2, c3 C4 and O are constants that depend only on L, l p. p and Bwn
Proof. An application of /Zhag al. Theorem 1] gives that
2021
E[F (w, v1)1 18v2L2 wEW
(
max
LE
v)]
min
(130)
DEV
n
Using the relation above with an application eq. and eq. (09), we have
18V21.
(1+1)
+ 1)
XB
(w"" vz)
[ will
E|L| 2
(131)
n
1
2
By an application of eq.
117 we further get
2mL
E [ wاlll s An E(1 + 2/p)m
Vdar
(132)
and
2mL
E E 3 <
+ dzaz.
(133)
um - ē(1 + 2/A)m
Plugging 132) and eq. generalization guarantee:
133 into
131
with noise scales given in Lemma 18 we can get our
A"(W", Vn) S 0
(
1222
m² (log(1/)) L282
mL²
mL2
AB (134)
13
X2p
nee
An
+
pm
where d = m2x
31

---

Lemma 20 (Population Strong PD Risk). Under the same settings of Lemma 19 the population strong PD risk (w". 1²)) returned by Algorithm is
(" v²) S 30
L 1
L
L2R
m
d
(log(1/))
mL mL?
+
221
n²E
An
um
(135)
LL
L
+
AB
12/2
/3/2213/21
where d == max(d1, d. ). In particular, by setting the regularization parameter as:
I m Lem
(Valog(1/0)
( lllg(//0))
112
12
À max
B V n "uuu
(136)
1 63 pmn / (1))
1/44
122
2/5
1
2/3
BL
B
12
11
B n
have the following population strong PD risk:
A \"WW",
1-)
s 0
C1
m
+
m
C3
/log(110))
1/2th
+ ca
/llog(100)
1/3 m 2
dloo((1o))
1/4
m 1
cs
+ C6
CT 2233
2/2
n
(137)
where C1, C2 C3 Ca. Cs C6 and 07 are constants that depend only on L, L, P. and B
Proof. An application of Lemma gives that
36v / 22 A
E max F(Wss, v) min NEV
F(w, vz) < wEW
+
X3/2
/1/2/3/2
(138)
108
1/12
11/2
n
Using an application of eq. 83 scales given in Lemma 18
and eq. eq.011) 111
together with eq. 1188
eq.
eq.4132 eq. 133 and the noise
132
we have
(
L 13113
L2
L
m²
Vdlog(100)
mL² mL?
A A"(w",
+
X21
X122
nPe
An
um
(139)
T,2
T,2
XB2
+
1222
11/2213/21
Lemma 21 (Deletion Capacity). Under the same settings as Lemma 19 the deletion capacity of Algorithm is
n
A,A m m,,57 (di, n) (dlog(1/8))3/4
(140)
where the constant e depends on L, p. μ and Ba and max
Proof. By the definition of deletion capacity, in order to ensure the population PD risk derived in A.A Lemma 20 bounded by 7, suffices to let m (d1, d2, n) 2 c. (dlog(1/6))74 O
Lemma 19
nye
32


Reviews:
[{"review_id": "FtSCPaQsXV", "reviewer": "Reviewer_DtDD", "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.", "questions": "1. Please answer the question posed in weakness 1.\n2. Please answer the question posed in weakness 2.\n3. Please answer the question posed in weakness 3.", "limitations": "1 The work is limited to the approximate unlearning setting, as opposed to exact unlearning. \n2. The authors study generalization performance in terms of weak gap as opposed to strong gap.", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "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.\n\n2. 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.\n\n3. 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?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for his/her careful reading of our manuscript and numerous constructive remarks and questions.\n\n**Regarding additional challenges due to the minimax structure and comparison to prior works:**\n\nThank you for your valuable suggestion and constructive comments. Due to the character limit, we provide explanations of additional challenges due to the minimax structure in General Response. We will revise Sec 4.1 by adding these explanations to clearly convey the challenges, as suggested by the reviewer.\n\n**Regarding Equation (10):**\n\nThe left hand of Equation (10) contains two terms. The first term is the direct Hessian (also known as the conventional Hessian) of $F_{S^{\\setminus}}(\\omega,\\nu)$, which has already appeared in the unlearning update for SLT models. The second term is unique to the minimax unlearning, which captures the inter-influence between the min and max variables and leads to the total Hessian to be used in the minimax unlearning update. In detail, the second term spells out as follows. To get \n$\\nu^\\*\\_{S^{\\setminus}} - \\nu_{S}^\\* \\approx -\\partial^{-1}\\_{\\nu\\nu} F_{S^{\\setminus}}(\\omega_S^\\*,\\nu_S^\\*) \\partial_{\\nu\\omega} F_{S^{\\setminus}}(\\omega_S^\\*,\\nu_S^\\*) (\\omega_{S^{\\setminus}}^\\* - \\omega_{S}^\\*)$, we begin with $\\nu^\\*\\_{S^{\\setminus}} - \\nu^\\*\\_{S} \\approx V\\_{S^{\\setminus}}(\\omega^\\*\\_{S^{\\setminus}}) - V\\_{S^{\\setminus}}(\\omega ^\\*\\_{S}) \\approx \\Big{(}\\frac{d V\\_{S^{\\setminus}}(\\omega^\\*\\_{S})}{d \\omega} \\Big{|}\\_{\\omega = \\omega^\\*\\_{S}}\\Big{)}\\cdot(\\omega^\\*\\_{S^{\\setminus}} - \\omega^\\*\\_{S})$, where the second ''$\\approx$'' is the linear approximation step and is the response Jacobian of the auxiliary function $V$ defined in Definition 8. Next, by implicit function theorem, we further have $\\Big{(}\\frac{d V\\_{S^{\\setminus}}(\\omega^\\*\\_{S})}{d \\omega} \\Big{|}\\_{\\omega = \\omega^\\*\\_{S}}\\Big{)} = -\\partial^{-1}\\_{\\nu\\nu} F\\_{S^{\\setminus}}(\\omega\\_S^\\*,\\nu\\_S^\\*) \\partial\\_{\\nu\\omega} F\\_{S^{\\setminus}}(\\omega_S^\\*,\\nu_S^\\*) $\n, which leads to the result. We emphasize that this only provides the intuition to introduce the total Hessian (rather than the conventional Hessian) in the minimax unlearning, which is not meant to be rigorous. We rigorously derive the $(\\epsilon,\\delta)$-certified minimax unlearning algorithm based on the one-step complete Newton update and Gaussian mechanism. \n\nWe will move the above derivation from Appendix to Sec 4.1, as suggested by the reviewer.\n\n**Regarding the comparison between Section 4.3 and 5.2 (Algorithm 2 and Algorithm 3):**\n\nWe thank the reviewer for the valuable suggestion. Algorithm 3 in Sec 5.2 is indeed a strict improvement over Algorithm 2 in Sec 4.3, with better efficiency and similar guarantees in terms of generalization and deletion capacity. We choose to present Algorithm 2 in detail first in the paper mainly due to the following two considerations. \nFirst, the minimax unlearning update in Algorithm 2 is a direct consequence of the intuition in Sec 4.1 to introduce the total Hessian of $F_{S^{\\setminus}}(\\omega,\\nu)$ (rather than the conventional Hessian in prior SLT unlearning updates). Thus, Algorithm 2 has a closer relation to the intuition than Algorithm 3, which uses the total Hessian of $F_{S}(\\omega,\\nu)$ and does not need to update the total Hessian. This cannot be directly derived from the intuition and it is only after formally bounding the closeness upper bound and deriving the generalization and deletion capacity results that we can ensure that replacing $F_{S^{\\setminus}}(\\omega,\\nu)$ with $F_{S}(\\omega,\\nu)$ still have the same utility but better efficiency. \n\nSecond, sequentially introducing Algorithms 2 and 3 is aligned with the chronological development of certified unlearning methods in SLT, which facilitates direct comparison between certified unlearning for minimax models and SLT models. That is, early works on certified unlearning for SLT proposed to use the conventional Hessian of $F_{S^{\\setminus}}(\\omega)$ first, while later works discovered that replacing it with the conventional Hessian of $F_{S}(\\omega)$ can still yield certified unlearning guarantee as well as generalization and deletion capacity guarantees. Thus, we chose to present Algorithms 2 and 3 according to this chronological development so that both minimax unlearning updates can be directly compared with their counterparts in SLT unlearning updates.\n\nWe will revise our manuscript according to the reviewer's constructive comments. Specifically, we will: 1) relegate the detailed analysis for Algorithm 2 in Sec 4.3 to the appendix; 2) Move Algorithm 3 and its analysis from Sec 5.2 to Sec 4.3; 3) Highlight the additional challenges between certified minimax unlearning over SLT unlearning in Sec. 4.1; 4) Add discussions in Sec 4.2 to compare the differences between minimax unlearning and SLT unlearning and provide discussions to motivate the changes made to Algorithm 2 to yield Algorithm 3. \n\n\n**Regarding Strong gap vs weak gap:**\n\nThank you for the valuable suggestion. We have derived new population performance results in terms of the strong primal-dual risk for our minimax unlearning algorithm, as can be found in General Response and the attached PDF.\n\n**Regarding limited to the approximate unlearning setting, as opposed to exact unlearning:**\n\nIn this paper, we focus on the approximate unlearning that comes with $(\\epsilon,\\delta)$-certified unlearning guarantee, generalization, and deletion capacity guarantees. We will add discussions in the future work part about the potential for developing minimax unlearning methods under the exact unlearning setting."}, {"review_id": "rK6vmEpGJC", "reviewer": "Reviewer_R8EP", "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})$.                               ", "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?\n\n- 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?\n\n- 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?\n\n", "limitations": "N/A", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "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.\n\n- The proposed algorithm shows improvement in both strongly convex-strongly convex and the more general convex-concave settings.\n\n- 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.\n\n- 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.\n\n- 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.\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for his/her careful reading of our manuscript and numerous constructive remarks and questions.\n\n**Some of the technical details are used before being defined properly:**\n\nThank you for your valuable suggestion. We will move Assumptions 1 and 2 from Sec 4 to Sec 3.3. \nAdditionally, we will carefully check all definitions of terms in the paper to ensure that they are defined before being used.\n\n**Regarding the intuition part in Sec 4.1:**\n\nWe apologize for causing the confusion. We will provide more detailed explanations of the intuition and the derivation of Fact 1 in our paper, as follows. \n\nFor the linear approximation and the implicit function theorem to get $\\nu^\\*\\_{S^{\\setminus}} - \\nu\\_{S}^\\* \\approx -\\partial^{-1}\\_{\\nu\\nu} F\\_{S^{\\setminus}}(\\omega\\_S^\\*,\\nu\\_S^\\*) \\partial\\_{\\nu\\omega} F\\_{S^{\\setminus}}(\\omega\\_S^\\*,\\nu\\_S^\\*) (\\omega\\_{S^{\\setminus}}^\\* - \\omega\\_{S}^\\*)$ is as follows. Following Eq.(61), we have $\\nu^\\*\\_{S^{\\setminus}} - \\nu^\\*\\_{S} \\approx V\\_{S^{\\setminus}}(\\omega^\\*\\_{S^{\\setminus}}) - V\\_{S^{\\setminus}}(\\omega ^\\*\\_{S}) \\approx \\Big{(}\\frac{d V\\_{S^{\\setminus}}(\\omega^\\*\\_{S})}{d \\omega} \\Big{|}\\_{\\omega = \\omega^\\*\\_{S}}\\Big{)}\\cdot(\\omega^\\*\\_{S^{\\setminus}} - \\omega^\\*\\_{S})$, where the second ''$\\approx$'' is the linear approximation step and is the response Jacobian of the auxiliary function $V$ defined in Definition 8. Next, by implicit function theorem, we further have $\\Big{(}\\frac{d V\\_{S^{\\setminus}}(\\omega^\\*\\_{S})}{d \\omega} \\Big{|}\\_{\\omega = \\omega^\\*\\_{S}}\\Big{)} = -\\partial^{-1}\\_{\\nu\\nu} F\\_{S^{\\setminus}}(\\omega\\_S^\\*,\\nu\\_S^\\*) \\partial\\_{\\nu\\omega} F\\_{S^{\\setminus}}(\\omega\\_S^\\*,\\nu\\_S^\\*) $, which leads to the result. We emphasize that this only provides the intuition to introduce the total Hessian (rather than the conventional Hessian) in the minimax unlearning, which is not meant to be rigorous. We rigorously derive the $(\\epsilon,\\delta)$-certified minimax unlearning algorithm based on the one-step complete Newton update and Gaussian mechanism. To do so, it requires to bound the closeness upper bound in Lemma 1, which is more involved than the certified machine unlearning for standard learning models. \n\nFor the purpose of leaving out $V\\_{S^{\\setminus}}(\\omega^\\*\\_{S})-\\nu\\_S^\\*$: This is based on the observation that we already have the direct and partial Hessian of $F\\_{S^{\\setminus}}$ in Eq.(10), both are for the loss $F\\_{S^{\\setminus}}$. Thus, when dealing with the remaining term $\\nu^\\*\\_{S^{\\setminus}} - \\nu\\_{S}^\\*$, we want to convert it into a form having strong correlations with $F_{S^{\\setminus}}$ (rather than $F_{S}$). First, according to Definition 8, we notice that  $\\nu^\\*\\_{S^{\\setminus}} - \\nu\\_{S}^\\*$ can be equivalently represented as $V\\_{S^{\\setminus}}(\\omega^\\*\\_{S^{\\setminus}}) - V\\_{S}(\\omega^\\*\\_{S})$, where the term $V\\_{S}(\\omega^\\*\\_{S})$ does not related to $F_{S^{\\setminus}}$. We further convert it to $[V\\_{S^{\\setminus}}(\\omega^\\*\\_{S^{\\setminus}}) -V\\_{S^{\\setminus}}(\\omega^\\*\\_{S})] + [V\\_{S^{\\setminus}}(\\omega^\\*\\_{S}) - V\\_{S}(\\omega^\\*\\_{S})]$. Then, the first square bracket belongs to the total Hessian of $F_{S^{\\setminus}}$ after conversions, while the second bracket still has $V\\_{S}(\\omega^\\*\\_{S})$ that does not have relationship with $F_{S^{\\setminus}}$ (instead it is related to $F_{S}$). We have shown that the second bracket can be bounded in Lemma 2 and the increased approximation does not affect the overall certified unlearning guarantee and the order of generalization and deletion capacity. As a result, this term can be safely left out. \n\n**Why we want Algorithm 2:**\n\nWe choose to present Algorithm 2 in detail first in the paper mainly due to the following two considerations. \nFirst, the minimax unlearning update in Algorithm 2 is a direct consequence of the intuition in Sec 4.1 to introduce the total Hessian of $F_{S^{\\setminus}}(\\omega,\\nu)$ (rather than the conventional Hessian in prior SLT unlearning updates). Thus, Algorithm 2 has a closer relation to the intuition than Algorithm 3, which uses the total Hessian of $F_{S}(\\omega,\\nu)$ and does not need to update the total Hessian. This cannot be directly derived from the intuition and it is only after formally bounding the closeness upper bound and deriving the generalization and deletion capacity results that we can ensure that replacing $F_{S^{\\setminus}}(\\omega,\\nu)$ with $F_{S}(\\omega,\\nu)$ still have the same utility but better efficiency. \n\nSecond, sequentially introducing Algorithms 2 and 3 is aligned with the chronological development of certified unlearning methods in SLT, which facilitates direct comparison between certified unlearning for minimax models and SLT models. That is, early works on certified unlearning for SLT proposed to use the conventional Hessian of $F_{S^{\\setminus}}(\\omega)$ first, while later works discovered that replacing it with the conventional Hessian of $F_{S}(\\omega)$ can still yield certified unlearning guarantee as well as generalization and deletion capacity guarantees. Thus, we chose to present Algorithms 2 and 3 according to this chronological development so that both minimax unlearning updates can be directly compared with their counterparts in SLT unlearning updates.\n\n**Regarding improvement in results in SC-SC case compared to C-C case:**\n\nThe generalization performance of the C-C case is worse than the SC-SC case, where the former is $O(\\sqrt{\\frac{m}{n}} + (\\frac{m}{n})^{2/7})$ while the latter is $O(\\frac{1}{n} + \\frac{m^2}{n^2})$. In terms of the deletion capacity, the two cases indeed have the same order of deletion capacity $\\frac{n}{d^{1/4}}$, which indicates that both cases can support the same amount of samples to be deleted. This order of deletion capacity matches that of SLT unlearning, which can be regarded as a special case of minimax unlearning. Therefore, it does not seem to be an artifact of our certified minimax unlearning algorithm. "}, {"review_id": "xoVZjEFRMt", "reviewer": "Reviewer_sP3P", "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.\nThey 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.", "questions": "None", "limitations": "None", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "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:\n1. 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.\nFor 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.\nTherefore, the reviewer thinks the paper can be improved if the authors can extend their result to strong PD risk. \n2. 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.\n3. Missing reference: ''Uniform convergence and generalization for nonconvex stochastic minimax problems'',   ''What is a Good Metric to Study Generalization of Minimax Learners''.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for his/her careful reading of our manuscript and numerous constructive remarks and questions.\n\n**Regarding strong primal-dial risk vs weak primal-dual risk:**\n\nThank you for the valuable suggestion. We have derived new population performance results in terms of the strong primal-dual risk for our minimax unlearning algorithm, as can be found in General Response and the attached PDF.\n\n**Regarding specific terminology for machine unlearning and deletion in the abstract and beginning of the paper:**\n\nThank you for your valuable suggestions. We will revise the introduction section to include the following content.\n\n1) Introduce unlearning-related terminologies and their intuition: We will provide clear definitions and explanations of key unlearning-related terms and concepts to help readers better understand the motivation and significance of our work.\n\n2) Motivation of our algorithm: We will discuss the challenges and limitations of existing unlearning methods and explain how our algorithm and analysis address these challenges to provide effective certified minimax unlearning algorithms with generalization and deletion capacity guarantees.\n\n3) Meaning and significance of our results: We will provide a clear and concise summary of our main results and their implications, as well as meanings to potential applications.\n\n**Missing references:**\n\nThank you for pointing us to these references. We will introduce and cite them in our paper. "}, {"review_id": "eGaq91Eo02", "reviewer": "Reviewer_fuZ1", "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.", "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.\n2. On Line 98, is it intentionally “extract” or should it be “exact”?", "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?\n2. 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.\n3. 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.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "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.\n2. Certified minimax unlearning can be well extended to more general loss functions with reasonable generalization rates and deletion capacity results.\n3. 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.\n2. This work does not discuss the relationships of certified unlearning between STL model and minimax model theoretically (How are they different).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for his/her careful reading of our manuscript and numerous constructive remarks and questions.\n\n**Regarding 1) providing some preliminary results on some datasets and 2) discussing scenarios or applications:**\n\nThank you for the valuable suggestions. For 1), we will consider the machine unlearning under the pre-training and fine-tuning setting described in [1]. In this setting, all network parameters are fixed except for the loss layer, which will be fine-tuned on a dataset. During the fine-tuning stage, we effectively consider a SC-SC/C-C model. We will test the performance of our proposed methods with deletion requests made only from this dataset. For 2), we will add discussions about the applications (e.g., machine unlearning for GAN, fairness learning, RL, adversarial training) in the introduction section.\n\n[1] Golatkar, Aditya, et al. \"Mixed-privacy forgetting in deep networks.\" CVPR'21.\n\n**Regarding differences of certified unlearning between SLT model and minimax model theoretically:**\n\nThank you for your valuable suggestion and constructive comments. Due to the character limit, we provide detailed discussions of their differences in General Response. We will revise the introduction section and Sec 4.1 by adding these discussions to clearly convey the differences and challenges, as suggested by the reviewer.\n\n**Regarding advantage over differential privacy:**\n\nThe main advantage of certified unlearning over differential privacy is its better deletion capacity. This has two interpretations: First, for a given level of generalization performance, certified unlearning supports a larger number of data deletions while maintaining that generalization performance. Second, for a given number of deletions, certified unlearning yields better generalization performance than differential privacy. The intuition behind this is that certified unlearning has smaller sensitivity than differential privacy, and therefore requires less random perturbation to maintain utility.\n\n**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:**\n\nThank you for your constructive comment. We will add a paragraph to the introduction section discussing how our certified minimax unlearning algorithm can be applied to existing minimax models to facilitate effective unlearning with certified unlearning endurance, along with generalization and performance guarantees. \n\n**Regarding adding one or two sentences for each theorem or lemma about the clue to prove:**\n\nThank you for the valuable suggestion. We will provide the essential ideas and clues used to derive our main results including Lemma 1 to 3 and Theorem 2 to 4.\n\n**Miswrote \"exact\" on Line 98:**\n\nThank you for your careful reading and pointing out the miswriting. We will fix it and thoroughly proofread our paper to address other potential representational issues."}, {"review_id": "F2ekb2chEk", "reviewer": "Reviewer_kPH1", "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. ", "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. \n2. 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.\n3. 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). \n4. 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. \n\nI 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. ", "limitations": "Yes, they have sufficiently addressed the limitations of their works. ", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "1. This paper is well-written and structured. The narrative is very easy to follow, and the analysis is strong. \n2. The unlearning update is simple.\n3. While in a restricted setting, the analysis is coherent.\n4. Motivation is obviously, well done, given the connections to privacy. \n\nThis 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.\n2. In equation 6, you should specify that $m$ is the size of $U$.\n3. You miswrote Assumption 2 in Lemma 2.\n4. 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. \n\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for his/her careful reading of our manuscript and numerous constructive remarks and questions.\n\n**Notational mistake, size of $U$, and miswrote Assumption 2 in Lemma 2:**\n\nThank you for your careful reading and pointing out these issues. We will fix them and thoroughly proofread our paper to avoid other potential representational issues. \n\n**Regarding the SC-SC/C-C assumptions:**\n\nYes, we acknowledge that the SC-SC/C-C assumptions can limit the applicability of our proposed method. However,  we would like to emphasize that existing certified unlearning methods, especially those focused on establishing theoretical results, have largely focused on convex/strongly convex settings. As a nascent research field, we expect to develop advanced certified unlearning methods that rely on relaxed assumptions to be applicable to more general tasks in the future. That being said, it does not diminish the significance of our current work as the first certified minimax unlearning algorithms. \n\n\n**Regarding the set of memory variables $T$:**\n\nThe set of memory variables $T$ corresponds to variables that can be computed based on a trained model and memorized to facilitate the unlearning algorithms. When it comes to our certified minimax unlearning algorithm (e.g., Algorithm 2), this set contains the total Hessian matrices with respect to $\\omega$ and $\\nu$, which are inputs to Algorithm 2. We will formally define the set of memory variables for each algorithm in our paper, as suggested by the reviewer. \n\n**Regarding making variables in Lemma 2 and Theorem 5 more clear:**\n\nThank you for pointing it out. We will provide all necessary descriptions to clearly introduce the variables that appear in all lemmas and theorems. \n\n**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):**\n\nWe appreciate your suggestion and agree that it is a valuable direction for future research. We sincerely thank the reviewer for pointing us in this future direction.\n\n**Regarding inclusion of some small toy experiments:**\n\nWe appreciate your suggestion and agree that including toy experiments could strengthen our paper. We will consider machine unlearning under the pre-training and fine-tuning setting described in [1]. In this setting, all network parameters are fixed except for the loss layer, which will be fine-tuned on a dataset. During the fine-tuning stage, we effectively consider a SC-SC/C-C model. We will test the performance of our proposed methods with deletion requests made only from this dataset.\n\n[1] Golatkar, Aditya, et al. \"Mixed-privacy forgetting in deep networks.\" CVPR'21.\n\n**Missing a relevant citation:**\n\nThank you for pointing us to this missing reference. We will introduce and cite it in our paper."}]

Author rebuttal:
In this general response, we would like to first thank all reviewers for their careful review and valuable comments. Next, we provide the responses to two common comments that are shared by at least two reviewers. We provide the remaining point-to-point responses to each reviewer in our individual responses.

**Regarding the comparison of certified unlearning between minimax models and SLT, and additional challenges overcome in relation to prior works (Reviewers DtDD and fuZ1):**

Comparing the certified unlearning between minimax models and SLT, there are three main differences: 

1) Different designs of the unlearning update: minimax unlearning introduces the total Hessian (i.e., direct Hessian plus indirect Hessian) to sufficiently capture the data influence for unlearning, which is tailor-made to the minimax structure that has the inter-influencing min and max variables. In contrast, SLT unlearning requires only the direct Hessian (also known as the conventional Hessian). 
2) Different calibrations of the random perturbation: In order to properly calibrate the random perturbation to guarantee $(\epsilon,\delta)$-certified unlearning, it is essential to analyze the closeness upper bound (e.g., Lemma 1), which signifies the magnitude of the randomized perturbation. Three factors make the analysis of the closeness upper bounds very different between minimax unlearning and SLT unlearning: i) extra approximation terms are introduced during the derivation of the minimax unlearning update formula; ii) the minimax unlearning update utilizes the total Hessian-based unlearning update rather than the conventional Hessian; iii) the auxiliary functions (as defined in Definition 8) that arise due to the minimax structure appear in the analysis.
3) Different generalization performance metrics: SLT unlearning uses the excess population risk to measure generalization performance. In our minimax unlearning, we provide weak primal-dual risk in our paper. Additionally, we derive new generalization results in terms of the strong primal-dual risk during the rebuttal period.

Due to these differences, certified minimax unlearning presents additional challenges:
1) it is nontrivial to design the certified minimax unlearning update scheme, which requires a series of conversions and proper approximations to come up with a closed-form update in the form of the total Hessian-based complete Newton step. This challenge corresponds to Equations (9) to (11) in the paper and the development of Fact 1 in Appendix A.2. 

2) it is challenging to derive the closeness upper bound to guarantee certified minimax unlearning, which requires dealing with i) the extra approximation terms left out during the minimax unlearning update design, ii) the total Hessian that has different characteristics compared to the conventional Hessian, and iii) best response auxiliary functions that are unique to the minimax structure and do not appear in STL unlearning.

3) it was previously unknown whether it was possible to achieve ideal generalization performance and deletion capacity for certified minimax unlearning. Our work is the first to show that the rates of generalization and deletion capacity match the state-of-the-art rates derived previously for SLT unlearning, which are special cases of minimax unlearning. This indicates that certified minimax unlearning can indeed achieve ideal generalization performance and deletion capacity.

**Regarding strong primal-dual risk (Reviewers DtDD and sP3P):**

Thank you for your valuable suggestion. During the rebuttal period, we have derived new generalization performance results for our certified minimax unlearning algorithms in terms of strong primal-dual risk. In the general response below, we summarize our main results derived. In the attached PDF file, we provide more detailed results, along with a sketch of the proof highlighting the main differences in derivation compared to the weak primal-dual risk counterpart. Due to space limits, we provide the new results for Algorithm 2 as an example in this response. We will provide the counterpart results for all proposed algorithms to our paper.  
Denote $d=\max\\{d_1,d_2\\}$, under the same settings of Lemma 1, the population strong primal-dual risk for the certified minimax unlearning variables $(\omega^u,\nu^u)$ returned by Algorithm 2 is $ \triangle^s (\omega^u,\nu^u) = O \left( (L^3 \ell^3 \rho / \mu^6 + L^2 \ell^2/\mu^3)\cdot \frac{m^2 \sqrt{d\log(1/\delta)}}{n^2 \epsilon} + \frac{mL^2}{\mu n} + \frac{L^2\ell}{\mu^2 n}\right)$. Define the deletion capacity $m^{A,\bar A}_{\epsilon,\delta,\gamma}(d_1,d_2,n)$ as the maximum number of samples $U$ that can be unlearned while still ensuring the population strong primal-dual risk is at most $\gamma$.Then it suffices to let $m ^ { A,\bar A} _ {\epsilon,\delta,\gamma}(d_1,d_2,n) \geq c \cdot \frac{n\sqrt{\epsilon}}{(d\log(1/\delta))^{1/4}}$, where the constant $c$ depends on $L, l, \rho,$ and $\mu$ of the loss function $f$.



Meta-review: The paper studies the problem of unlearning in the (epsilon, delta)-unlearning model. It provides a new algorithm and shows that with n training samples and models with d parameters, one can unlearn up to O(n/d^{1/4}) samples, which is strictly better than the previous known result of O(n/sqrt{d}). Unlearning has attracted a lot of interest in recent years and the reviewers agree that the paper makes a nice contribution to the field. I would appreciate it if authors could incorporate reviewer suggestions in the camera-ready version.
Decision: Accept (poster)