Stochastic Extragradient with Flip-Flop Shuffling & Anchoring: Provable Improvements
Authors: Jiseok Chae
Chulhee Yun
Donghwan Kim
Venue: NeurIPS 2024 poster (2024)
Keywords: minimax optimization
stochastic optimization
extragradient method
without-replacement sampling
Primary area: optimization
TL;DR: We study the convergence of the stochastic extragradient method with flip-flop shuffling sampling scheme and anchoring, and show provable improvements over other SGDA/SEG variants.

Abstract: In minimax optimization, the extragradient (EG) method has been extensively studied because it outperforms the gradient descent-ascent method in convex-concave (C-C) problems. Yet, stochastic EG (SEG) has seen limited success in C-C problems, especially for unconstrained cases. Motivated by the recent progress of shuffling-based stochastic methods, we investigate the convergence of shuffling-based SEG in unconstrained finite-sum minimax problems, in search of convergent shuffling-based SEG. Our analysis reveals that both random reshuffling and the recently proposed flip-flop shuffling alone can suffer divergence in C-C problems. However, with an additional simple trick called anchoring, we develop the SEG with flip-flop anchoring (SEG-FFA) method which successfully converges in C-C problems. We also show upper and lower bounds in the strongly-convex-strongly-concave setting, demonstrating that SEG-FFA has a provably faster convergence rate compared to other shuffling-based methods.

Stochastic Extragradient with Flip-Flop Shuffling & Anchoring: Provable Improvements
Jiseok Chae
Chulhee Yun
Department of Mathematical Sciences KAIST
Kim Jaechul Graduate School of Al
KAIST
Daejeon, Republic of Korea jsch@kaist.ac.
Seoul, Republic of Korea chulhee, yunkkaiskkkk......... ac. kr
Donghwan Kim
Department of Mathematical Sciences KAIST
Daejeon, Republic of Korea donghwankim@kaiist. ac kr
Abstract
In minimax optimization, the extragradient (EG) method has been extensively studied because it outperforms the gradient descent- ascent method convex- concave (C-C) problems. Yet, stochastic EG (SEG) has seen limited success in C-C problems, especially for unconstrained cases. Motivated by the recent progress shuffling-bard based stochastic methods, investigate the convergence of shuffling- based SEG in unconstrained finite-sum minimax problems, in search of convergent shuffling-based SEG. Our analysis reveals that both random reshuffling and the recently proposed flip-flop shuffling alone can suffer divergence in C-C problems. However, with additional simple trick called anchoring, we develop the SEG with fli--llp anchoring (SEG-FFA) method which successfully converges in C-C problems. We also show upper and lower bounds in the strongly-convex convex-strongly- concave setting, demonstrating that SEG-FFA has a provably faster convergence rate compared other shufffing-basee methods.
Introduction
Minimax problems with a finite-sum structure, which are optimization problems of the form
x2
min max f(x, y)
f( y),
y
can be found in many interesting applications, such generative adversarial networks [19] refining diffusion models (28). adversarial training (37), optimal transport based generative models [48), multi-agent reinforcement learning (53) and so on. Deterministic methods for minimax problems, such as gradient descent-ascent (GDA) 3 and extragradient (EG) (29), have been extensively studied in the literature. It is though known that, unlike gradient descent (GD) for minimization problems, GDA may diverge even when f is convex on and concave on On the other hand, EG employs two-step update procedure, named extrapolation and update steps (see Section 2 for details), which allows it to find an optimum under this convex-concave setting (29 [1], and moreover, attains convergence rate faster than GDA when f is strongly convex on æ and strongly concave on y.
In contrast, attempts to construct stochastic variants of these algorithms have not been so fruitful. When / is convex-coneave, stochastic gradient descent-ascent (SGDA) clearly may diverge, just as
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

in the deterministic GDA. To make matters worse, stochastic extragradient (SEG) methods have also had limited success on unconstrained convex-concave problems. As we elaborate in Section [ in more detail, existing versions of SEG and their analyses have limitations that hinder its application to general unconstrained finite-sum convex-concaye problems, requiring additional assumptions such as bounded domain, increasing batch size, convex-concavity of each component ft, uniformly bounded gradient variance, and/or absence of convergence rates.
In the context of finite-sum optimization, most of the theoretical studies on stochastic methods have long been based on the with-replacemmnt sampling scheme, where an index i(t) is independently and uniformly sampled among (1...., n at each iteration t. Such sampling scheme is relatively easy to theoretically analyze, because the sampled f((:) is an unbiased estimator of the full objective function f. In practice, however, inspired by the empirical observations of faster convergence in finite-sum minimization 8 47 the withouttreplacement sampling schemes have been the de facto standard. Among them, the most popular is the random reshuffling (RR) scheme, where in every epoch consisting of n iterations, the indices are chosen exactly once in a randomly shuffled order.
This gap between theory and practice in minimization problems is being closed by the recent breakthroughs in stochastic gradient descent (SGD), namely that SGD with RR leads to provably faster convergence compared to with-replacemeen SGD when the number of epochs is large enough MI
35
S5 56]. This has motivated further studies on finding other shuffling- based sampling schemes that can improve upon RR. resulting in the discoveries such as the fli-flop scheme [46]
39
and gradient balancing (GraB) I 32). The flip-flop scheme is a particularly simple yet interesting modification of RR with improved rates in quadratic problems: random permutation is used twice in single epoch (i.e., two passes over n components in an epoch), but the order is reversed in the second pass.
The aforesaid progress in minimization also triggered the study of stochastic minimax methods with shuffling. Similar to minimization problems, SGDA with RR indeed converges faster than the with- replacement SGDA, under assumptions such f satisfying the
objectives [15 or condition [3]. Despite the superiority of EG over GDA, the SEG with shuffting has not been shown to have a solid theoretical advantage over the SGDA with shuffling yet. This motivated us to study the following question:
Can shuffling schemes provide convergence guarantees for SEG, improved upon SGDA with shufffing, in unconstrained finite-sum
settings?
There are two types of SEG: same-sample SEG, where sample chosen is used both for the extrapolation step and the update step, and independent-sample SEG, where two independently chosen samples are used in each step. We will particularly focus on the same-s SEG because combines more naturally with shuffligg-asse schemes than independent-sampee SEG. Therefore, to be more specific, we are interested in developing shuffling-based variants of same-sample SEG in unconstrained finite-sum minimax problems with minimal modifications to the algorithm. We show that (a) in convex- convex-concav concave settings, our new method reaches an optimum with a guarantee on the rate of convergence, overcoming the limitations of existing results; (b) in strongly-convex -orvex-stronlly- concave settings, the method converges faster than other SGDA/SEG variants.
1.1 Our Contributions
In this paper, we study various same-sample SEG algorithms under different shuffling schemes, and propose the stochastic extragradient with flip-flpp anchoring (SEG-FFA) method, which is SEG amended with the techniques of flip-flop shuffling scheme and anchoring. Here, by anchoring we refer to step of taking convex combination between the initial and final iterates of an epoch, resembling the celebrated Trasnosel'skii-Monn Mkin-nnnnnn iteration [30 33 as we discuss in Section 5 With such minimal modifications to SEG, we show that SEG-FFA achieves provably improved convergence guarantees. More precisely, our contributions can be listed as follows (see Table [for a summary). For clarity, we use SEG-US refer with with-replacement SEG, where US stands for uniform sampling.
We first study the same-sample versions of SEG-US, SEG with RR (SEG-RR), and SEG with flip-flop (SEG-FF). We show that they all can diverge when / is convex-concave
'This does not contradict the result in 225 which shows that the independent-sanee SEG with carefully designed step sizes rule converges to optima for convex-concan settings, albeit without convergence rate.

---

Table 1: Summary of upper/lloer convergence bounds of same-sample SEG for unconstrained unite-sum minimax problems, without requiring increasing batch size, convex-coneaviyy component, and uniformly bounded gradient variance. Pseudocode of algorithms can be found in Appendix We only display terms that become dominant for sufficiently large I and K. To compare the with-replacement versions (-US) against shuffling-basee versions, one can substitute 7 nK. The optimality measure used for SC-SC problems is E[| =*1l [|²]] for the last iterate 2. For C-C problems,
each
we consider min,=......T [[| F for with-replacemeet methods and ming= [8] F =0 for
shuffling- based methods.
BAHONNLY-COOVEE-STTRONGGOC CONCAVVEE
CONVEX-CONCAVE
METHOD
UPPER BOUND
LOWER BOUND
UPPER BOUND
LOWER BOUND
SGDA-US
(
RI
R )
BR]
N/A
?(1) (As GDA) ((() (THM
SEG-US
((+)
20
Q
N/A
SGDA-RR
O
(THM
5.6
N/A
2(11) (AS GDA)
SEG-RR
O T22
Q k
(THM.
5.6
2(1) (THм.
4.1
SEG-FF
(THM. F.5
N/A
(111) (TuM.
4.1
SEG-FFA
((xTT) (THM
Õ
K1y3 (THM
1r
show upper bounds for SEG-US, hut they require increasing batch sizes well other assumptions Appendix
35 shows that nddepedent-smmpl SEG-US US converges for stepaizes or., 8, docaying at different rates, but gives no conv. ralc
Unfortunately. the proof this convergence bound in this recent AISTATS paper seems incomect: see Appendix B
by constructing an explicit counterexample (Theorem 4.1 This shows that shuffling alone cannot fix the divergence issue of SEG-US.
We next investigate the underlying cause for the nonconvergence of SEG-US, SEG-RR, and SEG-FF. In particular, we identify that either they fail match the update equation of the reference method EG beyond first-order Taylor expansion terms, or attempting match both first- and second-order Taylor expansion terms results in divergence (Proposition 5.2)
By adopting simple technique of anchoring on top of flip-flop shuffling. we devise our algorithm SEG-FFA, whose epoch-wise update deterministically matches EG up to second- order Taylor expansion terms (Proposition 5.3) We prove that SEG-FFA enjoys improved convergence guarantees, as anticipated by our design principle. Most importantly, we show that SEG-FFA achieves a convergence rate of (3/xx//) when f is convex-concaye where K denotes the number of epochs. This is in stark contrast to other baseline algorithms that diverge under this setting (see the last column of Table [
Moreover, we show that when f is wroonllyconvex--ttrngyyyyyy
SEG-FFA achieves convergence rate of O(1/nk*) (Theorem 5.5). In addition. by proving [(1/nx²) lower bounds for the convergence rates SGDA-RR and SEG-RR under the same setting (Theorem 5.6), we show that SEG-FFA has provable advantage over these baseline algorithms.
2 Related Works
Extragradient and EG+ Extragradient (EG) method [29] is widely used minimax optimization problems.
method, well-known for resolving the nonconvergence issue of GDA on In this paper, also consider EG+ [17], which is generalization of EG. The update rule of EG+ is defined, for stepsizes {7,,) and (122,s 11200 as
ut +- x Mi. V. (
h+3 +- xx 1/2,1 Vn flu x²*) yht n** 12,6 V, I (uu o*
k nh +T1 V., (ath. )²²
The first step is called the extrapolation step, and the second step is called the update step. If is convex-concave, Diakonikolas et [17 show that FG+ reaches an optimum when 7), 12, In particular, when 7/, 72,k. recover the standard EG by Korpelevich [29]
3

---

Stochastic Variants of Extragradient In (2) if the stochastic estimators of Vz f and Vy f are used instead of the gradients themselves, we get the standard SEG. If estimator chosen is used for both the extrapolation and the update steps, we get the same-sample SEG, which we focus on in this paper; see Appendix
A for the pseudocode.
While EG improves upon GDA, unfortunately, SEG has not been able to show a clear advantage over SGDA. On one hand, analyses of SEG on hetil//-oooeeeettooyy--o-ooo
problems have shown some success; see, e.g. [8 20 Yet, on the other hand, for general unconstrained convex-concave problems, to the best of our knowledge, the existing stochastic variants of EG and their analyses face several limitations I Assumptions commonly imposed in the existing literature include: (i) the domain is bounded, either explicitly or implicitly [6], (ii) one must increase the batch size R and (iii) each component f. is convex
to achieve convergence [9] [7 20
[20] 36], and
(iv) the components have uniformly bounded gradient variance 17
For further details, see
Appendix B. and Table therren.. Notably, Hsieh et al. [25] prove convergence of the independent- sample SEG without these four restrictions, but the result lacks an explicit convergence rate.
Our proposed SEG-FFA overcomes all the aforementioned limitations, and reaches an optimum with an explicit rate in unconstrained convex-concave problems, under relatively mild conditions. The readers may also refer to 77] for a comprehensive overview on this topic.
Meanwhile, under the finite-sum setting, variance reduction schemes have also been considered, achieving some promising results 2 [0]. Yet, although theoretically appealing. variance reduction is less widely used in practice due their curiously inferior performance in training neural networks [16]. On top of this practical issue, variance reduction techniques share the aforementioned limitation (ii), as accessing full gradients this paper is to study how a carefully chosen sampling scheme, with minimal modifications to the algorithm, can improve the convergence of SEG without the need for increased batch size; therefore, we believe that our work is not directly comparable to variance reduction-ban based EG.
be viewed as increasing the batch size. In contrast, our main goal in
Taylor Expansion Matching and Convergence Guarantees It has been repeatedly reported that the convergence of an optimization method is deeply related to the degree to which the Taylor expansion (with respect to the step size) of its update equation matches with that of already known convergent method. For example, Mokhtari et al. (38] observed that the advantage of EG over GDA comes from the Taylor expansion of update equations of EG matching that of the proximal point (PP) method 34 up to second-order terms, whereas GDA matches PP only up to first-order terms.
The advantages of the shuffling scheme over the with-replacemment sampling can be explained in similar way. One key property of shuffling-based methods is that, while the individual estimators are biased as they are dependent to other estimators within the same epoch, the overall stochastic error across the epoch decreases dramatically compared to using n independent unbiased estimators. For instance, in SGD with RR [I] and in SGDA with RR [15), the overall progress made within each epoch exactly matches their deterministic counterparts up to the first-order, leaving an error as small as O17²), where is the stepsize. Rajput al. (46) observed that, when each component functions are convex quadratics, then using flip-flop on SGD can reduce the error further to ((r²), resulting in an even faster convergence. As further elaborate in Section 5 the motivation behind our design principle of SEG-FFA is also based on this line of observations.
Notations and Problem Settings
Let [n] C Z denote the set (1.....n) .n). The set of all permutations on [m] will be denoted by S,,. For
the finite-sum minimax problem (T). we denote the saddle gradient operators by
V f( v, [ F(.) =-()= V fi()) - f((-) [
F()=
i
"Most of these results are carried assuming access stochastic oracle of f. which indeed subsumes the unite-sum setting as a special case. However. it seems unlikely that these limitations the existing studies will be easily resolved by simply narrowing the focus down to the finite-sum setting: see Appendix [.3)
'Recently. Emmanouilidis et al. [18] claimed the convergence of SEG-RR in the convex-concave setting. Unfortunately, however. there seems to a flaw in their proof. We defer a discussion on this Appendix B.
'In fact, for the methods studied in 17 20 it is possible to show that increasing the batch size is stricily necessary and unavoidable for convergence; see Appendix H.2

---

The derivative of an operator will be denoted with prefix D. For example, the derivative of F is denoted by DF. Often single vector will be used to denote the minimization and the maximization variable at once. For instance, for E RRdi-da which is concatenation of x E Rdd and y E R we simply write Fz to denote Fxx, y)-
It is well known that, if f is p-strongly convex on and μ-strongly concave on for some > 0 (respectively, μ 0), then its saddle gradient F is p-strongly monotone (respectively, monotone), in the following sense. For a proof of this standard fact, see, e.g., 22.
Assumption 3.1 (Monotonicity & Strong Monotonicity). For μ > 0, we say that an operator F is j--stongly monotone if, for any u E R2 holds that
Fz Fw, 2 - w) 2 1 |= - w0l
If 33 holds for O, then we say that F is monotone.
Thus, from now on, we will use the term strongly monotone (respectively, monotone) problems rather than soonnngyyoooee-strnnnyy-y-o assume that the full saddle gradient F (strongly) monotone, not the individual ','s.
(respectively, convex-concave) problems. Notice that we only
In addition, we remark that our convergence analysis under the monotonicity of F, Theorem 5.4 in fact requires only relaxed version of monotonicity, known star-monotonicity, This condition imposes the inequality 33) with O, but only when w z", where z" is point such that
Fz" O. This relaxation allows for certain degree of noncomvex-noncoocavity in For more detailed discussion on the star-monotonicity condition, see Appendix G.T
Other three underlying assumptions make the problem can be listed as follows.
Assumption 3.2 (Existence of an Optimal Solution), An optimal solution of the problem I which a point we denote by -(x", y²) that satisfies
f(x", .)) S f(x', ,y") S f(x,y'))
for any Rd and y Rd exists in d2d-
Because the problem is unconstrained and f only if Fz" 0. For strongly monotone problems, Assumption 3.2 is not explicitly required, as it is guaranteed a priori [5] Proposition 22.11]. For monotone problems, we explicitly impose Assumption in order to exclude pathological problems such as f(x,,) = y.
a point 2" is an optimum if and
Assumption 3.3 (Smoothness). Each f. L-smooth, and each F; is M-smooth. That is, for any 2, d2
(i) [Ez Faall| S L |1 w//.
(ii) [DF DF S M || w/|-
w|]
is worth mentioning that the gradient operator F; arising from a quadratic function fi is M- smooth with M O. Notice also that, by the finite-sum structure == E. F, it is clear that Assumption 3.3 implies f being L-smooth and F being Msmootth.
The L-smoothness assumption on the objective functions is standard in the optimization literature, while the M smoothhess assumption on the saddle gradients may look less standard. This smoothness assumption on the saddle gradient, in other words the Lipschitz Hessian condition. for analyzing SEG- FFA stems from the analysis of the flip-flop sampling scheme [46]. In particular, this is needed for bounding the high-order error terms between the (deterministic) EG and SEG-FFA in Section 5.1 The existing analysis of flip-flop sampling [46) is limited to quadratic functions that trivially have O-Lipschitz Hessians (M = 0),
analysis is step forward.
Assumption 3,4 (Component Variance). There exist constants 2 0 and 2 0 such that
F Fz < [p +0)²
Vz.
(4)
For strongly monotone problems, Assumption 3.4 is not explicitly required, because it can be obtained as a consequence of the preceding assumptions: see Lemma C.9 Nevertheless, for convenience, we will keep the notations p and in (4) for the strongly monotone setting well.
5

---

In many existing works on stochastic optimization methods for minimax problems, Assumption 3.4 with p 0 is imposed. This uniform bound on the variance simplifies the convergence analyses, but it is also fairly restrictive especially in the unconstrained settings. Already for bilinear finite-sum minimax problems (a, y) 1 > a: B.y. one can easily check that setting / = forces the matrices B, to be exactly equal to each other. For machine learning applications, it has been also reported that the assumption with p = often fails to hold [7]. Therefore, allowing the variance to grow with the gradient Fz makes the assumption much more realistic.
The Lipschitz Hessian condition and the component variance assumption for monotone problems may still look rather strong. We leave the study on how one can relax such assumptions to prove upper bounds for convergence rates as an interesting future direction. On the other hand, while our lower bound results in Theorems 4.1 and 5.6 are derived under those strong assumptions, they still serve as lower bound results also for larger function classes that do not have those assumptions. In other words, the value of those results are not limited because of those assumptions being imposed.
4 Shuffling Alone Is Not Enough
Under the settings we have discussed, we study the SEG with shuffling- -ased sampling schemes. First we describe the precise methods of our consideration, namely the SEG-RR and SEG-FF.
For k in the beginning of an epoch, random permutation The sampled from a uniform distribution over Sn Then, for n iterations, we use each of the component functions once, in the order determined by тg. That is, for 0.1...., n
do
w t- 2 - - 441 + z -BpFFriittt)ur
(5)
for some stepsizes on and Sg. In case of SEG-RR, the epoch is completed here, and we set =0 k+1 +- z as the initial point for the next epoch.
In case of SEG-FF, et al. [46]. In these additional iterations, the component functions are each used once more, but in the reverse order. That is, for n, n I...., 2n 1, we do
additionally perform more iterations in the epoch, proposed in Rajput
w t 2 a Fr. (2n- * < z - -BaFr. (2n-
(6)
Then we set 2 z as the initial point for the next epoch. The full pseudocode of these methods can be found in Appendix
When F is strongly monotone, it is possible to show that both SEG-RR and SEG-FF indeed provide speed-up up over SEG-US. The well-known rate of SEG-US under strong monotonicity of F is @(/rr), where T' is the total number iterations 66 20 Translating this rate our shuffling- based setting, where there are (n) iterations per epoch, this rate amounts to ((/nk), ). Recently, Emmanouilidis al. [88 have shown that SEG-RR. under the same setting as ours, attains convergence rate of O(/ux²)) ), on par with the rate of SGDA-RR [5] Appendix we also show that SEG-FF attains similar rate of convergence.
However, it turns that the benefit of shuffling does not extend further beyond the strongly monotone setting. In fact, when F is merely monotone, then in the worst case, SEG-RR and SEG-FF suffers from nonconvergence. just in the case of SEG-US.
Theorem 4.1. For monotone F, consisting of L-smooth quadratic f; 's satisfying Assumption 3.4 with (p,o) = (1,0), such that SEG-US, SEG-RR and SEG-FF diverge in expectation for any positive stepsizes.
there exists minimax problem with f(x, - ()
2 Ee fi(z, having
We provide the explicit counterexample and the proof of divergence in Appendix H.1
Note that
Theorem 4.1 and its proof Appendix H.1 imply that min E|| F2, 12 2211 for SEG-US
and mink=o..... [E[| Fx ||²] 2(1) for SEG-RR and SEG-FF, summarized in Table

---

5 SEG-FFA: SEG with Flip-Flop Anchoring
In this section, we investigate the underlying cause for nonconvergence of SEG-RR and SEG-FF from the perspective of how accurately they match the convergent EG or PP methods in terms of the Taylor expansions of updates. We then propose adding a simple anchoring step at the end of each epoch of SEG-FF. turns out that adding the anchoring step, which is step of taking convex combination of an iterate with a previously computed iterate, reduces the stochastic noise and leads method with improved convergence properties.
5.1 Design Principle: Second-Order Matching
As observed by [38. the key feature of EG behind its superior convergence properties compared to GDA is its update rule closely resembling PP, while the "error" of GDA as an approximation of PP is so large that it hinders convergence. The difference between the updates of EG and PP, in the Taylor expansion, is small as (n²²) per iteration, where is the stepsize. On the other hand, GDA and PP show a difference of (17)) ) and this greater "error" explains why GDA diverges while EG and PP converge. Of course, EG and PP are not the only two algorithms that converge in the monotone setting; let us recall the update rule of EG+ method [17), and Taylor-expand it as the following:
z == 1/2 F(z 771 Fz)
(7)
mp F= m172 O1im2)).
EG+ is known to converge for unconstrained monotone problems if m 2 72. When n 7/2, recovers EG and matches PP up to second-order terms.
Based on these observations, we now state our key principle for designing convergent version of SEG: second-order matching. We would like to choose proper stepsizes, sampling scheme, and anchoring scheme so that our equation of convergent algorithm (EG/PP or EG+) up to the O(1²²) terms (i.e., second-order terms in the Taylor expansion), thereby satisfying small Onr²) approximation error. We show that (a) this second-order matching can be achieved with flip-flop anchoring, but not solely by permutation- sampling such as RR and flip-flop (without anchoring), and (b) second-order matching indeed grants convergence for monotone problems. In particular, we demonstrate that
SEG can deterministically match the update
1. SEG-RR suffers a poor approximation error of O(7²)) as an approximation of EG/EG+.
2. SEG-FF can match EG+ up to second-order terms, but it results in a choice of stepsizes
(7/2 2nn) that make EG+ diverge (Proposition 5.2)
3. SEG-FFA, the method we propose, matches EG up to second-orde order terms to get an error of (17²)) Prroposition achieving convergence in monotone problems (Theorem 5.44
To this end, let us consider general form of SEG that incorporates any arbitrary sampling scheme. More precisely, in the k-th "epoch" consisted of N iterations, the components are chosen in the order of To T some multiple of n (e.g., N = n for SEG-RR, N 2n for SEG-FF). Then, given a and / we perform SEG updates, for i = 0, 1, N - 1,
T N where T [F...... F,} for each i. For our purpose, we assume that N is
1 + z aT, z
(8)
# + 2 - BT.
5.1.1 Necessity of Flip-Flop Sampling
The general method in (8) that sets the initial point for the next epoch as 2 2/ satisfies the following property.
Proposition 5.1. Suppose that Assumption 3.3 holds. For some t o ((a + 3)2), it holds that
N-1
A-1 20
=8 3
I
a8
Σ DT
32 Σ
+ + (9)
i=0
==
7

---

See Appendix D.I for the proof. To make 7 and
9
match up to the second-order, both the equations
7/2
F k
B
T
and
(10)
N DF, (+) + (P) aB Σ DT + 3 DT (z0 I 1g3
12 n
icj
(11)
must hold. Clearly, without-replacement sampling will make (TO) hold. However, it is easy to check that random reshuffling falls short of making [TT hold. This is because, if RR is used, then Tot Th ...., T is nothing but a reordering of Fi, i,.... Fn into Fr(i)..... Fr(n), the RHS of
(TT) can only contain terms DF) (xb) ) (1))) with S j. This observation motivates the use of flip-flpp sampling, because choosing T. T2 lets all the required terms DF, F( to appear in the RHS of (1I).
5.1.2 Designing SEG-FFA
Flip-flop does resolve the aforesaid issue, but still another complication remains for plain SEG-FF Proposition 5.2. Suppose we use flip-flop sampling (without anchoring). order to make (T0) and (II) hold, must choose 3 = m/n and a .//2. However, this leads to mp2 = 2m,,, which is the set of parameters that fails to make EG+ converge.
For the proof, see Appendix D.2 This shows that a modification necessary develop stochastic method that achieves second-orda matching to convergent EG/EG+ methods.
We thus propose to add an anchoring step:
1 (2N + zb)
(12)
after finishing the N updates (8) instead of 2/=1 2 This is Stochastic ExtraGradient with Flip-Flop Anchoring (SEG-FFA) method, named after the design of combining the flip-flop sampling scheme and the anchoring step. We note that this idea of taking convex combination has originally appeared in the Krasnosel's pooeee'ski-aaan iteration 30, 33 and also under the name of
Lookahead methods [22 43) This slightly differs from the more widely used Halpern iteration 23
based anchoring (cf. 54 which would have used the initial point zg instead of z in (12).
This anchoring step changes 9 accordingly, and essentially amounts to dividing the right-hand sides of (TO) and (TT) each by 2 (see Appendix [D] for the detailed derivations). We show that choosing 3/2 in fact leads to the second-order matching to EG, i.e., EG+ with 7/1 1p2-
Proposition 5.3. Suppose that Assumptions 3.3 and 3.4 hold. Then, for Sy = and ag 8v/2, SEG-FFA becomes an approximation of EG with error at most O ). In other words, we achieve
|| - rmF F=
20 k+1 0(r))
In other words, adding the anchoring step allows us to get method that well approximates the convergent EG with an error as small as (17²). For more in-depth discussion, see Appendix E
5.2 Convergence Analysis of SEG-FFA
As result of the second-order matching, we obtain SEG-FFA, a stochastic method that has an error of O(1²²) as an approximation of EG. Achieving this order of magnitude for the approximation error turns out to the key to the exact convergence an optimum under the monotone setting.
Theorem 5.4. Suppose that F (star- Imonotone, Assumptions 3.2 3.3 3.4 hold, and we are running SEG-FFA Then, for any K > 1, by choosing the stepsizes sufficiently small and decaying as Ba (1/22//3 (ogg// k) and ag Be/2, the iterates generated by SEG- FFA achieves the bound
(log K)²
min
Fz
=0
0= K
K1/33
8

---

We note that, although Theorem 5.4 and also Theorem 5.5) below, are stated specifically for SEG-FFA, our analyses show that both theorems can be applied to any method that achieves the second-order matching in terms of Proposition 5.3
For the full statement of the theorem and its proof, see Appendix G
The reduced error also shows gain in the rate of convergence under the strongly monotone setting. This aligns with the intuition that error hinders convergence, hence having a smaller error is beneficial. Theorem 5.5. Suppose that F is μ utsstoongyy monotone with μ. > O and Assumption 3.3 holds. Then, there exists choice of n > O such that, when SEG-FFA is run for K epochs with constant stepsizes 3x = ll and ag = */2, for some constant w independent of 7, the iterates generated by SEG-FFA achieves the bound
>=11² S exp (-1uwnk) ||00 2=1²+ +0 ( (1og(n1/4AK))
B
z²
nK4
Theorem 5.5
actually stems from unified analysis that encompasses all the shuffling- bbatid SEG methods introduced in this paper, including SEG-RR and SEG-FF. See Appendix For the details.
Notice the exponent of the number of epochs K in the convergence rate, which twice as large as the exponent 2 of SGDA-RR and SEG-RR. In fact, this gain in the rate of convergence turns out to be fundamental. As we show in the following theorem, the theoretical lower bounds of convergence for SGDA-RR and SEG-RR with constant stepsize are both (2(//x²)). This exhibits that there is provable gap between those methods and SEG-FFA, which attains O(//kk*).
Theorem 5.6. Suppose n 2 For both SGDA-RR with constant stepsize ak = > and SEG-RR with constant stepsize ag a > 0, Bg = 3 > 0, there exists a u-strongly monotone minimax problem [(z) = ( with μ > such that regardless of stepsizes, we have
if S L/M.
|| z" ==1
Lank La n
Ω
if L/P.
Proof. The full statement and the proof are presented in Appendix H.3
Experiments
We consider randomly generated quadratic problems of the form
min max MER yER
A
B
a
(13)
B
C.
ni
In particular, we sample the random components so that the full objective is either monotone or strongly monotone, respectively, while each of the components may be nonmonotone. For the exact descriptions on how we constructed the problems, see Appendix I.1
Monotone Case
We the experiment 5 random instances of 133 with the stepsizes scheduled
as 77 7o/(1+k/1000.0) where 77o = min (0.01, + for SEG-FFA, and Cq = 3g = 7) for SEG-US. SEG-RR, and SEG-FF. The exponent 0.34 to ensure sufficient decay rate required by Theorem 5 and the convergence of SEG-FFA under such stepsize scheduling is validated in Remark G.5 The value of 1/o is, however, heuristically determined small number. The results of the geometric mean over the runs are plotted in Figure ] As expected by our theory, SEG-FFA successfully shows convergence, while all of SEG-FF, SEG-RR. and SEG-US diverge in the long rum.
Strongly monotone case Along with the variants of SEG, also compare the performances of SGDA-RR and SGDA-US. We ran the experiment on random instances of (3) with stepsizes T 0.001, and the results plotted in Figure Additional results obtained from using other stepsizes can be found in Appendix [.4] We again observe an agreement between the empirical results
and theory; SEG-FFA eventually finds the point with the smallest gradient norm among the methods that are considered.
Further additional experiments and ablation studies we have conducted can be found in Appendix

---

10
10a
SEG FF
SEG
SEGUS
SCDA-US
SEG RR
10
10a
SEG
10
[22 Di 1P49
10
10"3
1P22
10-3
10-1
10
10
20000
40000 number passes
60000
80000
number passes (1)
Figure Experimental results the (left) monotone and (right) strongly monotone examples, comparing the variants of SEG. For a fair comparison, we take the number of passes over the full dataset as the abscissae. In other words, we plot "|I for SEG-FFA and SEG-FF, as they pass through the whole dataset twice every epoch, and || |= //1==001" for the other methods, as they pass once every epoch.
7 Conclusion
We proposed SEG-FFA, a new stochastic variant EG that uses flip-flop sampling and anchoring. While being minimal modification from the vanilla SEG, SEG-FFA attains the erucial "second- order matching" property to the deterministic EG, leading to a two-fold improved convergence. On one hand, SEG-FFA reaches optimum in the monotone setting, unlike many baseline methods such as SEG-US, SEG-RR, and SEG-FF that diverge. Moreover, in the strongly monotone setting, SEG-FFA shows faster convergence with a provable gap from the other methods.
An interesting future direction would be to extend our work to more general problems, further exploring the potentials of the second-order matching technique. It would also be appealing to further study whether it possible to devise a new method that achieves second-order (or higher) matching without the anchoring step, potentially enhancing our understanding of the effectiveness of the matching technique.
Acknowledgments and Disclosure of Funding
This work was supported in part by the National Research Foundation of Korea (NRF) grant funded by the Korea government (MSIT) (No. 9S-2019-NR0400550 JC and DK acknowledge support from the NRF grant (No. RS-2022-NR0717115 funded by the Korea government (MSIT), and the Samsung Science Technology Foundation grant (No. SSTF-BA2101-2 CY acknowledges support from the NRF grant (No. RS-2023-0021 105220111111))) funded by the Korea government (MSIT).
References
[1] 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.
[2] Ahmet Alacaoglu and Yura Malitsky. Stochastic variance reduction for variational inequality methods. In Conference on Learning Theory, pages 778-816 PMLR, 2022.
[3] Kenneth Arrow and Leonid Hurwicz. Reduction of constrained maxima to saddle-poin problems. In Proc. Third Berkeley Symp. Math. Statist. and Prob., volume 5, pages 1-20. 1956. Univ. of Calif. Press.
[4] Waiss Azizian, Ioannis Mitliagkas, Simon Lacoste-Julien, and Gauthier Gidel. tight and unified analysis of saddient-based methods for whole spectrum of differentiable games. In
10

---

International Conference on Artificial Intelligence and Statistics, pages PMLR, 2020.
[5] Heinz H. Bauschke and Patrick L. Combettes. Convex Analysis and Monotone Operator Theory in Hilbert Spaces. Springer, 2nd edition, 2017.
[6] Aleksandr Beznosikov, Valentin Samokhin, and Alexander Gasnikov. Distributed saddle-point problems: Lower bounds, near-optimal and robust algorithms. arXiv preprint arXiv:2010.13112 2020.
[7] Aleksandr Beznosikov, Boris Polyak, Eduard Gorbunov, Dmitry Kovalev, and Alexander Gasnikov. Smooth monotone stochastic variational inequalities and saddle point problems: A survey. European Mathematical Society Magazine, 127:15-28, -8, 2023.
[8] Léon Bottou. Curiously fast convergence of some stochastic gradient descent algorithms. In Proceedings of the symposium on learning and data science, Paris, volume 8, pages 2624-2633. Citeseer, 2009.
[9] Xufeng Cai, Chaobing Song, Cristóbal Guzmán, and Jelena Diakonikolas. Stochastic Halpern iteration with variance reduction for stochastic monotone inclusions. Advances in Neural Information Processing Systems, 35:24766-245 24779, 2022.
[10] Yair Carmon, Yujia Jin, Aaron Sidford, and Kevin Tian. Variance reduction for matrix games. Advances in Neural Information Processing Systems, 32, 2019.
[11] Jacyoung Cha, Jacwook Lee, and Chulhee Yun. Tighter lower bounds for shuffling SGD: Random permutations and beyond. International Conference on Machine Learning, pages 3855 3912. PMLR, 2023.
[12] Tatjana Chavdarova, Matteo Pagliardini, Sehastian U Stich, François Fleuret, and Martin Jaggi. Taming GANs with Lookahead-ming minmaxx. In The Ninth International Conference on Learning Representations, 2021.
[13] Hanseul Cho and Chulhee Yun. SGDA with shuffling: faster convergence for nonconvex-Pt. minimax optimization. In The Eleventh International Conference on Learning Representations, 2023.
[14] Sayantan Choudhury, Eduard Gorbunov, and Nicolas Loizou. Single-call stochastic extragradient methods for structured non non-monotone variational inequalities: Improved analysis under weaker conditions. Advances Neural Information Processing Systems, 36:64918-6666 1-64955,, 2023.
[15] Aniket Das, Bernhard Schölkopf, and Michael Muehlebach. Sampling without replacement leads faster rates in finite-sum minimax optimization. Advances in Neural Information Processing Systems, 35:6749 2022.
[16] Aaron Defazio and Léon Bottou. On the ineffectiveness of variance reduced optimization for deep learning. Advances in Neural Information Processing Systems, 32, 2019.
[17] Jelena Diakonikolas, Constantinos Daskalakis, and Michael I. Jordan. Efficient methods for structured
min-max optimization. In International Conference
Artificial Intelligence and Statistics, pages 2746-2754. PMLR, 2021.
[18] Konstantinos Emmanouilidis, René Vidal, and Nicolas Loizou. Stochastic extragradient with random reshuffling: Improved convergence for variational inequalities. In International Conference on Artificial Intelligence and Statistics, pages 3682-3690. PMLR, 2024.
[19] Ian Goodfellow, Jean Pouget-Abadie Mehdi Mirza, Bing Xu. David Warde-Farley, Sherjil Orair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. Advances in neural information processing systems, 27, 2014.
[20] Eduard Gorbunov, Hugo Berard, Gauthier Gidel, and Nicolas Loizou. Stochastic extragradient: General analysis and improved rates. In International Conference on Artificial Intelligence and Statistics, pages 7865-7901. PMLR, 2022.

---

[21] Eduard Gorbunov, Nicolas Loizou, and Gauthier Gidel. Extragradient method: O(1/K) last- iterate convergence for monotone variational inequalities and connections with cocoercivity. In International Conference on Artificial Intelligence and Statistics, pages 366-402. PMLR, 2022.
[22] Benjamin Grimmer, Haihao Lu, Pratik Worah, and Vahab Mirrokni. The landscape of the proximal point method for nonconvex-noncoocave minimax optimization. Mathematical Programming, 201(1-2):373-400) 2023.
[23] Benjamin Halpern. Fixed points of nonexpanding maps. Bulletin of the American Mathematical Society, 73(6)957--61, 1967.
[24] Charles R. Harris, K. Jarrod Millman, Stéfan J. van der Walt, Ralf Gommers, Pauli Virtanen, David Cournapeau, Eric Wieser, Julian Taylor, Sebastian Berg, Nathaniel Smith, Robert Kern, Matti Picus, Stephan Hoyer, Marten H. van Kerkwijk, Matthew Brett, Allan Haldane, Jaime Fernández del Río, Mark Wiebe, Pearu Peterson, Pierre Gérard-Marchant, Kevin Sheppard, Tyler Reddy, Warren Weckesser, Hameer Abbasi, Christoph Gohlke, and Travis E. Oliphant. Array programming with NumPy. Nature, 585(7825):357-366 September 2020.
[25] Yu-Guan Hsieh, Franck lutzeler, Jérôme Malick, and Panayotis Mertikopoulos. Explore aggressively, update conservatively: Stochastic extragradient methods with variable stepsize scaling. Advances in Neural Information Processing Systems, 33:16223-16234, 2020.
[26] D. Hunter. Matplotlib: 2d graphics environment. Computing Science Engineering, 09:90-95,200 2007.
[27] Anatoli Juditsky, Arkadi Nemirovski, and Claire Tauvel. Solving variational inequalities with stochastic mirror-prox algorithm. Stochastic Systems, 1(1):17-58, 2011.
[28] Dongjun Kim, Chich Chieh-Hsin Lai, Wei-Hsiang Liao. Naoki Murata, Yuhta Takida, Toshimitsu Uesaka, Yutong He, Yuki Mitsufuji, and Stefano Ermon. Consistency trajectory models: Learning probability flow ODE trajectory of diffusion. In International Conference Learning Representations, 2024.
[29] Galina M. Korpelevich. The extragradient method for finding saddle points and other problems. Matecon, 12:747-756, 1976.
[30] M. A. Krasnosel'ske skii. Two remarks on the method of successive approximations. Uspekhi Matematicheskiikh Nauk, 10:123-127, 1955.
[31] Nicolas Loizou, Hugo Berard, Gauthier Gidel, Ioannis Mitliagkas, and Simon Lacoste-Julien. Stochastic gradient descent-ascent and consensus optimization for smooth games: Convergence analysis under expected co-coercivity. Advances in Neural Information P Processing Systems, 34: 19095-19108, 2021.
[32] Yucheng Lu, Wentao Guo, and Christopher De Sa. GraB: Finding provably better data permutations than random reshuffling. Advances in Neural Informtionn Processing Systems, 35: 2022.
[33] W. Robert Mann. Mean value methods in iteration. Proceedings of the American Mathematical Society, 4(3):506-510, 1953.
[34] Bernard Martinet. Regularisation d' d'inéquations variationelles par approximations succesives. Revue Française d'informatquue et de Recherche opérationelle, 1970.
[35] 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.
[36] Konstantin Mishchenko, Dmitry Kovalev, Egor Shulgin, Peter Richtárik, and Yura Malitsky. Revisiting stochastic extragradient. In International Conference on Artificial Intelligence and Statistics, pages 3573-458- PMLR, 2020.
[37] Aleksander Mądry, Aleksandar Makelov, Ludwig Schmdit, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. International Conference on Learning Representations, 2018.
12

---

[38] Aryan Mokhtari, Asuman Ozdaglar, and Sarath Pattathil. A unified analysis of extra- atra-ggraieett and optimistic gradient methods for saddle point problems: Proximal point approach. In International Conference on Artificial Intelligence and Statistics, pages 1497-1507. PMLR, 2020.
[39] Dheeraj Nagaraj, Prateek Jain, and Praneeth Netrapalli. SGD without replacement: Sharper rates for general smooth convex functions. International Conference on Machine Learning. 1. PMLR, 2019.
pages
[40] Yurii Nesterov. Lectures on convex optimization, volume 137 of Springer Optimization and Its Applications. Springer, second edition, 2018.
[41] Lam M. Nguyen, Quoe Tran-Dinh, Dzung T. Phan, Phuong Ha Nguyen, and Marten Van Dijk. A unified convergence analysis for shufflin-tyype gradient methods. The Journal of Machine Learning Research, 22(1):9397-9440, 2021.
[42] Thomas Pethick, Olivier Fercoq, Puya I Latafat, Panagiotis Patrinos, and Volkan Cevher. Solving stochastic weak Minty variational inequalities without increasing batch size, In International Conference on Learning Representations, 2023.
[43] Thomas Pethick, Wanyun Xie, and Volkan Cevher. Stable nonconvex- ancconve--nonconcav training via linear interpolation. Advances in Neural Information Processing Systems, 37, 2023.
[44] L.. D. Popov. A modification of the EurowiHurwizz method of search for saddle points. Matematicheskie Zamerki, 28(5)7777-784 1980.
[45] Shashank Rajput, Anant Gupta, and Dimitris Papailiopoulos. Closing the convergence gap of SGD without replacement. In International Conference on Machine Learning, pages 7964-7973. PMLR, 2020.
[46] Shashank Rajput, Kangwook Lee, and Dimitris Papailiopoulos. Permutation-basse SGD: Is random optimal? In International Conference on Learning Representations, 2022.
[47] Benjamin Recht and Christopher Ré. Parallel stochastic gradient algorithms for large-scale matrix completion. Mathematical Programming Computation, 5(2):201-25) 2013.
[48] Litu Rout, Alexander Korotin, and Evgeny Burnaev. Generative modeling with optimal transport maps. International Conference on Learning Representations, 2022.
[49] Itay Safran and Ohad Shamir. How good is SGD with random shuffling? In Conference on Learning Theory, pages 3250-3284. PMLR, 2020.
[50] Itay Safran and Ohad Shamir. Random shuffling beats SGD only after many epochs on ill- conditioned problems. Advances in Neural Information Processing Systems, 34:15151-15161, 2021.
[51] Mikhail V. Solodov and Benar Svaiter. hybrid approximate extragradient-proxiie point algorithm using the enlargement of a maximal monotone operator. Ser- Analysis, 7()): 323-345, 1999.
[52] Pauli Virtanen, Ralf Gommers, Travis E. Oliphant, Matt Haberland, Tyler Reddy, David Cournapeau, Evgeni Burovski, Pearu Peterson, Warren Weckesser, Jonathan Bright, Stéfan J. van der Walt, Matthew Brett, Joshua Wilson, K. Jarrod Millman, Nikolay Mayorov, Andrew R. J. Nelson, Eric Jones, Robert Kern, Eric Larson, CJ Carey, ilhan Polat, Yu Feng, Eric W. Moore, Jake VanderPlas, Denis Laxalde, Josef Perktold, Robert Cimrman, Ian Henriksen, E. A. Quintero, Charles R. Harris, Anne M. Archibald, Antônio Ribeiro, Fabian Pedregosa, Paul van Mulbregt, and SciPy 1.0 Contributors. SciPy 1.0: Fundamental Algorithms for Scientific Computing in Python. Nature Methods, 17:261-272 2020.
[53] Hoi-To Wai, Zhuoran Yang, Zhaoran Wang, and Mingyi Hong. Multi-agent reinforcement learning via double averaging primal-dual optimization. Advances in Neural Information Processing Systems, 31, 2018.
13

---

[54] TaeHo Yoon and Ernest K. Ryu. Accelerated Algorithms for Smooth Coareve- Minimax Problems with ((1/k²) Rate on Squared Gradient Norm. In International Conference on Machine Learning, pages 12098-12109. PMIR, 2021.
[55] 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, pages 4653-4658. PMLR, 2021.
[56] Chulhee Yun, Shashank Rajput, and Suvrit Sra. Minibatch vs local SGD with shuffling: Tight convergence bounds and beyond. In International Conference on Learning Representations, 2022.
14

---

Contents
Introduction
1.1 Our Contributions
2
Related Works
3
Notations and Problem Settings
Shuffling Alone Is Not Enough
SEG-FFA: SEG with Flip-Flop Anchoring
5.1
Design Principle: Second-Order Matching
5.1.1
Necessity of Flip-Flop Sampling
5.1.2
Designing SEG-FFA
5.2
Convergence Analysis of SEG-FFA
Experiments
7
Conclusion
10
Pscudocode of the Algorithms
17
Further Details and Discussions the Related Works
18
B.1
Summary of the Limitations of the Existing Works in the Monotone Setting
18
B.2
On the Assumptions Made by Gorbunov et al. [20]
19
B.3
Finite Sum Structure vs. General Stochastic Setting
19
the Claimed Convergence SEG-RR the Monotone Setting by Emmanouilidis
et al. [18]
20
Useful Lemmata
20
D Missing Proofs for Section 5
25
D.I Unravelling the Recurrence of the Generalized SEG and (12)
................................
25
D.2 Insufficiency of Only Using Flip-Flop Sampling
27
Within-Epoch Error Analysis for Upper Bounds
28
E.
Auxiliary Lemmata
29
E.2
Upper Bounds of the Within Epoch Errors
37
E.2.1
Proof of Equation (31) for SEG-FFA
37
E.2.2
Proof of Equation (32) for SEG-FFA
43
E.2.3
Upper Bounds of the Within Epoch Errors for SEG-FF
45
E.2.4
Upper Bounds of the Within -poch Errors for SEG-RR
47
F
Convergence Bounds in the Strongly Monotone Setting
48
15

---

Unified Analysis of the Upper Bounds for Shuffling Based SEG Methods
48
Convergence Rate of SEG-FFA in the Monotone Sefting
54
G.I
Star-monotonicity
54
G.2
Convergence Analysis of SEG-FFA in the (Star- Monotone Setting
54
Proof of Lower Bounds
59
H.1
Proof of the Divergence of SEG-US, SEG-RR and SEG-FF
59
H.2
Proof of Limited Convergence of SEG-US in Monotone Cases
61
H.3
Proof of SGDA-RR and SEG-RR Lower Bounds
64
H.3.1
Existing Lower Bound for SGD-RR
64
H.3.2
Proof of Lower Bound for SGDA-RR
65
H.3.3
Proof of Lower Bound for SEG-RR
65
Additional Experiments
69
Problem Constructions for Experiments in Section
70
I.2
Monotone Case & Ablation Study on the Anchoring
................................
70
1.3
Monotone Case: Comparison with Hsieh et al. 25
71
1.4
Strongly Monotone Case Again, with Various Stepsizes
72
16

---

A Pseudocode of the Algorithms
We present the pseudocode of the algorithms consider in this paper in Algorithms 2 and with the pseudocode the with-replacement stochastic methods in Algorithm
Algorithm 1 LEG-US/SGDA-US
Input: The number of components n: stepsize sequences {ar)22 and 18. Initialize: 2g E Rdd for t = 0, 1.... do
sample (t) uniformly from n1....,n} if SGDA-US then
2:+11 f- 2, ar F( else if SEG-US then
wr +- 2t 0r Fx)
2:+1 c 2t (r)
end if
end for
Algorithm 2 SEG-RR/ SGDA-RR
Input: The number of components n; stepsize sequences (aw)220 and h220 Initialize: =0 E Rd
for 0, 1,... do sample Tx: uniformly from Sn for = 0 to n do if SGDA-RR then
- <- x Fg
else if SEG-RR then w
+ z
Org (1+1))
2, t - - FB Fr
end if end for
=
2
end for
Algorithm 3 SEG-FF
Input: The number of components nı stepsize sequences {an)120 and (Bs J220 Initialize: =0 E Rdd++d
for 0, 1,.. do
sample Ty uniformly from S, for i = to
do
w. +- z au FrF (1+11)
2/11 2 3r (T
end for
for i
n 2n do
t z - as F (2n 23
* t- 2 - 3r F 12 w
end for
=/ k+I
*
22n
end for
17

---

Algorithm 4 SEG-FFA
Input: The number of components n; stepsize sequences (me 1200 Initialize: =0 E Rd
for 0, ..... do
sample Tk uniformly from Sn
for = 0 to n do
w. t 2
F 11 -; zi F (1+1) w
end for
for = n 2n do
W. t x
F (2n
z/_1 f- z - FrF (2n ?
end for
k+1 +- +
end for
B Further Details and Discussions on the Related Works
B.1 Summary of the Limitations the Existing Works in the Monotone Setting
In Table we have summarized the settings considered in each of the previous works on stochastic variants EG discussed in Section / and compare them with our settings. Please note that we focus on the monotone F setting in the table. Entries that are worth further discussions are marked, with the corresponding explanations below.
Table 2: Comparison of the underlying settings between ours and the existing works.
same sample?
required batch size
bounded
uniform gradient variance?
monotone components?
domain?
Ours
/
constantly
X
Cai al. [9]
N/A
increasing
x
Choudhury et al. [14]
N/A
increasing
x
Diakonikolas et al. [17
X
increasing
x
X
V
increasing
x
(star-) /
Gorbunov al.
X
increasing*
x
Hsieh al. 25
X
constant
x
Juditsky et al. 27
X
constant
/
X
Mishchenko et al. 36
V
constant
/
Pethick et
[42
X
constant
(*) The methods proposed in these works are not stochastic variants of EG strict sense. The method introduced by Cai et al. [9] is rather a hybrid of EG and the Halpern iteration (33. while the method by Choudhury et al. [4 is a stochastic version of the so-called optimistic gradient method [44. Hence, determining whether these methods fall into the category of same-sample methods or not is unnecessary. Nonetheless, as these works focus on solving similar problem to ours, we include them as references.
(f) Under the assumptions that Gorbunov al. 20 make in their paper, one can show that each of the components must necessarily be (star-)monotom)) when the full F is sttooonmooooon.. For further explanations on why this is the case, see the following Appendix B.2
(+) Yet, to be precise, what Gorbunov et al. 20 have shown in the monotone case is that SEG-US find an optimal solution if we increase the batch size each iteration. If the batch size is fixed as constant, then they were only able to show that the iterates will be bounded the monnoooee setting. In particular, they did not provide guarantee that the iterates will be necessarily convergent.
In fact, as we demonstrate with an explicit counterexample in Appendix H.2 if we do not increase the batch size each iteration, then it is possible show that SEG-US in the worst case will never
18

---

converge to an optimal point. This nonconvergence result in fact holds for any SEG-US whose extrapolation and update stepsizes differ by a constant factor. Hence, it not only applies [20] but also to 17
($) Hsieh et al. 25 show that independent-sumple SEG-US converges for stepsizes ot, Br decaying at certain different rates, but gives no convergence rates.
(I) Mishchenko et al. [36] assume uniformly bounded gradient variance in the strongly monotone case. In the monotone case, the bound they derived depends on the supremum of the gradient variance over the domain that is under consideration. Hence, in the monotone case, either the domain has to be (implicitly) bounded, or the uniform gradient variance assumption should be imposed.
B.2 On the Assumptions Made by Gorbunov et al. (20
We would like to first clarify that in 200), the requirement to increase the batch size is utilized only in the monotone setting: see, e.g., Corollary E.4 therein.
Gorbunov et al. (20 use generalized notion of jı-strong monotonicity, namely the p-quasii strong monotonicity, which requires the operator to satisfy
= =*) 2 1 ||= ==11?
(14)
In the notion of y-quasi strong monotonicity they also allow S 0. In particular, if (14 holds with μ = 0, then F is called a star-monotone operator. In Appendix G.I we further discuss on star-monotone operators.
Meanwhile, let us further elaborate on why in the (star-)monotone setting, the assumptions made by the authors of 20 lead to each component being star-monotong In their work the authors require, as equation (10) therein, that
1
Σ 2:
Σ Epp<0
p4 20. 0.
(15)
Observe that this amounts to
3
Σ
14
3
Σ /sl.
(16)
S:p4 <0
However, if any of μ4 is strictly negative, then the rightmost sum in (16) becomes strictly positive, hence cannot be less than or equal to μ if μ = 0. Therefore, the only possible case is when the rightmost sum is an empty sum. In other words, (15) can hold with μ 0 only when μu 2 0 for all i, so that each F; is star-monotone. We would like to remind the readers that our analyses, on the other hand, do not have any restrictions on the individual components.
B.3 Finite Sum Structure vs. General Stochastic Setting
The works mentioned in Section 2 usually assume that we have access to a stochastic oracle that returns stochastic estimator of F. Indeed, having finite sum structure is special case of having stochastic oracle, as each F; can be seen as an estimator of F. One might then ask whether assuming the finite sum structure can help the works mentioned in 2ectiooeooverromee the mentioned limitations. We strongly believe that this is not the case. Recall Theorem 4.1] where we have constructed an explicit counterexample that SEG-US, SEG-RR, and SEG-FF all diverge. Because the set of problems with a finite sum structure is a subset of the set of problems with stochastic oracle, the (exmpler-)example in Theorem 4. also works as an example that displays the nonconvergence of SEG-US, SEG-RR, and SEG-FF in the general stochastic setting. That is, variant of SEG that only modifies the stepsizes and/or the sampling scheme into a without--eplacemmen based one will suffer from nonconvergence, due to the counterexample in Theorem 4.1 It is also true that there are some methods that cannot exactly be classified as one of SEG-US, SEG-RR, or SEG-FF, but this counterexample demonstrates that, unless explicitly proven otherwise, there is not good reason to believe that the existing convergence analyses will be easily extended beyond the assumptions they each based on.
19

---

B.4 On the Claimed Convergence of SEG-RR in the Monotone Setting by Emmanouilidis al. [8]
Recently, paper focusing on the study of SEG-RR [18] has been published. As we have briefly introduced in Table with with discussion Section the authors have established convergence rate (()xk*) of SEG-RR in the strongly monotone setting, using an independent analysis of ours.
On the other hand, the authors of [8] furthermore claim that SEG-RR is capable of finding an optimum in the monotone setting, which is seemingly contradictory this is not the case, as their proof, at least in their AISTATS 2024 version, seems to have flaw.
analyses. We assert that
In establishing equation (85) in 18] the authors claim that the inequality
K K
K
2
R=
holds by Jensen's 's inequality, where G 2 6 is fixed constant. However, Jensen's inequality cannot be applied here, because not only || [-)]1 is possibly nonconvex, but also the weights multiplied to the iterates, namely 1/KG*, do not sum up to 1. Hence, the "averaged" iterate is not in the form of a convex combination. So, even if | [-)l was convex, if we were to properly apply Jensen's 's inequality, at least the averaged iterate should be multiplied by Er 1/C* instead of k- Yet then,
the sum Σk=o 1 G S G=T is bounded above by a constant independent of K, and the right hand side of the equation right above (85) in [8] shall no longer divided by K. Therefore, their claimed convergence is unobtainable.
G
We would also like to remark that the linear decay rate of 1/G* can make the series Lk= Gr B[]] (()))()))) convergent even when B[]] ((+)) [[]] grows exponentially k oo, as long as its rate of exponential growth is less than G. In particular, once their (85) is corrected, there no contradiction with our divergence result in Theorem 4.1
C Useful Lemmata
Lemma C.1 (Polarization identity). For any two vectors and b, it holds that
2 (a, b) = ||a|| + ||b|| - ||a bll
aa b1² 2 -1bb1
Proof. The identities are immediate from ||a + bl]² = ||a|| + 2 (a, b) + |b|
Lemma C.2 (Weighted AM-GM inequality). For any > 0 and two vectors a and b in Idd,
1 |bb||
(a, b)l S 7 ||a||2
Proof. Notice that
2 (a, b)1 s 2 (larbil + ..... laabal)
< na? +
b2 + ...
2
62
1 ||a||
|bb|
?
?
Lemma C.3 (Young's inequality). For any 7 > and two vectors a and b.
||a + b112 (1 (1++) |all (1 |16|1
(17)
In particular, as a special case where 7 = holds that
||a + bll < 2 |al| + 1b]
(18)
Proof. The left hand side of
17 is ||||
+2 (a, b) + |611 Applying Lemma C.2 then suffices.
20

---

Lemma C.4. For any two vectors a and b, it holds that
l|a b112 2 2
||a|| -|b||
Proof. From
18 it follows that
||a|| = (I(a b) + 5 la -bla- + 2|blb
Simply rearranging the terms gives us the result.
Lemma C.5 (Generalized Young's inequality). For any nonnegative sealars .r..... Pr Pr. such that ...... + and vectors a1 axg it holds that
[|p11 + an 11 S p1 || +... Pr. ||..
In particular, setting P1 =... = Pr 1/ and multiplying both sides by n² yields
|a1 +... anll S (11a211
||a,11)))
Proof. We use induction on n. If then P1 1, so there is nothing to show. For the inductive step, suppose that the statement holds for some
1. Say we are given nonnegative scalars Pl,.... Pt41 such that pl +.... + Pn+1 1, and vectors a 01....y an+1. For the moment, suppose that Pn+1 < 1. Applying Lemma C.3 with 7 pa+1 and using the induction hypothesis, we get Pott
d +... + Pa an + Pu+ Pu+11att11
[|praj
+ pran
1 Pa+1
|| (pu+1antill
1 Pn-1
= (1 - -Pn+1)
P1 + .... + 1- Pn+1
Pn
an
+ Pn+1 ||axt1l?
1 - Pn+1
Pi ||a 1| +... Pn | 12 Pn+1 ||a 1
where in last line used that pl + Pr. 1 Pu+1- Now, if pn+1 then must have =.... 0, so the claimed inequality holds in this case also This completes the proof. D
Lemma C.6. Suppose that F is M- M-smooth. Then for any and holds that
M
Fw Fz - (F =)
=||²
2
Proof. The proof closely follows the arguments used for Lemma 1.2.4 in 40 by replacing the gradients therein by saddle gradients. The fundamental theorem of calculus with the M-smoothness of F gives us
Fw Fz -DF()()) 2)11 =)|== = /1/- (F + t(w 2)) dt (w z) (F -z) 2)
$ w| =|| jn
IDF(z + t(w - =)) DF(2)] dt
< |/w
=||
Mt 2|| dl
M
|| =1|
2
Lemma C.7. Let F be a u-strongly monotone operator. Let x" be a point such that Fz = 0, and let n > Then, for any point the domain of and z FF holds that
z²) 2 1 || 2-12 r²2p F F>
Fw, w
2
21

---

Proof. By the p-strong monotonicity of F and Lemma C.4 it holds that
FFw w x²) 2 1 ||0 -2"1'" z²12
= M || - =1F2 - 2=1
11 1| z²12 p 11
so we done.
The following lemma generalizes Lemma 3.2 in monotone F with μ >> O.
21 shown for monotone F to p-strongly
Lemma C.8. Let F be p-strongly monotone L- L-Lipschitz operator, and let z be any point in the domain of F. Then for any < 1] < LVD'' holds that
F( (2 F (1- 2mp4
|F2|22
Proof. For convenience, let us define Because is ju-strongly monotone, we have
F= and 2 = 1 n1F2) 2 FnFw.
1 "1|= =||² S FFI= Fz,z 2)
(19)
= n FF Fzt Fw)
Also from the μ-strong monotonicity of F we get
# ||w - 2 2+1 - Fw Fzt + 1 x+)
(20)
77 Fww Fzt Fw Fz)
Meanwhile, from the L-Lipschitzness of F we have
Fw - Fz 1 < L2 Fw - Fz
(21)
Summing up the inequalities
19
20
21 with weights 2/n, 1/2n, and 8/2 respectively, we obtain
11 2 2|| - = =1²² +
w 1|²)
+ 2
Fw F2
7
3r F - Fz
2 22(F== Fzt, Fw) + FFw Fz Fw Fz)
2
From this inequality, we can exactly follow the arguments used in the proof Lemma D.4 in 21 to derive that
dt 22| =||² +
1 + -|- z+ 11² + || < |2|1
(22)
Meanwhile, Young's 's inequality (Lemma C..) tells us that
: w - +1 - =||²
7 | = || - 2 <
+
Using this to lower bound the left hand side of (22) get that
2np
F2|1
+
Fz + 1| < ||22|
5
remains simply rearrange the terms.
Lemma C.9. Suppose that F; is L-Lipschitz for all 1.... and that F == - F is
ju-strongly monotone with p > 0. Define K. = 4/u and o² = +E F. 1. Then, for any
E ddd it holds that
Fiz F2ll2 (V3(1+ + x2) F2 + v3o.)² 2
22

---

Proof. For any z, w E Rdd as Assumption 3.1 holds with μ > 0, by SchwarySchwarz inequality
p || - wil2 - F= Fw, x w) S Fx Fw] || - -wll,
and as a consequence, ||2 w| - 1/2 Fz Fwol Thus, for any i E [n]. it holds that
F - Fz v 3 Fiz - F22 1| + F2 - F= 1| + 3 F12" Fz 1|
331 2 x=1² 21 FFz - F="11 +
F
L
33 1 +1 | FF=1'==11' F 33
= 3(1 + x²) Fz 2 + 3 F
Summing this inequality over i = ,,.... and then dividing by leads to
3
Fiz- Fz 3(1 (0(1+R)) |2
F
3(1 + x²) |2|1 +30
The conclusion follows from the basic inequality + < (a+ which holds for any a, b 2 0.
Lemma C.10 (Nonexpansivenesss of the EG operator). Let F be monotone L-Lipschitz operator, and xt be a point such that Fz = 0. Then, for any point z in the domain of F and > 0,
|| 1z-nF(2z FF z" 11 = x 11 17 [
Proof. This classical result dates back to the original paper EG by Korpelevich completeness, we replicate the proof using our notations.
29 Here, for
Expanding the left hand side of the inequality stated, we obtain
>| - 1/ F) x" 1 = || ==" =2 - f1),, -²) [|1 F)
==1² =1|2-2*||--2nj 122 F)) 1/F= 2²)
- 2n1² (F(zz - FFF2), Fz) - n²² | - n=F2)11
(23)
For the first inner product term, we have
22 (F(z -1 - z²) S
because F is monotone. For the second inner product term, the polarization identity (Lemma and the L-Lipschitzness of F to get
Fz) =I nF²2) Fz [F(z fFF2) Fx|
< L2 1 |= -
-|
--11- |F ||F(z -]F2)]]
Applying these two bounds on 23 completes the proof.
Lemma C.11. Let (ozo (ba)x20 {Cu and {du (du be sequences of nonnegative numbers satisfying the recurrence relation
bk (1 )x dx+1 + ck
vk2 0.
Then for any it holds that
k
k
k dg +
d +
Σ
b,
<
(1 az)
Σ 0=
cj
1=0
1=0
23

---

Proof. Because aę 2 0, it suffices to show that
&
Eb,
c2) II (1 ail
-x- do II az),
(24)
5=0
(=+1
j=0
as this implies
k
k
Σ
bj
- j=0
bj
II i=j+1
(1 a1+a.)
==0
Σ
(1 (1+a))
de+1 + do II + aA)
Cj
s=j+1
5=0
h
<dd++1+ + do +
Ck
II
[ a2).
f=0
j=0
So, show that 24 holds, by induction on k. For the base case i 0, the recurrence relation tells us that
bo co (1 ag)do d1
which is exactly 24 when Now suppose that (4 holds for some & 2 0. Using the induction
hypothesis and the recurrence relation we get
1++1
66 c2)
II
(1+ a:) bx+1 ck+1 (1 + ax+1)
II
(1 + aa)
0=
#=f+1
5=0
i=j+1
A+1
I bott - Ck+1 - (1 + ax )d841 do
II (1+ag)
j=0
k++
$ -d + do [1+
j=0
This shows that (44 holds also for k 1, and we are done.
The subsequent lemma is technical, but it can be derived from elementary calculus. Lemma C.12. For any K 2 1,
K+2
(K 3)1/3
k2/3 (log k)
(log( K + 3))2
2=2
Proof. Consider the function h(x)) = 2 Blog 2
over the interval [2, K + 33. As
l'(x)
3x 3/ )2 <0,
5/3 (log
h is decreasing. Hence, an upper Riemann sum becomes an upper bound for the integral, so we have
K+2
K+3
x 2/3 (log dr.
(25)
12/3 (logk)
Now consider a function
[1, 00) + R. defined as
g vt3
(y 3)2/3 (log(y + 3))2
dr
2 2/3 (logr)²
Differentiating, we get
2
2
g'v)) (y + (logg + 3))3
+
3(y + 3)2/3 - 3))2
24

---

whenever 2 1. That is, is increasing on 2 1. We then show that g(1) 2 0. To this end, let us begin with observing that
14
10
h" hx) (l/gg)) 320//3 x))3
0,
9 x)2
from which we get that h is convex. In particular, it holds that
J h(z)dr
/ h' (2)))
5
5
(3)
+
dr
and similarly, 13 h(x) dx h(7/2). Thus indeed have
s(1) f h(x)dr dx (log 4)2
42/3
41/3
0.
(log)//()) (7/2)2/(log(7/2)) (log 4)
Recalling that g is increasing, have g (K) 2 g(1) 0 for all K 2 1. This, with 25 implies that
K+2
K+3
(K + 3)3/3
/
2/3 (log 3//g x)² dx
22/ (log k)2
(log( K + 3))2
holds whenever K 1, which exactly the claimed.
D Missing Proofs for Section
D.1 Unravelling the Recurrence of the Generalized SEG in (8 and (22)
In Section [.I] we considered the method where, in a single epoch (hence omitting all superscripts that are used to denote the epoch number for convenience), the iterates are generated following the recurrence
W = 2; -oT;z 21+1 2; wT,
(26)
for 0, I....,N- 1, where each T, are sampled from the (Fi..... F. }. and an additional anchoring step
# NN + Ozo
(27)
1+0 0
performed so that 2² is used the initial point of the next epoch. Notice that 27 generalized anchoring step that incorporates all the settings we are considering, as the versions of SEG where anchoring is used correspond taking 0 O, and the anchoring step (12) that is used in SEG- FFA corresponds to taking = 1. In this section we would like to prove the following statement regarding this update rule.
Proposition D.1 (Proposition
5.1
It holds that
=²
2n
3
N-1
T2 +
a8 1+0 1=
N-1
Σ
DT,
(Z. +
32
Σ
DT, (Tz)
+
EN 1 1
I+ 0
I+0
1=0
OSi<jeN-1
(28)
for some o ((a 3)²).
Proof. Equation 28 immediately follows from Proposition D.2 with (30) giving us the precise
definition of e. To show that ex ((a ()))) we begin with noting that both || = and
I|w -y are of ( + B). because both z, and w, are obtained from zu by performing at most
j updates following 26 Thus, the first term in the right hand side of 33 is of ( 3)2) by
Lemma C.6 and the remaining terms are of O(aa B)33) by the T-smoothness of the operators
F
25

---

Proposition D.2. For any = 0.1..... N, it holds that
1-1
2: = 20
3
Σ 5=0
= + aB
_
DT, (z)) T2
g2
E
(2) t
(29)
j=0
oskojši-1
where denote
E == 3
Tjw,y T, (Z)(2))( zu)
j=0
(30)
i-1
+ a Σ
+ 32
Σ (zo)
Σ
(T wR T.=0)
j=0
k=
Proof. We use induction on i. There is nothing to show for the base case = 0. Now, suppose that
29 and 30 hold for some < N, and write
Zi+1 = 2i - wT,
2: - 20 (zo)( - zo) - (T:w:; - Tiz0 DTi(zz)(w; - -20)
Here, notice that by the update rule we have
we 2; aTi
i-1
20 3
Σ
T,w, af,z
5=0
Using this identity and the induction hypothesis get
1-1
i-1
2,+1 = Zn
- -
Σ
Tz20 + 0.
Σ
DT, (2)
TTz0
+ 82
(20 +,
1=0
j=0
Oskcisi-1
-T (DT:(2))
-13 Σ
Tywg aTizi
1=0
Tiw; Tiz0
DT.(z)) 20)
{-1
i-1
20 B Σ Tiz0 a.
DT (20) (2o) g
Σ
(2)) +,
5=
1=0
OSkcjŚi-1
-T. + (T)((z))) Σ T2z0 + 2 (20) Σ
(Tywy T,z0)
j=0
+ (Z)) (Tiz, T,20) + a,BT, (2))
(T))
-3 (T.. T,20 DT: (20) - z0))
20 - 3 Σ T2z0 + 0B Σ (2))) + Σ
(2)) +
1=0
j=0
OSk<jši
i-1 WT, T,z0) + ( (Txz T,z0)
32 (z))
j=0
T.w: Tiz0
DT, (T)( - 20))
2n 8
Σ
20 aB Σ (20) 82
Σ
(2) + 1
j=0
ock<jši
which asserts that (29) also holds for i i 1.
26

---

D.2 Insufficiency of Only Using Flip-Flop Sampling
Here we prove the following.
Proposition D.3 (Proposition 5.2 Suppose use flip-flop sampling only. In order make 1O)
and (IT) hold, we must choose ni/n and a = 8/2. However, this leads to 1/2 = 27,,, which is the of parameters that fails to make EG+ converge.
Proof. Suppose that we have already established the upcoming Lemma D.4 Then, we can see by
setting / 0 in the result of Lemma D.4 that for (TT) to hold, the following system of equations should be satisfied:
7/122 2n B32
1/ (2a + 1²),
!/2 = 2nB.
Solving this system of equations, we get = =n3, 2n3, and a = 9/2.
For the latter part of the statement the divergence of EG+ with 7/2 2mn, consider the (1 + 1)- dimensional bilinear problem
min max zy
y
whose unique optimum is z² = (0, 0). A simple computation shows that
0 1
Fz
0]
Consequently, for any > 0, the update rule of EG+ with 171 = and 1)2 = 21 amounts to
1 - 21/²
21
z' z - 2n - -F=) =
211
2y7²
2.
follows that
1| - 2²1 =2=1²==
-2"
2112
-2n
x
2n
2n/²
V/
((1 21)² x 2ny) 2
+ (2m (1 )y)
(1 + 41 (x² + 122)
(1 4m) || 2² 11
Therefore, the distance from the optimal solution strictly increases every iterate.
remains actually prove Lemma D.4
Lemma D.4. When flip-flp sampling is used with the generalized anchoring step 27
it holds that
a
Σ DT,(
B²
Σ
DT,
(zo)
1+0
1
OSiejEN-1
20 + 32 n
2,32
Σ (2)
(F.
1+0
1+0 0
Proof. As we are using flip-flop sampling, we have N = 2n, and it is clear that
(2)
DF DF, (2o)
For the second term, as - have
Σ
(2)
Σ
(2 +
Σ
(2))
0
osicjSn-1
ngicjs2n-1
27

---

n- 2n-2-1
n- 1
2n
(2) + Σ Σ
(2))
J=n
1=0 j=2n=
DT2 2n 21-2-1-1(2))
i=0
Σ
DT (2u) +
Σ
D (20)
0SiciSn-1
0SsciSn-1
n- 1-1
(2)) +
ΣΣ
(2)
j=i+1
1= 1=0
DT. (zo)
2
Σ
(z)) +2
Σ
(2)
OSicisn-1
0Sicisa-1
n-1
(2))
1=0
The claimed identity can be obtained by taking the weighted sum of the two results.
E
Within-Epoch Error Analysis for Upper Bounds
All the upper bounds for SEG-RR, SEG-FF, and SEG-FFA this paper are established by following the two steps below.
The first step to decompose the cumulative updates made within an epoch by using the method into sum of an exact EG update and within-epoch error term, which we denote by r In particular, we show that error term p occurring from any of SEG-RR, SEG-FF, and SEG-FFA can be expressed in specific unified form (described in Theorem E.1 This will be the main focus of this section.
The second step is establishing a convergence rate that can be applied to any method whose update can be decomposed into a sum of an exact EG update and an error term that is of the specific unified form mentioned above. By doing so, the convergence rates of SEG-RR, SEG-FF, and SEG-FFA will automatically follow as special cases of the general convergence result. This step will dealt in Appendices F and G
To this end, for any of SEG-RR, SEG-FF, and SEG-FFA, let us decompose the cumulative updates made within an epoch into a sum of an exact EG update and within-epoch error term r. as
l++ 20
z m (
m F2
The quality of the method will depend on how small the "noise" term p is, as the noise will in general hinder the convergence. As mentioned above, it turns out that, regardless of the method that is use, the noise term can bounded in a unified format, as follows.
Theorem E.1. Suppose that Assumptions 3.3 and 3.4 hold. Then, for each of SEG-RR, SEG-FF, and SEG-FFA, there exists a choice of stepsizes that makes the following hold: for an exponent that depends on the method, there exist constants C, D,, V,, C2, D2 and Va. all independent of m and such that the error term kk satisfies a deterministic bound
|| S Thn&C [| + n D, Fz k 2 + V
(31)
and a bound that holds on expectation
E
|
2
m
2a 20
n
C2 Fz!
+ m n 2a
D2
Fz R
+ mh n
2a V2.
(32)
Furthermore, the exponent is 2 for SEG-RR and SEG-FF, and a 3. SEG-FFA
28

---

In other words, SEG-FFA has an enror that is an order of magnitude smaller than other methods. Thus, is now intuitively clear that SEG-FFA should have an advantage in the convergence. The proof of Theorem F.1 is quite long and technical, so we defer it to Appendix
Within the remaining of this section only, although it is abuse of notation, for convenience will write F; to denote the saddle gradient of the component function chosen in the zh iteration. More precisely, for indices i 0, ; n2 we denote Fr(e+1) by F; Similarly, in cases of considering SEG-FF or SEG-FFA, for i 2 n we denote Fr by F.. Also, we omit the superscripts and subscripts denoting the epoch number & unless strictly necessary, as all the iterates that we consider will be from the same epoch.
Let us reformulate the update rule
8 into
Wi = 2; - Fi
(33)
2 F,
Note that ç = 1/2 for SEG-FFA, and 5 = for SEG-RR and SEG-FF
E.1 Auxiliary Lemmata
For j .,..., 2n we define
j-1
9j = Fizo.
(34)
6j = 9j - j jF zo 1l
(35)
Σ 8,
(36)
V 8
(37)
We set Eg V = 0, as they empty sums. Notice that 8, is random variable that depends on the permutation т. Meanwhile, by triangle inequality it is immediate that
||وو|| S i Fzol + رj.
and by Young's 's inequality it holds that
1g, 12 < 2j² Fz 122 + 26..
Lemma F.2. For any index i 1, it holds that || zoll s 17 (1 + Ln) ||g:||
2-2
(38)
+ 1 (2c + 2E + 2 Σ
(1 n1 En 13) 1lg
2=0
lww zoll < En119++1l || + En ((1 - + 2mL L1² |
+ n1( EnL (2EmL + 2
Σ (1 m/ + (3)
l|ge+1l
(39)
Proof. By the fundamental theorem of calculus for line integrals and the update rule
33 we have
w. 2; Fi2
Z; F11 Enn - -F:20)
z, Fn En 1' DF + t(zz 20)) dt (z, 20)
29

---

and similarly
-++1 = 2; FFWW
= F2 17( (: - Fiz0)
2, F - 11 ! DF - -((u; - z0)) dl (w; 20).
Hence, by defining
A = S. (F + t(2 -20)) dt
(40)
B B S. DF + lww; 20)) dt
the update rule can be rewritten using these quantities
w; = 2, - F, A1,,(2 - 20);
(41)
Zi+1
Fi 11 [B;(w;; 20)-
(42)
Subtracting zo from both sides of (4)) we get
w; 20 2, 20 Fn - A, (z+ 20)
(43)
= (I Ai) (zi 20) - Fi
and plugging this into
42 gives
zi+1
20
2i 20 =0 - nBB,(w; - 20)
2 20 Fi nB. ((I EMA,) (zi 20) F(0))
(44)
I n B: ² B:A:) (z: =220 17 (I -1n Fizo.
For convenience let us define
n B.A.:
P Ce+2Ce+1
and P., I as it denotes an empty product. Observe that for any j we have
||C,| = | I- BBnBBB E B, S + nL + L2.
(45)
Also note that for any E it holds that
(I - B1+1) - C4+1 (I - Bi)
= (1 - -nn - (1- BBBei1 + Enj Aet1 (I - Bi)
= [En( + BB) - -57² B:+1(AA++)) + B,) + En Be+1Art1B
and hence
[[ - (1)ea) Ce+1 (I - Bt)l < 25y + + 1
(46)
Unravelling the recurrence relation
get
x;+1 2p = Cz - 20) 77 (I B;) F,
-C-(---( - 20) - 1 (I Bi) ( - nn - (I
B. F,z0
- 20) 11 Σ = -
Pie (I - B)) Fi20
{=f-1
= - 20) - (I - B.n 17 Σ
P.e (I - Bn F.
E=i-1
= -
20) nn Σ
- BnB Fizo -I-
E=1-2
= PP,-1(Z0 - -20) -1 Σ
p.. (I - Be) Fizo
0=
30

---

and therefore
20 -1)
(I Fizo-
(47)
6=0
In order to compute the bound for || =o|1, we summation by parts to get
1-1
(20 - zi)
Pi (I (T Fiz0 Σ
E=
P (I - -(nB:-1) Σ
Fizo
t=0
Σ (P-11 -e -P -I-11((-((BB)) Σ
Fiz0
1=0
(I - Bn B-
Σ
(PI-1441(I- -n - P.-1, (I -nn ge+1-
t=0
Here, observe that
Pi-1841 - (1+41B PI-
= Ce+2 ((I EnB(+1 -I-
so by using 45 and 46) we obtain
P1-1e41 (I (n) P:- (I Bt)
I ( 2 L2 + + (1 + nL + En L3)
Therefore, conclude that
i-2 ||2 - zoll (1 + EnL) 11 (28 2E + 2²2²
Σ t=
(1 + nL + +
|
Meanwhile, substituting 47 back to 43
gives us
W: 2a F,z 1)
Σ
(I- EnA,) P:- (I- Fizo-
(48)
For < i let us define
: (1- P Bn)
= (I ( C,-1C,-2... C442 (I BnBi
and for convenience R. == so that (88 can be rewritten as
En [20 w:) = Σ R..
(49)
t=
Applying summation by parts on the above, we obtain
i-1
1
ET (zo - w.) = Ri,
F2z0
Σ
R Rie)
Σ
F,z0
t=
1=
1=0
g++1
(R
Rgt)
and as a consequence we get
1 w zoll S
||g +
R R.ell
(50)
En
2=
31

---

It remains to bound || RR,e+1 - Ri,ell- For the special case where 8= - - 1, a direct computation leads to
B -1 -- B1)
-1-5- + + - EnÍ A,B
and thus we have
| R || (1 (1- - - 2n + 1.
(51)
For the other cases; that is, when E < 1, we have
R R,, = 5-1 (I - En4,) C,-
C422 ((I - Bt4) - C4+1 (nn
so by using 45 and (46) we get the bound
[R - R S 5 (1 + EmL) (2En) + rE + + E
+1+ 1-12 (52)
Applying (51) and 52) on (50) gives the bound for ||w; zoll-
Proposition E.3. Suppose that SEG-FFA is used, 1) < nb. and let v == 1 + we have the bounds
1
1
Then for any
2n
i -,....,2 2n
|| - -zoll s
mu0i +
FFzll + +nvs + 1"² Lu² Ei-
2n
1 + ++222i++ + US -2 -
2 20441 + 17(222 -1) 1)
1|w; =zoll -
1
| +
8, + 11² LIde2
2
n
2
(372 (i + 1)²
317² - 1)222
12'86 i(i - 1)2(2i -11) || 12
1w0, zoll2 S
2
2
n²
311²
32 -
1)2 -1)²
0 6njive - 1) V:-1-
0/41
2
n²
Proof. Using elementary calculus one can show that x + (1 + 2x2 )rr increases on x > and is l
bounded above by e. Hence for all 0 <
<
i S 2n we have
2 6-8-2
(1+NL+
nL
S E2
2
2n
Applying the definitions
35 and (36 on (38) and then substituting & 1/2 we get
nL
nL
2 2--2
11²1?
i-t-2
||ا zoll S
+
||9.l| + L [1
Σ
1 + nL +
|g(+1l |I
2
2
2
E=
i-2
qp [i] + 02) n7² Lv²2
Σ
e²
((1 + 1) || + +541))
(=0
S (i + 0 + n
F20 I + + -
2n
Similarly, from
39 we get
T2222
lw =zoll < |1 +
? 2
1 2nL +
|19.1|
2
1+ T T. (1
nL 3i-2
L2
i-t-2
Σ
1 + nT..
1g
2
S "1 (i + 1) |Zoll + 81+1)
+ 71
1 2
1
(i (illFzol) +5))
2
2
n
2n²
i-2
+ LV3
Σ
2 ((e + 1)
Fzol| + 8c+1)
8=0
< 7 (1 + 2
"
F Fzoll +
nu²e2i(i- -1)
||20o|| |l + " 54+1+
+ n12u22 1)
-1)
5, + 1 2u3 EE
2
2n
2
2
32

---

Finally, applying generalized Young's inequality on (39 we get
3n²
3r²²
1
2
110, z0ll²= -
9
11
+
1
2n
|1a.11
4
4
2
nL
3 2-2
n
6-6-2
2
+
1
+
1+
lgeezal)
2
2
Using generalized Young's inequality once more the last term gives
n
3 2--
6-8-2
2
m
i-2
2
3 L 1+
Σ
1 nL +
lsee-il)
33
3
11
2
11
v
et
1)
1-2
g
n²
Plugging this back yields
3
4 |9++1|1 12+ 31/²
1/2122
11:.112 31 -1]
1-2
| z0l12 -
(1+2nL+
Σ
11 11
4
2
n²
1=
(2 + +1)² FF + 20% )) + 37²²
(2v² - -1)((22) |zoll + 20
$
4
4
37220c41 1) 2-2
+
(2(E + 1)3 1 + +20%+1)
n²
t=
372
372
< (i+ 1)a || 12 00+1)
-1)² ( + 63))
+
2
v2 e(i- (()- 1)
6172 1) 11
|Fzol| 2 +
n²
n²
Now the claimed inequalities can be obtained simply by rearranging the terms appropriately.
Proposition E.4. Suppose that either SEG-RR or SEG-FF is used with a = B = nt. and let
<
1
; == 1 1. Then for any i = I,.... 2n 1 we have the bounds
16ni21 -1) || + nps; + 2 LE
||2 - zoll 5
nii +
LE
1 + it? + 160 (af((d11)) 1) | + n6:+1 + t - 1)o; + 32m² Li E,-1,
1w0, zoll S 17
+ 6n7² (1 + D) 1
1024n i(1 - 1) 1)2 11 -1)
l|w; =00l S
1)2 (in2(+11)
+
||
n²
n²
6n² (1 + D)2
6144n 1) V 1
+ 66772
+
n²
n²
Proof. One can verify that x (1 + 4 )a increases on x 2 3 and is bounded above by 4/3 4.
With noting that (1+7+) ) 3 < 4, (1+ + }
49
< 4. and
+
1 +
< 1
1 32
T6
whenever x 2 3, we see that for all 0 < l < 2n it holds that
(1+ + [ i--- <
1
1
+
2n
S 4 = 16.
n
n2
Also, we have
1
+ 2n
22+
1 + 12 22
n n2
33

---

Applying the definitions 35
and 36 on
38
and then substituting & = 1 we get
|| zall S 17 (1 nL) |1 + 2f (2 24 + 2 L23)
nL n 17 12 i-e-2
11
i-2
S n (i Fool + 6.) + 27j² LE
Σ
((( + Fzul + dx+1)
1=1
S nの Fzol + 6,) + 16q i(i -1)
LE L; 11 Fzoll - 3
Similarly, from 39 we get
||1; - - 17 gi+1ll 11 17² (2 + nL) |1911
i-2
+ 1 Tn) (2 + 24L + 17 L?)
Σ
(1+ 1==n+1223)+ 1
==
| + 61+1) + 17 2 7 1)
+)
S
(i F + +,)
n
n
2-2
+ LD LD (26²)
(6 Fzol + 5z).
1 + 1D²) Fzoll + 16ni i(i i(i-
Fzoll + no,+1 + t - 1)6; + 1321"L0
Finally, applying Young's 's inequality
(39) we get
1 317² (2 + nz)²
||w, =zoll² S 3n/² 19
||
n²
+3 1/T((1 + nT) (2 + 2nI + 1.2
(1 + +1+
e-2-
|1
t=0
3rd (2 + n1)²²
2mp3
i-2
< 37 |g+1
|| +
16 19
n²
t=
Using Young's inequality once more on the last term gives us
32m
3072,)
3
19ttall
Σ
l1 11?
n²
t=
Plugging this back yields
372 (2 (2+ + nn)
11g:11 + 3072n) (i - 1) 1-2
lww, - =zol? s 377 11
Σ
19 12
n²
n²
8=
6n7² (2 nL)²
S 617² (i+1)² | 10 + 6/+1) +
(12 FF + 82
n²
6144172780i 1)
i-2
+
Σ
1)² |F + +82+1)
n2
2=
(2 F| + 57 6n7² (1 + D)²
S 61² 11) 1)2 Fzoll + (
+
n²
- 1)? -1) F
6144)
V V
n²
n²
Now the claimed inequalities can be obtained simply by rearranging the terms appropriately.
Let us now derive the upper bounds for the quantities related to 6, and E,, defined respectively, using the upper bound of the variance of saddle gradients
335 and 36
34

---

Lemma E.5. For any j = ...... 2n, it deterministically holds that
6j npp Fz + a).
(53)
Proof. For any set of indices I {O,.....t 1]. by Assumption 3.4 holds that
Σ
Fizo - Fzoll
Fizo Fzoll² 2 nlp || F Fz + to)².
EEJ
Hence, for any j 1 ................................ have
99 --FFFoll
Fiz0 j
3 1=0
Fizzo Fzol 1
I jm(p || Fzoll + t0)²
1 (p Fzol! +0)²
and for any 1,..., 2n we have
j-1
|9g j F2ol2
Σ
F,Z0 + Σ Fi20 jizzo
F,50 (j (-nn) Fz0
(54)
Pizo - -(j -ij- ([-n)) Fn))
i= 2n-j
$ (j n) Σ
F120 F2ol1
S 2 F +0)
Therefore, in any case we have
||9, jF <
+ ta)²
Taking square roots on both sides gives us the desired bound. Lemma E.6. For any j = 1.... 2n, it holds that
p(p
F Fz
+ to)
E, 10
(55)
Proof. If n = 1 then the left hand side is always O, so there is nothing to show. So, we may assume that n 2 2. Then, for any 1,...,P3 n, using Lemma in 35 we obtain
1 9, F
n2 n-j
E
(p F + to)²
j(n 1)
Multiplying both sides by j2 and applying AM-GM inequality leads to
E, [gg, Fz < j(n - j)
1 (o Fzoll + + < 4(n (pl
n
Fzol| - -0 <
n (p | + +o)²
2
Meanwhile, for j = n + 1,..., 2n, following the first few steps in [54h we get
1g, - =200
Σ
Fi (j - F
2nn
35

---

Here, once more applying Lemma 1 of [35,, we get
n-1
E, |وg - - FF B,
Σ
Pi20
(j 1.gnn) n)
i=2n-
(j - n)²E, Ey
Fiz0 F20
T3 2=2n
n - (j - n.
S n)3
(j n) 1) (pl Fzoll +0)²
(j - (2n 1)
(pl Fz + +o)²
Using AM-GM inequality the last line gives
E,, [gg, F v (j n2 5) (p Fzol +o)² S 4(n - 1)
n²
(F11F22ll+0))
"1
Fz +
n
Thus, for any case, have (55)
Lemma F.7. For any k, E {0, 1, (...,,2.,,,, 2n), it holds that
kEn(p || |zoll + to)²
E, EgE <
(56)
Proof. Expanding the product ΣgLe and writing in terms of d, we get
k
ΣgEr
Σ
8,
5j
i=1
j=1
8 83 + 63 :=1
j=1
2
where the last line follows from the AM-GM inequality. Taking the expectation with respect to and using the bound from Lemma E.6
we obtain
E, En
5
E
(0 + B, 1o,
i= 1=1
a(p Fzoll + +0)²
n(p | + to)²
2
2
i= j=1
kEn(p
Fzol
+ o)
which is exactly the claimed.
Lemma E.8. For any k, l E 10,1,.... .n.), it holds that
k(k + 1)E(E
1)n(p
Fzol [
+ 0
E,
Σ
(57)
8
36

---

Proof. Expanding the product in the left hand side of (57 and applying 56),
we get
Er
Σ
Σg i=1
Σ 5
EE,
و
E, زز
i=1
ijn(p | +o)²
2
k(k + 1)e(E+ + 1mm(p F zoll + t)²
E.2 Upper Bounds of the Within-Epoch Errors
The full proof Theorem F. is quite long and technical, so we divide it into several parts. First we show that (31 and (32) holds with 3 when SEG-FFA is in use. Then show that Theorem E.] also holds for SEG-FF Appendix E.2.3 and for SEG-RR in Appendix E.2.4
Throughout the remaining of this section, we always assume that the variance of the saddle gradients satisfies
E.2. Proof of Equation (31) for SEG-FFA
In this section we prove the following.
Theorem E.9, Say we use SEG-FFA. Then, long as the stepsize used in an epoch satisfies rj <
w..
it holds that
|r|| S n Fzoll + n/'n
D
I
F F
n7"n VIA
(58)
for constants
1
2c
6 + c²
CIA 1
1
15p
(59)
2
3
83
24c
243
DAA M
+
+ 27c
(60)
5
16
244
VIA = Mo²
27e
+ 15L
(61)
16
We first list the intermediate results. The actual proof of Theorem F.9 is in page 43 at the end of this section. Proposition E.10. For using SEG-FFA. the within-epoch update x² as given by 12 satisfies
z² Fnn Fo) +
where we denote
= nn (Z0 F 20) - F n2=1² F((o))(())))) Fio
(62a)
2n
F, - F2 DF, (20)( - 20))
(62b)
1=
+
DF DF, (F) Fiz0)
(62c)
+
1
DF,
DF,(2z) (2u)
Σ
(F FąZ0)
(62d)
2 ==
k=
Proof. Setting a n/2, B = 1), and
1 in 28
we get
z 20
2n
Fzz0 + ? 2n
Σ
7 (z)
+
Σ
(F)
1
E2n (63)
2 1=0
1=0
ogkej$2n-1
37

---

where Enn is defined as in 30 Recall that F; = F2n-1-; for all i = 0,1,..., ,2 - 1, and moreover,
Ei F. = -
ii=n
2n
F. =.F. Thus, the first sum in the above is equal to 2n zo. and the second 20 For the last sum, observe that
sum is equal Σド= (20)
Σ
(2)
Σ
(20)
E
(z)
Fozo
0ckcjS2n-1
ockejEn-1
nskeistn-1
Σ
(z))
0sk<n-1
nS152n-1
Σ
(2) +
Σ
(2 Fi.0
OSkejsn-1
n 12k3-20
Σ
(z)
0Skšn-1
n- 12/20
= 2 Σ
(2)
Σ
DF, (zo) (zo)
j=0
Hence, 63 is equivalent to
q n
(20) + 172
2 2g m F2o
Σ
(z)
E2n
2
1=0
05kcj52n-1
20 Fm + 11
DF P220 +1²
DF
E2n
n-1
n-1
1
= 20 - Fn + 17²
Σ DF (20)
+ = C2n
2
1=0
i=0
20 Fz n22 DF Z0)
F
62n-
Observing that the terms 62b 62ch
and 62d add up to jezn completes the proof.
Proposition E.11. Suppose that n bound
nL. and let 1 + 2n Then the noise term satisfies the
1.
1
20²
4v + e²
||||| s 8 L2 Fzoll
1
+
2n
3
(1
16ve 4
+ 11 n M Fzol1
+
4v
+
2
5
3
4 2n-2
Ven + (20²- - -1)2 2n- +
Σ j&,/z
8
n
1/² L L +1)
L22L222 + LLe
2n
11
L3333 e
2n-2
+
Sin +
+
(2n - k - 1)24-11
4
2
2
Proof. We bound each line in equation 62 For 62a) we use Lemma C.6
to get
wMM
| - F0) - F 20 + n2 DF 5
|1-
2
n²n M
|F
38

---

In bounding the remaining three lines we repeatedly use the bounds obtained in Proposition E.3 will also use the following bounds, which follows from (35 and Young's inequality:
We
7
7 2
W00 zoll
|
|l
-
Fz
2
Ww zol1²
n72
1
1|
-
"
|
F 2|
17 8P. 2
4
2
For 62b). observe that Lemma C.6 gives us
M
1F F, 1 (z))( - z0)ll -
Iwj
zoll
2
Thus, by using the bound obtained in Proposition E3
we get
2n-1
Σ
Fj Fjz0 - (z)) - z0))
-x0)
ド=
1/ 2n-1
Σ
|| 1 F,z0 - DF, (F0((2) -z0]
1=0
M 2n-1 1
Σ
(w-- 2011
4
/=0
MM 2n-1 1
3//2 + 1)2
3n02 -1
P9 1 -1)
+
|| F 12
4
2
2
n²
j=1
M
2n-1
Σ
3r
2
8
j+1
+
3172
2
- 1)2
03
+
6nivact(j 1) 1
n²
j=1
n
+
1|w0 - z0l1
4
nM
17
n1 + 21 + 4n)
3n²
12(222
1)2n(2n 1)(4n - 1)
4
2
2
n2 1)(2n - 1)m32n² -42n + =11)
|F
5n
31 M
3
1)2
3m M 6 ca 2n-1
(vnn 2n
-57)+
V 2n
Σ
(j 11)1)
8
2n2
M
|Fzol12 17
87
4
2
2
(v² + (2v² - -
16ve2)
F Fzull2
5
317
M
317 M M2 - 1)3
3 De
2n-2
U2 +
V2n-1
8
8
2n1
16ve |
31
10 2n-2
S
M (40 +
+
Vzn + (2u2 - 1)2 2 2n
+ n²
2
5
8
1=1
where along the derivation we used the inequality
i 1) 1)(32n - 42n 11) S 64n
which holds for all n 2 1. From now on, we will keep using similar techniques reduce the exponents of vs without explicitly stating the inequalities used, but recovering the inequalities that are used should be clear from context.
39

---

For 62c we use L-smoothness of F,, and also the fact that it implies [IDF) - L, to get
2n-1
11
DF,
(20) (Fzz) F)20)
j=0
2n
71
[DF] 20) ||
F2zol
4
22
2n-1
|| zoll
4
j=0
22
2n-1
nujj + n/222 11)
Σ
|| + nuōr + (
4
2n
j=1
11
mpun(21 (2n - 1) + 2 1)(2n 11)
|F
4
1 L'y 2i
17 v² 2n-1
1i-11
n2
26
1
TT
2n-2
1+
|| +
E2n-1
Σj.
3
4
By the same logic, each summand in 62d with j can be bounded
j-1
(z))
Σ (F.W
Fozo)
k=
< (DFF
Fg - F1
k=0
1-1
< 1,2
Σ
||w03 - zoll
A=
< 1
|| + ',,))
2
vše2k(k -1) ||Fzoll
+ 1
1 1+ 2v²k
n
j-1
7/222 - 1)
+ 2
7 6x+1 +
5z + 7 L
2
A=1
112
7L?
(j-1+ - -1) 1)+ Je (1)]--)(j-- - 2) || F z
(1) Fz + 61) +
2
2
3n
nL
(E) - -8)+ (22 1) E + 133
Σk-1
2
2
3ejiij -1)(i -2)
j j0 1) +
||Foo||
2
3n
+ nI
- 1)
j-1
E, +
Σ, i- + 7 13,30
Σ
Eイ-1
2
2
k=
40

---

and when 0 the sum with respect to & becomes an empty sum. Thus, 62d in total satisfies the bound
7 2n
(2))
Σ
FR
Fszo)
2
1=0
k=0
2n
1-1
11
DF
Σ FR - Pozo)
2
1=0
k=0
L
2n-1
jiv22(( - 1) 12e2j(i - 1)(j -1)(i -2)
<
4
3n
j=l
112
2n-1
nn1²2 Sij T/L22222 - 1) -
i-1
Σ
1 12 Σ
ER-1
j=l
k=1
11
4v2n(n -1) 1] +
vs - 1)(2n
1) - 3)
(2n 1) +
|
4
3
S
17² L2v2 1) 2n-1
Ej-1+ n/'L3vZEe j-11
Σ
Σ
+
Σ
Σ
Ek-1
1=l
k=1
17 L2
3
2
F
12
2
3
3
+ 3
L
2n
1/¹ L2
1)
2n-2
1 2n
2n
Dj +
Σg
Σ--1
2
f=1
j=1
k= j=k+1
+ e2
I I,2
|
3
2n-2
1
3
2n
+
2n +
Σ
+
Σ
(2n - k 1)
2
2
j=1
k=
Simply collecting all the inequalities and rearranging the terms leads to the claimed bound.
Before we proceed, let us write
3 M
4
2n-2
X1
Uen + (2v² 21
Σ
(64)
n12
j=1
TTT2(v+1),
1T2222211 nTee)
2n
T/?
2n-2
X2
E2n-1+
Σj +
Σ
(2n k:
1)E
4
2
(65)
so that the bound on ||>|| obtained in Proposition
E. can be written as
2ea
4u + e²
||| < 1 | F
1
+
2n
3
(1
16ve 4
(66)
+ + AM Fzoll
+
4
2
5
+ + X2.
41

---

Theorem E.12.
Suppose that 17 < satisfies the bound
1 ni and let ==
+
1.
Then the noise term deterministically
2n'
|r|| S 12 Fzzll
1
(1+
2e
+
4u +
e²
+ +10vp)
2n
3
3
1 M F zoll
1
+
+
16ve
o² (30* + Bu²et))
2
5
n Mo² (3v"
+ S
+ 10
Proof. From (6). 37). and Lemma E.5 it holds that
Σ
8, S jn(p F + o))
(67)
3
V = Σ
8 S jn (p F + +o)²
(68)
i=1
Plugging the bound for V into 664
we get
3 M
2n-2
X1 <
(p F + +0)² + (2x² - -202-1))(2 (2 ()n
Fzoll +o)² + e Σ
8
31 M
(2n + (2v² - -1)((2n +
4v8e4
(n 1) - 1)m 3)) (0 Fz +0)²
8
3
3r
32
4v3 +
(o Fzoll + t0)
8
3
n
(
F + +02²
(30' + Su3E
2
By Young's s inequality, holds that
+ t0)² (pl || F Fzoll
S <p21[Fz)) 2
2
from which we get
X1 S p Fzul Meanwhile, plugging the bound for Σg into 665 we get
12 (3r" + Sy3e + 1n Mo² (3v* &v²et).
(69)
X₂ S (22 + 1)
(2n 1)m(e |Fzl| +o) L²² (1 + Lee
2n-2
jn(p Fzoll +
2
1/th L3 2n-2
(2n - k - 1)(k - 1)m(p)) (( Fzol| +
2
k=1
LL2 + 1)
(2n 1)n(p |F + 122 +
(n 1)(2n - 1)m(p) || Fzoll + +
2
1/ L3'330
(-3 11m 12n + 4n²) n(p || +a)
2nLe²
<n1² || FZoll + +o)
n² + (1 + nL m +
n
3
(1 +1
2²
2ea
$ <n Fzol +0)
n
3
where in the last line we used that 1) <
Because the inequality
n..
2
26
+
+
10v
n2
n
42

---

holds for all n 2 1, continuing from above we obtain
X2 S 10vT) n. L2 (p F +
(70)
Σ 10 n. I p Fzol + 10 2
Rearranging 66 with applying the bounds
69 and 77 gives the claimed result.
Proof of Theorem E.9
As 2 1, we notice that I/n < 1 and v S 3/2 where 2n
following
the notation of Theorem
E.12 Then the bound 58 immediate from Theorem E.12
E.2.2 Proof Equation (32) for SEG-FFA
In this section, we prove the following.
Theorem E.13. Say we use SEG-FFA. Then, long as the stepsize used an epoch satisfies aE it holds that
E
|||]
20
I In'n
C2a
F F
+ n D2A F Fzoll* + n7 V2A
(71)
for constants
2e
6 6
2
C2A == 4IAa
+
+
+ 36ppe
(72)
3
3
[83
24c
243
2
D2A = 4M²
+p- p"
+ 27E
(73)
4
5
16
243
2
V24 42
+
27e
+
144
(74)
16
Proof. The bound is then immediate from the following Theorem E.14 and D & 3/2 for v defined in the statement Theorem E. 14
2 implies 1/a <
Theorem E.14. Suppose that 1l T and let == 1 27 satisfies the bound
Then, expectation, the noise term
((2))
26
4v +
e
2
36p²
E ||||
1|
20
S
n L F2oll2
+
+
2n
3
3
n
(( + 4v 4 + 16ve
2
pa (302 8)²
+ 4n 'n 2
|
+
5
n
+ 4n'n² (3v* e)² + 144c 1
Proof. Notice that, when conditioned on 2g. the only source of randomness included in V is the random permutation selected for the epoch. Hence, we can use Lemma E.6 to get
jn(p
F +
E
2o]
20
E
18
øo| <
Applying Young's 's inequality on (66) we get
1
20²
4u + e²
|||| < 4n7"n I
F 2
1
2n
3
16ve
(75)
+ 4n) , M2
Fzull'
+
4
+
2
+ 4x? + 4X3.
When conditioned on Zp. the first two lines are not random quantities. Thus, it suffices to derive the bounds for E [x? zo]. 2,
43

---

Recall that the bound
69 on X1 holds deterministically. Hence, it holds that
E { zu] = X1 1 Mp² F (3v² E) n/'n² Mo? (3rr + 8y² 20)
= = M (3v* c) (p² Fzoll + 0² E [X1 so].
Now, to compute E [X zo], we apply the linearity of expectation on
64 to get
E [X1 zo]
31 M
2n-2
E [2 20] + (2x2 - 1) E 24
20]
Σ j B VV zo]
n²
3
(p F + +0)² -0) - 1)n(p1 || | Fu + +0)²
4v 2n-2 jnn(p Fzoll + to)²
+
2
n² j=1
2
3
2nn² + (2v² - -1)2(2n² - m) 20 1) - 1)(4n -))
(pl | || + +o)²
3n
3
2n/n2² + e6
(011F20ll + to)
3
M( |Fzoll + o0)
(30" + Su²c").
4
Young's 's inequality gives us the bound
(o F 0z S Fzo12 o2
(76)
which, with the inequality derived above, leads to
[ z0] S n M
(30* + & (p'11Fzoli + 0²)
2
As consequence, with using Young's inequality once again, we obtain
M²²
2 (3w* + Su'ed)² (0² Fzoll + 02) 2
E [ zo] S
(77)
S n 2 (3v + su²cd)² (0* |Fooll + +ot)
To get the bound of EE [x]] z0]. we begin by using
2n - k -
nLv k 1) -
1
+
2n
k:
k
k
1
1
+
+ $
2,
4n3
n22
71
4no
2n2
11
which holds for all 1 5 k < 2n - 2, to
65
to obtain
X2 < ( + 1)
133L2
+ mLe
2n 2
6²
2n-2
2n
K
Ezn-1
Σj +
4
2
2
11
j=1
k=1
TT, +1)
+ nIee 11
2n-2
2n-2
Egn-1
Σ
Eg + 17 Live²
Σ
Σk-1
4
2
k=
17a
L22 + 1)
17 122L2 (1 + 2
2n-2
22n-1 +
+n 3 veve?
Σ
2ij
4
2
j=1
(2 1)
2n
E
+ 31 I2e
Σj.
4
j=1
44

---

Then we directly square both sides and expand them to get
2
1 (V + 2- + e2
X3 v
Σj
17 L (v + 1)²
23 2n-1 + 91) L
2n 2
Σ
D
3r L
+1)
2n-2
22n Eg.
16
2
j=1
Here, using Lemma
and Lemma E.8
on the right hand side leads
E [ zo] - n L + 1)2 2n
() Fzol
|| + +o)²
917 L e2nnnnnnn2222))
1) +o)²
32
3 L (v+ 1)
2n-2 jn(2n 1) +0)²
2
1=1
T0 + 1)2n(2n - 1) F + to)²
In 22 1) [ooll+o)) +
32
37 + 1)m(n 1) 1)2
Fzol| +0)²
1/ 18 (p) + o0²²
91/8 LA (2n 2)²(2n 1)2 F + +o)²
+
2
8
+ 1
1) Fzol + 00)²
n3
Det (22 22 1)2
= =
+ 6e n ( n 11) (p (0 12 +0)²
8 < 1 (p) Fzoll =
As a consequence, with using 76) once again, we obtain
E
X3
2o]
"6 (p² || +
(78)
Taking the conditional expectation on (75). applying the bounds (77 and 778 and then rearranging the terms leads to the claimed inequality.
E.2.3 Upper Bounds of the Within-Epoch Errors for SEG-FF
Theorem E.15. Say we use SEG-FF with epoch satisfies 1) < T holds that
3 1/2. Then, as long the stepsize used in
|r|| S 2 O Fzoll ll + + D F F +
222
E ||]
Zu S sn''n C2F |2ull? + D2F
Fzull I|
V2
for constants 1FF, DIF, V1F. C25, D2F, and V2 to be determined later in
81 and
82
Proof. As have discussed in Section 5.1 already know that aiming to achieve Onr²)) error without anchoring is futile. Instead, we show that error of magnitude (11²) is possible with the chosen stepsizes.
By Proposition
D.2 and Lemma
D.4 we have For any = 0, 0, .N, holds that
Z2n = 20
11
2n
T,z0 +
172
2n
(2)) +
n72
Σ
(2) + E2n
j=0
j=0
05k<j52n-1
3n2
DF (2)() Fjz0 + 72
20 1)
F,20
DF, (zu) (2)((z))FFF))) FizO + C2n
j=0
j=l
2/2 n Σ j=1
1/2 Σ (2) Fiz0 + 62n
= 20 - MnF 20 + n2 DF 20)
Fzo
DF, (2))
2
45

---

where we denote
Fjwy- F2z0- DF; - =0))
62n =
i=0
(79)
1 2n-1 1
" 2n-1
j-1
+ Σ 4 j=0
(2) - Fjz0) + DF, (zo)
Σ
Σ
Fg Fazo))
4
j-0
km0
Comparing 22n to a point that would have been the result of a deterministic EG update with stepsize v7n we get
Z2n (20 - fm m)F) - rfnF(20 -
F0 + +12nn (F Fzo + 62n
11² n DF, (2)
11² 2
Σ (2)
Riz.
j=1
(
Let us define
== nnF 7mFF2)) Fm.F22 20 + D Fzo E2n-
(80)
Noticing the resemblence between (62) and the equations in 799 and (0). we can repeat the
same reasoning used for Theorem E.9 and Theorem E. but with replacing the bounds given by
Proposition E.3 to those in Proposition E.4 (and plugging in 1/2 in place of 1j in the statement of
Proposition B.4) conclude that
|| S n C1A || 20 + n DIA Fzo 11 17 17²n2 VIA
E
20|
S n | z0 12 + 178 n D2a F Zo || + 7 V2A
for some constants ČiA, DIA. ViA C2a. Dea and V2A. Mcanwhile, we also have
n
1/² Σ
DF (2)
(20)
DFF
Fiz0
(+)
n2n DF (zz)FFz
112
DF Fjz0
2
4
j=1
n2
1/²
[IDF(
+
Σ
DFF (20)ll |F
2
4
j=l
n2nn
772
L 1|
+
L
Fl - Fzoll + F
2
4
1=1
112n22
+ +n)L
12L Σ
Fzol ||
+
F2z20
Fzoll |l
4
j=1
1/2
1/2
T
n
< 172n2 L | +
Σ
|1
Fzol
Σ
4
j=1
n²
(p
Fzul +
4
where in the second to the last line we used the Cauchy- Schwarziinqquliin Therefore, as 17 S 1/nL, we conclude that
|| 12n - (zo mmF (nFF2)))l S C Fzol + 1 D1F 1| 12 + 1f 1 2
for constants
CF = L + pL Čia
DiA
σh + ViA
D =
ViF
(81)
L
46

---

Moreover, using Young's inequality, we see that
11 n
oP
DFJ 20
F2z0 +
Σ
DF,
Fizu
4
j=1
3r'nn" L
3n2nn22
S 31 n
|Zool
p² F|
16
16
so we also conclude that
E
Z2n (zo- rnF -
S
Sn C2F
| +17" nn D2F
|| +n =n" V2F
holds for constants
3p²
20₂A 1
2D1A
3, 2
2VIA
C2F = 6
D2F
V2F
+
(82)
8
L
8
L
E.2.4 Upper Bounds of the Within-Epoch Errors for SEG-RR
Theorem E.16. Say we use SEG-RR with a = = 1)- Then, as long as the stepsize used in an epoch satisfies 1j Th, it holds that
||||| S 1/ C Fzoll + = DR Fzoll + 1
E
||||
zo]
S . C2R
F Fzoll² 1 n D2A
F F= l= + +1 11"1'² V2R
for constants CIA, DIA. VIR. C2R. D2R. and V2a to be determined later in 86 and (87
Proof. As we have discussed in Section 5.1 we already know that aiming to achieve O17²²) error with only using random reshuffling is futile. Instead, we show that error of magnitude ( is possible with the chosen stepsizes.
By Proposition
D.2 and Lemma
D.4 we have For any i 0, 1,.,,, N, holds that
Zn =
F 20 + n
Σ
+
Σ
DF, (z)) en
1=0
==
0skrjsn-1
F 20 1 DF
Fzu n
Σ
Fzz0 tE,
Ošjeksn-1
where we denote
Ejm F,z0 (2)((2) - 20)
=
j=0
(83)
n-1
カ-
1-1
+ 2
(20) - Fy20) +
Σ
(20)
Σ
FRwx FAZ0)
1=0
j=0
k=0
Comparing 2, to point that would have been the result of a deterministic EG update with stepsize we get
Zn (zo 1nnFF22 mmF22))
F F)F
Fm + DF cn
-
n?
Σ
(2)
0šjcksn-1
Let us define
Tpn F F(z
17n F F2 + DF Fzo + 6
(84)
Comparing the sums 62b and Theorem E. but with replacing the bounds given by Proposition E.3 to those Proposition E.4 to conclude that
62d) to
83 we repeat the same reasoning used for Theorem
E.9
| $ n ČiA Fzol + + DIA F Fzol'
+ 172n 2 VViA
E
=
< " Č2a
F 20 + 17 n DeA F =zol!* + n V2A
47

---

for some constants CiA. DIA, VIA. C2A. D2A, and ViA. Meanwhile, we also have
Σ
(2)
Poz0
Σ
(1 95-1)
OStchSn-1
==
n-1
n-1
Σ
(m=
-
Σ
(20) - (f+ ++1) Fz.)
1=0
==
which leads
n-1
n-1
Σ
(0)
$
Σ
(n - - 1)L
#ool
L
6j+1
Osicken-1
1=0
1=0
(85)
n²L
L
n-1
+
65+1-
1=0
Therefore, from 17 S 1/1L and Lemma E.5 on one hand we obtain
=| (zo F=o mFFF S 2 Fzoll + n DIR |F + in
for constants
ČiA L
DIA
V/A
CAR 2
+ +
DIR
=L=
(86)
L
L
On the other hand, applying Young's ' inequality on 88 we get
Σ
DF
Ln Fzol 11 + 2L
6j+1
oSjckšn-1
i=0
S Ln 2n
87
Taking the expectation conditioned on zn and applying Lemma E.6
we conclude that
E 1|22| (zo F(= FF =1]
S 1/ 1
*C2
C2r
F +1/
D2a
|
+n1
VZA
holds for constants
20₂A L
2D²A 2
2Ve0
C2R = 21 + 42²
D2R =
VeR
40 +
(87)
L
F
Convergence Bounds in the Strongly Monotone Setting
In this section, we focus only on the iterates {2 So, we omit the subscript 0 unless necessary, and simply write z² instead of k
F1 Unified Analysis of the Upper Bounds for Shuffling-Basee SEG Methods
When is j-strongly monotone with μ > 0, all of SEG-RR, SEG-FF, and SEG-FFA do not diverge. In fact, it is possible to establish the following unified analysis of the methods.
Theorem F1 (Theorem F.5 simplified). Suppose that F is p-strongly monotone with 0.
Assumption 3.3 holds, and an optimization method whose within-epoch error satisfies (31) and (32 for some constant a >> 0 is run for K epochs. Then, for a sufficiently small constant w that does not depend on K, we achieve the bound
E E||2 - =1 < exp (-bmwnk)
1|=0 2=12²+0 +
48

---

The goal of this section is to prove this theorem, whose precise statement is in Theorem F.5 As
the polynomial decay will dominate the exponential decay for large enough K, the bound we get is essentially Ô ('/Kk===). Recall that for SEG-FF and SEG-RR we have a 2 (by Theorems F.
and 16 which leads to an upper bound of (( whereas for SEG-FFA we have a = (by
Theorems E.9 and E.13 which gives an upper bound of O(/nx*).
As also mentioned in the beginning of Appendix E. for any of SEG-RR, SEG-FF, and SEG-FFA,
we can decompose the update across the epoch into a deterministic EG update plus a noise. this section, letting w == xh MT.FF'" we define F by the relation T = 77 Fu + +r so that
k+1 2t - FFFF..
(88)
Let F be p-strrongl monotone with fs > O. Then, for any Tee > 0, it holds that Proposition F.2.
n
2
3
11 n
(1 1 (1+
zumm n
1
||
(89)
||ش - 201 || 201 ==12²+
2 + pTlM
||m
<
prxn
Proof. From 88).
using Lemma C.7 we get
= ||2 -=--=- ==1 2 KnnnF F* ,² - x²) nen n Fate 1
| k+l
= 1|2 -- ==11²- 2m ( (Feo n0t ²²) 2n (Foof Fz")
+ | 2
2 ((tt, x²th xx===²) -²²)
s $112* x=2 wm || - =1 221 2
FF F
- 2( 2t - 2²) + n 1
+ 2pm
F
Mcanwhile, using the polarization identity (Lemma C.I and the L-smoothness of F we get
-2 (Fw Fz = F Fu
Fz 2
Fw x || Fz ||
S 2 221101 / z* 1|2- 1-1| F 2 - || 1| 1|
S - - n 2 L2) F= I12 - F !|?
Combining the two inequalities and using the definition of F we obtain
|| - x11 < (1 -mmmn) || 2²1 nin? (1 -nnn22 |F || n
F k $1
-2 2 -((rr: zt= -z") + | + nk 11 2umin |
< (1 (mnpen ||= =211
nmn211 (1 -2mmk ninn? T.?) x12
2 2(px 2² - -x") + + (T* n. Fw
+ ||10011
< (1 (mrpen)
|| =01
n2n² (1 -2mmk n L22) F
2 (rr =t Fu 2²) + b
Let us consider the inner product term in the last line above. By Lemma C.2 and the nonexpansiveness of the EG update (Lemma C. for any 7t > O we have
-2 (r 2² F - xx) < 7k
||
11
+ 7M 1| FFFFFFF
2=1
1
||
2
||
2-12
2 nnn - ") || &
7/
7k
49

---

Plugging this back we get
n (1 + 7 21 - (1 + 7/k m 22 Fz
S (1 7 -mm || 2" 2²1²² | 1 - -2- (1+
(90)
||a
Phk
Choosing 7/k completes the proof.
Proposition F.3. Let be a p-strongly monotone and L-Lipschitz operator. Then, whenever
1 it holds that Th nLv2"'
|| (1-
||
Proof. Let 24 2 the L-smoothness of F and Lemma C.8 implies
(( m. Fz*), so that we have
k+1
|r
Then,
|| 11F**11
< F k+1
F k+1
F
k+1
v L
x+1
2
k+
||
+
Fz
k-1
$ L |||||| + 11- 2umnn
1/2
||F*|||
s L |||||| +
|
5
where in the last line we apply a simple inequality 2x S (1 - x²² which holds for all x E RR
Lemma F4. Suppose that 31 holds.
Say
constant stepsize Ti 17 where n satisfies
7 I nLv? and
1
1
n
10
min
L2
L(C + Di( vi/ue))
(91)
Then for any k = 0...... the following two inequalities both hold:
121+1| || - (1
pmm
F=
1
(92)
10
V
F= < Fx F2
+
(93)
μL
Proof. For the case k = 0, the inequality (33) clearly holds. For the remaining cases, we use strong induction on k. More precisely, assuming that (33 holds for 0, 1,..., k, we will show that 92 holds, and from that the inequality
V nT.
F <
F>
(94)
follows. To this end, let us begin from noting that Proposition 93 implies
and the induction hypothesis
<
pmm
D, F2 11 + v4) + + LC₁ + n LD, (1 + μL ) || + n
F + L (G Fz"
(95)
pmn
5
Here, from the choice of the stepsize 91). we have
V41 (1
umm
77 LC LC + LD,
<
μL
10"
50

---

Hence, from 95
we get
Fx *++1 S 511- )
||
+ 17" n LV1.
10
which is exactly (92). Now, considering that we are assuming (93) holds for all 0, 1,.... k we must
also have (22 for 0, 1, ,....,,. k. Thus we can unravel the recurrence to get
Fz k+1
M 1
|
+ LV
10
||
I| (1
pmm 10
17 LV LV + 1
10
k
< (1
Fz
+ 1f n LV
Σ
(1
pmm
(96)
10
10
j
LV
|=
(1
prrr
10 1| + 107 In - LV
As 91 also implies 10m n - S 1/L, we obtain (44. as claimed. This completes the proof.
Theorem F.5 (Theorem holds, and an optimization method whose within-epoch error satisfies (31) and for some constant >> 0 is run for K epochs. Let define a constant
Suppose that F is p-strongly monotone with μ >> 0, Assumption 3.3
Vg ||
Φ =
C2 C2
D2
+ μL
Say we use a constant stepsize 7ik = 7,, where 1j is chosen as
min
(97a)
5nL
(97b)
(11012)1/(-11)
1/(-11))
(97c)
m(10L(C1 + D2 Fzoll + V(/
(97d)
(120//)2/(2aa-
4(a 1) log(n (n 1/22n 2) 2)
(97c)
pnk
Then for w denoting the minimum among (97a) 97d
it holds that
(log(n//(aa2)) K)) 2a-2
E ||| - =11 < exp (-5uwmk)
||
2" 2112 +0
(98)
nK20-2
As reminder, for SEG-FF and SEG-RR we have = 2, and for SEG-FFA we have = 3.
Proof. Notice that 97bb and 97ch
together implics 91 and that 77s- = 17 S 5mL
1
ntv2
m..
So, we can utilize and Lemma to get
E
||||
< n n 20 C2
Fz
n 20 20 D2 12 + 17 20-10111
V1 ) || ||
1| 20n 20 C2
| 2 20 20 D2
|| j.t.)
+ 1,200
20 V22
2n 2a $
Fz 212
+ 7720 20 V2.
51

---

Taking the conditional expectation on 89 and applying the bound just derived, we obtain
17 n2? (1 2 wmm
1 +
2
wmm
11 n2²211 2 1
|
1 (1 -mmm)) ||2 =²1 E ||| 1--1-==1p =012 =
2 pmm (1 (122-11122 1220 | + 11 2---1 1n 20 2 212)
A simple rearrangement of the terms leads to
1 n2nn
3
zum - 1 + z n L2
2 pam
11 20- 20- 3
|| ||
(99)
$ 1 2 (m))
||~" x= 1| E - x=12²
xx
2 pmn
17 20-1 nn 20 2 V2.
Notice that by assuming (97a) and (97)). it holds that
3
2 + pry
umm
+
1 + 2 uum
17 nr²n²I²
+
8n 1
20
2a-B5
3 2
2 5
2
12
/1
124
1+
5/
12Φ
125"
so we can guarantee that the left hand side of (99) is nonnegative. It then follows that
E ||| ==10² 2² S (
2 umm
||** ==1²+
2 + pmm
11 20-
1, 20 2 V/2
/
Applying the law of total expectation, from the above we obtain
E ||| - 1=
1 _
B B||2*
2 + 2 pm
17 20 n 20 2V2
We can now unravel this recurrence over A 0,,,.... K - 1 as done in 96 to get
|| x" x²11 1 1
1
E =| - x² 2=1
+ pmm
17 20 1 2a 2 1/2
5 ...
K
K-1
1
1
| |>"-="1²
2 + pmm +
20
11
20
22 V/2
Σ
(1 pmmm
1
1
P
j-0
1
+ 4 + 2pmm
1
Jum
1|20 - =11
1720
2
1mm
S exp
||=0 2²1
+ 5112
24
1120 20-2,
n
20
where in the last line we used the basic inequality 1 + x S ex which holds for all x E R. With the choice of the stepsize (97e), we arrive at
E 12* K 2²1 S exp (
1 (-bum
||20 =112 24. (4a 4)2a-2
(log(n 2120-2) 2a-2
5a
n. 2222a-
(100)
Now, recall that 1) is chosen to be the smallest one among 97a) 97a
97e).
Notice that the options
d7 independent with respect K, and (97e) is the only one that depends on K. Let us
consider these two cases separately.
(i) 1) is chosen to be the minimum among 99aa
97d
This is the case where we have 17 w. Notice that the constant w that does not depend on K. The inequality (T0Op then takes the form
E z
2²1² S exp
x²
jwnk
|120 - x" 12+ +
(log(n K))
2
n2k2a-2
52

---

2) chosen be (7e). that is, r)
4(a-1) log(n) 2126022
log(n
jon
In this case, the exponential factor of the first term in the right hand side of (100) reduces
exp -
(-5umk)
Thus, the second term in (100) dominates the first term, and in total 100) becomes
(log(n>/(2a- K))
2a
2² =11 =11==00
E
nK20-2
Therefore, in both cases we have
(logg(n//220
K)) 2a-2
B||2* 2" 11 &
(-Jlunk) - -21=
exp
nK 222-22
which is exactly
98 This completes the proof.
Remark F66 To compare the convergence rate of SEG-FFA in the strongly monotone setting with that of SEG-RR by Emmanouilidis al. [18] more in depth, let us make estimation on the size of w appearing in Theorem F5 when a = 3.
To this end, we need estimates on the constants CIA. DIA, VIA, C2A. and D2A. From their definitions in (59
(72). and (73) we have CIA Ltd DIA x M, VIA X M + L22, C2a x L and D2A M In general, there is not direct relation between L and M. For example, recall that all components are quadratic, then M = O. Meanwhile, Gorbunov et [21] has argued that M can be much larger than in certain cases, by providing an example where M /3/2, For our purposes, however, let us allow M to be even as large as M x L2, so that the situation is simplified into C1A DAA VIA 2 and C2a = D2A L
Then, we get the estimate (97c).
1/2 (C + DIA([ Fzol + Viafp2)))112
P
nI2
Meanwhile, as for the constant & it holds that
Φ C2a D2A (11291|
ViA
I66
uT.
112
for 97d we have
1 nI?
(120/p))11 As 97a while 197b) are both ((//L) and S L, we essentially have w x M/nL3, Or equivalently, ((1), the convergence rate (98) reads
for some
by² K
(log(n)/<K))*
E || K 1=1 < exp
||0
121=2=112+0
(101)
1,
nk*
On the other hand, Theorem 2.1 of [18 states that, for some 1/ 0(1), SEG-RR exhibits rate of
ppp2K) 2
(
(log(n>/²k))²
E Bl|2* x" 2=1 < exp
|| x +
2=
(102)
nk²
Comparing [01] with 102) the exponents in the exponentially decaying term of the same order # of 1 so SEG-FFA having faster polynomially decaying term ((1/xx*)) enjoys an improved convergence rate.
53

---

G Convergence Rate of SEG-FFA in the Monotone Setting
G.1
Star-monotonicity
Notice that we only used Assumptions 3.3 and 3.4 in deriving the results in Appendices and F and in particular, the monotonicity assumption on was not necessary. Moreover, among the lemmata Lemma|C.100s is the only one that possibly uses the (non-strongly) monotone assumption, but that lemma is not used in this section.
listed in Appendix C Lemma ic
In fact, as it turns out in Appendix G.2 in the convergence analysis of SEG-FFA, we need not fully exploit the inequality (3) provided by the monotonicity assumption. Rather, all the results the performance of SEG-FFA can be established with only assuming the following condition (which has been also briefly mentioned in Appendix B.2).
Assumption G.1 mttatmoonttoiccty). Given an operator F with point x" E R +di such that
Fz" 0, we say that F is star-monotone if, for any 2 E Rd it holds that
(Fz, - x²) 2 0.
(103)
Monotone and strongly- hand, there exist operators that are star- monotone but not monotone: see, e.g., [31 Appendix A.6].
strongly-monotone monotone operators are clearly star monotone,,,, as they satisfy (3. On the other
Recall that when F is monotone, Assumption 3.2 is equivalent to assuming the existence of a point z" that satisfies Fz* O. Hence, after simply replacing the optimality condition in Assumption 3.2 with Fx" = O, our convergence analyses not only will show that our SEG-FFA finds an optimum on monotone problems, but also that it can be also used to find stationary points in "star-monotone" problems, allowing the objective function f to be nonconvex amnconvex-nonconet nonconcave..
Star-monotonicity is also known as the variational stability condition 25 and has much been studied
in the literature. For further details on star-monotonicity, we refer to 25 31
and the references
therein.
G.2 Convergence Analysis of SEG-FFA in the (Star-)Monotone Setting
Let us in particular consider SEG-FFA. As in the previous section, we focus only on the iterates Ix20- {=0hx20 so again, we omit the subscript 0 unless necessary, and simply write z² instead of 2
Decompose the update across the epoch into a deterministic EG update plus noise, as
w = 2h +NnFF=
(104)
k+l = -
for f defined by the equation
F* Fu + x
(105)
Lemma G.2. Let F be (star- mmonotone operator with point 2" that satisfies Fz"
0, and
suppose that Assumption 3.3 holds. Then for any T}k > and 7/k > 0, holds that
|| k+ - 2² 2=11 n (1 Ti 2 L2) F2 x
1
(106)
7k
7/
Proof.
By
104
and (05)
we get
12h41 x" 112
m.n Fk 2-
= || - x x=12 2 2 (in 2² -x-) + m
= || - 2¹1 - 2 Fn wi - x²) - 2 (ninFwe x² -wt) 2 (r* , -x")
+ F w + (T* FmFF ) + ||
= ||2 - =111² - 2m (Fu wi - x²) - 2 (m.FFert Fz
+IImunFww (r *² FmnF -²") ||
54

---

|| ==11²
2mp (Foof, uot 2²)
( FF 2 Fz2)
|| n
(r z =²) - -1|
We now bound the inner products. On hand, by the polarization identity (Lemma C.1 L-smoothness of f. we have
and the
-2 -2 F Fz = ||| F F2
Fw d
|
F *
$ 1.2 1) z 21
k F
2
F
= -1 - n L- Fz
|
Fu
On the other hand, by the weighted AM-GM inequality (Lemma C.2 holds that
for any number as (0, 1) it
2 (r" k+1
2²) 1 0k |r + an || =01
Using these two bounds, get
|| 1 1* =2²1/ 2m (F wt - -²") mn:n2 n1=221?)
|F21|1
nên Fwo || + nin? Fwo 2 + to || - =01 +
{1) -1) ||
ax
Choosing On =
7h and rearranging the terms, we obtain 14%
2mpn (Fw w - ==") I 2011 1 Ykk
|| =2²11"
(107)
nEn (1 n Fz 1|²
1
||
79k
The left hand side of (107) is nonnegative by the star-monotonicity of F (103), and the claimed inequality follows.
Now we show that choosing the appropriate stepsizes leads to Fz being bounded uniformly over k.
Proposition G.3. Let F be mmonotoee operator with point z" that satisfies Fz* 0. and suppose that Assumptions 3.3 and 3.4 hold. Say we are using SEG-FFA, or any optimization
method whose within-epoct error satisfis 58 and (7I). Let the sequence of stepsizes (mp hx2o be nonincreasing, with
S =
& 1 30. Σ
(108)
Suppose that initial stepsize t/u is chosen sufficiently small that
n
3
3monD?
e (1="- 2- 1=
6SV2
S
(109)
L3
L
I
for constants C1A. DIA and ViA defined
59
611.
Then for all kllk2 k 0.
|| - 2¹1 6.5V2 1A
Fzk S e
TT2
(110)
Proof. We use induction on k to establish stronger inequality
6SV
||
21
<
211
1A
(111)
7
To that [1I] indeed implies
110p. notice that by the L-smoothness of f it holds that
Fz k
Fz
Fz" 12 < L2 1| -z" =²1
55

---

For the case when & = 0, as S > O, it is clear that I1I holds. Now suppose that 111
holds for
some & 2 0. Applying Young's inqquality on (31 leads
||~||
3nf (CiA F=
DiA
F2 |1 +
ViA)
Applying this bound 2 (06). obtain
||
on
n (1 1 (1-1gre nrn=~
3n CiA
3 Di
[F24 |F
The
(112)
$ $11 2²
1=1
1
2 k+1 x" 211²+
37ff2V 1A
+ 7/
7/
Choose " = 2/ 1,3. Notice that (109 implies yonl I 1, henceforth 8) S 70 S 1nt. This, with the induction hypothesis [TOp. implies
"hn 1,2 3nd
3n DiA ||
|
7
7k
3T
3mmnDiA
n 2T? ?²
||
L3
La
3
3imnDi
S 21,22,,2
|F
L3
L3
S 22² +
37
?
1A
D
1A
es LL
(1=0-x'11*+
+
6.5V2 L
1A
L3
L3
1
That is, the left hand side of 1122 becomes nonnegative. Then it is immediate from (112) that
21 s (1 + 74) ||2* =112² 3n/ne (1 + vk) V
|| ++1
7/k
6n V22
(1 & =112
1,3
Using Lemma C.Il to unravel this recurrence relation, we obtain
61,
| k+l
x² 1 <
I1 (1 + 12)0L9)
|1 |120->01|
211
1A
1=0
1=0
$ Ch 1f 13
|| ||100~011 201
6V/2 76
Σ
n3 n 13
1=0
S Se (1~00 =012
6SV2 I
1A
which shows that (1I) also holds when replaced by k + 1. This completes proof.
Theorem G.4 (Formal version of Theorem 5.4). Let F be (star- Imonotone operator with a point x that satisfies Fz" = O, and suppose that Assumptions 3.3 3.4 h.ld Say that we are using SEG-FFA, or any optimization method whose within-epoch error satisfies (58) and (TI), with
no V/llog 3 T = (k+2))/3 log(k2) and a₁ Ba/2 k = 0, 1,..,, where, for S = Σx k= Thn L3, the
initial stepsize nu is chosen that
30anCi L3
3mnnD? σ (1>0-
6SV2
2
TA
<
(113)
L
L
for constants CTA. DIA, and ViA defined in (59) that
(61. and there exists positive constant À > 0 such
22
Con
nonDeA
5 |1 2012
6SV2
< 11ーA
(114)
L3
L
1
56

---

for constants C24. D2A, and V2A defined in 72
(7
for any K 2 1, it holds that
(log( K +3))
(1==-~2"1 z" 2=112
3
min
IE
F2
mL ngn?
(115)
0=
(K + +3)1/3
Xe-3/2
(o2 2)2
Proof. As the sequence of stepsizes {mk k=00 is nonincreasing and (13) asserts that 77 S 1/nL, we use the bounds established in Theorem E.9 and Theorem E.13 Also, the premises required for
Proposition G.3 are also satisfied, so the bound (110) holds.
Setting 7/ n 1,3 in (16)) and then taking the conditional expectation given zt, with using
71
and 114). we obtain
S
|
1
E
||
2012²
2/
nnnn(1 n222212) F2 & ||
1 E 7kk
||md ||
26
+ 7k
$
|
x |1?
||
x"11 $11
x/
+
n (1
nnn )) |=*11"
1
CZa C2a F2*1|² + + D2A |=*1|
+ +n m2 V2a)
1,3
< $112" 111
E
|| - =1
+
m2n12a
man
|| | |F + 122
- n 1
212
I3
I
I
|2 + man V2A
$ 1| 2²
E
|| - 211
z²1
unin
+
L3
By the law of total expectation, and that 7k n2 11 L3 1, from the above we get
(1 + 7he m
(1 + (n)n)nn E F= 11 < (1 + 7w. EE || - =1 B|| k+1 - ==1 +
1,3
2 n V2A
s (1 ) 11 B1 2=1
33
This recurrence can be unraveled using Lemma C.I1 giving us
B B||= ||
x=11² + Σ (1 + +x+ An F|
(116)
K II (1 + mm)
K
2 n2 V2A
| - x=
+
L3
k=
k=U
For the left hand side of (16 we have
K
E K-
xx 2 + Σ
1
(1
+
7h
|
2 >
m IE |
k=
(117)
K
E Fz F2 112
min K
n
k=0
From Lemma C.12 we know that whenever K 2 1,
K
K
Th (
(k: + (log) (k: + 2))²
k=
A=0
(K + 1/3
2 n3n (V2log22
(log(K K 3))3
57

---

Meanwhile, as x. (=o)(((((+2)]
2(1og 2)
is decreasing function, have
20
2log 2)3
S +1+ 2(log 2)S
2log 2)
+
(x + 2)(lok + 2))3 de
(k +
(log 2))8
3(lgg 3)3
A=
2og 2)
(log 2)s
S +
+
S 2
3log 3)3
(log 3)2
and thus
S
n 2 L3 - nn a L3
2(log 2)3
S
3
311
n
3,
L
3 2
(A: + 2)og l: + 2))3
2
kmm
km0
Thus, for the right hand side of (16)). holds that
II (1 + mw)) (w)+
[110->011] 201
n V2A
EN
|100 ----2- 11
K
2m n V22
L3
1
k==
k=0
S 5 | =11
2.5V2A
nL6
I 2/2
||20 211
3V2A
nL6
(118)
Therefore, from [16) we get
>n 2/2 log 2)2..
(K 3)//3
min E|
F S
S2202 2/2 |1000 =0
3V2A
(log( K + 3))² k=o,
n.6
Simply rearranging the terms gives us the desired inequality.
Remark G.5. While 7/ should be chosen so that both (113) and (14) hold, in practice, there is a way circumvent this complication. Notice that in deriving the upper bound (188) of the right hand side
of (T16), it suffices to have The S
(K-42)*75 log(k+2)) and the lower bound 117 of the left hand side
Ti log
holds for any 7h 2 0. In other words, if we have had chosen 77k- = e (1/(+1))) for > 3 so that
S= Ex= n 3 L < oo, as long as roo satisfies (13)) and (14), we would still have obtained the
inequality
min k=
B||F=*|| < dn Ek the
(120-~ -1=0-2112 2=2
2SV2 nL6
(119)
In particular, if we additionally assume that q < 1 then
K 222
k:29
so from 119) we would have obtained the convergence rate
min k=
E F1 = O K1-29
(120)
We now claim that, if one accepts slight sacrifice the convergence rate from O(/)tta) to O (1/x1-2r) for 1/3
1/2, one can simply choose the stepsizes 7 moo((*+))* for sufficiently small 1ouo- To see why this is the case, let us fix no to be a number that satisfies the inequalities
(144))/11g((++2)) there will exist nonnegative integer ko such that 17p S (k+2)-/3 log(k+2) for all le > kg. So, by ignoring the first ko terms necessary- that is, considering as if the both iteration is the Oth iteration it follows from the discussions made above in obtaining (20)) that get the rate of convergence O (1/x2-20).
113) and (14). Then, because non/(l++)"
Yo $2logg
This discussion also justifies the choice of stepsizes y θ (1/0+2/1000.23) used in the experiments for the monotone setting.
58

---

H Proof of Lower Bounds
H.1 Proof of the Divergence of SEG-US, SEG-RR and SEG-FF
We prove the divergence of SEG-US, SEG-RR and SEG-FF in each proposition below, using the same worst-case problem for 2. These constitute the proof of Theorem 4.1
Proposition H.1 (Part of Theorem 4.1 For n. 2. there exists convex-concave minimax problem
f(, = E 1= fe (x.y)) y) having monotone F, consisting of L-smooth quadratic fi's satisfying (1,0) such that SEG-US diverges in expectation for any choice of stepsizes farh:o and {Bt h120 That is, for all t 2 0.
Assumption 3.4
with (p.
11
>
E
2
F 12
> E
Fzll?
Proof. We consider the case of
L
L
L 2 zy
f1
4
2
I
L
fz(x,
x²
2y
V
which result in a bilinear (and hence convex-concave) objective function
L 1 E f((x.v) zy. f(z,v)= =
(121)
One can quickly check from the definitions of the component functions fi and fz that the corresponding saddle gradient operators given
L/2 Fi = - L L/2
L
L/2 L/2
L/2
T.2
2,
F2z
-L/2
2,
Fz
L1/2
z
A=
A=
where (z. 3) IR?. From the fact that ||-A,|| S L for all i's, confirm that ft's are indeed L-smooth. As for Assumption 3.4, we can verify that
1
L
Σ
F2
F2
Fz
|| F
2
thus proving that our example f indeed satisfies Assumption 3.4 with (p. = (1,
We now proceed to show that for this particular worst-case example f. SEG-US diverges in expectation. For 2 0, the +t+ 1)-th iteration of SEG-US starts at ze, and the algorithm uniformly chooses an index i(t) from [n]. The algorithm then makes update
wi 2t Og F(te) Ze.
1 2, Br Fi()) Wr.
our worst-case example f, the updates can be compactly written as
zt+1 = (I - 3,4 + a,,3,A )z.
Since we have n = 2, the update can be summarized as
[[I A.Ai o, 3, Af)
with probability 1/2.
2t+1
(I 3.A2 a, A3))z
with probability 1/2.
By the definition of A, and Ag and using A A3
we can verify that
1 BeL 8 L
N I 3,4 3
3
2
2
B.L
B.h
N₂ = I -- --442221 + 0.3,43
D.
2
+
3.
59

---

From this, we notice that the expectation of ||= conditional on reads
N Ni
2 N2
E |e++|l 2
=t 2t
Zt-
Working out the calculations, we can check that
N Ni + No
N₂
3 +
0
2
1 1+
2
thus resulting in
E ||
||
21
Since this holds for all f 2 0, SEG-US diverges in expectation, for any positive stepsizes (achc20 and (Be )20. The statement on |2 follows by realizing that F= = |||||-
Proposition H.2 (Part of Theorem f(x, = 5
For n = there exists convex-concave minimax problem =1 J fx y) having a monotone F. consisting of L-smooth quadratic fi's satisfying
Assumption 3.4 with (p.o) )- (1, 0) such that SEG-RR diverges in expectation for any choice of
stepsizes {as k20 and {3x 1k20 That is, for any 2 0,
2
> E 1
E
21 >
E
F F
Proof. The proof uses the same example as Proposition H.I outlined in (1TT). We show that for this
particular worst-case example f. SEG-RR diverges in expectation. For A 2 0. the (I: 1)-th epoch of SEG-RR starts at z8. and the algorithm randomly chooses a permutation algorithm then goes through series of updates
[r]] - [m]. The
w 2/ ag F (1+1))
= = 2 By Fr. (1+1))
for 0,..., In our worst-case example J. the updates can be compactly written as + = (I - 3x + 8x3444 (++1))))
Since we have 2 and there are only two possible permutations, the updates over epoch can be summarized as
[ [I 3:41 a4 4x) Ax + ax
with probability 1/2,
k+1 = 2
(T Ax a 8 3 A3) A;A, t Af)
with probability 1/2.
By the definition of A₁ and Ag and using A A = 0, we can verify that
12
BL 1212
Mi = (I B + an (I -3 Bx
B
1.2
1
18 1. 2
(122)
1 L
-ByL + LL
M2 = (I- A, 0z A3) A1 + (A)
82L 2
(123)
B&L
From this, we notice that the expectation of +1
conditional on 2/ reads
M, M1 + M M2
E
(=))
=/.
2
Working out the calculations, check that
M, M, + MM M2
0
2
0
1 +
L
2
thus resulting in
||=0
=
1
Since this holds for all A 2 0. SEG-RR diverges in expectation, for any positive stepsizes (aw
and [8x h220 The statement on | follows by realizing that Fz
||]]]
60

---

Proposition H.3 (Part of Theorem For n. = 2, there exists convex-concave minimax problem
fxx,v) = E 1 fa fz( v) having monotone F, consisting of L-smooth quadratic fi's satisfying (1, (1.0) such that SEG-FF diverges in expectation for any positive
Assumption 3.4 with (p.
stepsizes far and ( 3220 That is, for any k 2 0.
++1
E [
IE F
k+1 2 E
F=
We prove that SEG-FF also diverges for this f. For k: 2 0, the (I: + 1) epoch of SEG-FF starts at z and the algorithm randomly chooses permutation тą : [n] [m]. in the of SEG-RR. The algorithm then goes through a series of updates for i 0....,
Proof. The proof uses the same example as Proposition
outlined in 121
w = 2 az F
2,1 z Fx (1+1) w
which the same SEG-RR; but then, performs another series of n updates, in the reverse order. For = n, 2n 1,
/ = z C.., Fr. (2
++ = 2 Fr.FFr(2n ()
Using the definition of M1 and M2 from T22) and 113 one can verify that the 2n- = updates over an epoch of SEG-FF be summarized as
M2M 20 M, M22
with probability 1/2.
++1
0
22n
with probability 1/2.
From this, we notice that the expectation of ||
conditional on z reads
M M2 M2M + M2 M, M
E
||= =
(2())
70.
k
2
Working out the calculations, we can check that
M, MY M2M + M. M, M M,
1
++
2
0
+ 2
thus resulting in
E
11
k++
20
kk = -1++28
Since this holds for all & 2 SEG-FF diverges in expectation, for any positive stepsizes {au) and (2x) The statement on |= follows by realizing that F2 |||||
H.2 Proof of Limited Convergence of SEG-US in Monotone Cases
In 17 20]. the authors study the same-sample and independent-samee sample versions SEG-US, with step sizes a; and 3, satisfying a constant ratio: 3, 7a, for 7 E (0, 1]. While the authors show convergence in the monotone F case, there is one important limitation shared by the existing analyses. In order achieve min, [[]] =2,11²] 22 for an arbitrarily chosen e, the algorithms must repeat the same query the stochastic gradient oracle b ( ) times at every iteration reduce
the gradient variance from 2² to 7 In other words, the convergence bounds for SEG-US in the monotone case have an additive term ( that cannot be reduced to zero by proper choices of stepsizes. Below, we prove that such a o² term ratio 7 is fixed constant. This indicates that SEG-US considered in the existing results can never converge all the way to the optimum if = 1 is maintained throughout training. contrast, our SEG-FFA shows convergence in the monotone case when b = 1.
fact inevitable for any choices of stepsizes, if
Theorem H.4. n. 2, there exists a convex-concuve minimax problem f(x, = - having monotone F, consisting of L-smooth quadratic fo fe's satisfying Assumption 3.4 with (p,
-= ((
61

---

(0, such that SEG-US with any positive stepsizes {az 1:20 and h22 satisfying St = 7a for
7 > cannot converge beyond certain fixed constant (2 More concretely, for any 0,
{
70² 2
E
2 min
1 =0
regardless of the stepsizes. This holds for both same-sample and independent-sample SEG-US.
Proof. We consider the case of
(xx,1) Lay + by: f2(x, = Lay - vx + vy:
which results bilinear (and hence convex-coneave) objective function
2
f(x,
Σ
fi(x,y) = Lay.
2 i=1
One can quickly check from the definitions of the component functions f1 and f2 that the corresponding saddle gradient operators are given
Fiz
v1, F2z Az -- v1, Fz Az,
L
where 2 = (z,, y) E IR2 From the fact that ||||| S L, we can confirm that ft's are indeed L-smooth.
As for Assumption 3.4 we can verify that
F.z
F2 F
E 2v² =2v2.
Therefore, by choosing 2² 2 our example f indeed satisfies Assumption 3.4 with (p.o) (0, σ).
The proof is outlined as follows. For the example constructed above, we will calculate the [E[ - [| and show that the expectation identical for both same-sample and independent sample versions of SEG-US. We will then show that the update on the expected squared distance to equilibrium E||| [2] for given can only belong to two categories: either |||, 1| s [[[|=++a|| (expected
squared distance increases) or ||= 2 [ 2 2L (expected squared distance shrinks but bounded from below by constant). Since the two cases hold for any 2 0 and any choices of and
2a²
3 = 7a,, we show that the "convergence" can happen only up to neighborhood of equilibrium.
At iteration 6, SEG-US samples component indices i(t), E {1,2} 2 for its extrapolation step and update step, respectively.
the independent-samppl sample version i(t) and j(t) are independently sampled from Unif( (1, 2)), and in the same-sample version i(t) is sampled uniformly at random and j(t) is set to be equal to (t)). With the indices sampled as above, SEG-US then makes an update
w: 2: Oit F(t) Z
2++1
())) w
In our worst-case example f. the updates can be written
w: 2: a, Az (1(1)
= [I -, 8i(1) O//1
2111 = 2: Aw 8300)3,01
(I 3,A + 04,:A7
a, -
where we defined 81 = +1 and 82 = -1 for simplicity of notation.
We now calculate the expected value of ||
|| 2 (I 3.A ar 01.rA42)2 af 0333²² ||ll 2 R.22 |1l11
+ +23 A,A A 2,, A1) 28 3.A + -0,8AA)22,,1
-2 1
62

---

For the independent-sample case, since Si(e) and 8)(1) are independent mean-zen random variables,
Ee(e) + In the same-sample case, Ac()) = 8)(() is mean-zero random variable, so
= ||(T 5,4 + 3 A + o ||| || 1
2 + 83 |112
(124)
Eacey [e+ |1 || A + or,3, A )= + 03 |1l| 8,v2 ||| 20x, (2,,3,22(A0)) (A1, 1);
but once we realize that (A1, 1) O, the expectation becomes identical to (124); hence, the rest of the analysis the same for the two versions.
We now expand and arrange the RHS of (24).
It is easy to check that
-B,L
Zt
[1- ac 3, BeLox (1 (r33eL2))r
(I 1-3,44 + o,
BeL
1- 0,,222
1/+ 2
and hence
-I- - 3.A+ a,B.AA))11 112 ((1 a 3, L) ||=
= =11 - 20, + 3 al |
From this, get
10 Z
== [1]]= || (,0, 8. + - +28
= |= (20r B7 + aRL3)) +80
where we used the choice V22 2 as above.
The rest of the proof proceeds as follows: we show that, regardless of t 2 0 and the choices of ar and Br yau, the expected value of || given 2 can be categorized into only two cases:
1. | 2 < Bill ]] That is, the iterate moves away from the equilibrium in expectation.
yo² That is, the expected squared distance shrinks but is lower 2. || > Elll + 2 21.2
bounded by certain constant independent of the stepsizes.
Showing this immediately finishes the proof, because there is way that any E|||2:11 can get smaller than min min (1|=011 2 ). and || F=|| = T. || for our example f.
The remaining proof is simple, by noticing that ||= < =[+|=++1|] 11] is equivalent to
(2a, 58 a²)
|| s of L3).
(125)
Hence, if a, 8c, and satisfies 125 we belong to the first category. Otherwise, we are in the second category, for which we need to additionally show |[[|
27. When the inequality
(25)) is satisfied with the opposite sign, we must have 20, L2 (1+((a() > and
80 + az 1,2) || 2 20, - 8, + a3
Also, notice that
a - -1 (1- (3 <. - B. - Using 20, 2,, L1
+11++a0 L²) E 10 and substituting the lower bound on || into the
update equation, find that
[|| Z 11 = 1| (20r 83 L2 + oz || + 8:0 +
(10++++,11 aa
0² (1 + L²)
2 20, 3.2 33 12 + a
L
2ai
(1 L.2
Lastly, substituting B, = Yau into the RHS gives
702
E 12411111
>
1
- 1)
21
This finishes the proof.
63

---

Remark H.5. We remark that, while Theorem H.4 successfully shows that SEG-US as studied in
17 20 cannot converge to an optimal point unless the batch size increased every iteration, it does
not contradict the (almost sure) convergence result of independent-sample SEG by Hsieh et al. [25] Indeed, in [5], the stepsizes {(ts 1:20 and {Be |22 are chosen so that they decay to with different rate and hence the corresponding ratio 7 approaches O, while Theorem H.4 considers the case where Ot and 3, differ by a constant factor 7.
H.3 Proof of SGDA-RR and SEG-RR Lower Bounds
Theorem H.6. Suppose n. 2 2 and L, 0 satisfies L/p There exists p-strongly-comee strongly-concave minimax problem f(z)
consisting of L-smooth quadratic fi satisfying Assumption 3.4 with (p. a) (0, o and initialization zi such that SEG-RR with any
constant stepsize a 0, 3k = 3 > O satisfies
Ω
if S L/P,
110 - x x11
Lpnk La maKS
Ω
if > L/p.
where x" is the unique equilibrium point of f. For similar choice of problem (this time with (p, = (1, SGDA-RR with any constant stepsize = a > 0 satisfies
Ω
if S L/P
|1=00 - 21113]
-
Lank K K
La PAKK
if > L/p.
Remark H.7. In Theorem H.6. we adopt techniques from the existing lower bounds for SGD-RR to prove lower bounds for the minimax algorithms SGDA-RR and SEG-RR. In the literature, there are two types of lower bounds for SGD-RR when K Z L.pr: namely, Q (==K== + nk*) bounds for strongly convex quadratic functions 49 50 and ?
bounds for strongly convex non-quadratic functions 45 45 56]. Upper bounds that match the lower bounds in n and K are also known, indicating that SGD-RR is one of the rare examples of minimization algorithms whose tight convergence rates for quadratic vs. non-quadratic functions differ, within the narrow scope of strongly convex and smooth functions. While it is tempting to aim for a tighter Q nk lower bound for our algorithms of interest, we note that the existing Q2 n, bounds for SGD-RR are proven for percewise-quaddee
functions whose Hessian is discontinuous. Since the discontinuous Hessian violates our Assumption 3.3 we instead adhere to the quadratic case to prove lower bounds O (( for both SGDA-RR and SEG-RR (when K 2 p/).). These bounds may not be the tightest possible (since they are restricted to quadratics), but they still suffice to demonstrate that SEG-FFA provably superior to both SGDA-RR and SEG-RR.
H.3.1
Existing Lower Bound for SGD-RR
For the proof of lower bounds for SGDA-RR and SEG-RR, we utilize the results and techniques from the lower bounds proven for SGD-RR; thus, would be profitable to summarize the existing result.
In case of SGD-RR, it is known from Theorem of Safran and Shamir [50] that there exists minimization problem (xx) such that SGD-RR satisfies a lower bound of Q Ta + 1 nka for large enough values of K. We rewrite the theorem version in accordance with our notation and assumptions:
Theorem H.8 (Theorem 2 of Safran and Shamir [50). For any n 2 and L, > 0 satisfying L/p 2 there exists p-strongly convex minimization problem g(x) E (x) consisting of L-smooth quadratic gi 's satisfying Assumption 3.4 with (p. o) = (1, a)) such that SGD-RR using any constant stepsize Og
satisfies
E
x =0]]]]
Ω
Lunk
o²
min
{1,
unk
L
p²k²
L
The statement is equivalent to saying that for SGD-RR with constant stepsize a > 0, the bound o²
Ω( L holds for K S L/u and Q k=
+ w for K 2 L/p.
Lo
64

---

The function n, Ei= 9: used in the theorem is defined by the following component functions:
1
L
2 +
2 23
2
23
i
g((z) gi 2-1
22
+
(126)
2
--202
2
i i>
B
2
thus making the objective function
11
L
=
2
2 22
2
4
One can notice that the linear terms in Ji (126) change signs depending on I or not, and handling these sign flips the key the proof of the lower bound.
H.3.2 Proof of Lower Bound for SGDA-RR
For the SGDA-RR lower bound, we consider the following minimax optimization problem:
1 Σ f(x, v)
fi where E R2, y R,
i=1
(127)
[i v) (z(
10 2 2 1
where gi 's are from (26).. We need to first check if the problem instance satisfies the assumptions listed in the theorem statement. Since f(x, g(x)) 5²²² and g is p-strongly convex function, f is j--strongly-oe wesstrongly-conve--tteee www.--oo-ttoogly-cooooee Ii that each component fz y) L-smooth quadratic.
as claimed. Also, it is easy to check from the definition of
Lastly, to verify Assumption 3.4 we first define $1,..., as 8; = for i < n and s; = for i " Using this notation, The function gi be compactly written as the following:
2
2'
11 2
L
L
ge (2) 22, xz) = "
2 (2s; 1)x2 + 5.'3 3 + 2 (28; 1)23.
2
2
Therefore, the saddle gradient operators F; of f. and of f evaluate
u
Lx + 7 (28; 1)
Læ
F,z =
Fz
LS,33 + 7 (2s; 1)
13
14
ky
which in turn yields
[2 - Fz
0² +
L
o
rzl + S [[|] +0)
4
2
2
for all i = I,..., This confirms that the function f 1 E, fi satisfies Assumption 3.4 with (p. = (1,
If we run SGDA-RR on this problem, the updates on æ done by SGDA-RR is exactly identical what SGD-RR would perform for the minimization problem g(z) same choices of random permutations. Therefore, after K epochs of SGDA-RR, it follows from Theorem H that
(:(x)) with the
o² LjIn
min {1 jnnK
1 K2 )).
E
x"
E ||
+
which in fact a tighter lower bound for SGDA-RR than what is stated in Theorem H.6 finishes the proof.
This
H.3.3 Proof of Lower Bound for SEG-RR
In this subsection, we prove the lower bound for SEG-RR. We will first define a new problem instance / to be used here, and verify that the assumptions in the theorem statement are indeed satisfied by this new f. We will then spell out the update equation of SEG-RR for this example, which will serve basis for the case analysis that follows: we will divide the choices of stepsizes
65

---

a,3 > 0 to four regimes and prove lower bound for each of them. Combining the regimes will result the desired lower bound.
For SEG-RR, we use a slightly different problem from 127 This time, we consider
f(z, v)
Σ
fi y), where E R VER,
i=1
(128)
I
L
(xx
2 #1
2
+
222 + (2s;; 1)22 n0²
4
where = for S and = 00 2. as defined above.
We first check if the problem 128 satisfies the assumptions in the theorem statement. Since
L L
f(z, y) 2
2
and L/2 2 by assumption, f is p-strongly-come www-r-cooeexssseee www.sssty--cooccaaae Also, it straightforward to that each is an L-smooth quadratic function. It is left to check Assumption 3.4, The saddle gradient operators F; of fi and of f evaluate to
Lx + (281
Lo
F2z
1)
Fz
1/ 22
2
which in turn yields
|| Fi= F =²²
Fz
for all i 1,.--, n. This confirms that the function f n E. I satisfies Assumption 3.4 with
(p,o) = (0, as required by the theorem.
For k 2 0, the (k 1)-th epoch of SEG-RR starts 2 (at v²) and the algorithm chooses random permutation Tą. The algorithm then goes through a series of updates
w x aF (F)
2 2 (
for = O,..., - 1. For our example f 128), it can be checked that single iteration by SEG-RR reads
(1- BL + +a3L))af
1111
1+1
x
1,2
SL
aBL" )ott B0
2 (1 Bu 1-
aL. (2 (1-1) 1)
Aggregating the SEG-RR updates over entire epoch (i = O,..., 1) results in
k+1
(1 BL yz
00,1
(1
BL
aBL2
x0022 -B0 (1- aL
(28 1) (1 8L a;3 n
k+1 2022
30
2
4
k+1 = (1 B₁ + )" vo-
1o
We will now square both sides of these equations above and take expectations over тg- In doing so, there is useful identity:
(B)2 - (1- 3L
aB3
n-i
B 4
Σ
2 +
0.
4
Also, it is worth mentioning that The is independent of can arrange the terms to obtain
(a
o wd))
Using these facts,
(oot1)² = (1 BL +
(129)
((( = (1 (1- 2
3L a.31?)
2n
8202 (1
al 2
+ 4
8202
E[
(130)
2
(1 (1 - Bp +a,yy 2)m (0 ()
(131)
66

---

Based on these three per-epoch update equations above, we now divide the choices of SEG-RR stepsizes a, B into the following four cases and handle them separately:
1. +. in which deterministically, so that we initialize at 48.1 LL
show that SEG-RR makes 1=
(x0,1) hold
then we have
o²
E
(=
(=0,1) TAp
2. a - and 3 I unkk in which case we show that SEG-RR initialized at 38
suffers
vLp
| Ω
Lμ
3. a S 2 and
pnk <B< < n.. in which case we show that SEG-RR initialized at 48,2 = 0
suffers
||
Lo²
E
4. a S 3 >
and B 2
1 nZ.
in which case we show that SEG-RR initialized at <0,2 0
unk
suffers
E
K 11 = (
[yunk
Notice that the third case uuk B case just disappears. Hence, for the "large epoch" regime where K L/ p. the third case achieves the minimum error possible, so it holds that
mI only makes sense when K L/p; otherwise, the third
E || x [2]
= (
Lo²
11nn33
For the "small epoch" regime (K p.) the third case does not exist and the fourth case achieves the minimum, so
||
E
L
Combining the two cases yields the desired lower bound in the theorem statement. It now remains to carry out the case analysis.
Case 1: a > t.
For this case, we use 129 to prove divergence. Notice from a > & that
1 1 BL + a. = 1 BL(aL - 1,
regardless of 8 > 0. Hence, from 112 we get
E
K
(क )2 > 12
we initialize at 08.1 VLn
then this proves
F
K
Case 2: < I and 3 < unk For this case, we employ [31 to show that the "contraction rate" too small to make enough "progress." Notice from stepsizes that
1- 1-3p aB8² 2
Bp 21
2 0.
nk
Applying this inequality to [3] we have
2
(2
nk
67

---

which in turn means that the progress over K epoch is bounded from below by
(5))
1
2nk
(v0)²
(v8)
nk
16
where used our assumption that 2 2 and K 2 1. Hence, if our initialization was given as 3 = VLn then this proves
E
| K 11
(y6
K
(o0) 16
o²
L
For stepsizes in this interval, we use (30) to derive the desired bound. Here, is important to characterize lower bound on the quantity
Case a S + and uon < <
at.
3L 2
aBL²
B B = E
Σ (28 11
To this end, we can use a lemma from Safran and Shamir 44).
stated below:
Lemma H.9 (Lemma of Safran and Shamir 49 Let Ti. Tn (for even n) be a random permutation of (1, 1,,1,.... 1.,,,-1..... -1) where both 1 and 1 appear exactly n/ n/2 times. Then
there is numerical constant > such that for any v >
27
n
T. (((--))* w)(-)
zc.
c..min min
1+ 2 .nnzz
One can notice that Lemma
H.9 is directly applicable to E[ with v + 8L
aBL2
Since
2
BL
aBL²
3L
V
5
2
2n
we have n2u2 S 8V* thereby
min { 1
1 n2002
n,
2 min
n
n
v.
Therefore, Lemma H.9 gives
BL
aBL? 2
n32
aL 2
e
E 2 3n
(132)
2
16
where the last inequality used
< }. Applying
132 to (30) and also using
(1-
8L + a
2n
B 2 2
Bl(x
4
64
Unrolling the inequality for k = 0,... K gives
BL
aBL2
2nK
(o) 3 K-1
Σ
3L
aBL
2nj
E
1
f=
2n.
BL
o:31,>
2nK
(x
1
(1
2
4
1
2
4
64
1-
81
0.812
2n
Now note that our initialization 20 can set to zero, which eliminates the need to think about the first term in the RHS. It is now left to bound the second term. First, by the stepsize range a < T. 3 > Wnk and our assumption L/P 1 2 2, we have
3L
aBT,2
2
BL
2nK
S (1
L
<
Se Se-1
2
4
4
4umK
68

---

Next, by Bernuuli's 's inequality
(1-2
3L
0,
2n
3L
2m
2
21 BuI. > 0.
2
Plugging in the two inequalities to above, we obtain
2 + oBL" 2nK
(1
35
E [x0,2)) )
64
PL
+ aBL2 2n
2
cB n2 L²
1 - e
= c 3 n Lo²
64
(1 - BnL)
for numerical constant
>> 0. Plugging in the lower bound B pnk yields
(Lo* Lo²
2 E (a
1ink3
Case 4: a S ł. B>
unk" and B 2 m
We again use (10 By noticing that the initialization
002 = 0, we can unroll (330) for h: = 0,
K - to get
0²0²
K
3L
aBL²
2nf
8²002
E (
E
1
E|
(133)
2
4
4
1=
where the last inequality holds regardless of because each summand with j 1 is nonnegative. We then invoke Lemma H.9 to lower bound [] again with v + 0L
aBL Since
2
3L
aBL
3L
2
4n'
we have n23r2 2 1_
64 thereby
min 1
+
1 ,nn² 22
min
n 2
2
1
v
64v
Therefore, Lemma H.9 gives
c
1
c
E 0
(134)
64v
32
1
al
32
Combining 134) with 133 gives
c30²
o²
Ω
128L
Lunk
where the last step used | unk
This finishes the case analysis, hence the proof of Theorem H.6
I Additional Experiments
To evaluate our algorithm SEG-FFA as well as other baseline algorithms, we conduct numerical experiments monotone and strongly monotone problems. Specifically, we have mentioned in Section 6) we consider random quadratic problems of the form
A
B
æ
min max RE D
y
B
-C
y
y
We choose d, = dy = 20 and n 40 for all the experiments. Numerical computations are done using NumPy [24] and SciPy [52]. and the plots drawn using Matplotlib (26).
69

---

I.1 Problem Constructions for Experiments in Section 6
For an experiment for the monotone case, the random components sampled follows. We choose B, so that each element is an i.idd sample from uniform distribution over the interval [O, 1]. and t; so that each element is an i.idd sample from a standard normal distribution. We chose A; to be diagonal matrices in the following procedure: for each j = 1....; 20 we randomly chose a subset I of n 20 indices from [n] fl...., 40), and set the
of A; to be
( -2
if E Ij otherwise
(Ai)s.s
We repeat the exact same procedure for C, as well. Notice that 4, 1 C, = 0 by design. Hence, each of the component functions will be minconvex-nonconeee quadratic function in general, but the objective function itself becomes a convex-concave function.
For the experiment in the strongly monotone case, we sample B; and t; in the same way as in the monotone case, but we use different choices of A, and C, to ensure the objective function to be strongly-convex-stronn ceoess-stroggyyconccce
In particular, for each i = I,.... we sample A, by computing A; = Q. where D; is a random diagonal matrix whose diagonal entries are i.i.d. samples from uniform distribution over the interval [2. 1]. and Q; a random orthogonal matrix obtained by computing a QR decomposition of 20 x 20 random matrix whose elements are i.i.d. samples from a standard normal distribution. We sample C; by the exact same method.
1.2 Monotone Case & Ablation Study the Anchoring Step
In Section 6 compared the empirical performance of various SEGs, namely SEG-FFA, SEG-FF, SEG-RR, and SEG-US. Here, as an ablation study on the anchoring technique, we additionally compare SEG-RRA and SEG-USA, which are each SEG-RR and SEG-US with additional anchoring step, respectively. For these two methods, we take the anchoring step after every n iterations. We ran those methods RRA and SEG-USA, we ran the method with two different stepsize choices, namely (inspired by the stepsize used in deterministic EG) and aj: = 8./2 n//2 (the stepsize used for SEG-FFA) where we again set T7 = no/(( noo(1=*/10) with 170- = min }..
the same 5 random instances used in Section O For both SEG-
3x = 7
The results plotted in Figure 2
As SEG-RRA and SEG-USA designed to take one pass per epoch, for those methods, we compute the ratio |=
where t denotes the number of passes, and F=
plot the geometric mean over the 5 runs.
From the performance of SEG-RRA with a₃ 8g and the two variants of SEG-USA, it is possible to observe that adding the anchoring step does improve the performance of the method up to certain level, but it alone does not fully resolve the nonconvergence issue. On the other hand, quite interestingly, SEG-RRA with a 8x/2 shows a hint of convergence. While its performance is slightly worse compared to SEG-FFA, is nonetheless still notable as it the only other method from SEG-FFA that seems to be capable of converging to an optimum.
We conjecture that this intriguing performance of SEG-RRA with a₃ Bx/2 is because it achieves an "expected" second order matching to the (deterministic) EG. Indeed, following the notations of Proposition D.I one can deduce from Proposition D.I that using SEG-RRA with 9/2 will result in an epoch-level update of
3 n-1 T2
82
g2
2 20
Σ
+
(2)
Σ
En (20 + 2
(135)
2 j=0
4
1=
0SKJSa-1
for some randomly chosen permutation E S,, Now, observe that for any two distinct i,j E [n]. there are n! exactly 2 permutations in S, such that i comes before j in the sequence (()) T(m), and also exactly a! permutations such that comes before i. Thus, in taking the expectation over the
T,,1)) with c, = o (B2). Here, notice that (Tg. T........TT.l..
(F Free)..... ...........))) Fr(n))
70

---

SEGFFA
SEGRRA,
SEGFF
SEGRRA, c 8/2
SEGAR
SEG-USA, 8
10a
SEGUS
3/2
or 1
1F2
10a
F 1
10-1
10-1
10-3
20000
40000
60000
BOO00
100000
passes
Figure 2: Experimental results in the monotone example, comparing the performance of SEG-RRA and SEG-USA with the results displayed in Figure [ Because SEG-FFA and SEG-FF use two passes epoch, for those two methods, we plot [F= 1f 11
randomness of choosing the permutation T, we get
E,
Σ
DT, (20)
= Er
Σ
DF (2))
0siciSn-1
Isicisn
Σ
Σ
(Z)
m!
TES, ISiejsn
Σ (2)( it3
where in getting the third line we have used the previously made observation that for any fixed and j with * j. the term (z, appears exactly 3 times in the sum on the second line. Hence, taking the expectation with respect the random permutation (355 get
n3
82
32 Σ (2) + Er [en]
E, 2 =
FzO
+
Σ
(Z) FzZ +
4
4 it
1=1
n
8
F +
DF Fizo Er [En]
4
1=1 t=1
n3
3²
20
Fu +
DF F zu
+ 2 E, [En]
4
Comparing this to when 1/2 = n8/2, we indeed see that the update rule of SEG-RRA with = 8/2 achieves second-order matching on expectation to the (deterministic) EG update with stepsize m8/2.
We also conjecture that the relatively worse performance of SEG-RRA with 8/2 compared to SEG-FFA is because the error over an epoch is O17²) only on expectation, and thus the actual occurring in each epoch can be larger than O Unfortunately,
convergence analysis on SEG-FFA relies on the error over an epoch being (17²)) deterministically (cf. Proposition 5.3). hence cannot be directly applied to SEG-RRA with 8/2. We leave the search for a theoretical explanation on this alluring performance of SEG-RRA with a 8/2 as a stimulating direction for future work.
I.3 Monotone Case: Comparison with Hsieh et al. (25
Let us also compare the performance of SEG-FFA with the independent-sample double stepsize SEG (DSEG) by Hsich et al. (25). Writing in terms of the finite-sum structure, the update rule of DSEG
71

---

10%
SEGFFA
DSFG, exporents (0. 1)
DSEG, exponents (1/3, 2/3)
10
[ or 1
1F211
10
10-3
10-4
10-1
2000
4000
6000
8000
10000
of passes (t)
Figure 3: Experimental results in the monotone example, comparing SEG-FFA and the methods proposed by Hsich et al. [25]. By the same reason as in Figure SEG-FFA only.
plot || 11/ for
can be written as
w t- x* -1, Fa.iFaaaa ((1,)) ++1 +- 2² - 122, F((2. wn
where i(1, k) and i(2, k) are random indices that are independently drawn from [n] for each k. The stepsizes are chosen in the form of 7h. ((/+r)) and 17.x (1/xr=), where setting rı S r2 the key point of DSEG. Two choices of the exponent pair (r1, r2) proposed in (55 are (1/3, 2/3) for
general monotone problems and (0, 1) exclusively for the case when F is affine.
We again use the same component functions as in the previous experiment. The setup for running SEG-FFA are kept the same. For DSEG, namely
the default choices suggested by Hsich al. [25], no/(k- 19)" and 72. No/(k=199'2, where (70, 7o) = (1, 0.1) for the bilinear case with (r1, (0, 1) and (To 1u) 10.1, 0.05) for the general
with (r1, T2) (1/3, 2/3).
The results are displayed in Figure 3 where the details on how the plots are drawn are the same as Figure Here we can clearly that SEG-FFA outperforms both versions of DSEG.
1.4 Strongly Monotone Case Again, with Various Stepsizes
also ran the experiment on strongly monotone problems described Section 6 but with changing the stepsizes. We tested six different values of 7x; we have tested with mh 10 where a E (1,2,5) 5} and (-4,-3) Notice the case TJ 10-3 exactly the experiment conducted in Section
The results are plotted in Figure The overall details are the same as described in Section as the only difference is the stepsize choice. We can observe that, while the initial speed of convergence may not the fastest depending on the stepsize, SEG-FFA always the method that eventually finds the point with the smallest gradient. In other words, as predicted by our theoretical analyses, the supremacy of SEG-FFA in general not affected by the choice of the stepsize, as long as the chosen stepsize is reasonably small.
72

---

SEG
SGDA.RR SCDAJUS
10a
FEG
SGDA. AR
10-1
SEG-FF
SEG-US
SEC-FF
SEC-US
SCD4-US
10:2-
10
or In2
1721 or IF
11277
10-
10r4
174
IF
10"
10
10.
10-11
10-10
2000
1000
3000 number passes
number of pesses
(a) 1//- 0.0001
(b) 1/2 0.0002
SEC FRA
SEG AR
SCDA AR
107
SEG FFA
SEG-RR
SCDA-RR SCDA-US
SEC-FF
SEG
SCDA-LS
SEC-FF
SEG-US
10-2
10-2
1936 p
IPS1 IF 1/21
1F25
10-2
10-1
10
1221
10
10-1
10-1
250
500
750
1000
1250
1500
1750
2000
0
100
200
300
400
500
600
700
800
number of passes (t)
number of passes (t)
(c) 17
0.0005
(d) 17h. 0.001
107
FFA
SEC-RR
SCDARR
102
SEC
SCDA-AR
SEC-FF
SEG-US
SCDA-US
SEC-FF
SEG-US
SCDA-US
10
10
o1 1F
10-2
IF
or 1E2
10t2
10
1F21
10
10
10
10-1
100
200
400
500
600
200 250
400
number passes (t)
number passes
(c) 776
0.002
(f) mp
0.005
Figure 4: Experimental results the strongly monotone problems with different stepsizes. Notice that Figure 4d is exactly the plot that is included in Section 6 The only difference between the experiments conducted is the choice of the stepsize.
73

---

NeurIPS Paper Checklist
1. Claims
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Question:
Answer: [Yes]
Justification: The abstract and the introduction well summarizes our theoretical results and the problem settings we considering.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: While we do not have a separate "Limitations" sections, Section 3 we thoroughly discuss about the assumptions
have imposed. The paper is highly theoretical, hence the other factors listed in the guidelines below are either not applicable to this paper, apparent from the statements of the aicorems/enmmat/prropssiiii and the discussions that follow.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
74

---

Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: Section Bls devoted for the discussions on the assumptions. Full proofs of the thooreens/emmnat//ppooiiiooss can be found in the appendices.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question:
Does the paper fully disclose all the information needed reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclusions the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: In Appendix || we provide full explanations on how the experiments have been conducted. We have also submitted the exact code that we used for our experiments as supplemental material.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to model. In general. releasing code and data often one good way to accomplish this, but reproducibilityy can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, other means that are appropriate to the research performed.
specific model and empirical evaluation, may
While NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm.
(b) If the contribution is primarily the architecture clearly and fully.
model architecture, the paper should describe
(c) the contribution is a new model (c.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the partieular way they provide for reproducibiliity In the case of closed-source models, it may be that access to the model is limited in
75

---

some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
Question:
Does the paper provide open access to the data and code, with sufficient instructions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: have submitted the exact code that we used for our experiments as supplemental material, so that it becomes revealed to the public once our paper gets accepted.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.co cc/
for more details.
While we encourage the release of code and data, we understand that this might be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https https///ooSSuuiissee.oe
/ //nipscco wwtppcpcccggpcicecccccooocccccce Btalliicggides/Coooe
for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Question:
Answer: [Yes]
Justification: The overall settings are discussed Appendix [ The code we submit along with the paper is an exact copy of the one we used in the reported experiments, so the details not included in the paper shall be found in the code itself.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them.
The full details can provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [No]
Justification: Our paper is mainly theoretical, and the experiments are to demonstrate that analyses correct. Hence, claim that error bars information about the statistical significance are not necessary, and rather, the interpretations we made regarding our experiments in the relevant section(s) are enough.
Guidelines:
76

---

The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report I-sigma error bars, but should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not show in tables figures symmetric error bars that would yield results that are out of range (c.g. negative error rates).
error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [No]
The experiments numerical validations of our theoretical analyses using simple quadratic functions, so they should be executable on any modern computer with reasonable CPU.
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer: [Yes]
Justification: We have read through the Code of Ethics, but due the theoretical nature of the paper, there are no risks regarding ethical issues.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.
The authors should make sure preserve anonymity (e.g., if there is special consideration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative socictal impacts of the work performed?
77

---

Answer:
[NA]
Justification:
There are no societal impacts of this paper, as it is a theory paper.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deploymentt of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning conrectly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
This paper is highly theoretical, hence poses no such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: Packages used experiments, NumPy, SciPy, and Matplotlib, are cited. No existing data nor models are used.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
78

---

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

---

The answer NA means that the paper does not involve crowdsoureing nor research with
human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
80


Reviews:
[{"review_id": "5di4UkUuc5", "reviewer": "Reviewer_19M7", "summary": "The paper studies various same-sample SEG algorithms under different shuffling schemes, including SEG-US, SEG-RR and SEG-FF. The three algorithms all can diverge when $f$ is convex-concave. Furthermore, the authors discuss the underlying cause for the nonconvergence of the three algorithms. Moreover, the authors propose a novel stochastic extragradient method named as SEG-FFA, which is SEG amended with flip-flop shuffling scheme and anchoring. The proposed algorithm enjoys improved convergence guarantees and the convergence rate is calculated under different conditions of $f$. Finally, the authors conduct numerical experiments to verify the convergence of SEG-FFA.", "questions": "1. Section 4 explains the reasons why simple shuffling is not enough for convergence for monotone problems. However,  why the added anchoring step can make the algorithm SEG-FFA converge is not sufficiently demonstrated in the proof, especially compared with SEG-FF.\n2. What is the difference between the stepsizes $\\alpha_k, \\beta_k$ of SEG-FF and $\\eta_k$ of SEG-FFA.\n3. In Figure 4(a) and 4(b), the convergence result of SEG-FFA is better than other baseline algorithms. However, the convergence rate appears slower.\n4. There are few typos in the main text and appendix.", "limitations": "1. The length of the paper is excessive, especially the appendix section.\n2. The experiments could consider demonstrating the performance of SEG-FFA on more large-scale problems.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper proposes a novel algorithm SEG-FFA for minimax problems, which achieves a better convergence rate when $f$ is strongly-convex-strongly-concave. Furthermore, the algorithm enjoys convergence when $f$ is convex-concave while other baseline algorithms diverge under this setting.\n2. The paper provides comprehensive proof for divergence of other baseline algorithms when $F$ is merely monotone.\n3. The proposed algorithm SEG-FFA can match extragradient up to second-order terms and get an error of $\\mathcal{O}(\\eta)$ where $\\eta$ is the stepsize. As a result, SEG-FFA achieves convergence in monotone problems.\n4. Sufficient numerical experiments verify the convergence result and superiority of SEG-FFA.", "weaknesses": "1. Due to the presence of anchoring step, the initial point seems to be more important, which implies that the algorithm is more dependent on the selection of the initial points.\n2. How to select the parameter $\\epsilon$ concerning convergence in Table 1 and Theorem 5.5 for practical applications and specific problems.\n3. Table 1 does not provide the lower bound of SEG-FFA under convex-concave setting. Is there such a lower bound on the iterative complexity for SEG-FFA?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer for the constructive feedback and thoughtful comments. \n\n1. **Importance of Initial Point due to the Anchoring Step (W1):**\n\n    For any optimization method, its behavior is more or less influenced by the choice of the initial point, and our SEG-FFA is not an exception. However, as we have shown (in Prop. 5.3) that the total update of SEG-FFA made over an epoch is equal to an update made by a deterministic EG up to a small $\\mathcal{O}(\\eta^3)$ noise, we think the dependency of SEG-FFA on the initial point is as minimal as that of the deterministic EG. \n\n2. **On $\\varepsilon$ in the Convergence Rates (W2):** \n\n    Please refer to the general comments. \n\n3. **Lower Bounds on SEG-FFA (W3):** \n\n    Unfortunately, at the moment we are not aware of the lower bound complexities for SEG-FFA. To the best of our knowledge, our work is the first to introduce the idea of flip-flop + anchoring, and has not been investigated even in the context of minimization problems. A search for an explicit lower bound would also be an interesting direction of future work. \n\n4. **Why SEG-FFA is better than SEG-FF (Q1):** \n\n    The explanations on how SEG-FFA outperforms SEG-FF are detailed thoroughly in Section 5 through the lens of Taylor expansion matching, with a summary in lines 257–261, rather than in the proofs. To summarize, SEG-FFA can achieve a second-order matching to the deterministic EG, leaving an error as small as $\\mathcal{O}(\\eta^3)$. Whereas, SEG-FF is at best only a first-order matching method, since an attempt to make it a second-order matching method leads to it approximating a nonconvergent method. Please refer to to Section 5.1.2, and the related Appendices D and E, for the details.\n\n5. **Difference in the Notations for Stepsizes across the Methods (Q2):** \n\n    Please refer to the general comments.   \n\n6. **Interpretations on Fig. 4 (Q3):** \n\n    The reviewer has made a correct observation. However, as discussed in lines 1519–1521, these results do not counter our theoretical analyses. Indeed, the convergence results in the strongly monotone setting are established under a fixed choice of the time horizon $K$ (see Thm. 5.5). More precisely, the results for strongly monotone $F$ are interested on how small $\\|\\| F z \\|\\|$ can be eventually made after running for $K$ epochs. So, for the initial few steps, the *speed* of convergence may be slightly suboptimal.  \n\n7. **Typos (Q4):** \n\n    Thank you for notifying us about the typos. We will try our best to fix them. We would also greatly appreciate it if you could point out some of them to help us correcting them.\n\n8. **Paper is Too Long (L1):** \n\n    It is true that the paper is longer than average, but we hope that the reviewer understands the length of the paper as an unavoidable side effect of encompassing multiple rigorous proofs with technical details.\n\n9. **Additional Experiments on Large-Scale Problems (L2):** \n\n    Due to the nature of our paper focusing more on the theoretical results, we admittedly did not consider much about additional experiments. Yet, we thank the reviewer's suggestion, and will contemplate on which additional experiments will be beneficial to our paper.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "AF1ljfQZ99", "reviewer": "Reviewer_jRnf", "summary": "This paper proposes a new algorithm, SEG-FFA, which converges for the convex-concave minimax problem, while existing algorithms like SEG-RR and SEG-FF diverge for the same class of problem. Moreover, the authors show that SEG-FFA can better approximate EG in comparison to SEG-RR and SEG-FF.", "questions": "- What is $\\eta_k$ in Theorem 5.4? The step sizes of SEG-FFA are $\\alpha_k$ and $\\beta_k$ in Eq 5. \n- Is it possible to relax Assumption 3.3? \n- Multiple papers show the convergence of SEG and Stochastic Past Extragradient [1] method for monotone problems with increasing batch sizes. Moreover, a work [2] proposes BCSEG (bias-corrected SEG), which proves convergence without increasing batch sizes. I recommend comparing these works with your Theorem 5.4 in terms of the number of oracle calls to achieve a given accuracy $\\epsilon$.\n\n\n[1] \"Single-Call Stochastic Extragradient Methods for Structured Non-monotone Variational Inequalities: Improved Analysis under Weaker Conditions.\"\n \n[2] \"Solving stochastic weak Minty variational inequalities without increasing batch size.\"", "limitations": "NA", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- It proposes a new stochastic algorithm, SEG-FFA, which simultaneously incorporates flip-flop shuffling and anchoring to prove convergence. To the best of my knowledge, this is the first work to successfully combine these two techniques.  \n- Usual Halpern iterations take a convex combination with the initial iterate, while SEG-FFA takes a convex combination with the initial iterate of the epoch. This idea is interesting and certainly paves the way for further research. \n- I find section 5.1 very interesting, where the authors explain how well different algorithms can approximate EG.", "weaknesses": "- Lipschitz Hessian in Assumption 3.3 is too restrictive, and the authors agree. I don't know if practical ML applications satisfy such assumptions. \n- In each epoch, SEG-FFA and SEG-FF make $4n$ oracle calls compared to $2n$ oracle calls made by SEG-RR and SEG-US and $n$ oracle calls by SGDA-US and SGDA-RR. Therefore, the comparison made in the second plot of Figure 1 is unfair. I recommend having the number of oracle calls on the $x$-axis to compare these algorithms fairly. \n- In Theorem 5.4, authors propose a decreasing step size of the order $\\mathcal{O} \\left( 1/ k^{1/3} \\log k \\right)$ while in plot 1 of the experiment, they use a different step size. Why not use the step size proposed in the Theorem?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the effort made by the reviewer in inspecting our manuscript. \n\n1. **On the Lipschitz Hessian Assumption (W1):** \n    As both our manuscript and the reviewer have mentioned, the Hessian Lipschitz assumption is a somewhat unusual one, not widely assumed in the literature. Still, it is not too difficult to find machine learning problems that satisfy the Hessian Lipschitz condition. As a basic example, consider the logistic loss function $\\ell(w;a) = \\log(1+e^{aw})$. It is not difficult to verify that $\\ell'''(w;a) = \\frac{a^3 e^{aw} \\left(1 - e^{aw}\\right)}{\\left(1 + e^{aw}\\right)^3} = \\frac{a^3}{1+e^{aw}} \\cdot \\frac{e^{aw}}{1+e^{aw}} \\cdot \\tanh(-\\frac{1}{2}aw)$ and thus $|\\ell'''(w;a)| \\leq |a|^3$. Now, when given a dataset $(x_i, y_i), i=1, \\dots, n$, recall the typical form of the loss function $\\frac{1}{n} \\sum_{i=1}^n \\ell(w;-y_ix_i)$. Since $|\\ell'''(w;-y_ix_i)|$ is upper bounded by a constant $\\max_{i=1,\\ldots,n} |y_i x_i|^3$ for all $i$, the Hessian Lipschitzness follows.  \n\n2. **Relaxations of Assumption 3.3 (Q2):** \n    While we unfortunately do not have a definite answer to this question, let us at least share our intuitions on this assumption. The reason we impose the Hessian Lipschitzness assumption originates from the analysis of the flip-flop sampling scheme (*cf.* [41]). In short, the desideratum is that the change in the Hessian of $f$ remains controllable throughout an epoch, so that after aggregating the updates we get a good enough approximation of a deterministic EG step. If such control is possible with other assumptions then one would be able to replace Assumption 3.3 with it. \n\n      We would also like to make a final remark that as we discussed in lines 199–202, the lower bound results that are obtained under our set of assumptions also serve as valid lower bounds for weaker settings that are implied by ours, so having the Lipschitz Hessian assumption is not a weakness in this scope.  \n\n3. **Comparing Methods on the Same Plot (W2):** \n    We would like to remark that, in the plot(s), we actually do count in the fact that SEG-FF and SEG-FFA make twice as many oracle calls than other methods. \n        That is why for those two methods we plot the values of $\\|\\|Fz_0^{t/2}\\|\\|$ instead of $\\|\\|Fz_0^{t}\\|\\|$; please refer to the captions below the plots.\n\n4. **Choice of Stepsizes in the Experiments (W3):** \n    We thank the reviewer for bringing up this point.  We realized that the rationale behind our choice of the $\\mathcal{O}(1/k^{0.34})$ stepsize schedule  has not been thoroughly discussed in the submission, so please allow us to elaborate further. \n\n    Strictly speaking, to make use of the convergence result of Thm 5.4—or more precisely, Thm. G.4—one should choose $\\eta_0$ so that it satisfies both equations $(121)$ and $(122)$. However, if one closely examines the proof of Thm. G.4., it is not difficult to realize that choosing the stepsizes so that $\\eta_k = \\Omega({1}/{k^q})$ for $\\frac{1}{3} < q < \\frac{1}{2}$ while $\\eta_k \\leq \\frac{\\eta_0 \\sqrt[3]{2} \\log 2}{(k+2)^{1/3} \\log (k+2) }$, we will still achieve a convergence to a stationary point, but at a cost of having a slightly slower rate of convergence $\\mathcal{O} ({1}/{K^{1-2q}} )$. But then, since the decay of $1/k^q$ is faster than that of $1/(k^{1/3}\\log k)$, simply taking $\\eta_k = {\\eta_0^*}/{k^e}$ for a suitably small $\\eta_0^*$ will suffice, as there will exist some $K_0$ such that $k \\geq K_0$ implies the inequality $\\eta_k \\leq \\frac{\\eta_0 \\sqrt[3]{2} \\log 2}{(k+2)^{1/3} \\log (k+2) }$, and we may simply ignore the first $K_0$ iterates to get a convergence guarantee. \n\n    We will add a more formal version of the discussion above in our revision.\n\n5. **Notation in Thm. 5.4 (Q1):** \n    Please refer to the general comments. \n\n6. **Additional Comparisons with the Existing Works (Q3):**\n    Despite everything, if we were to compare the number of gradient oracle calls according to their face values, SEG-FFA would in fact require $\\tilde{\\Omega}(1/\\epsilon^3)$ calls as the rate of convergence is $\\tilde{\\mathcal{O}} (1/K^{1/3})$, whereas, for example SPEG would require $\\Omega(1/\\epsilon^2)$ calls as claimed in p. 34 in their paper. \n\n     However, we would like to raise the point of whether it is fair to compare our SEG-FFA in its current form to methods that allow increasing batch sizes. SEG-FFA allows a constant batch size (of 1), which is common in practice, by coping with noise induced by gradient variance. Conversely, increasing batch size is not only rarely used in practice but also essentially sidesteps the complexities of dealing with gradient variance, as a batch size of $b$  reduces variance by a factor of $b$. Please recall Thm. H.4, where we showed that methods known to converge with increasing batch sizes may no longer converge if the batch size is kept constant. \n\n    Thus, if we really were to compare SEG-FFA to such methods, it shall be allowed for SEG-FFA to have increasing batch sizes as well. But this approach not only reduces the RHS of Assumption 3.4 by the size of the batch but also reduces the number of passes in an epoch—which is $n$ for single-sample-in-a-batch SEG-FFA—according to how batches are formed. Consequently, the size of the noise term $\\|\\|r^k\\|\\|$ will be reduced, and SEG-FFA would enjoy a much better convergence rate.  We believe that convergence analyses incorporating this change should be conducted as future work.\n\n    On a different note, as we have listed in Table 2, the work on BC-SEG+ ([39] in our paper) assumes uniformly bounded gradients. This, as discussed in lines 190–196, is too strong to be a realistic assumption, so we have not included a thorough review of it in the current submission. But yet, we agree that supplementing additional comparisons with [39], and the suggested related work by Choudhury et al., will make how our paper is positioned within the existing literature clearer. We will modify Section B.1 accordingly.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ATdisE1na4", "reviewer": "Reviewer_hmmd", "summary": "In this paper the authors study stochastic extragradient methods for solving unconstrained minimax convex-concave problems with a finite sum structure. In particular, various shuffling schemes (random reshuffling without replacement, flip-flop, uniform sampling with replacement) are investigated and it was shown that stochastic extragradient with them can lead to divergent behavior when $f$ is merely convex-concave. The authors proceed to propose stochastic extragradient with flip-flop + anchoring which successfully converges in convex-concave problems with rate $O(1/K^{1/3})$ and rate $O(1/nK^{4-5\\epsilon})$ for $\\epsilon < 2/3$ when $f$ is strongly-convex-strongly-concave. This is supplemented with a lower bound on random-reshuffling based stochastic gradient descent-ascent and stochastic extragradient in the same setup, demonstrating advantage of the proposed algorithm. The analysis is based on controlling the degree of approximation to a known convergent method. Some numerical experiments are presented to illustrate the practical performance.", "questions": "- It seems like this gap of $1/nK^3$ for SEG-RR vs. $1/nK^{4-5\\epsilon}$ for SEG-FFA only exists in a very narrow range of $\\epsilon$. Is $\\epsilon$ tied to other parts of the results? If not, I'd recommend just optimizing over $\\epsilon$ and state the final complexity instead.\n\n- Is there any special meaning behind the $1/2$ in (12)? Would other convex combination of the iterates work as well? Or possibly with other anchor points or even more than $1$ point help for higher-order matching?\n\n- In Theorem 5.4, can one afford a constant (and larger) stepsize if instead of asking guarantee in $\\min_k ...$ we do tail averaging?\n\n- The parameter $\\rho$ or $\\sigma$ from Assumption 3.4 don't make an appearance in Theorem 5.4 and 5.5?\n\n- What's the difficulty of generalizing this framework from same sample to independent sample extragradient methods?", "limitations": "Yes it's adequately addressed.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The results in this paper removed several limitations from the previous work and shed light on algorithm design for the appropriate sampling scheme on stochastic min-max problem. I believe the contributions are of great interest for the community and the resulting proposal is conceptually simple, easy to implement with minimum modification from known algorithms. The exposition is clear with nice explanation of the design principle (second-order matching to a known deterministic convergent method) and the relevant literature is thoroughly surveyed and compared against. The technical claims are sound with supporting numerical evidence.", "weaknesses": "I've listed a few questions in the section below but I don't think there are major weakness with the paper.\n\nMinor comments: \n\n- In the second set of equations in (2), I'd recommend changing the subscript in nabla to u and v instead, or some other notation to avoid confusion.\n\n- In the definition of Assumption 3.3, it might make more sense to call each $F_i$ $L$-lipschitz (corresponding to (i)) and each $F_i$ $M$-smooth (corresponding to (ii)) - this would possibly make things more consistent with convex optimization literature. In Line 178, should it be $f$ being $L$-smooth or $F$?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer for the positive feedback and thoughtful comments. \n\n1. **On the Comments on the Notations Used (W1, W2):** \n\n    The reviewer has made valid points, and let us share our thoughts about the comments made by the reviewer. The second set of equations in (2) may cause a bit of confusion, as concerned by the reviewer. However, considering the problem formulation in Eq. $(1)$, the subscripts $x$ and $y$ are to represent which argument we are taking the derivative with respect to. In contrast, $u$ and $v$ in Eq. $(2)$ are actual points we evaluate the gradients at. This notation is consistently used throughout the paper.\n\n    Regarding the second suggestion, we realized that saying that $F_i$ is $L$-Lipschitz and $M$-smooth indeed sounds more natural, coherent to the existing literature. We will make necessary changes in the revision.\n    \n    In line 178, as the first equation in Asmp. 3.3 asserts that $F$ is $L$-Lipschitz, we would have $f$ being $L$-smooth, as in the original submission.\n\n2. **Existence of $\\varepsilon$ in the Convergence Rate (Q1):** \n\n    Please refer to the general comments. \n\n3. **Other Possible Variants of SEG-FFA (Q2):** \n\n    The weights $1/2$ in the convex combination $(12)$ are judiciously chosen so that SEG-FFA achieves second-order matching, under the choice of $\\alpha_k = \\eta_k /2 $ and $\\beta_k = \\eta_k$. Our Prop. D.1 demonstrates what happens when we choose other convex combinations. It is indeed possible to choose $\\alpha_k$, $\\beta_k$, and the weight $\\theta$ in the convex combination as long as Eq. (29) achieves an error of $\\mathcal{O}(\\eta^3)$ à la Prop. 5.3. \n        \n4. **On the Idea of Tail Averaging (Q3):** \n\n    Based on our current understanding, the benefits of the averaging technique (in minimization problems) mostly comes from applying Jensen's inequality. However, in minimax problems where a possibly nonconvex function $||F(\\cdot)||$ is used as an optimality measure, we are not sure how averaging could be applied. We would also like to remark that this inability to apply Jensen's inequality to $||F(\\cdot)||$ was overlooked in [17], leading to an invalid convergence result.\n        \n5. **Appearence of the Noise Parameters $\\rho$ and $\\sigma$ (Q4):** \n\n    Please refer to the general comments.\n\n6. **Extending to Independent Sampling (Q5):** \n\n    As we work in the context of random reshuffling schemes, the correct update rule for the independent-sample setting is less clear than in the same-sample setting. The main challenge in generalizing our framework to independent-sample SEGs thus lies in interpreting it in terms of random reshuffling, rather than in technical difficulties. Nonetheless, should we aim to devise an independent-sample method, the simplest way would be to use two independently chosen permutations, one for the extrapolation step and the other for the update step. For such a method, Eq. (8) reads $w_i^k = z_i^k - \\alpha T_i^k z_i^k$,  $z_{i+1}^k = z_i^k - \\beta T_{\\pi(i)}^k w_i^k$ for some permutation $\\pi:[n]\\to[n]$. Accordingly, the right hand side of Eq. (11) then becomes ${\\alpha\\beta} \\sum_{j=0}^{N-1} DT_{\\pi(j)}^k (z_0^k) T_j^k z_0^k + {\\beta^2} \\sum_{ i < j }  DT_{\\pi(j)}^k (z_0^k) T_i^k z_0^k$. It is not difficult to check that the exact same choices of $\\alpha$, $\\beta$, and $\\theta$ used in the same-sample SEG-FFA will also achieve second-order matching in the independent-sampling case. As our convergence analyses are valid for generic methods that achieve the second-order matching property (recall the statements of Theorems F.5 and G.4), we expect that it is possible to derive analogous results for the independent-sample variant of SEG-FFA, but there remain details to be checked of course.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "QhCZRm9oQp", "reviewer": "Reviewer_k7BS", "summary": "The paper studies unconstrained (strongly)-monotone finite sum minimization problems. They introduce a new scheme called SEG-FFA which:\n\ni) for a given epoch runs stochastic extragradient (SEG) with possibly two different stepsizes\nii) uses flip-flop shuffling per epoch\niii) uses the average of the epoch initialization and the last iterate as the initialization for the next epoch\n\nWith $K$ being the number of epochs and $n$ being the number of finite sum elements, they show:\n\n- For the monotone case a $\\tilde{\\mathcal O}(1/K^{1/3})$ rate for the squared norm of the operator.\n- For the $\\mu$-strongly-monotone case a $\\mathcal O(\\exp{(-\\mu K^\\epsilon)\\Vert z^0_0 - z^\\star \\lVert^2} + \\tfrac{1}{nK^{4-5\\epsilon}})$ rate where $\\epsilon \\in (0,2/3)$.", "questions": "See weaknesses.", "limitations": "The paper lacks appropriate discussion on the rates obtained in the main results of Thm. 5.4-5.5 (see weaknesses).", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The paper reads very well in terms of laying out what problem is being addressed and the current landscape of the literature (including the extended discussion in the appendix). The reasoning behind their algorithmic construction is also very clear.", "weaknesses": "My main concern is with the strength of the results:\n\n- Regarding the monotone case (Thm. 5.4): The argument seems to be that one _full epoch_ of SEG-FFA can approximate one step of the deterministic EG accurately. In other words, the rate has no dependency on $n$. Why not instead simply run full batch EG which would get the much faster $\\mathcal O(1/K)$ rate? (e.g. using gradient accumulation to make it memory efficient)\n- Regarding the strongly-monotone case (Thm. 5.5): There is a tradeoff in the rate. If we want fast rate for the stochastic term $\\mathcal O(\\tfrac{1}{nK^{4-5\\epsilon}})$ we need to take $\\varepsilon \\rightarrow 0$ in which case the linear rate $\\mathcal O(\\exp{(-\\mu K^\\epsilon)\\Vert z^0_0 - z^\\star \\lVert^2})=\\mathcal O(\\exp{(-\\mu)\\Vert z^0_0 - z^\\star \\lVert^2})$ cannot be made small. Even if we ask to just match the lowerbound $\\mathcal O(\\tfrac{1}{nK^{3}})$ on SGDA-RR and SEG-RR we run into trouble.  Pick $\\epsilon=1/5$ to get $\\mathcal O(\\exp{(-\\mu K^{1/5})\\Vert z^0_0 - z^\\star \\lVert^2} + \\tfrac{1}{nK^{3}})$. If we plot the two terms (ignoring the constants) we will see that the linear rate dominates the polynomial term for even very large $K$ (100M+). In other words, it is unfair to compare only the polynomial terms in this case, and the benefit of SEG-FFA over e.g.  SEG-RR is much less clear when the linear term is taken into account.\n\nOther concerns:\n\n- Regarding Thm. 4.1: It seems surprising that it is possible to show divergence for e.g. SEG-US (with two stepsizes) since this is the scheme that [24] shows converges almost surely. How is it possible for these two results to coexist?\n- Currently the rates do not state dependencies on noise parameters. It is good practice to include $\\rho$ and $\\sigma$ in the rates as we should expect different dependencies.\n- Table 1 currently does not include the dependency on the initialization in the rate for SEG-FFA, which can be misleading. I suggest also including the rate $\\mathcal O(\\exp{(-\\mu^2 K)\\Vert z^0_0 - z^\\star \\lVert^2} + \\tfrac{1}{nK^2})$ of e.g. SEG-RR [17, Thm. 2.1] to make the smaller dependency on $K$ in the linear rate apparent.\n\nMinor:\n\n- SEG-RR/SEG-FF is already introduced using two stepsizes, so it is slightly confusing when EG+ is introduced in (7) and contrasted with EG as being a version with two stepsizes. You might also want to shortly comment that strictly speaking the method you consider is not an instance of [16] as you consider a _larger_ second stepsize as oppose to a smaller second stepsize.\n\nRelated work:\n\n- Apart from mention KM iterations it might be worth referencing the Lookahead algorithm for minimax https://arxiv.org/pdf/2006.14567 (LA–ExtraGrad, for which also two different stepsizes are considered, is essential equivalent to SEG-FFA but without flipflip)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the effort made by the reviewer in inspecting our manuscript. \n\n1. **Monotone Case: Why Not Use Full Batch? (W1):** \n\n     This point, raised by the reviewer, is valid. However, in practice, shuffling-based stochastic methods are prevalent; it is not an exaggeration to say that they are now the *de facto* standard. While shuffling-based stochastic minimization is now relatively well understood, there has been limited progress on studies that theoretically support using shuffling-based stochastic minimax optimization methods.  In particular, it was unknown whether shuffling is beneficial in the monotone setting. The main purpose of our study is to enhance our understanding of this already widely used sampling scheme.\n\n    Just to add our two cents: in minimization problems, recall that SGD is asymptotically slower than GD,  as SGD only converges sublinearly on strongly convex problems while GD enjoys linear convergence. In spite of that, SGD and its variants are used everywhere in practice,  whereas full-batch GD appears rarely. We believe the machine learning community has reached a consensus that using SGD has benefits beyond textbook convergence rates, such as better generalization properties and implicit regularization; see for example `[A]` and `[B]`, and we refer to `[C, Chapter 9]` for an in-depth discussion. It is natural to expect similar benefits in minimax problems if stochastic methods are used, but to reach that state, we first have to understand the convergence properties of stochastic minimax methods. Thus, we believe our work is an important step forward in this direction.\n\n2. **Tradeoff in the Convergence Rate for Strongly Monotone Problems (W2):** \n\n    We have realized that the convergence rate in the original submission was derived suboptimally regrading $\\varepsilon$, and a slight modification in the final few steps of the proof makes the exponent of the exponentially decaying term to depend on $K$ instead of $K^\\varepsilon$. Please refer to the general comments for the details.         \n\n3. **Theorem 4.1 vs. Hsieh et al. (W3):**\n\n    Hsieh et al. [24] use independent-sample SEG, while we consider same-sample SEG. Thus, the two results can coexist. Our focus lies on the same-sample strategy as it combines more naturally with shuffling-based schemes.  Please refer to the paragraph on lines 57–65, and the footnote in the same page.\n\n4. **Dependencies on Noise Parameters (W4):** \n\n     Please refer to the general comments. \n\n5. **On How Rates are Demonstrated in Table 1 (W5):** \n\n    Considering that an improved rate (regarding the exponentially decaying term) has now been obtained, we now could safely say that omitting the exponentially decaying term does not give a decisive advantage to us.  In fact, as we can see from Table 1 in [17] as an example, it is customary to hide the logarithmic dependencies when one summarizes the convergence rates into a table, while deferring the exact formulae to the theorem statements. We hope that the reviewer will agree that, given the improved exponential term, omitting the exponential terms in the table is no longer misleading.\n\n6. **On Using Two Stepsizes (W6):** \n\n    We are indeed using the term EG in a broad sense, allowing it to use two stepsizes. Hence we introduced the update rule of EG using two stepsizes from the beginning, in (2). However, while we admittedly have not made this point clear enough, we do not assume any explicit constraints on $\\alpha_k$ and $\\beta_k$, unlike [16] which only considers when $\\alpha_k \\geq \\beta_k$.\n\n    Also, while the inner iteration of SEG-FFA does use $\\alpha = \\beta/2$, thanks to the anchoring step, the overall update of the epoch sums up to the \"standard\" EG as introduced by Korpelevich [27]), modulo a small noise. Hence, our method is not *completely* different from [16].\n\n    We understand that these might cause slight confusions. We will try to find a way to present this clearer in our revision. \n\n7. **Additional Related Work (W7):**\n\n    Thank you for notifying us about the related work.  We agree with you on that there is an interesting resemblance between SEG-FFA and the mentioned Lookahead methods, and we will add a comment on it in our revision.\n\nWe hope that our response resolves your concerns. We would greatly appreciate it if you could consider re-evaluating our paper. Thank you.\n\n> [A] On Large-Batch Training for Deep Learning, Keskar et al. (2017)\n>        \n> [B] On the Generalization Benefit of Noise in Stochastic Gradient Descent, Smith et al. (2020)\n>\n> [C] Understanding Deep Learning, S.J.D. Prince (2023)", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We thank all the reviewers for their constructive feedback. Here, we would like to discuss some important
issues commonly raised by the reviewers.

1. **On the Convergence Rate in the Strongly Monotone Setting ([k7BS] W2, [hmmd] Q1, [19M7] W2):** 

    One of the common questions raised by the reviewers was about the parameter $\varepsilon$ in the convergence rate derived in the strongly monotone setting. Admittedly, in our original submission, we were more or less satisfied with getting a rate that is provably faster than the $\Omega(1/nK^3)$ lower bound of SEG-RR, hence the rate we derived remained having an additional obscure parameter $\varepsilon$. However, reading the comments from the reviewers, and following the suggestion of one of the reviewers, we revisited our analyses to see if we can optimize the rate with respect to $\varepsilon$. Surprisingly, with a slight modification in the proofs, we were able to remove the dependency on $\varepsilon$ and derive a rate of $\mathbb{E} \|\| z_0^K - z^*\|\|^2 \leq \exp \left( - \frac{b \mu^2 K}{L^2}  \right)  \|\|z_0^{0} - z^*\|\|^2 + \mathcal{O}\left(\frac{\left(\log(n^{1/4} K)\right)^{4}}{ n  K^{4}} \right)$ for a constant $b$ that does not depend on $\mu$, $L$, $n$, and $K$. 

    Since we cannot make a revision of our paper during the discussion phase, please allow us to briefly explain how our proofs can be modified to obtain a new rate of $\tilde{\mathcal{O}}(1/nK^4)$ below.  We are more than happy to take follow-up questions if anyone wishes for further verifications/clarifications. 

    First we modify Lemma F.4, so that the number of epoch $K$ is no longer involved: more precisely, we show that using a constant stepsize (possibly independent of $K$) it holds that $\|\| F z^k\|\| \leq \|\| F z^0\|\| + V_1 / (\mu L)$ for all $k = 0, 1, \dots$. The trick is simple. In the current form of Lemma F.4 we show that $\|\|Fz^{k+1}\|\|$ is bouned by $\|\|Fz^k\|\|$ plus some error term; see Eq. (95). However, by choosing a smaller stepsize it is not difficult to improve this bound to $(1-\frac{\mu \eta n}{10}) \|\|Fz^k\|\|$ plus some error term. This "exponential decay with an error" type of recurrence also arises in the analysis of SGD on stongly convex problems (see, *e.g.*, Thm. 5.8 in arXiv:2301.11235), so we can use standard techniques with mathematical induction to unroll this recurrence and get the claimed bound.  

    With this modification, in Thm. F.5, we then have that the inequality right below line 1057 holds whenever $\eta$ is sufficiently small, regardless of the choice of $K$. Again unravelling this ``exponential decay with an error'' type recurrence, one gets $\mathbb{E} \|\| z^K - z^* \|\|^2 \leq \left(1 - \frac{1}{2} \mu \eta n \right)^K \|\| z^{0} - z^* \|\|^2 + \frac{4+2\mu \eta n}{\mu^2} \cdot \eta^{2a-2} n^{2a-3} V_2$ , for any $K \geq 0$. Compare this with the first line of Eq. (101), which was obtained by a slightly looser unravelling of the same recurrence. However, unlike Eq. (101) where $\eta$ was already constrained to be $\mathcal{O}(1/K^{1-\varepsilon})$ due to (the unmodified) Lemma F.4, we have no dependency of $\eta$ on $K$ yet. So we can choose $\eta$ now, to have the best dependency on $K$ that minimizes the bound. We set $\eta$ to be $\mathcal{O}(\log(K) / K)$, inspired by the convergence analyses made in p. 26 of [17]. It is then easily able to show the $\tilde{\mathcal{O}}(1/nK^4)$ rate claimed above.



2. **Dependence of Convergence Rates on the Noise Parameters $\rho$ and $\sigma$ ([k7BS] Q4, [hmmd] Q4):** 

    As mentioned by the reviewers, it is indeed good practice to write down the dependencies on the problem-dependent constants as explicitly as possible. However, the dependencies of the convergence rates on $\rho$ and $\sigma$ are quite involved (see, *e.g.*, Theorems E.9 and E.13), so we decided to highlight the concise versions of the rates in the main text, while deferring the exact details to the appendices. We hope the reviewers generously understand this as our effort to find the sweet spot between readability and rigor.



3. **What is $\eta_k$ in Theorem 5.4? ([jRnf] Q1, [19M7] Q2):**

    We admit that the relationship between the step sizes $\alpha_k,\beta_k$ and $\eta_k$ for the SEG-FFA  was not clearly stated. Following Prop. 5.3, regarding equations (5) and (6) in the case of SEG-FFA, we selected step sizes $\alpha_k = \beta_k/2$ and $\beta_k = \eta_k$ for some sequence $\eta_k$, $k \geq 0$. This was implicitly assumed in Thm. 5.4 (and only written explicitly in Alg. 4). We will clarify this by adding that we choose $\alpha_k = \beta_k/2$ and $\beta_k = \eta_k$ in the statement of Thm. 5.4.

Meta-review: This paper introduces a new algorithm, SEG-FFA, which successfully converges for the convex-concave minimax problem, whereas existing algorithms such as SEG-RR and SEG-FF fail to converge for this class of problems. Additionally, the authors establish both upper and lower bounds in the strongly convex-strongly concave setting, demonstrating that SEG-FFA achieves a provably faster convergence rate compared to other shuffling-based methods.

All reviewers agree that the paper is clearly written and presents a novel approach of significant interest. Some questions were raised regarding assumptions about Hessian Lipschitzness, hyperparameter settings, and comparisons with EG. These concerns have been satisfactorily addressed in the authors' responses. Therefore, I recommend acceptance.
Decision: Accept (poster)