SGDA with shuffling: faster convergence for nonconvex-PŁ minimax optimization
Authors: Hanseul Cho
Chulhee Yun
Venue: ICLR 2023 poster (2023)
Keywords: minimax optimization
SGDA
without-replacement sampling
random reshuffling
Polyak-Łojasiewicz

Abstract: Stochastic gradient descent-ascent (SGDA) is one of the main workhorses for solving finite-sum minimax optimization problems. Most practical implementations of SGDA randomly reshuffle components and sequentially use them (i.e., without-replacement sampling); however, there are few theoretical results on this approach for minimax algorithms, especially outside the easier-to-analyze (strongly-)monotone setups. To narrow this gap, we study the convergence bounds of SGDA with random reshuffling (SGDA-RR) for smooth nonconvex-nonconcave objectives with Polyak-{\L}ojasiewicz (P{\L}) geometry. We analyze both simultaneous and alternating SGDA-RR for nonconvex-P{\L} and primal-P{\L}-P{\L} objectives, and obtain convergence rates faster than with-replacement SGDA. Our rates extend to mini-batch SGDA-RR, recovering known rates for full-batch gradient descent-ascent (GDA). Lastly, we present a comprehensive lower bound for GDA with an arbitrary step-size ratio, which matches the full-batch upper bound for the primal-P{\L}-P{\L} case.

Published as a conference paper at ICLR 2023
SGDA WITH SHUFFLING: FASTER CONVERGENCE FOR NONCONVEX-PE PL MINIMAX OPTIMIZATION
Hanseul Cho, Chulhee Yun
Kim Jaechul Graduate School of AI, KAIST (jhs4015, chulhee. @ka 1st a.c. kr
ABSTRACT
Stochastic gradient descent-ascent (SGDA) is one of the main workhorses for solving finite-sum minimax optimization problems. Most practical implementa- tions of SGDA randomly reshuffle components and sequentially use them (i.e. without-replacemmen sampling); however, there are few theoretical results on this approach for minimax algorithms, especially outside the easier-to-analyze (strongly)mmonotee setups. To narrow this gap. we study the convergence bounds of SGDA with random reshuffling (SGDA-RR) for smooth nonconvex- nonconcave objectives with simultaneous and alternating SGDA-RR for nonconvex-Pt. and primal-PE-PE. ob- jectives, and obtain convergence rates faster than with-replacement SGDA. Our rates extend mini-batch SGDA-RR, recovering known rates for full-batch gra- dient descent-ascent (GDA). Lastly, we present comprehensive lower bound for GDA with an arbitrary step-size ratio, which matches the full-batch upper bound for the primal-P2 PL-PE case.
(PL) geometry. We analyze both
INTRODUCTION
finite-sum minimax optimization problem aims to solve the following:
min max f(x; = 1 fx wEY
where fi denotes the i-th component function. In plain language. we want to minimize the average of n component functions for æ, while maximizing for y given æ. There are many important areas in modern machine learning that fall within the minimax problem, including generative adversar- ial networks (GANs) (Goodfellow et al., 2020), adversarial attack and robust optimization (Madry et al., 2018; Sinha et al., 2018), multi-agent reinforcement learning (MARL) (Li et al., 2019), AUC maximization (Ying et al., 2016; Liu et al., 2020; Yuan et al., 2021), and many more. most cases, i.e., neither convex in nonconvex-nonconcave problems are known to be intractable, we would like to tackle the
the objective f is usually general nonconvex- nonconcave problems with some additional structures, such smoothness and Polyak-Lojasiewiez (PL) con- dition(s). We elaborate the detailed settings for our analysis, noncomvex-PL. PL and primal-PE, PP-PPP (or, PL( PE), Section 2.
concave in y. Since
One of the simplest and most popular algorithms to solve the problem (1) would be stochastic gra- dient descent-ascent (SGDA). This naturally extends the idea of stochastic gradient descent (SGD) used for minimization problems. Given an initial iterate (Zo; yo), at time t N, SGDA (randomly) chooses an index i(t) E {1,...,,u n) and accesses the i(t)-th component to perform a pair of updates
Φ; T;-1 a V, fan (x Vi-1,,
[e-11 (simSGDA), or Dte
where x'
V: V:-1 V fat) v.);
(altSGDA).
Here, and are the step sizes and V denotes the gradient with respect j-th argument for fi(e) (j = 1,2). As shown in the update equations above, there are two widely used versions of SGDA: simultaneous SGDA (simSGDA), and alternating SGDA (altSGDA).
In such stochastic gradient methods, there are two main categories of sampling schemes for the component indices it)). One way is to sample i(t) independently (in time) and uniformly random

---

Published as a conference paper at ICLR 2023
from {l,..., ni), which is called with-replacement sampling. This scheme is widely adopted in theory papers because makes analysis of stochastic methods amenable: the noisy gradients V fite) are independent over time and are unbiased estimators of the full-batch gradient f. In contrast, the vast majority of practical implementations employ without-rppacemmen sampling, indicating a huge theory-practice gap. In without-replacement sampling, we sample each index precisely once each epoch. Perhaps the most popular of such schemes is random reshuffling (RR), which uniformly randomly shuffles the order of indices at the beginning of every epoch. Unfortunately, it well- known that vithout-replacenet because the sampled indices in each epoch are no longer independent of each other.
methods are much more difficult to analyze theoretically, largely
Interestingly, for minimization problems, several recent works overcome this obstacle and show that SGD using replacemet sampling leads to faster convergence, given that the number of epochs is large enough (Nagaraj et al., 2019; Ahn et al., 2020; Mishchenko et al., 2020; Rajput et al., 2020; Nguyen et al., 2021; Yun al., 2021; 2022). On the other hand, for minimax problems like (I), the majority of the studies still assume with-replacement sampling and/or rely on independent unbiased gradient oracles (Nouiched et al., 2019; Guo et al., 2020; Lin et al., 2020; Yan et al., 2020; Yang et al., 2020; Loizou et al., 2021; Beznosikov et al., 2022). There max algorithms using without-replacement sampling; even most of the existing ones take advantage of
very few results mini-
(in æ) and/or strong-)Jconavite (in y) (Das et al., 2022; Maheshwari al., 2022; Yu et al., 2022). Detailed comparative analysis of these works is conducted in Section 4.
Putting all these issues into consideration, our main question is the following.
Does SGDA using without reepacemeee component sampling provably converge fast, even on smooth noncomvex-nonnconeee objective f with PL structures?
1.1 SUMMARY OF OUR CONTRIBUTIONS
To answer the question, we analyze the convergence of SGDA with random reshuffling (SGDA-RR. Algorithm 1). We analyze both the simultancous and alternating versions of SGDA-RU RRR and prove convergence theorems for the following two regimes. Here denote the step size ratio
3/a.
When =f y) satisfies μ22PL condition in y (nonconvex-PL) and component function f; 's are L-smooth, we prove that SGDA-RR with r 2 22) converges to e-stationarity in expectation after O (nr - + v Vir 1.5 ")= gradient evaluations (Theorem 1).
Further assuming 1lt condition on (--) == maxy f(;y) (primal-PL-PPL, or PL(Ø)-
PF.), we prove that SGDA-RR with 2 (L/ p2) )2 converges within e-accuracy in expecta- tion after Ô nie log(s-') +
gradient evaluations (Theorem 2).
As will be discussed in Section 4, the rates shown above are faster than existing results on with- replacement SGDA. In fact, Theorems 1 & 2 are special cases (b 1) of our extended theorems (Theorems 4 & 5 in Appendix A) that analyze mini-bated SGDA-RR of batch size b; by setting b = n, we also recover known convergence rates for full-batch gradient descent ascent (GDA). Hence, our analysis covers the entire spectrum between vanilla SGDA-RR (b = 1) and GDA (b n).
Additionally, we provide complexity lower bounds for solving
concave (SC-SC) minimax problems using full-batee simultancous GDA with an arbitrarily fixed step size ratio r = B/a. Perhaps surprisingly. we find that the lower bound for SC-SC functions matches the convergence upper bound for a much larger class of primal-Pt.-PP.. functions when the step size ratio satisfies 2 T.2 22/p2 (Theorem 3).
2 PROBLEM SETUP
2.1 NOTATION
In our problem (I), the domain of every f, is 2 X'xxx VJ, where X -d= Rd., and Z R4: we concern unconstrained problems for simplicity. We denote the Euclidean norm and the standard inner product by |I-1 and (:.)), respectively. We often use an abbreviated notation 2 = =(x; y) E Z for E X and y E y. Even when or (æ: y) is followed by superseripts and/or subscripts, use the symbols interchangeably; e.g., xt = ( Note that we split the arguments æ (for minimization) and y (for maximization) by semicolon (c:". We use V, and V2 to denote the
2

---

Published as a conference paper at ICLR 2023
Algorithm SinSGDAAVlIISGDDARRR
1: Given: The number of components n: the number of epochs K;; step sizes a, > 0
2: Initialize: (argi yō) E IR
IR
3: for k [K] do
4: Sample okk ~ Unif(Sn)
> RR: uniformly randomly shuffle the indices every epoch
5: for i [n] do
6: a. o - 1J, (o.(()) (1) (xt (1f wf
7:
if SimSGDA-RR then
8:
y = y 1 (V2fan(0) (2 (2)-1: U--1)
> simultaneous update: x: & alternating update: æ +
9:
else if allSGDARRR then
10:
y = y + Ve (2) (1)1)(1))
11:
(xr yo
k+t 4+1 (w yh)
gradients with respect to first and second arguments, Aeppcctively.Acooddnngll. we can write the full gradient as, e.g., Vg iV V29 ] For a positive integer N, we denote [N] := .1.....NJ N). Let the set S be symmetric group of degree N. That is, each permutation a E Sy is bijection from [N] to itself, equivalently, re-arrangement of [N]. Lastly, use the usual O/0/e notation for bounds, where Ó/Ộ/ê used for hiding some logarithmic factors, respectively.
2.2 ALGORITHMS: SIMSGDA-RR & ALTSGDA-RR
As we explained in Section 1, we consider SimSGDA and altSGDA combined with RR, a without- replacement sampling scheme. We call them simSGDA-RR and altSGDA-RR, respectively. We present a detailed description of the methods in Algorithm 1. For completeness, we also provide an extended version that uses mini-batches of size 2 (Algorithm 2) in Appendix A, For comparison, we call the SGDA algorithms using with-replacement sampling by just simSGDA and altSGDA.
The quantities a, 33 > O are step sizes associated with æ and y. respectively. We use two separate symbols and 3 to allow the two step sizes to be different. Such algorithms are sometimes called two-time-scale algorithms, mization problems (Heusel et al., 2017; Lin et al., 2020; Yang al., 2020). In fact, recent result (Li et al., 2022) shows that having a # 3 sometimes necessary for convergence.
a broader sense, and they are adopted in nonconvex minimax opti-
2.3 ASSUMPTIONS AND DEFINITIONS
To define the function classes that interested in solving, introduce few assumptions. Assumption (Component smoothness). Every i-th component f. Z + ER is L L-soohth, i.c. fa is differentiable and Vf, is L-Lipschitz continuous:
S L || æ||. As result, (Vf((=), 2 2-2) - (Vz, 2) and the average f of fi is also L-smooth. Assumption (Component gradient variance). There exist constants A, B 2 0 such that, for any z (2: E Z and E (1,2), we have 1 En= fe(z) [=)] S A A|V, [(z ||2 B. X
Assumption 3. For a function as ((x) := maxy'y (x; y'). For each x E X, the set ) = arg max ey fa; ) is non-empty and closed. Moreover, we assume ((x)) ) is bounded below by th" inf (xx') -cc
R. the primal function + : X R is well-defined
Note that Assumption 2 controls the discrepancy between the objective function f and its compo- nents fi fss; it is similar to Assumption 2 of Nguyen et al. (2021), adapted to minimax problems. Letting A = 0 recovers common assumption of the uniformly bounded variance of component gradients; thus, our assumption relaxation. Also, note that A = B when n 1.
objective function, which is called Dolyak-Lojasiewice (PE) condition. A function 2d + IR is said to be pt it has minimum value g" and satisfies
We add additional structure
V (t)l 2 2p(g(t) -*).. (V t E Rd)
(μ-PL)
As noted, Assumption 1 directly implies the average smoothness which is common requirement in the analysis with unbiased gradient oracles. Nevertheless, claim that Assumption is not more crucial than without--eplacemmet sampling obtain faster convergence rates: Appendix F for details and proofs.
3

---

We say the function f is nonconvex-PP when it satisfies Assumption Since we do not assume any convexity/concavity. it is generally hard to reach global optima. Due to the y-side PL condition, can guarantee that the primal function & is differentiable and even Le -smooth with Le S L++L//u the minimization Published as a conference paper at ICLR 2023
Readers could find several studies and applications that the condition involves, in the papers by Karimi et al. (2016); Nouiched et al. (2019); Yang et al. (2020); Liu et al. (2020), and more. Note that every p-strongly convex² function satisfies μ-PE condition, whereas PL function does not need to be convex. Hence, jt-Pt. is a strict generalization of j--strong convexity. In addition, every stationary point of Pt. function is global optimum, which is benign property for optimization.
We are interested in the case where our objective function f(; y) has such a structure in terms of y (Assumption 4). Sometimes, we further assume the primal function & is also PE (Assumption 5). We emphasize that we do not necessarily assume the PL. conditions for the individual fi's,
Assumption 4 (y-side PE.). For each (fixed) x E X, ff(;;;) is Pt-Pt, i.e for every (æ:: y) E 2,
V (a; y)"l 2 2 ((x)) (z) f((::; y)), where t is the primal function associated with J.
Assumption 5 (Primal PE. or PL(()). The primal function ((.) = maxy' f(x; yo) of f is pa Pt, i.e., every X, | ((x))l - 2pr (f(()) o"),, where g- min ((x)) is well-defned.
(Proposition 9 in Appendix B). Since the problem (1) be reformulated
problem of Φ (when we can always find y well that maximizes f(: y) given œ), we could aim to find an approximate first-order stationary point of 4, by making the norm of the gradient of & small.
On top of that, if ʃ satisfies both Assumptions 4 and 5, the function is said to be primal-PE-Pt. only decrease the primal function &
PE for short.3 In this case, we directly aim associated with the objective function f but also to increase the function value f(æ; y) in terms of y. To evaluate how close we are to our goal, we define a potential function V2, later in Section 3. When we attain (x y=) = O, it implies that we arrive at a global minimax point: f(=", .y") (x=") = 4- The function Vs enables us to develop a unified analysis for nonconvex-Po and PE( objective functions; we discuss this in greater detail in Section 3.
MAIN RESULTS
Based on the assumptions stated in the previous section, we present the convergence results for both smooth nonconvex-PE. -PL objectives and smooth PL( objectives. Before stating the main theorems, we first introduce the most important tool for our analyses: the potential function.
3.1 POTENTIAL FUNCTION VA
For our convergence analyses, we utilize a function V2 X' x y + R defined as
V2(2; y) := x(*(z) - 40) + (Φ(x) f(x; B)),
(2)
where À= > is a constant. We borrow inspiration from Yang et al. (2020) and Das et al. (2022) to come up with this function, although the placement of À of ours is different. In fact, the convergence to a neighborhood of a global minimax point (if it exists) implies the reduction of this function. For each æ. a non-negative term ((x)- f(æ; y gets smaller y makes f(æ; y) larger. The term becomes zero when y = y" (z) for some y" (z) E Vr. since ((x) = f [x: y (x)) Also, another makes ((x)) smaller. Thus, (æ; y) approaches to a minimax optimal point, Vx y) decreases to near zero. In general, VA is not guaranteed to attain exact zero, especially when the objective function fxx; y) is nonconvex in (e.g., I is nonconvex- PE.). Nevertheless, the potential function is still useful for deriving our convergence results.
non-negative term ((x)) o gets smaller
3.2
MAIN THEOREMS: UPPER BOUNDS OF CONVERGENCE RATES
Now, present main results. We provide detailed comparison of our theorems against ex- isting results in Section 4. We present the full proof in Appendices C and D. We remark that both Theorems and 2 are special cases (for mini-batch size = 1) of their mini-batch extensions: Theorems 4 and 5 in Appendix A.
We say a function : Rd + R is p-strongly convex for some μ > if it holds g(a') 2 g(x)) + (Vg(z), x' x² (n/2) |a' - =11 (Var, .²); we say g is ju-strongly concave -g j--troonlyy convex. "The P PL condition is much weaker than two-sided PL condition assuming "æ-side" PE condition:
see Proposition 10. As pointed out by Guo et al. (2020), there exist a PP.P function g(x; y) that is not ar-ide JtPPt for any μ 0 but even strongly concave a7
4

---

Published as a conference paper at ICLR 2023
Theorem (Nonconvex-PEa) PE.). Suppose that f satiisfes Assumptions 1, 2, 3, and 4. Let R2 L/p2. where H2 is PL constant of -f(x;)) )) at all a. Let = Choose the step sizes a and such that
}}
Va(=b) Bn²K
and a 3 F
B min
69 6Lv/ A)
for some r 2 14 Then, both simSGDA-RR and altSGDA-RR (Algorithm) 1) satisfy
K
LLVV(=))
A +r L L2 3/5
E [a
So
K
K
n
nk2
Upper bound on gradient complexity. To achieve E-stationarity of the primal function, i.e., E K
< e2, sufficient number of gradient evaluations (denoted by Te nK) is E [
R
Tg O (=V)(=b)
max Vn² nA, VrnB 1)
8
Theorem (P.)) Suppose that I satisfies Assumptions 2, 4, and 5. Let = LL/p and K2 L/pg, where μr and μ2 are PL constants of 2(-) and f(x;)) (at all x), respectively, Let 4 Choose appropriate step sizes and B such that
(mAnk) and 3 r'
δ
K3
B = min
69 ELVnn(++A
for some r 2 14kg. Then, both simSGDA-RO RR and altSGDA-RI RR (Algorithm 1) satisfy
E B[V3(20 {z) 50
V((=b) exp
K
K2r B
1inK2
12
Upper bound on gradient complexity. To achieve -cccuracy on expectation of Vx(2 (2 i.e, (V < e2, sufficient number of gradient evaluations (denoted by T nK) is
TV max f (1IVVn22+ +nA log
V((z))
)
Kir
3/2
nB
E
Remark step size ratio. In both theorems, is common to use such a step size scheme r = (x²3) to analyze two-time-scale (S)GDA for nonconvex minimax problems (Jin et al., 2020: Lin al., 2020; Yang al., 2020).
the step sizes of ratio B/a 2 x3.
Remark on the parameter X. In our convergence analyses, we arbitrarily choose À = 4 which makes the numerical calculations easier. The value of X > 0 does not matter for the equivalence be- 0 and global minimax condition (Proposition 11 in Appendix B). Also, the choice of À in both theorems can be arbitrary as long as À > our logic does not fall apart other appropriate step sizes for that X are chosen. That is to say, we can show that the sequence VA (22)) almost monotonically decreases, ignoring some small variance terms.
tween the equation Vx ) ">"""""")
COMPARISON WITH RELATED WORKS
4.1 COMPARISON WITH STOCHASTIC WITH-REPLACEMER SETTING
First of all. we confirm that SGDA with random reshuffling (RR) has faster convergence rates (i.e., fewer gradient computations) than SGDA based on with-replacement sampling. In particular, compare our results with the analyses on the purely stochastic minimax settings which assume that every stochastic gradient oracle is independently sampled and unbiased: this assumption natu- rally satisfied by with-replacemmnt sampling for the finite-sum settings we consider. To make the comparisons fair and easy, we simply let r = B/a ( = 0, and B 72
Lin al. (2020, Theorem 4.5) present a convergence rate for with-replacement simSGDA with r= (m=) run on nonconvex #2--srrongly-concar problems with a convex bounded constraint set y for dual variable y. Their gradient complexity to achieve + +E E (=)()))) E (where T is the
5

---

Published as a conference paper at ICLR 2023
number of iterations) is written as T. = O 1 Aq = ((x0)) 6. D = diam), and 7² is the variance of the (unbiased) stochastic gradient oracles. Their complexity can be simplified O(x3r²==*) treating other factors constants. In contrast, our Theorem has a better gradient complexity in terms of & and T, thanks to shuffling:
}) where R2 = L/
max
(=)) E2
K
n1
(Ours, from Theorem 1)
or simply O VoeV/) Thus, our gradient complexity for both simSGDA-RR and altSGDA- RR is better than that of with-replacement simSGDA when E is small as = S O()/Vn). Our rate has three more strengths: (i) we do not require strong concavity in y, which is a strictly stronger assumption than requiring y-side PL condition; (ii) we do not require the constraint set y to be bounded; (iii) our result can easily extend to the case of any mini-batch sizes, whereas Lin et al. (2020) need particular choice of mini-batch size M = ((k2T=/e)) to ensure convergence.
For nonconvex- Pt. objectives, Yang al. (2022, Theorem 3.1) provide convergence rate for with- replacement altSGDA with r = (m²). Their rate can be translated to a gradient complexity for achieving
+Σ== E [==)))] s E², written as 1
1
( or simply
Age
On +). Therefore, our gradient complexity for both altSGDA REEDA-RRAAA and simSGDA -RR is better when is small OKKTT/V/)
For PL objectives, Yang et al. (2020, Theorem 3.3) obtain a convergence rate for with- replacement altSGDA with O(x)). They apply diminishing step sizes (O(1/t), t E N) to derive a gradient complexity bound o
NNN to achieve [[V)( < e². One can apply the PIE
constant step sizes depending on the total number of iterations to their analysis and derive a sim- ilar complexity with only deterioration in logarithmic factor. In contrast, our gradient complexity for both sim/altSGDA-RR using constant step sizes can be written as, for small enough E,
(IINTTVR
(Ours, from Theorem 2)
EVPT
This is a better complexity in E and Ri, especially when E S Ō (M2Tt//pp)) even without the requirement of diminishing step size.
4.2 COMPARISON WITH OTHER WORKS ON STOCHASTIC WITHOOUT-REPLACEMMERT SETTING
One of the most relevant works to this paper is Das et al. (2022, Theorem 3). The authors obtain a similar convergence rate to us for the two-sided PE objective, based on linearization of gradients, but for dissimilar algorithm which they refer to as AGDA-RR. The algorithm can be also thought of as epoch-wise- wrooc--wse-alteraatin alternating SGDA-RE RRR, whereas our algorithm (altSGDA- -R) can be called as step- wise-alternating -GDA-RR. In epoch ks their algorithm (i) performs updates only while fixing y to y and then (ii) performs updates only on y (yf...., vt) while fixing x to k+1 = x; We believe that our step-wise algorithm is closer to practice, especially when n is large. Because of the distinction between algorithms, the proof techniques are also different.
(af......") ..,)
Xie et al. (2021, Theorem 3) present a convergence rate of CD-MA, an extension of simSGDA to the cross-device federated learning setup, nonconvex-Pt. setting. Their convergence result for CD-MA also assumes mini-batch sampling by random reshuffling. As a consequence, they yield rate analogous to our Theorem if we reduce their result the single-machine setup. Nevertheless, our convergence bound contains a term that shrinks with the number of components or mini batces, whereas theirs does not. For more detailed comparison, please refer to Appendix H.
There are also some works on RR-based (constrained) minimax optimization algorithms other than SGDA, but for convex-concave problems. Maheshwari al. (2022) present OGDA-RR, a gradient- free RR-based optimistic GDA algorithm. Yu et al. (2022) study stochastic proximal point with RR, consisting of double-loop epochs. Their analyses exploit convex-concavity and Lipsehitz continuity of their objective, based on the arguments by Nagaraj et al. (2019). This enables direct usage of the duality gap, the difference between primal function (--) and dual function (r()) = min, f(æ; :), as different structure of the functions,
criterion for optimality. On the contrary, work relies which in turn differentiates the constructions of convergence rates.
A Athoughh they consider two-sided Pf. problems, their analysis applies PF.(D)-PE. problems as well.

---

Published as a conference paper at ICLR 2023
4.3 COMPARISON WITH DETERMINISTIC SETTING
Here, we compare our rates with (full-batch) gradient descent-ascent (GDA):
---1 V ((x=-1; Dk-1), yk Vk-1 VV2 yk-),,
1k-1, (simGDA), or
where x'
Tk: (alGDAA).
It uses the whole information of the objective / at every iteration without any noise. For comparison with GDA, we utilize our extended theorems for arbitrary mini-batch size b (Theorems 4 and 5 in Appendix A). By letting
n and matching our iterate = (a5 36) to GDA iterate 2/ (#t; Vk), our results reduce to upper convergence bounds for simGDA and altGDA.
For nonconvex-PP PE problems (Theorems 4), the convergence rate and iteration complexity (i.e. sufficient number of iterations K2) become
min [V S So( ( kE[K]
(Z 8²
i.e., Kg =0
(3)
when (n.). This is similar to known rate of simGDA with r ((2)) for nonconvex-
strongly-concave problems by Lin et al. (2020, Theorem 4.4) as a special case. Their iteration where the symbols
already defined in Section 4.1. To see how the two bounds compare in terms of the factors other than E, notice that we have ((x)) f(x; y) < L lly y² I² for any (z;y). due to the L-smoothness of -f. Here, arg max, f(: y). Thus, we have (1
complexity is written as [ + x22.2
2
y yx(x) is an element of Vm
{[ Φ01 +
((()) f(z1)) & AAa + LD3 /2. As a result, we could loosely translate our iteration complexity (3) to ((KgLA0 + //E") We suspect that the discrepancy in terms of 82 comes from the fact that our analysis does not require the (strong) concavity in terms of y or a bounded constraint
Y: these requirements made considerable difference in proofs.
For PE problems (Theorems 2 & 5), the rate and iteration complexity (K)) become
vx(**+1) S V2(2)) exp (- (cspppccpp (-ch)r3) i.e., K² 0 (RI (R1n)log(1/e) log(1/e))
K
(4)
where r (x2) and C' is numerical constant. This recovers the linear convergence by Yang et al. (2020, Theorem 3.2) as a special case, where they prove convergence of altGDA with step size ratio ((x)) ) for two-sided PL problem. Following the proof of (Yang et al., 2020. Theorem 3.2), one can show that the bound (4) indeed implies the actual convergence to a global minimax point z", in the sense that can achieve || z" < & in O (kg23 (1))) iterations.
5 LOWER BOUND FOR (FULL-BATCH) SIMGDA USING SEPARATE STEP SIZES
As an extension of the discussion from Section 4.3, we characterize a lower complexity bound of de- terministic simGDA with separate step sizes (a, (8) of arbitrary ratio B/a, for smooth strongly- monve--strongly-coned
(SC-SC) cases. Surprisingly, at least for r Z x2, our lower bound matches the upper complexity bound of GDA for much wider class of smooth (P problems, which is quite surprising.
For a smooth PL(D)-PL problems, simGDA with at least r = ((x3) has an upper complexity bound K O((rr log(1/=)) for global E e-convergence VΛ(*k) < =² in terms of potential function. This means that the lowest complexity is O(K log(1/e)) achieved when r = (x2)). On the other hand, for L-smooth SC problem with saddle point 2", it is well-known that the simGDA with a single step-size (a = 3) has a tight upper/lower complexity K = O(k² log(1/s)) to achieve ||æx- 11 < E² where k = L/μ (e.g., Das et al. (2022, Theorem C)) The difference of complexity bounds in condition number (21 v.s. x²2) is somewhat questionable because, at least in smooth minimization problems, strongly convex problems and PL problems have identical gradient descent (GD) iteration complexity ( (oe) (Karimi et al., 2016, Theorem 1).
One could ask where the discrepancy in terms of x comes from: is it due to (i) the criteria (Vx I 1²) for e-accuracy, (ii) the function classes (PL -PP v.s. SC-SC), (iii) the step size
stromnyyycoovee.stttolyyyoooee (SC-SC) C two-sided PF. C Pi nonconvex-Pt..

---

Published as a conference paper at ICLR 2023
ratios (12(R2) v.s. 1)? We answer the question by showing the following theorem: the discrepancy in & comes from the step size ratio difference. We defer the proof to Appendix E.
Theorem (Lower bound, ratio-specific), Consider a class F(I, ,1,122 of functions [(x;;) y) with two arguments x and y, which I-smoothh yx-strongly-conve in a. and pu2-trongly-conee Suppose K1 L/p1 #1 2 с and K2 = L/ 2 cfoor some constant > 1. Then, for any step size ratio r= r33/a > there exists a function E F(L, p1, p2) with a unique saddle point z", for which simGDA with any step sizes (a, 3) = (3/r, 3) requires at least
in y.
n (mir ((aaroog(1/e))
ifr k2/c,
K =
22 (k]n2 log(1/E)),
ifc/ S S k2/C, if S c/Ki
((((22/)) log(1/E))
iterations to achieve either ||2K ==1 50 or V1(x)) S
Thanks to Theorem 3, we can say from Theorem that for any step size ratio r Z x3., we have a tight upper bound the iteration complexity K = (og(/))) of simGDA for general PL( PL problems. Note that Theorem 3 also subsumes the existing lower bound of the equal-step-size (r === 1) simGDA for s-SC-SC problems.
Given the tightness of bounds for r Z x2. natural next step is to discuss 1 S r S nr3. Recent work by Li et al. (2022) also discusses the step size ratio of simGDA. In Li et al. (2022, Theorem 4.1), the authors construct a y-side strongly-concave function" and show that simGDA with a step size ratio K2 is impossible to converge. The necessity of Z K2 implied by this theorem also applies to the -PE case. Thus, there is no hope for showing an upper convergence bound of simGDA with S S K2 for general nonconvex-PE problems. We remark that their theorem does not contradict nor subsume Theorem 3 because we consider a much smaller function class (SC-SC) to construct the lower bounds.
On the sufficiency of r 2 K2 for convergence, Li et al. (2022, Theorem 4.2) show that simGDA with r 2 en (for some e > 1) can locally converge at the iteration complexity O log (1))) for some sunconvex-stronglyy-ootn
problems, which matches the bound in Theorem 3. Our upper bounds (Theorems 4 and 5) do require Z <²2, which may look suboptimal, but we claim that our results are not necessarily weaker. One reason is that convergence guarantee is global. i.e., independent of the initialization. Another reason is that their analysis is only valid when a differential Stackelberg equilibrium? exists, whereas general PE)-PP function may not have such equilibrium (for an example, see Proposition 13 in Appendix B).
As far know, it is still an open problem whether global convergence bound for simGDA on nonconvex-PE. problems can be shown when the step size ratio r is between 2(x22) and (x2)).
EXPERIMENTS
To validate our main theoretical findings, here we present some numerical results, We focus on the (or PE(O)-SC, which is P as well) quadratic games of the form me yER- f(x; y) = 1xx T Ax + x By Cy = 1 E' f((z;))
min max
Cy
(5)
where f((x; v) = Lar A + x B.y Ju C.y + u, x v.y.
This toy example is often used numerically evaluate the minimax algorithms (Yang et al., 2020; Loizou et al., 2021; Das et al., 2022) and appears in various domains such as AUC maximization (Ying et al., 2016). policy evaluation (Du et al., 2017), and imitation learning (Cai et al., 2019)
To make the game in Equation (5) satisfy (LC and component L-smoothness, we should sam- ple the coefficient matrices and vectors carefully. First, they need to be ||ill || llz S L and > ui Em v; O. To make the primal function 4 a well-defined real-valued function
||C
.(x;)) = - 32 Lay 5 where T./p > 1: its primal function is strongly convex.
Loosely speaking, differential Stackelherg equilibrium is a stationary point (m";y") where f(x :) is locally strongly concave near y and (--) is locally strongly convex near a:"
8

---

Published as a conference paper at ICLR 2023
00
A00A AGDA-99
10
Pozzrka memraaae 73
20001 Murbbr Persiione (202
104.0 Number henttion 1200
Numbbr Inerionn 2000
(a) simSGDA v.s. BOMSGDA-RR.
(b) altSGDA V.S. altSGDA-RR.
(c) AGDA v.s. AGDA-RR.
Figure I: Experimental results on quadratic games (5), Solid lines: average across 10 different runs. Shaded regions: 95% confidence intervals 1=1.96 std). Dots: start/end of epochs. The vertical axes are on a logarithmic scale.
for any x E RRd, we choose C = - matrix and μ > 0. Then, the primal function can be explicitly written as
i= C, to be positive definite, i.e., pI 3 C for an identity
+ (x) yax (ax; y) = (A+ BC= x ==
T Mæ.
We construct matrix M A + BC-1B to be rank-deficient positive semi-definite. Letting the smallest nonzero eigenvalue of M by 14, we ensure that 4 is μ-PE but not strongly convex. We emphasize that the objective function f is not even (strongly-)conve in in general.
We compare six algorithms in total: simSGDA-RR, alISGDA-RR, AGDA-RR (as defined in Das al. (2022)), and the with-replacement counterparts of these three algorithms. To this end, on different randomly-genene generateed quadratic games and under 2 random seeds per game (i.e., 10 runs per algorithm), we run each algorithm for the same number of epochs using constant step sizes of ratio 8/ux cx2 for some constant and 62 L/p.
We report the potential function values (V,, defined Equation (2)) at every iteration. 8 Results are presented in Figure 1: the values are normalized by dividing them by the initial value. As we discussed in Section 4.1, we observe that the random reshuffling considerably accelcrates the convergence of the algorithms. Furthermore, all three algorithms with random reshufiling show more or less the same performance. Specifically, the plots for simSGDA (resp. simSGDA-RR and altSGDA (resp. altSGDA-Re -RR) are almost identical. We believe this is because we choose a random seed for each of the 10 different runs and share it across different algorithms.
Please refer Appendix G for more detailed construction, discussion, and comparative study of the experimental results.
7 CONCLUSION
We investigated stochastic algorithms based on withoutt-rellacmment component sampling, called simSGDA-RR and altSGDA-RR, for solving smooth nonconvex finite-sum minimax optimization problems, We established convergence rates under the y-side PL condition (nonconvex-PP) and, additionally, the primal PL condition (PL())-PL). We ascertain that the SGDA-RR can achieve faster rate than its with-replaccment counterpart, which agrees with the existing theory on without- replacement SGD for minimization. Lastly, provided complexity lower bounds for simGDA with an arbitrarily fixed step size ratio r, demonstrating that the full-batch upper bound with r 2 x3 for P -t. functions is tight.
Possible future directions include widening our results beyond sim/altSGDA (e.g., extra-gradient or optimistic GDA) and beyond RR (e.g., single/adversarial shuffling). As also discussed in Section 5, an interesting open question remains open: can we identify tight convergence rates for stochastic hrtth-wwithout-rellaceeen and/or deterministic GDA with step size ratio satisfying K2 X S k for general nonconvex-P4. problems?
As described in Section 4.2, AGDA RR uses only one-side gradient (Vi or V2) at each iteration; given fixed budget of gradient computations, should access components twice many times SGDA-RR. Hence, we report the values every other iteration of AGDA & AGDA-RR, for fair comparison.

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGMENTS
This work was supported by Institute of Information & communications Technology Planning & evaluation (IITP) grant (No. 2019-0-00075, Artificial Intelligence Graduate School Program (KAIST)) funded by the Korea government (MSIT). The work was also supported by National Research Foundation of Korea (NRF) grant (No. NRF-2019R A55A AAA202333)) funded by the Korea government (MSIT). CY acknowledges support from grant funded by Samsung Electronics Co., Ltd.
REFERENCES
Kwangjun Ahn, Chulhee Yun, and Suvrit Sra. SGD with shuffling: optimal rates without component convexity and large epoch requirements. Advances in Neural Information Processing Systems, 33; 17526-17535, 2020. 22
Alcksandr Beznosikov, Eduard Gorbunov, Hugo Berard, and Nicolas Loizou. Stochastic gradient descent-ascent: Unified theory and new efficient methods. arXiv preprint arXiv:2202.07662, 2022. 2
Qi Cai, Mingyi Hong, Yongxin Chen, and Zhaoran Wang. On the global convergence imitation learning: A case for linear quadratic regulator. arXiv preprini arXiv:190..03672 2019, 8
Aniket Das, Bernhard Schölkopf, and Michael Muehlebach. Sampling without replacement leads to faster rates in finite-sum minimax optimization. arXiv preprint 1xXiv:2206.02953 2022. 4, 6,
7, 8, 9, 22
Simon Du, Jianshu Chen, Lihong Li, Lin Xiao, and Dengyong Zhou. Stochastic variance reduction methods for policy evaluation. In International Conference on Machine Learning, pp. 1049-1055
PMLR, 2017.
Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial networks. Communications of the ACM, 63(11):139-144, 2020.
Zhishuai Guo, Zhuoning Yuan, Yan Yan, and Tianbao Yang. Fast objective duality gap con- vergence for nonconnex-stronglyycone min-max problems. arXiv preprint arXiv:2006.0660 06889, 2020. 2, 4, 19
Martin Heusel, Hubert Ramsauer, Thomas Unterthiner, Bernhard Nessler, and Sepp Hochreiter. GANs trained by a two time-scale update rule converge to a local nash equilibrium. Advances in neural information processing systems, 30, 2017.
Roger A Horn and Charles Johnson. Matrix Analysis. Cambridge University Press, Cambridge, England, 2 edition, October 2012. 37
Chi Jin, Pranceth Netrapalli, and Michael Jordan. What is local optimality in nonconvex-noncconcav minimax optimization? In International conference on machine learning, pp. 4880-4889, PMLR, 2020. 5, 19
Hamed Karimi, Julie Nutini, and Mark Schmidt. Linear convergence of gradient and proximal- condition. In Joint European conference on ma-
gradient methods under the chine learning and knowledge discovery databases, pp. 795-811. Springer, 2016. 4, 7, 16, 17, 19
Haochuan Li, Farzan Farnia, Subhro Das, and Ali Jadbabaie. On convergence of gradient descent ascent: A tight local analysis. In International Conference Machine Learning, pp. 12717- 12740. PMLR, 2022. 3, 8, 19, 42
Shihui Li, Yi Wu, Xinyue Cui, Honghua Dong, Fei Fang, and Stuart Russell. Robust multi-agent reinforcement learning via minimax deep deterministic policy gradient. In Proceedings of the AAAI Conference Artificial Intelligence, volume 33, pp. 4213-4220, 2019.
10

---

Published as a conference paper at ICLR 2023
Tianyi Lin, Chi Jin, and Michael Jordan. On gradient descent ascent for nonconvex- mini- max problems. In International Conference on Machine Learning, pp. 6083-6093, PMLR, 2020. 6,
Mingrui Liu, Zhuoning Yuan, Yiming Ying, and Tianbao Yang. Stochastic AUC maximization with deep neural networks. In International Conference on Learning Representations, 2020. URL
https: / http://ppeeeeeeeeeeeeeeee net/
1,
Nicolas Loizou, Hugo Berard, Gauthier Gidel, Ioannis Mitliagkas, and Simon Lacoste-Julien. Stochastic gradient descent-ascen and consensus optimization for smooth games: Convergence analysis under expected co-coercivity. Advances in Neural Information Processing Systems, 34: 19095-19108, 2021. 8, 15, 44
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. In International Conference Learning Reprexentations. OpenReview.net, 2018.
Chinmay Maheshwari, Chih-Yuan Chiu, Eric Mazumdar, Shankar Sastry, and Lillian Ratliff. Zeroth- order methods for convex-concave min-max problems: Applications decision-dependent risk minimization. In International Conference on Artificial Intelligence and Statistics, pp. 6702- 6734. PMLR. 2022. 2,
Konstantin Mishchenko, Ahmed Khaled, and Peter Richtárik. Random reshuffling: Simple analysis with vast improvements. Advances in Neural Information Processing Systems, 33:17309-17320, 2020. 2, 21, 22, 44
Dheeraj Nagaraj. Prateek Jain, and Praneeth Netrapalli. SGD without replacement: Sharper rates for general smooth convex functions. In International Conference on Machine Learning (ICML), pp.
PMLR, 2019. 2. 6
Lam M Nguyen, Quoc Tran-Dinh, Dzung T Phan, Phuong Ha Nguyen, and Marten Van Dijk. A uni- fied convergence analysis for shuffling-type gradient methods. The Journal of Machine Learning Research, 22(1):9397-9444 2021. 2, 2, 25
Maher Nouiched, Maziar Sanjabi, Tianjian Huang, Jason D Lee, and Meisam Razaviyayn. Solving class of non-convex min-max games using iterative first order methods. Advances in Neural Information Processing Systems (NeurIPS), 32, 2019. 2, 4, 17, 18,
Shashank Rajput, Anant Gupta, and Dimitris Papailiopoulos. Closing the convergence gap of SGD without replacement. In International Conference Machine Learning, pp.
PMLR,
2020. 2
Aman Sinha, Hongseok Namkoong, and John Duchi. Certifialle distributional robustness with principled adversarial training. In International Conference on Learning Representations, 2018. URL /tttts:s//ppeeevviee... net.eeeeeeeeeeeeeeeeeeeeee.eeeee forum? id=Hk 6xP
Jiahao Xie, Chao Zhang, Zebang Shen, Weijie Liu, and Hui Qian. Efficient cross-device federated learning algorithms for minimax problems. arXiv e-prints, pp. arXiv-2105, 2021. 6, 14, 45, 46
Yan Yan, Xu, Qihang Lin, Wei Liu, and Tianbao Yang. Optimal epoch stochastic gradient descent ascent methods for min-max optimization. Advances Neural Information Processing Systems, 33:5789-5800 2020. 2
Junchi Yang. Negar Kiyavash, and Niao He. Global convergence and variance reduction for class of nonconvex-noncooeen minimax problems. Advances in Neural Information Processing Systems, 33:1153-1163 2020. 2, 3, 4, 6, 8, 18, 40
Junchi Yang, Antonio Orvieto, Aurelien Lucchi, and Niao He. Faster single-loop algorithms for minimax optimization without strong concavity. In International Conference on Artificial Intelli- gence and Statistics, pp. 5485-5517. PMLR, 2022.
Yiming Ying, Longyin Wen, and Siwei Lyu. Stochastic online AUC maximization. Advances in neural information processing systems, 29, 2016. 1,8

---

Published as a conference paper at ICLR 2023
Yaodong Yu, Tianyi Lin, Eric V Mazumdar, and Michael Jordan. Fast distributionally robust learn- ing with variance- reduced min-max optimization. In International Conference on Artificial Intel- ligence and Statistics, pp. 1219-1250. PMLR, 2022. 2, 6
Zhuoning Yuan, Yan Yan, Milan Sonka, and Tianbao Yang. Large-scale robust deep AUC maximiza- tion: A new surrogate loss and empirical studies on medical image classification. In Proceedings of the IEEE/CVF International Conference on Computer Vision. pp. 3040-3049, 2021.
Chulhee Yun, Suvrit Sra, and Ali Jadbabaie. Open problem: Can single-shuffle SGD be better than reshuffling SGD and GD? In Conference on Learning Theory, pp. 4653-4658, PMLR, 2021. 2
Chulhee Yun, Shashank Rajput, and Suvrit Sra. Minibatch local SGD with shuffling: Tight con- vergence bounds and beyond. In International Conference on Learning Representations. Open- Review.net, 2022. 2
12

---

Published as a conference paper at ICLR 2023
CONTENTS
1
Introduction
1.1
Summary of contributions
2
Problem setup
2.1
Notation
2.2
Algorithms: simSGDA-RR RR & altSGDA-RR
2.3
Assumptions and definitions
3
Main results
3.1
Potential function V
3.2
Main theorems: upper bounds of convergence rates
4
Comparison with related works
4.1
Comparison with stochastic with-replacement setting
4.2
Comparison with other works on stochastic without--eplacemenn setting
4.3
Comparison with deterministic setting
5
Lower bound for (full-batch) simGDA using separate step sizes
6
Experiments
7
Conclusion
Mini-batch SGDA-RR and convergence rates
15
Technical propositions
16
B.1 Function classes: PE condition, smoothness, and more
16
B.2 Without-replacemment sampling
20
B.3 Basic recurrence inequality
22
Proofs for (mini-batch) simultancous SGDA-RR
22
C.I Warm-up: proof sketch for b =
22
C,2 Epoch-wise representations and bounding noise terms
23
C.3 Recurrence inequalities for general smooth nonconvex-PE. objective
27
C.4 Convergence rates for smooth nonconvex-PE. problem
30
C.5 Convergence rates for smooth primal-Pt.-Pt problem
30
Proofs for (mini-batch) alternating SGDA-RR: focusing on changes the proof
32
D.I Epoch-wise representations and bounding noise terms
32
D.2 Bounding noise terms: bit different proof of Lemma 18
33
D.3 Recurrence inequalities for general smooth nonconvex-PP. objective
34
13

---

Published as a conference paper at ICLR 2023
D.4 Small step size assumptions...
34
Proofs for lower bound of deterministic full-batch simGDA
35
Remark on smoothness assumptions and Lower bound with-replacemmnt SGD(A)
39
G Experiments: quadratic games
41
G.1 Parameter choices
G.2 Comparison: the effect of component discrepancy
43
G.3 Comparison: the effect condition number
43
G.4 Comparison: the effect of batch size
44
H Omitted comparison with related works
45
H.I Comparison with Xie al. (2021)
45
14

---

Published as a conference paper at ICLR 2023
A MINI-BATCH SGDA-RR AND CONVERGENCE RATES
In this appendix, we present an algorithm that extends simSGIDA-RK and altSGDA-RR by using mini-batches of size b 1. For simplicity, integer multiple of the mini-batch size b in our analysis; i.e., n by for some integer 2 1. One can extend this to the case when n. is not necessarily multiple of b (e.g., = b(g 1) + where q 2 1, 8 E [6]) so that there are q mini-batches of size and one more mini-batch size s I b.
assume that the number of components is an
Algorithm 2 Mini-batch SimSGDAVIISSDA-RR
1: Given: The number of components b(g 1) (q: number of iterations per epoch); mini-batch size the number of epochs K; step sizes a,
2: Initialize: (at): yo) E IR x 18
3: for & [K] do
4: Sample dg ~ Un)
RR: uniformly randomly shuffle the indices every epoch
5: for E [g] do
6:
B = (ox 6(1 - <j bbj [n]] 2t = =x
Miiii-btthh a of component indices
7:
Eie V (
8:
if simSGDA-RR then
9:
yi = v + Eiest (2/ else aRISGDARRR then
p simultaneous update: ar y
10:
11:
y yーー EieBt (2f((=;; yo ++1) (3/ yn,
alternating update: y
(
k+1,
Next, we illustrate the generalized versions of our main results (Theorems and 2) for Algorithm with mini-batches of size 6 > 1. Let us assume n 2 2 because the case = 1 trivially boils down to simGDA or altGDA. We defer the proofs for simultaneous updates Appendix C. We present the parts that change in the proof for alternating updates in Appendix D.
Theorem 4 (Nonconvex-PE., mini-batch SGDA-RR). Suppose I satisfies Assumptions Let = 4. Choose the step sizes a and B by a = Bir for some r 2 14k and
and 4.
1
vx(2b) (n?(
8= min
6Lm 1 n-b
for some numerical constant > batch size b (a divisor of n) satisfy
Then, mini-batch simSGDA-RA and altSGDA- with mini-
(V Σ [|)v 1=1
K
n2 b
L2
n- 1/3
1
+ 2cr
K
11
nK2
n-
Theorem (PL mini-batch SGDA-RR). Suppose f satisfies Assumptions 1, 3, 4, and 5. Let A = 4. Choose the step sizes a and ß by a B/r for some r 2 14k3 and
2r
Vi(=b)unn2
8 b- min
max
1, log
6Ln 1+ a-b A
JinK
8c3
B
for some numerical constant batch size b (a divisor of n. satisfy
Then, mini-batch simSGDA-RR and altSGDA-RR with mini-
K
K B kinn2
b
BIV [+)] 50 Va(=b) exp
+
12K1T R-b
As side remark, some works consider a sampling method called b-minibatch sampling where all the elements in each mini-batch are distinct (i.e., without--relacemment component sampling per mini-batch), egg. Loizou et al. (2021, Definition 2.1). However, there significant gap be- tween this method and ours: any two distinct mini-batches sampled by the b-minibatch sampling can intersect with each other (i.e., mini-batches are sampled with replacement), whereas, in each epoch of our Algorithm 2, all the mini-batches are mutually disjoint.
15

---

Published as a conference paper at ICLR 2023
B TECHNICAL PROPOSITIONS
Notation. Throughout this appendix, we use X = Rd and y = R Given a closed set S C RR denote the of all projection(s) of 12d onto S, i.e., the nearest point(s) in S from v, by [1) == arg min | -wll-
B.1 FUNCTION CLASSES: PL CONDITION, SMOOTHNESS, AND MORE
Proposition 6 (R 2 1). Let g be an L-smooth which is bounded below by g² Then, for any
2,
[Vg(z)]1 s 2L ([(x)) -g'l.
9 is p-PL as well, then μ S L. Consequently, the condition number == L/
Proof.
Since g is L-smooth, for any and y.
g" $ r - g(x) + (Vg(z). x)) + 11 x=12
(6)
Now define convex quadratic function ر2g (y) of y as
T. hx( = ((x) + (Vg(z), σ²) 2 lly x:1?
Since its gradient is
Vha(v) Vg(a)) L(y x))
y" x (g(z) is minimum of hy Plugging y yy to the equation (6), we get
9" Σ g(x)) -Vo(=),-1vvl Vo(())
L
Vg(2z) g(x) 2L |g(22)1
1
Rearranging the terms,
[V 2L [g)x) g"l
we additionally utilize PE inequality with g" min g(z))
[|Vg(>)]1 2 2p (zx g²],
we directly yield μ S L and thus x == 1.
1
Definition 1 (Karimi et al. (2016)). Consider X R. Let up IIx- (x) be projection of onto the optimal set X = arg min g(x).
(I) We say g satisfies j--strong convexity (SC) if g(x') 2 g(x) + (Vg(x), xx) +
: || - x|I for any x, X.
(2) We say satisfies ju-restricted secant inequality (RSI) if (Vg(#), x xp) 2 1| 2z12 for any a e X.
(3) We say g satisfies p-error bound (EB) condition if Vg(()) > μ [xp for any x E
(4) We say g satisfies p-quadratic growth (QG) condition if g(æ))ming, min g(x') 2 x,- for any x E X.
Proposition 7. From Definition 1, The following implications are true.
P-SC implies μ-Pt. and p-RSI.
p- PL implies μ-QG and μ-EB.
μ- R-RSI implies μ-EB.
F-EB and T--smoothness together imply (.P...
16

---

Published as a conference paper at ICLR 2023
Proof. Most of the proofs originated from Karimi et al. (2016, Theorem 2).
(SC = PL) Substitute a to zp and x' to æ, respectively, from Definition 1.(1).
(PL QG & EB) See the proof in Karimi et al. (2016, Theorem 2)
(SC + RSI) We know μ-SC = μ-PPt + μ-QG. From Definition I.(1) 1.(4),
(Vg(z), xp)
SC g(x) g(xp)) +
# upp x=|
QG 4
I - x=| 2
+ p 2
u æ1|² = 1xp x1(²
This implies y--SII.
(RSI = EB) See the proof in Karimi et al. (2016, Theorem 2).
(EB & smooth = PL) We use Vg(pp)) = 0. By L-smoothness and μ-EB condition,
smooth
(Vg(z)). x - app) + L 2 | xpp 2 x x.pll 1
g(x) g(0p))
|g(+))1
2p
This implies (1º/L)-PE condition on
Proposition 8 (Lipschitz continuity like property of y (x)). For aecamoottfuuctttii g xxy I. suppose -g(x;-) P22 Let K2 = H/
Consider any Bg E X. For any yú V arg maxyey ( y). there exists y EV
arg ya g(x1: 3) such that 11 vil S K2 x xill-
In fact, it is enough to choose yi as a projection of yo onto the set V" namely, yi E Ty (16).
Proof. We borrow the proof from Nouiehed et al. (2019, Lemma A.3).
Recall ((x) == ma ( y²) By PL inequality and smoothness of g,
2p2 (#(x1) - g v6)) - V2 ( 16
V[ v6) 22g mo; 26 T.? ||l moll
The second equality applies V ( 36) 0, since yo E arg max, g y).
Moreover, note that -g(x1i)) satisfies μ2 P2-QG condition (:: Proposition 7). To apply this, utilize our choice of y
((x1) g ((:1:36) 2
//2 2 1yf -
As a result, we have ق3 l1 will < L 1 x 11. This completes the proof.
Proposition 9 (Smoothness of primal function). Consider the same function 9 as Proposition 8 Then, the function ((x)) maxyey g(x; y²) is differentiable with
vΦ(x)) Vig(=; y² (x)), regardless of the choice of y²(x) E arg gaxg(xx;)))))
yey
Moreover, is I(K2 + 1) 1)-smooth, where n2 = T./12-
Proof. This is already proved in Lemma A.5 of Nouiched et al. (2019). However, we present bit different proof without using second-order Taylor expansion. To start, recall ) arg ya g(x; y). That is, we could choose any y²()) E )
We first show the differentiability of Φ. Fix unit vector E = R4: |u]| 1. Let any h > 0.
We first claim that there exists a path p : (-h, h] + y Rdd which continuous at 0 and p()) V In fact, let p(t) be projection of yd (xx) (that we chose) onto the set y ((
17

---

Published as a conference paper at ICLR 2023
Then, p(0) y (x:), and by Proposition 8, we have ||((0) p(t)ll I Ki || (æ + tu)l K2t.
This shows the continuity of p(t) at t = O. Now, note that there exists a tt E (0, h) such that,
(x + ha) - ((x))
- g(x + hu; p(h)) - g(x;; p())
= {((( + hu: p(h)) - g(x + hu: p(0)) + {g(x + hu:p(0)) - g(x; p(0))
2 ++ (Vig(æ + lu ((); lu),
by mean value theorem (applied to the first argument). We have the inequality at the last line because g(x hu; p(h) 2 g(x + hu: p(0)), since p(h) E Va+hu) With similar logic, there exists t2 E (0, h) such that,
(xx + hu) ((x))
= g(x + hu; p(h)) - g x: (0))
= {g(x + hu; p(h)) - (0 p(h)) + (o(=: -((=:((0))
& (Vig(æ + (2p;:(h)) hw) +
To combine these two inequalities into single line,
(Vig(æ +tu: u) S o(x hu) 4(x) < (Vig(æ + tzu: p(h),,)
Using the continuity of p(-) and Vig(:;-) (: has Lipschitz continuous gradient), we can deduce that the directional derivative of direction u (denoted by Du 4) is in fact
D (xx) (V (ig (a)), u).
by taking the limit h 0+ Since is arbitrary, we can conclude that VQ(x2) V1 (igg
The proof of Lipschitz smoothness of 4 exactly follows the proof by Nouiched et al. (2019). Con- sider any æo. æ1 X. As Proposition choose any yú E V and yi E Hl., (16). Then,
V < ||
Vig vū) V 1g( 15 wi)ll
VVig(aa)) yū) Vig(<1 yblll + | [V1g(<1:66) - Vig(zi:
L [1|æz) x1 1 vil
I L(1 + N2) ||z0 - x1ll-
The last inequality holds because of Proposition 8.
Proposition 10 (æ-side PE = primal PE.. Suppose 9 X x y + is L-smooth and two- sided PL with constants bn and #2- Then, g satisfies primal PL condition: the function Φ(x) maxy Ey g(x; y/) ) is i PPL As result, a smooth two-sided PL function is PL(D)-P
Proof. See Lemma A.3 of Yang et al. (2020).
Definition 2. Consider g X y R. Then, the point (x":y") X x y is called
(i) a stationary point of if V "ig(x";"" = V2g(#"; = O.
(ii) saddle point of g if y() I g( 3n) g( y¹) for all x, y.
(iii) global minimax point of g if g(z" y) S g( S max, g(x;; y for all æ,
(iv) global maximin point of g if min g(x'; y) gi y²) S g(æ; y²) for all y. Proposition 11. Consider a function g X x y + TR.
(1) In general, saddle point of g is global minimax//mxximin point.
(2) Let ((x) maxy g(x; y) and x² = ming ((x)) be well-defined. Let X be constant. In general, point (x";y") is a global minimax point of g if and only if
Va(a" {((((z) क0 + (Φ(x))
g(æ; y)] 0.
18

---

Published as a conference paper at ICLR 2023
(3) If is smooth nonconvex- PL, then global minimax point is stationary point.
(4) If g P- then there exists a global minimax point (x"; of g. As a result, if is also smooth, then the point (x";y") is stationary point.
(5) If g is smooth two-sided PL, every stationary point is saddle point. As result, there exists a saddle point (z"; of
In particular, smooth two-sided PL functions enjoy the "minimax theorem," " which establishes "min- imax maximin." "
Proof. (1) (saddle point + global minimax & global maximin) This is straightforward by the defi- nitions: for any x and y.
min g( S g(0";""0" S g(xt :a"d";"")) S g(;
max g(;; 3/²
(2) (global minimax + VA The terms ((x) $* and (xx) g(:; y) are non-negative. Hence, V (2 y) is non-negative, and Vi (x"""y") = 0 if and only if d= ((xx) y"",
which is equivalent the global minimax point condition.
(3) (smooth nonconvex-PL. global minimax + stationary) Suppose (x":y") is global minimax point. Since g(0:;
(<a'y) y) S g(x";;"""">"""" 3²* for any y. (xx") max, g(ø"; y) = g( yy) Thus, & has
minimum g( yy"
at æ = x By Proposition 9, (-) is a differentiable function and we have
Vig(=": = V ④ (x)) = 0.
Also, since differentiable function g has maximum at y", we also have V2g("";;"" y²) = 0. Therefore, (x";"") is a stationary point.
(4) (P 3 global minimax) Let x" E arg min ((x)) and y² E arg maxy [(x;;)) Then, f(x", y²) (xx") Φ- noted in (2), (x=, is global minimax point. By (3), it is in fact stationary point, when g smooth as well.
(5) (smooth two-sided PE: stationary = saddle) Let (x";y") be stationary point. By PE inequali-
ties, for any x and y.
0 V2 g ( y )1( > 24 (max g(x" : y) g(>"; yy")) 2
0 V Vig(=": y 1] > ( ; y²)
min g y 2 0.
Since (41, u42 > 0, these imply max, g(x y) saddle point. Note that (4) and Proposition 10 together proves the existence of stationary point of Therefore, there must exists a saddle point, which is also pointed out by Guo et al. (2020. Lemma 8). This concludes the proof.
= min (z; y"). Thus, (x"; is
We remark that, in the proof above, (3) is false for general (nonconvex-nonccocaavv)) functions. Only local minimax point can ensure stationarity (Jin et al., 2020). As remarked by Jin et al. (2020) (Figure 2 of their paper), the function ry cys(y) has non-stationary global minimax points (0, #T).
The following two propositions are for showing that general two-sided function may not have differential Stackelberg equilibrium defined as Li et al. (2022, Definition 3.1).
Proposition 12. Let g be p-strongly convex function on R.. Consider any matrix M E maxm with positive rank. Suppose that 0 the smallest nonzero singular value of M. Then g (My) is PL function of E Rm
Proof. See Karimi al. (2016, Appendix B) for the proof.
Proposition 13. Consider twice continuously differentiable function h : R" IR + RR. That is, for some constants μr H2 > 0, h(x, is Y1 -u-strongly-comve in and - h(x; y) is j1-sttrogly-coonve in y. Let (x² "o";"" y²) be the unique stationary point of h. Of
19

---

Published as a conference paper at ICLR 2023
course. it is differential Stackelberg equilibrium of h. That is, the hessian matrix (²h(x";y") at that point is written as
V h(a"; : y²) V2h(2" :y") = V2,1 yx)
V 222h("111"
C
B
22 (22(("yy"))
= B
-A
then A and C- BBB are both positive definite matrices. Consider a function g R R2 R defined by g(:: y) = h(Mx; Ny) for some matrices M E R N E R Then, is two- sided PL. Moreover, each stationary point of g may not be differential Stackelberg equilibrium in general, for example, when 8 < 4.
Proof. Because of Proposition 12, g is clearly two-sided PL function.
(æ; y) is a stationary point of then it must be an element of an affine set {(0; y) E R x R Mx x=: y²) This is because
V Vig(ayy) y)
M Vi M(Mæ; Ny)
Vg(a; v)
V2 g(x;
N V2 h <Mx;; Ny)
and only V MMMx; Ny) = and <xa: Ny) = 0, being equivalent to Mæ = x= and Ny y² Furthermore, the hessian of (æ: y) is
[MTV, (MM;; Ny)
M MM; N
V gg((;))) = N V2,1 h(Mx; Ny)
N 22
MTCM M BN (M BN) -NTAN
If < q. the q matrix N AN cannot have full rank, thereby it cannot be even invertible. This implies the stationary point (x; y) cannot be a differential Stackelberg equilibrium.
B.2 WITHOUU--REPLCEMMEN SAMPLING
In this subsection, provide useful proposition for analysis of miii-batchinng approach under authout-replacemeen sampling. We consider the case of mutually disjoint mini-batches in a whole epoch, not only applying without--relaacement sampling each individual mini-batch.
Consider a collection of n vectors 01,..., Vn E TRd Suppose we uniformly randomly sample a permutation [m] [m]: a Unif(S.). Define
(sample mean) and
10 m||2 (sample variance).
Fix any b E [ri] and let n b0q 1) for some integers q 2 and [b]. Now, divide the indices [n] into batches, with exactly items per batch (except for the last batch when s < b). as follows:
= (o()) 101 < < bi [m]}
(1 E (d))
For each batch We, define
wt
Σ SEW
24 (batch mean).
W
For any ls [q 1], define
my = 7: Σ
w. (accumulative average of batch means over k)..).
Of course, we may simply take m, m (deterministically) for = 9. Thus, because of the randomness of obtain the mean (vector) and the variance (scalar) of m& follows. Proposition 14 WWthhout-replacement sampling). Given the setup above, for any and 1,
E mx = m and E ||mm- ml]3] (n bk)
bk(n 1) 7
(Of course, if or q. Eilim, m 2 since my m.)
20

---

Published as a conference paper at ICLR 2023
Remark. As special case, if bq (namely, divides and b), then for any k S
(g k) k(n 1)
E m+ mll
we further assume s = 1 and g = n, this proposition recovers Lemma of Mishchenko et al. (2020).
Proof of Proposition 14. Since a is uniformly randomly sampled permutation, it is easy to obtain that
B[ea()) = E[w,,] = E[mpg] = m,
for any i E [n)] E [g). and & E [d]-
The covariances between vo(i)'s 's can be deduced from the proof by Mishchenko et al. (2020, Lemma as follows:
if j. =f
Cov(Uo(O) Po()) = E [(va()) - m, 2o() mm)] =
Thus, for each E 14]. the variance w, is obtained as
I0, - ml
E
Σ iEW.
(v
m)
W
1
Σ E
||u ml|²] + Σ
Cov(ui, 00))
iEW;
ijeW, $5$
1
(-,--)
2
W Well -))
[W
IWI((W)) -I
1)
which also be directly deduced by Lemma of Mishchenko et al. (2020). We notice that this does not depends on the size the batch W,.
Next, we look at the covariances between distinct w.'s. For pair of distinct integers u E [q]. by the bi-linearity of covariance,
Cov(w:, w.) [Wal- (Wul
1
Σ
Cov(u, vy))
(KJ)eW....
1
E
72
pA [Wul
(KJ)EW.W.
The second equality holds because W; and Ww are disjoint set of integers whenever + u.
Now, fix any [g 1). Note that, by our mini-batching strategy. [W& b for every t q. Therefore, by definition of mx.
|| ml|
we m)
E
1 ml|²]
Σ
Cov( Wa)
22
b(n - -1-b, x22 x²)
n
bk: bk(n - 1)
k:
+ k(k - 1)
71
21

---

Published as a conference paper at ICLR 2023
B.3 BASIC RECURRENCE INEQUALITY
In this subsection, we present a basic result of a recurrence inequality. It serves as a stepping-stone of our convergence bound, particularly the end of the proof (Appendix C.5).
Proposition 15. Let {ak [k=1 be sequence of non non-negative numbers satisfying the following re- currence inequality:
ax+1 S (1 (1- bm)as + cij"++1
where b, and n are non-negative real numbers such that by E (0, 1), and m is a non-negative integer. Then, for any integer K > 1, we have
ak+1 S (1-br)** 01 + en
Proof. We proceed with induction on K = 0, Note that
01 (1 bn)aai -rn""/// /b.
This shows the case when K = 0. On the other hand, if K 2 1, by an inductive assumption,
a 2 (1 by)) ax) + cT)
S (1 br)) ((1 bu)) k K0 + on /b) + cn)
(1 br)) K a1 + cni""//0 /b.
C PROOFS FOR (MINI-BATCH) SIMULTANEOUS SGDA-RR
In this appendix, we provide a convergence analysis for the mini-batch simSGDA-RR (Algorithm 2) on both general nonconvex-PE. problems and primal-Pt.-PE, problems. The two cases mostly share the same proof strategies; they only diverge the end of the proofs. The proof long; we first pro- vide the sketch of proof in subsection C.I;; then, we provide the full proof by dividing it into follow- this appendix. The proof for the alternating counterpart (minibatch altSGDA-RR) can be done with some modifications illustrated in Appendix D. All technical propositions required for the proofs can found in Appendix B.
up subsections
C.I WARM-UP: PROOF SKETCH FOR =
Here simply consider the proofs of Theorem and 2 for simSGDA-RR, which is fully stochas- tic case (mini-batches of size b = 1). The proofs for altSGDA-RR can be done with slight modifi- cations.
We start the proof by aggregating all updates throughout an epoch to obtain an "epoch-wise" update:
x 2 nag g² = Σm V yo
(=
k+I = yo n. h² === = n Σ (2
The reason is that the sampled components in each epoch are dependent to each other that it is much harder to deal with each iteration individually. The strategy of updatc-aggreeattio is quite general for analysis of optimization algorithms involving without-replacemmet sampling (Ahn al., 2020; Mishchenko et al., 2020; Nguyen et al., 2021; Das et al., 2022). We assume that the interme- diate iterates = 2 stay close to the starting iterate z of epoch which can be ensured by small step sizes, Then, we can approximate the aggregated epoch of SGDA-RR as a step of simGDA applied to f Σi= fú, with approximations g x Vif(zū) and h (2)()
With Assumptions and note that the primal function (--) (L+ (////22)sssoooo -smooth (Proposition 9). Applying this and L-smoothness of -f. we can have the following inequality (Lemma 16):
() (z(=t) - ((A 1)/2) (+))))
+ (A 1)ma (T V {=+)))
+ (na/2) f( (23/2)
V2 [2f(=))]] 2
+ (A + 1/2) na |وg* v=)(>>) | (n 11a
22

---

Published as a conference paper at ICLR 2023
Hence, to guarantee the fast decrease of V (=())) is important control the "noise" terms for GDA
approximations, | 1 f=t) and || h+ k V2 f(ū) in the last line of inequality above. By applying the tools for without without-replacent replacementn sampling (Proposition 14), we can actually upper-bound the conditional expectations of both noise terms by
21. 2m.2n(n + A) a² V s(=i)| B² V ((=))l)) + 2T.2n((² + BB)B. (Lemma 17 & 18)
Then, by taking advantage of several properties of smooth nonconvex-PE. functions (e.g., Proposi- tions 7, 8, and 9) and some small-step-size assumptions (e.g., B (1/nnL), 3/a = 12), we eventually have
E [Va(=)+t]] - E [Va(=))] s -naB ||
(Ixgna / 2 ( - [(200) + Ca.
where C 2 0 is a constant (with respect to k) depending on L, n, B, and r 3/a. (Lemma 20). We note that the step size ratio 2 12 is crucial for showing that the coefficient in front of the term E [0()]) [ [=(]] is non-positive: even if it is possible with r S xž we must assume that 22 upper-bounded by positive numerical constant, which is not desirable for showing convergence bounds. Thus, we expect that different proof strategy should be applied to avoid the requirement r 2 x3 on the step size ratio.
The proofs of Theorems and diverge from here. The rest of the proof is mostly about choosing appropriate step sizes and solving the recurrence inequalities.
The full proof of Theorems 4 and 5 starts from the following subsection.
C.2 EPOCH- EPOCH-WISE WISE REPRESENTATIONS AND BOUNDING NOISE TERMS
Before starting the proof, we again remark that we assume that the mini-batch size divides the number of components n (namely, q := b is positive integer) for simplicity: thus, readers who want to read proofs for fully stochastic case (i.e., b = 1) can substitute n to every q. Also, there problem in treating any fraction with positive numerator and zero denominator +00. Moreover, we simply regard (q 1)/(n - 1) = when n =
We start the proof by aggregating all updates throughout an epoch to obtain "epoch-wise" update equation. The reason is that the sampled components in each epoch depend on each other, so is much harder to deal with each iteration individually. At iteration we use a mini-batch
[n/b] [q] of epoch k E [K].
B == (ox b(t 1) < S bt. E [n]]-
To ease the analysis of Algorithm define the following sums associated with (partial) gradient oracles point (æ; y) over the mini-batch:
( = 1 -
- ViSit)) REB!
hx(2) ( ) E
By Assumption 1, of and h are L-Lipschitz continuous. Computing the average of them over a whole epoch (=h, =) we define
g" Df ht
t=1
Then, by summing up the updates in the epoch k. summarize the epoch as follows.
z 2t -aag,, ybt1 = yā g
(simSGDA-RR)
We may assume that the intermediate iterates zf..... z epoch k which results from, e.g., small step sizes. Then, we can approximate the aggregated epoch of SGDA-RR as a step of simGDA applied to In_ fi: g* ~ (z)(z)), h & (2)(z)) In other words.
* stay close to the starting iterate z of an
k+1
L qa (zf
yo e vs (z
(zsimGDA)
With Assumptions 1, 3 and 4, we can yield a naive (but complicated) upper bound of the gap +2(+) Va (2 only applying the smoothness of and -f, without any assumptions on step sizes.
23

---

Published as a conference paper at ICLR 2023
Lemma 16. Suppose that Assumptions 1, 3 and 4 hold. Let rig L/ L/2,, where p2 is PL constant of -f(x; )). Then, the mini-batch simSGDA- RR satisfies that
(= (x)
)
Vx(=t)
A=1 1
+ (2 + 1)ga -
ga
2
qa
-8 Vef(z$)]1
A 2 qa |g* v+5(=)) ||
q3 h² (2)()
[A {(A + (kg + + + 1) Lya] qo 1g 01 2 (1 Ly3) 98
|10/1²²
Proof. By definition of Vx. the following equation holds:
V2 (=)) = (A + ( (2 - ((a0)) + [5 - ((20-11)
(8)
First, we seek for an upper bound of (axb - (xxt). By Proposition 9 L(ke + 1)-smooth. Hence, we have
((ab+t) ((x()
20) + L(ng + 1)
(Vo((r)) 20t1 -
[00
2
qa (v
Llkg + 1)
q
2²a |19
qa
{1 (|v0(2))
||
| - | / (20)) - 9 [/] + 2
T[k2 +1)
qp q²a² ||
2
qa
qa |( 1²1 qa
2 (1 L(n2 + +))aa) 1
2
qa
+ gox
() V V r( + qqa |وg - (+)()
qo
(1 - L(ke + 1)ga) ||"²12
(9)
2
The third line is due to polarization equality and the last inequality applies Young's inequality." 10
Next, applying Assumption 1, L-smoothness of f(:-) yields an upper bound of f(=)) - f(z)" (
f(x)) 1(
S (v)())),, +, xt) + L k+l =011
2 =
= [ x+1 - =8) - (V2((=)), stt - v + 2
|
++1 20l1
+ _ 11 - 2/
I "² 2 || + 2 3² |
= qa (Vif(=0),
g²) q8 (V2f(=)), h²
2
qai
vif(at))
qa
l vif(2
12 + qa
(1 + Lqa) ||
2
2
2
93
9
q3 (1 (1) |
|2)
+ 2
| -2/((
(10)
2
The last equality is due to polarization equality. Lastly, substituting (9) and (10) to (8) finishes the proof.
We remark that the last two terms of the inequality (7) can be simply ignored by applying small enough step sizes. However, the terms in the third line of (7) are non-negatives terms related to the
FFor any a, b E Rd, For any b E RR. la b1l2 < 2 ||a|| + +2|b
2(a, b) = ||a|| + ||b|1 I|a b1p2.
24

---

Published as a conference paper at ICLR 2023
"noise" of approximation gf Vzf(zE), h = V2f(=(). Hence, it is important to control the noise terms ||g - V and || ha v2f(=b)] to guarantee fast decrease of V*(=5).
Lemma 17. For mini-batch simSGDA-RK define
Gp := ー -
- =
(11)
9 1=1
With Assumption 1, then
||g* - viS(= S G₂ and | v2](()1 S 1.
As a side remark, Gk = 0 when 9 = 1 and, in particular, n =
Proof. Recall that Σ (z) (zf and Ex hz(2) = V2f(z). By Lipschitz continu- ity and Jensen's 's incquality,"
1|g - v=f(=
g. (z(_1) g. (=+i)
=
1
g (z gt (1 1
Σ 1/-1
2 2)
Similarly,
2 S q m=1
hh v2f(2())1
- - =b11
This concludes the proof.
Thanks to the lemma, it suffices to bound the term Gs. One can notice that it also represents how far the intermediate iterates 2t are from the pivot z in average. Before moving on, we define an sigorithm-specifee symbol denoting conditional expectation.
Definition 3. We denote conditional expectation of a random variable X given all iterates of the first k 1 epochs by E& [X] = B[X 2 2!...., 2 =k11 In particular, if k 1, it boils down to conditional expectation given only the initial iterate z).
We get upper bound of (conditional) expectation Eg [Gk] in the following lemma, which extends a lemma of Nguyen et al. (2021, Lemma 6) to our minimax problems.
Lemma 18. Suppose that Assumptions and 2 hold. Assume that the permutation d% is sampled uniformly at random from S.. Then, for any step sizes 0,3 satisfying a² + B2 S 1)L" the
iterates {2) (2) )iz of the kitth epoch of mini-batch simSGDA-RR satisfies (for n n>>
G& 22 x2+ 669
- 1) 1 (a (a21\viS(=b)1' + 8 [[ A)
+ 29(9 - 1)
n-1 (a² + BB
1
Proof. Note that G 0 when g 1 by its definition. From now, we may assume q 1 and n > in this proof. By summing the first E l - 1] updates of the k-th epoch of mini-hatch SimSGDA-RR, we have
1
Σ m))))t)))
at x to
x¹ = vt + tB
j=1
For any n vectors ai,...,
an,
Σイ= 0s
||
s ΣE 1,.112
25

---

Published as a conference paper at ICLR 2023
Then we can bound the following squared distance.
1 1 - (
| - ab'l" =
22
I 32
Σ و (2) - c
+
7 1=1
1
- - v
+ [(i((ttt
2
S3a2t Σ
|1a5/ (z}- وج (= 2 + +aa22
1
of -v5(E)))
+ [
j=1
j=1
12
I <3a Σ || =b11? + 3a²t²
Σ 9 (=x) - vIf(Et)
+ +1
- - -v
S $3a²13 1,2L. yGs + 30222
+||V,/(=3)1
(12)
The second and third lines are due to Jensen's inequality. The fourth line is due to L-Lipschitz continuity of gf. Likewise,
ト hラ (=0) - verlet)
+ +IV0r1=631*
| všll s 382 L2t- 90k= - -382
(13)
Summing up (12) and (13),
b z 1| = | - 2/ + -1 - y
2
| ト Eog(Eb) - vib()))
S 331a² + B²) 1.11,,21. lgGk + 3a21?
+ +
1 c 1
+ +352g2
Σ h (1(())
V2f(=t)
+ [2f(=t)1
(14)
Taking (conditional) expectation E, (given 2B) to inequality (14),
Ex
|| | =/1
(14)
I 3(a² + +32) (Ba()))
i + 3a2??
||
V (1)())))1 +33322 (+)())))
+ 2B
+ 1
M - - (15)
Here we take advantage of the without--eelacemmet sampling. Putting V. f(((z))) + v; (s E {1, 21), one can realize a correspondence between the quantities that arise from our algorithm and the sym- bols in Appendix B.2: for = 1 (Vif((=)) + vz).
+ B, w: = of (=()) m. = 1 + Of
m = Vif((b))
7s A
26

---

Published as a conference paper at ICLR 2023
and for = 2((2f((( - Uz).
V2f(zt), -² (2(((()) + +B, w; = (=(),
m. (=()))
The upper bounds of rs come from Assumption 2. Then by Proposition 14, for any t S 9.
i Σ 96 (=
v15(={)
t(g - t) n
(A|\VI((>b))** + B)
Σ
hラ -
v2/(=()
(1q -1)
(A||Vo/(=t))1=+ +B).
n-1
j=1
Putting these to the inequality (15),
=001 s 3(a² + 3²) L L'tggEn[Gk]] + t(q t(q-1) - t)
Ex c
n - 1 B
+ + ||2f{( [ Taking an average of the incquality above over 0 5
+3 (3
10
tlg t) A n -
GR
1
9-1
Ex
=0:l
9 1=0
39(q
1)
(a² + + + (a² + 39) 9² -
2
2(n - 1)
+ |
(q (99-1)(2))
1)(2q - 1)
+
2(n 1) A)
(16)
2
where we used the facts
Σ t= = 2 1) - 12 = (g- 1) and
13 f(g-t) -1-1 n- :la-13 1y-
Since assumed a² + 32 < 3419 1)L2, we have 1 522(1 3a(a-1)12 (a² - B8)) Using this,
G 2 1- 39(9 - 1)L² 11-39(1
(a² + (2) EnGr
2
(1))
(g - 1)(29- - 1) + (n - 1) A (a2 [22|\ + 8² (2((tt)) 1²) 9² 2-1 (a² + B2)
q² - 1
n -
< 2 (2 + q(q 1 n n
1) A) (o² V2 /| + 32 | + 29(4 - 1)
n- (a² + BB²)
where the last inequality used (q () - 1) S 24 and + 1 S 2q for q 2 1.
C.3 RECURRENCE INEQUALITIES FOR GENERAL SMOOTH NONCONVEX- PL OBJECTIVE
Subsequently, we obtain recurrence inequalities about (expected) potential function Egg (Vx for nonconvex-PE problem. Since primal-PL. PP-PPL problem is subclass of nonconvex-Pl PL problem, the recurrence relations can serve as stepping-stones of our convergence rates.
We introduce some assumptions some terms from our bound. On top of that, combining the PE condition (Assumption 4) with Lemmas 16, 17, and 18, we eventually obtain much more concise bound on the expected per- epoch change of VA. This simple recurrence inequality becomes the key to proving our convergence bounds.
small step sizes which enable us to get rid of few trouble-
27

---

Published as a conference paper at ICLR 2023
Lemma 19. Suppose that Assumptions 1, 2, 3. and 4 hold. Assume that the step sizes and 3 satisfy A
1
a $ (1A-1)((g) + 1) + 139L
3 qi' a² + 3 - 34(4 1)12
(17)
and the condition
93= 21 92 d1
d0 - 1a ((2) + ((2+
1)a++++++)) 3) 20
as well. Then, the iterates of sin.-eDDrR satisfy
- - Ci | C2 1C -(+t)) + C3
where
A 1 qa -2L'9 (x+ g(9 1(9-1)), 1)
C
A
((2) + 1oax+1J+++ 3)a²
2
n
949 - A) ((2) + 1)a + 3)a²
C2 u2Co 2((A + 2) - 4L3ke9 k2g
q2
n1
42q q q (0-1) 1)
U298 2( + 2)22aa - -2L 229
A) ((2) 1)a 1)a+1))))) 3) (2k3a² + +²²)
n
1,2 1)) n2 n ((2) 1)a (22+1)aa+
C3
1)++ 3) (a² + B²)
Proof. The first two inequalities of (17) eliminate the last two terms on the right-hand side of the inequality in Lemma 16. addition, applying Lemma 17 to Lemma 16 as well, we have
V3(= V. Va())s
1 2 qa
12 (A 1) ( {=
qUe
|if(=t)
43
(2) + 1)xx + 3 T. (18)
If we take the conditional expectation E, and apply Lemma 18 (which requires the third inequality of (17) to hold) to (18)
E& Vv (=6+11) (=()
A ++11
qa: ( + (A l) /
vif(=b)]1
2
(2² + 414 1) A a) ((2) 1)a + a)a²
+
qa + 2L'g
||
2
n 1
g(q - 1)
93 2L'9
q
n 1 A) ((2) + 1)a + 3²
|22f(z
Co
L' 1) n-1
((2) + 11a++)a++ 3) (a (a BBB
(19)
: It is now left to bound terms in (19) using the tools developed so far. First, recall that ((x)) m f(r; Since fxx;; y) is Pt- in y, we have
- vef(<t))l < - (2z2((()))) - f(())).
(20)
Given any x, (T Vıf(<z y (x)) for any y (x) E arg max [x; by Proposition 9. Besides. - fx -) satisfies QG condition with constant #2 by Proposition Thus, by choosing
(arft) to be the projection of y onto arg max f'a
| vif(=b)) < L2 (x+) 1tll < 2Liz (0(x)) f(z)))
(21)
28

---

Published as a conference paper at ICLR 2023
Here, the first inequality applies L-Lipschitz continuity of V Fif(2 On top that, applying the Young's inequality to the term V1f
) implied by Assumption 1.
V |[]((=))||
= 2 v
+ ( v=f(2))]
< 2 2 + 4Lx2 (((()) - [(=))]
(22)
By applying inequalities (20), (21), and (22) the bound (19), we conclude the proof.
In Lemma 19, saw that if step sizes chosen to satisfy certain conditions, then simplify the per-epoch progress a great deal. now left to choose appropriate step sizes and parameters (e.g., A) so make sure not only that and 3 meet the small step size conditions (17) but also that the constants Co. C1, C2, and C3 are positive.
Lemma 20. Suppose that Assumptions 1, 2, 3 and 4 hold. Let X 4 and assume that
1
0<BS
where 2 14m2.
61 de 29--1) R-
Then these satisfy all the inequalities (17) and the terms defined in Lemma 19 satisfy
Ci > qo, Consequently, due to the recurrence inequality Lemma 19, mini-batch simSGDA-RO satisfies, for some numerical constant > O.
Co > O,
C2 > Lszqur/2, C3 2 0.
Ex Ex[V (V2 (2()
g2 1) n
$ -qa [ 1 (Ix2qa/2) (0(x)) - s(z()] + (or)²
Ba
(*)
Please note that we mark the recurrence inequality above with a special symbol (*) because this inequality is the exact point where the proofs of Theorems 4 and 5 start to deviate.
Proof. Regardless of 2 O, we have
B 6Lq and a: S 6Lgr S
(23)
84LK24
This is enough to guarantee that the inequalities (17) hold with A = 4. Since Co > C2/pg. it is
enough to show C2 prove that Co O. Applying 4, X2 2 and 3/a 2 14kg,
C
3
④/g 1),
21
+
A
(9 + +) a²
go
2
n
3
2
9
rr
2.23
2
> 1,
2
62
22
62 142
C2
12k3
11-1) 1)
9
2k²
2L
9²
A
+1
+ B²
3
n
1
72
12
2
+1)
2
+1)
>
2
2
23
198
1
14
62
14k2
14
14
6
14a
2 14'
Thus, C1 > qa and
C2
Txzqa
2 14
2
14
Then we conclude the proof by bounding the term C3.
We already check from the definition
that C3 2 O. We can upper-bound C's by
L3 ( n1 1
(1+ 2) s L2 ( (2 1)
C3 =
3a
n -
for numerical constant 0.
29

---

Published as a conference paper at ICLR 2023
C.4 CONVERGENCE RATES FOR SMOOTH NONCONVEX- PL PROBLEM
In this subsection, we show the convergence bound of general smooth nonconvex-PE. problems in terms of [i] ||] From the inequality (+) in Lemma 20, we can simply ignore the second term
-Lxxzqa/2) (0 - f(=0) S 0
of the right-hand side because ((x)) 2 f(x; y) for any (x; y). other words, we may deal with the inequality
(0 (
E& [=(+(=))))] Va(=t) -qa - (cr)
n Ba
(nc-PE.)
Plugging & n n/b, eventually show the convergence rate (Theorem 4). (Recall that b is the size of mini bati-bacches)
Theorem 21 (Equivalent Theorem 4, for simSGDA-RR), Suppose that satisfies Assumptions 1, 2, 3, and 4 are satisfied. Let X = 4. Choose the step sizes a and by B/r for some 2 14k3 and
(x(= (-
B min
69 q2
A n-
BK
for some numerical constant >> O. Then, mini-batch simSGDA-RR RR satisfies
E [|][(=))])]
(L K
1-1
A
LB
(a())
9 1
2cr
qK2
q
Proof. To replace the conditional expectations with unconditional expectations, we take expectation both sides of the inequality (nc-PF.):
(2 (f(1-11)
E (= 1 vx(2)) < -qaB [|] (2r)
n n-1
Ba
Rearranging the terms and taking sum from 1 to k K, we have
( Ba K.
gcc
E
[[Ve())))))
[1( + (er) (+/)
n-1
Dividing both sides by qka, we get the following. Note that V, is non-negative.
K
va(=g) ạka + (er)3
[g 10-1)
K E
<
Ba²
Since our choice of step sizes implies
(2(2))
= min
Gr Gr q2 اا n-
or
(2
eventually prove the theorem by using the inequality max (a,b) a + b (for a, b 0).
C.5 CONVERGENCE RATES FOR SMOOTH PRIMAL-PEL-PE. PROBLEM
In this subsection, we prove the convergence bound of primal-PE-PP (or, PL(()-PL) problems in terms of E (= [=).
Unlike the previous subsection, we additionally utilize Assumption 5 stating that f(x; y) satisfies primal PL condition, namely. the primal function ((x)= maxy' fx: y²) is PP- function. With this assumption, we yield another recurrence inequality from the inequality (x). We note that it uses the -Pt condition for t (: Proposition 10) but not necessarily for ((;y).
30

---

Published as a conference paper at ICLR 2023
Lemma 22. Suppose that f satisfies Assumptions 1, 2, 3, 4, and S. Then, with the same choice of and the same condition of the step sizes a and as in Lemma 20, the mini- batch simSGDA-RR satisfies that, for some numerical constant >> 0,
P (2(9-1) n1 11-1
(=+++) + S (1 (19a/2)V{( (2r) (=0
Ba².
(PL())-PL)
Proof. Since the primal function a -1 function,
- ~|[V I -2 [ - $+1
Also, since μu S and K2 1, we know that L -Pi Applying these the inequality (*),
we have
Es [Va(t)+)) (=5))
(pl4 (p(4--) 1)
S (2(2u1g0/)) [ - -5- - (Miqa//2) [ f(z))] + (cr)3
Bo
n
= -(11qa/2) (=(8) + (2 (9 (((a-1)) 1) n - Ba
since A = 4. By re-arranging the terms, we conclude the proof.
Of course, the multiplier 1 - piqo:/2 has a value between 0 and 1. To see why, note that from Equation (23),
< p1qa/2 S P19 2 2-84L 168K L.
Theorem 23 (Equivalent Theorem 5, for simSGDA-RR), Assume that f satisfies Assumptions I, 2, 3, 4, and 5. Let X 4. Choose the step sizes by a = 3/Tr for some 2 14k3 and
2r
Val=h)uagK²
B = min
max
1, log
6L 92
29-1) A
KigK
8(cr)3n² x=1
for some numerical constant O. Then, mini-batch simSGDA-RR satisfies
E (2
13(21)) exp
kft B +
9-1
Higk?
n n-1
12kLr
n-1
Proof. To replace the conditional expectations with unconditional expectations, we take expectation both sides of the inequality (PL.:
(P(9-11) 1) Ba
E (+ [+) (1 uı9a 12 [v(2)] + L2
1
Unrolling the recurrence inequality (Proposition 15) and using the facts 3 = 14riza, we have
2 2. 1,
(2(1- 1))
{[ $ (1 V +
Bo
Piqa
11 n-1
[glg - 1) n 1
$ ccp(<Hu.ga/22)4 + 2(cr))mmi)
Ba².
(24)
Note that, in the inequality above, the second term of the right hand side becomes zero when q 1. In that case, we can prove exponential decay of EVV (=))). Thus, we simply assume 4j > hereafter.
Case 1: If K is large
Ri 3/2
SeBe
9-1). (e exp(1))
K
VPi
va(zb)g
31

---

Published as a conference paper at ICLR 2023
have step size as a = min
(2(2)) 8(cr) - B
log
where
6Lm / q²
2ل-و1ع n-1
A Miqi
Due to the lower bound of epoch size K, the fraction inside the log factor indeed greater than 1, which guarantees the step size is positive. Putting this the inequality (24) and using the fact that max(a, b} I a + b (for a, b 2 0), we eventually have
[=(x
K
2 8(G))
S (x(2 exp
+
[1 + log (+)
12
1
9-1
119K2
11
n-1
K
KRT B
9-1
(=))) exp
+
Migk2
12
1
カー
Case 2: Otherwise, the log factor might have a negative value when is too small. However, in this case, we have
(=(2) S 8(cr)
q 9-1
2 piqK
a=
min
MigK2
n
84Tm2 / 92 ملي A
Putting these to the inequality (24), we have
8(cr) E [[<[=*)] &
q
(oo(-1ggK//) (vigKa/2)²
Migk2
11 1
8(cr)
9 19-1
( k B
(mirr)
9-1
o
MiqK2
n 1
Migk2
n n 1
The inequality in the last line is due the fact that e- + 12 H1gKa/22 E 1). Combining both Case and Case 2, conclude the proof of the theorem.
for each I (0, 1). and that
D PROOFS FOR (MINI-BATCH) ALTERNATING SGDA-RR: FOCUSING ON CHANGES IN THE PROOF
In this appendix, prove the same convergence rates for altSGDA-RR the simultaneous update counterpart. Since most of the steps in the proof are similar to those in Appendix C, we only describe which steps change the proof.
D.1 EPOCH-WISE WISE REPRESENTATION, AND BOUNDING NOISE TERMS
To analyze altSGDA-RR, we modify the notation for epoch-wise updates. The only change that an update si vit1 uses a4+1 instead of af. Hence, the definition of h² should be modified. Recall that
(+))) = Σ vi)((=), hT(=) Σ Vef((=),
KEB
where Bf is mini-batch of size b formed iteration / of epoch k. Then, at epoch k, by re-definition of hk
gt = Σ
g
(
(xt
w)1), h² : 1 Σ
h (a
4 t=1
t=1
k+1
vot = y 93h
(alSSGDA-RR)
32

---

Published as a conference paper at ICLR 2023
We still approximate this epoch wise update rule to full-batch simultaneous GDA update (ssimnDDA) with step sizes qa and q3. Again, we control the "noise" terms l|9* - (= and ||h* V2f (b)]= not to be large. Because of the modification of h², we have different result for || (2](=+))| as follows.
Lemma 24. For mini-butch alISGDA- recall that
1 9
GK
=6
9
If we have Assumption 1, then we have
|| - V2f(=>)]| < I. + L2 ||gh1]
whereas l|g* - -iS(E s G. (25)
Proof. Because of L-Lipschitz continuity of h (:3.).
h² - V2[(2b)1 =
[ (a:); : n (ari vt)]
? t=1
nn (azt; 2 - n (at) 36 10)
<
L
+ 2
x
=bll
x
xtll" = L' + L' |g*1|?.
The last ineqaulity holds because 2 20 1++
D.2 BOUNDING NOISE TERMS: BIT DIFFERENT PROOF OF LEMMA 18
We notice that the same result as Lemma 18 holds not only for simultancous updates but also al- ternating updates, even though it is not very straightforward. We need to reflect the changes from the previous subsection. That is, we have to be careful when we expand the term | - lt (0 S k q 1). Unlike the inequality (12) (in the original proof), we have
| v/'l = 322
(a wうー1)
12
| Σ hnt (cnt) (
< <3328
+
Σ nラ hッ(t)t - v2f(2tt
+ [2f(2t)11
S $3
1
1
Σ
1 ス hラ (=b)) - ver(2t)
+ +
L
+ Σ || -
t
1 Σ
< 2
||00 (lni-arjj
uلاه" ||
+
-
- v2r(Et)
+ (+)(i
j=1
/ nラ ((())) - -(+()))2((+))))
<38 Σ ||
-| + 38222
+ +|[V2/(=t)11?
j=1
2
$ 13 gGk +3322
- nッ())))
+ [e5(2t))1
33

---

Published as a conference paper at ICLR 2023
The second and third inequality holds by Jensen's inequality, and the last inequality holds because t S 9 - 1. The resulting upper bound is identical to the inequality (13). Proving this inequality above suffices to show that the conclusion of Lemma 18 also holds for altSGDA-RR, because
eventually take an average along 0 < t v q - and the other steps in the proof do not utilize the "order" (either simultaneous alternating) of updates.
D.3 RECURRENCE INEQUALITIES FOR GENERAL SMOOTH NONCONVEX- OBJECTIVE
In the proof for SimSGDA-RR, we applied Lemma 16, Lemma 18, and the stmall-step-size" as- sumptions (three inequalities in (17)) to deduce Lemma 19. However, due to Lemma 24 that we obtained for altSGDA-RR, we need slightly different assumptions on step sizes rather than (17).
Fortunately, we notice that the Lemma 16 also holds for altSGDA- RR, with modified version of h*, This because the proof of the lemma does not utilize step-wise updates, while the discrepancy between simultaneous and alternating updates only appears in the step-wise updates. Thus, we have the same result as Lemma 19.
Lemma 25. Suppose that Assumptions 1, 2, 3, and 4 hold. Modify the inequalities (17) (from Lemma 19) by
- [(A ()(k2 + + 13 Lqo L'qaB 20, B qT.'
a² a3+
(26)
3q(q 1)T.²
(In fact, only the first one is different.) Then, the result of Lemma 19 still holds for mini-batch aRRRGDA-RR.
Proof. We first apply Lemma 24 to the general bound resulted from Lemma 16:
(= (1 - (=()
A + 1
qe> [
(A 1)qa [[ - vI5(=))1
2
+
qa
Vif >
[2f(2
(2) + 1)a + 8 9I.²Gx
2
[A {(> + (k +) + 13 Lga L2 qa
qa
|gg111"
(27)
Hence, the first two inequalities (26) eliminate the last two terms on the right side of the inequal- ity (27) above:
A 1+1) qa
-
v2()))s-
(x 2 + (A 1)qa [ V (
gar
||
9
(2) 1)a + 3 qT. gI²
2
This is identical to the inequality (18) in the proof of Lemma 19. From this point on, the rest of the proof is exactly identical to Lemma 19,
Lemma 25 establishes that alSSGDA-RR also satisfies a concise bound on the expected per-epoch change of VA, albeit under slightly different set of assumptions (26) step sizes. Using this result, we can prove the convergence rates for altSGDA-RE -RR that are exactly the same as simSGDA-RO
D.4 SMALL STEP SIZE ASSUMPTIONS
is left to show an altSGDA-RR counterpart for Lemma 20 which establishes the general recurrence inequality (+). In fact, the same choice of step sizes as simSGDA-RU namely
3 and
0 < 3
where r > 14
61
92 + ala A
r
34

---

Published as a conference paper at ICLR 2023
actually meets the newly introduced conditions (26). Among the three inequalities, the only that needs to be checked is
A [(A () + 1) + }} Lqo g2 > 0.
Note that, regardless of A 2 0,
1
B 6L4
and 5 6lar 84LN39
In this case,
A - ( 1) + +)+11 Lqa g.8
[1KK + :/)
2 -41k11xp + Lga 2 4
0.
84m3
Therefore, there no need modify our choices of X and the step sizes a, for the analysis of altSGDA-RR, and the rest of the proof for simSGDA-RR goes through.
E PROOFS FOR LOWER BOUND OF DETERMINISTIC FULL-BATCH SIMGDA
In this appendix, we illustrate a comprehensive lower bound for full-batch GDA, which specific the choice of step size ratio (Theorem 3). Before we start the proof, we define class of smooth dtrongl-coovec--stonee
concave functions.
Definition 4. Let F(I,, .22)2) be the class of functions [(x;; y) with two arguments x and y of any dimension, which is L-smooth, wu-strongly-conve in and u2-strooggy-concavv in y. Let K1 = L/p1 2. 1 and K2 = Lipe 2 1 be condition numbers of the function class. Denote the (unique) saddle (or, global minimax) point by z² (x";
We restate and prove the Theorem 3 for reader's convenience.
Theorem (Restatement of Theorem 3). Suppose K1 2 c and R2 2 c cfr some constant 1. Then, for each step size ratio > O, there exists a function f E F(L, pı, p2) for which simGDA with any step sizes a and 3 of ratio
B/a requires
Ω (Kir log(1e) Ω 12 (1
if k2/C, cf S k2/C,
K
((((2/T) log (1/E)),
if0 < r c/K1
iterations to achieve either 1| 201 < a (
Proof. The proof is done in case by case, constructing worst-case function for each of 4 different regimes of step size ratio r: (I) p1/p2 S k2/c, (2) c/mi SrS p1/p2, (3) 2 k2/c, and (4)
O < r I c/R1. Readers might notice the similarities of the proofs for (1)+)(2 and (4).
Case 1. (1I/22 Sr S k2/c). Consider
(e, r;y) = 141 22 +
T12 x²
1/2 y² + txy,
2
where -= - -1 Luair > 0. Applying Proposition 28, it can be shown that (1)
([T,,11,,55) Also, z" = (0, 0, 0) is its unique saddle point. Note that, the GDA on f()) can be written as
8pm U++1 1
T++1
1-3
-BE/T 8112
4t Vt
A
r
yt++
3e
1
y/.
Also, the eigenvalues of A
B112 v(1 (1 32222² ((1 +
BE
1 1Bp2 +
V-T.
Vr
35

---

Published as a conference paper at ICLR 2023
The spectral radius (i.e., maximum absolute eigenvalue) is
((A) - (11- 8p2)2 //.2/r.
Since the eigenvalues are complex conjugates of each other (the magnitudes are the same), both cigenvalues have magnitude A)) Then, by Proposition 27, (AA) < 1 is necessary for convergence. To this end, we need B > satisfying B < 222r/ (r/2 e2).
zez 2x.gk) - (0,0;0)1 < E², we need a large enough & to have of 2 O Such To guarantee (1vk a is required be at least S2
log(1/e))
Now note that, since ln 1/2 S r S K2/ and No 2 e,
Bps
r
L - Luzir
L 1
11
L
1 -
(1-
3
2P2T
2
2pur
K2
2
The last inequality is true by minimizing (1-1x |---| for r E [41/ p2, /2/cl. I 2 it has smaller
x2
value when is larger: by taking k2/c, /c, we have 1 s3/c=1 2 1- _ Otherwise (r < 1), which is possible only when μl U2, the term has smaller value when is smaller: by taking r p1 U2, we have 1 #1/wa-1
K2
1- - 1. Thus, we eventually need Ω
1,2 log(1/8) (1/e) |1/22
Ma
iterations.
Case 2. (c/K1 S S p1/p2). Consider
(I;
p1 x²² 2
M1 2² + Exy 2r
12 w²
where 12 -2-1pt/r - Lpi|1 - 1/rl 2 0. Applying Proposition 28, it can be shown that
f(2) E F(L, M1, p22,, and x" = 00 0, 0) is its unique saddle point. Note that, the GDA on f(2) can be written
Tz+1
3u1/r -3e/r 38
xt
= B
Xt yt
Wi+1 = (1- Bp2) wi.
1r+1
1- Bu//r
1/+
Also, the eigenvalues of B is
== 1 - Bun/r + v v(1
3p1 38
VF V-T.
The spectral radius is
(BB) (1-8///r)2+ B2
Since the eigenvalues are complex conjugates of each other (the magnitudes are the same), both cigenvalues have magnitude p(B). Then, by Proposition 27, p)B) < is necessary for conver-
gence. To this end, need 3 > satisfying 3 < (nā/ 19).
To guarantee [[(Ta; yk, ux) - (0; 0)1 S E2, we need large enough to have w S ( Such l is required be at least Ω Buz log(L/E)) Now note that, since c/R1 S r S 11/1e and
R1 2c C,
1
+
La L²-
LHi l/rl
L2
(1-11-1/1
L 2p11
1
1
2
c
8
2/11
2/11
2/11
The last inequality is true by minimizing (1-
|1-1/|] for [C/K1, /1/ p1/p2) //2). If 1 1/r, which
Xi
is possible only when > #2, it has smaller value when is larger: by taking r = p1/22, we have mi 1 1-- Otherwise (1 1/r), the term has smaller value 1 -. Thus, we eventually need when r is smaller: by taking c/NI, we have 1 1-xI/e 61
1- 1-#2/m1 1 "1 61
1
Ω
1.²
log(1/s)) iterations.
36

---

Published as a conference paper at ICLR 2023
Case 3. (r 2 k2/c). Consider (z:
x²
52 Clearly, f() E F(L, M1, c
F(L, H22) and x= (0, 0) is its unique saddle point. The GDA on f(8) can be written as
1k+1 (1 ) TR, MR+1 - (B) yk-
8p1
To guarantee (axx: yk.) (0, 0), S E2, we need large enough & to have zf S O( Such k is required be least Ω Byg log(1/e)). Also, need / 2/ L guarantee y/s - 0 (i.e.
otherwise, diverges). Combining these facts, we eventually need f Na
log(1/E) iterations.
Case 4. (0 < r S c/K1). Consider (x; y) = x² Ha y. Clearly, f(4) E F(L, (22 c
FiL, H22 and x= = 0) is its unique saddle point. The GDA on f(4) can be written as
(1
3L
2k+1
Tks
Wk+1 = (1 - 3p2) yk-
To guarantee [[ yk)) - 0)12 I E², we need large enough k to have u S O Such a k
is required to be at least Ω 1ppz log(1/e)) Also, we need 3 < 2r/ L to guarantee Ti + 0 (iee.
otherwise, it diverges). Combining these facts, we eventually need f2 (+/2 log(1/E)) iterations.
Lastly, we note that the lower iteration complexity bound in terms of the potential function VA equivalent to the complexity in terms of squared distance norm from the (unique) saddle point z". up to constant factors. This proved in Lemma that we defer its proof.
Here the postponed/omitted proofs from the proof above.
Proposition 27. For a square matrix A Rmxx and a sequence of m-ddmmensooaal vectors (vk), the matrix iteration Vk+1 Au converges Us - 0 if and only if the spectral radius fi.e., maximum absolute eigenvalue) of pl of A is less than I. Furthermore, its convergence speed is characterized by (((((A) + e)*) for any (arbitrarily small) e >
Proof. See Horn & Johnson (2012, Theorem 5.6.10-12).
Proposition 28. Let μl, U/2 and L be positive numbers such that L 2 max[H1, H2)- Consider quadratic function f on IR x R defined by
try, Then, f F(, M1, (1,H2), and its unique saddle point is z = (0, 0).
f(x; v)
[1 2 12 + Cry, where l < L2 11f122 - L L u2l.
2
For example, if #1 p2, C (4] + m22) is enough to guarantee L-smoothness.
Proof. The wwtaveeeesttong-ccccaiityg is trivially true. Note that the gradient and hessian of f
Vf(zy)) H(x v)T, =
i
122
Since H is non-singular matrix, has unique stationary point at origin (z 0, y 0). By Proposition 11, it also a unique saddle global minimax point.
For any two distinct points 21 (#1:01) and 22 (I2: V2) in R RR
V (= V (=2)) H [ (2)= ||] ا2|l
S H 112
| - 22ll
where |||]| spectral norm (i.e., maximum singular value) of H. We would like show that
H lg2 < L. To this end, it is enough to verify the following two inequalities:
det(T?2 - HHT) I.A ( 22 + (1192 + + 0.
trace HH H/T)/2 )/2 1/2 (uf 1 I?
37

---

Published as a conference paper at ICLR 2023
This is because the characteristic polynomial of HH det(wI - HHH) is a quadratic poly-
nomial of w. and its maximum root should not be greater than L2. Let l L M1P2 + a for some E R. Plugging this le into both inequalities above, we get
a² - - 12) 2 and a - n2)2122
respectively. One can check that -Ilu1 p2l is the largest possible satisfying both inequali- ties above. This proves the proposition.
Subsequently, we show that if our convergence rate is exponential, then the iteration complexity in
terms of || - 1² ==1 Pf.(D)-P.. problem, up to constant factors. This also applies to the function class F(L., ,1,12) since
is equivalent to that in terms of (=) (( $* + ($(x) [[))] for
it is a subclass of smooth ( functions (:: Propositions 7 and 10).
Lemma 29. Suppose fa: y) is an L-smooth function satisfying y-side Pz-Pt condition and primal n pt-PE condition (i.e., PL())-PL) Suppose xt : is a global minimax point of f. Then, satisfies
gm1n 2(Ap1 + 21?)
||> - =- (A+1)L3 P2
1| 1---2 211
We remark that the second inequality also holds for general smooth nonconvex-PE. problems.
Proof. Let K1 L/M and X2 = L/p2 be condition numbers. By the conditions of (smoothness and PL conditions), for any æ and y.
f1 x x:" 1|
Prop, 10
(xx) - -
Prop.
L(K2 + 1)
1 x x01
2
2
P2 y y (1= I (xx) - f(x; S 2
L
2 1 y" (x:)11
where y=x)) is projection of y to arg max, f(:;; yz). In particular, y (x=" = yy. Since y (ar) is a function of æ and can differ from y", we need to bound the term 1/ - y² (x)) using || - x ||? and y 11 To upper-bound the term |/ (x))) note that,
yy - y² (2))) < (lyy - y² ||| + 1 (z) - y (x*)))))²
< (1ly y"'l + K2 | x²1
< (1 + x3) (I w²1l +
+|æ || x= 11²)
The first inequality holds by triangle inequality, the second inequality holds by Proposition and the last inequality holds by Cauchy-Schwarz inequality. 12 To lower-bound in a similar way, note that for any constant O,
1 - 1²12 < (1ly) (x)) +
11 (x) - 3" )1)
122 3/2 vā | x²11 2
y y (a))
1 + 2
[18
y" (=)) 2 a x x²1)2)
:: ::1ly y (x))
y 12 a | x²1
+ x 2
(2x + by) 5 (a² + (0² )² for real numbers a, b, V-
38

---

Published as a conference paper at ICLR 2023
Now can prove the inequalities in the lemma. We first show the second one. Applying K2 multiple times.
(a y) ((((2))
D"] (+(x)) f())
XT(ri2 + 11
||
x²11²+ + y yy (x)))
2
AL(122
+
T(1 + 13))
||00 x²1 $12++
T(1 + kZ))
11 y 1
2
2
2
(A + 1)
$ (A + 1) L
1 x
+ 11 - -011)
|| - == ==1
To show the first inequality of the lemma, let
Ar1 2μ²2
Ap1
vx 2
x:
"12
1 y (x))
2
Aff
P2a
||00 x x²1 + 2(1 + K2/aa
P2
11 1
2
2
A/11
Ap1
|
x 2²11
|1 3"11
4(a + R3))
Apl
(1:00 x 1|2 + 111 -
(111-"113) -r1)²)
2(A 2T22 1z 2=
4(a k3)
This concludes the proof.
The equivalence of iteration complexities for achieving || 121 S E² or V*(x) I E² is quite straightforward from this lemma, as long as the convergence speed is exponential. For ex- ample, suppose we have a upper convergence bound | - 11 <
exxp(- K/r) for some con- stants a, >> 0. This implies upper iteration complexity bound K = O(rlog(1/e) sufficient E². Then by Lemma 29, we also have (xx=))2 < a' c'exp(-K/r) where a' = a( + 1)L$ /uz is also constant. This implies lower iteration complexity bound K = Or log(1/e)) as well, sufficient to achieve (=()))² S s². The other way of complexity translation operates with similar logic.
achieve || 2² 11
F REMARK ON SMOOTHNESS ASSUMPTIONS AND LOWER BOUND OF WITH-REPLACEMENT SGD(A)
During the discussion phase of the conference, a reviewer raised a question about whether or not the component smoothness (Assumption 1) is more crucial than the mrthout-replacement component sampling for faster convergence. However, we would like to claim that the component smoothness alone is not sufficient for improving the convergence rate for with-replacement SGD(A). To this end, we provide some formal results on lower convergence bounds. For simplicity, we use mini-batches of size throughout this appendix.
Firstly, the theorem below provides a lower bound on with-replacement SGD for minimization prob- lems. Readers can also verify that an analogous lower bound holds for SGD with unbiased and in- dependently sampled gradient oracle for more general stochastic minimization problems. The proof will appear later this appendix.
Theorem 30. For any step size 1) > 0, there exists a real-valued strongly-convex function f(x) defined on R with == ming f(x), satisfying:
1. I consists n > 1 smooth component functions fs: f(xx) = EE fe(ar), where each component f. is smooth;
2. After ranning T> 1 iterations of with replaceept SGD (with mini-batch size 1) starting from 2o E Ra the last iterate 2T satisfies (f] 2 ((1/T), where the expectation is taken with respect to the randomness i.i.d. index choice each tteration.
39

---

Published as a conference paper at ICLR 2023
Next, we show this theorem naturally induces convergence lower bound for the minimax counter- part: with-replacement SGDA. Consider a (finite-sum) minimax problem ming max, g(, y) := f(x) - -(y), where f = 1 Si= fi is a worst-case function in the proof of Theorem 30. Here, the minimax problem
g be solved by minimizing f. Moreover, since the primal function ((x) := max, g( y) associated with is in fact the same as f(x) - f", the po-
tential function (1 y) X (x) (ming (xx))] + [T(x) g(z, y)] becomes the same as ([(()) f*) + (f()) - )*) for constant À > O. Combining these facts, we can immediately obtain the following lower convergence bound of with-replaaemmet SGDA.
function g y) == - Ei=19((a, y) consisting of smooth component functions where the last iterate (æTT, yr) of with-replacement SGDA satisfies BB[ (a)r 2 (11/T))
Corollary 1. There exists prrongly-comve--oo waaror-tttooooooncieeeee
n.
Corollary 1 formally proves that with-replacement SGDA strongly-oonee--ttrrngyyyyyo minimax problems with smooth components has a worst-case convergence rate ((1/T). This in fact matches the (1/TT) upper bound obtained for primal-PE-PP PL-PPL problems by Yang et al. (2020). Considering that
functions form a strict subset of primal-Pt.-PE. functions, Corollary 1 establishes that adding component smoothness assumption does not provide further speed up for with-replacement SGDA.
soonvex-ttrongly-coee
In contrast, our theoretical result in Theorem 2 shows that SGDA-RR has much faster convergence rate B[[]] Ó k== for primal-Pt.-Pt. minimax problems, where K is the number of epochs. One can check that our O 1 bound faster than the tight convergence rate ((1/T) of with- nK=
replacement SGDA by simply plugging in T = nk. In light of Corollary we proved, we can now claim that the improvement can be solely attributed to RR.
Although we do not provide lower bound for more general nonconvex-PE. problems here, believe the more challenging case of nonconvex-PL. lower bound is a topic for another separate paper. Nonetheless, we conjecture that the speed up by SGDA-RR in nonconvex-PL. settings is also due to the effect of RR, not component smoothness.
From now on, we provide the postponed proof of Theorem 30.
Proof of Theorem 30. We construct worst-case functions with quadratic functions on R. which clearly L-smooth for fixed constant > O. Then, it is easy to extend the logic to the functions with domains of higher dimensions. Let zo E IR be the initial iterate.
Case 1 ( S n S (2 )) Note that the condition on the step size, LT S S ( ET )
equivalent to an inequality (1 12) < (1-1/7)²
We first assume an even number. We will encounter the case with an odd n a bit later. Consider f(x) = _2²² consisting of even number of components fi ft's defined by
( 12 + vx, fx(x) = 40 vx,
(i < ) (i 2 2 1),
for some number v E R.. At each iteration 2 1, we choose component index i(t) lid [ni)( (with-replacement sampling). Then we can write the chosen component function iteration é as fc(t) = 4 - 5,10 for some i.i.d. random variable 8, ~ Unif()+ Accordingly, an SGD step can be written as
3e = xt-1 1/ (1 = (1 - 11),..11 + 18...
By applying telescopic sum, we have
FT = - - xo + np
(T) 8t-
1=1
Taking squares and expectations (with respect to the random variables 81, 81,...,88 ST) to both sides, we have
T
E| (1 (1-
2
(1
(1-n (
40

---

Published as a conference paper at ICLR 2023
by applying the fact that st iss are zero-mean independent random variables with absolute values 1:
0, t t' (: independent);
Elss st]]
1 = (: ( = 1).
We calculate the sum above as follows: since (1 - n21² S 1/7) and (1 - 1/T)" S se_1,
Σ (L (1-mL) (1- 1 - (1 - 11.
1 (1 - )) 1 1 (1 nyL, 21
7/. 24L
With this inequality, and since (1 n1) 2T z 2 0, we can lower-bound the expectation B[zğ]:
1 2 1f 72²v2 1 e (1 e 1j
(1
21-
2111.
2L.
21.77
Since f has minimum f* 0 at 0, we eventually have
(1 (1-e-3)u
u² LT
B[f(2T) - f*) Bl+i
4LT
Now we consider the case when the number of components > is odd. Consider (x) = 0 and let the remaining components). Note that the zero-component fn does not affect the trajectory of SGD (i.e., the points visited by SGD) and the optimality f (f = at æ 0), while the whole objective function becomes (a)
components the same as the case above (with an even number of
n-1 1/2 2 Thus, it can be easily shown that the Ω
lower bound also holds. 2
Case 2 < <イ< + or ( )) From the condition on the step size, we have (1-nL)²
(1 - 1/T)2. Consider f(()) = L x² for every E [n]] every components are the same. In this case,
show that the last iterate of SGD is bounded below by a constant with respect to T > 1.
At each iteration
2 1, we obtain Te = (1 - x by a step of SGD. Then, applying T 2 2,
2T
2 (1 (1-11) -nn 2T =
(1
1
1
x
2
16'
Since f(x) =
1 n Σm f((x)) = L has a minimum f" at r = 0, we have
Le
f
2((1 Lا
32
G EXPERIMENTS: QUADRATIC GAMES
In this appendix, we provide a more detailed illustration of our numerical evaluations on quadratic games introduced Section 6. Recall that the objective function and its component functions fa are given in Equation (5) as
1 T
1 Aa x By
f(;; y)
x
TyyCy Cy.
2
1
1 y
(x;
A,a + xx B,y
C,y + u, x v.
We choose the same dimensions for the variables dd and y E Rdv; we set d, d, = d.
G.1 PARAMETER CHOICES
To sample the matrix C C + C, E dd satisfying that ucls - C and ||C.]|2 Lc, we first randomly generate an orthogonal matrix Qc E Rdxd (Le., Q Ia). by taking advantage of
41

---

Published as a conference paper at ICLR 2023
the QR uR-decomposition of a random matrix. Then, generate the eigenvalues of C,'s 's as follows. We sample the entries of n vectors X E 12 (i E [n]] unifornly from the interval juc, Lc]. We add some level of perturbations to some entries of each X.: we replace some entries to the numbers in an interval c. Hcl, keeping the entries of the vector 1
we define C, = Q Qe where AÇ = diag( ( a >i=1 2 in the interval [uc, Lc]. Finally, not positive definite, thereby some components fi become (stroongly-)oonccetco
Because of the perturbation step, some C,'s
in y.
Next, we sample the matrix B''s. There are no requirements for B but | < LB: B,'s are even not necessarily symmetric when dz + dy. Thus, we first generate the orthogonal matrices U.B and V by taking advantage of the singular value decomposition of random matrices. Then, we generate the singular values of B,'s by sampling the entries of n vectors of uniformly from the interval [0, Lc]. After that, we define B, U where Σ diag(of)) We typically want to take larger LB than Lc to strengthen the interaction term By.
Recall that the primal function & associated with f is explicitly written as
i (xx)
max f(x: y) = 2² (A+ "BC x = 20 Mæ. yER"
(28)
Note that the inverse of C' can be efficiently computed as C-1= = =Q
Before generating the matrices A,'s, we first generate Má'S satisfying that 1 - M, = M and the nonzero eigenvalues of positive semidefinite M are in the interval [NM; L.). The process of sampling M,'s 's is almost identical to how to sample C s. One notable difference is, M,'s and M are forced to have r(< d) zero eigenvalues: this makes M a positive semidefinite (but not strictly positive definite) matrix of rank d - r. Moreover, we get the -M(() condition in æ as follows:
Proposition 31. Consider positive semidefinite matrix M E R. If the smallest nonzero eigen- value of M p. then ((x) == f Mæ is p-PL in æ. Also, 4- -min (xx) O.
Proof. Apply the eigendecomposttion of M: M = QAQT. Let M = AT/2TT. Then, we have (xx) = 3 Max]² which implies that (xx) 2 0 (Vx) and in fact t- = 0. Note that 1 ||=]|² is I-strongly convex. Also, the minimum nonzero singular value of M is vp (: M M M). Therefore, by the proof of Proposition 12, (xx) is a μ-PL function of æ. Lastly, we note that ((x) is not strongly convex in general, especially when M is a rank-deficient matrix.
Typically, the spectral norm | [|2 is known to be bounded above by || + L /C in worst-case (Nouiched et al., 2019; Li et al., 2022). However, since we sample M without knowing the exact form of A, 's while want to control the spectral norm ||A, not too large (for smoothness of fi), we (empirically) decide to choose rather smaller Lys: simply. we choose Las = LB-
Now let A, M, BB and A = Σ A, satisfy Equation (28). We emphasize that A may have negative eigenvalues; the objective is nonconvex in æ in general. We have checked this is true across the experimental settings. Also, we let L max || LB, L } for further parameter selection. (In fact, because of our choice of parameter values, L was always equal to LB in our experiments.)
Furthermore, we generate the vectors u,'s and v;'s satisfying E u; = = D;. The entries of these vectors are uniformly sampled from an interval [-A, A]. thereby the average of entries is centered to zero. In addition, to verify our theory, we choose the step-sizes of the form 3 = c1 8/LL and a = cg 8/n3 for some constants co and e₁ and batch size
Lastly, we specify the values of parameters described above: n = 100, d = 25, PM = μe. and Le = < LM = Lp. The constants co and ei are tuned among 1 115,, +1, 20.5, 0f In the following subsections, we investigate the effects of the change of
ii) A {10, 20, 40), determining the discrepancy between components, iii condition number H2 E (5, 10, determined by I.n and Pc, and (iii) batch size E (1, 25, 50, 100).
42

---

Published as a conference paper at ICLR 2023
unddaveR
100
156
30
250
340
160
130
3-8
200
100
130
(a) A 10, SimSGDA(-RR)
(b)
A 20, SimSGDA(-RR)
(c) A 40, SimSGDA(-RR)
100
150
30
Spodh Spodi/dda:2 120
Opech Juna
Esech pead
(d) A 10, alSGDAA-RRR
(e) 20, altSGDA(-RR)
(f) A 40, altSGDA(-RR)
AGEA
ASDA
ADUA
Poavedt comrabeee
3uta:
Jonat
t200h Soiat 2001
(g) A = 10, AGDA(-RR)
(h) A = 20, AGDA(-RR)
i1) A = 40, AGDA(-RR)
Figure 2: Comparisons by changing the value of A {10, 20, 40). Solid lines:
average across 10
different runs. Shaded regions: 95% confidence intervals 1=19 std). The vertical axes are on logarithmic scale.
from the plots of the values potential function Vx(x;;) = (1 (1)))((z) f(x; y) over epochs. 13 (Numbers in bold font above the default values of parameters.)
G.2 COMPARISON: THE EFFECT OF COMPONENT DISCREPANCY
Notice that the discrepancy between component functions gets larger as A grows. Technically, one can check that the gradient variance (that we controlled in Assumption of the vectors u, and v;. Moreover, we have already discussed that the gap between convergence speeds of SGDA and SGDA-RR becomes larger especially when the gradient variance large.
proportional to the norms
Now, we present the results of numerical experiments by varying the values of A to 10, 20, and 40, while fixing LB = 4, |AC. = 0.4, 1, and other experiment parameters. As shown in Figure 2, we observe that the difference between the random-resse maadum--eshufflig algorithm and the uniform-sane safforn-sampling algorithm gets larger as increases.
G.3 COMPARISON: THE EFFECT CONDITION NUMBER
Here, we present the results of experiments by varying the values of Ka to 5, 10, and 20, while fixing A = 20, b = 1, and other experiment parameters. To this end, we applied the parameter settings for Lg and pac (LB, Pc) (2.5, 0.5), (4, 0.4), (5, 0.25), respectively.
13 During and after the discussion phase, we performed some more experiments. As we tried to plot all the results over iterations, the size of the figures in pd format became too large. Consequently, in this appendix, only plot the results epochs reduce the file size of the figures.
43

---

Published as a conference paper at ICLR 2023
Poperaal poevestont
100
156
30
200
340
150
130
3-8
200
35
200
190
(a) 122
5, (-
(b) Kgg
10. SimSGDA(-RR)
(c) 20, SimSGDA(-RR)
6850
100
150
30
100
Epodh Spodi 120
Opech Juna
Spech Jutai: 1000
K2 5, al-RDA(-RR)
(c) K2 10, alSSGDA(-RR)
Ai2 20, al-SGDA(-RR)
AGEA
ASSA
AQUA
Poavedd eoorrabed
3uta:
Jonne
2po.1) 7000
(g) R2 5, AGDA(-RR)
(h) K2 = 10, AGDA(-RR)
(i) R2 = 20, AGDA(-RR)
Figure 3: Comparisons by changing the value of K2 = L/ue (5, 10, 203. Solid lines: average across 10 different runs. Shaded regions: 95% confidence intervals (#11 1.96 std). The vertical axes are on logarithmic scale. Note: we run 1000 epochs for R2 20 (see the rightmost column), whereas we run 300 epochs for the other K2 {5, 10} (see the leftmost & middle columns).
The results are shown in Figure 3. We observe that more epochs are required for convergence when l2 increases, regardless of the type of algorithm. One may think that the performance gap between RR- baa-badnoon-RR-baaeeeee
algorithms is small when N2 is huge. However, when run the algorithm for an extended number of epochs, we observe a significant gap in convergence speeds.
G.4 COMPARISON: THE EFFECT OF BATCH SIZE
The last comparison is about the effect of batch size b {1, 50, 1003. Recall that we linearly scale the step sizes as the batch size changes. However, since the number of epochs is fixed, the number of iterations decreases as gets larger.
As the readers can notice, the convergence behavior of SGDA (resp., SGDA-RR) and AGDA (resp., AGDA-RR) are similar in our construction of quadratic games. Thus, this subsection, we only compare simSGDA and its variants. Rather, we introduce two more methods of component choice other than with-replacement uniform sampling and random reshuffling:
mini miii-Batcchnnll every mini-batch is without-replacemenn & uniformly-randomlly sampled, while any pair of mini-batches in an epoch may have some indices in common; the same as b-minibatch sampling (Loizou et al., 2021).
NS(No Shuffle): accessing 1,..., in its predefined order to construct mini-batches; weihoutt but deterministic. Remark: for minimization problems, SGD with NS is usually referred to incremental gradient (IG) algorithm (Mishchenko al., 2020).
44

---

Published as a conference paper at ICLR 2023
simSGDA simSGDA-RR RR
simSGDA
simSGDA RR
10"1
SimSCDA-WORE simSODA-NS
10-1
BInSGDA-WORB
Poteriial (normalzod)
Poteniaal (noemaland)
simSODA-NS
10-2
10-2
10"
10
10-1
10-1
10-4
50
100
160
200
250
300
50
100
150
2000
250
300
Epoch (total: 300)
Epoch (total: 300)
(a)
(b) b 25
simSGDA
simSGDA
simSGDA RR simSGDA
simSGDA RR
10
10-1
simSGDA
Patentaal (normalizdd)
BimSCDA-NS
Patenfial (narmllizdd)
BimSCDA-NS
201-3
10
10-3
10-1
10-1
10
10
50
100
150
200
300
0
50
150
200
250
300
Epoch (total: 200)
Epoch (total: 300)
(c) b 50
(d) b 100
Figure 4: Comparisons of SimSGDA(RRR, WORB,, -NS) as changing b E {1, 50, 100). Solid lines: average across 10 different runs. Shaded regions: 95% confidence intervals 1#19 std). The vertical axes are on a logarithmic scale.
These two methods are somewhat related to vithout-replacement component sampling, whereas they are both different from RR which uniformly randomly samples permutation of [r]] every epoch. We call simSGDA using mini-batches sampled by WORB and NS as simSGDA- MOOA-WWRBBBB and simSGDA-NSS respectively. Remarks: If b 1, SimSGDA-
becomes the same algorithm as vanilla simSGDA. Also, since we choose n = 100, if = n 100, all three algorithms simSGDA- RR/-WORB/-NS become the same deterministic full-batch (simultaneous) GDA.
The results are shown in Figure 4. One can notice that the potential plots of simSGDA, SimSGDA- RR, and simSGDA-NS Also, if > 1, AMSGGD-WOOL has better performance than vanilla simSGDA. These imply that wethout-replacemmen mini-batches benefit the convergence speed to some extent our quadratic game. However, the result of experiments also implies that both (i) without-replacemmnt per epoch (i.e., shuffling) and (ii) randomization are indeed essential for fast convergence our quadratic game experiments. In particular, WORB requires very large batch size but still has much slower convergence rate than RR (see Figure 4c which is the case using half of the total components at each iteration).
respectively the same even if we change the batch size (b 100).
H OMITTED COMPARISON WITH RELATED WORKS
H.1 COMPARISON WITH XIE ET AL. (2021)
setup and discuss their results in To specialize Xie et al. (2021, Theorem 3) to the terms of our notation, we need to replace their symbols
(T, S, K, 3 G2, G2 T12, I, 11, Too, Lo, n1:71) 76)
45

---

Published as a conference paper at ICLR 2023
with the following symbols from notation
[K, 1, n. 8, ty + 1), (=)
L(n
and also put A = O (their analysis only applies uniformly bounded component variance per ma- chine). Then naively translate the bound of Xie et al. (2021, Theorem 3) to language as
K2LV)(E)) min E [10())) 2 RE(K]
BL K2
1/3
K
To the best of our knowledge, however, we believe there may be a mistake the proof Xie et al. (2021, Appendix C.4). From the inequalities the last page of their paper, notice that the term fo might be missing in step. where y is chosen to be the minimum of several terms including KT
87L,K Thus, as far as we can tell, it seems inevitable that this omitted term would lead to an additional term 3150L, Li in the final bound. By combining this to their bound and re-translating H²T
it, eventually have
L= K
BV 1/3 K2
[100))]] so
min E kE[R]
+ K22
since their 2/2/4² translates to our n... Therefore, their result actually shows the same depen- dency condition number our Theorem Nevertheless, comparing the terms related to the component-wist variance B, ours better. In the second term in the bound above does not shrink even when the number of iterations (per machine & per communication) grows. In our case (The-
1/3) which can TK
orem 1), however, the dominant term (in K) can be briefly written as O diminish with large n, ie., the number of iterations per epoch.
46


Reviews:
[{"review_id": "f_5lArtr26", "reviewer": "Reviewer_9Nrg", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "In this paper, authors studied two-time-scale SGDA (both simultaneous and alternative fashions) with random reshuffling, applied on nonconvex-PL and primal-PL minimax problems. They provided the gradient complexity results of proposed algorithms, which are claimed to outperform over existing literature. Furthermore authors studied the lower bound of SGD with two-time-scale on SC-SC problem, which verifies the tightness of complexity results in the deterministic primal-PL case.", "summary_of_the_review": "1. I am confused on the comparison in Section 4. Your paper only considered the finite-sum case, while you compare with the SGDA result in Lin et al. (2020), and their paper considers the purely stochastic case $\\mathbf{E}_{\\xi}[f(x,y;\\xi)]$. In my opinion, I may compare Theorem 1 with existing finite-sum algorithm complexity and corresponding lower bound results, e.g., SREDA paper (let's restrict to nonconvex-strongly-concave case only, because Lin et al. (2020) only discussed this case). And with that I may found that the $O(\\epsilon^{-3})$ result is not sharp enough compared to SREDA (which is $O(\\sqrt{n}\\epsilon^{-2})$), is any reason on it, do I miss anything here?\n\n- SREDA: *Luo, Luo, et al. \"Stochastic recursive gradient descent ascent for stochastic nonconvex-strongly-concave minimax problems.\" NeurIPS 2020*.\n\n2. Also at the same time, the comparison with Lin et al. (2020) is not that fair in my opinion. You assumed component smoothness (Assumption 1), while Lin et al. (2020) only requires the smoothness of the whole objective function. Also some lower bound works shows that $O(\\epsilon^{-4})$ should be the fundamental limit in the case of Lin et al. (2020). With that, it is less convincing for me that the improvement that authors claimed stem from random reshuffling (or without replacement), I may argue that the improvement (if any) originates from the additional component smoothness assumption.\n\n3. Also when in complexity result summary (e.g., Section 1.1), I found the complexity results always omit the dependence $n$, while Theorem 1 and 2 still have dependence on $n$. But in some other random reshuffling literature (e.g., Mishchenko et al., 2020), their results summary often come with the dependence on $n$, is there any difference between your work and existing literature which comes with the $n$ dependence? \n\n4. I found that there is another work on nonconvex-PL problems, while authors do not discuss it.\n\n- Yang, Junchi, et al. \"Faster single-loop algorithms for minimax optimization without strong concavity.\" AISTATS 2022.\n\n5. A minor question is that, in several existing finite-sum algorithm literature (e.g., SREDA above), they do not need the bounded variance assumption (or its variant), but here you need Assumption 2, should I regard it as a disadvantage of the random reshuffling?\n\nI do not have enough time to check the lengthy proof regarding such short review time frame, but I will try to check it after the review deadline. \n\nAll in all, now I am concerned on evaluating the significance of the results compared to literature, I am skeptical on that the improvements on complexities has nothing to do with RR. I hope to have more insights from authors. Please definitely correct me if I misunderstand anything here. Thank you very much for the efforts.", "strength_and_weaknesses": "Strength:\n1. The writting of the paper is pretty good, the flow is pretty clear, I appreciate it.\n2. The work extends the SGDA with reshuffling into the nonconvex minimax regime.\n\nWeakness:\n1. The comparison with exisitng works (to show the outperformance of proposed algorithms) made me a little confusing (details below).\n2. Some closely related works are missing in the discussion.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "WH1WmXrdZma", "reviewer": "Reviewer_8wv3", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "This paper studies the convergence of stochastic gradient descent ascend (SGDA) for nonconvex-PL minimax problems, where the data points are randomly shuffled and sampled without replacement during the training. The authors provided strong theoretical convergence of SGDA and confirm the empirical observation that random shuffling converges faster than sampling with replacement. They also provided a lower bound for strongly-convex-strongly-convex mini-max optimization problems. \n", "summary_of_the_review": "In general, this paper is a strong work with a good presentation and solid theoretical results. I only have the following minor comments that could potentially improve the current manuscript.\n\nIs $\\nabla f_i(z)$ in Assumption 1 the concatenation of the gradients $\\nabla_1$ and $\\nabla_2$? I did not find a definition for it.\n\nI am not sure why it is called a two-time-scale algorithm since the order of learning rates $\\alpha$ and $\\beta$ are both in the same order with respect to the time parameter $T$. It is just two different updating frequencies that differ in a constant order.\n\nIn Section 4, you mentioned that the results can be easily extended to the mini-batch setting. Can you elaborate more on this? Since the data points in the batch are not i.i.d. (if you first shuffle the data and then read a batch in a sequential way), does this bring benefit in the convergence rat?\n\nIt would be nice to have some empirical comparison between the wise-alternating SGDA-RR in this paper and the AGDA-RR in Das et al. (2022) which is proved to be optimal in the two-sided PL setting. This is also to verify the practical advantage of SGDA-RR claimed in this paper for different epoch sizes $n$.\n", "strength_and_weaknesses": "This paper is clearly written and well organized. The theoretical analysis is solid and the results are strong enough to show the advantage of the studied method over its competitors. A minor weakness is a comparison with recent work on similar topics.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "H4egUFC8GK", "reviewer": "Reviewer_CLz9", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "This paper studies the SGDA algorithm with shuffling and sampling without replacement for non convex-PL minimax optimization problem. The complexity results show significant improvement over exiting analysis that use sampling with replacement.", "summary_of_the_review": "I vote to accept this submission based on its significance and novelty. However, there are indeed some flaws as I mentioned above. ", "strength_and_weaknesses": "Strength:\n\n1. The analysis of sampling without replacement for minimax optimization is indeed rare while it is the practical implementation in many cases. Therefore, this work fills a gap here.\n\n2. The complexity results and lower bound results are all solid contributions. They are state-of-the-art results for the considered problems in a sense that they match their minimization problem counterparts in the literature. \n\nWeakness:\n\n1. It lacks some empirical studies to verify the theory. I would not doubt that the strategy of sampling without replacement can show its effectiveness in many cases, because there are extensive studies of it in minimization problems already. However, some empirical studies are still expected here in order to make the argument whole and convincing.\n\n2. It needs to be justified that what applications can satisfy a nonconvex-PL landscape or a primal-PL-PL landscape. Would those problems be of enough interest to the community? \n\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "1uFcgFq1RX_", "reviewer": "Reviewer_s6TB", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "The paper focuses on SGDA with random reshuffling (SGDA-RR) for solving finite-sum min-max optimization problems. In particular, it studies simultaneous and alternative SGDA-RR for two different classes of problems nonconvex-PL and primal-PL-PL. The proposed analysis extends to the mini-batch regime and as a result, main theorems can capture the deterministic GDA as a special case. A lower bound of the two time-scale GDA is also presented. \n", "summary_of_the_review": "The paper has a solid theoretical contribution and it is very well-written. \n\nI gave a score of 6 rather than 8 for one main reason:\nI believe that the paper needs experimental evaluation. That is provide plots where the theoretical results are verified. The comparison of the proposed SGDA-RR compared to the classical SGDA is heavily needed to convince the reader that this is a valuable algorithm that works also in practice. \n\n--------Update------------\n\nThank you to the authors for providing further clarification on the raised points. I have read the other reviews and the rebuttal and browsed through the paper again.\n\nI increase my score from 6 to 8. ", "strength_and_weaknesses": "The paper is well-written and the main contributions are clear. To the best of my knowledge, this is one of the first papers that provides an analysis of random reshuffling methods for solving min-max problems. Das et. al 2022 as correctly pointed out by the authors is the most closely related work to this paper but it focuses on either different classes of problems or slightly different algorithms. \n\nI enjoy reading this paper. I went through the proofs and the results seem correct. The related work from optimization literature is also very well presented. \n\nI gave a score of 6 rather than 8 for one main reason:\nI believe that the paper needs experimental evaluation. That is provide plots where the theoretical results are verified. The comparison of the proposed SGDA-RR compared to the classical SGDA is heavily needed to convince the reader that this is a valuable algorithm that works also in practice. \n\nEven if the experiments do not match exactly the theoretical results, the reader needs to know what to expect. The existing theorems suggest very small step sizes which means that in practice the proposed RR might not work as expected compared to the vanilla uniform sampling SGDA.\n\nIn terms of space, the current section \"6. Proof Sketch\" could easily move to the Appendix and get replaced by Numerical experiments section.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster