Shuffling Gradient-Based Methods for Nonconvex-Concave Minimax Optimization

Authors: quoc  tran-dinh
trang h tran
lam m nguyen
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-13 21:20:15

Abstract: This paper aims at developing novel shuffling gradient-based methods for tackling two classes of minimax problems: nonconvex-linear and nonconvex-strongly concave settings. The first algorithm addresses the nonconvex-linear minimax model and achieves the state-of-the-art oracle complexity typically observed in nonconvex optimization.  It also employs a new shuffling estimator for the ``hyper-gradient'', departing from standard shuffling techniques in optimization. The second method consists of two variants: semi-shuffling and full-shuffling schemes.  These variants tackle the nonconvex-strongly concave minimax setting.  We establish their oracle complexity bounds under standard assumptions, which, to our best knowledge, are the best-known for this specific setting. Numerical examples demonstrate the performance of our algorithms and compare them with two other methods.  Our results show that the new methods achieve comparable performance with SGD, supporting the potential of incorporating shuffling strategies into minimax algorithms.

Main paper: 
 introduction: 
 Minimax problems arise in various applications across generative machine learning, game theory, robust optimization, online learning, and reinforcement learning (e.g., [1, 2, 3, 5, 12, 13, 17, 19, 21, 25, 35, 40] ). These models often involve stochastic settings or large finite-sum objective functions. To tackle these problems, existing methods frequently adapt stochastic gradient descent (SGD) principles to develop algorithms for solving the underlying minimax problems [4, 13] . For instance, in generative adversarial networks (GANs), early algorithms employed stochastic gradient descentascent methods where two routines, each using an SGD loop, ran iteratively [13] . However, practical implementations of SGD often incorporate shuffling strategies, as seen in popular deep learning libraries like TensorFlow and PyTorch. This has motivated recent research on developing shuffling techniques specifically for optimization algorithms [4, 5, 8, 16, 26, 32, 38] . Our work builds upon this trend by developing shuffling methods for two specific classes of minimax problems.Problem statement. In this paper, we study the following minimax optimization problem:EQUATION38th Conference on Neural Information Processing Systems (NeurIPS 2024).where f : R p ! R [ {+1} is a proper, closed, and convex function, H i : R p ⇥ R q ! R are smooth for all i 2 [n] := {1, 2, • • • , n}, and h : R q ! R [ {+1} is also a proper, closed, and convex function. In this paper, we will focus on two classes of problems in (1) , overlapped to each other.(NL) H i is nonconvex in w and linear in u as H i (w, u) := hF i (w), Kui for a given function F i : R p ! R m and a matrix K 2 R q⇥m for all i 2 [n] and (w, u) 2 dom (L). (NC) H i is nonconvex in w and H i (w, •) h(•) is strongly concave in u for all (w, u) 2 dom (L).Although (NC) looks more general than (NL), both cases can be overlapped, but one is not a special case of the other. Under these two settings, our approach will rely on a bilevel optimization approach, where the lower-level problem is to solve max u L(w, u), while the upper-level one is min w L(w, u).Challenges. The setting (NL) is a special case of stochastic nonconvex-concave minimax problems because the objective term H(w, u) := hF (w), Kui is linear in u. It is equivalent to the compositional model (CO) described below. However, if h is only merely convex and not strongly convex (e.g., the indicator of a standard simplex), then 0 in (CO) becomes nonsmooth regardless of F 's properties. This presents our first challenge. A natural approach to address this issue, as discussed in Section 2, is to smooth 0 . The second challenge arises from the composition between the outer function h ⇤ and the finite sum F (•) in (CO). Unlike standard finite-sum optimization, this composition prevents any direct use of existing techniques, requiring a novel approach for algorithmic development and analysis. The third challenge involves unbiased estimators for gradients or "hyper-gradients" in minimax problems. Most existing methods rely on unbiased estimators for objective gradients, with limited work exploring biased estimators. While biased estimators can be used, they require variance reduction properties (see, e.g., [10] ). The setting (NC) faces the same second and third challenges as the setting (NL). Additionally, when reformulating it as a minimization problem using a bilevel optimization approach (3), constructing a shuffling estimator for the "hyper-gradient" r 0 becomes unclear. This requires solving the lower-level maximization problem (2) . Therefore, it remains an open question whether shuffling gradient-type methods can be extended to this bilevel optimization approach to address (1) . In this paper, we address the following research question:Can we efficiently develop shuffling gradient methods to solve (1) for both (NL) and (NC) settings?Our attempt to tackle this question leads to a novel way of constructing shuffling estimators for the hyper-gradient r 0 or its smoothed counterpart. This allows us to develop two shuffling gradientbased algorithms with rigorous theoretical guarantees on oracle complexity, matching state-of-the-art complexity results in shuffling-type algorithms for nonconvex optimization.Related work. Shuffling optimization algorithms have gained significant attention in optimization and machine communities, demonstrating advantages over standard SGDs, see, e.g., [4, 5, 8, 16, 26, 32, 38] . Nevertheless, applying these techniques to minimax problems like (1) remains challenging, with limited existing literature (e.g., [3, 8, 11] ). Das et al. in [8] explored a specific case of (1) without nonsmooth terms f and h, assuming strong monotonicity and L-Lipschitz continuity of the gradient rH := [r w H, r u H] of the joint objective H. Their algorithm simplifies to a shuffling variant of fixed-point iteration or a gradient descent-ascent scheme, not applicable to our settings. Cho and Yun in [3] built upon [8] by relaxing the strong monotonicity to Polyak-Łojasiewicz (PŁ) conditions. This work is perhaps the most closely related one to our algorithm, Algorithm 2, for the (NC) setting. Note that the method in [3] exploits Nash's equilibrium perspective with a simultaneous update, which is different from our alternative update. Moreover, [3] only considers the noncomposite case with f = 0 and h = 0. Though we only focus on a nonconvex-strongly-concave setting (NC), our results here can be extended to the PŁ condition as in [3] . Very recently, Konstantinos et al. in [11] introduced shuffling extragradient methods for variational inequalities, which encompass convex-concave minimax problems as a special case. However, this also falls outside the scope of our work due to the nonconvexity of (1) in w. Again, all the existing works in [3, 8, 11] utilize a Nash's equilibrium perspective, while ours leverages a bilevel optimization technique. Besides, in contrast to our sampling-without-replacement approach, stochastic and randomized methods (i.e. using i.i.d. sampling strategies) have been extensively studied for minimax problems, see, e.g., [9, 14, 15, 18, 22, 23, 31, 37, 42] . A comprehensive comparison can be found, e.g., in [3] .Contribution. Our main contribution can be summarized as follows.(a) For setting (NL), we suggest to reformulate (1) into a compositional minimization and exploit a smoothing technique to treat this reformulation. We propose a new way of constructing shuffling estimators for the "hyper-gradient" r (cf. (10) ) and establish their properties.(b) We propose a novel shuffling gradient-based algorithm (cf. Algorithm 1) to approximate an ✏-KKT point of (1) for the setting (NL). Our method requires O(n✏ 3 ) evaluations of F i and rF i under the strong convexity of h, and O(n✏ 7/2 ) evaluations of F i and rF i without the strong convexity of h, for a desired accuracy ✏ > 0. (c) For setting (NC), we develop two variants of the shuffling gradient method: semi-shuffling and full-shuffling schemes (cf. Algorithm 2). The semi-shuffling variant combines both gradient ascent and shuffling gradient methods to construct a new algorithm, which requires O(n✏ 3 ) evaluations of both r w H i and r u H i . The full-shuffling scheme allows to perform both shuffling schemes on the maximization and the minimization alternatively, requiring either O(n✏ 3 ) or O(n✏ 4 ) evaluations of r u H i depending on our assumptions, while maintaining O(n✏ 3 ) evaluations of r w H i for a given desired accuracy ✏ > 0.If a random shuffling strategy is used in our algorithms, then the oracle complexity in all the cases presented above is improved by a factor of p n. Our settings (NL) and (NC) of ( 1) are different from existing works [3, 8, 11] , as we work with general nonconvexity in w, and linearity or [strong] concavity in u, and both f and h are possibly nonsmooth. Our algorithms are not reduced or similar to existing shuffling methods for optimization, but we use shuffling strategies to form estimators for the hyper-gradient r 0 in (5) . The oracle complexity in both settings (NL) and (NC) is similar to the ones in nonconvex optimization and in a special case of (1) from [3] (up to a constant factor).Paper outline. The rest of this paper is organized as follows. Section 2 presents our bilevel optimization approach to (1) and recalls necessary preliminary results. Section 3 develops our shuffling algorithm to solve the setting (NL) of ( 1) and establishes its convergence. Section 4 proposes new shuffling methods to solve the setting (NC) and investigates their convergence. Section 5 presents numerical experiments, while technical proofs and supporting results are deferred to Supp. Docs.Notations. For a function f , we use dom (f ) to denote its effective domain, and rf for its gradient or Jacobian. If f is convex, then rf denotes a subgradient, @f is its subdifferential, and prox f is its proximal operator. We use F t to denote (w 0 , w 1 , • • • , w t ), a -algebra generated by random vectors w 0 , w 1 , • • • , w t , E t [•] = E[•|F t ]Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? Answer: [Yes] Justification: Our claims made in the abstract reflects our contribution stated in the introduction, see the "Contribution" paragraph in the introduction section. Our contribution consists of two algorithms, Algorithm 1 and Algorithm 2, and their theoretical convergence guarantees stated in the subsequent theorems. Guidelines:• The answer NA means that the abstract and introduction do not include the claims made in the paper. • The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers. • The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings. • It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper. 
bilevel optimization approach and preliminary results: 
 Our approach relies on a bilevel optimization technique [9] in contrast to Nash's game viewpoint [24] , which treats the maximization as a lower level and the minimization as an upper level problem.The minimax model ( 1) is split into a lower-level (i.e. a follower) maximization problem of the form:EQUATIONFor 0 defined by (2), then the upper-level (i.e. the leader) minimization problem can be written asEQUATIONClearly, this approach is sequential, and only works if 0 is well-defined, i.e. ( 2) is globally solvable. Hence, the concavity of H(w, •) h(•) w.r.t. to u is crucial for this approach as stated below. However, this assumption can be relaxed to a global solvability of (2) combined with a PŁ condition as in [3] .Assumption 1 (Basic). Problems This assumption remains preliminary. To develop our algorithms, we will need more conditions on H i and possibly on f and h, which will be stated later. In addition, we can work with a sublevel setEQUATIONof 0 for a given initial point w 0 from our methods. If u ⇤ 0 (w) is uniquely well-defined for given w 2 L 0 (w 0 ), then by the well-known Danskin's theorem, 0 is differential at w and its gradient isEQUATIONWe adopt the term "hyper-gradient" from bilevel optimization to name r 0 in this paper.2.2 Technical assumptions and properties of 0 for nonconvex-linear setting (NL) (a) Compositional minimization formulation. If H i (w, u) := hF i (w), Kui as in setting (NL), then (1) is equivalently reformulated into the following nonconvex compositional minimization problem:EQUATIONwhere h ⇤ (v) := sup u {hv, ui h(u)}, the Fenchel conjugate of h, and 0 (w) = h ⇤ (K T F (w)). If h is not strongly convex, then h ⇤ is convex but possibly nonsmooth.(b) Technical assumptions. To develop our algorithms, we also need the following assumptions. Assumption 2. h is µ h -strongly convex with µ h 0, and dom(h) is bounded by M h < +1. Assumption 3 (For F i ). For setting (NL) with H i (w, u) := hF i (w), Kui (i 2 [n]), assume that (a) F i is continuously differentiable, and its Jacobian rF i is L Fi -Lipschitz continuous. (b) F i is also M Fi -Lipschitz continuous or equivalently, its Jacobian rF i is M Fi -bounded. (c) There exists a positive constant J 2 (0, +1) such thatEQUATIONAssumption 2 allows µ h = 0 that also covers the non-strong convexity of h. Assumption 3 is rather standard to develop gradient-based methods for solving (1) . Under Assumption 3, the finite-sum F is also M F -Lipschitz continuous and the Jacobian rF of F is also L F -Lipschitz continuous withEQUATIONCondition ( 6) can be relaxed to the form1 n P n i=1 krF i (w) rF (w)k 2  2 J + ⇥ J kr 0 (w)k 2for some ⇥ J 0, where r 0 is a [sub]gradient of 0 or (its smoothed approximation). Moreover, under Assumption 3, ifµ h > 0, then rh ⇤ is L h ⇤ -Lipschitz continuous with L h ⇤ := 1 µ h .Thus it is possible (see [9] ) to prove that 0 is differentiable, and r 0 is also L 0 -Lipschitz continuous withL 0 := M h kKkL F + M 2 F kKk 2 µ has a consequence of Lemma 4 when # 0 + in Supp. Doc. A.(c) Smoothing technique for lower-level maximization problem (2). If h is only merely convex (i.e. µ h = 0), then (2) may not be uniquely solvable, leading to the possible non-differentiability of 0 . Let us define the following convex function:EQUATIONThen, 0 in ( 2) or (CO) can be written as 0 (w) = 0 (F (w)) = 0EQUATIONwhere > 0 is a given smoothness parameter and b : R q ! R is a proper, closed, and 1-strongly convex function such that dom(h) ✓ dom(b). We also denoteD b := sup{krb(u)k : u 2 dom (h)}.In particular, if we choose b(u) := 1 2 ku ūk 2 for a fixed ū, then u ⇤ (v) = prox h/ (ū K T v).Using , problem (CO) can be approximated by its smoothed formulation:EQUATIONTo develop our method, one key step is to approximate the hyper-gradient of in (10) , whereEQUATIONThen, r is L -Lipschitz continuous withL := M h kKkL F + M 2 F kKk 2 µ h +(see Lemma 4).To develop our shuffling gradient-based algorithms for solving (1) under the nonconvex-stronglyconcave setting (NC), we impose the following assumptions. Assumption 4 (For H i ). H i for all i 2 [n] in (1) satisfies the following conditions:(a) For any given w such that (w, u)2 dom (H), H i (w, •) is µ H -strongly concave w.r.t. u. (b) rH i is (L w , L u )-Lipschitz continuous, i.e. for all (w, u), ( ŵ, û) 2 dom (H):EQUATION)(c) There exist two constants ⇥ w 0 and w 0 such that for (w, u) 2 dom (H), we haveEQUATION)There exist two constants ⇥ u 0 and u 0 such that for all (w, u) 2 dom (H), we haveEQUATIONAssumption 4(a) makes sure that our lower-level maximization of ( 1) is well-defined. Assumption 4(b) and (c) are standard in shuffling gradient-type methods as often seen in nonconvex optimization [9] . Lemma 1 (Smoothness of 0 ). Under Assumptions 2 and 4,u ⇤ 0 (•) in (2) is -Lipschitz continuous with  := Lu µ H +µ h . Moreover, r 0 in (5) is L 0 -Lipschitz continuous with L 0 := (1 + )L w .(a) Exact and approximate KKT points and stationary points. A pair (w ? , u ? ) 2 dom (L) is called a KKT (Karush-Kuhn-Tucker) point of (1) if 0 2 r w H(w ? , u ? ) + @f (w ? ) and 0 2 r u H(w ? , u ? ) + @h(u ? ).Given a tolerance ✏ > 0, our goal is to find an ✏-approximate KKT point ( b w, b u) of ( 1) defined asEQUATION)A vector w ? 2 dom ( 0 ) is said to be a stationary point of (3) ifEQUATION)Since f is possibly nonsmooth, we can define a stationary point of (3) via a gradient mapping as:EQUATIONwhere ⌘ > 0 is given. It is well-known that G ⌘ (w ? ) = 0 iff w ? is a stationary point of (3). Again, since we cannot exactly compute w ? , we expect to find an ✏-stationary point bw T of (3) such that E ⇥ kG ⌘ ( b w T )k 2 ⇤  ✏ 2 for a given tolerance ✏ > 0.(b) Constructing an approximate stationary point and KKT point from algorithms. Our algorithms below generate a sequence { e w t } T t 0 such that 1T +1 P T t=0 E ⇥ kG ⌘ ( e w t )k 2 ⇤  ✏ 2 .Hence, we construct an ✏-stationary point b w T using one of the following two options:EQUATIONEQUATIONClearly, we haveE ⇥ kG ⌘ ( b w T )k 2 ⇤  1 T +1 P T t=0 E ⇥ kG ⌘ ( e w t )k 2 ⇤  ✏ 2 .We need the following result.Lemma 2. (a) If (w ? , u ? ) is a KKT point of (1), then w ? is a stationary point of (3). Conversely, if w ? is a stationary point of (3), then (w Lemma 2 allows us to construct an ✏-approximate KKT point (w T , u T ) of ( 1) from an ✏-stationary point b w T of either (3) or its smoothed problem (10) , where ✏ = O(max{✏, }).? , u ⇤ 0 (w ? )) is a KKT point of (1). (b) If b w T is an ✏-stationary point of (3) and r 0 is L 0 -Lipschitz continuous, then (w T , u T ) is an ✏-KKT point ofTo handle the nonsmooth term f of (1) in our algorithms we require one more condition as in [5] . Assumption 5. Let be defined by (10) , which reduces to 0 given by (2) as # 0 + , and G ⌘ be defined by (18) . Assume that there exist two constants ⇤ 0 1 and ⇤ 1 0 such that:EQUATIONIf f = 0, then G ⌘ (w) ⌘ r (w), and Assumption 5 automatically holds with ⇤ 0 = 1 and ⇤ 1 = 0.If f 6 = 0, then it is crucial to have ⇤ 0 1 in (20) . Let us consider two examples to see why?(i) If f is M f -Lipschitz continuous (e.g., `1-norm), then (20) also holds with ⇤ 0 := 1 + ⌫ > 1 and ⇤ 1 := 1+⌫ ⌫ M f for a given ⌫ > 0. (ii ) If f = W ,Question: Does the paper discuss the limitations of the work performed by the authors? Answer: [Yes] Justification: This paper has limitation as it only focuses on two classes of minimax problems defined in (1) . Yes, we only consider two classes of minimax problems: nonconvex-linear (NL) and convex-strongly concave (NC), covered by our assumption, Assumptions 1 to 5. Guidelines:• The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper. • The authors are encouraged to create a separate "Limitations" section in their paper.• The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be. • The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach.For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon. • The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size. • If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness. • While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
shuffling gradient method for nonconvex-linear minimax problems: 
 We first propose a new construction using shuffling techniques to approximate the true gradient r in (11) for any 0. Next, we propose our algorithm and analyze its convergence.Challenges. To evaluate r (w) in ( 11), we need to evaluate both rF (w) and F (w) at each w. However, in SGD or shuffling gradient methods, we want to approximate both quantities at each iteration. Note that this gradient can be written in a finite-sum (11) ), but every summand requires r (F (w)), which involves the full evaluation of F .1 n P n i=1 rF i (w) T r (F (w)) (seeOur estimators. Let F ⇡ (t) (i) (w (t) i 1 ) and rF ⇡(t) (i) (w (t)i 1 ) be the function value and the Jacobian component evaluated at w(t) i 1 respectively for i 2 [n], where ⇡ (t) = (⇡ (t) (1), ⇡ (t) (2), • • • , ⇡ (t) (n)) and ⇡(t) = (⇡ (t) (1), ⇡(t) (2), • • • , ⇡(t) (n)) are two permutations of [n] := {1, 2, • • • , n}.We want to use these quantities to approximate the function value F (w (t) 0 ) and its Jacobian rF (w(t) 0 ) of F at w (t)0 , respectively, where w (t) 0 the iterate vector at the beginning of each epoch t.For function value F (w (t) 0 ), we suggest the following approximation at each inner iteration i 2 [n]:EQUATION)Alternative to (21) , for all i 2 [n], we can simply choose another option:Option 2:EQUATIONFor Jacobian rF (w(t)0 ), we suggest to use the following standard shuffling estimator for all i 2 [n]:EQUATIONFor F (t) i from (21) (or ( 22)) and for rF (t) i from ( 23), we form an approximation of r (wEQUATION)Discussion. The estimatorF (t) i for F requires n i more function evaluations F ⇡ (t) (j) (w (t) 0 ) at each epoch t.The first option (21) for F uses 2n function evaluations F i , while the second one in (22) only needs n function evaluations at each epoch t 0. However, (21) uses the most updated information up to the inner iteration i compared to (22) , which is expected to perform better. The Jacobian estimator rF (t) i is standard and only uses one sample or a mini-batch at each iteration i.We propose Algorithm 1, a shuffling gradient-type method, to approximate a stationary point of (10) .Discussion. First, the cost per epoch of Algorithm 1 consists of either 2n or n function evaluations F i , and n Jacobian evaluations rF i . Compare to standard shuffling gradient-type methods, e.g., in [8] , Algorithm 1 has either n more evaluations of F i or the same cost. Second, when implementing Algorithm 1 (Shuffling Proximal Gradient-Based Algorithm for Solving (10)) Now, we are ready to state the convergence result of Algorithm 1 in a short version: Theorem 1. The full version of this theorem is Theorem 6, which can be found in Supp. Doc. B. Theorem 1. Suppose that Assumptions 1, 2, 3, and 5 holds for the setting (NL) of (1) and ✏ > 0 is a sufficiently small tolerance. Let { e w t } be generated by Algorithm 1 after T = O(✏ 3 ) epochs using arbitrarily permutations ⇡ (t) and ⇡(t) and a learning rate ⌘ t = ⌘ := O(✏) (see Theorem 6 in Supp. Doc. B for the exact formulas of T and ⌘). Then, we have 1T +1 P T t=0 kG ⌘t ( e w t )k 2  ✏ 2 .Alternatively, if { e w t } is generated by Algorithm 1 after T := O(n 1/2 ✏ 3 ) epochs using two random and independent permutations ⇡ (t) and ⇡(t) and a learning rate ⌘ t = ⌘ := O(n 1/2 ✏) (see Theorem 6 in Supp. Doc. B for the exact formulas). Then, we have 1T +1 P T t=0 E[kG ⌘t ( e w t )k 2 ]  ✏ 2 .Our first goal is to approximate a stationary point w ? of (CO) as E[kG ⌘ ( b w)k 2 ]  ✏ 2 , while Algorithm 1 only provides an ✏-stationary of (10) . For a proper choice of , it is also an ✏-stationary point of (3). Corollary 1. Let b w T defined by (19) be generated from { e w t } of Algorithm 1. Under the conditions of Theorem 1 and any permutations ⇡ (t) and ⇡(t) , the following statements hold.(a) If h is µ h -strongly convex with µ h > 0, then we can set = 0, and Algorithm 1 requires O(n✏ 3 ) evaluations of F i and rF i to achieve an ✏-stationary b w T of (3). (b) If h is only convex (i.e. µ h = 0), then we can set := O(✏), and Algorithm 1 needs O(n✏ 7/2 ) evaluations of F i and rF i to achieve an ✏-stationary b w T of (3).If, in addition, ⇡ (t) and ⇡(t) are sampled uniformly at random without replacement and independently, and ⇤ 1 = O(n 1 ), then the numbers of evaluations of F i and rF i are reduced by a factor of p n.• The answer NA means that the paper does not include experiments.• The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper. • The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions). • The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.) • The assumptions made should be given (e.g., Normally distributed errors).• It should be clear whether the error bar is the standard deviation or the standard error of the mean. Justification: Our data is publicly available online from LIBSVM.Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 
shuffling method for nonconvex-strongly concave minimax problems: 
 In this section, we develop shuffling gradient-based methods to solve (1) under the nonconvexstrongly concave setting (NC). Since this setting does not cover the nonconvex-linear setting (NL) in Section 3 as a special case, we need to treat it separately using different ideas and proof techniques.Unlike the linear case with H i (w, u) = hF i (w), Kui in Section 3, we cannot generally compute the solution u ⇤ 0 ( e w t 1 ) in ( 2) exactly for a given e w t 1 . We can only approximate u ⇤ 0 ( e w t 1 ) by some e u t . This leads to another level of inexactness in an approximate "hyper-gradient" e r 0 (w(t) i 1 )defined by e r 0 (wEQUATIONThere are different options to approximate u ⇤ 0 ( e w t 1 ). We propose two options below, but other choices are possible, including accelerated gradient ascent methods and stochastic algorithms [6, 20] .(a 1 ) Gradient ascent scheme for the lower-level problem. We apply a standard gradient ascent scheme to update e u t : Starting from s = 0 with uEQUATIONfor a given learning rate ⌘t > 0. Then, we finally output e u t := b u (t)S to approximate u ⇤ 0 ( e w t 1 ).To make our method more flexible, we allow to perform either only one iteration (i.e. S = 1) or multiple iterations (i.e. S > 1) of ( 26). Each iteration s requires n evaluations of r u H i .(a 2 ) Shuffling gradient ascent scheme for the lower-level problem. We can also construct e u t by a shuffling gradient ascent scheme. Again, we allow to run either only one epoch (i.e. S = 1) or multiple epochs (i.e. S > 1) of the shuffling algorithm to update e u t , leading to the following scheme:Starting from s := 1 with b u (t) 0 := e u t 1 , at each epoch s = 1, 2, • • • , S, having b u (t)s 1 , we generate a permutation ⇡ (s,t) of [n] and run a shuffling gradient ascent scheme as 8 > > > > > < > > > > > : u (s,t) 0 := b u (t) s 1 , For i = 1, 2, • • • , n, update u (s,t) i := u (s,t) i 1 + ⌘t n r u H ⇡ (s,t) (i) ( e w t 1 , u (s,t) i 1 ), b u (t) s := prox ⌘th (u (s,t) n ).For i = 1, 2, • • • , n, update w (t) i := w (t) i 1⌘t n e r 0 (wEQUATIONThese two steps (26) (or ( 27)) in u and (28) in w are implemented alternatively for t = 1, • • • , T .(c) The full algorithm. Combining both steps (26) (or (27) ) and ( 28), we can present an alternating shuffling proximal gradient algorithm for solving (1) as in Algorithm 2.Algorithm 2 (Alternating Shuffling Proximal Gradient Algorithm for Solving (1) under setting (NC))1: Initialization: Choose an initial point ( e w 0 , e u 0 ) 2 dom (L).2: for t = 1, 2, • • • , T do 3:Compute e u t using either (26) or (27) . 5:for i = 1, • • • , n do 6:Evaluate e r 0 (w(t) i 1 ) := r w H ⇡(t) (i) (w (t)i 1 , e u t ). ). Moreover, Algorithm 1 solves the smoothed problem (10) of (3), while Algorithm 2 directly solves (3). Depending on the choice of method to approximate u ⇤ 0 ( e w t 1 ), we obtain different variants of Algorithm 2. We have proposed two variants:• Semi-shuffling variant: We use (26) for computing e u t to approximate u ⇤ 0 ( e w t 1 ). • Full-shuffling variant: We use (27) for computing e u t to approximate u ⇤ 0 ( e w t 1 ).Note that Algorithm 2 works in an alternative manner, where it approximates u ⇤ 0 ( e w t 1 ) up to a certain accuracy before updating e w t . This alternating update is very natural and has been widely applied to solve minimax optimization as well as bilevel optimization problems, see, e.g., [1, 9, 13] .Now, we state the convergence of both variants of Algorithm 2: semi-shuffling and full-shuffling variants. The full proof of the following theorems can be found in Supp. Doc. C.(a) Convergence of the semi-shuffling variant. Our first result is as follows. Theorem 2. Suppose that Assumptions 1, 2, 4, and 5 hold for (1), and G ⌘ is defined by (18) .Let {( e w t , e u t )} be generated by Algorithm 2 using the gradient ascent scheme (26) with⌘ := O(✏) explicitly given in Theorem 8 of Supp. Doc. C, ⌘ 2 (0, 2 Lu+µ h ], S := O 1 ⌘ µ h + 4Luµ H Lu+µ H 1 = O(1),and T := O(✏ 3 ) explicitly given in Theorem 8. Then, we have 1T +1 P T t=0 kG ⌘ ( e w t )k 2  ✏ 2 .Consequently, Algorithm 2 requires O(n✏ 3 ) evaluations of both r w H i and r u H i to achieve an ✏-stationary point b w T of (3) computed by (19) .Note that Theorem 2 holds for both S > 1 and S = 1 (i.e. we perform only one iteration of ( 26)).(b) Convergence of the full-shuffling variant -The case S > 1 with multiple epochs. We state our results for two separated cases: only H i is µ H -strongly convex, and only h is µ h -strongly convex. Theorem 3 (Strong convexity of H i ). Suppose that Assumptions 1, 2, 4, and 5 hold, andH i is µ H -strongly concave with µ H > 0 for i 2 [n], but h is only merely convex.Let {( e w t , e u t )} be generated by Algorithm 2 using S epochs of the shuffling routine ( 27) and fixed learning rates ⌘ t = ⌘ := O(✏) as given in Theorem 8 of Supp. Doc. C for a given ✏ > 0, ⌘t := ⌘ = O(✏), S := ⌅ ln(7/2)µ H ⌘ ⇧, and T := O(✏ 3 ). Then, we have 1T +1 P T t=0 kG ⌘ ( e w t )k 2  ✏ 2 .Consequently, Algorithm 2 requires O(n✏ 3 ) evaluations of r w H i and O(n✏ 4 ) evaluations of r u H i to achieve an ✏-stationary point b w T of (3) computed by (19) . Theorem 4 (Strong convexity of h). Suppose that Assumptions 1, 2, 4, and 5 hold for (1), and h is µ h -strongly convex with µ h > 0, but H i is only merely concave for all i 2 [n]. Then, under the same settings as in Theorem 3, but with S := ⌅ ln(7/2)µ h ⌘ ⇧, the conclusions of Theorem 3 still hold.(c) Convergence of the full-shuffling variant -The case S = 1 with one epoch. Both Theorems 3 and 4 require O(n✏ 4 ) evaluations of r u H i . To improve this complexity, we need two additional assumptions but can perform only one epoch of ( 27), i.e. S = 1.Assumption 6. Let Ĝ⌘ (u) := ⌘ 1 (u prox ⌘h (u + ⌘r u H(w, u))) be the gradient mapping of (w, •) := H(w, •) + h(•). Assume that there exist ⇤0 1 and ⇤1 0 such thatEQUATION)Clearly, if h = 0, then Ĝ⌘ (u) = r u H(w, u) and ( 20) automatically holds for ⇤0 = 1 and ⇤1 = 0. Assumption 6 is similar to Assumption 5, and it is required to handle the prox operator of h in (27) . Assumption 7. For f in (1), there exists L f 0 such thatEQUATIONClearly, if f is L f -smooth, then (30) holds. If f is also convex, then (30) implies that f is L f -smooth.Under these additional assumptions, we have the following result. Theorem 5. Suppose that Assumptions 1, 2, 4, 5, 6, and 7 hold and G ⌘ is defined by (18) .Let {( e w t , e u t )} be generated by Algorithm 2 using one epoch (S = 1) of the shuffling routine (27) , and fixed learning rates ⌘ t = ⌘ := O(✏) as in Theorem 9 of Supp. Doc. C for a given ✏ > 0, ⌘t := ⌘ = 30 2 ⌘, and T := O(✏ 3 ), where  := Lu µ H +µ h . Then, we have 1T +1 P T t=0 kG ⌘ ( e w t )k 2  ✏ 2 .Consequently, Algorithm 2 requires O(n✏ 3 ) evaluations of both r w H i and of r u H i to achieve an ✏-stationary point b w T of (3) computed by (19) .Similar to Algorithm 1, if ⇡ (s,t) and ⇡(t) are generated randomly and independently, ⇤ 1 = O(1/n), and ⇤1 = O(1/n), then our complexity stated above can be improved by a factor of p n. Nevertheless, we omit this analysis. Finally, we can combine each Theorem 2, 3, 4 or 5 and Lemma 2 to construct an ✏-KKT point of (1). Theorem 5 has a better complexity than Theorems 3 and 4, but requires stronger assumptions. Algorithm 2 is also different from the one in [3] both in terms of algorithmic form and the underlying problem to be solved, while achieving the same oracle complexity. 
numerical experiments: 
 We perform some experiments to illustrate Algorithm 1 and compare it with two existing and related algorithms. Further details and additional experiments can be found in Supp. Doc. D.We consider the following regularized stochastic minimax problem studied, e.g., in [9, 33] :EQUATIONwhere F i,j : R p ⇥ ⌦ ! R + can be viewed as the loss of the j-th model for data point i 2 [n]. If we define 0 (v) := max 1jm {v j } and f (w) := 2 kwk 2 , then (31) can be reformulated into (3). Since v j 0, we have 0 (v) := max 1jm {v j } = kvk 1 = max kuk11 hv, ui, which is nonsmooth. Thus we can smooth 0 as (v) := max kuk11 {hv, ui ( /2)kuk 2 } using b(u) := 1 2 kuk 2 . Here, we apply our problem (31) to solve a model selection problem in binary classification with nonnegative nonconvex losses, see, e.g., [41] . Each function F i,j belongs to 4 different nonconvex losses (m = 4): 2 , and F i,4 (w, ⇠) := log(1 + exp( b i ha i , wi)) (see [41] for more details), where (a i , b i ) represents data samples.F i,1 (w, ⇠) := 1 tanh(b i ha i , wi), F i,2 (w, ⇠) := log(1 + exp( b i ha i , wi)) log(1 + exp( b i ha i , wi 1)), F i,3 (w, ⇠) := (1 1/(exp( b i ha i , wi) + 1))We implement 4 algorithms: our SGM with 2 options, SGD from [10] , and Prox-Linear from [11] . We test these algorithms on two datasets from LIBSVM [6] . We set := 10 4 and update the smooothing parameter t as t := 1 2(t+1) 1/3 . The learning rate ⌘ for all algorithms is finely tuned from {100, 50, 10, 5, 1, 0.5, 0.1, 0.05, 0.01, 0.001, 0.0001}, and the results are shown in Figure 1 for w8a and rcv1 datasets using k b = 32 blocks. The details of this experiment is given in Supp. Doc. D. As shown in Figure 1 , the two variants of our SGM have a comparable performance with SGD and Prox-Linear, providing supportive evidence for using shuffling strategies in minimax algorithms. 
conclusions: 
 This work explores a bilevel optimization approach to address two prevalent classes of nonconvexconcave minimax problems. These problems find numerous applications in practice, including robust learning and generative AIs. Motivated by the widespread use of shuffling strategies in implementing gradient-based methods within the machine learning community, we develop novel shuffling-based algorithms for solving these problems under standard assumptions. The first algorithm uses a nonstandard shuffling strategy and achieves the state-of-the-art oracle complexity typically observed in nonconvex optimization. The second algorithm is also new, flexible, and offers a promising possibility for further exploration. Our results are expected to provide theoretical justification for incorporating shuffling strategies into minimax optimization algorithms, especially in nonconvex settings. 
broader impacts: 
 Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?Answer: [NA] Justification: We do not yet know if our paper has an immediate broader impact. However, since our problems and our algorithms are sufficiently general, we hope they will create broader impacts. Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations. • The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)? Answer: [NA] Justification: We do not have our own real data or specific model that has a high risk for misuse.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort. 12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected? Answer: [NA] Justification: Our code is open-source and will be made available online under a standard public license. Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. • We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution. • For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review. 
 
 Appendix:  


Decision: Stochastic methods for minimax optimization using traditional IID sampling strategies are well-studied. There is less work on shuffling methods for minimax optimization which may perform better in practice. The authors design shuffling based algorithms for nonconvex-linear minimax and nonconvex-strongly concave minimax problems, and provide worst-case analysis of their proposed algorithms for finding stationary points. In the former setting their algorithm matches the best-known oracle complexities (achieved with IID sampling strategies). The authors tested one of their algorithms numerically. While it performed well in the author’s experiments, the test problems could have been more compelling and the competing algorithms stronger. 

Comments for the authors:

While you state the minimax setting is well-studied, it would be helpful if you provided a paragraph in the related work pointing to papers that study the NL and NC setting using IID sampling strategies. In particular, it would have been nice if there were clear comparisons between the techniques. A table as reviewer 4w6E suggested would be helpful as well.

Please be careful about how you describe IID sampling strategies, sometimes you describe it as SGD which is confusing. Typically people do not use SGD in this way. For example, often people say “SGD with Random Shuffling”, etc. In particular, one page the phrase “that the new methods achieve comparable performance to SGD” should be rephrased as our shuffling based algorithm achieves comparable performance to methods that use IID sampling strategies. This is an issue throughout the paper including in the labels on the numerical results.

Phi_0 is introduced on page 2 with no description but not defined until page 3

Reviews: review: paper_summary: paper_summary: The paper presents new shuffling gradient-based methods for solving two classes of nonconvex-concave minimax optimization problems: nonconvex-linear and nonconvex-strongly concave settings. 

The first algorithm is designed for the nonconvex-linear setting and achieves state-of-the-art oracle complexity, employing a new shuffling estimator for the hyper-gradient. 

The second method introduces semi-shuffling and full-shuffling schemes for the nonconvex-strongly concave setting, establishing their oracle complexity bounds for the first time. 

Numerical examples are provided to demonstrate the performance of the proposed algorithms.
strength_weakness: strength_weakness: 1. **Complexity Comparison with Existing Works**. The authors are encouraged to present a comparative table that delineates the oracle complexity of their proposed methods alongside that of existing works, including standard nonshuffling methods. This side-by-side comparison should aim to explicitly demonstrate the theoretical advantages of their methods.

2. **Shuffling Methods vs. Nonshuffling Methods**. The paper should discuss the distinctions between shuffling methods and traditional nonshuffling approaches. Specically, it is better to clarify whether shuffling methods consistently yield superior performance over nonshuffling methods theoretically.

3. **Numerical Experiments Expansion**. While the experiments have been conducted on synthetic datasets and small-scale datasets, which is customary for theoretical papers, the scope of empirical validation could be enhanced. It would be much better if the authors could extend their experiments to include large-scale datasets.
questions: questions: See above.
limitations: limitations: Yes
paper_summary: paper_summary: This paper proposes shuffling gradient-based methods for addressing two classes of minimax optimization problems: nonconvex-linear and nonconvex-strongly concave settings. The first algorithm focuses on the nonconvex-linear minimax setting and the second algorithm, consisting of semi-shuffling and full-shuffling schemes, focuses on the nonconvex-strongly concave minimax setting. The authors establish oracle complexity bounds for these algorithms under some standard assumptions. Numerical experiments are conducted.
strength_weakness: strength_weakness: The proposed Algorithm 1 requires solving a maximization problem at each iteration, which can be computationally expensive.

The numerical experiment section is quite weak. First, only Algorithm 1 is tested, with no results related to Algorithm 2. Second, only one minimax model is tested. More complex and popular minimax models should be included, and state-of-the-art competitors should be used to evaluate the performance of the proposed methods.

Typo in Line 187 and Line 459: $M_f \rightarrow M_f^2$
questions: questions: What are the advantages of the proposed methods in this paper, given the introduction of the semi-shuffling and full-shuffling schemes? Do they have a better convergence rate or sample complexity compared to existing methods?
limitations: limitations: yes
paper_summary: paper_summary: This paper focuses on nonconvex-concave, finite-sum (stochastic) minimax problems with possibly nonsmooth regularization. Aiming to find $\epsilon$-stationary points, the paper proposes shuffling-based proximal gradient descent-ascent algorithms and verifies gradient computation complexity upper bounds via a bilevel optimization perspective. The results consider various settings, such as (1) the nonconvex-linear (NL) case with either strongly convex or convex $h$, each requiring $\mathcal{O}(n \epsilon^{-3})$ and  $\mathcal{O}(n \epsilon^{-7/2})$ gradient evaluations, respectively, and (2) the nonconvex-strongly-concave (NS) case with smoothness assumptions, where semi-shuffling requires $\mathcal{O}(n \epsilon^{-3})$ while full-shuffling requires (naively) $\mathcal{O}(n \epsilon^{-4})$ gradient evaluations. The paper contains proofs of the convergence theorems and supporting numerical experiments.
strength_weakness: strength_weakness: * Despite that the novelty of this work would be in the fact that the results apply for broader settings than previous literature rather than obtaining *faster* convergence under similar settings, the paper still should have included a fair, more detailed comparison with previous work and illustrated how the gradient evaluation complexity becomes different from settings with stronger assumptions. The current draft does not contain any meaningful quantitative comparison with previous work.
* In particular, I don’t think that the settings in [2] are different from the results for the (NS) setting. Apart from the fact that the objective function does not contain $f$ and $h$, the assumptions used in Theorem 1 of [1] (Assumptions 1-4) and the NS setting seem to be nearly identical, and the goal of finding $\epsilon$-stationary points also seem to be equivalent. (In fact, for the variable $u$ the PŁ assumption is weaker than strong concavity.) In terms of the convergence rates, Theorem 1 of [1] requires only $\mathcal{O} (n \epsilon^{-2} + n^{1/2} \epsilon^{-3})$ gradient evaluations, which is smaller than $\mathcal{O} (n \epsilon^{-3})$. The authors should have at least explained how introducing $f, h$ changes the difficulty of the problem, or given any other reasons why one could prefer the bilevel optimization framework over the simple SGDA algorithm as in [1].
questions: questions: - Why is it necessary to use bilevel optimization, i.e., update $n$ steps of $w$ and then $n$ steps of $v$, instead of iteration-wise updates? Also, am I right that the results for the (NS) settings are weaker than that of [2] at least when $f, h = 0$? Is there a particular reason why the weaker convergence rates are inevitable if we consider $f, h$?
- Some technical parts of the algorithms are brought from previous work, such as the use of $\Phi_{\gamma}$ inspired by Yang et al., 2020 [3]. Some other parts look new, such as the placement of the proximal steps considering $f$ and $h$ and the variants of algorithms like choosing between (21), (22) in Algorithm 1 and (26), (27) in Algorithm 2. I am curious about the motivations of the new components of the algorithms, especially considering the different types of shuffling techniques I mentioned last—whether these have clear motivations or are more like artifacts of the proof techniques, if there were similar approaches in minimization problems, etc.

- Light question: Would it be able to relax the strongly concave case to weaker PŁ-type assumptions, or consider alternating type updates as in [2]? Moreover, is it possible to compare the presented results for minimax problems with nonconvex, nonsmooth *minimization* as in Cutkosky et al., 2023 [4]?
- Light question: Are there examples of when the nonconvex-linear (NL) setting could be of interest in practice?
- Minor: Why are there two bibliographies, and why are the contents different? It seems that the one at the end of the appendix has the correct numbers.
limitations: limitations: There seems to be no potential negative societal impact.
paper_summary: paper_summary: This work propose shuffling gradient-based methods for nonconvex-linear and nonconvex-strongly convex minimax optimization and obtain complexity results.
strength_weakness: strength_weakness: The contribution is in general combinational, with slightly more techniques such as smoothing and shuffling-based function evaluations. Also, comparison with previous stochastic algorithms for minimax optimization and shuffling for nonconvex optimization is lacking, as shown in question 1 below.
questions: questions: (1) You could compare your complexity results (Theorem 2) with previous stochastic gradient-based minimax optimization works (e.g. [a]) and shuffling for nonconvex optimization (e.g. [b]). 

[a] Lin, T., Jin, C., \& Jordan, M. (2020, November). On gradient descent ascent for nonconvex-concave minimax problems. In International Conference on Machine Learning (pp. 6083-6093). PMLR.

[b] Nguyen, L. M., Tran-Dinh, Q., Phan, D. T., Nguyen, P. H., \& Van Dijk, M. (2021). A unified convergence analysis for shuffling-type gradient methods. Journal of Machine Learning Research, 22(207), 1-44.

(2) At the bottom of page 1, for problem (NL), it looks possible to remove matrix $K$ and use $F_i:\mathbb{R}^p\to \mathbb{R}^q$, since $\langle F_i(w),Ku\rangle=\langle K^{\top}F_i(w),u\rangle$ and we could replace $K^{\top}F_i(w)\in \mathbb{R}^q$ with $F_i(w)\in \mathbb{R}^q$. 

(3) In Assumption 2, do you mean for any $v\in {\rm dom}(h)$, $||v||_2\le M_h$? 

(4) In "Condition (6) can be relaxed to the form $\frac{1}{n} \sum_{i=1}^n||\nabla F_i(w)-\nabla F(w)||^2 \leq \sigma_J^2+\Theta_J||\nabla \Phi_0(w)||^2$", should $\Phi_0$ be $F$? 

(5) After Assumption 5, ``If $f=0$, then $\mathcal{G} _ {\eta}(w)\equiv\nabla\Phi_{\gamma}(w)$''. Should it be $\nabla\Phi_0(w)$ instead of $\nabla\Phi_{\gamma}(w)$, since the definition of $\mathcal{G} _ {\eta}(w)$ in eq. (18) involves $\nabla\Phi_0(w)$ not $\nabla\Phi _ {\gamma}(w)$? Or you might consider defining $\mathcal{G} _ {\eta,\gamma}(w)$ with $\nabla\Phi_0(w)$ replaced by $\nabla\Phi _ {\gamma}(w)$, such that $\epsilon$-stationary point of (3) and that of (10) in Lemma 2 correspond to $\mathcal{G} _ {\eta,0}(w)$ and $\mathcal{G} _ {\eta,\gamma}(w)$ respectively. 

(6) I found that Eq. (21) (Option 1) needs to save {$F_{\pi^{(t)}(j)(w_0^{(t)})}$}$_{j=1}^n$ to avoid repeated evaluation of these $n$ values. Yes? 

(7) Line 255: "fix number" $\rightarrow$ "fixed number". 

(8) At the end of Theorem 2, do you mean to change one of the $\nabla_w\mathcal{H}_i$ into $\nabla_u\mathcal{H}_i$? It seems that the complexity of semi-shuffling is bettter than full-shuffling. Then what's the advantage of full-shuffling?
limitations: limitations: The checklist mentions the limitation that this work only focuses on nonconvex-linear and nonconvex-strongly convex minimax optimization, and says "We do not yet know if our paper has an immediate broader impact. However, since our problems and our algorithms are sufficiently general, we hope they will create broader impacts." I agree with both of them.

Comments: title: Thank you!
Thank you very much for your support!
Follow up
Thank you!
Follow up on the rebuttal
Follow up on the rebuttal
Thank you for your support!
Reviewer QEyv is satisfied with the authors' response and will increase rating to 7
comment: Dear Area Chair and Reviewers,

We would like to thank the AC and the reviewers for your time and effort in handling and reviewing our paper.

Best regards,

Authors
Dear Reviewer czC8,

Thank you very much for your feedback and support! 

Best regards,

Authors
Thank you for the detailed response to my questions. I will raise my score accordingly.
Dear Reviewer czC8,

Since the Author-Reviewer discussion phase will end in two days, we would like to follow up and discuss with you. Please do not hesitate to contact us if there are additional answers or explanations that we can make to clarify our paper within this discussion period. We appreciate your timely response, as it would provide us with an opportunity to address any remaining questions.

If your concerns are all properly addressed, we really hope that the reviewer positively re-evaluates our work. We appreciate your inputs and we thank you for your time spent reviewing this paper.

Best regards,

Authors
Dear Reviewer jEDb,

We thank you very much for your time and your appreciation. Your support is meaningful for us to explore this direction.

Thank you again! 

Best regards,

Authors
Thank you for your detailed and precise answers.
Dear Reviewer jEDb,

We hope our responses answer all your questions!

In case you need any remaining clarifications, we would be more than happy to reply. Please let us know your thoughts as soon as you can (within this discussion period). If your questions are all properly addressed, we really hope that you consider increasing your score to support our work.

Regards,

Authors
Dear Reviewer czC8,

We hope our responses answer all your questions!

In case you need any remaining clarifications, we would be more than happy to reply. Please let us know your thoughts as soon as you can (within this discussion period). If your questions are all properly addressed, we really hope that you consider increasing your score to support our work.

Regards,

Authors
Dear Reviewer QEyv, 

We are glad that you are satisfied with our response and increase the rating score. This is very encouraging!

Thank you very much for your support! 

Best regards,

Authors
Reviewer QEyv is satisfied with the authors' response and will increase rating to 7.