Stochastic Extragradient with Flip-Flop Shuffling & Anchoring: Provable Improvements

Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 11:13:17

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.

Main paper: 
 introduction: 
 Minimax problems with a finite-sum structure, which are optimization problems of the formEQUATIONcan be found in many interesting applications in machine learning, such as generative adversarial networks (GANs) (Goodfellow et al., 2014) , adversarial training (M ądry et al., 2018) , multi-agent reinforcement learning (Wai et al., 2018) , fair classification (Mohri et al., 2019) , and so on. Deterministic methods for minimax problems, such as gradient descent-ascent (GDA) (Arrow & Hurwicz, 1956) and extragradient (EG) (Korpelevich, 1976) , 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 x and concave on y. On the other hand, EG finds an optimum under this convex-concave setting (Gorbunov et al., 2022b) , and moreover, attains a convergence rate faster than GDA (Azizian et al., 2020) when f is strongly convex on x and strongly concave on y.In contrast, attempts to construct stochastic variants of these algorithms have not been so fruitful.When f is convex-concave, stochastic gradient descent-ascent (SGDA) clearly can diverge, as the deterministic GDA does not. To make matters worse, stochastic extragradient (SEG) methods have also had limited success on convex-concave problems. As we summarize in Section 2 in more detail, existing versions of SEG and their analyses have limitations that hinder its application to general unconstrained convex-concave problems, such as uniformly bounded gradient variance, bounded domain, increasing batch size, monotonicity of components, and/or absence of convergence rates.In the context of finite-sum optimization, most existing theoretical studies on stochastic methods (including the aforementioned results) have long been based on the with-replacement sampling scheme.In with-replacement sampling, at each iteration t an index i(t) is independently and uniformly sampled among {1, . . . , n}. Such a sampling scheme is relatively easy to theoretically analyze, because the sampled f i(t) is an unbiased estimator of the full objective function f . In practice, however, inspired by the empirical observations of faster convergence (Bottou, 2009; Recht & Ré, 2013) , the without-replacement sampling schemes have been the de facto standard. Among them, the most popular one 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 is being closed by the recent breakthroughs in stochastic gradient descent (SGD), namely that SGD with RR leads to a provably faster convergence compared to with-replacement SGD when the number of epochs is large enough (Nagaraj et al., 2019; Ahn et al., 2020; Mishchenko et al., 2020a; Nguyen et al., 2021; Yun et al., 2021; 2022) . This has motivated further studies on finding other shuffling-based sampling schemes that can improve upon RR, resulting in the discoveries such as the flip-flop scheme (Rajput et al., 2022) and GraB (Lu et al., 2022; Cha et al., 2023) . The flip-flop scheme is a particularly simple yet interesting modification of RR with improved rates in quadratic problems: a random permutation is used twice in a single epoch (i.e., two passes over n components in an epoch), but the order is reversed in the second pass.The aforementioned 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 as strongly-convex-strongly-concave objectives (Das et al., 2022) , or f satisfying the Polyak-Łojasiewicz condition (Cho & Yun, 2023) . Despite the superiority of EG over GDA, SEG with shuffling has not yet been investigated in the literature, and the promising achievements in SGDA motivates us to study the following question:Can shuffling schemes provide improved convergence guarantees for SEG, in unconstrained convex-concave and strongly-convex-strongly-concave settings?More specifically, we are interested in developing shuffling-based variants of SEG with minimal modifications to the algorithm in unconstrained finite-sum minimax problems, and showing that (a) in convex-concave settings, the new method reaches an optimum with a guarantee on the rate of convergence, overcoming the aforementioned limitations of existing results; (b) in strongly-convexstrongly-concave settings, the method converges faster than existing SGDA/SEG variants.In this paper, we propose the stochastic extragradient with flip-flop anchoring (SEG-FFA) method, which is SEG amended with the techniques of flip-flop sampling scheme and anchoring.1 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 1 for a summary).For clarity, we use SEG-US to refer to with-replacement SEG (US for uniform sampling).• We first study SEG with RR (SEG-RR) and SEG with flip-flop (SEG-FF), and find out that shuffling alone does not fix the divergence issue of SEG-US 2 in convex-concave functions.In particular, we demonstrate that SEG-RR and even SEG-FF still fail to converge in the convex-concave setting, by constructing an explicit counterexample (Theorem 4.2).• We next investigate the underlying cause for the nonconvergence of SEG-RR and SEG-FF, and a way to remedy this issue. In particular, we identify that either they fail to match the update equation of the reference method EG beyond first-order Taylor expansion terms, or attempting to match both the firstand second-order Taylor expansion terms results in divergence (Proposition 5.2). By adopting a simple technique called 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).Table 1 : Summary of upper/lower bounds. Pseudocode of algorithms can be found in Appendix A. We only display terms that become dominant for sufficiently large T and K. To compare the with-replacement versions (-US) against shuffling-based versions, one can substitute T = nK. The optimality measure used for SC-SC problems is E[∥ ẑz * ∥ 2 ] for the last iterate ẑ. For C-C problems, we consider mint=0,...,T E[∥F zt∥ 2 ] for with-replacement methods and min k=0,...,K E[ F z k 0 2 ] for shuffling-based methods.Strongly-Convex-Strongly-Concave Convex-Concave Upper BoundLower Bound Upper Bound Lower Bound SGDA-US O( 1T ) (Loizou et al., 2021 ) Ω( 1 T ) (Cho & Yun, 2023) N/A Ω(1) (as GDA) SEG-US O( 1T ) (Gorbunov et al., 2022a ) Ω( 1 T ) (Beznosikov et al., 2020) N/A Ω(1) (Thm. 4.2) † SGDA-RR Õ( 1 nK 2 ) (Das et al., 2022 ) Ω( 1 nK 3 ) (Thm. 5.6) N/A Ω(1) (as GDA) SEG-RR O( 1 nK 2-3ε ) (Thm. 4.1) Ω( 1 nK 3 ) (Thm. 5.6) N/A Ω(1) (Thm. 4.2) SEG-FF O( 1 nK 2-3ε ) (Thm. 4.1) -N/A Ω(1) (Thm. 4.2) SEG-FFA O( 1 nK 4-5ε ) (Thm. 5.5) -Õ( 1 K 1/3 ) (Thm. 5.4) - † Hsieh et al. ( 2020) also show Ω(1) bounds, but for independent-sample SEG with stepsize αt = βt.• We prove that SEG-FFA enjoys improved convergence guarantees, as anticipated by our second-order matching principle. Most importantly, we show that SEG-FFA achieves a convergence rate of Õ( 1 /K 1/3 ) when f is convex-concave. This result is in stark contrast to other baseline algorithms that diverge under this setting (see the last column of Table 1 ), and it overcomes limitations of existing SEG results on unconstrained setups.• Moreover, we show that when f is strongly-convex-strongly-concave, SEG-FFA achieves a convergence rate of O( 1 /nK 4-5ε ) for any fixed 0 < ε < 2 /3, where K denotes the number of epochs (Theorem 5.5). Additionally, by proving lower bounds Ω( 1 /nK 3 ) for the convergence rates of SGDA-RR and SEG-RR under the same setting (Theorem 5.6), we show that SEG-FFA has a provable advantage over these baseline algorithms. 
related works: 
 Extragradient and EG+ Extragradient method (Korpelevich, 1976 ) is a widely used minimax optimization method, well-known for resolving the nonconvergence issue of GDA on convex-concave problems. It has been observed by Mokhtari et al. (2020) that this advantage of EG over GDA comes from the fact that the Taylor expansion of update equations of EG and the proximal point (PP) method (Martinet, 1970) match each other up to the second-order terms, i.e., O(η 3 ) approximation error when η is the stepsize. In contrast, GDA matches PP only up to first-order terms, being an approximation with error O(η 2 ).In this paper, we also consider EG+ (Diakonikolas et al., 2021) , which is a generalization of EG.The update rule of EG+ is defined, for stepsizes {η 1,k } k≥0 and {η 2,k } k≥0 , asEQUATION)If f is convex-concave, Diakonikolas et al. (2021) show that EG+ reaches an optimum when η 1,k ≥ η 2,k . In particular, when η 1,k = η 2,k , we recover the standard EG by Korpelevich (1976) .Shuffling and flip-flop As previously described, shuffling-based stochastic methods can outperform the methods based on with-replacement sampling, both in theory and in practice. One key property of shuffling-based methods is that, while the individual estimators become biased as they become 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 (Ahn et al., 2020) and in SGDA with RR (Das et al., 2022) , the overall progress made within each epoch exactly matches their deterministic counterparts up to the first-order, leaving an error as small as O(η 2 ) , where η is the stepsize. Rajput et al. (2022) observe that, when each component functions are convex quadratics, then using flip-flop on SGD can reduce the error further to O(η3 ), resulting in an even faster convergence.Stochastic Variants of Extragradient While EG improves upon GDA, unfortunately, SEG has not been able to show a clear advantage over SGDA. To the best of our knowledge, for general unconstrained convex-concave problems, the existing stochastic variants of EG and their analyses face several limitations: (i) many assume that the components have uniformly bounded gradient variance (Diakonikolas et al., 2021; Cai et al., 2022; Pethick et al., 2023) , which becomes particularly restrictive for unconstrained setups (see discussion after Assumption 4) 3 ; (ii) some (implicity) require that the domain is bounded (Juditsky et al., 2011; Mishchenko et al., 2020b) ; (iii) some require increasing the batch size for convergence (Diakonikolas et al., 2021; Cai et al., 2022) ; (iv) sometimes each stochastic component is assumed to be monotone (Mishchenko et al., 2020b) ; (v) convergence is proved without the above four restrictions in (Hsieh et al., 2020) , albeit for independent-sample SEG, but the result lacks a convergence rate. Variance reduction techniques have also been considered (Carmon et al., 2019; Alacaoglu & Malitsky, 2022) , but in this case the access to the full objective function f (or its gradient) is assumed. We note that our proposed SEG-FFA overcomes the aforementioned limitations, and reaches an optimum with an explicit rate in unconstrained convexconcave problems, under relatively mild conditions. The readers may also refer to Beznosikov et al. (2023) for a comprehensive overview on this topic.It is worth mentioning that the gradient operator F i arising from a quadratic function f i is M -smooth with M = 0. Notice also that, by the finite-sum structure F = 1 n n i=1 F i , it is then clear that Assumption 3 implies f being L-smooth and F being M -smooth. The L-smoothness assumption on the objective functions is standard in the optimization literature, while the M -smoothness assumption on the saddle gradients may look less standard. This smoothness assumption on the saddle gradient (or the Lipschitz Hessian condition) for analyzing SEG-FFA stems from the analysis of the flip-flop sampling scheme (Rajput et al., 2022) . In particular, this is needed for bounding the high-order error terms between the (deterministic) EG and SEG-FFA in Section 5.1. Indeed, existing analysis of flip-flop sampling (Rajput et al., 2022) is limited to quadratic functions that trivially have the 0-Lipschitz Hessian, so our analysis is a step forward. Admittedly, the Lipschitz Hessian condition may still look rather strong, but we would like to also point out that this assumption does not lead to unfair comparisons against other algorithms; we show our divergence and lower bound results (Theorems 4.2 and 5.6) for the baseline algorithms using quadratic functions (i.e., M = 0). We leave studying how one can remove this assumption as an interesting future work. Assumption 4 (Component Variance). There exist constants ρ ≥ 0 and σ ≥ 0 such thatEQUATIONIn the existing works studying stochastic optimization methods for minimax problems, it is almost always the case where Assumption 4 with ρ = 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, one can easily check that setting ρ = 0 prohibits any "noise" in the bilinear terms in component functions. For machine learning applications also, it has been reported that this assumption often fails to hold (Beznosikov et al., 2023) .Allowing the variance to grow with the gradient F z makes the assumption much more realistic. 
shuffling alone is not enough in monotone cases: 
 Under the settings we have discussed, let us study the consequences of applying shuffling-based sampling schemes to SEG. First we describe the precise methods of our consideration, namely the SEG-RR and SEG-FF.For k ≥ 0, in the beginning of an epoch, a random permutation τ k is sampled from a uniform distribution over S n . Then, for n iterations, we use each of the component functions once, in the order determined by τ k . That is, for i = 0, 1, . . . , n -1 we doEQUATIONfor some stepsizes α k and β k . In case of using SEG-RR, the epoch is completed here, and we set z k+1 0 ← z k n as the initial point for the next epoch. In case of SEG-FF, we perform n more iterations in the epoch, as proposed in Rajput et al. (2022) . In these additional iterations, the component functions are each used once more, but in reverse order. That is, for i = n, n + 1, . . . , 2n -1, we doEQUATIONThen we set z k+1 0 ← z k 2n as the initial point for the next epoch. The full pseudocode of these methods can be found in Appendix A.When F is strongly monotone, it is possible to show that both SEG-RR and SEG-FF indeed provide speed-up over SEG-US, by proving a O( 1 /nK 2-3ε ) rate of convergence for a small ε > 0. Theorem 4.1. Suppose that F is µ-strongly monotone with µ > 0, Assumptions 3, 4 hold, and we are running either SEG-RR or SEG-FF for K epochs. For any given ε ∈ (0, 1 /2), let the stepsize be chosen to be a constant α k = β k = ω nK 1-ε for a sufficiently small constant ω. Then we achieve the boundEQUATION)Proof. See Section 6 for the proof sketch, and the appendices referred therein for the full proof.The well-known convergence rate of SEG-US under strong monotonicity of F is Θ( 1 /T ), where T is the total number of iterations (Gorbunov et al., 2022a; Beznosikov et al., 2020) . Translating this rate to our shuffling-based setting, where there are Θ(n) iterations per epoch, this rate amounts to Θ( 1 /nK). Therefore, Theorem 4.1 shows that simply by controlling the order of how component functions are sampled we can have an improvement in the speed of convergence when K is large enough. Considering that SGDA-RR and PP with RR achieves the rate of Õ( 1 /nK 2 ) in the strongly monotone setting (Das et al., 2022) , the performance of SEG-RR and SEG-FF is on par with the existing known methods.However, it turns out that the benefit of shuffling does not extend further beyond the "easy" strongly monotone setting. In fact, when F is merely monotone, then in the worst case, SEG-RR and SEG-FF suffers from nonconvergence, just as in the case of SEG-US.Theorem 4.2. For n = 2, there exists a minimax problem with f (x, y) = 1 2 2 i=1 f i (x, y) having a monotone F , consisting of L-smooth quadratic f i 's satisfying Assumption 4 with (ρ, σ) = (1, 0), such that SEG-US, SEG-RR and SEG-FF diverge in expectation for any positive stepsizes.Proof. We provide the explicit counterexample and the proof of divergence in Appendix G.1. In particular, for SEG-US we showE[∥F z t+1 ∥ 2 ] > E[∥F z t ∥ 2 ]for all iterations t ≥ 0, and for SEG-RR and SEG-FF, we showE[ F z k+1 0 2 ] > E[ F z k 0 2 ] for all epochs k ≥ 0. These results indicate that min t=0,...,T E[∥F z t ∥ 2 ] = Ω(1) for SEG-US and min k=0,...,K E[ F z k 0 2 ] = Ω(1)for SEG-RR and SEG-FF, as summarized in Table 1 .5 SEG-FFA: SEG WITH FLIP-FLOP ANCHORINGIn 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. Our analysis is in line with the existing analysis showing the superiority of EG over GDA by comparing how close they are to the PP updates (Mokhtari et al., 2020) and also the analysis of shuffling-based SGD as an approximation of GD updates (Ahn et al., 2020; Rajput et al., 2022) .As an outcome of our analysis, we will propose adding a simple anchoring step at the end of each epoch of SEG-FF. After the 2n iterations described by ( 6) and ( 7), for a predetermined constant θ k ≥ 0 we perform an additional averaging of the initial iterate z k 0 and the last iterate z k 2n :EQUATIONwhen setting the initial point for the next epoch. As both flip-flop and anchoring are used, we call this method Stochastic ExtraGradient with Flip-Flop Anchoring (SEG-FFA). The particular choice of parameters we employ is α k = β k/2 and θ k = 1. One may check the pseudocode of SEG-FFA, presented as Algorithm 4 in Appendix A, to see the precise description of the method. 
designing seg-ffa via second-order matching: 
 Let us provide a sketch of the motivations behind introducing the anchoring step (9) and our choice of the parameters α k = β k/2 and θ k = 1. Proof details are deferred to Section 6 and Appendix C.As observed by Mokhtari et al. (2020) , 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 as small as O(η 3 ) per iteration, where η is the stepsize. On the other hand, GDA and PP show a difference of O(η 2 ), 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 (Diakonikolas et al., 2021) , and Taylor-expand it as the following:EQUATIONEG+ is known to converge for unconstrained monotone problems if η 1 ≥ η 2 . When η 1 = η 2 , it recovers EG and matches PP up to second-order terms.Based on these observations, we now state our key principle for designing a convergent version of SEG: second-order matching. We would like to choose proper stepsizes, sampling scheme, and anchoring scheme so that our without-replacement SEG can deterministically match the update equation of a convergent algorithm (EG/PP or EG+) up to the O(η 2 ) terms (i.e., second-order terms).We show that (a) this second-order matching can be achieved with flip-flop anchoring, but not solely by permutation-based 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 1. SEG-RR suffers a poor approximation error of O(η 2 ) 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 (η 2 = 2η 1 ) that make EG+ diverge (Proposition 5.2). 3. SEG-FFA matches EG up to second-order terms to get an error of O(η 3 ) (Proposition 5.3), achieving convergence in monotone problems (Theorem 5.4) unlike SEG-RR or SEG-FF.To this end, consider a general form of SEG that incorporates any arbitrary sampling scheme and anchoring. More precisely, in a certain "epoch," the components are chosen in the order ofT 0 , T 1 , • • • , T N -1, where T i ∈ {F 1 , . . . , F n } for each i, and N is some multiple of n (e.g., N = n for SEG-RR, N = 2n for SEG-FF/SEG-FFA). Then, given α, β, and θ, we perform SEG updatesEQUATIONfor i = 0, 1, . . . , N -1, and then the anchoring stepEQUATIONso that z ♯ is used as the initial point of the next epoch. For this method, we show the following. Proposition 5.1. Suppose that Assumption 3 holds. For some ϵ N = o (α + β) 2 , it holds thatEQUATIONSee Appendix C.1 for the proof. Comparing (10) with (13), for them to match up to the second-order, η 2 n n j=1EQUATIONEQUATIONmust hold simultaneously. Clearly, without-replacement sampling will make (14) hold. However, it is easy to check that random reshuffling falls short of making (15) hold. This is because, if RR is used, then T 0 , T 1 , . . . , T n-1 is nothing but a reordering of F 1 , . . . , F n into F τ (1) , . . . , F τ (n) , so the RHS of (15) can only contain terms DF τ (j) (z 0 )F τ (i) z 0 with i ≤ j.This observation motivates the use of flip-flop sampling, because choosing T i = T 2n-1-i lets the RHS of (15) "cover" all required terms DF j (z 0 )F i z 0 . Indeed, flip-flop does resolve this issue, but there is still one complication remaining for SEG-FF, as described below. Proposition 5.2. Suppose we use flip-flop sampling. Without anchoring, or equivalently when θ = 0, in order to make (14) and (15) hold, we have to choose β = η1 /n and α = β /2. However, such a choice leads to η 2 = 2η 1 , which is the set of parameters that fails to make EG+ converge.The details can be found in Appendix C.2. This result shows that anchoring is necessary to get a stochastic method that achieves second-order matching to a convergent method. Now, say we actually use anchoring. Introducing the parameter θ increases the degree of freedom, and it opens up multiple possible stepsizes and parameters that make ( 14) and ( 15) hold. We show that α k = β k/2 and θ k = 1 are the simplest choices that, in fact, lead to the second-order matching to EG (instead of the more general EG+). A more precise statement is in Theorem 6.1.Proposition 5.3. Suppose that F is µ-strongly monotone with µ ≥ 0, and Assumptions 3 and 4. Then, for β k = η, α k = β k/2, and θ k = 1, SEG-FFA becomes an approximation of EG with error at most O(η 3 ). In other words, we achievez 0 -ηnF (z 0 -ηnF z 0 ) -z ♯ = O(η 3 ).As a result of the second-order matching, we obtain SEG-FFA, a stochastic method that has an error of O(η 3 ) as an approximation of EG. Achieving this order of magnitude for the approximation error turns out to be the key to the exact convergence to an optimum under the monotone setting, as demonstrated in the following result. Theorem 5.4. Suppose that F is monotone, Assumptions 2, 3, 4 hold, and we use SEG-FFA. By choosing the stepsizes sufficiently small and decaying at the rate of η k = O( 1 /k 1/3 log k), the iterates generated by SEG-FFA achieves the bound ofEQUATION)Proof. For the full statement of the theorem and its proof, see Appendix F.The reduced error also shows a 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 will be beneficial in the convergence of a method. Theorem 5.5. Suppose that F is µ-strongly monotone with µ > 0, Assumptions 3, 4 hold, and we are running SEG-FFA for K epochs. For any given ε ∈ (0, 2 /3), let the stepsize be a constant equal to α k = β k = ω nK 1-ε for a sufficiently small constant ω. Then we achieve the boundEQUATIONProof. See Section 6 for the proof sketch, and the appendices referred therein for the full proof.Notice the exponent of 4 -5ε in the convergence rate, which is twice as large as the exponent 2 of SGDA-RR and 2 -3ε of 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 Ω( 1 /nK 3 ). This exhibits that there is a provable gap between those methods and SEG-FFA, which attains O( 1 /nK 4-5ε ).Theorem 5.6. Suppose n ≥ 2. For both SGDA-RR with constant stepsize α k = α > 0 and SEG-RR with constant stepsize α k = α > 0, β k = β > 0, there exists a µ-strongly monotone minimax problem f (z) = 1 n n i=1 f i (z) with µ > 0 such that regardless of stepsizes, we haveE z K 0 -z * 2 =    Ω σ 2 LµnK if K ≤ L/µ, Ω Lσ 2 µ 3 nK 3 if K > L/µ.Proof. The full statement and proof are presented in Appendix G.2.In Appendix H, we present experiments to numerically validate our convergence and divergence analyses. We conducted experiments spanning monotone and strongly monotone cases. The experiments also include a comparison against existing convergent independent-sample SEG method by Hsieh et al. (2020) , and an ablation study testing the effect of anchoring applied to uniform sampling and random reshuffling versions of SEG. 
proof sketches: 
 Let us briefly sketch the proofs of the convergence results we have presented in the previous sections. To this end, the statements shown in this section may be slightly informal. The precise statements and the details are deferred to the appendices.Let us focus on the upper bounds of convergence. For the moment, we are only interested in the sequence {z k 0 } k≥0 , so for convenience let us drop the subscripts and write z k to denote z k 0 . The cumulative updates made within an epoch can decomposed into a sum of an exact EG update and a within-epoch error term, which we denote by r k , asEQUATION)The quality of the method will depend on how small the "noise" term r k is, as the noise will in general hinder the convergence. It turns out that, regardless of the method that is in use, the noise term can be bounded using a unified format, as follows. The proof can be found in Appendix D.2. Theorem 6.1. Suppose that F is µ-strongly monotone with µ ≥ 0, and Assumptions 3, 4 hold. For each of SEG-RR, SEG-FF, and SEG-FFA, there exists a choice of stepsizes that makes the following hold: For an exponent a that depends on the method, there exist constantsC 1 , D 1 , V 1 , C 2 , D 2 ,and V 2 , all independent of η k and n, such that the error term r k satisfies a deterministic boundr k ≤ η a k n a C 1 F z k + η a k n a D 1 F z k 2 + η a k n a V 1 (19) and a bound that holds on expectationEQUATION)Furthermore, the exponent is a = 2 for SEG-RR and SEG-FF, and a = 3 for SEG-FFA.In other words, SEG-FFA has an error that is order of magnitude smaller then other methods. Thus, it is now intuitively clear that SEG-FFA should have an advantage in the convergence.When F is µ-strongly monotone with µ > 0, all SEG-RR, SEG-FF, and SEG-FFA do not diverge.In this case, it is possible to establish the following unified analysis of the methods. Theorem 6.2. Suppose that F is µ-strongly monotone with µ > 0, Assumptions 3, 4 hold, and an optimization method whose within-epoch error satisfies (19) and (20) is run for K epochs. Then, for any given ε ∈ (0, 1 -1 /a), by choosing a constant stepsize η k = ω nK 1-ε for a sufficiently small constant ω, we achieve the boundEQUATION)For the precise statement of this result and its proof, see Appendix E. As the polynomial decay will dominate the exponential decay for large enough K, the bound we get is essentially O( 1 /K 2a-2-(2a-1)ε ). For SEG-RR and SEG-FF where a = 2, we get the upper bound O( 1 /K 2-3ε ), and for SEG-FFA where a = 3 we get the upper bound O( 1 /K 4-5ε ).When F is non-strongly monotone, as shown in Theorem 4.2, SEG-RR and SEG-FF diverge in the worst case. On the other hand, thanks to the second-order matching, the reduced error O(η 3 ) of SEG-FFA provides us convergence. See Appendix F for the precise statement on the convergence rate and the affiliated details. 
conclusion: 
 We proposed SEG-FFA, a new stochastic variant of EG that uses flip-flop sampling and anchoring. While being a minimal modification from the vanilla SEG, SEG-FFA attains the "second-order matching" property to the deterministic EG, leading to a two-fold improved convergence. On one hand, SEG-FFA reaches an 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 a faster convergence with a provable gap from the other methods.An interesting future direction would be to extend our work to nonmonotone problems, further investigating the potentials of the second-order matching technique. Also, we note from our experiments that, while our work successfully shows the convergence of SEG-FFA, the convergence rate we derived may be suboptimal. Closing this gap between the observed convergence and the theoretical rate would be an appealing future work.  
 
 Appendix: We present the pseudocode of the algorithms we consider in this paper in Algorithms 2, 3 and 4, with the pseudocode of the with-replacement stochastic methods in Algorithm 1.Algorithm 1: SEG-US / SGDA-USThe number of components n; stepsize sequences {α t } t≥0 and {β t } t≥0 Initialize :z 0 ∈ R d1+d2 for t = 0, 1, . . . do sample i(t) uniformly from {1, . . . , n} if SGDA-US then z t+1 ← z t -α t F i(t) z t end else if SEG-US then w t ← z t -α t F i(t) z t z t+1 ← z t -β t F i(t) w t end end Algorithm 2: SEG-RR / SGDA-RR Input :The number of components n; stepsize sequences {α k } k≥0 and{β k } k≥0 Initialize : z 0 0 ∈ R d1+d2 for k = 0, 1, . . . do sample τ k uniformly from S n for i = 0 to n -1 do if SGDA-RR then z k i+1 ← z k i -α k F τ k (i+1) z k i end else if SEG-RR then w k i ← z k i -α k F τ k (i+1) z k i z k i+1 ← z k i -β k F τ k (i+1) w k i end end z k+1 0 ← z k n end Algorithm 3: SEG-FF Input :The number of components n; stepsize sequences {α k } k≥0 and{β k } k≥0 Initialize : z 0 0 ∈ R d1+d2 for k = 0, 1, . . . do sample τ k uniformly from S n for i = 0 to n -1 do w k i ← z k i -α k F τ k (i+1) z k i z k i+1 ← z k i -β k F τ k (i+1) w k i end for i = n to 2n -1 do w k i ← z k i -α k F τ k (2n-i) z k i z k i+1 ← z k i -β k F τ k (2n-i) w k i end z k+1 0 ← z k 2n end Algorithm 4: SEG-FFA 1 Input : The number of components n; stepsize sequences {η k } k≥0 2 Initialize : z 0 0 ∈ R d1+d2 3 for k = 0, 1, . . . do 4 sample τ k uniformly from S n 5 for i = 0 to n -1 do 6 w k i ← z k i -η k 2 F τ k (i+1) z k i 7 z k i+1 ← z k i -η k F τ k (i+1) w k i 8 end 9 for i = n to 2n -1 do 10 w k i ← z k i -η k 2 F τ k (2n-i) z k i 11 z k i+1 ← z k i -η k F τ k (2n-i) w k i 12 end 13 z k+1 0 ← z k 0 +z k 2n 2 14 end B USEFUL LEMMATA Lemma B.1 (Polarization identity).For any two vectors a and b, it holds that2 ⟨a, b⟩ = ∥a∥ 2 + ∥b∥ 2 -∥a -b∥ 2 = ∥a + b∥ 2 -∥a∥ 2 -∥b∥ 2 .Lemma B.2 (Weighted AM-GM inequality). For any γ > 0 and two vectors a and b in R d ,2 |⟨a, b⟩| ≤ γ ∥a∥ 2 + 1 γ ∥b∥ 2 .Proof. Notice that2 |⟨a, b⟩| ≤ 2 (|a 1 b 1 | + • • • + |a n b n |) ≤ γa 2 1 + b 2 1 γ + • • • + γa 2 d + b 2 d γ = γ ∥a∥ 2 + 1 γ ∥b∥ 2 .Lemma B.3 (Young's inequality). For any γ > 0 and two vectors a and b,∥a + b∥ 2 ≤ (1 + γ) ∥a∥ 2 + 1 + 1 γ ∥b∥ 2 .In particular, as a special case where γ = 1, it holds thatEQUATION)Lemma B.4. For any two vectors a and b, it holds that∥a -b∥ 2 ≥ 1 2 ∥a∥ 2 -∥b∥ 2 .Proof. From ( 22) it follows that∥a∥ 2 = ∥(a -b) + b∥ 2 ≤ 2 ∥a -b∥ 2 + 2 ∥b∥ 2 .Simply rearranging the terms gives us the result.The following inequality is also frequently referred to as Young's inequality, so we will also do so.Lemma B.5 (Generalized Young's inequality). For any positive scalars p 1 , . . . , p n such that p 1 + • • • + p n = 1 and vectors a 1 , . . . , a n , it holds that∥p 1 a 1 + • • • + p n a n ∥ 2 ≤ p 1 ∥a 1 ∥ 2 + • • • + p n ∥a n ∥ 2 .In particular, settingp 1 = • • • = p n = 1n and multiplying both sides by n 2 yields∥a 1 + • • • + a n ∥ 2 ≤ n ∥a 1 ∥ 2 + • • • + ∥a n ∥ 2 .Lemma B.6. Suppose that F is M -smooth. Then for any z and w it holds that∥F w -F z -DF (z)(w -z)∥ ≤ M 2 ∥w -z∥ 2 .Proof. The proof closely follows the arguments used for Lemma 1.2.4 in Nesterov (2018) , by replacing the gradients therein by saddle gradients. The fundamental theorem of calculus with the M -smoothness of F gives us∥F w -F z -DF (z)(w -z)∥ = 1 0 DF (z + t(w -z)) dt (w -z) -DF (z)(w -z) ≤ 1 0 ∥DF (z + t(w -z)) -DF (z)∥ dt ∥w -z∥ ≤ 1 0 M t ∥w -z∥ dt ∥w -z∥ = M 2 ∥w -z∥ 2 .Lemma B.7. Let F be a µ-strongly monotone operator. Let z * be a point such that F z * = 0, and let η > 0. Then, for any point z in the domain of F and w := z -ηF z, it holds that⟨F w, w -z * ⟩ ≥ µ 2 ∥z -z * ∥ 2 -η 2 µ ∥F z∥ 2 .Proof. By the µ-strong monotonicity of F and Lemma B.4 it holds that⟨F w, w -z * ⟩ ≥ µ ∥w -z * ∥ 2 = µ ∥z -ηF z -z * ∥ 2 ≥ µ 2 ∥z -z * ∥ 2 -µ ∥ηF z∥ 2 so we are done.Lemma B.8 (Nonexpansiveness of the EG operator). Let F be a monotone L-Lipschitz operator. Let z * be a point such that F z * = 0, and z be any point in the domain of F . Then, for any η > 0 it holds that∥z -ηF (z -ηF z) -z * ∥ 2 ≤ ∥z -z * ∥ 2 -η 2 (1 -η 2 L 2 ) ∥F z∥ 2 .Proof. This lemma is exactly from Gorbunov et al. (2022b) ; see Section D.7 therein.The following lemma generalizes Lemma 3.2 in Gorbunov et al. (2022b) shown for monotone F to µ-strongly monotone F .Lemma B.9. Let F be a µ-strongly monotone L-Lipschitz operator, and let z be any point in the domain of F . Then for any 0< η < 1 L √ 2 , it holds that ∥F (z -ηF (z -ηF z))∥ 2 ≤ 1 - 2ηµ 5 ∥F z∥ 2 .Proof. For convenience, let us define w := z -ηF z and z+ := z -ηF (z -ηF z) = z -ηF w.Because F is µ-strongly monotone, we haveEQUATIONAlso from the µ-strong monotonicity of F we getEQUATIONMeanwhile, from the L-Lipschitzness of F we haveEQUATION)Summing up the inequalities ( 23), ( 24), ( 25) with weights 2 /η, 1 /2η, and 3 /2 respectively, we obtainµ η 2 z + -z 2 + 1 2 w -z + 2 + 3 2 F w -F z + 2 ≤ 2 F z -F z + , F w + 1 2 F w -F z + , F w -F z + 3η 2 L 2 2 ∥F w -F z∥ 2 .From this inequality, we can exactly follow the arguments used in the proof of Lemma 3.2 in Gorbunov et al. (2022b) to derive thatEQUATION)On the other hand, Young's inequality (Lemma B.3) tells us thatη 2 ∥F z∥ 2 = ∥w -z∥ 2 ≤ 1 + 1 4 w -z + 2 + (1 + 4) z + -z 2 .This, combined with (26), implies that2ηµ 5 ∥F z∥ 2 + F z + 2 ≤ ∥F z∥ 2 .It remains to simply rearrange the terms.Lemma B.10. Let {a k } k≥0 , {b k } k≥0 , {c k } k≥0 , and {d k } k≥0 be sequences of nonnegative numbers satisfying the recurrence relationb k ≤ (1 + a k )d k -d k+1 + c k ∀k ≥ 0.Then for any k ≥ 0 it holds thatEQUATIONas this impliesk j=0 b j ≤ k j=0 b j k i=j+1 (1 + a i ) ≤   k j=0 c j k i=j+1 (1 + a i )   -d k+1 + d 0 k j=0 (1 + a j ) ≤ -d k+1 +   d 0 + k j=0 c k   k j=0(1 + a j ). (1+ a i ) = b k+1 -c k+1 + (1 + a k+1 )   k j=0 (b j -c j ) k i=j+1 (1 + a i )   ≤ b k+1 -c k+1 -(1 + a k+1 )d k+1 + d 0 k+1 j=0 (1 + a j ) ≤ -d k+2 + d 0 k+1 j=0 (1 + a j ).This shows that ( 27) holds also for k + 1, and we are done.The subsequent lemma is technical, but it can be derived from elementary calculus.Lemma B.11. For any K ≥ 1,K+2 k=2 1 k 2/3 (log k) 2 ≥ (K + 3) 1/3 (log(K + 3)) 2 . Proof. Consider integrating the function x → 1 x 2/3 (log x) 2 over the interval [2, K + 3],where the function is decreasing. An upper Riemann sum is an upper bound for an integral, so we haveEQUATION)Now consider a function g : [1, ∞) → R, defined asg(y) := y+3 2 1 x 2/3 (log x) 2 dx - (y + 3) 1/3 (log(y + 3)) 2 .Differentiating, we getg ′ (y) = 2 (y + 3) 2/3 (log(y + 3)) 3 + 2 3(y + 3) 2/3 (log(y + 3)) 2 > 0 whenever y ≥ 1. That is, g is increasing on y ≥ 1.It is easy to verify that g(1) ≥ 0; one way to do so is, for Ei( • ) denoting the exponential integral function (Abramowitz & Stegun, 1965, Chapter 5) , to use the indefinite integral1 x 2/3 (log x) 2 dx = 1 3 Ei log x 3 - 3 √ x log x (29)to numerically evaluate g(1). Since g is increasing, we have g(y) ≥ g(1) ≥ 0 for all y ≥ 1. This, with (28), implies thatK+2 k=2 1 k 2/3 (log k) 2 ≥ K+3 2 1 x 2/3 (log x) 2 dx ≥ (K + 3) 1/3 (log(K + 3)) 2holds whenever K ≥ 1, which is exactly the claimed.In Section 5.1, we considered the method where, in an epoch, the iterates are generated following the recurrenceEQUATION)for i = 0, 1, . . . , N -1, where each T i are sampled from the set {F 1 , . . . , F n }, and an additional anchoring stepz ♯ := z N + θz 0 1 + θ (31)is performed so that z ♯ is used as the initial point of the next epoch. In this section we would like to prove the following two statements regarding this update rule. Proposition C.1 (Proposition 5.1). It holds thatz ♯ = z 0 - β 1 + θ N -1 j=0 T j z 0 + αβ 1 + θ N -1 j=0 DT j (z 0 )T j z 0 + β 2 1 + θ 0≤i<j≤N -1 DT j (z 0 )T i z 0 + ϵ N 1 + θ (32) for some ϵ N = o (α + β) 2 .Proof. Equation (32) immediately follows from Proposition C.2, with (34) giving us the precise definition of ϵ N . To show that ϵ N = o (α + β) 2 , we begin with noting that both ∥z j -z 0 ∥ and ∥w j -z 0 ∥ are of O(α + β), because both z j and w j are obtained from z 0 by performing at most j updates following (30). Thus, the first term in the right hand side of ( 34) is of O(β(α + β) 2 ) by Lemma B.6, and the remaining terms are of O((α + β) 3 ) by the L-smoothness of the operators F 1 , . . . , F n .Proposition C.2. For any i = 0, 1, . . . , N , it holds thatEQUATION)where we denoteEQUATIONProof. We use induction on i. There is nothing to show for the base case i = 0. Now, suppose that (33) and ( 34) hold for some i < N , and writez i+1 = z i -βT i w i = z i -βT i z 0 -βDT i (z 0 )(w i -z 0 ) -β T i w i -T i z 0 -DT i (z 0 )(w i -z 0 ) .Here, notice that by the update rule we havew i = z i -αT i z i = z 0 -β i-1 j=0 T j w j -αT i z i .Using this identity and the induction hypothesis we getz i+1 = z 0 -β i-1 j=0 T j z 0 + αβ i-1 j=0 DT j (z 0 )T j z 0 + β 2 0≤k<j≤i-1 DT j (z 0 )T k z 0 + ϵ i -βT i z 0 -βDT i (z 0 )   -β i-1 j=0 T j w j -αT i z i   -β T i w i -T i z 0 -DT i (z 0 )(w i -z 0 ) = z 0 -β i-1 j=0 T j z 0 + αβ i-1 j=0 DT j (z 0 )T j z 0 + β 2 0≤k<j≤i-1 DT j (z 0 )T k z 0 + ϵ i -βT i z 0 + β 2 DT i (z 0 ) i-1 j=0 T j z 0 + β 2 DT i (z 0 ) i-1 j=0 (T j w j -T j z 0 ) + αβDT i (z 0 )(T i z i -T i z 0 ) + αβDT i (z 0 )T i z 0 -β T i w i -T i z 0 -DT i (z 0 )(w i -z 0 ) = z 0 -β i j=0 T j z 0 + αβ i j=0 DT j (z 0 )T j z 0 + β 2 0≤k<j≤i DT j (z 0 )T k z 0 + ϵ i + β 2 DT i (z 0 ) i-1 j=0 (T j w j -T j z 0 ) + αβDT i (z 0 )(T i z i -T i z 0 ) -β T i w i -T i z 0 -DT i (z 0 )(w i -z 0 ) = z 0 -β i j=0 T j z 0 + αβ i j=0 DT j (z 0 )T j z 0 + β 2 0≤k<j≤i DT j (z 0 )T k z 0 + ϵ i+1which asserts that (33) also holds for i + 1.Here we prove the following. Proposition C.3 (Proposition 5.2). Suppose we use flip-flop sampling. Without anchoring, or equivalently when θ = 0, in order to make (14) and (15) hold, we have to choose β = η1 /n and α = β /2. However, such a choice leads to η 2 = 2η 1 , which is the set of parameters that fails to make EG+ converge.Proof. Suppose that we have already established the upcoming Lemma C.4. Then, according to Lemma C.4, for (15) to hold with θ = 0, the following system of equations should be satisfied:     η 1 η 2 = 2n 2 β 2 , η 1 η 2 = n 2 (2αβ + β 2 ), η 2 = 2nβ.Solving this system of equations, we get η 1 = nβ, η 2 = 2nβ, and α = β /2.For the latter part of the statement on the divergence of EG+ with η 2 = 2η 1 , consider the (1 + 1)dimensional bilinear problem minx max y xy whose unique optimum is z * = (0, 0). A simple computation shows thatF z = 0 1 -1 0 z.Consequently, for any η > 0, the update rule of EG+ with η 1 = η and η 2 = 2η amounts toz + = z -2ηF (z -ηF z) = 1 -2η 2 -2η 2η 1 -2η 2 z. It follows that z + -z * 2 = 1 -2η 2 -2η 2η 1 -2η 2 x y 2 = (1 -2η 2 )x -2ηy 2 + 2ηx + (1 -2η 2 )y 2 = (1 + 4η 4 )(x 2 + y 2 ) = (1 + 4η 4 ) ∥z -z * ∥ 2 .Therefore, the distance from the optimal solution strictly increases every iterate.It remains to actually prove Lemma C.4. Lemma C.4. When flip-flop sampling is used, it holds thatαβ 1 + θ N -1 j=0 DT j (z 0 )T j z 0 + β 2 1 + θ 0≤i<j≤N -1 DT j (z 0 )T i z 0 = 2αβ + β 2 1 + θ n j=1 DF j (z 0 )F j z 0 + 2β 2 1 + θ i̸ =j DF j (z 0 )F i z 0 .Proof. As we are using flip-flop sampling, we have N = 2n, and it is clear thatN -1 j=0 DT j (z 0 )T j z 0 = 2 n j=1 DF j (z 0 )F j z 0 .For the second term, asT i = T 2n-1-i , we have 0≤i<j≤2n-1 DT j (z 0 )T i z 0 = 0≤i<j≤n-1 DT j (z 0 )T i z 0 + n≤i<j≤2n-1 DT j (z 0 )T i z 0 + n-1 i=0 2n-2-i j=n DT j (z 0 )T i z 0 + n-1 i=0 2n-1 j=2n-i DT j (z 0 )T i z 0 + n-1 i=0 DT 2n-1-i (z 0 )T i z 0 = 0≤i<j≤n-1 DT j (z 0 )T i z 0 + 0≤j<i≤n-1 DT j (z 0 )T i z 0 + n-1 i=0 n-1 j=i+1 DT j (z 0 )T i z 0 + n-1 i=0 i-1 j=0 DT j (z 0 )T i z 0 + n-1 i=0 DT i (z 0 )T i z 0 = 2 0≤i<j≤n-1 DT j (z 0 )T i z 0 + 2 0≤j<i≤n-1 DT j (z 0 )T i z 0 + n-1 i=0 DT i (z 0 )T i z 0 .The claimed identity can be obtained by taking the weighted sum of the two results.D MISSING PROOFS FOR SECTION 6.1In this section, although it is an abuse of notation, for convenience we will write F i to denote the saddle gradient of the component function chosen in the i th iteration. More precisely, for indices i = 0, 1, . . . , n -1 we denote F τ (i+1) by F i . Similarly, in cases of considering SEG-FF or SEG-FFA, for i ≥ n we denote F τ (2n-i) by F i . Also, we omit the superscripts and subscripts denoting the epoch number k unless strictly necessary, as all the iterates that we consider will be from the same epoch.We consider the iterates generated by the update ruleEQUATION)Note that ξ = 1 /2 for SEG-FFA, and ξ = 1 for SEG-RR and SEG-FF.For j = 1, . . . , 2n we defineEQUATIONEQUATIONEQUATIONEQUATIONWe set Σ 0 = Ψ 0 = 0, as they are empty sums. Notice that δ j is a random variable that depends on the permutation τ .Meanwhile, by triangle inequality it is immediate that∥g j ∥ ≤ j ∥F z 0 ∥ + δ j ,and by Young's inequality it holds thatEQUATION)EQUATION)Proof. By the fundamental theorem of calculus for line integrals and the update rule (35), we havew i = z i -ξηF i z i = z i -ξηF i z 0 -ξη(F i z i -F i z 0 ) = z i -ξηF i z 0 -ξη 1 0 DF i (z 0 + t(z i -z 0 )) dt (z i -z 0 )and similarlyz i+1 = z i -ηF i w i = z i -ηF i z 0 -η(F i w i -F i z 0 ) = z i -ηF i z 0 -η 1 0 DF i (z 0 + t(w i -z 0 )) dt (w i -z 0 ).EQUATIONthe update rule can be rewritten using these quantities asEQUATIONEQUATION)Subtracting z 0 from both sides of (43) we getEQUATIONand plugging this into (44) gives usEQUATIONFor convenience let us defineC i := I -ηB i + ξη 2 B i A i , P i,ℓ := C i C i-1 . . . C ℓ+2 C ℓ+1and P i,i := I as it denotes an empty product. Observe that for any j we haveEQUATION)Also note that for any ℓ it holds that(I -ξηB ℓ+1 ) -C ℓ+1 (I -ξηB ℓ ) = (I -ξηB ℓ+1 ) -I -ηB ℓ+1 + ξη 2 B ℓ+1 A ℓ+1 (I -ξηB ℓ ) = ξη(B ℓ+1 + B ℓ ) -ξη 2 B ℓ+1 (A ℓ+1 + B ℓ ) + ξ 2 η 3 B ℓ+1 A ℓ+1 B ℓand henceEQUATION)Unravelling the recurrence relation ( 46) we getz i+1 -z 0 = C i (z i -z 0 ) -η (I -ξηB i ) F i z 0 = C i C i-1 (z i-1 -z 0 ) -η (I -ξηB i-1 ) F i-1 z 0 -η (I -ξηB i ) F i z 0 = P i,i-2 (z i-1 -z 0 ) -η i ℓ=i-1 P i,ℓ (I -ξηB ℓ ) F ℓ z 0 = P i,i-2 C i-2 (z i-2 -z 0 ) -η (I -ξηB i-2 ) F i-2 z 0 -η i ℓ=i-1 P i,ℓ (I -ξηB ℓ ) F ℓ z 0 = P i,i-3 (z i-2 -z 0 ) -η i ℓ=i-2 P i,ℓ (I -ξηB ℓ ) F ℓ z 0 . . . = P i,-1 (z 0 -z 0 ) -η i ℓ=0 P i,ℓ (I -ξηB ℓ ) F ℓ z 0and thereforeEQUATIONIn order to compute the bound for ∥z i -z 0 ∥, we use summation by parts to get1 η (z 0 -z i ) = i-1 ℓ=0 P i-1,ℓ (I -ξηB ℓ ) F ℓ z 0 = P i-1,i-1 (I -ξηB i-1 ) i-1 ℓ=0 F ℓ z 0 - i-2 ℓ=0 (P i-1,ℓ+1 (I -ξηB ℓ+1 ) -P i-1,ℓ (I -ξηB ℓ )) ℓ j=0 F ℓ z 0 = (I -ξηB i-1 ) g i - i-2 ℓ=0 (P i-1,ℓ+1 (I -ξηB ℓ+1 ) -P i-1,ℓ (I -ξηB ℓ )) g ℓ+1 .Here, observe thatP i-1,ℓ+1 (I -ξηB ℓ+1 ) -P i-1,ℓ (I -ξηB ℓ ) = C i-1 C i-2 . . . C ℓ+2 ((I -ξηB ℓ+1 ) -C ℓ+1 (I -ξηB ℓ ))so by using ( 47) and ( 48) we obtain∥P i-1,ℓ+1 (I -ξηB ℓ+1 ) -P i-1,ℓ (I -ξηB ℓ )∥ ≤ 2ξηL + 2ξη 2 L 2 + ξ 2 η 3 L 3 1 + ηL + ξη 2 L 2 i-ℓ-2 .Therefore, we conclude that∥z i -z 0 ∥ ≤ η (1 + ξηL) ∥g i ∥+η 2 L 2ξ + 2ξηL + ξ 2 η 2 L 2 i-2 ℓ=0 1 + ηL + ξη 2 L 2 i-ℓ-2 ∥g ℓ+1 ∥ .Meanwhile, substituting (49) back to (45) gives usEQUATIONFor i > ℓ let us defineR i,ℓ := ξ -1 (I -ξηA i ) P i-1,ℓ (I -ξηB ℓ ) = ξ -1 (I -ξηA i ) C i-1 C i-2 . . . C ℓ+2 C ℓ+1 (I -ξηB ℓ )and for convenience R i,i := I so that (50) can be rewritten asEQUATION)Applying summation by parts on the above, we obtain1 ξη (z 0 -w i ) = R i,i i ℓ=0 F ℓ z 0 - i-1 ℓ=0 (R i,ℓ+1 -R i,ℓ ) ℓ j=0 F j z 0 = g i+1 - i-1 ℓ=0 (R i,ℓ+1 -R i,ℓ )g ℓ+1and as a consequence we getEQUATION)It remains to bound ∥R i,ℓ+1 -R i,ℓ ∥. For the special case where ℓ = i -1, a direct computation leads toR i,i -R i,i-1 = I -ξ -1 (I -ξηA i ) (I -ξηB i-1 ) = (1 -ξ -1 )I + ηA i + ηB i-1 -ξη 2 A i B i-1and thus we have∥R i,i -R i,i-1 ∥ ≤ (1 -ξ -1 ) + 2ηL + ξη 2 L 2 .(53) For the other cases; that is, when ℓ < i -1, we haveR i,ℓ+1 -R i,ℓ = ξ -1 (I -ξηA i ) C i-1 C i-2 . . . C ℓ+2 ((I -ξηB ℓ+1 ) -C ℓ+1 (I -ξηB ℓ ))so by using ( 47) and ( 48) we get the bound∥R i,ℓ+1 -R i,ℓ ∥ ≤ ξ -1 (1 + ξηL) 2ξηL + 2ξη 2 L 2 + ξ 2 η 3 L 3 1 + ηL + ξη 2 L 2 i-ℓ-2 . (54)Applying ( 53) and ( 54) on ( 52) gives the bound for ∥w i -z 0 ∥. Proposition D.2. Suppose that SEG-FFA is used, η < 1 nL , and let ν := 1 + 1 2n . Then for any i = 1, . . . , 2n -1 we have the bounds∥z i -z 0 ∥ ≤ ηνi + ην 2 e 2 i(i -1) 2n ∥F z 0 ∥ + ηνδ i + η 2 Lν 2 e 2 Σ i-1 , ∥w i -z 0 ∥ ≤ η 2 1 + 2ν 2 i + ν 3 e 2 i(i -1) n ∥F z 0 ∥ + η 2 δ i+1 + η(2ν 2 -1) 2 δ i + η 2 Lν 3 e 2 Σ i-1 , ∥w i -z 0 ∥ 2 ≤ 3η 2 (i + 1) 2 2 + 3η 2 (2ν 2 -1) 2 i 2 2 + η 2 ν 6 e 4 i(i -1) 2 (2i -1) n 2 ∥F z 0 ∥ 2 + 3η 2 2 δ 2 i+1 + 3η 2 (2ν 2 -1) 2 2 δ 2 i + 6η 2 ν 6 e 4 (i -1) n 2 Ψ i-1 .Proof. Using elementary calculus one can show that x → (1 + 1 x + 1 2x 2 ) x increases on x > 0 and is bounded above by e. Hence for all 0 ≤ ℓ < i ≤ 2n we have1 + ηL + η 2 L 2 2 i-ℓ-2 ≤ 1 + 1 n + 1 2n 2 2n ≤ e 2 .Applying the definitions ( 37) and ( 38) on (40) and then substituting ξ = 1 /2 we get∥z i -z 0 ∥ ≤ η 1 + ηL 2 ∥g i ∥ + η 2 L 1 + ηL 2 2 i-2 ℓ=0 1 + ηL + η 2 L 2 2 i-ℓ-2 ∥g ℓ+1 ∥ ≤ ην (i ∥F z 0 ∥ + δ i ) + η 2 Lν 2 i-2 ℓ=0 e 2 ((ℓ + 1) ∥F z 0 ∥ + δ ℓ+1 ) ≤ ην (i ∥F z 0 ∥ + δ i ) + ην 2 e 2 i(i -1) 2n ∥F z 0 ∥ + η 2 Lν 2 e 2 Σ i-1 .Similarly, from (41) we get∥w i -z 0 ∥ ≤ η 2 ∥g i+1 ∥ + η 2 1 + 2ηL + η 2 L 2 2 ∥g i ∥ + η 2 L 1 + ηL 2 3 i-2 ℓ=0 1 + ηL + η 2 L 2 2 i-ℓ-2 ∥g ℓ+1 ∥ ≤ η 2 ((i + 1) ∥F z 0 ∥ + δ i+1 ) + η 2 1 + 2 n + 1 2n 2 (i ∥F z 0 ∥ + δ i ) + η 2 Lν 3 i-2 ℓ=0 e 2 ((ℓ + 1) ∥F z 0 ∥ + δ ℓ+1 ) ≤ η 2 (1 + 2iν 2 ) ∥F z 0 ∥ + ην 3 e 2 i(i -1) 2n ∥F z 0 ∥ + η 2 δ i+1 + η(2ν 2 -1) 2 δ i + η 2 Lν 3 e 2 Σ i-1 .Finally, applying generalized Young's inequality on (41) we get∥w i -z 0 ∥ 2 ≤ 3η 2 4 ∥g i+1 ∥ 2 + 3η 2 4 1 + 2ηL + η 2 L 2 2 2 ∥g i ∥ 2 + 3 η 2 L 1 + ηL 2 3 i-2 ℓ=0 1 + ηL + η 2 L 2 2 i-ℓ-2 ∥g ℓ+1 ∥ 2 .Using generalized Young's inequality once more on the last term gives us3 η 2 L 1 + ηL 2 3 i-2 ℓ=0 1 + ηL + η 2 L 2 2 i-ℓ-2 ∥g ℓ+1 ∥ 2 ≤ 3 ην 3 e 2 n i-2 ℓ=0 ∥g ℓ+1 ∥ 2 ≤ 3η 2 ν 6 e 4 (i -1) n 2 i-2 ℓ=0 ∥g ℓ+1 ∥ 2 .Plugging this back yields∥w i -z 0 ∥ 2 ≤ 3η 2 4 ∥g i+1 ∥ 2 + 3η 2 4 1 + 2ηL + η 2 L 2 2 2 ∥g i ∥ 2 + 3η 2 ν 6 e 4 (i -1) n 2 i-2 ℓ=0 ∥g ℓ+1 ∥ 2 ≤ 3η 2 4 2(i + 1) 2 ∥F z 0 ∥ 2 + 2δ 2 i+1 + 3η 2 4 2ν 2 -1 2 2i 2 ∥F z 0 ∥ 2 + 2δ 2 i + 3η 2 ν 6 e 4 (i -1) n 2 i-2 ℓ=0 2(ℓ + 1) 2 ∥F z 0 ∥ 2 + 2δ 2 ℓ+1 ≤ 3η 2 2 (i + 1) 2 ∥F z 0 ∥ 2 + δ 2 i+1 + 3η 2 2 2ν 2 -1 2 i 2 ∥F z 0 ∥ 2 + δ 2 i + η 2 ν 6 e 4 i(i -1) 2 (2i -1) n 2 ∥F z 0 ∥ 2 + 6η 2 ν 6 e 4 (i -1) n 2 Ψ i-1 .Now the claimed inequalities can be obtained simply by rearranging the terms appropriately.Proposition D.3. Suppose that either SEG-RR or SEG-FF is used with α = β = η < 1 nL , and let ν := 1 + 1 n . Then for any i = 1, . . . , 2n -1 we have the bounds∥z i -z 0 ∥ ≤ ηνi + 16ην 2 i(i -1) n ∥F z 0 ∥ + ηνδ i + 32η 2 Lν 2 Σ i-1 , ∥w i -z 0 ∥ ≤ η 1 + iν 2 + 16ν 3 i(i -1) n ∥F z 0 ∥ + ηδ i+1 + η(ν 2 -1)δ i + 32η 2 Lν 3 Σ i-1 , ∥w i -z 0 ∥ 2 ≤ 6η 2 (i + 1) 2 + 6η 2 (1 + ν) 2 i 2 n 2 + 1024η 2 ν6 i(i -1) 2 (2i -1) n 2 ∥F z 0 ∥ 2 + 6η 2 δ 2 i+1 + 6η 2 (1 + ν) 2 n 2 δ 2 i + 6144η 2 ν6 (i -1) n 2 Ψ i-1 .Proof. One can verify that x → (1 + 4 3x ) x increases on x ≥ 3 and is bounded above by e 4/3 < 4. With noting that (1+ 1 1 + 1 1 2 ) 1 = 3 < 4, (1 + 1 2 + 1 2 2 ) 2 = 49 16 < 4, and 1 + 1 x + 1 x 2 ≤ 1 + 4 3xwhenever x ≥ 3, we see that for all 0 ≤ ℓ < i ≤ 2n it holds that1 + ηL + η 2 L 2 i-ℓ-2 ≤ 1 + 1 n + 1 n 2 2n ≤ 4 2 = 16.Also, we have2 + 2ηL + η 2 L 2 ≤ 2 + 2 n + 1 n 2 = 1 + ν2 ≤ 2ν 2 .Applying the definitions ( 37) and ( 38) on ( 40) and then substituting ξ = 1 we get∥z i -z 0 ∥ ≤ η (1 + ηL) ∥g i ∥ + η 2 L 2 + 2ηL + η 2 L 2 i-2 ℓ=0 1 + ηL + η 2 L 2 i-ℓ-2 ∥g ℓ+1 ∥ ≤ ην (i ∥F z 0 ∥ + δ i ) + 2η 2 Lν 2 i-2 ℓ=0 16 ((ℓ + 1) ∥F z 0 ∥ + δ ℓ+1 ) ≤ ην (i ∥F z 0 ∥ + δ i ) + 16ην 2 i(i -1) n ∥F z 0 ∥ + 32η 2 Lν 2 Σ i-1 .Similarly, from (41) we get∥w i -z 0 ∥ ≤ η ∥g i+1 ∥ + η 2 L (2 + ηL) ∥g i ∥ + η 2 L(1 + ηL) 2 + 2ηL + η 2 L 2 i-2 ℓ=0 1 + ηL + η 2 L 2 i-ℓ-2 ∥g ℓ+1 ∥ . ≤ η ((i + 1) ∥F z 0 ∥ + δ i+1 ) + η n 2 + 1 n (i ∥F z 0 ∥ + δ i ) + η 2 Lν 2ν 2 i-2 ℓ=0 16 (ℓ ∥F z 0 ∥ + δ ℓ ) . ≤ η(1 + iν 2 ) ∥F z 0 ∥ + 16ην 3 i(i -1) n ∥F z 0 ∥ + ηδ i+1 + η(ν 2 -1)δ i + 32η 2 Lν 3 Σ i-1 .Finally, applying Young's inequality on (41) we get∥w i -z 0 ∥ 2 ≤ 3η 2 ∥g i+1 ∥ 2 + 3η 2 (2 + ηL) 2 n 2 ∥g i ∥ + 3 η 2 L(1 + ηL) 2 + 2ηL + η 2 L 2 i-2 ℓ=0 1 + ηL + η 2 L 2 i-ℓ-2 ∥g ℓ+1 ∥ 2 ≤ 3η 2 ∥g i+1 ∥ 2 + 3η 2 (2 + ηL) 2 n 2 ∥g i ∥ + 3 2ην 3 n i-2 ℓ=0 16 ∥g ℓ+1 ∥ 2 .Using Young's inequality once more on the last term gives us3 32ην 3 n i-2 ℓ=0 ∥g ℓ+1 ∥ 2 ≤ 3072η 2 ν6 (i -1) n 2 i-2 ℓ=0 ∥g ℓ+1 ∥ 2 .Plugging this back yields∥w i -z 0 ∥ 2 ≤ 3η 2 ∥g i+1 ∥ 2 + 3η 2 (2 + ηL) 2 n 2 ∥g i ∥ + 3072η 2 ν6 (i -1) n 2 i-2 ℓ=0 ∥g ℓ+1 ∥ 2 ≤ 6η 2 (i + 1) 2 ∥F z 0 ∥ 2 + δ 2 i+1 + 6η 2 (2 + ηL) 2 n 2 i 2 ∥F z 0 ∥ 2 + δ 2 i + 6144η 2 ν6 (i -1) n 2 i-2 ℓ=0 (ℓ + 1) 2 ∥F z 0 ∥ 2 + δ 2 ℓ+1 ≤ 6η 2 (i + 1) 2 ∥F z 0 ∥ 2 + δ 2 i+1 + 6η 2 (1 + ν) 2 n 2 i 2 ∥F z 0 ∥ 2 + δ 2 i + 1024η 2 ν6 i(i -1) 2 (2i -1) n 2 ∥F z 0 ∥ 2 + 6144η 2 ν6 (i -1) n 2 Ψ i-1 .Now the claimed inequalities can be obtained simply by rearranging the terms appropriately.Lemma D.4. For any j = 1, . . . , 2n, it deterministically holds thatEQUATIONProof. For any set of indices J ⊂ {0, . . . , n -1}, by Assumption 4 it holds thati∈J ∥F i z 0 -F z 0 ∥ 2 ≤ n-1 i=0 ∥F i z 0 -F z 0 ∥ 2 ≤ n(ρ ∥F z 0 ∥ + σ) 2 .Hence, for any j = 1, . . . , n we have∥g j -jF z 0 ∥ 2 = j-1 i=0 F i z 0 -jF z 0 2 ≤ j j-1 i=0 ∥F i z 0 -F z 0 ∥ 2 ≤ jn(ρ ∥F z 0 ∥ + σ) 2 ≤ n 2 (ρ ∥F z 0 ∥ + σ) 2 ,and for any j = n + 1, . . . , 2n we haveEQUATIONTherefore, in any case we have∥g j -jF z 0 ∥ 2 ≤ n 2 (ρ ∥F z 0 ∥ + σ) 2 .Taking square roots on both sides gives us the desired bound.Lemma D.5. For any j = 1, . . . , 2n, it holds thatEQUATIONProof. If n = 1 then the left hand side is always 0, so there is nothing to show. So, we may assume that n ≥ 2. Then, for any j = 1, . . . , n, using (Mishchenko et al., 2020a , Lemma 1) we obtainE τ 1 j g j -F z 0 2 ≤ n -j j(n -1) (ρ ∥F z 0 ∥ + σ) 2 .Multiplying both sides by j 2 and applying AM-GM inequality leads toE τ ∥g j -jF z 0 ∥ 2 ≤ j(n -j) n -1 (ρ ∥F z 0 ∥ + σ) 2 ≤ n 2 4(n -1) (ρ ∥F z 0 ∥ + σ) 2 ≤ n 2 (ρ ∥F z 0 ∥ + σ) 2 .Meanwhile, for j = n + 1, . . . , 2n, following the first few steps in (56) we get∥g j -jF z 0 ∥ 2 = n-1 i=2n-j F i z 0 -(j -n)F z 0 2Applying (Mishchenko et al., 2020a , Lemma 1) here, we getE τ ∥g j -jF z 0 ∥ 2 = E τ n-1 i=2n-j F i z 0 -(j -n)F z 0 2 = (j -n) 2 E τ 1 j -n n-1 i=2n-j F i z 0 -F z 0 2 ≤ (j -n) 2 • n -(j -n) (j -n)(n -1) (ρ ∥F z 0 ∥ + σ) 2 ≤ (j -n)(2n -j) n -1 (ρ ∥F z 0 ∥ + σ) 2 .Using AM-GM inequality on the last line gives usE τ ∥g j -jF z 0 ∥ 2 ≤ (j -n)(2n -j) n -1 (ρ ∥F z 0 ∥+σ) 2 ≤ n 2 4(n -1) (ρ ∥F z 0 ∥+σ) 2 ≤ n 2 (ρ ∥F z 0 ∥+σ) 2 .Thus, for any case, we have (57).Lemma D.6. For any k, ℓ ∈ {0, 1, . . . , 2n}, it holds thatEQUATION)Proof. Expanding the product Σ k Σ ℓ and writing in terms of δ, we getΣ k Σ ℓ = k i=1 δ i   ℓ j=1 δ j   = k i=1 ℓ j=1 δ i δ j ≤ k i=1 ℓ j=1 δ 2 i + δ 2 j 2where the last line follows from the AM-GM inequality. Taking the expectation with respect to τ and using the bound from Lemma D.5, we obtainE τ [Σ k Σ ℓ ] ≤ 1 2 k i=1 ℓ j=1 E τ [δ 2 i ] + E τ [δ 2 j ] ≤ 1 2 k i=1 ℓ j=1 n(ρ ∥F z 0 ∥ + σ) 2 2 + n(ρ ∥F z 0 ∥ + σ) 2 2 = kℓn(ρ ∥F z 0 ∥ + σ) 2 2which is exactly the claimed.Lemma D.7. For any k, ℓ ∈ {0, 1, . . . , 2n}, it holds thatEQUATION)Proof. Expanding the product in the left hand side of (59) and applying (58), we getE τ   k i=1 Σ i   ℓ j=1 Σ j     = E τ   k i=1 ℓ j=1 Σ i Σ j   = k i=1 ℓ j=1 E τ [Σ i Σ j ] ≤ k i=1 ℓ j=1 ijn(ρ ∥F z 0 ∥ + σ) 2 2 ≤ k(k + 1)ℓ(ℓ + 1)n(ρ ∥F z 0 ∥ + σ) 2 8 .The full proof of Theorem 6.1 is quite long and technical, so we divide it into several parts. First we show that ( 19) and ( 20) holds with a = 3 when SEG-FFA is in use. Then we show that Theorem 6.1 also holds for SEG-FF in Appendix D.2.3, and for SEG-RR in Appendix D.2.4.In this section we prove the following. Theorem D.8. Say we use SEG-FFA. Then, as long as the stepsize used in an epoch satisfiesEQUATIONfor constantsEQUATIONEQUATIONEQUATION)We first list the intermediate results. The actual proof of Theorem D.8 is in page 37, at the end of this section. Proposition D.9. For using SEG-FFA, the within-epoch update z ♯ (12) satisfiesz ♯ = z 0 -nηF (z 0 -nηF z 0 ) + rwhere we denoteEQUATIONProof. Setting α = η /2, β = η, and θ = 1 in (13), we getz ♯ = z 0 - η 2 2n-1 j=0 F j z 0 + η 2 4 2n-1 j=0 DF j (z 0 )F j z 0 + η 2 2 0≤k<j≤2n-1 DF j (z 0 )F k z 0 + 1 2 ϵ 2n (65)where ϵ 2n is defined as in (34). Recall that F i = F 2n-1-i for all i = 0, 1, . . . , 2n-1, and moreover,n-1 i=0 F i = 2n-1i=n F i = nF . Thus, the first sum in the above is equal to 2nF z 0 , and the second sum is equal to 2 n-1 j=0 DF j (z 0 )F j z 0 . For the last sum, observe that 0≤k<j≤2n-1DF j (z 0 )F k z 0 = 0≤k<j≤n-1 DF j (z 0 )F k z 0 + n≤k<j≤2n-1 DF j (z 0 )F k z 0 + 0≤k≤n-1 n≤j≤2n-1 DF j (z 0 )F k z 0 = 0≤k<j≤n-1 DF j (z 0 )F k z 0 + n-1≥k>j≥0 DF j (z 0 )F k z 0 + 0≤k≤n-1 n-1≥j≥0 DF j (z 0 )F k z 0 = 2 k̸ =j DF j (z 0 )F k z 0 + n-1 j=0 DF j (z 0 )F j z 0 .Hence, ( 65) is equivalent toz ♯ = z 0 -nηF z 0 + η 2 2 n-1 j=0 DF j (z 0 )F j z 0 + η 2 2 0≤k<j≤2n-1 DF j (z 0 )F k z 0 + 1 2 ϵ 2n = z 0 -nηF z 0 + η 2 n-1 j=0 DF j (z 0 )F j z 0 + η 2 k̸ =j DF j (z 0 )F k z 0 + 1 2 ϵ 2n = z 0 -nηF z 0 + η 2   n-1 j=0 DF j (z 0 )     n-1 j=0 F j z 0   + 1 2 ϵ 2n = z 0 -nηF z 0 + n 2 η 2 DF (z 0 )F z 0 + 1 2 ϵ 2n .Observing that the terms (64b), (64c), and (64d) add up to 1 2 ϵ 2n completes the proof.Proposition D.10. Suppose that η < 1 nL , and let ν := 1 + 1 2n . Then the noise term satisfies the bound∥r∥ ≤ η 3 n 3 L 2 ∥F z 0 ∥ 1 2n 1 + 2e 2 3 + 4ν + e 2 3 + η 3 n 3 M ∥F z 0 ∥ 2 1 2 + 4ν 4 + 16νe 4 5 + 3η 3 M 8   Ψ 2n + (2ν 2 -1) 2 Ψ 2n-1 + 4ν 6 e 4 n 2 2n-2 j=1 jΨ j   + η 3 L 2 (ν + 1) 4 Σ 2n-1 + η 3 L 2 ν 2 (1 + ηLe 2 ) 2 2n-2 j=1 Σ j + η 4 L 3 ν 3 e 2 2 2n-2 k=1 (2n -k -1)Σ k-1 .Proof. We bound each line in equation ( 64). For (64a), we use Lemma B.6 to getnηF (z 0 -nηF z 0 ) -nηF z 0 + n 2 η 2 DF (z 0 )F z 0 ≤ nηM 2 ∥-nηF z 0 ∥ 2 = n 3 η 3 M 2 ∥F z 0 ∥ 2 .In bounding the remaining three lines we repeatedly use the bounds obtained in Proposition D.2. We will also use the following bounds, which follows from ( 35), (37), and Young's inequality: For (64b) , observe that Lemma B.6 gives us∥w 0 -z 0 ∥ = η 2 ∥g 1 ∥ ≤ η 2 ∥F z 0 ∥ + η 2 δ 1 , ∥w 0 -z 0 ∥ 2 = η 2 4 ∥g 1 ∥ 2 ≤ η 2 2 ∥F z 0 ∥ 2 + η 2 2 δ 2 1 .∥F j w j -F j z 0 -DF j (z 0 )(w j -z 0 )∥ ≤ M 2 ∥w j -z 0 ∥ 2 .Thus, by using the bound obtained in Proposition D.2, we get- η 2 2n-1 j=0 F j w j -F j z 0 -DF j (z 0 )(w j -z 0 ) ≤ η 2 2n-1 j=0 ∥F j w j -F j z 0 -DF j (z 0 )(w j -z 0 )∥ ≤ ηM 4 2n-1 j=0 ∥w j -z 0 ∥ 2 ≤ ηM 4 2n-1 j=1 3η 2 (j + 1) 2 2 + 3η 2 (2ν 2 -1) 2 j 2 2 + η 2 ν 6 e 4 j(j -1) 2 (2j -1) n 2 ∥F z 0 ∥ 2 + ηM 4 2n-1 j=1 3η 2 2 δ 2 j+1 + 3η 2 (2ν 2 -1) 2 2 δ 2 j + 6η 2 ν 6 e 4 (j -1) n 2 Ψ j-1 + ηM 4 ∥w 0 -z 0 ∥ 2 = ηM 4 η 2 n(1 + 2n)(1 + 4n) -3η 2 2 + η 2 (2ν 2 -1) 2 n(2n -1)(4n -1) 2 + η 2 ν 6 e 4 (n -1)(2n -1)(32n 2 -42n + 11) 5n ∥F z 0 ∥ 2 + 3η 3 M 8 (Ψ 2n -δ 2 1 ) + 3η 3 M (2ν 2 -1) 2 8 Ψ 2n-1 + 3η 3 M ν 6 e 4 2n 2 2n-1 j=1 (j -1)Ψ j-1 + ηM 4 η 2 2 ∥F z 0 ∥ 2 + η 2 2 δ 2 1 ≤ η 3 n 3 M ν 2 + (2ν 2 -1) 2 + 16νe 4 5 ∥F z 0 ∥ 2 + 3η 3 M 8 Ψ 2n + 3η 3 M (2ν 2 -1) 2 8 Ψ 2n-1 + 3η 3 M ν 6 e 4 2n 2 2n-2 j=1 jΨ j ≤ η 3 n 3 M 4ν 4 + 16νe 4 5 ∥F z 0 ∥ 2 + 3η 3 M 8   Ψ 2n + (2ν 2 -1) 2 Ψ 2n-1 + 4ν 6 e 4 n 2 2n-2 j=1 jΨ j  where along the derivation we used the inequality ν 5 (n -1)(2n -1)(32n 2 -42n + 11) ≤ 64n 4 which holds for all n ≥ 1. From now on, we will keep on using similar techniques to reduce the exponents of ν, without explicitly stating the inequalities used, but recovering the inequalities that are used should be clear from context. For (64c), we use L-smoothness of F j , and also the fact that it implies ∥DF j (z 0 )∥ ≤ L, to getη 2 4 2n-1 j=0 DF j (z 0 )(F j z j -F j z 0 ) ≤ η 2 4 2n-1 j=0 ∥DF j (z 0 )∥ ∥F j z j -F j z 0 ∥ ≤ η 2 L 2 4 2n-1 j=0 ∥z j -z 0 ∥ ≤ η 2 L 2 4 2n-1 j=1 ηνj + ην 2 e 2 j(j -1) 2n ∥F z 0 ∥ + ηνδ j + η 2 Lν 2 e 2 Σ j-1 = η 2 L 2 4 ηνn(2n -1) + 2ην 2 e 2 (n -1)(2n -1) 3 ∥F z 0 ∥ + η 3 L 2 ν 4 Σ 2n-1 + η 4 L 3 ν 2 e 2 4 2n-1 j=1 Σ j-1 ≤ η 3 n 2 L 2 2 1 + 2e 2 3 ∥F z 0 ∥ + η 3 L 2 ν 4 Σ 2n-1 + η 4 L 3 ν 2 e 2 4 2n-2 j=1 Σ j .By the same logic, each summand in (64d) with j > 0 can be bounded asDF j (z 0 ) j-1 k=0 (F k w k -F k z 0 ) ≤ ∥DF j (z 0 )∥ j-1 k=0 ∥F k w k -F k z 0 ∥ ≤ L 2 j-1 k=0 ∥w k -z 0 ∥ ≤ L 2 η 2 ∥F z 0 ∥ + η 2 δ 1 + L 2 j-1 k=1 η 2 1 + 2ν 2 k + ν 3 e 2 k(k -1) n ∥F z 0 ∥ + L 2 j-1 k=1 η 2 δ k+1 + η(2ν 2 -1) 2 δ k + η 2 Lν 3 e 2 Σ k-1 = ηL 2 2 (∥F z 0 ∥ + δ 1 ) + ηL 2 2 j -1 + ν 2 j(j -1) + ν 3 e 2 j(j -1)(j -2) 3n ∥F z 0 ∥ + ηL 2 2 (Σ j -δ 1 ) + ηL 2 (2ν 2 -1) 2 Σ j-1 + η 2 L 3 ν 3 e 2 j-1 k=1 Σ k-1 = ηL 2 2 j + ν 2 j(j -1) + ν 3 e 2 j(j -1)(j -2) 3n ∥F z 0 ∥ + ηL 2 2 Σ j + ηL 2 (2ν 2 -1) 2 Σ j-1 + η 2 L 3 ν 3 e 2 j-1 k=1 Σ k-1 ,and when j = 0 the sum with respect to k becomes an empty sum. Thus, (64d) in total satisfies the boundη 2 2 2n-1 j=0 DF j (z 0 ) j-1 k=0 (F k w k -F k z 0 ) ≤ η 2 2 2n-1 j=0 DF j (z 0 ) j-1 k=0 (F k w k -F k z 0 ) ≤ η 3 L 2 4 2n-1 j=1 j + ν 2 j(j -1) + ν 3 e 2 j(j -1)(j -2) 3n ∥F z 0 ∥ + η 2 2 2n-1 j=1 ηL 2 2 Σ j + ηL 2 (2ν 2 -1) 2 Σ j-1 + η 2 L 3 ν 3 e 2 j-1 k=1 Σ k-1 = η 3 L 2 4 n(2n -1) + 4ν 2 n(n -1)(2n -1) 3 + ν 3 e 2 (n -1)(2n -1)(2n -3) 3 ∥F z 0 ∥ + η 3 L 2 4 2n-1 j=1 Σ j + η 3 L 2 (2ν 2 -1) 4 2n-1 j=1 Σ j-1 + η 4 L 3 ν 3 e 2 2 2n-1 j=1 j-1 k=1 Σ k-1 ≤ η 3 L 2 2 n 2 + 4n 3 3 + 2e 2 n 3 3 ∥F z 0 ∥ + η 3 L 2 4 2n-1 j=1 Σ j + η 3 L 2 (2ν 2 -1) 4 2n-2 j=1 Σ j + η 4 L 3 ν 3 e 2 2 2n-2 k=1 2n-1 j=k+1 Σ k-1 ≤ η 3 n 3 L 2 4ν + e 2 3 ∥F z 0 ∥ + η 3 L 2 4 Σ 2n-1 + η 3 L 2 ν 2 2 2n-2 j=1 Σ j + η 4 L 3 ν 3 e 2 2 2n-2 k=1 (2n -k -1)Σ k-1 .Simply collecting all the inequalities and rearranging the terms leads to the claimed bound.Before we proceed, let us writeEQUATIONX 2 := η 3 L 2 (ν + 1) 4 Σ 2n-1 + η 3 L 2 ν 2 (1 + ηLe 2 ) 2 2n-2 j=1 Σ j + η 4 L 3 ν 3 e 2 2 2n-2 k=1 (2n -k -1)Σ k-1 (67)so that the bound on ∥r∥ obtained in Proposition D.10 can be written asEQUATION)Theorem D.11. Suppose that η < 1 nL , and let ν := 1 + 1 2n . Then the noise term deterministically satisfies the bound∥r∥ ≤ η 3 n 3 L 2 ∥F z 0 ∥ 1 2n 1 + 2e 2 3 + 4ν + e 2 3 + 10νρ + η 3 n 3 M ∥F z 0 ∥ 2 1 2 + 4ν 4 + 16νe 4 5 + ρ 2 3ν 4 + 8ν 3 e 4 + η 3 n 3 M σ 2 3ν 4 + 8ν 3 e 4 + 10νη 3 n 3 L 2 σ.Proof. From ( 38), ( 39), and Lemma D.4, it holds thatEQUATIONEQUATION)Plugging the bound for Ψ j into (66) we getX 1 ≤ 3η 3 M 8   2n 3 (ρ ∥F z 0 ∥ + σ) 2 + (2ν 2 -1) 2 (2n -1)n 2 (ρ ∥F z 0 ∥ + σ) 2 + 4ν 6 e 4 2n-2 j=1 j 2 (ρ ∥F z 0 ∥ + σ) 2   = 3η 3 M 8 2n 3 + (2ν 2 -1) 2 (2n -1)n 2 (ρ ∥F z 0 ∥ + σ) 2 + 4ν 6 e 4 3 (n -1)(2n -1)(4n -3)(ρ ∥F z 0 ∥ + σ) 2 ≤ 3η 3 M 8 4ν 4 n 3 (ρ ∥F z 0 ∥ + σ) 2 + 32ν 3 e 4 n 3 3 (ρ ∥F z 0 ∥ + σ) 2 = η 3 n 3 M (ρ ∥F z 0 ∥ + σ) 2 2 3ν 4 + 8ν 3 e 4 .By Young's inequality, it holds that(ρ ∥F z 0 ∥ + σ) 2 2 ≤ ρ 2 ∥F z 0 ∥ 2 + σ 2 ,from which we getEQUATION)Meanwhile, plugging the bound for Σ j into (67) we getX 2 ≤ η 3 L 2 (ν + 1) 4 (2n -1)n(ρ ∥F z 0 ∥ + σ) + η 3 L 2 ν 2 (1 + ηLe 2 ) 2 2n-2 j=1 jn(ρ ∥F z 0 ∥ + σ) + η 4 L 3 ν 3 e 2 2 2n-2 k=1 (2n -k -1)(k -1)n(ρ ∥F z 0 ∥ + σ) = η 3 L 2 (ν + 1) 4 (2n -1)n(ρ ∥F z 0 ∥ + σ) + η 3 L 2 ν 2 (1 + ηLe 2 ) 2 (n -1)(2n -1)n(ρ ∥F z 0 ∥ + σ) + η 4 L 3 ν 3 e 2 6 -3 + 11n -12n 2 + 4n 3 n(ρ ∥F z 0 ∥ + σ) ≤ η 3 L 2 n 2 (ρ ∥F z 0 ∥ + σ) + (1 + ηLe 2 )n 3 (ρ ∥F z 0 ∥ + σ) + 2ηLe 2 3 n 4 (ρ ∥F z 0 ∥ + σ) ≤ η 3 n 3 L 2 (ρ ∥F z 0 ∥ + σ) 1 n + 1 + e 2 n + 2e 2 3where in the last line we used that η < 1 nL . Because the inequality1 n + 1 + e 2 n + 2e 2 3 ≤ 10νholds for all n ≥ 1, continuing from above we obtainEQUATIONRearranging ( 68) with applying the bounds ( 71) and ( 72) gives us the claimed result.Proof of Theorem D.8. As n ≥ 1, we notice that 1 /n ≤ 1 and ν ≤ 3 /2. Then the bound ( 60) is immediate from Theorem D.11.In this section, we prove the following. Theorem D.12. Say we use SEG-FFA. Then, as long as the stepsize used in an epoch satisfies η < 1 nL , it holds thatEQUATION)for constantsEQUATION)EQUATIONEQUATION)Proof. As n ≥ 1, we notice that 1 /n ≤ 1 and ν ≤ 3 /2. The bound is then immediate from the following Theorem D.13.Theorem D.13. Suppose that η < 1 nL , and let ν := 1 + 1 2n . Then, in expectation, the noise term satisfies the boundE ∥r∥ 2 z 0 ≤ 4η 6 n 6 L 4 ∥F z 0 ∥ 2 1 2n 1 + 2e 2 3 + 4ν + e 2 3 2 + 36ρ 2 e 4 n + 4η 6 n 6 M 2 ∥F z 0 ∥ 4 1 2 + 4ν 4 + 16νe 4 5 2 + ρ 4 3ν 4 + 8ν 3 e 4 2 n + 4η 6 n 5 M 2 σ 4 3ν 4 + 8ν 3 e 4 2 + 144e 4 η 6 n 5 L 4 σ 2 .Proof. Notice that, when conditioned on z 0 , the only source of randomness included in Ψ j is the random permutation τ selected for the epoch. Hence, we can use Lemma D.5 to getE [Ψ j | z 0 ] = E j i=1 δ 2 i z 0 = j i=1 E δ 2 i z 0 ≤ jn(ρ ∥F z 0 ∥ + σ) 2 2 .Applying Young's inequality on (68) we get∥r∥ 2 ≤ 4η 6 n 6 L 4 ∥F z 0 ∥ 2 1 2n 1 + 2e 2 3 + 4ν + e 2 3 2 + 4η 6 n 6 M 2 ∥F z 0 ∥ 4 1 2 + 4ν 4 + 16νe 4 5 2 + 4X 2 1 + 4X 2 2 .(77)When conditioned on z 0 , the first two lines are not random quantities. Thus, it suffices to derive the bounds for E X 2 i z 0 , i = 1, 2.Recall that the bound (71) on X 1 holds deterministically. Hence, it holds thatE X 2 1 z 0 ≤ E X 1 η 3 n 3 M ρ 2 ∥F z 0 ∥ 2 3ν 4 + 8ν 3 e 4 + η 3 n 3 M σ 2 3ν 4 + 8ν 3 e 4 z 0 = η 3 n 3 M 3ν 4 + 8ν 3 e 4 ρ 2 ∥F z 0 ∥ 2 + σ 2 E [X 1 | z 0 ] . Now, to compute E [X 1 | z 0 ],we apply the linearity of expectation on (66) to getE [X 1 | z 0 ] = 3η 3 M 8   E [Ψ 2n | z 0 ] + (2ν 2 -1) 2 E [Ψ 2n-1 | z 0 ] + 4ν 6 e 4 n 2 2n-2 j=1 j E [Ψ j | z 0 ]   ≤ 3η 3 M 8   n 2 (ρ ∥F z 0 ∥ + σ) 2 + (2ν 2 -1) 2 (2n -1)nσ 2 2 + 4ν 6 e 4 n 2 2n-2 j=1 j 2 n(ρ ∥F z 0 ∥ + σ) 2 2   = 3η 3 M 8 2n 2 + (2ν 2 -1) 2 (2n -1)n 2 (ρ ∥F z 0 ∥ + σ) 2 + 2ν 6 e 4 (n -1)(2n -1)(4n -3)(ρ ∥F z 0 ∥ + σ) 2 3n ≤ 3η 3 M 8 2ν 4 n 2 (ρ ∥F z 0 ∥ + σ) 2 + 16ν 3 e 4 n 2 (ρ ∥F z 0 ∥ + σ) 2 3 = η 3 n 2 M (ρ ∥F z 0 ∥ + σ) 2 4 3ν 4 + 8ν 3 e 4 .Young's inequality gives us the bound(ρ ∥F z 0 ∥ + σ) 2 2 ≤ ρ 2 ∥F z 0 ∥ 2 + σ 2 (78)which, with the inequality derived above, leads toE [X 1 | z 0 ] ≤ η 3 n 2 M 2 3ν 4 + 8ν 3 e 4 ρ 2 ∥F z 0 ∥ 2 + σ 2 .As a consequence, with using Young's inequality once again, we obtainEQUATION)To get the bound of E X 2 2 z 0 , we begin by usingηLν 2 (2n -k -1) ≤ 1 + 1 2n 2 2n -k -1 n = - k 4n 3 - k n 2 - k n - 1 4n 3 - 1 2n 2 + 1 n + 2 ≤ 2,which holds for all 1 ≤ k ≤ 2n -2, to (67) to obtainX 2 ≤ η 3 L 2 (ν + 1) 4 Σ 2n-1 + η 3 L 2 ν 2 (1 + ηLe 2 ) 2 2n-2 j=1 Σ j + η 3 L 2 ν 3 e 2 2 2n-2 k=1 2n -k -1 n Σ k-1 ≤ η 3 L 2 (ν + 1) 4 Σ 2n-1 + η 3 L 2 ν 2 (1 + ηLe 2 ) 2 2n-2 j=1 Σ j + η 3 L 2 νe 2 2n-2 k=1 Σ k-1 ≤ η 3 L 2 (ν + 1) 4 Σ 2n-1 + η 3 L 2 ν 2 (1 + ηLe 2 ) 2 + η 3 L 2 νe 2 2n-2 j=1 Σ j ≤ η 3 L 2 (ν + 1) 4 Σ 2n-1 + 3η 3 L 2 e 2 2n-2 j=1 Σ j .Then we directly square both sides and expand them to getX 2 2 ≤   η 3 L 2 (ν + 1) 4 Σ 2n-1 + 3η 3 L 2 e 2 2n-2 j=1 Σ j   2 = η 6 L 4 (ν + 1) 2 16 Σ 2 2n-1 + 9η 6 L 4 e 4   2n-2 j=1 Σ j   2 + 3η 6 L 4 e 2 (ν + 1) 2 2n-2 j=1 Σ 2n-1 Σ j .Here, using Lemma D.6 and Lemma D.7 on the right hand side leads toE X 2 2 z 0 ≤ η 6 L 4 (ν + 1) 2 n(2n -1) 2 (ρ ∥F z 0 ∥ + σ) 2 32 + 9η 6 L 4 e 4 n(2n -2) 2 (2n -1) 2 (ρ ∥F z 0 ∥ + σ) 2 8 + 3η 6 L 4 e 2 (ν + 1) 2 2n-2 j=1 jn(2n -1)(ρ ∥F z 0 ∥ + σ) 2 2 ≤ η 6 L 4 (ν + 1) 2 n(2n -1) 2 (ρ ∥F z 0 ∥ + σ) 2 32 + 9η 6 L 4 e 4 n(2n -2) 2 (2n -1) 2 (ρ ∥F z 0 ∥ + σ) 2 8 + 3η 6 L 4 e 2 (ν + 1)n(n -1)(2n -1) 2 (ρ ∥F z 0 ∥ + σ) 2 4 ≤ η 6 L 4 n 3 (ρ ∥F z 0 ∥ + σ) 2 2 + 9η 6 L 4 e 4 n(2n -2) 2 (2n -1) 2 (ρ ∥F z 0 ∥ + σ) 2 8 + 6η 6 L 4 e 2 n 3 (n -1)(ρ ∥F z 0 ∥ + σ) 2 = η 6 L 4 (ρ ∥F z 0 ∥ + σ) 2 n 3 2 + 9e 4 n(2n -2) 2 (2n -1) 2 8 + 6e 2 n 3 (n -1) ≤ 18e 4 η 6 L 4 n 5 (ρ ∥F z 0 ∥ + σ) 2 .As a consequence, with using (78) once again, we obtainEQUATION)Taking the conditional expectation on (77), applying the bounds ( 79) and ( 80), and then rearranging the terms leads to the claimed inequality.Theorem D.14. Say we use SEG-FF with α = β = η /2. Then, as long as the stepsize used in an epoch satisfiesη < 1 nL , it holds that ∥r∥ ≤ η 2 n 2 C 1F ∥F z 0 ∥ + η 2 n 2 D 1F ∥F z 0 ∥ 2 + η 2 n 2 V 1F E ∥r∥ 2 z 0 ≤ η 4 n 4 C 2F ∥F z 0 ∥ 2 + η 4 n 4 D 2F ∥F z 0 ∥ 4 + η 4 n 3 V 2F for constants C 1F , D 1F , V 1F , C 2F , D 2F, and V 2F to be determined later in (83) and (84).Proof. As we have discussed in Section 5.1, we already know that aiming to achieve O(η 3 ) error without anchoring is futile. Instead, we show that error of magnitude O(η 2 ) is possible with the chosen stepsizes.By Proposition C.2 and Lemma C.4 we have For any i = 0, 1, . . . , N , it holds thatz 2n = z 0 - η 2 2n-1 j=0 T j z 0 + η 2 4 2n-1 j=0 DT j (z 0 )T j z 0 + η 2 4 0≤k<j≤2n-1 DT j (z 0 )T k z 0 + ϵ 2n = z 0 -η n-1 j=0 F j z 0 + 3η 2 4 n j=1 DF j (z 0 )F j z 0 + η 2 2 i̸ =j DF j (z 0 )F i z 0 + ϵ 2n = z 0 -ηnF z 0 + η 2 n 2 DF (z 0 )F z 0 - η 2 4 n j=1 DF j (z 0 )F j z 0 - η 2 2 i̸ =j DF j (z 0 )F i z 0 + ϵ 2nwhere we denoteEQUATIONComparing z 2n to a point that would have been the result of a deterministic EG update with stepsize ηn we getz 2n -(z 0 -ηnF (z 0 -ηnF z 0 )) = ηnF (z 0 -ηnF z 0 ) -ηnF z 0 + η 2 n 2 DF (z 0 )F z 0 + ϵ 2n - η 2 4 n j=1 DF j (z 0 )F j z 0 - η 2 2 i̸ =j DF j (z 0 )F i z 0 .Let us defineEQUATION)Noticing the resemblence between ( 64) and the equations in ( 81) and ( 82), we can repeat the same reasoning used for Theorem D.8 and Theorem D.12, but with replacing the bounds given by Proposition D.2 to those in Proposition D.3 (and plugging in η /2 in place of η in the statement of Proposition D.3) to conclude that∥r∥ ≤ η 3 n 3 C1A ∥F z 0 ∥ + η 3 n 3 D1A ∥F z 0 ∥ 2 + η 3 n 3 Ṽ1A E ∥r∥ 2 z 0 ≤ η 6 n 6 C2A ∥F z 0 ∥ 2 + η 6 n 6 D2A ∥F z 0 ∥ 4 + η 6 n 5 Ṽ2Afor some constants C1A , D1A , Ṽ1A , C2A , D2A , and Ṽ2A . Meanwhile, we also haveη 2 4 n j=1 DF j (z 0 )F j z 0 + η 2 2 i̸ =j DF j (z 0 )F i z 0 = η 2 n 2 2 DF (z 0 )F z 0 - η 2 4 n j=1 DF j (z 0 )F j z 0 ≤ η 2 n 2 2 ∥DF (z 0 )∥ ∥F z 0 ∥ + η 2 4 n j=1 ∥DF j (z 0 )∥ ∥F j z 0 ∥ ≤ η 2 n 2 2 L ∥F z 0 ∥ + η 2 4 n j=1 L (∥F j z 0 -F z 0 ∥ + ∥F z 0 ∥) ≤ η 2 (n 2 + n)L 2 ∥F z 0 ∥ + η 2 L 4 n j=1 ∥F j z 0 -F z 0 ∥ ≤ η 2 n 2 L ∥F z 0 ∥ + η 2 L 4   n j=1 ∥F j z 0 -F z 0 ∥ 2   1/2   n j=1 1   1/2 = η 2 n 2 L ∥F z 0 ∥ + η 2 nL 4 (ρ ∥F z 0 ∥ + σ)where in the second to the last line we used the Cauchy-Schwarz inequality. Therefore, as η ≤ 1 /nL, we conclude that∥z 2n -(z 0 -ηnF (z 0 -ηnF z 0 ))∥ ≤ η 2 n 2 C 1F ∥F z 0 ∥ + η 2 n 2 D 1F ∥F z 0 ∥ 2 + η 2 n 2 V 1Ffor constantsEQUATIONMoreover, using Young's inequality, we see thatη 2 4 n j=1 DF j (z 0 )F j z 0 + η 2 2 i̸ =j DF j (z 0 )F i z 0 2 ≤ 3η 4 n 4 L 2 ∥F z 0 ∥ 2 + 3η 4 n 2 L 2 16 ρ 2 ∥F z 0 ∥ 2 + 3η 4 n 2 L 2 16 σ 2 ,so we also conclude thatE ∥z 2n -(z 0 -ηnF (z 0 -ηnF z 0 ))∥ 2 z 0 ≤ η 4 n 4 C 2F ∥F z 0 ∥ 2 + η 4 n 4 D 2F ∥F z 0 ∥ 4 + η 4 n 3 V 2Fholds for constants EQUATIONsatisfies η < 1 nL , it holds that ∥r∥ ≤ η 2 n 2 C 1R ∥F z 0 ∥ + η 2 n 2 D 1R ∥F z 0 ∥ 2 + η 2 n 2 V 1R E ∥r∥ 2 z 0 ≤ η 4 n 4 C 2R ∥F z 0 ∥ 2 + η 4 n 4 D 2R ∥F z 0 ∥ 4 + η 4 n 3 V 2R for constants C 1R , D 1R , V 1R , C 2R , D 2R, and V 2R to be determined later in (88) and (89).Proof. As we have discussed in Section 5.1, we already know that aiming to achieve O(η 3 ) error with only using random reshuffling is futile. Instead, we show that error of magnitude O(η 2 ) is possible with the chosen stepsizes.By Proposition C.2 and Lemma C.4 we have For any i = 0, 1, . . . , N , it holds thatz n = z 0 -η n-1 j=0 F j z 0 + η 2 n-1 j=0 DF j (z 0 )F j z 0 + η 2 0≤k<j≤n-1 DF j (z 0 )F k z 0 + ϵ n = z 0 -ηnF z 0 + η 2 n 2 DF (z 0 )F z 0 -η 2 0≤j<k≤n-1 DF j (z 0 )F k z 0 + ϵ nwhere we denoteEQUATIONComparing z n to a point that would have been the result of a deterministic EG update with stepsize ηn we getz n -(z 0 -ηnF (z 0 -ηnF z 0 )) = ηnF (z 0 -ηnF z 0 ) -ηnF z 0 + η 2 n 2 DF (z 0 )F z 0 + ϵ n -η 2 0≤j<k≤n-1 DF j (z 0 )F k z 0 . Let us define ř := ηnF (z 0 -ηnF z 0 ) -ηnF z 0 + η 2 n 2 DF (z 0 )F z 0 + ϵ n .(86) Comparing the sums (64b)-( 64d) to (85), we can repeat the same reasoning used for Theorem D.8 and Theorem D.12, but with replacing the bounds given by Proposition D.2 to those in Proposition D.3, to conclude that∥ř∥ ≤ η 3 n 3 Č1A ∥F z 0 ∥ + η 3 n 3 Ď1A ∥F z 0 ∥ 2 + η 3 n 3 V1A E ∥ř∥ 2 z 0 ≤ η 6 n 6 Č2A ∥F z 0 ∥ 2 + η 6 n 6 Ď2A ∥F z 0 ∥ 4 + η 6 n 5 V2Afor some constants Č1A , Ď1A , V1A , Č2A , Ď2A , and V2A . Meanwhile, we also haveEQUATIONTherefore, from η ≤ 1 /nL and Lemma D.4, on one hand we obtain∥z n -(z 0 -ηnF (z 0 -ηnF z 0 ))∥ ≤ η 2 n 2 C 1R ∥F z 0 ∥ + η 2 n 2 D 1R ∥F z 0 ∥ 2 + η 2 n 2 V 1Rfor constantsEQUATIONOn the other hand, applying Young's inequality on (87) we get0≤j<k≤n-1 DF j (z 0 )F k z 0 2 ≤ n 4 L 2 ∥F z 0 ∥ 2 + 2L 2   n-1 j=0 δ j+1   2 ≤ n 4 L 2 ∥F z 0 ∥ 2 + 2nL 2 n j=1 δ 2 j .Taking the expectation conditioned on z 0 and applying Lemma D.5, we conclude thatE ∥z 2n -(z 0 -ηnF (z 0 -ηnF z 0 ))∥ 2 z 0 ≤ η 4 n 4 C 2R ∥F z 0 ∥ 2 +η 4 n 4 D 2R ∥F z 0 ∥ 4 +η 4 n 3 V 2Rholds for constantsEQUATIONIn this section, we provide further details for Theorem 6.2. The precise statement of Theorem 6.2 is presented as Theorem E.4. As we are now interested in the iterates {z k 0 } k≥0 , we omit the subscript 0 unless necessary, and simply write z k instead of z k 0 . 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. More precisely, lettingEQUATION)Proposition E.1. Let F be µ-strongly monotone. Then, for any η k > 0, it holds thatEQUATIONProof. From (90), using Lemma B.7 we getz k+1 -z * 2 = z k -z * 2 -2 η k n F k , z k -z * + η k n F k 2 = z k -z * 2 -2η k n F w k † , w k † -z * -2η 2 k n 2 F w k † , F z k -2 r k , z k -z * + η k n F k 2 ≤ z k -z * 2 -µη k n z k -z * 2 -2η 2 k n 2 F w k † , F z k -2 r k , z k -z * + η k n F k 2 + 2µη 3 k n 3 F z k 2 .Meanwhile, using the polarization identity (Lemma B.1) and the L-smoothness of F we get-2 F w k † , F z k = F w k † -F z k 2 -F w k † 2 -F z k 2 ≤ L 2 w k † -z k 2 -F w k † 2 -F z k 2 ≤ -(1 -η 2 k n 2 L 2 ) F z k 2 -F w k † 2 .Combining the two inequalities and using the definition of F we obtainz k+1 -z * 2 ≤ (1 -µη k n) z k -z * 2 -η 2 k n 2 (1 -η 2 k n 2 L 2 ) F z k 2 -η 2 k n 2 F w k † 2 -2 r k , z k -z * + η k nF w k † + r k 2 + 2µη 3 k n 3 F z k 2 ≤ (1 -µη k n) z k -z * 2 -η 2 k n 2 (1 -2µη k n -η 2 k n 2 L 2 ) F z k 2 -2 r k , z k -z * + 2 r k , η k nF w k † + r k 2 ≤ (1 -µη k n) z k -z * 2 -η 2 k n 2 (1 -2µη k n -η 2 k n 2 L 2 ) F z k 2 -2 r k , z k -η k nF w k † -z * + r k 2 .Let us consider the inner product term in the last line above. By Lemma B.2 and the nonexpansiveness of the EG update (Lemma B.8), for any γ k > 0 we haveEQUATIONChoosingγ k = µη k n 2 completes the proof.Proposition E.2. Let F be a µ-strongly monotone and L-Lipschitz operator. Then, wheneverη k < 1 nL √ 2 , it holds that F z k+1 ≤ 1 - µnη k 5 F z k + L r k . Proof. Let z k+1 † := z k -η k nF (z k -η k nF z k ), so that we have z k+1 -z k+1 † = r k .Then, the L-smoothness of F and Lemma B.9 impliesF z k+1 ≤ F z k+1 -F z k+1 † + F z k+1 † ≤ L z k+1 -z k+1 † + F z k+1 † ≤ L r k + 1 - 2µη k n 5 1/2 F z k ≤ L r k + 1 - µη k n 5 F z kwhere in the last line we apply a simple inequality 1 -2x ≤ (1 -x) 2 which holds for all x ∈ R.Lemma E.3. Let Ω := F z 0 , and suppose that (19) holds. Given a constant b ≥ 1 /a and the number of epochs K, say we use constant stepsizeEQUATIONwhere κ = L /µ denotes the condition number. Then for any k = 0, 1, . . . , K, it holds thatEQUATIONProof. We show a stronger statement thatEQUATIONholds for all k = 0, 1, . . . , K, by induction on k. For k = 0 there is nothing to show. Let us use induction on k, and to this end, suppose that (95) holds for some k ≥ 0. Then, with noting that ( 95) implies ( 94), by Proposition E.2 and ( 19) we haveEQUATIONHere, observe that if ω satisfies (93) thenEQUATIONwhere the last line follows from b(a -1) ≥ 0 and κ = L /µ. Therefore, combining ( 96) and ( 97) and then invoking the induction hypothesis (95) leads toF z k+1 ≤ F z k + η a k n a LV 1 = F z k + ω a LV 1 K ab ≤ F z 0 + ω a LV 1 • k + 1 K ab .That is, (95) also holds for k + 1, so we are done.Theorem E.4 (Theorem 6.2). Let Ω := F z 0 , and suppose that both (19) and (20) hold. Given a constant b ∈ ( 1 /a, 1) and the number of epochs K, say we use constant stepsizeη k ≡ η = ω nK b where ω is a constant such that ω ≤ 1 L √ 2 and ω a-1 (C 1 + D 1 (Ω + ω a LV 1 )) ≤ 1 5κ .Furthermore, for a constantΦ := C 2 + D 2 (Ω + ω a LV 1 ) 2 ,suppose that ω is chosen sufficiently small so that the constant stepsize η further satisfiesEQUATIONThen for ε = 1 -b, it holds thatEQUATIONProof. From (20) and Lemma E.3 it follows thatE ∥r∥ 2 z k ≤ η 2a k n 2a C 2 F z k 2 + η 2a k n 2a D 2 F z k 4 + η 2a k n 2a-1 V 2 ≤ η 2a k n 2a C 2 F z k 2 + η 2a k n 2a D 2 (Ω + ω a ZLV 1 ) 2 F z k 2 + η 2a k n 2a-1 V 2 = η 2a k n 2a Φ F z k 2 + η 2a k n 2a-1 V 2 .Thus, taking the conditional expectation on (91) we getη 2 k n 2 1 - 3 2 µη k n -1 + 1 2 µη k n η 2 k n 2 L 2 F z k 2 ≤ 1 - 1 2 µη k n z k -z * 2 -E z k+1 -z * 2 z k + 2 + µη k n µ η 2a-1 k n 2a-1 Φ F z k 2 + η 2a-1 k n 2a-2 V 2 .Rearranging the terms, we further getη 2 k n 2 1 - 3 2 µη k n -1 + 1 2 µη k n η 2 k n 2 L 2 - η 2a-3 k n 2a-3 Φ(2 + µη k n) µ F z k 2 ≤ 1 - 1 2 µη k n z k -z * 2 -E z k+1 -z * 2 z k + η 2a-1 k n 2a-2 V 2 (2 + µη k n) µ .(100) Because η k = η, by assuming (98), we can guarantee that the left hand side of ( 100) is nonnegative, so we obtainE z k+1 -z * 2 z k ≤ 1 - 1 2 µη k n z k -z * 2 + η 2a-1 k n 2a-2 V 2 (2 + µη k n) µ .Applying the law of total expectation, and using the simple identity 1 -x ≤ e -x which holds for all x ∈ R, from the above we getEQUATIONAs η k nL ≤ 1 and κ = L /µ, we have L(2 + µη k n) ≤ 2µκ + µ, so (101) in turn impliesE z k+1 -z * 2 ≤ e -1 2 µη k n E z k -z * 2 + η 2a-1 k n 2a-2 V 2 (2κ + 1) L .Noting that e -1 2 µη k n ≤ 1, simply unravelling this recurrence leads toEQUATIONNow, for the first term to get smaller as the choice of the number of epochs K gets larger, we want1 -b > 0. Choosing b = 1 -ε, we get E z K -z * 2 ≤ exp - µωK ε 2 z 0 -z * 2 + O 1 nK 2a-2-(2a-1)ε as claimed.In this section, we consider SEG-FFA. As in the previous section, we decompose the update across the epoch into a deterministic EG update plus a noise, asEQUATION)for F k defined by the equationEQUATION)Lemma F.1. Let u be any point in R d1+d2 . Then, for any η k > 0 and γ k > 0, it holds thatEQUATION)Proof. By ( 103) and ( 104) we getz k+1 -u 2 = z k -η k n F k -u 2 = z k -u 2 -2 η k n F k , z k -u + η k n F k 2 = z k -u 2 -2 η k nF w k † , w k † -u -2 η k nF w k † , z k -w k † -2 r k , z k -u + η k nF w k † 2 + 2 r k , η k nF w k † + r k 2 = z k -u 2 -2η k n F w k † , w k † -u -2 η k nF w k † , η k nF z k + η k nF w k † 2 -2 r k , z k -η k nF w k † -u + r k 2 = z k -u 2 -2η k n F w k † , w k † -u -2η 2 k n 2 F w k † , F z k + η 2 k n 2 F w k † 2 -2 r k , z k+1 -u -r k 2 .We now bound the inner products. On one hand, by the polarization identity (Lemma B.1) and the L-smoothness of f , we have-2 F w k † , F z k = F w k † -F z k 2 -F w k † 2 -F z k 2 ≤ L 2 -η k nF z k 2 -F w k † 2 -F z k 2 = -(1 -η 2 k n 2 L 2 ) F z k 2 -F w k † 2 .On the other hand, by the weighted AM-GM inequality (Lemma B.2), for any number a k ∈ (0, 1) it holds that-2 r k , z k+1 -u ≤ 1 a k r k 2 + a k z k+1 -u 2 .Using these two bounds, we getz k+1 -u 2 ≤ z k -u 2 -2η k n F w k † , w k † -u -η 2 k n 2 (1 -η 2 k n 2 L 2 ) F z k 2 -η 2 k n 2 F w k † 2 + η 2 k n 2 F w k † 2 + a k z k+1 -u 2 + 1 a k -1 r k 2 .Choosing a k = γ k 1+γ k and rearranging the terms, we obtainEQUATION)As the monotonicity of F implies plugging this to (106) gives us the claimed inequality. Now we show that choosing the appropriate stepsizes leads to F z k being bounded uniformly over k.F w k † , w k † -u ≥ F u, w k † -u ,Proposition F.2. Say we are using SEG-FFA. Let the sequence of stepsizes {η k } k≥0 be nonincreasing, withEQUATION)Suppose that initial stepsize η 0 is chosen sufficiently small so thatη 2 0 n 2 L 2 + 3η 0 nC 2 1A L 3 + 3η 0 nD 2 1A L • e S z 0 -z * 2 + 6SV 2 1A L 6 ≤ 1 (108)for constants C 1A , D 1A , and V 1A defined in (61)-( 63). Then for all k ≥ 0,EQUATION)Proof. We use induction on k, to establish a stronger inequalityEQUATION)To see that (110) indeed implies (109), notice that by the L-smoothness of f it holds thatF z k 2 = F z k -F z * 2 ≤ L 2 z k -z * 2 .For the case when k = 0, as S > 0, it is clear that (110) holds. Now suppose that (110) holds for some k ≥ 0. Applying Young's inequality on (19) leads tor k 2 ≤ 3η 6 k n 6 C 2 1A F z k 2 + D 2 1A F z k 4 + V 2 1A .Taking u = z * in (105) and then using the bound on r k 2 above, we obtainEQUATIONChoose γ k = η 3 k n 3 L 3 . Notice that (108) implies η 0 nL ≤ 1, henceforth η k ≤ η 0 ≤ 1 /nL. This, with the induction hypothesis (109), impliesη 2 k n 2 L 2 + 3η 4 k n 4 C 2 1A γ k + 3η 4 k n 4 D 2 1A γ k F z k 2 = η 2 k n 2 L 2 + 3η k nC 2 1A L 3 + 3η k nD 2 1A L 3 F z k 2 ≤ η 2 0 n 2 L 2 + 3η 0 nC 2 1A L 3 + 3η 0 nD 2 1A L 3 F z k 2 ≤ η 2 0 n 2 L 2 + 3η 0 nC 2 1A L 3 + 3η 0 nD 2 1A L 3 • e S L 2 z 0 -z * 2 + 6SV 2 1A L 6 ≤ 1.That is, the left hand side of (111) becomes nonnegative. Then it is immediate from (111) thatz k+1 -z * 2 ≤ (1 + γ k ) z k -z * 2 + 3η 6 k n 6 (1 + γ k ) V 2 1A γ k ≤ 1 + η 3 k n 3 L 3 z k -z * 2 + 6η 3 k n 3 V 2 1A L 3 .Using Lemma B.10 to unravel this recurrence relation, we obtainz k+1 -z * 2 ≤   k j=0 1 + η 3 j n 3 L 3     z 0 -z * 2 + k j=0 6η 3 j n 3 V 2 1A L 3   ≤ e k j=0 η 3 j n 3 L 3   z 0 -z * 2 + 6V 2 1A L 6 k j=0 η 3 j n 3 L 3   ≤ e S z 0 -z * 2 + 6SV 2 1A L 6which shows that (110) also holds when k is replaced by k + 1. This completes the proof.Theorem F.3 (Formal version of Theorem 5.4). Suppose that we are using SEG-FFA with η k = η0 3 √ 2 log 2 (k+2) 1/3 log(k+2) for k = 0, 1, . . . , where, for S := ∞ k=0 η 3 k n 3 L 3 , the initial stepsize η 0 is chosen so thatη 2 0 n 2 L 2 + 3η 0 nC 2 1A L 3 + 3η 0 nD 2 1A L • e S z 0 -z * 2 + 6SV 2 1A L 6 ≤ 1 (112)for constants C 1A , D 1A , and V 1A defined in (61)-( 63), and there exists a positive constant λ > 0 such thatEQUATIONfor constants C 2A , D 2A , and V 2A defined in (74)-( 76). Then forEQUATION)Proof. As the sequence of stepsizes {η k } k≥0 is nonincreasing and (112) asserts that η 0 ≤ 1 /nL, we can use the bounds established in Theorem D.8 and Theorem D.12. Also, the premises required for Proposition F.2 are also satisfied, so the bound (109) holds.Taking u = z * and γ k = η 3 k n 3 L 3 in (105), with using ( 73) and ( 113), we obtain0 = 2η k n F z * , w k † -z * ≤ z k -z * 2 - 1 1 + γ k E z k+1 -z * 2 z k -η 2 k n 2 (1 -η 2 k n 2 L 2 ) F z k 2 + 1 γ k E r k 2 z k ≤ z k -z * 2 - 1 1 + γ k E z k+1 -z * 2 z k -η 2 k n 2 (1 -η 2 k n 2 L 2 ) F z k 2 + 1 L 3 η 3 k n 3 C 2A F z k 2 + η 3 k n 3 D 2A F z k 4 + η 3 k n 2 V 2A ≤ z k -z * 2 - 1 1 + γ k E z k+1 -z * 2 z k -η 2 k n 2 1 -η 2 k n 2 L 2 - η k nC 2A L 3 - η k nD 2A L 3 F z k 2 F z k 2 + η 3 k n 2 V 2A L 3 ≤ z k -z * 2 - 1 1 + γ k E z k+1 -z * 2 z k -λη 2 k n 2 F z k 2 + η 3 k n 2 V 2A L 3 .By the law of total expectation, and that γ k = η 3 k n 3 L 3 < 1, from the above we get(1 + γ k )λη 2 k n 2 E F z k 2 ≤ (1 + γ k ) E z k -z * 2 -E z k+1 -z * 2 + (1 + γ k )η 3 k n 2 V 2A L 3 ≤ (1 + γ k ) E z k -z * 2 -E z k+1 -z * 2 + 2η 3 k n 2 V 2A L 3 .This recurrence can be unraveled using Lemma B.10, giving usEQUATION)For the left hand side of (115), we haveE z K+1 -z * 2 + K k=0 (1 + γ k )λη 2 k n 2 E F z k 2 ≥ λ K k=0 η 2 k n 2 E F z k 2 ≥ λ min k=0,1,...,K E F z k 2 K k=0 η 2 k n 2 .From Lemma B.11, we know that whenever K ≥ 1,K k=0 η 2 k n 2 = η 2 0 n 2 ( 3 √ 2 log 2) 2 K k=0 1 (k + 2) 2/3 (log(k + 2)) 2 ≥ η 2 0 n 2 ( 3 √ 2 log 2) 2 • (K + 3) 1/3 (log(K + 3)) 2 . Meanwhile, as x → 2(log 2) 3 (x+2)(log(x+2)) 3 is a decreasing function, we have ∞ k=0 2(log 2) 3 (k + 2)(log(k + 2)) 3 ≤ 1 + 2(log 2) 3 3(log 3) 3 + ∞ 1 2(log 2) 3 (x + 2)(log(x + 2)) 3 dx ≤ 1 + 2(log 2) 3 3(log 3) 3 + (log 2) 3 (log 3) 2 ≤ 3 2and thusS = ∞ k=0 η 3 k n 3 L 3 = η 3 0 n 3 L 3 ∞ k=0 2(log 2) 3 (k + 2)(log(k + 2)) 3 ≤ 3 2 η 3 0 n 3 L 3 ≤ 3 2 .Thus, for the right hand side of (115), it holds thatK k=0 (1 + γ k ) z 0 -z * 2 + K k=0 2η 3 k n 2 V 2A L 3 ≤ e K k=0 γ k z 0 -z * 2 + K k=0 2η 3 k n 2 V 2A L 3 ≤ e S z 0 -z * 2 + 2SV 2A nL 6 ≤ e 3/2 z 0 -z * 2 + 3V 2A nL 6 .Therefore, from (115) we getλη 2 0 n 2 ( 3 √ 2 log 2) 2 • (K + 3) 1/3 (log(K + 3)) 2 • min k=0,1,...,K E F z k 2 ≤ e 3/2 z 0 -z * 2 + 3V 2A nL 6 .Letting Λ := λe -3/2 ( 3 √ 2 log 2) 2 and simply rearranging the terms gives us the desired inequality.G.1 PROOF OF SEG-US, SEG-RR AND SEG-FF DIVERGENCEWe prove the divergence of SEG-US, SEG-RR and SEG-FF in each proposition below, using the same worst-case problem for n = 2. These constitute the proof of Theorem 4.2.Proposition G.1 (Part of Theorem 4.2). For n = 2, there exists a convex-concave minimax problem f (x, y) = 1 2 2 i=1 f i (x, y) having a monotone F , consisting of L-smooth quadratic f i 's satisfying Assumption 4 with (ρ, σ) = (1, 0) such that SEG-US diverges in expectation for any choice of stepsizes {α t } t≥0 and {β t } t≥0 . That is, for all t ≥ 0,E ∥z t+1 ∥ 2 > E ∥z t ∥ 2 , E ∥F z t+1 ∥ 2 > E ∥F z t ∥ 2 .Proof. We consider the case off 1 (x, y) = - L 4 x 2 + L 2 xy - L 4 y 2 , f 2 (x, y) = L 4 x 2 + L 2 xy + L 4 y 2 ,which result in a bilinear (and hence convex-concave) objective functionEQUATIONOne can quickly check from the definitions of the component functions f 1 and f 2 that the corresponding saddle gradient operators are given asF 1 z = -L/2 L/2 -L/2 L/2 :=A1 z, F 2 z = L/2 L/2 -L/2 -L/2 :=A2 z, F z = 0 L/2 -L/2 0 zwhere z = (x, y) ∈ R 2 . From the fact that ∥A i ∥ ≤ L for all i's, we can confirm that f i 's are indeed L-smooth. As for Assumption 4, we can verify that1 2 2 i=1 ∥F i z -F z∥ 2 = L 2 4 ∥z∥ 2 = (∥F z∥) 2 ,thus proving that our example f indeed satisfies Assumption 4 with (ρ, σ) = (1, 0).We now proceed to show that for this particular worst-case example f , SEG-US diverges in expectation. For t ≥ 0, the (t + 1)-th iteration of SEG-US starts at z t , and the algorithm uniformly chooses an index i(t) from [n]. The algorithm then makes an updatew t = z t -α t F i(t) z t , z t+1 = z t -β t F i(t) w t .In our worst-case example f , the updates can be compactly written asz t+1 = (I -β t A i(t) + α t β t A 2 i(t) )z t .Since we have n = 2, the update can be summarized asz t+1 = (I -β t A 1 + α t β t A 2 1 )z t with probability 1/2, (I -β t A 2 + α t β t A 2 2 )z t with probability 1/2.By the definition of A 1 and A 2 and using A 2 1 = A 2 2 = 0, we can verify thatN 1 := I -β t A 1 + α t β t A 2 1 = 1 + βtL 2 -βtL 2 βtL 2 1 -βtL 2 , N 2 := I -β t A 2 + α t β t A 2 2 = 1 -βtL 2 -βtL 2 βtL 2 1 + βtL 2 .From this, we notice that the expectation of ∥z t+1 ∥ 2 conditional on z t readsE ∥z t+1 ∥ 2 z t = z ⊤ t N ⊤ 1 N 1 + N ⊤ 2 N 2 2 z t .Working out the calculations, we can check thatN ⊤ 1 N 1 + N ⊤ 2 N 2 2 = 1 + β 2 t L 2 2 0 0 1 + β 2 t L 2 2 , thus resulting in E ∥z t+1 ∥ 2 z t = 1 + β 2 t L 2 2 ∥z t ∥ 2 .Since this holds for all t ≥ 0, SEG-US diverges in expectation, for any positive stepsizes {α t } t≥0 and {β t } t≥0 . The statement on ∥F z t ∥ follows by realizing that ∥F z∥ = L 2 ∥z∥. Proposition G.2 (Part of Theorem 4.2). For n = 2, there exists a convex-concave minimax problem f (x, y) = 1 2 2 i=1 f i (x, y) having a monotone F , consisting of L-smooth quadratic f i 's satisfying Assumption 4 with (ρ, σ) = (1, 0) such that SEG-RR diverges in expectation for any choice of stepsizes {α k } k≥0 and {β k } k≥0 . That is, for any k ≥ 0,E z k+1 0 2 > E z k 0 2 , E F z k+1 0 2 > E F z k 0 2 .Proof. The proof uses the same example as Proposition G.1, outlined in (116). We show that for this particular worst-case example f , SEG-RR diverges in expectation. For k ≥ 0, the (k + 1)-th epoch of SEG-RR starts at z k 0 , and the algorithm randomly chooses a permutation τ k : [n] → [n]. The algorithm then goes through a series of updatesw k i = z k i -α k F τ k (i+1) z k i , z k i+1 = z k i -β k F τ k (i+1) w k i , for i = 0, . . . , n -1.In our worst-case example f , the updates can be compactly written asz k i+1 = (I -β k A τ k (i+1) + α k β k A 2 τ k (i+1) )z k i .Since we have n = 2 and there are only two possible permutations, the updates over an epoch can be summarized asz k+1 0 = z k n = (I -β k A 1 + α k β k A 2 1 )(I -β k A 2 + α k β k A 2 2 )z k 0 with probability 1/2, (I -β k A 2 + α k β k A 2 2 )(I -β k A 1 + α k β k A 2 1 )z k 0 with probability 1/2.By the definition of A 1 and A 2 and using A 2 1 = A 2 2 = 0, we can verify thatEQUATIONEQUATION)From this, we notice that the expectation of z k+10 2 conditional on z k 0 reads E z k+1 0 2 z k 0 = (z k 0 ) ⊤ M ⊤ 1 M 1 + M ⊤ 2 M 2 2 z k 0 .Working out the calculations, we can check thatM ⊤ 1 M 1 + M ⊤ 2 M 2 2 = 1 + β 4 k L 4 2 0 0 1 + β 4 k L 4 2 , thus resulting in E z k+1 0 2 z k 0 = 1 + β 4 k L 4 2 z k 0 2 .Since this holds for all k ≥ 0, SEG-RR diverges in expectation, for any positive stepsizes {α k } k≥0 and {β k } k≥0 . The statement on F z k 0 follows by realizing that ∥F z∥ = L 2 ∥z∥.Remark. In Theorem G.4, 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 ≳ L/µ: Ω( 1 n 2 K 2 + 1 nK 3 ) bounds for strongly convex quadratic functions (Safran & Shamir, 2020; 2021) and Ω( 1 nK 2 ) bounds for strongly convex non-quadratic functions (Rajput et al., 2020; Yun et al., 2022; Cha et al., 2023) . Upper bounds that match the lower bounds in n and K are also known, which indicates 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 Ω( 1 nK 2 ) lower bound for our algorithms of interest, we note that the existing Ω( 1 nK 2 ) bounds for SGD-RR are proven for piecewise-quadratic functions whose Hessian is discontinuous. Since the discontinuous Hessian violates our Assumption 3, we instead adhere to the quadratic case to prove lower bounds Ω( 1nK 3 ) for both SGDA-RR and SEG-RR (when K ≥ L/µ). These bounds may not be the tightest possible (since they are restricted to the quadratics), but they still suffice to demonstrate that SEG-FFA is provably superior to both SGDA-RR and SEG-RR.For the proof of lower bounds for SGDA-RR and SEG-RR, we utilize results and techniques from the lower bounds proven for SGD-RR; thus, it would be profitable to summarize the existing result.In case of SGD-RR, it is known from Theorem 2 of Safran & Shamir (2021) that there exists a minimization problem g(x) such that SGD-RR satisfies a lower bound of Ω( 1n 2 K 2 + 1 nK 3 ) for large enough values of K. We rewrite the theorem in a version in accordance with our notation and assumptions: Theorem G.5 (Theorem 2 of Safran & Shamir ( 2021)). For any n ≥ 2 and L, µ > 0 satisfying L/µ ≥ 2, there exists a µ-strongly convex minimization problem g(x) = 1 n n i=1 g i (x) consisting of L-smooth quadratic g i 's satisfying Assumption 4 with (ρ, σ) = (1, σ) such that SGD-RR using any constant stepsize α k = α > 0 satisfies E x K 0 -x * 2 = Ω σ 2 LµnK • min 1, L µnK + L 2 µ 2 K 2 .The statement is equivalent to saying that for SGD-RR with constant stepsize α > 0, the bound Ω( σ 2 LµnK ) holds for K ≲ L/µ and Ω( σ 2 µ 2 n 2 K 2 + Lσ 2 µ 3 nK 3 ) for K ≳ L/µ.The function g = 1 n n i=1 g i used in the theorem is defined by the following component functions:EQUATIONthus making the objective functiong(x 1 , x 2 , x 3 ) := µ 2 x 2 1 + L 2 x 2 2 + L 4 x 2 3 .One can notice that the linear terms in g i (119) change signs depending on i ≤ n 2 or not, and handling these sign flips is the key to the proof of lower bound.For the SGDA-RR lower bound, we consider the following minimax optimization problem:EQUATIONwhere g i 's are from (119). We need to first check if the problem instance satisfies the assumptions listed in the theorem statement. Since f (x, y) = g(x) -µ 2 y 2 and g is a µ-strongly convex function, f is µ-strongly-convex-strongly-concave as claimed. Also, it is easy to check from the definition of g i that each component f i (x, y) is L-smooth quadratic.Lastly, to check Assumption 4, we first define s 1 , . . . , s n as s i = 1 for i ≤ n 2 and s i = 0 for i > n 2 . Using this notation, The function g i can be compactly written as the following:g i (x 1 , x 2 , x 3 ) = µ 2 x 2 1 + L 2 x 2 2 + σ 2 (2s i -1)x 2 + L 2 s i x 2 3 + σ 2 (2s i -1)x 3 .Therefore, the saddle gradient operators F i of f i and F of f evaluate toF i z := ∇g i (x) µy =    µx 1 Lx 2 + σ 2 (2s i -1) Ls i x 3 + σ 2 (2s i -1) µy    , F z =    µx 1 Lx 2 L 2 x 3 µy    ,which in turn yields∥F i z -F z∥ 2 = σ 2 4 + L 2 x 3 + σ 2 2 ≤ L 2 |x 3 | + σ 2 ≤ (∥F z∥ + σ)2 for all i = 1, . . . , n. This confirms that the function f = 1 n i f i satisfies Assumption 4 with (ρ, σ) = (1, σ).If we run SGDA-RR on this problem, the updates on x done by SGDA-RR is exactly identical to what SGD-RR would perform for the minimization problem g(x) = 1 n i g i (x) with the same choices of random permutations. Therefore, after K epochs of SGDA-RR, it follows from Theorem G.5 thatE z K 0 -z * 2 ≥ E x K 0 -x * 2 = Ω σ 2 LµnK • min 1, L µnK + L 2 µ 2 K 2 ,which is in fact a tighter lower bound for SGDA-RR than what is stated in Theorem G.4. This finishes the proof.In this subsection, we prove the lower bound for SEG-RR. We will first define a new problem instance f 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 as a basis for the case analysis that follows: we will divide the choices of stepsizes α, β > 0 to four regimes and prove a lower bound for each of them. Combining the regimes will result in the desired lower bound.For SEG-RR, we use a slightly different problem from (120). This time, we considerEQUATIONwhere s i = 1 for i ≤ n 2 and s i = 0 for i > n 2 , as defined above. We first check if the problem (121) satisfies the assumptions in the theorem statement. Sincef (x, y) = L 2 x 2 1 + L 4 x 2 2 - µ 2 y 2and L/2 ≥ µ by assumption, f is µ-strongly-convex-strongly-concave. Also, it is straightforward to see that each f i is an L-smooth quadratic function. It is left to check Assumption 4. The saddle gradient operators F i of f i and F of f evaluate toF i z =   Lx 1 L 2 x 2 + σ(2s i -1) µy   , F z =   Lx 1 L 2 x 2 µy   ,which in turn yields ∥F i z -F z∥ 2 = σ 2 , for all i = 1, . . . , n. This confirms that the function f = 1 n i f i satisfies Assumption 4 with (ρ, σ) = (0, σ), as required by the theorem.For k ≥ 0, the (k + 1)-th epoch of SEG-RR starts at z k 0 = (x k 0 , y k 0 ) and the algorithm chooses a random permutation τ k . The algorithm then goes through a series of updatesEQUATIONi+1) w k i , for i = 0, . . . , n -1. For our example f (121), it can be checked that a single iteration by SEG-RR readsz k i+1 =   x k i+1,1 x k i+1,2 y k i+1   =   (1 -βL + αβL 2 )x k i,1(1-βL 2 + αβL 2 4 )x k i,2 -βσ(1 -αL 2 )(2s τ k (i+1) -1) (1 -βµ + αβµ 2 )y k i   .Aggregating the SEG-RR updates over an entire epoch (i = 0, . . . , n -1) results in = (1 -βµ + αβµ 2 ) n y k 0 . We will now square both sides of these equations above and take expectations over τ k . In doing so, there is a useful identity:E[Φ] = n i=1 E[2s τ k (i) -1] 1 - βL 2 + αβL 2 4 n-i = 0.Also, it worth mentioning that τ k is independent of z k 0 = (x k 0,1 , x k 0,2 , y k 0 ). Using these facts, we can arrange the terms to obtain (x k+1 0,1 ) 2 = (1 -βL + αβL 2 ) 2n (x k 0,1 ) 2 , (122)EQUATION(y k+1 0EQUATION)Based on these three per-epoch update equations above, we now divide the choices of SEG-RR stepsizes α, β > 0 into the following four cases and handle them separately:1. α > 1 L , in which case we show that SEG-RR makes (x k+1 0,1 ) 2 > (x k 0,1 ) 2 hold deterministically, so that if we initialize at x 0 0,1 = σ √ Lµ then we haveE z K 0 2 ≥ (x K 0,1 ) 2 > (x 0 0,1 ) 2 = σ 2 Lµ .2. α ≤ 1 L and β ≤ 1 µnK , in which case we show that SEG-RR initialized at y 00 = σ √ Lµ suffers E z K 0 2 = Ω σ 2 Lµ ,3. α ≤ 1 L and 1 µnK < β < 1 nL , in which case we show that SEG-RR initialized at x 0 0,2 = 0 suffersE z K 0 2 = ΩLσ 2 µ 3 nK 3 , 4. α ≤ 1 L , β > 1 µnK , and β ≥ 1 nL in which case we show that SEG-RR initialized at x 0 0,2 = 0 suffersE z K 0 2 = Ω σ 2 LµnK .Notice that the third case 1 µnK < β < 1 nL only makes sense when K > L/µ; otherwise, the third case just disappears. Hence, for the "large epoch" regime where K > L/µ, the third case achieves the minimum error possible, so it holds thatE z K 0 2 = ΩLσ 2 µ 3 nK 3 .For the "small epoch" regime (K ≤ L/µ), the third case does not exist and the fourth case achieves the minimum, soE z K 0 2 = Ω σ 2 LµnK .Combining the two cases yields the desired lower bound in the theorem statement. It is now left to carry out the case analysis.Case 1: α > 1 L . For this case, we use (122) to prove divergence. Notice from α > 1 L that 1 -βL + αβL 2 = 1 + βL(αL -1) > 1, regardless of β > 0. Hence, from (122), we getE z K 0 2 ≥ (x K 0,1 ) 2 > (x 0 0,1 ) 2 .If we initialize at x 0 0,1 = σ √ Lµ , then this provesE z K 0 2 ≥ σ 2 Lµ .Case 2: α ≤ 1 L and β ≤ 1 µnK . For this case, we employ (124) to show that the "contraction rate" is too small to make enough "progress." Notice from our stepsizes that1 -βµ + αβµ 2 ≥ 1 -βµ ≥ 1 - 1 nK ≥ 0.Applying this inequality to (124), we have(y k+1 0 ) 2 ≥ 1 - 1 nK 2n (y k 0 ) 2 ,which in turn means that the progress over K epoch is bounded from below by(y K 0 ) 2 ≥ 1 - 1 nK 2nK (y 0 0 ) 2 ≥ (y 0 0 ) 2 16 ,where we used our assumption that n ≥ 2 and K ≥ 1. Hence, if our initialization was given as y 0 0 = σ √ Lµ , then this provesE z K 0 2 ≥ (y K 0 ) 2 ≥ (y 0 0 ) 2 16 = Ω σ 2 Lµ .Case 3: α ≤ 1 L and 1 µnK < β < 1 nL . For stepsizes in this interval, we use (123) to derive the desired bound. Here, it is important to characterize a lower bound on the quantityE[Φ 2 ] := E   n i=1 (2s τ k (i) -1) 1 - βL 2 + αβL 2 4 n-i 2   .To this end, we can use a lemma from Safran & Shamir (2020), stated below: is to ensure a sufficient decay rate following Theorem 5.4, but the value of η 0 is a heuristically determined small number.The results are plotted in Figure 1 . To have a fair comparison between the methods and across the random instances, we compute the ratio ∥F z t 0 ∥ 2 ∥F z 0 0 ∥ 2 where t denotes the number of passes, and plot the geometric mean over the 5 runs. Notice that, for SEG-FFA and SEG-FF, we are then plotting the values ofF z t/2 0 2 ∥F z 0 0 ∥ 2 instead of ∥F z t 0 ∥ 2 ∥F z 0 0 ∥2 , because SEG-FFA and SEG-FF takes two passes per epoch (i.e., the number of epochs is half the number of passes) while other methods take one pass per epoch.As it is predictable from our theoretical results, SEG-FFA successfully shows convergence, while all of SEG-FF, SEG-RR, and SEG-US diverge in the long run. As for anchoring, it turns out that adding the anchoring step does improve the performance of the method up to a certain level, but it alone does not fully resolve the nonconvergence issue: observe that both SEG-RRA and SEG-USA fail to demonstrate convergence.Monotone case: comparison with (Hsieh et al., 2020) Let us also compare the performance of SEG-FFA with the independent-sample double stepsize SEG (DSEG) by Hsieh et al. (2020) . Writing in terms of the finite-sum structure, the update rule of DSEG can be written asw k ← z k -η 1,k F i(1,k) z k z k+1 ← z k -η 2,k F i(2,k) w kwhere 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 η 1,k = Θ( 1 /k r 1 ) and η 2,k = Θ( 1 /k r 2 ), where setting r 1 ≤ r 2 is the key point of DSEG. Two choices of the exponent pair (r 1 , r 2 ) proposed in (Hsieh et al., 2020) 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, we found that η 1,k = η0 /(k+19) r 1 and η 2,k = η0 /(k+19) r 2 , where again η 0 = min{0.01, 1 L }, works the best among the candidates we have tried (and the choices in (Hsieh et al., 2020) ). The number 19 in the denominators is the constant suggested in the experiments section of (Hsieh et al., 2020) .The results are displayed in Figure 2 , where the details on how the plots are drawn are the same as Figure 1 . Here we can see that SEG-FFA shows also a faster speed of convergence than both versions of DSEG. /∥F z 0 0 ∥ 2 for SEG-FFA and SEG-FF.Strongly monotone case For the experiment in the strongly monotone case we again use the random quadratic problem ( 128), but with different choices of A i and C i to ensure the objective function to be strongly-convex-strongly-concave. In particular, for each i = 1, . . . , n, we sample A i by computingA i = Q i D i Q ⊤ i, where D i is a random diagonal matrix whose diagonal entries are i.i.d. samples from a uniform distribution over the interval [ 1 2 , 1], and Q i is a random orthogonal matrix obtained by computing a QR decomposition of a 20 × 20 random matrix whose elements are i.i.d. samples from a standard normal distribution. We sample C i by the exact same method.As we are considering strongly-convex-strongly-concave problems, along with the variants of SEG, we also compare the performances of SGDA-RR and SGDA-US. We ran the experiment on 5 random instances of (128) with stepsizes η k ≡ 0.001.The results are plotted in Figure 3 , where the details of the plotting are the same as the monotone cases. We again observe an agreement between the empirical result and our theory; all methods used in the experiment are expected to find a point with a reasonably small gradient, but nonetheless, the fastest decrease of the gradient norm is demonstrated by SEG-FFA. Moreover, we see that SEG-FFA eventually finds the point with the smallest gradient norm among the methods that are considered.The anchoring in this paper simply averages the initial and terminal points of the epoch. The readers should not be confused with the anchoring in(Cai et al.,2022; Yoon & Ryu, 2021;Lee & Kim, 2021), which are based specifically on the Halpern iteration(Halpern, 1967).2 This paper focuses on the same-sample version of SEG, which uses a single sample for both extrapolation and update steps in the update of SEG (seeBeznosikov et al. (2023) for the details). So, to be precise, we are stating here that the same-sample SEG-US suffers divergence, which does not contradictHsieh et al. (2020) where the authors show that the independent-sample (i.e., independent samples for extrapolation and update steps) version of SEG converges to optima for convex-concave settings, albeit without a convergence rate.Gorbunov et al. (2022a) do not assume any condition on the variance, but their results require a strong regularity condition that is close to assuming strong monotonicity for the majority of component functions. 


Decision: 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.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: 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.
2. How to select the parameter $\epsilon$ concerning convergence in Table 1 and Theorem 5.5 for practical applications and specific problems.
3. 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?
questions: 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.
2. What is the difference between the stepsizes $\alpha_k, \beta_k$ of SEG-FF and $\eta_k$ of SEG-FFA.
3. 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.
4. There are few typos in the main text and appendix.
limitations: limitations: 1. The length of the paper is excessive, especially the appendix section.
2. The experiments could consider demonstrating the performance of SEG-FFA on more large-scale problems.
paper_summary: paper_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.
strength_weakness: strength_weakness: - Lipschitz Hessian in Assumption 3.3 is too restrictive, and the authors agree. I don't know if practical ML applications satisfy such assumptions. 
- 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. 
- 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?
questions: questions: - What is $\eta_k$ in Theorem 5.4? The step sizes of SEG-FFA are $\alpha_k$ and $\beta_k$ in Eq 5. 
- Is it possible to relax Assumption 3.3? 
- 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$.


[1] "Single-Call Stochastic Extragradient Methods for Structured Non-monotone Variational Inequalities: Improved Analysis under Weaker Conditions."
 
[2] "Solving stochastic weak Minty variational inequalities without increasing batch size."
limitations: limitations: NA
paper_summary: paper_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.
strength_weakness: strength_weakness: I've listed a few questions in the section below but I don't think there are major weakness with the paper.

Minor comments: 

- 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.

- 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$?
questions: 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.

- 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?

- In Theorem 5.4, can one afford a constant (and larger) stepsize if instead of asking guarantee in $\min_k ...$ we do tail averaging?

- The parameter $\rho$ or $\sigma$ from Assumption 3.4 don't make an appearance in Theorem 5.4 and 5.5?

- What's the difficulty of generalizing this framework from same sample to independent sample extragradient methods?
limitations: limitations: Yes it's adequately addressed.
paper_summary: paper_summary: The paper studies unconstrained (strongly)-monotone finite sum minimization problems. They introduce a new scheme called SEG-FFA which:

i) for a given epoch runs stochastic extragradient (SEG) with possibly two different stepsizes
ii) uses flip-flop shuffling per epoch
iii) uses the average of the epoch initialization and the last iterate as the initialization for the next epoch

With $K$ being the number of epochs and $n$ being the number of finite sum elements, they show:

- For the monotone case a $\tilde{\mathcal O}(1/K^{1/3})$ rate for the squared norm of the operator.
- 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)$.
strength_weakness: strength_weakness: My main concern is with the strength of the results:

- 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)
- 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.

Other concerns:

- 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?
- 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.
- 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.

Minor:

- 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.

Related work:

- 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)
questions: questions: See weaknesses.
limitations: limitations: The paper lacks appropriate discussion on the rates obtained in the main results of Thm. 5.4-5.5 (see weaknesses).

Comments: comment: We are glad that our explanations have cleared up your concerns. If there are further comments or questions, we would be glad to continue our discussion.
We are pleased that your concerns have been resolved. We will ensure that the additional details discussed in the comments are well incorporated into the revision.

If you have any further questions or comments, we would be happy to address them.
Thank you for your time and effort in reviewing our work. If you have anything you would like to discuss further, please feel free to leave additional comments.
We appreciate your thoughtful reevaluation of our work.

We agree that the strongly monotone case results now deserve more emphasis than in the original manuscript given the improvement, and that the current convergence rate in the (star-)monotone case is not ideal. While we fully respect your perspective, we also hope you understand our assertion that the monotone case result is worth some highlighting, as it effectively demonstrates our second-order matching framework and offers new theoretical explanations on how the SEG variants behave in the more practical setting where stochastic gradients are used throughout the optimization procedure. In the revision, we will
adjust our tone, taking into account what deserves more attention and what remains relatively limited.

Regarding the connection between our work and the Lookahead method, we thoroughly agree with you; we condensed our viewpoint into the phrase “interesting resemblance” because of the character limit. Your additional suggestions will help us make a more detailed comparison in our revision.

Please feel free to add any further comments or questions.
I thank the authors for providing detailed replies to all my concerns.  The authors' discussions on the practical algorithms and theoretical investigation are thoughtful.
Thanks for the explanation. I intend to keep my rating.
I thank the authors for the rebuttal, which addresses my concern regarding the strongly monotone case, where there now seems to be a significant improvement in terms of the rate. Trusting that the derivation is correct and that the constant $b$ does not have strange dependencies (like e.g. on $\Vert z^0-z^* \Vert^2$), I have increased my score.

I still consider the results in the monotone case somewhat unsatisfying, since the rate $\mathcal O(1/K^{1/3})$ is worse than the $\mathcal O(1/K)$ rate of EG. In other words, there seem to be no reason for running SEG-FFA if we know that only monotonicity holds:

- For this reason I would downplay the monotone case by instead focusing on SEG-FFA provably benefiting the strongly monotone, while providing some kind of "fallback" guarantee in the monotone case.
- Since we are in the finite sum case it is possible to run deterministic methods (e.g. EG) even with same memory footprint by simple accumulating gradients. I suggest comparing against EG in Table 1.

> "there is an interesting resemblance between SEG-FFA and the mentioned Lookahead methods"

I would argue that its more than a resemblance, since Lookahead has also been connected with the Krasnosel’skii-Mann iteration (see e.g. https://arxiv.org/pdf/2310.13459). Compared with Lookahead with EG+ as the base optimizer the main differences seems to be:

- SEG-FFA picks a smaller extrapolation stepsize (so that the inner loop is no longer strictly the EG+ scheme of [16] – this is why I think it is important to differentiate SEG-FFA from EG+ regarding the inner loop. Your modification is crucial!)
- SEG-FFA uses flip-flop

Both are important modification, so I am not trying to argue against the contributions, but I think making the connection precise might be valuable. Especially considering that both Lookahead for minimax and the original Lookahead algorithm for minimization (https://arxiv.org/pdf/1907.08610) introduces the scheme in order to reduce variance.
Thank you for the reply. Please add the above details in the updated version.

I will raise my score to 6.