Shuffling Gradient-Based Methods for Nonconvex-Concave Minimax Optimization
Authors: Quoc Tran-Dinh
Trang H. Tran
Lam M. Nguyen
Venue: NeurIPS 2024 poster (2024)
Keywords: Shuffling gradient method; nonconvex-concave minimax problem; oracle complexity; sample without replacement
Primary area: optimization
TL;DR: This paper develops two novel shuffling-based algorithms to solve two classes of nonconvex-concave minimax problems that have provable convergence guarantees.

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.

Shuffling Gradient-Based Methods for Nonconvex-Concave Minimax Optimization
Quoe Tran-Dinh
Trang H. Tran
Department of Statistics and Operations Research The University of North Carolina Chapel Hill
School of OR and Information Engineering
Cornell University, Ithaca, NY
quoctd&email. unc.edu
htt27@cornell.co edu
Lam M. Nguyen
IBM Research, Thomas J. Watson Research Center
Yorktown Heights, NY
MMt.iggyen....TD@I... com
Abstract
This paper aims at developing novel shuffling gradient- methods for tackling classes of minimax problems: nomconvex-lineur and nonconver-stronggly con- cave settings. The first algorithm addresses the nonconvex-linea minimax model and achieves the state-of-the-an oracle complexity typically observed in nonconvex optimization. It also employs a new shufiling estimator for the ttyper-gradient" departing from standard shuffling techniques optimization. The second method consists of two variants: semi-shuffling and full-shuffling schemes. These variants tackle the manconve--strongg 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 per- formance 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.
1 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 descent- ascent methods where two routines, each using an SGD loop, ran iteratively [13]. However, practical implementations of SGD often incorporate shuffling strategies, libraries like TensorFlow and Py Torch. 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.
seen in popular deep learning
Problem statement. In this paper, we study the following minimax optimization problem:
min max [(w, u) = f(w) + H(w u) - h(u)) = ((w) + Σ Hi(w, u) - nuu).. (1)
WERP oER
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

R + +UUffo is proper, closed, and convex function. Hi R" x X + R are smooth where f R:
for all i E 'n] := 21, n.. and h I' + R U {+00} 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. is nonconvex in w and linear in u as (w, u) := (F((w), Ku) for given function F; - RT and matrix K E R for all i [n] and (w, u) E dom (C).
(NC) H4 is nonconvex in w and (w,, -) - h(-) is strongly concave in u for all (w,, u) E dom (4). 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,, L(w, u), while the upper-level one is min,, [(w, u).
minimax problems because the objective term H(w, u) == (F(w), Ku) is linear in u. 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 Φ in (CO) becomes nonsmooth regardless of F's properties. This presents our first challenge. natural approach to address this issue, as discussed in Section 2. is to smooth Po. The second challenge arises from the composition between the outer function Λ* 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-gradienn 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 shuffling estimator for the thyper-gradient V 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:
Challenges. The setting (NL) is special case of stochastic nonconvex-coneet
in
Can efficiently develop shuffling gradient methods to solve 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 4 or its smoothed counterpart. This allows to develop two shuffling gradient- based 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, IID. Das et al. in [8] explored specific case of (1) without nonsmooth terms f and h, assuming strong monotonicity and I.-Lipschitz continuity of the gradient VH := H. v. HH] of the joint objective H. Their algorithm simplifies to shuffling variant of fixed- -pint itcration 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-Lojasiewic (PL) 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 's equilibrium perspective with simultaneous update, which is different from our alternative update. Moreover, [3] only considers the noncomposite case with 0 and h- 0. Though we only focus on a srrcoovvx--strnnlee strroggly-concvee -conavve setting (NC), our results here can be extended to the Pt. condition as in [3]. Very recently, Konstantinos el 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) 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-witte witthout-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 compositional minimization and exploit a smoothing technique to treat this reformulation. We propose a new way of constructing shuffling estimators for the "hyper-gradient" V (cf. (10)) and establish their properties.

---

(b) We propose a novel shuffling gradient-based algorithm (cf. Algorithm 1) to approximate
an e-KTT point of (1) for the setting (NL). Our method requires O evaluations of
F3 and FF; under the strong convexity of h, and (n2=)/2) evaluations of F; and V VF; without the strong convexity of h, for desired accuracy > 0.
(c) For setting (NC), we develop two variants of the shuffling gradient method: semi-shuffiing and full-shufling schemes (cf. Algorithm 2). The semi-shuffling variant combines both gradient ascent and shuffling gradient methods to construct a new algorithm, which requires O(ne-3 evaluations of both V Hi and V.HH: The full-shuffling scheme allows to perform both shuffling schemes on the maximization and the minimization alternatively, requiring either One 3) or ()) evaluations of H, depending on our assumptions, while maintaining One evaluations of V H, for a given desired accuracy e > 0.
If a random shuffling strategy is used in our algorithms, then the oracle complexity in all the cases presented above is improved by factor of vn. Our settings (NL) and (NC) of (1) are different from existing works [3, 8, 11], as we work with general nonconvexity in and linearity or [strong] concavity in u, and both I and 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 v in (5). The oracle complexity in both settings (NL) and (NC) is similar to the ones in nonconvex optimization and in special case of (1) from [3] (up to a constant factor).
Paper outline. The rest of this paper organized as follows. Section 2 presents our bilevel optimization approach to (1) and recalls necessary preliminary results. Section 3 develops our shuffling algorithm 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 Supp. Docs.
Notations. For a function S. we use dom (f) to denote its effective domain, and V / for its gradient or Jacobian. If / is convex, then f denotes a subgradient, as is its subdifferential, and prox, is its proximal operator. We use Fg denote a (wo, W1," We), o-algebra generated by random vectors Wo, W1," Wtz E, [-] = [[-]FF,] is a conditional expectation, and E[-] is the full expectation. As usual, (-) denotes O notation in the theory of algorithm complexity.
2 Bilevel Optimization Approach and Preliminary Results
Our approach relies on 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.
2.1 Bilevel optimization approach
The minimax model (1) is split into lower-level (i.e. followeer maximization problem of the form:
Po(w) := max wER:
{ [H(w, u) h(u)= = 1 Ei= He(w, u) h(u)),
(2)
ug (w) == argmax HER* { (N(w, u) h(u) = Σm h(()).
For oy defined by (2), then the upper-level (i.e. the leader) minimization problem can be written as
min WER
Wo Vo(w) = Fo(w) + [(w)).
Clearly, this approach is sequential, and only works if Po is well-defined, i.e. (2) is globally solvable. Hence, the concavity of H(w,,) -h())) w.r.t. to u crucial for this approach as stated below. However, this assumption can be relaxed to global solvability of (2) combined with PL condition in [3].
Assumption (Basic). Problems (1) and (3) satisfy the following assumptions for all i E [n]:
V : inf Volw) > -00. Hi is differentiable w.r.. (w,, u) E dom (L) and H:(w.-) -) is concave in u for any w. Both f TRP + [+00} and h: Ro R U {+00} are proper, closed, and convex.
This assumption remains preliminary. To develop our algorithms, we will need more conditions on Hi and possibly on f and h, which will be stated later. In addition, we can work with a sublevel set
Lys (wo) == (w dom (Vo) (o(w) S (o(w))
(4)
3

---

of Vo for given initial point from our methods. If (u((w) is uniquely well-defined for given w E Lv. (Wo), then by the well- well-known Danskin's 's theorem, Do is differential at w and its gradient
(e = Hw, (())) - + V Hi(,, un (w))..
(5)
We adopt the term "hyper-gradient" from bilevel optimization to name Vdg in this paper.
2.2 Technical assumptions and properties of 2o for nonconvex-linear setting (NL)
(a) Compositional minimization formulation. If Hi (w, u) == (F,(w), Ku) as in setting (NL), then
(I) is equivalentyy reformulated into the following nonconvex compositional minimization problem:
VD((w = ((w) + +o(w) = ((w) + 2
min W VRR
(CO)
where h (v) == sup u) h,( the Fenchel conjugate of h, and Φo(w) ht" (K"FF()) If 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. H4 -tronnly convex with μa 2 O, and dom(h) is bounded by Mn. +00. Assumption 3 (For F,). For setting (NL) with H,(w, u) = (Fi(w), Ku) (i E [n]),. assume that
Fg is continuously differentiable, and its Jacobian F,, is Lr, -ipscchizz continuous.
F; is also p, -Lipcchitz continuous or equivalently, its Jacobian F,; is Mp -bounded.
There exists a posifive constant J. E (0, +-0) such that
DL (w) F (1= o3. Ve dom (F).
(6)
Assumption 2 allows 14,, = O that also covers the non-strong convexity of h. Assumption 3 is rather standard to develop gradient-basee methods for solving (1). Under Assumption 3, the finite-sum F is also Mp-Lipschitz continuous and the Jacobian VF of F is also ---Liscchitz continuous with
MF == max{Mpr : [n]] and LF == max Lp i [n]].
Condition (6) can be relaxed to the form EE [V) [F()]] oî +V>>|lVVuuur for some e, 2 O, where D&b is [sub] [sub]gradient ou D (its smoothed approximation). Moreover, under Assumption 3, if μtg > O, then Vh² is Lii-schhit continuous with Ln- == L. Thus is possible (see [9]) to prove that to is differentiable, and P also Læ., -Lipschiz continuous with consequence of Lemma 4 when 7 4 O in Supp. Doc. A.
Lao M₁ [| M2 1 Ah
(c) Smoothing technique for lower-level maximization problem (2). If only merely convex (i.e. Let us define the following convex function:
μ4 = 0), then (2) may not be uniquely solvable, leading to the possible non non-differentiabiiiyy of Po.
Φo == max {vu, Ku) h(w)) h (K*".)
(8)
Then, Po (2) or (CO) can be written as Po(w) = (Fw))) = Φ0 E. (.()). Our goal is to smooth do if h is not strongly convex, leading to
(v) max (1u, Ku) h(u)) pb(4)}
(9)
(v) = argmax (1v, Ku) h(u)) - vb(4)}
where y
is given smoothness parameter and b R - R is proper, closed, and 1-strongly convex function such that dom(h) (h) C dom(b). We also denote D, = sup([ u dom (h)).
In particular, if we choose b(u)= := _ |lu a for a fixed ū. then u (v) prox (ā kTv).
Using Φy, problem (CO) can be approximated by its smoothed formulation:
min (w)(w)= == f(w) (w) f(w) (F(w))) f(w) + o (h }. (10)
MERP
To develop our method, one key step is to approximate the hyper-gradient Φ,, in (10), where
(w) = Then, V is L,, Lipsccitz continuous with La, = MR | + M Mitt (see Lemma 4).
(F((w) Σ Vo,
(1I)

---

2.3 Technical assumptions and properties of Py for the nonconvex-ttrongly-conee setting
To develop our shuffling gradient-basse algorithms for solving (1) under the nonconvex nonconvex-strongly concave setting (NC), we impose the following assumptions.
Assumption 4 (For Hi). Hi for all E [m]] in (1) satisfies the following conditions:
For any given w such that (w, u) dom (H), H,(w,) :) is pgg-strongly concave w.r.l. u.
b) VH, is (Lws -uppsiihtitzz continuous, i.e. for all (w,u), (10, û) E dom (H):
[VH:(w, u) (ú ai| _ L w12 L u//
(12)
(c) There exist two constants o. 2 0 and σw 2 such that for (w, u) E dom (H), we have
1 E V (w u) V v H(w, u)l z e V H(w, 1) + o.
(13)
There exist two constants O₂ 2 0 and du 2 0 such that for all (w, u) E dom (H). we have
1 22 E V. u) V. H(w, u) S Oul V.H(W, w)ll o.
(14)
Assumption 4(a) makes sure that our lower-level maximization of i) is well-defined. Assumption 4(b) and (c) are standard in shuffling gradient-type methods as often seen nonconvex optimization [9].
Lemma (Smoothness of &o). Under Assumptions 2 and 4, (.(()) in (2) is r-Lipschitz continuous
with K +u+
____,, Moreover, 4 in (5) is L4.- -Lpschitz continuous with Leo == (1 + k)
2.4 Approximate KKT points and approximate stationary points
(a) Exact and approximate KKT points and stationary points. A pair (w* u²) E dom (C) is called
KKT (Karush-Kuhn- Kuhn- Tucker) point of (1) if
0 E V u ",""(w,, u²) aw(") and 0E -V-V.RK "Hw u²) + Oh(u").
(15)
Given a tolerance >> 0, our goal is to find an e-approximate KKT point (w, ū)) of (1) defined as
Tw V. H( ū) + @m)) Ta v, (WW, ū) @h(ā), and E [lllm ru rw]l < e². (16)
vector w* E dom (v)) is said to be a stationary point of (3) if
0 E V + @fw")
(17)
Since f is possibly nonsmooth, can define stationary point of (3) via gradient mapping as: (w)w)= == 1 (w prox,, 17 v/Voow)))
(18)
where 77 > 0 is given. It is well-known that G, (w=) 0 iff w" is stationary point of (3). Again, since we cannot exactly compute w', we expect find an e-stationary point wr of (3) such that E [[Il,,, ((r)),((,)ll') [l?] < 2² for given tolerance c > O.
(b) Constructing an approximate stationary point and KKT point from algorithms. Our algorithms below generate sequence {w, )f'o such that тमा Ei= E [|||,, (wx)
(wx) < e2. Hence, we construct
an e-stationary point कr using one of the following two options:
Wr = W.,, where {
t. :- (7) 0
TT,
(Option 1) or (19)
1. is uniformly randomly chosen from {0, 10.,,...,TT. .T} (Option 2).
S² 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 wt is a stationary point of (3), then (w" wg "((w")) )) is KKT point of (1).
Clearly, we have [[| (wT) S S ElIS,
(b) If wT is an e-stationary point of (3) and Vdo is Lay -Lipschitz continuous, then (WT, WT) is an ē- KKT point of (1), where WT := prox, (wT- - 1n V (wT)), TT == uG(W)) and é == (1 (1+ m)e.
(c) If wT is an e-stationary point of (10), then (WT,UT) is an ē-KTT point of (1), where WT == prox,, ( V (wr)). रe (F((z) and é == max (1 + -,, "Db))
Lemma 2 allows us to construct an é-approximate KKT point (wy, Tr) of (1) from an e-stationary point का of either (3) or its smoothed problem (10), where é (max 71).
5

---

2.5 Technical condition to handle the possible nonsmooth term f
To handle the nonsmooth term f of (1) in our algorithms we require one more condition as in [5].
Assumption 5. Let Dy be defined by (10), which reduces to Po given by (2) as y 4 0*, and G, be defined by (18). Assume that there exist two constants Ao 2 1 and A1 2 0 such that:
[V v (w)) + A1, Vw E dom (+))
(20)
If O, then (w) V (w), and Assumption 5 automatically holds with Au 1 and A1 0. If f # O, then it is crucial to have Au 2 1 in (20). Let us consider two examples to see why?
(i If I My-Lipschitz continuous (e.g.. (--nrm)) then (20) also holds with Ao :- 1 + V >> 1
(ii and A == -" y for given v > 0. f ōy. the indicator of a nonempty, closed, convex, and bounded set W, then Assumption 5 also holds by the same reason as in Example (i) (see Supp. Doc. A).
3 Shuffling Gradient Method for Nonconvex-Linewt Minimax Problems
We first propose new construction using shuffling techniques to approximate the true gradient V in (11) for any 7 2 0. Next, we propose our algorithm and analyze its convergence.
3.1 The shuffling gradient estimators for V
Challenges. To evaluate (w) in (11), we need to evaluate both F 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 finite-sum 4 > V F. Vo, (F,(w))) (see (II)), but every summand requires V (F(w),, which involves the full evaluation of F.
and (1 be the function value and the Jacobian component evaluated at w;-1 respectively for i E [n],, where z(t) = (z (1), x (2), n (n)) and (0) (+ (1), #0 (2),.... (n)) are permutations of [n] (1, .... n). We want
Our estimators. Let Fxcogg
(6)
to use these quantities to approximate the function value F(w5() and its Jacobian VF(w))) (t)) ) of F at
w(") respectively, where wh the iterate vector at the beginning of each epoch t.
For function value )( we suggest the following approximation at each inner iteration E [m]: F!6 == - (n + Ej (um
Option 1:
(21)
Alternative to (21), for all i [n]. we can simply choose another option:
Option 2: F! == 1 - ()( = Ej= Fy (w)))) (9)
(22)
For Jacobian F (1))) (t)), we suggest to use the following standard shuffling estimator for all E [n]:
V (o
(23)
For (((() from (21) (or (22)) and for V p( from (23), we form an approximation of (.b. as
V (w (0
(VF (1) Vo, (1: (
(24)
Discussion. The estimator F.(0 for FF requires
i more function evaluations Fzog) (w at each epoch t. The first option (21) for F uses 2n function evaluations F,, while the second one in (22) only needs function evaluations at each epoch & > 0. However, (21) uses the most updated information up to the inner iteration compared to (22), which is expected to perform better. The Jacobian estimator VF!!) is standard and only uses one sample or a mini-batch at each iteration i.
(2)
3.2 The shuffling gradient-type algorithm for nonconvex-linee setting (NL)
We propose Algorithm 1, a shuffling gradient-type method, to approximate a stationary point of (10). Discussion. First, the cost per epoch of Algorithm I consists of either 2n function evaluations F,, and n Jacobian evaluations F,, Compare to standard shuffling gradient-type methods, e.g., in [8]. Algorithm I has either more evaluations of F, or the same cost. Second, when implementing

---

Algorithm 1 (Shuffling Proximal Gradient-Based Algorithm for Solving (10))
1: Initialization: Choose initial point wg dom (fo) and smoothness parameter 7 > 0.
2: for / 11,2,.... . do
3: Set W/ = w:-15
(f)
4: Generate two permutations (1) and #(*) of [n]] (identically or randomly and independently)
5: for L,... .n do
6: Evaluate F((!) by either (21) or (22) using x00, and V f by (23) using #(0.
7: Solve (9) get uc, (1,() and form v (0) (V (1(").
(t) 8: Update w!!h Wi-1 n (w
9: end for
10: Compute Wi prox (w
11:
end for
Algorithm I, we do not need to evaluate the full Jacobian VP but rather the product of matrix (V and vector (P(()) V0, (w (V yT (F,"),
Evaluating this matrix- vector multiplication is much more efficient than evaluating the full Jacobian V V and VΦ, (P(()) individually. Third, thanks to Assumption 5, the proximal step ū; := prox,, ff (w(²) is only required at the end of each epoch t. This significantly reduces the computational cost if prox,. is expensive.
3.3 Convergence Analysis of Algorithm 1 for Manronvex-Linenr Setting (NL)
Now, we are ready to state the convergence result of Algorithm I 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 sufficiently small tolerance. Let {we) } be generated by Algorithm I after T = O(E-5) epochs using arbitrarily permutations T(1) and (5) and a learning rate T) = 17 == O(e) (see Theorem 6 in Supp.
DOc. B for the exact formulls of and n). Then, we have T+I Σt= t= [| (12 S²
Alternatively, if (we} is generated by Algorithm I after T = O(n 1/2 c 3) epochs using two random and independent permutations (( and ((t) and a learning rate Th: 17 /2e) (see Theorem 6 in Supp. Doc. B for the exact formulas). Then, we have
Σ E Bl (wo)l e
Our first goal is to approximate a stationary point - of (CO) as E El (0) S e. while Algorithm 1 only provides e-stationary of (10). For a proper choice of 7, it is also an c-stationary point of (3).
Corollary 1. Let wr defined by (19) be generated from {we} of Algorithm 1. Under the conditions of Theorem I and any permutations (t)) and a(!), the following statements hold.
(a) h is py--stooglly convex with Ph > 0, then we can sel 7 0, and Algorithm I requires One 3) evaluations of F; and V F; to achieve an e-stationary ÜT of (3).
(b) If h is only convex (i.e. μbg. 0), then we can set y == O(e), and Algorithum 1 needs
One -7/2) evaluations of F; and F,F achieve an e-stationary wr of (3).
If. in addition, x(!) and ((1) are sampled uniformly random without replacement and independently, and A = Onn then the numbers of evaluations of F; and V F, are reduced by a factor of / T..
4 Shuffling Method for Nonconvex-Strome
Concave Minimax Problems
In this section, we develop shuffling gradient-based methods to solve (1) under the nonconvex- strongly concave setting (NC). Since this setting does cover the nonconvex-lines setting (NL) in Section 3 as a special case, we need to treat it separately using different ideas and proof techniques.
4.1 The construction of algorithm
Unlike the linear case with (w, u) (F) Ku) Section 3, we cannot generally compute the solution u)(w;=1) in (2) exactly for given w We can only approximate ug (w;-1) by some ū
This leads to another level of inexactness in an approximate thyper-gradient V (w("), defined by
( V. (1
(25)
7

---

There are different options to approximate (w) We propose two options below, but other choices are possible, including accelerated gradient ascent methods and stochastic algorithms [6. 20].
(a1) Gradient ascent scheme for the lower-level problem. We apply a standard gradient ascent scheme to update ūg Starting
(8) 0 with un 1, al each epoch 1,... ,S, update
(4) == proXieh (o de E V. V.Ha( (00)
(26)
((t) for a given learning rate în > O. Then, we finally output ū, := ug to approximate ui ui( (W+-1)
To make our method more flexible, allow to perform either only iteration (i.e. S 1) or multiple iterations (i.e. S > 1) of (26). Each iteration s requires n evaluations of V.H,,
(a2) Shuffting gradient ascent scheme for the lower-level problem. We can also construct ü, by a shuffling gradient ascent scheme. Again, we allow to run either only one epoch (i.e. 1) or multiple epochs (i.e. S > of the shuffling algorithm to update i, leading to the following scheme:
Starting from s 1 with a == u at each epoch 1.2.....5 S. having v Ug- we generate permutation n (*a1)) of [n] and run a shuffling gradient ascent scheme as
(x,t) = 8,-11 4
For i 1,2, n update
(27)
u. (1,0) u, u + V, (0) (
(2-1)).
(1) Us = prox h (un (1.t)).
At the end of the S-th epoch, we output ū, U. the same learning rate f₁. for all epochs a E [S]. Each epoch 8 requires n evaluations of V V.H.i.
(t)
approximation to (1, Here,
(b) Shuffling gradient descent scheme for the upper-level minimization problem. Having ū from either (26) or (27), we run a shuffling gradient descent epoch to update We from W as
(1t)) == W1-1+
For i = 1,2, ... update (t)
(28)
w (t) w wi-1 (
w V. Ha ūe),
W/ == prox, (wh (2))
These 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), present an alternating shuffling proximal gradient algorithm for solving (1) as in Algorithm 2.
Algorithm 2 (Altemating Shuffling Proximal Gradient Algorithm for Solving (1) under setting (NC))
1: Initialization: Choose an initial point (Wo, ūo) E dom (C).
2: for t= 1, ... T do
3: Compute Ue using either (26) or (27).
4: Set w/y
(1) = i and generate permutation #(0) of [n).
5: for 1, ... . do
6: Evaluate ( 1 = V Ha (w Tz).
(1)
7: Update w = w (1) Ih
(w
8: end for
9: Compute 37 == prox (wh))
end for
Discussion. Algorithm has a similar form as Algorithm 1, where un (w;-1) 1 is approximated by ü
In Algorithm 1, (w;-1) is approximated by ui; (F.()))) Moreover, Algorithm 1 solves the smoothed problem (10) of (3), while Algorithm 2 directly solves (3). Depending on the choice of method to approximate up (1))), we obtain different variants of Algorithm 2. We have proposed two variants:

---

Semi-shufllig variant: We use (26) for computing ün to approximate ug (20211)))
Full-shuflling variant: We use (27) for computing U, to approximate ug (/-1)/
Note that Algorithm works in an alternative manner, where it approximates ()("-11) up to certain accuracy before updating Wt- This alternating update is very natural and has been widely applied to solve minimax optimization as well as bilevel optimization problems, see, c.g., [1, 9, 13].
4.2 Convergence analysis
Now, we state the convergence of both variants of Algorithm 2: semi- shuff-iuffiig and full shlffshuf 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 follows.
Theorem 2. Suppose that Assumptions 1, 2, 4, and 5 hold for (1), and Gn is defined by (18).
Let {(wr, } be generated by Algorithm using the gradient ascent scheme (26) with dj = (c))
explicitly given in Theorem 8 of Supp. Doc. C, fj E (0, Trm? S :- O ( 4Le8H
-1 O1))
Lutps
and T == (===) explicitly given in Theorem 8. Then, we have T+I Ei=o 119, 2
Consequently, Algorithm/ 2 requires (nc-3) evaluations of both V Hi and WH to achieve an c-stationary point Ür 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-shuffting variant- The case S> 1 with multiple epochs. We state results for two separated cases: only H4 is HH--stongly convex, and only h is Wht-trongly convex.
Theorem (Strong convexity of H.). Suppose that Assumptions I, 2, 4, and 5 hold, and Hi Ha Ha--trongly concave with μи > 0 for i E [n], but h is only merely convex.
Let {(we } be generated by Algorithm using S epochs of the shuffling routine (27) and fixed learning rates T)
= Oee) as given in Theorem 8 of Supp. Doc. C C.for a given e > 0, ie = -) O()), S ===1 1n(7 Psh ), and T ;= OEE Then, we have T Et ( S e.
Consequently, Algorithm 2 requires Onne 3) evaluations of He and Onn evaluations of V.H; to achieve an c-stationary point ur of (3) computed by (19).
Theorem (Strong convexity of h). Suppose that Assumptions 1, 2, 4. and 5 hold for (1), and is Mh strongly convex with μn, 0, but H. is only merely concave for all i [n]. Then, under the same settings as in Theorem 3, but with S = ln(T/2) the conclusions of Theorem still hold.
(c) Convergence of the full-shuffling variant - The case 5 = 1 with one epoch. Both Theorems and 4 require One--) evaluations of V.Hi To improve this complexity, we need two additional assumptions but can perform only one epoch of (27), i.c. S =.
Assumption 6.
Let (,)(u) +u prox,t (u + 1/ v/V.,H((,, u))) be the gradient mapping of (ww,) :) == -H(W,.) + h(-). Assume that there exist Åo 2 1 and & 2 such that
|I N(w,(w, u)11 < (u)l + Åι, V(w, u) E dom (f).
(29)
Clearly, if h = O, then (,(u)= ,,, u) and (20) automatically holds for Ås and A Assumption is similar to Assumption 5, and it is required to handle the prox operator of in (27).
0.
Assumption 7. For f in (1), there exists L 2 such that
f(v) S f(x) + (f'(x) x) + L 2 by - =el?: Va, y E dom (ʃ) f'(x) E (s().
(30)
Clearly, if f is Ly-smooth, then (30) holds. If f is also convex, then (30) implies that f is L -mooth. Under these additional assumptions, we have the following result.
Theorem 5. Suppose that Assumptions 1, 2, 4, 5, 6, and 7 hold and 9r, is defined by (18).
Let ((we, ] be generated by Algorithm 2 using one epoch (S = 1) of the shuffling routine (27). and fixed learning rates T)t 1] == O(e) as in Theorem 9 of Supp. Doc. C for a given > 0, fJ. :=
f 30k²,, 11 and T : O where == puu t
L
Then, we have T4I Σ (,,0) < e

---

Consequently, Algorithm 2 requires One evaluations of both w and of V Hi to achieve an e-stationary point ür of (3) computed by (19).
Similar to Algorithm 1, if (*:1) and (0 are generated randomly and independently, A, O(1/n),
and A = (11/n). then our complexity stated above can be improved by a factor of yn. Nevertheless, omit this analysis. Finally, can combine each Theorem 2, 3, 4 or 5 and Lemma 2 construct an ē-KKT point of (1). Theorem 5 has a better complexity than Theorems 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]:
min max 15)5
1 1 (w)) + 2 [2]
(31)
WERP
where Fig 12 Ω R can be viewed the loss of the j-th model for data point i E [n]] If we
define (u) == max { and f(w)= 2 [|ul|? then (31) can be reformulated into (3). Since 2/ 2 0, we have Φ = maxisism [2,} = -1ol = maxijull <1 (v, 2), which is nonsmooth. Thus we can smooth @ as (v) == max/ g1 ((V, - (7/2)[|u|]3) using b(u) == 1 u/l
Here, apply our problem (31) to solve model selection problem in binary classification with nonnegative nonconvex losses, see, e.g., [41]. Each function Fú, belongs to 4 different nonconvex losses (m = 4): (w. {) == 1 - tanh (a,, w)). (r, == log(1 + <xp(-b,(0a: w))) log(1 exp(- (a,, w) - 1)), F F,,( {) = (1 - (exp(_b, w²) + 1))², and F., E)
log(1 + exp(- (a,, w))) (see [41] for more details), where (a,, b,) represents data samples.
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 and update the
smooothing parameter " as == 2(1+1)1/3- The learning rate 1) for all algorithms is finely tuned
1
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 for
w8a and revl datasets using hig 32 blocks. The details of this experiment is given in Supp. Doc. D.
SVM - wBa: 40740. 300
SVM- revl: n 20042 47736
SGM--pption
10P
SGM Option
SGM Option
10-1-
SGM-Option
SGD
SGD
Prox Linear
8:x 100-1
Prox Linear
Objecti Vaua
6 60-00-1
Objective
7 10-1--1
6 10-11
4010
3x 10-0
5x 10-1-
50
70
100
125
150
175
200
0
20
30
75
100
125
130
175
200
Epochs
Epochs
Figure 1: The performance of 4 algorithms for solving (31) on two datasets after 200 epochs.
As shown in Figure 1, the two variants of our SGM have 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 nonconvex- concave 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 non- standard shuffling strategy and achieves the state-of-the -fet---rr----t oracle complexity typically observed in nonconvex optimization. The second algorithm is also new, flexible, and offers 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.
10

---

Acknowledgments and Disclosure of Funding
This work was partly supported by the National Science Foundation (NSF): NSF-RTG grant No. NSF DMS-2134107 and the Office of Naval Research (ONR), grant No. N00014-23-1-2588.
References
[1] M. Arjovsky, S. Chintala, and L. Bottou. Wasserstein generative adversarial networks. In International Conference on Machine Learning, pages 214-223, 2017.
[2] M. G. Azar, Osband, and R. Munos. Minimax regret bounds for reinforcement learning, In International Conference on Machine Learning, pages 263-277 PMLR, 2017.
[3] A. Ben-Tal, L. El Ghaoui, and A. Nemirovski. Robust optimization. Princeton University Press, 2009.
[4] A. Beznosikov, E. Gorbunov, H. Berard, and N. Loizou. Stochastic gradient descent-ascent: Unified theory and new efficient methods. In International Conference on Artificial Intelligence and Statistics, pages 172-235. PMLR, 2023.
[5] K. Bhatia and K. Sridharan. Online learning with dynamics: A minimax perspective. Advances in Neural Information Processing Systems, 33: 15000 2020.
[6] C.-C. Chang and C.-J. Lin. LIBSVM: A library for Support Vector Machines. ACM Transactions on Intelligent Systems and Technology, 2:27:1-27:27, 2011.
[7] H. Cho and C. Yun. SGDA with shuffling: faster convergence for nonconvex-PE minimax optimization. The I 11th International Conference on Learning Representations, pp. 1-10, 2022.
[8] A. Das, B. Schölkopf, and M. Muehlebach. Sampling without replacement leads to faster rates in finite-sum minimax optimization. Advances in Neural Information Processing Systems, 35:6749-6768 2022.
[9] S. Dempe. Foundations of Bilevel Programming. Springer Science & Business Media, 2002.
[10] D. Driggs, J. Liang, and C.-B. Schönlieb. On biased stochastic gradient estimation. Journal of Machine Learning Research, vol. 23, no. 24, pp. 1-43, 2022.
[11] K. Emmanouilidis, R. Vidal, and N. Loizou. Stochastic extragradient with random reshuffling: Improved convergence for variational inequalities. In International Conference Artificial Intelligence and Statistics, pages
PMLR, 2024.
[12] G. Gidel, H. Berard, G. Vignoud, P. Vincent, and S. Lacoste-Julien. A variational inequal- ity perspective on generative adversarial networks. International Conference on Learning Representations, pp. 1-10, 2019.
[13] I. Goodfellow, J. Bouget-Abadis, M. Mirza, B. Xu, D. Warde-Farley, S. Ozair, A. Courville, and Bengio. Generative adversarial nets. In Advances neural information processing systems, 2014.
pages
[14] E. Gorbunov, H. Berard, G. Gidel, and N. Loizou. Stochastic extragradient: General analysis and improved rates. In International Conference on Artificial Intelligence and Statistics, pages PMLR, 2022.
[15] E. Y. Hamedani, A. Jalilzadeh, N. S. Aybat, and U. V. Shanbhag. Iteration complexity of randomized primal-dual methods for convex-concave saddle point problems. arXiv preprint 1806 04118, 2018
[16] J. Z. HaoChen and S. Sra. Random shuffling beats SGD after finite epochs. International Conference on Machine Learning, pp. 2624-2633, 2019.
[17] F. Ho, A. Rajagopalan, Skvortsov, S. Arulampalam, and Piraveenan. Game theory in defence applications: A review. Sensors, 22(3): 2022. 2022.

---

[18] Y. Hsieh, F. Iutzeler, J. Malick, and P. Mertikopoulos, Explore aggressively, update conserva- tively: Stochastic extragradient methods with variable stepsize scaling. Advances in Neural Information Processing Systems, 33:16223-16234, 2020.
[19] Abdul Jabbar, Xi Li, and Bourahla Omar. A survey on generative adversarial networks: Variants, applications, and training. ACM Computing Surveys (CSUR), 54(8):1-45) 2021.
[20] G. Lan. First-order and Stochastic Optimization Methods for Machine Learning. Springer, 2020.
[21] Lin, X. Fang, and Z. Gao. Distributionally robust optimization: A review on theory and applications. Numerical Algebra, Control & Optimization, 12(1):159, 2022.
[22] N. Loizou, H. Berard, G. Gidel, I. Mitliagkas, and S. Lacoste-Julien. Stochastic gradient descent-ascent and consensus optimization for smooth games: Convergence analysis under expected co-coercivity. Advances in Neural Information Processing Systems, 34:19095-19108, 2021.
[23] I. Luo, H. Ye, and T. Zhang. Stochastic recursive gradient descent ascent for stochastic sircovee-stroonly-coocvvee minimax problems. Advances in Neural Information Processing Systems, vol. 33, pp. 20566,
[24] Z. Luo, J. Pang. and D. Ralph. Mathematical Programs with Equilibrium Constraints. Cam- bridge University Press, Cambridge, 1996.
[25] A. Madry, A. Makelov, L. Schmidt, D. Tsipras, and A. Vladu. Towards deep learning models resistant to adversarial attacks. In International Conference on Learning Representations, 2018.
[26] Q. Meng, W. Chen, Y. Wang, Z.-M. Ma, and T.-Y. Liu. Convergence analysis of distributed stochastic gradient descent with shuffling. Neurocomputing, 337:46-57, 2019.
[27] K. Mishchenko, A. Khaled, and P. Richtárik. Random reshuffling: Simple analysis with vast improvements. Advances in Neural Information Processing Systems, 01111739-173222 2020.
[28] K. Mishchenko, A. Khaled, and P. Richtárik. Proximal and federated random reshuffling. In International Conference on Machine Learning, pages 15718-15749 PMLR, 2022.
[29] Y. Nesterov. Introductory lectures on convex optimization: A basic course, volume 87 of Applied Optimization. Kluwer Academic Publishers, 2004.
[30] L. M. Nguyen, Q. Tran-Dinh, D. T. Phan, P. H. Nguyen, and M. van Dijk. A unified convergence analysis for shuffling-type gradient methods. Journal of Machine Learning Research, 22(207):1- 44, 2021.
[31] B. Palaniappan and F. Bach. Stochastic variance reduction methods for saddle-point problems.
In Advances in Neural Information Processing Systems, pages 1416-1424, 2016.
[32] I. Safran and O. Shamir. How good is SGD with random shuffling? Conference on Learning Theory, pp. 3250-3284, 2020.
[33] A. Shapiro and A. Kleywegt. Minimax analysis of stochastic problems. Optim. Methods Softw. 17(3):523 (20)5523-552,,.0 2002.
[34] Q. Tran-Dinh, D. Liu, and L. M. Nguyen. Hybrid variance-reduced SGD algorithms for noncomvex-concave minimax problems. The 34th Conference on Neural Information Processing Systems (NeurIPs 2020), 2020.
[35] J. Wang, T. Zhang, S. Liu, P.-Y. Chen, J. Xu, M. Fardad, and B. Li. Adversarial attack generation empowered by min-max optimization. Advances in Neural Information Processing Systems, 34:16020-16033, 2021.
[36] M. Wang, E. Fang, and L. Liu. Stochastic compositional gradient descent: algorithms for minimizing compositions expected-value functions. Math. Program., 161(1-2):419444, 2017.
12

---

[37] J. Yang, N. Kiyavash, and N. He. Global convergence and variance-reduced optimization for class of
minimax problems. arXiv preprint wwXiv:2002.0962/ 2020.
[38] B. Ying, K. Yuan, and A. Sayed. Convergence of variance-reduced stochastic learning under random reshuffling, arXiv preprini urXiv:/708.0133 2(3):6, 2017.
[39] J. Zhang and L. Xiao. Stochastic variance-reduced prox-lineat algorithms for nonconvex composite optimization. Mathematical Programming, pp. 1-43, 2022.
[40] K. Zhang, Z. Yang, and T. Başar. Multi-agent reinforcement learning: A selective overview of thcories and algorithms. Handbook of reinforcement learning and control, pages 321-384, 2021.
[41] L. Zhao, M. Mammadov, and J. Yearwood. From convex to nonconvex: loss function analysis for binary classification. IEEF International Conference on Data Mining Workshops (ICDMW), pages 1281-1288. IEEF, 2010.
[42] R. Zhao. Optimal stochastic algorithms for convex-coneave saddle-point problems. arXiv preprint 1931v11903.01687, 2019.
13

---

NeurIPS Paper Checklist
1. Claims
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Question:
Answer: [Yes]
Justification: Our claims made in the abstract reflects our contribution stated in the intro- duction, see the "Contribution" paragraph in the introduction section. Our contribution consists of two algorithms, Algorithm I 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 the paper.
The abstract and/or introduction should clearly state the claims made, including 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 be expected to generalize other settings.
It is fine include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
This paper has limitation as it only focuses on two classes of minimax problems defined in (1). Yes, only consider two classes of minimax problems: nonconvex-linent (NL) and convex-strongly concave (NC), covered by our assumption, Assumptions to 5.
Justification:
Guidelines:
The answer NA means that the paper has 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 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 few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or 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 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, 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 impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs

---

Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: We state all required assumptions in Assumptions 1 to Our theoretical results stated in each theorem also refers to these assumptions when required. Our full proofs are given Supp. Docs. due to space limit, and we believe that our technical proofs are correct.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: We provide the details of our experiments, including mathematical models, the detailed implementation of algorithms, the choice of parameters, and datasets. We also upload the code with examples to run and verify.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).

---

(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: Our data available online from LIBSVM. The code is implemented in Python. The code for all experiments is also provided with instruction.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips. cc/ mublic/guides wwwooeooeeeeioooooooooooo
icy for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: / //nips. wwcpublcc/gpeeccccccccccccc mmmbic/guuide/// Sewieeee//oeedmmiiiiiieeee ss ssisnnooi onPolicy) for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question:
Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Ye]]
Justification: Supp. Doc. D provides all the details of our experiments, including how to select parameters, and how to report our results.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification:
The paper does not have such result to report.
Guidelines:

---

The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by enror bars, confi-
dence 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).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative етror rates).
If error bars are reported in tables or plots. The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yss]
Justification: Our experiments were MacBook Pro. 2.8GHz Quad- Core Intel Core 17, 16Gb Memory specified at the beginning of Supp. Doc. D.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: h/tp:://eeeu./eeeeeee
Answer: [Yes]
Justification:
Our data publicly available online from LIBSVM.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive socictal impacts and negative socictal 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 no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation. generating fake profiles, surveillance), faimess 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 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 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 system learns from feedback over time, improving the efficiency and accessibility of ML).
Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
We do not have our own real data specific model that has high risk for misuse.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have 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 usage guidelines 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 encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
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?
Question:
Answer: [NA]
Justification: Our code is open-source and will be made available online under standard public license.
Guidelines:
The answer NA means that the paper does not use existing assets.
5

---

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 URL.
The name the license (e.g.. CC-BY 4.0) should be included for each asset. For scraped data from a particular source (c.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, paperswi thcode. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that re- re-packaged, both the original license and the license of the derived asset (if has changed) should provided.
If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: It does not have new asset.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/moodl as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: It does not relate to crowdsourcing experiments and research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: It does not require any approval.

---

Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with
human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and 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 the institution conducting the review.


Reviews:
[{"review_id": "QTtVdTSrlM", "reviewer": "Reviewer_4w6E", "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. \n\nThe 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. \n\nThe second method introduces semi-shuffling and full-shuffling schemes for the nonconvex-strongly concave setting, establishing their oracle complexity bounds for the first time. \n\nNumerical examples are provided to demonstrate the performance of the proposed algorithms.", "questions": "See above.", "limitations": "Yes", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper is well-written, offering a clear exposition of the current state of the art, along with explicit assumptions and conditions for the proposed methods.\n\n2. The authors introduce novel smoothing techniques similar to Nesterov's smoothing approach for lower-level maximization problems, and establish oracle complexity bounds for both nonconvex-linear and nonconvex-strongly concave settings. This introduces a novel perspective on addressing nonconvex optimization problems.\n\n3. The paper presents two distinct algorithms, each carefully tailored to different problem settings, showcasing a profound comprehension of diverse problem landscapes.", "weaknesses": "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.\n\n2. **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.\n\n3. **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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank you for your appreciation of our strengths and your positive evaluations. We addressed your comments in the general response. We repeat it below for your convenience: \n\n**1. Comparison of complexity with other shuffling methods**\n\nThank you for your suggestions. Among the stochastic shuffling gradient methods for the minimax problem, we have found three references (Das et. al., 2022; Cho & Yun, 2022; Emmanouilidis et. al., 2024) that are most related to our paper. \n\nHowever, the two references (Das et. al., 2022; Emmanouilidis et. al., 2024) are different from us that they consider two-sided PL condition for $H(w,u)$, or strongly monotone variational inequality. These settings are stronger than our general nonconvexity of $H_i$ in the first variable $w$. Thus our results cannot obtain the strongly convex (or PL) rate of $\\mathcal{O}(\\frac{1}{nK^2})$ as in these references. \n\nIn comparison with the reference (Cho & Yun, 2022), our setting is broader than the problem in (Cho & Yun, 2022) that we consider functions $f$ and $h$. When $f = h = 0$, the semi-shuffling variant of Algorithm 2 with a random reshuffling strategy obtains the complexity of $\\mathcal{O}(\\sqrt{n} \\epsilon^{-3})$ (noted in line 300, page 9), which is comparable with the complexity of Theorem 1 (Nonconvex-PL) in (Cho & Yun, 2022). \n\nNote that our Algorithm 2 is different from (Cho & Yun, 2022) even when $f=h=0$ since we do alternating epoch-wise update, while (Cho & Yun, 2022) uses component-wise update (alternating or simultaneous). When $f$ and/or $h$ are present, it remains unclear how to incorporate the prox operators in (Cho & Yun, 2022) as we have done.\n\nIn addition, our analysis can be relaxed to the settings of the PL Assumptions 3+4 in (Cho & Yun, 2022) and obtain the same complexity as the strongly convex case. \n\n**2. Comparison of complexity with other non-shuffling methods**\n\nA comparison between shuffling and other methods, including non-shuffling schemes was done in (Cho & Yun, 2022). For (Nonconvex-SC/PL) setting, the complexity $\\mathcal{O}(\\sqrt{n} \\epsilon^{-3})$ of our Algorithm 2 with a random reshuffling strategy and (Cho & Yun, 2022) is better than the complexity $\\mathcal{O}(\\epsilon^{-4})$ of non-shuffling iid scheme (Lin et. al., 2020, Theorem 4.5). \n\nNot only for minimax optimization, but it has also been observed that shuffling gradient methods often have faster convergence than non-shuffling versions for stochastic optimization (Nguyen et. al. 2021). Moreover, in practice, these methods have shown improved performance over iid algorithms (Bottou, 2009, 2012; Hiroyuki, 2018).\nThis is the motivation for us to work on the broad setting of our paper. \n\nAll the discussions above will be added to our latest revision, and we will also add complexity comparison table.\n\n**3. Experiments**\n\nWe thank you for your suggestions. We will add more examples in the revision. We tested our method on a relatively large dataset *url* from LibSVM with n=2,396,130 and p=3,231,951 for our binary classification. The results are in the appendix. \n\nHowever, we would like to emphasize that the main contributions of our paper are theoretical. We have 4 theorems corresponding to 5 settings (2 settings for (NL) and 3 ones for (NC)). To our best knowledge, our methods for (NL) appear to be the first to develop shuffling-type methods for the class of nonconvex-linear minimax problems which has various applications in distributionally robust optimization and other learning scenarios (like risk-averse portfolio, model-agnostic meta learning). The shuffling strategy we use in Algorithm 1 is also new.\n\nFor the nonconvex-strongly concave setting (NC), we have two strategies, and our model is more general than that of (Cho & Yun, 2022) due to $f$ and $h$. Our assumptions and methods are also different from (Cho & Yun, 2022).\n\nOverall, our paper is significant different from prior works except for (Cho & Yun, 2022) which we discussed above. We have other main contributions for the (NL) case, and our semi-shuffling scheme, apart from handling the nonsmooth terms $f$ and/or $h$. \n\n\nWe hope our response answers all of your questions. If you have any additional comments and suggestions, please discuss with us and we are happy to clarify further. \n\nAgain, thank you for your efforts in reviewing this paper!", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "wnFi2MsRzM", "reviewer": "Reviewer_czC8", "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.", "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": "yes", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The authors establish oracle complexity bounds for their algorithms under standard assumptions. These bounds provide theoretical guarantees on the performance of the proposed methods.", "weaknesses": "The proposed Algorithm 1 requires solving a maximization problem at each iteration, which can be computationally expensive.\n\nThe 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.\n\nTypo in Line 187 and Line 459: $M_f \\rightarrow M_f^2$", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank you for your appreciation of our strengths and soundness. Please see our responses to your concerns and questions below: \n\n**The proposed ... expansive**\n\nWe can choose a simple $b$ in (9) so that $u^*_{\\gamma} ( \\cdot )$ in Step 9 of Algorithm 1 has a **closed-form solution**. For instance, if $b(u) = \\frac{1}{2}\\Vert u - u^0\\Vert^2$ for a fixed $u^0$, then computing $u^*_{\\gamma}(\\cdot)$ reduces to computing the proximal operator of $h$ plus a linear term, i.e. $u^*_{\\gamma}( w ) := \\mathrm{prox}_{h/\\gamma}(u^0 - K^{\\top}F(w)/\\gamma)$. For many $h$ (e.g., $\\ell_1$-norm, the indicator of simple sets), this proximal operator has a closed form.\n\n\n**The numerical ... methods**\n\nWe appreciate your point. We can add more numerical examples in the Supp. Doc. as you suggested. \n\nApart from this point, we believe that our algorithms and theoretical analysis deserve to be reconsidered since we have 4 theorems corresponding to 5 settings (2 settings for (NL) and 3 ones for (NC)). To our best knowledge, our methods for (NL) appear to be the first to develop shuffling-type methods for the class of nonconvex-linear minimax problems which has various applications in distributionally robust optimization and other learning scenarios (like risk-averse portfolio, model-agnostic meta learning). The shuffling strategy we use in Algorithm 1 is also new. \n\nFor the nonconvex-strongly concave setting (NC), we have two strategies, and our model is more general than that of [9] due to $f$ and $h$. Our assumptions and methods are also different from [9].\n\n**Typo**\n\nThank you. We will fix it.\n\n**What are the advantages**\n\nIn our general response, we showed the complexity comparisons for our paper, which highlight the advantages of our shuffling method and settings compared to other prior work. A comparison between shuffling and SGD was done in (Cho & Yun, 2022), showing improvement of complexity under concrete scenarios.\n\nAs discussed in the first paragraph of the introduction, the motivation to study shuffling methods is that they are widely implemented in well-established packages like TensorFlow and Pytorch for optimization and deep learning. Empirically, it was observed, see e.g. [(Bottou, 2009, 2012; Hiroyuki, 2018)] that shuffling schemes decrease the loss faster than SGD and work well in practice, and in many cases. Such aspects motivate us to propose shuffling methods for minimax problems. We are not aware of a rigorously empirical study for minimax problems since such methods have not widely been developed yet. However, many researchers have used SGD to train GANs through standard libraries like TensorFlow or Pytorch, we believe that they could use shuffling SGD implemented in these packates. Our paper studies theoretical convergence guarantees for such strategies in minimax algorithms. \n\nWe hope our response answers all of your concerns and questions. If you have any additional comments and suggestions, please discuss with us and we are happy to clarify further.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "FdtYSUJk9z", "reviewer": "Reviewer_jEDb", "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.", "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$?\n- 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.\n\n- 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]?\n- Light question: Are there examples of when the nonconvex-linear (NL) setting could be of interest in practice?\n- 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": "There seems to be no potential negative societal impact.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "* The theoretical results and the problem-specific proof techniques could be a solid contribution. To the best of my knowledge, this is one of the very few works that discuss shuffling-type algorithms for minimax problems apart from Das et al., 2022 [1] and Cho & Yun, 2023 [2]. I think the results under the relaxed setting, especially the linear, non-strongly-convex case of (NL), and for the bilevel-type shuffling algorithms are quite novel. The paper also includes experimental results that align with the theoretical results.", "weaknesses": "* 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.\n* 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].", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank you for your appreciation of our contributions and your detailed reviews.  Please see our general responses along with the individual reply to you below.\n\n**Comparisons of complexity**\n\nThank you. As you mentioned above, we found the three references [1] [2] and (Emmanouilidis et. al., 2024) that are most related to our paper. In our general response we compared them with our work in details (we do not repeat due to space limit).\n\n**In particular ... in [1]**\n\nWe believe that you meant [2] (Cho & Yun, 2022). Thank you very much for this excellent point.\n\nWe agree with you that the assumptions of Theorem 1 in [2] are similar to our assumptions for (NC) when $f=0$ and $h=0$ (the difference is Assumptions 3 + 4 of [2] and our strong concavity of $\\mathcal{H}$). We believe that our analysis can be relaxed with Assumptions 3+4 in [2] by means of Eq. (21) in [2]). Let us explain in detail below.\n\nIf we set S=1 in (27), then Alg. 2 performs only one shuffling loop to solve $\\max_u$ subproblem. Alg. 2 is different from [2] due to epoch-wise, not update-wise as [2], but both have the same cost per epoch. When S is a constant and independent of $\\eta$, we would have similar complexity as Theorem 1 of [2] if we use a random shuffling strategy. This was noted at the end of Theorem 4: a $\\sqrt{n}$ improvement is achieved if random-reshuffling is used. Therefore, our complexity is $O (\\sqrt{n} \\epsilon^{-3} )$ as in [2]. \n\nIn our paper, the complexity of $\\nabla_w \\mathcal H_i $ could be $O ( \\sqrt{n} \\epsilon^{-3} )$, but the complexity of $\\nabla_u \\mathcal H_i $ is worse than than [2] by a factor of $1/\\epsilon$. This is due to an overestimate of $S$ in Theorem 7, which depends on $1/\\eta$, leading to a $1/\\epsilon$ factor worse than [2]. This factor can be removed by using a similar Lyapunov func. $V_{\\lambda}$ in [2] and modify our proof using Eq. (21) in [2] and Theorem 1 in [Nguyen et al, 2021] instead of our (56). We will update it in our revision.\n\nWe believe that adding nonsmooth terms $f$ and $h$ could change the algorithm as one has to decide when to apply the prox operator, every single update or at the end of each shuffling loop. We are not sure how these terms could change the analysis of [2], including their assumptions (like our Ass 5). We also consider the strong-concavity either of $\\mathcal{H}$ or of $-h$ separately (resp., our Thm 3 or 4).\n\nWe think that the bilevel opt. approach has more flexibility to tackle the $\\max$ and the $\\min$ independently, while the SGDA tackles them simultaneously. In general [not only specific to [2], since [2] looks like a mixed approach], the bilevel optimization approach also allows one to explore techniques from standard optimization, while Nash’s game approach (simultaneously solve the min and the max) such as SGDA often requires theory from montone/nonmonotone operators.\n\nApart from the above points, our work also considers the nonconvex-linear case (NL), overlapped with (NC) in Algorithm 1 (a new shuffling rule like (22)), and a semi-shuffling strategy, which could also be useful in practice. \n\n**Why is ... $f$ and $h$?**\n\nFor the choice of bilevel optimization approach, we have explained above. It is not necessary, but just a different approach. Note that Algorithm 2 only proposed two options (26) and (27), but other options (like accelerated or momentum gradient methods) may be possible to use to solve the strongly concave subproblem $\\max_u$. \n\nFor $f, h=0$, our complexity of $\\nabla_w\\mathcal{H}_i$ is the same as in Th. 1 of [2], but the complexity of $\\nabla_u\\mathcal{H}_i$ is currently weaker than Th. 1 of [2]. As we explained above, we can improve the latter one to $O(\\sqrt{n}\\epsilon^{-3})$.\n\n**Some ... etc.**\n\nYes, we have a clear motivation. For (NL), it is overlapped with (NC), but one is not included in the other. This setting is important as it can be reformulated equivalently to the compositional minimization (CO), and has many applications, including distributionally robust optimization (see Q4 below). The choice of (21) saves evaluations of $F_i$, while (22) uses the most updated information of $F_i$.\n\nFor (NC), we are flexible to use different methods to solve the strongly concave subproblem $\\max_u$. We gave two options: (26) and (27), but other choices can be used.\n\nWhen the maximization is \"simple\", it may be better to use a semi-shuffling strategy (26), where we can solve the max problem by deterministic methods. Note that one can replace (26) with other deterministic methods, but we need to carry out different analyses.\n\nFurthermore, we believe that the strong convexity either in the smooth term $\\mathcal{H}$ or in the nonsmooth term $h$ also makes a difference. So, we cannot incorporate $f$ and/or $h$ in the smooth term $\\mathcal{H}$ if they are nonsmooth. \n\nFor the motivation of the algorithm, we aim to design a natural application of shuffling data schemes in solving the stated minimax problems. The analyses of our algorithms follow after we have tried several different proof techniques. \n\n**Light question: Would ... [4]?**\n\nAs mentioned above, our analysis still works with Assumptions 3+4 in [2] by means of Eq. (21) in [2], at least when $f=0$ and $h=0$. This expression can be written as $L_u \\Vert \\tilde{u}_t - u^{*} ( \\tilde{w} _{t-1} ) \\Vert^2 \\leq 2\\kappa_2 [ \\Phi_0 ( \\tilde{w} _{t-1} ) - \\mathcal{H} (\\tilde{w} _{t-1}, \\tilde u_t ) ] $ in our context. We just need to adapt our proof lightly to accommodate it.\n\n**Light question: Are ... practice?**\n\nYes, there are so many applications, including distributionally robust optimization with finite discrete probability distribution, risk-averse portfolio, model-agnostic meta learning [Finn et al (2017)], etc.\n\n**Minor: Why ... numbers?**\n\nWe are sorry about this technical issue. We will fix it.\n\nWe hope our response answers all of your concerns and questions. If you have any additional comments, please discuss with us and we are happy to clarify further.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Pp1T6Ior4I", "reviewer": "Reviewer_QEyv", "summary": "This work propose shuffling gradient-based methods for nonconvex-linear and nonconvex-strongly convex minimax optimization and obtain complexity results.", "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]). \n\n[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.\n\n[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.\n\n(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$. \n\n(3) In Assumption 2, do you mean for any $v\\in {\\rm dom}(h)$, $||v||_2\\le M_h$? \n\n(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$? \n\n(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. \n\n(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? \n\n(7) Line 255: \"fix number\" $\\rightarrow$ \"fixed number\". \n\n(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": "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.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The presentation is clear. Based on my knowledge on both shuffling and minimax optimization, I found that the algorithms and complexity results are reasonable. The experiments provide sufficient details for reproducibility.", "weaknesses": "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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank you for your appreciation of our strengths and your positive evaluations. Please see our general responses along with the individual reply to you below. \n\n**The contribution ... below**\n\nWe thank you for your comments. While we agree that some individual techniques in our paper are not new, we believe that our algorithms and problem setting is new and has not been addressed in prior works. Our shuffling approximation for the \"hyper\" gradient in the (NL) case is new. To our best knowledge, our methods for (NL) appear to be the first to develop shuffling-type methods for the class of nonconvex-linear minimax problems which has various applications in distributionally robust optimization and other learning scenarios (like risk-averse portfolio, model-agnostic meta learning). \nFor the nonconvex-strongly concave setting (NC), we have two strategies, and our model is more general than that of (Cho & Yun, 2022) due to $f$ and $h$. Our assumptions and methods are also different from (Cho & Yun, 2022).\n\n**Comparisons of complexity**\n\nThank you for your suggestion. We have a detailed comparison in the general response, which included the reference (Lin et. al., 2020):\n\nFor (Nonconvex-SC/PL) setting ($f=h=0$), the complexity $\\mathcal{O}(\\sqrt{n} \\epsilon^{-3})$ of our Algorithm 2 with a random reshuffling strategy and (Cho & Yun, 2022) is better than the complexity $\\mathcal{O}(\\epsilon^{-4})$ of non-shuffling iid scheme (Lin et. al., 2020, Theorem 4.5). \n\nAbout the paper (Nguyen et. el. 2021), although the setting is different, we will still compare with that reference in our paper. \n\n**Remove K**\n\nYes, it is possible to remove $K$ as you suggested. Though, we note that $K$ plays an additional role as a linear transformation and matches the dimension between $u$ and $F(w)$ if they are not the same.\n\n**In Assumption 2 ...**\n\nYes. That is correct.\n\n**In \"Condition (6) ...?**\n\nIt is $\\nabla \\Phi_0$ since our convergence guarantee is eventually on $\\nabla \\Phi_0$.\n\n**After Assumption 5 ...respectively.**\n\nThank you for your suggestion. We will do as you suggested.\n\n**I found ... Yes?**\n\nThat is correct. (21) saves the evaluation of $F_{\\pi^{(t)}(j)}$, while (22) uses the most updated information of $F_{\\pi^{(t)}(j)}$.\n\n**Line 255 ...**\n\nIt will be fixed. Thank you.\n\n**At the end ... shuffling?**\n\nYes, sorry for the typo, we meant that the complexity of $\\nabla_w \\mathcal H_i $ and $\\nabla_u \\mathcal H_i $ is $O ( \\sqrt{n} \\epsilon^{-3} )$. For the full shuffling, we believe that we can improve the complexity of $\\nabla_u \\mathcal H_i $ to match with the complexity of the semi-shuffling case, as discussed with reviewer jEDb. This would only be a minor change to the theoretical contributions of our paper. \n\nWe hope our response answers all of your questions. If you have any additional comments and suggestions, please discuss with us and we are happy to clarify further.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
Dear Reviewers, 

Thank you all so much for reviewing our submission. We valued your comments and appreciation of our strengths and contributions. 

We have addressed each comment individually for each reviewer. In this general response, we highlight some common responses to all the reviewers.

**1. Comparison of complexity with other shuffling methods**

Thank you for your suggestions. Among the stochastic shuffling gradient methods for the minimax problem, we have found three references (Das et. al., 2022; Cho & Yun, 2022; Emmanouilidis et. al., 2024) that are most related to our paper. 

However, the two references (Das et. al., 2022; Emmanouilidis et. al., 2024) are different from us that they consider two-sided PL condition for $H(w,u)$, or strongly monotone variational inequality. These settings are stronger than our general nonconvexity of $H_i$ in the first variable $w$. Thus our results cannot obtain the strongly convex (or PL) rate of $\mathcal{O}(\frac{1}{nK^2})$ as in these references. 

In comparison with the reference (Cho & Yun, 2022), our setting is broader than the problem in (Cho & Yun, 2022) that we consider functions $f$ and $h$. When $f = h = 0$, the semi-shuffling variant of Algorithm 2 with a random reshuffling strategy obtains the complexity of $\mathcal{O}(\sqrt{n} \epsilon^{-3})$ (noted in line 300, page 9), which is comparable with the complexity of Theorem 1 (Nonconvex-PL) in (Cho & Yun, 2022). 

Note that our Algorithm 2 is different from (Cho & Yun, 2022) even when $f=h=0$ since we do alternating epoch-wise update, while (Cho & Yun, 2022) uses component-wise update (alternating or simultaneous). When $f$ and/or $h$ are present, it remains unclear how to incorporate the prox operators in (Cho & Yun, 2022) as we have done.

In addition, our analysis can be relaxed to the settings of the PL Assumptions 3+4 in (Cho & Yun, 2022) and obtain the same complexity as the strongly convex case. 

**2. Comparison of complexity with other non-shuffling methods**

A comparison between shuffling and other methods, including non-shuffling schemes was done in (Cho & Yun, 2022). For (Nonconvex-SC/PL) setting, the complexity $\mathcal{O}(\sqrt{n} \epsilon^{-3})$ of our Algorithm 2 with a random reshuffling strategy and (Cho & Yun, 2022) is better than the complexity $\mathcal{O}(\epsilon^{-4})$ of non-shuffling iid scheme (Lin et. al., 2020, Theorem 4.5). 

Not only for minimax optimization, but it has also been observed that shuffling gradient methods often have faster convergence than non-shuffling versions for stochastic optimization (Nguyen et. al. 2021). Moreover, in practice, these methods have shown improved performance over iid algorithms (Bottou, 2009, 2012; Hiroyuki, 2018).
This is the motivation for us to work on the broad setting of our paper. 

All the discussions above will be added to our latest revision, and we will also add complexity comparison table.

**3. Motivation (Reviewer #jEDb).**
As we will explaine below, we have clear motivation when combining different components. Some are due to different assumptions (e.g., strongly concave vs merely concave), and some are optional (e.g. semi-shuffling vs full-shuffling). In addition, our shuffling strategy is quite general, which can cover both deterministic (e.g., incremental methods) and randomized variants.

**4. Experiments**

We thank you for your suggestions. We will add more examples in the revision. We tested our method on a relatively large dataset *url* from LibSVM with n=2,396,130 and p=3,231,951 for our binary classification. The results are in the appendix. 

However, we would like to emphasize that the main contributions of our paper are theoretical. We have 4 theorems corresponding to 5 settings (2 settings for (NL) and 3 ones for (NC)). To our best knowledge, our methods for (NL) appear to be the first to develop shuffling-type methods for the class of nonconvex-linear minimax problems which has various applications in distributionally robust optimization and other learning scenarios (like risk-averse portfolio, model-agnostic meta learning). The shuffling strategy we use in Algorithm 1 is also new.

For the nonconvex-strongly concave setting (NC), we have two strategies, and our model is more general than that of (Cho & Yun, 2022) due to $f$ and $h$. Our assumptions and methods are also different from (Cho & Yun, 2022).

Overall, our paper is significant different from prior works except for (Cho & Yun, 2022) which we discussed above. We have other main contributions for the (NL) case, and our semi-shuffling scheme, apart from handling the nonsmooth terms $f$ and/or $h$. 

**Finally,**

We hope our response answers all of your concerns and questions. If you have any additional comments and suggestions, please discuss with us and we are happy to clarify further. 

Again, thank you for your efforts in reviewing this paper! 

**Added References:**

Tianyi Lin, Chi Jin, and Michael Jordan. On gradient descent ascent for nonconvex-concave minimax problems.  In International Conference on Machine Learning, pp. 6083–6093. PMLR, 2020

L. Bottou. Curiously Fast Convergence of Some Stochastic Gradient Descent Algorithms. In Proceedings of the Symposium on Learning and Data Science, Paris, volume 8, pages 2624–2633, 2009

L. Bottou. Stochastic Gradient Descent Tricks. In Neural networks: Tricks of the trade, pages 421–436. Springer, 2012.

K. Hiroyuki. SGDLibrary: A MATLAB Library for Stochastic Optimization Algorithms. Journal of Machine Learning Research, 18(215):1–5, 2018.

Meta-review: 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
Decision: Accept (poster)