Paper deep dive
Linear Convergence in Games with Delayed Feedback via Extra Prediction
Yuma Fujimoto, Kenshi Abe, Kaito Ariu
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 93%
Last extracted: 7/20/2026, 11:48:11 PM
Summary
This paper analyzes the linear convergence of Weighted Optimistic Gradient Descent-Ascent (WOGDA) in unconstrained bilinear games with delayed feedback. It demonstrates that while standard optimism (next-step prediction) yields a convergence rate of exp(-Theta(t/m^5)), employing extra optimism (predicting farther future rewards) significantly accelerates the rate to exp(-Theta(t/(m^2 log m))) and allows for larger step sizes, serving as an effective countermeasure against performance degradation caused by delays.
Entities (6)
Relation Signals (5)
WOGDA → solves → Bilinear Games
confidence 95% · This paper derives the rate of linear convergence of Weighted Optimistic Gradient Descent-Ascent (WOGDA)... in unconstrained bilinear games.
Extra Optimism → accelerates → Linear Convergence
confidence 93% · employing extra optimism... significantly accelerates the rate to exp(-Theta(t/(m^2 log m)))
WOGDA → approximates → EPP
confidence 92% · To analyze the algorithm, we interpret it as an approximation of the Extra Proximal Point (EPP)
Feedback Delay → degrades → Performance
confidence 90% · They are known to severely degrade performance
WOGDA → mitigates → Feedback Delay
confidence 88% · In summary, this paper validates that extra optimism is a promising countermeasure against performance degradation caused by feedback delays.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:Feedback delays are inevitable in real-world multi-agent learning. They are known to severely degrade performance, and the convergence rate under delayed feedback is still unclear, even for bilinear games. This paper derives the rate of linear convergence of Weighted Optimistic Gradient Descent-Ascent (WOGDA), which predicts future rewards with extra optimism, in unconstrained bilinear games. To analyze the algorithm, we interpret it as an approximation of the Extra Proximal Point (EPP), which is updated based on farther future rewards than the classical Proximal Point (PP). Our theorems show that standard optimism (predicting the next-step reward) achieves linear convergence to the equilibrium at a rate $\exp(-\Theta(t/m^{5}))$ after $t$ iterations for delay $m$. Moreover, employing extra optimism (predicting farther future reward) tolerates a larger step size and significantly accelerates the rate to $\exp(-\Theta(t/(m^{2}\log m)))$. Our experiments also show accelerated convergence driven by the extra optimism and are qualitatively consistent with our theorems. In summary, this paper validates that extra optimism is a promising countermeasure against performance degradation caused by feedback delays.
Tags
Links
- Source: https://arxiv.org/abs/2602.17486v1
- Canonical: https://arxiv.org/abs/2602.17486v1
Trouble viewing inline? Open PDF directly →
Full Text
60,639 characters extracted from source content.
Expand or collapse full text
Linear Convergence in Games with Delayed Feedback via Extra Prediction Yuma Fujimoto Kenshi Abe Kaito Ariu Abstract Feedback delays are inevitable in real-world multi-agent learning. They are known to severely degrade performance, and the convergence rate under delayed feedback is still unclear, even for bilinear games. This paper derives the rate of linear convergence of Weighted Optimistic Gradient Descent-Ascent (WOGDA), which predicts future rewards with extra optimism, in unconstrained bilinear games. To analyze the algorithm, we interpret it as an approximation of the Extra Proximal Point (EPP), which is updated based on farther future rewards than the classical Proximal Point (P). Our theorems show that standard optimism (predicting the next-step reward) achieves linear convergence to the equilibrium at a rate exp(−Θ(t/m5)) (- (t/m^5)) after t iterations for delay m. Moreover, employing extra optimism (predicting farther future reward) tolerates a larger step size and significantly accelerates the rate to exp(−Θ(t/(m2logm))) (- (t/(m^2 m))). Our experiments also show accelerated convergence driven by the extra optimism and are qualitatively consistent with our theorems. In summary, this paper validates that extra optimism is a promising countermeasure against performance degradation caused by feedback delays. Bilinear Games, Learning in Games, Last-Iterate Convergence, Optimistic 1 Introduction Online learning aims for efficient sequential decision-making. Typically, it assumes an ideal situation in which current strategies can be determined from all the past feedback. In real-world online learning scenarios, however, delays in feedback are generally inevitable. For instance, in online advertising, there is often a significant time lag between displaying an ad and observing a conversion (Chapelle, 2014; Yoshikawa & Imai, 2018; Yasui et al., 2020). Similarly, in distributed learning, communication latency and asynchronous updates inherently introduce delays in gradient aggregation (Agarwal & Duchi, 2011; McMahan & Streeter, 2014; Zheng et al., 2017). Indeed, a considerable number of papers on online learning are motivated by such feedback delays and report that delays amplify regret for full feedback (Weinberger & Ordentlich, 2002; Zinkevich et al., 2009; Quanrud & Khashabi, 2015; Joulani et al., 2016; Shamir & Szlak, 2017) and bandit feedback (Neu et al., 2010; Joulani et al., 2013; Desautels et al., 2014; Cesa-Bianchi et al., 2016; Vernade et al., 2017; Pike-Burke et al., 2018; Cesa-Bianchi et al., 2018; Li et al., 2019). Such feedback delays have also been of interest in multi-agent learning or learning in games (Zhou et al., 2017; Hsieh et al., 2022) and are known to severely degrade performance (Fujimoto et al., 2025a). This is because good performance in multi-agent learning is based on each agent predicting their future reward, and feedback delays make this prediction more challenging. Indeed, Optimistic Follow the Regularized Leader (OFTRL), which is a predictive algorithm and enjoys O(1)O(1)-regret under instantaneous feedback, suffers from Ω(T) ( T)-regret for the time horizon T. Even if we adopt a delay-correction mechanism called “Weighted” OFTRL (WOFTRL), the regret scales as O(m2)O(m^2), growing too large with delay m. Despite these prior studies, fundamental challenges remain in delayed feedback in multi-agent learning, especially about convergence analysis in bilinear games, defined as max∈min∈T. _ x _ y x^T B y. (bilinear game) The prior study (Fujimoto et al., 2025a) proved WOFTRL converges to the equilibrium, called last-iterate convergence (LIC), when X and Y are constrained to probability spaces. However, LIC in the unconstrained setting =ℝdXX=R^d_X and =ℝdYY=R^d_Y under delayed feedback is not guaranteed. Furthermore, its convergence rate is still unestablished. Finding this rate is vital for understanding how quickly agents can stabilize their strategies in applications, and thus convergence rate is an attractive topic in the context of learning in games. Lastly, although the experiment in the prior research suggests that predicting the farther future than necessary to correcting the delays (called “extra prediction”) results in faster convergence, the validity of this extra prediction has yet to be established. In this paper, we address these open problems in unconstrained bilinear games. Our contributions are as follows. • We establish the rate of linear convergence even with feedback delays. We approximate our algorithm WOGDA by Extra Proximal Point (EPP), an extension of classical Proximal Point (P) to predict future rewards. We prove that EPP linearly converges and that the difference between WOGDA and EPP is sufficiently small by setting the step size appropriately. • We demonstrate that extra prediction accelerates convergence. We find that extra prediction permits larger step sizes, and the underlying EPP converges faster. Therefore, WOGDA with extra prediction achieves much faster convergence at the scale of delay m. • Our theoretical results are also reproduced in experiments. Both the linear convergence and the acceleration by extra prediction are observed in experiments using both representative (Matching Pennies) and unintended (5×55× 5 random matrix) games. Unconstrained bilinear games: This study targets the class of unconstrained bilinear games. This class is closely related to min-max optimization, and convergence is an important issue there. Also, unconstrained bilinear games are one of the minimum necessary configurations (zero-sum utility and Euclidean strategy space), including difficulties specific to multi-agent learning, and thus have the potential to develop into other various advanced configurations, such as convex-concave utility and constrained strategy space. Indeed, the celebrated study showing LIC in unconstrained bilinear games (Daskalakis et al., 2018) has been thereafter applied to the constrained setting (Mertikopoulos et al., 2019). The linear convergence was first demonstrated in unconstrained bilinear games (Mokhtari et al., 2020) and later shown to hold in constrained saddle-point problems (Wei et al., 2021). Also, LIC in time-varying games was first proven in unconstrained bilinear games (Feng et al., 2023) and later discussed for the constrained setting (Feng et al., 2024; Fujimoto et al., 2025b). To summarize, unconstrained bilinear games serve as a touchstone for analyzing novel phenomena in learning in games. Analysis Based on P method: Many algorithms in learning in games are analyzed based on the P method. Here, P linearly converges to equilibrium and thus is a powerful algorithm, but its applicability is limited because it uses the information on the next-step reward (thus, implicit and coupled method). For example, in the unconstrained setting, P is used to evaluate predictive variant of gradient descent-ascent (GDA), i.e., optimistic GDA (OGDA) (Mokhtari et al., 2020). In the constrained setting, optimistic algorithms are analyzed using the next-step reward (Rakhlin & Sridharan, 2013; Syrgkanis et al., 2015). A method that approximates this P with arbitrary precision has been proposed (Piliouras et al., 2022; Cevher et al., 2023). Overall, the advantage of predicting the next step has been widely discussed, but this advantage is still unexplained for predicting farther future than the next step. 2 Unconstrained Bilinear Game This study addresses bilinear game with unconstrained setting =ℝdXX=R^d_X and =ℝdYY=R^d_Y. The solution of this bilinear game is given by (∗,∗)( x_*, y_*) such that T∗=,∗=. B^T x_*= 0, B y_*= 0. (1) For each time t∈1,⋯,Tt∈\1,·s,T\, each player determines their strategies as t∈ℝdX x_t ^d_X and t∈ℝdY y_t ^d_Y. Each game play returns the full feedback, where each player observes the gradient of their objective function, i.e., t=t u_t= B y_t for X and t=−Tt v_t=- B^T x_t for Y. 2.1 Delayed Feedback While standard online learning assumes instantaneous feedback where each player can use all their strategies and receive rewards up to time t to determine their next strategy, this study addresses a realistic scenario involving a fixed time delay of m steps in observing their rewards. Formally, although player X should determine their next strategy as a function t+1(s0≤s≤t,s0≤s≤t) x_t+1(\ x_s\_0≤ s≤ t,\ u_s\_0≤ s≤ t) in the standard setting, suppose that under delayed feedback with m∈ℕm , they should instead determine a function t+1(s0≤s≤t,s0≤s≤t−m). x_t+1(\ x_s\_0≤ s≤ t,\ u_s\_0≤ s≤ t-m). (Delayed Feedback) 2.2 Notation and Assumption For convenience, we introduce the notations of t=(t),t=(t), z_t= pmatrix x_t\\ y_t\\ pmatrix, w_t= pmatrix u_t\\ v_t\\ pmatrix, (2) =(−T),¯=(T). A= pmatrix O& B\\ - B^T& O\\ pmatrix, A= pmatrix O& B\\ B^T& O\\ pmatrix. (3) Here, t z_t and t w_t are the concatenation of the strategies and rewards, respectively. A is the matrix such that t=t w_t= A z_t holds. We also defined ¯ A, which satisfies ¯T=¯ A^T= A and T=¯2 A^T A= A^2. T=−,T=−2=¯2. A^T=- A, A^T A=- A^2= A^2. (4) Following the previous studies on linear convergence to the Nash equilibrium (Mokhtari et al., 2020), we also assume that B is a regular matrix. Assumption 2.1 (Regular Matrix Game). Suppose that dX=dY=:d_X=d_Y=:d and B is a regular matrix. This assumption is convenient for discussing several convergence properties. First, because B has the inverse matrix, the Nash equilibrium is uniquely given by ∗=∗= x_*= y_*= 0. Second, because B is a full-rank matrix, the skew-symmetric matrix A has only pure imaginary eigenvalues, denoted as ±iλmin,⋯,±iλmax± i _ ,·s,± i _ for some (0<)λmin≤⋯≤λmax(0<) _ ≤·s≤ _ . Thus, we can evaluate 0<λmin‖≤‖‖≤λmax‖, 0< _ \| z\|≤\| A z\|≤ _ \| z\|, (5) for all ∈ℝ2d∖ z ^2d \ 0\. We note that we use ∥⋅∥\|·\| indicates the Euclidean norm ∥⋅∥2\|·\|_2 throughout this paper. We also define the ratio of the maximum and minimum eigenvalues as κ=λmaxλmin(>1). κ= _ _ (>1). (6) Remark: Bilinear games can be extended to the following alternative problem max∈ℝdXmin∈ℝdYT+T′+T, _ x ^d_X _ y ^d_Y x^T B y+ x^T c + c^T y, (7) where ,′∈ℝd c, c ^d are unobservable vectors. The equilibrium of this alternative problem is ∗=−(T)−1 x_*=-( B^T)^-1 c and ∗=−1′ y_*=- B^-1 c . As similar to the study (Daskalakis et al., 2018), our algorithm is applicable to this alternative problem. Even though one might consider that ∗=∗= x_*= y_*= 0 is trivial equilibrium, this study, just for the simplicity of notation, chooses the special case of =′= c= c = 0 without loss of generality. 3 Algorithm In this work, we focus on Weighted Optimistic Gradient Descent-Ascent (WOGDA), which is the application of WOFTRL and WOMD algorithms (Fujimoto et al., 2025a) to unconstrained bilinear games. (Technically, WOGDA is obtained by replacing the constrained strategy domain with a Euclidean space and employing a Euclidean regularizer in WOFTRL and WOMD.) 3.1 WOGDA In the delayed feedback setting, the next strategy t+1 z_t+1 should be determined by the delayed rewards, i.e., 1,⋯,t−m w_1,·s, w_t-m. With extra prediction length n∈ℕn , the WOGDA gives t+1 z_t+1 as follows. ^t+1=^t+ηt+1t+1=^t−m+(n+m)ηt−m. cases z_t+1= z_t+η w_t+1\\ z_t+1= z_t-m+(n+m)η w_t-m cases. (WOGDA) Because the next strategy t+1 z_t+1 depends on ^t−m z_t-m (the first term) determined only by 1,⋯,t−m w_1,·s, w_t-m and t−m w_t-m (second), WOGDA is executable even with feedback delays m. By using the following notation Δt=t+1−t, a_t= a_t+1- a_t, (Δ -notation) WOGDA is also written as Δt z_t =ηt−m+(n+m)ηΔt−m−1. =η A z_t-m+(n+m)η A z_t-m-1. (8) Connection to GDA and OGDA: If there is no delay (m=0m=0), the WOGDA immediately reproduces the GDA (n=0n=0) and OGDA (n=1n=1) as t+1= z_t+1= t+ηt, \ z_t+η A z_t, (GDA) t+1= z_t+1= t+ηt+η(t−t−1). \ z_t+η A z_t+η A( z_t- z_t-1). (OGDA) Interpretation: Here, ^t z_t is a dummy variable and represents the cumulative rewards until the current time t. Thus, the strategy t+1 z_t+1 is given by the observable cumulative rewards ^t−m z_t-m and weighting the latest rewards (n+m)(n+m) times. Here, the weight m is interpreted as canceling out the delay, because depending on the delay length m, the number of observable rewards is reduced by m in ^t−m z_t-m. On the other hand, the weight n is interpreted as predicting the future reward, because the cumulative of future rewards t+1,⋯,t+n w_t+1,·s, w_t+n is extrapolated by the latest reward t−m w_t-m. Therefore, when n=1n=1, WOGDA predicts the next-step cumulative reward, called “next-step prediction”. When n>1n>1, it predicts further future cumulative rewards, called “extra prediction”. 4 Linear Convergence of WOGDA This section presents the main theorems, showing the rate of linear convergence of WOGDA. We consider two cases: n=1n=1 (next-step prediction) and n=m/2+1n=m/2+1 (extra prediction). Interestingly, depending on the difference of these n, the possible step size and convergence rate change on the scale of m. We skip the proofs of these main theorems until the later section, and see Appendix for the omitted full proofs. 4.1 Convergence by Next-Step Prediction Following the conventional methodology, suppose n=1n=1, where WOGDA predicts the reward at the next step, then we can provide the rate of linear convergence as follows. Theorem 4.1 (Linear Convergence by Next-Step Prediction). Suppose n=1n=1 and η=1/(56(m+1)2κ2λmax)η=1/(56(m+1)^2κ^2 _ ), then it holds ‖t‖ \| z_t\| ≤exp(−tcκ6(m+1)5)‖~0‖, ≤ (- tcκ^6(m+1)^5 )\| z_0\|, (9) with some positive constant c(>0)c(>0). Here, ‖~0‖\| z_0\| is defined as ‖~0‖ \| z_0\| =max0≤s≤4(m+1)‖s‖. = _0≤ s≤ 4(m+1)\| z_s\|. (10) Connection to Prior Research: Theorem 4.1 establishes a linear convergence rate, guaranteeing exponential convergence to equilibrium, whereas this remained an open question in previous work (Fujimoto et al., 2025a). Although our setting (unconstrained bilinear) differs to some extent from theirs (poly-matrix zero-sum), both approaches share the underlying mechanism (approximating the P method) and the step size scaling (η=O(1/m2)η=O(1/m^2)). 4.2 Convergence by Extra Prediction Beyond the conventional methodology, suppose n=m/2+1n=m/2+1, where WOGDA extra-predicts the reward beyond the next step, then we can prove accelerated linear convergence as follows. Theorem 4.2 (Linear Convergence by Extra Prediction). Suppose n=m/2+1n=m/2+1 and η=1/(93(m+1)2j2j−1κ2λmax)η=1/(93(m+1) 2j2j-1κ^2 _ ) with j=⌊log(m+1)⌋+2j= (m+1) +2, then it holds ‖t‖ \| z_t\| ≤exp(−tcκ6(m+1)2(log(m+1)+2))‖~0‖, ≤ (- tcκ^6(m+1)^2( (m+1)+2) )\| z_0\|, (11) with some positive constant c(>0)c(>0). Here, ‖~0‖\| z_0\| is defined as ‖~0‖ \| z_0\| =max0≤s≤2(m+1)(log(m+1)+2)‖s‖. = _0≤ s≤ 2(m+1)( (m+1)+2)\| z_s\|. (12) Accelerated convergence by extra prediction: Comparing Theorem 4.1 with Theorem 4.2, we see that the convergence rate is quite accelerated from exp(−Θ(t/m5)) (- (t/m^5)) in next-step prediction to exp(−Θ(t/(m2logm))) (- (t/(m^2 m))) in extra prediction. We also see that the step size increases from η=O(1/m2)η=O(1/m^2) in next-step prediction to η=O(1/(mlogm))η=O(1/(m m)) in extra prediction. Since a larger step size is known to destabilize convergence in general, extra prediction enhances the stability of WOGDA. In conclusion, extra prediction is a strong countermeasure against feedback delays in both accelerated and stabilized convergence, as later supported by rigorous proofs and experiments. 5 Proof of Theorems 4.1 and 4.2 To prove Theorems 4.1 and 4.2, we analyze the dynamics of WOGDA for all prediction lengths n∈ℕn and step sizes 0≤η≤O(1/(n+m))0≤η≤ O(1/(n+m)). The proof proceeds as follows. In §5.1, we prove that EPP, an implicit method approximating WOGDA, linearly converges. In §5.2, we evaluate the approximation error between WOGDA and EPP. In §5.3, we combine the convergence term by EPP and the error term. 5.1 Analysis of EPP We introduce EPP, an extension of the classical P method. For any t z_t, its EPP t+1† z _t+1 is determined as t+1†= z _t+1= t+ηt+nη(t+1†−t). \ z_t+η A z_t+nη A( z _t+1- z_t). (EPP) Here, n∈ℝn means the prediction length, corresponding to that in WOGDA. Connection to GDA and P: This EPP linearly connects well-known algorithms, GDA (n=0n=0) and P (n=1n=1) as t+1†= z _t+1= t+ηt, \ z_t+η A z_t, (GDA) t+1†= z _t+1= t+ηt+1†. \ z_t+η A z _t+1. (P) When n=0n=0, EPP corresponds to GDA and updates its strategy based on the previous reward t A z_t. When n=1n=1, EPP corresponds to P and is based on the next-step reward t+1† A z _t+1. When n>1n>1, EPP is based on the n-step future reward, meaning extra prediction. The dynamics of EPP satisfy the following lemma. Lemma 5.1 (Dynamics of EPP). For all n∈ℝn , 0≤η0≤η, and t∈ℝ2d z_t ^2d, it holds ‖t+1†‖2=tT+(n−1)2η2¯2+n2η2¯2t. \| z _t+1\|^2= z_t^T I+(n-1)^2η^2 A^2 I+n^2η^2 A^2 z_t. (13) Fraction of matrices: Here, note that we abused the fraction notation of matrices for convenience. This notation has no mathematical contradiction because the inverse matrix of the denominator (+n2η2¯2 I+n^2η^2 A^2) exists, and it is also commutative with the numerator (+(n−1)2η2¯2 I+(n-1)^2η^2 A^2). We will henceforth use this notation throughout this paper. Proof Sketch. First, EPP can be rewritten as (−nη)t+1†=(−(n−1)η)t. ( I-nη A) z _t+1=( I-(n-1)η A) z_t. (14) Since A is skew-symmetric, the inverse matrix of I−nηI-nη A exists and is also commutative with −(n−1)η I-(n-1)η A. Therefore, we obtain t+1†=−(n−1)ηI−nηt. z _t+1= I-(n-1)η AI-nη A z_t. (15) which derives Eq. (13). Here, note that by utilizing the properties of Eqs. (3), the cross terms between t x_t and t y_t cancels out and only the squared terms (corresponding to ¯2 A^2) remain. ∎ Since ¯ A has only positive eigenvalues, Lemma 5.1 immediately implies linear convergence as follows. Lemma 5.2 (Analysis of EPP). For all n∈ℝn , 0≤η≤1/(nλmin)0≤η≤ 1/(n _ ), and t∈ℝ2d z_t ^2d, it holds ‖t+1†‖ \| z _t+1\| ≤LCREPP(n)‖t‖, _EPP(n)\| z_t\|, (16) LCREPP(n) _EPP(n) =1−2n−12η2λmin2+n2(2n−1)2η4λmin4. =1- 2n-12η^2 _ ^2+ n^2(2n-1)2η^4 _ ^4. (Linear Convergence Rate of EPP) Proof. By Lemma 5.1, we obtain ‖t+1†‖2 \| z _t+1\|^2 =tT+(n−1)2η2¯2+n2η2¯2t = z_t^T I+(n-1)^2η^2 A^2 I+n^2η^2 A^2 z_t =1n2tT((n−1)2+(n2−(n−1)2)+n2η2¯2)t = 1n^2 z_t^T ((n-1)^2 I+ (n^2-(n-1)^2) I I+n^2η^2 A^2 ) z_t ≤1n2((n−1)2+n2−(n−1)21+n2η2λmin2)‖t‖2 ≤ 1n^2 ((n-1)^2+ n^2-(n-1)^21+n^2η^2 _ ^2 )\| z_t\|^2 =1+(n−1)2η2λmin21+n2η2λmin2‖t‖2 = 1+(n-1)^2η^2 _ ^21+n^2η^2 _ ^2\| z_t\|^2 (17) ≤LCREPP(n)2‖t‖2. _EPP(n)^2\| z_t\|^2. (18) In the final inequality, we used that the inequality (holding for all 0≤a≤b≤10≤ a≤ b≤ 1) 1+a1+b 1+a1+b ≤1−(b−a)(1−b) ≤ 1-(b-a)(1-b) ≤(1−12(b−a)(1−b))2. ≤ (1- 12(b-a)(1-b) )^2. (19) for a=(n−1)2η2λmin2a=(n-1)^2η^2 _ ^2 and b=n2η2λmin2b=n^2η^2 _ ^2. ∎ Interpretation: Lemma 5.2 is interpreted as LCREPP(n)=1−O(nη2)LCR_EPP(n)=1-O(nη^2), meaning that EPP achieves linear convergence under sufficiently small step sizes. Furthermore, it also shows that a larger n leads to faster convergence. Thus, if some external factor — just like delayed feedback — requires a small step size, EPP with extra prediction (n>1n>1) outperforms that with next-step prediction (n=1n=1, corresponding to classical P). We note that if no such factor exists, EPP no longer improves P. Indeed, the tighter rate, i.e., Eq. (17), shows that P (n=1n=1) converges arbitrarily fast in the limit of η→∞η→∞. Figure 1: Convergence in Matching Pennies with delayed feedback. We set the delay as m=10m=10 and the initial state as (0,0)=(/2,)( x_0, y_0)=( c/2, 0). In both panels, the solid lines are the trajectories on the plane of ⟨t,⟩ < x_t, c > and ⟨t,⟩ < y_t, c >. The black star markers are the Nash equilibria which satisfy ⟨∗,⟩=⟨∗,⟩=0 < x_*, c >= < y_*, c >=0. In A, the extra-optimistic weight is set to the minimum necessary value, n=1n=1. In B, it is to n=m/2+1=6n=m/2+1=6. The step size is respectively fine-tuned as η=10−1.95η=10^-1.95 in A and η=10−1.66η=10^-1.66 in B. The black cross marks indicate the first 2020 steps of learning, which visualize that learning proceeds more quickly in B than in A. The trajectory also requires fewer cycles until convergence in B than in A. Figure 2: Optimal step size (A) and optimal linear convergence rate (B) in Matching Pennies. The circle and triangle markers indicate n=1n=1 (next-step prediction) and n=m/2+1n=m/2+1 (extra prediction), respectively. We consider the delays from m=2m=2 (red) to m=80m=80 (purple). In A, the horizontal and vertical axes indicate logarithmic delay log10(m+1) _10(m+1) and logarithmic optimal step size log10η∗ _10η^*. The gray broken lines fit the circle markers with slope −3/2-3/2 and the triangle markers with slope −1-1, respectively. This means that the extra prediction admits a larger step size than the next-step prediction. In B, the vertical axis indicates logarithmic linear convergence rate log10(1−eLCR∗) _10(1-eLCR^*). The gray broken lines fit the circle markers with slope −3-3 and the triangle markers with slope −1-1, respectively. This means that the extra prediction converges faster than the next-step prediction. Figure 3: Optimal step size (A) and optimal linear convergence rate (B) in 5×55× 5 random matrix game. How to read the panels is the same as Figure 2. The initial state is (0,0)=(,)( x_0, y_0)=( 1, 0). 5.2 Evaluation of Error The difference between EPP (i.e., t+1† z _t+1) and WOGDA (i.e., t+1 z_t+1) is evaluated as follows. Lemma 5.3 (Dynamics of Error Term). For all n∈ℕn and 0≤η0≤η, it holds ‖t+1†−t+1‖2 \| z _t+1- z_t+1\|^2 =Δ2tTη2¯2+n2η2¯2Δ2t, = ^2 Z_t^T η^2 A^2 I+n^2η^2 A^2 ^2 Z_t, (20) t Z_t =n∑s=1m+1t−s+∑s=2m+1∑r=sm+1t−r. =n _s=1^m+1 z_t-s+ _s=2^m+1 _r=s^m+1 z_t-r. (21) Proof. We can directly obtain t+1†−t+1 z _t+1- z_t+1 =ηt+nη(t+1†−t) =\η A z_t+nη A( z _t+1- z_t)\ −ηt−m+(n+m)ηΔt−m−1 14.22636pt-\η A z_t-m+(n+m)η A z_t-m-1\ =η(t+1†−t+1)+ηnΔt =η A( z _t+1- z_t+1)+η A\n z_t +(Δt−1+⋯+Δt−m)−(n+m)Δt−m−1 14.22636pt+( z_t-1+·s+ z_t-m)-(n+m) z_t-m-1\ (22) =η(t+1†−t+1)+ηΔ2t. =η A( z _t+1- z_t+1)+η A ^2 Z_t. (23) Here, we remark that in Eq. (22), the numbers of +Δ+ z and −Δ- z are balanced, it degenerates to a finite number of Δ2 ^2 z. By using the fraction notation of matrices, we can write t+1†−t+1=η−nηΔ2t, z _t+1- z_t+1= η A I-nη A ^2 Z_t, (24) leading to Eq. (20) by performing the same operation as the proof of Lemma 5.1. ∎ Here, we note that ‖t+1†−t+1‖\| z _t+1- z_t+1\| is described as the finite number of Δ2s ^2 z_s, which is evaluated as sufficiently small below. Lemma 5.4 (Evaluation of Error Term). For all j,n∈ℕj,n and 0≤η≤1/(2(n+m)λmax)0≤η≤ 1/(2(n+m) _ ), it holds ‖t+1†−t+1‖≤ER(j,n)max2m≤s≤2j(m+1)‖t−s‖, \| z _t+1- z_t+1\| (j,n) _2m≤ s≤ 2j(m+1)\| z_t-s\|, (25) ER(j,n)=2(2n+m)(m+1)η3λmax3 (j,n)=2(2n+m)(m+1)η^3 _ ^3 +8(n+m)j+1ηj+2λmaxj+2 54.06006pt+8(n+m)^j+1η^j+2 _ ^j+2 +2(2n+m+1)(n+m)2jη2j+1λmax2j+1. 54.06006pt+2(2n+m+1)(n+m)^2jη^2j+1 _ ^2j+1. (Error Rate) Proof Sketch. By recursively substituting Eq. (8) j times, we obtain Δt= z_t= ∑k=1j(n+m)k−1ηkkt−k(m+1)+1 \ _k=1^j(n+m)^k-1η^k A^k z_t-k(m+1)+1 +(n+m)jηjjΔt−j(m+1). \ +(n+m)^jη^j A^j z_t-j(m+1). (26) ER(j,n)ER(j,n) is obtained by applying Eq. (26) to Δ2t ^2 Z_t twice and upper-bounding all t−s z_t-s by maxst−s _s z_t-s. Here, the first term of ER(j,n)ER(j,n) corresponds to the product of the first terms of Eq. (26). The second term of ER(j,n)ER(j,n) corresponds to the product of the first and second terms of Eq. (26). The third term of ER(j,n)ER(j,n) corresponds to the product of the second terms of Eq. (26). ∎ 5.3 Combination of EPP and Error By combining the convergence term by EPP and the error term, we can analyze WOGDA as follows. Theorem 5.5 (Analysis of WOGDA). For all j,n∈ℕj,n and 0≤η≤1/(2(n+m)λmax)0≤η≤ 1/(2(n+m) _ ), we derive ‖t+1‖≤LCRWOGDA(j,n)max0≤s≤2j(m+1)‖t−s‖, \| z_t+1\| _WOGDA(j,n) _0≤ s≤ 2j(m+1)\| z_t-s\|, (27) LCRWOGDA(j,n)=LCREPP(n)+ER(j,n). _WOGDA(j,n)=LCR_EPP(n)+ER(j,n). (Linear Convergence Rate of WOGDA) Proof. Eq. (27) is obvious by the triangle inequality of ‖t+1‖≤‖t+1†‖+‖t+1†−t+1‖, \| z_t+1\|≤\| z _t+1\|+\| z _t+1- z_t+1\|, (28) with the results from Lemma 5.2 and Lemma 5.4 ‖t+1†‖ \| z _t+1\| ≤LCREPP(n)‖t‖, _EPP(n)\| z_t\|, (29) ‖t+1†−t+1‖ \| z _t+1- z_t+1\| ≤ER(j,n)max2m≤s≤2j(m+1)‖t−s‖. (j,n) _2m≤ s≤ 2j(m+1)\| z_t-s\|. (30) ∎ Finally, Theorem 5.5 immediately derives Theorems 4.1 and 4.2 by setting the step size properly to cancel out the convergence and error terms. The proof sketches are below. Proof Sketch of Theorem 4.1. When n=1n=1, WOGDA linearly converges with the rate of LCREPP(1)=1−O(η2λmin2)LCR_EPP(1)=1-O(η^2 _ ^2). On the other hand, it also diverges with the rate of ER(j,1)=O(m2η3λmax3)ER(j,1)=O(m^2η^3 _ ^3). In order to cancels out the terms of O(η2λmin2)O(η^2 _ ^2) with O(m2η3λmax3)O(m^2η^3 _ ^3), we should set the step size as η=O(1/(m2κ2λmax))η=O(1/(m^2κ^2 _ )). When j≥2j≥ 2, the other terms can be ignored with this step size. Therefore, we set j=2j=2 at best and obtain the convergence rate as LCRWOGDA(2,1)=1−O(η2λmin2)=exp(−Θ(1/(κ6m4)))LCR_WOGDA(2,1)=1-O(η^2 _ ^2)= (- (1/(κ^6m^4))). This convergence rate scales down to exp(−Θ(1/(κ6m5))) (- (1/(κ^6m^5))) because the convergence delays O(m)O(m) times by the definition of Eq. (27). ∎ Proof Sketch of Theorem 4.2. When n=m/2+1n=m/2+1, WOGDA linearly converges with the rate of LCREPP(m/2+1)=1−O(mη2λmin2)LCR_EPP(m/2+1)=1-O(mη^2 _ ^2). On the other hand, it also diverges by the effect of ER(j,n)ER(j,n), and the leading term is O(m2j+1η2j+1λmax2j+1)O(m^2j+1η^2j+1 _ ^2j+1). In order to cancels out the terms of O(mη2λmin2)O(mη^2 _ ^2) with O(m2j+1η2j+1λmax2j+1)O(m^2j+1η^2j+1 _ ^2j+1), we should set the step size as η=O(1/(m2j2j−1κ2λmax))η=O(1/(m 2j2j-1κ^2 _ )), immediately leading to the convergence rate of LCRWOGDA(j,m/2+1)=1−O(mη2λmin2)=exp(−Θ(1/(κ6m1+22j−1)))LCR_WOGDA(j,m/2+1)=1-O(mη^2 _ ^2)= (- (1/(κ^6m^1+ 22j-1))). This rate scales down to exp(−Θ(1/(κ6jm2+22j−1))) (- (1/(κ^6jm^2+ 22j-1))) because the convergence delays O(jm)O(jm) times by the definition of Eq. (27). It takes the minimum value of exp(−Θ(1/(κ6m2logm))) (- (1/(κ^6m^2 m))) when j=O(logm)j=O( m). ∎ 6 Experiments This section numerically tests the performance of the WOGDA, based on the two measures of the optimal step size η∗η^* and the estimated linear convergence rate there eLCR∗eLCR^*. As far as we have conducted, our experiments guarantee that if WOGDA converges with a step size, it also converges with smaller step sizes. Thus, a larger step size contributes not only to faster convergence but also to the stability of convergence. Experimental Setup: For each delay m and prediction length n, we run WOGDA with 251251 step sizes of η=10−1.00,10−1.01,⋯,10−3.50η=10^-1.00,10^-1.01,·s,10^-3.50. We stop the algorithm either 10−9≤‖t≤10910^-9≤\| z\|_t≤ 10^9 or 104≤t10^4≤ t no longer holds. We measure the estimated linear convergence rate eLCReLCR by the final 100100 steps of t z_t. Finally, the optimal step size η∗η^* is one such that minimize eLCReLCR, and the optimal estimated linear convergence rate eLCR∗eLCR^* is the minimum eLCReLCR. First, let us pick up Matching Pennies, whose payoff matrix is given by =⊗,:=(+1−1). B= c c, c:= pmatrix+1\\ -1\\ pmatrix. (Matching Pennies) Because this payoff matrix is not regular, the Nash equilibrium is not unique but all (∗,∗)( x_*, y_*) such that ⟨∗,⟩=⟨∗,⟩=0 < x_*, c >= < y_*, c >=0. We should employ another measure for the distance from these equilibria as ⟨t,⟩2+⟨t,⟩2 < x_t, c >^2+ < y_t, c >^2. Matching Pennies is out of our theoretical scope, but our algorithm remains applicable. Fast convergence by Extra Prediction: We consider Matching Pennies with the delay m=10m=10. Figure 1-A considers the minimum optimistic weight n=1n=1 (next-step prediction), while B considers the extra weight n=m/2+1=6n=m/2+1=6 (extra prediction). In both A and B, we tuned the step size to the optimal one. We see two merits to take the extra weight. One is that the optimal step size is larger in B than in A. Another is that convergence to the Nash equilibrium is quick without cycling too many times. Scaling law: Keeping using Matching Pennies, we next see how the optimal step size and the linear convergence rate depend on the delay m. In Figure 2-A, which compares the optimal step size η∗η^* between n=1n=1 (next-step prediction) and n=m/2+1n=m/2+1 (extra prediction), we see that it shrinks with delay as η∗=O(1/m3/2)η^*=O(1/m^3/2) in n=1n=1, but this shrinking becomes slower in n=m/2+1n=m/2+1 as η∗=O(1/m)η^*=O(1/m). On the other hand, Figure 2 compares the optimal linear convergence rate eLCR∗eLCR^*, where we observe that convergence slows down with delay in n=1n=1 as eLCR∗=1−O(1/m3)eLCR^*=1-O(1/m^3), but it is faster in n=m/2+1n=m/2+1 as eLCR∗=1−O(1/m)eLCR^*=1-O(1/m). Random-matrix game: Not only for Matching Pennies, but we also conduct experiments for a randomly-generated 5×55× 5 matrix game, all of whose elements follows Gaussian distribution (0,1)N(0,1). Figure 3 observes that the same scaling law as in Matching Pennies holds. An interesting observation is that the scaling law for n=1n=1 is disordered a little as if the convergence speed must be lower than in n=m/2+1n=m/2+1. We see similar scaling law in all 1010 random matrices generated independently. 7 Discussion Comparison between theory and experiment: Our theoretical and experimental results share the qualitative consensus that extra prediction permits larger step sizes and accelerates convergence. We remark that a quantitative gap remains between these theoretical and experimental results. Regarding the next-step prediction, the optimal step size is O(1/m2)O(1/m^2) in theory versus O(1/m3/2)O(1/m^3/2) in experiments, and the corresponding convergence rate is exp(−Θ(t/m5)) (- (t/m^5)) in theory versus exp(−Θ(t/m3)) (- (t/m^3)) in experiments. Similarly, for the extra prediction, the optimal step size is O(1/(mlogm))O(1/(m m)) in theory versus O(1/m)O(1/m) in experiment, and the corresponding convergence rate is exp(−Θ(t/(m2logm))) (- (t/(m^2 m))) in theory versus exp(−Θ(t/m)) (- (t/m)) in experiment. Bridging the gap between these theories and experiments is an open problem. Especially for the extra prediction, however, the rate in theory could potentially be tightened to exp(−Θ(t/(mlogm))) (- (t/(m m))) by discovering the Lyapunov function and avoiding the bound using the max function in Eq. (25). Alternative algorithm that is memory complex: There is a way to force the existing algorithm OGDA to adapt to delayed feedback. Suppose m+1m+1 OGDA algorithms, labeled as OGDA0OGDA_0 to OGDAmOGDA_m, in parallel, and the reward at time t is assigned to OGDAtmod(m+1)OGDA_t (m+1). Although this parallelized algorithm trivially achieves the linear convergence rate of exp(−Θ(t/m)) (- (t/m)) by applying the previous paper (Mokhtari et al., 2020), it crucially suffers from the memory complexity of O(m)O(m). Because this memory complexity is obviously incomparable to ours O(1)O(1), we did not compare the parallelized algorithm with ours, but we note that at least, WOGDA also achieves the rate of exp(−Θ(t/m)) (- (t/m)) as well as the memory complexity of O(1)O(1) in our experiments. Robustness to stochastic and unknown delays: Although our algorithm assumes a fixed and known delay m∈ℕm , we hypothesize that exact knowledge of m is not strictly required to enjoy the qualitative benefits of extra prediction. In real-world scenarios such as online advertising, feedback delays are often stochastic or unknown, but their time scale is thought to be easily observable. As shown in the proof sketches in Theorems 4.1 and 4.2, we have discussed how the term contributing to convergence (i.e., LCREPP(n)LCR_EPP(n)) cancels out that contributing to divergence (i.e., ER(j,n)ER(j,n)), and this discussion is applicable to uncertainty in delays that does not affect the scale. Although a precise step size under unknown delays remains an open problem, this observation suggests that WOGDA could be robust to such uncertain delays. Conclusion: This paper has established the rate of linear convergence in learning in games with feedback delays. The convergence was proven based on unconstrained bilinear games, complementary to LIC in past constrained settings. This linear rate is a strong contribution to agents quickly stabilizing their optimal strategies. Furthermore, we successfully accelerated this convergence by introducing a novel mechanism that predicts the future reward farther away than the next step. This study developed a strong countermeasure against delayed feedback in learning in games. Impact Statement This paper presents work whose goal is to advance the field of Learning in Games, Multi-Agent Learning, and Online Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here. References Agarwal & Duchi (2011) Agarwal, A. and Duchi, J. C. Distributed delayed stochastic optimization. In NeurIPS, 2011. Cesa-Bianchi et al. (2016) Cesa-Bianchi, N., Gentile, C., Mansour, Y., and Minora, A. Delay and cooperation in nonstochastic bandits. In COLT, 2016. Cesa-Bianchi et al. (2018) Cesa-Bianchi, N., Gentile, C., and Mansour, Y. Nonstochastic bandits with composite anonymous feedback. In COLT, 2018. Cevher et al. (2023) Cevher, V., Piliouras, G., Sim, R., and Skoulakis, S. Min-max optimization made simple: Approximating the proximal point method via contraction maps. In SOSA, 2023. Chapelle (2014) Chapelle, O. Modeling delayed feedback in display advertising. In KDD, 2014. Daskalakis et al. (2018) Daskalakis, C., Ilyas, A., Syrgkanis, V., and Zeng, H. Training gans with optimism. In ICLR, 2018. Desautels et al. (2014) Desautels, T., Krause, A., and Burdick, J. W. Parallelizing exploration-exploitation tradeoffs in gaussian process bandit optimization. J. Mach. Learn. Res., 15(1):3873–3923, 2014. Feng et al. (2023) Feng, Y., Fu, H., Hu, Q., Li, P., Panageas, I., Wang, X., et al. On the last-iterate convergence in time-varying zero-sum games: Extra gradient succeeds where optimism fails. In NeurIPS, 2023. Feng et al. (2024) Feng, Y., Li, P., Panageas, I., and Wang, X. Last-iterate convergence separation between extra-gradient and optimism in constrained periodic games. In UAI, 2024. Fujimoto et al. (2025a) Fujimoto, Y., Abe, K., and Ariu, K. Learning from delayed feedback in games via extra prediction. In NeurIPS, 2025a. Fujimoto et al. (2025b) Fujimoto, Y., Ariu, K., and Abe, K. Synchronization in learning in periodic zero-sum games triggers divergence from nash equilibrium. In AAAI, 2025b. Hsieh et al. (2022) Hsieh, Y.-G., Iutzeler, F., Malick, J., and Mertikopoulos, P. Multi-agent online optimization with delays: Asynchronicity, adaptivity, and optimism. Journal of Machine Learning Research, 23(78):1–49, 2022. Joulani et al. (2013) Joulani, P., Gyorgy, A., and Szepesvári, C. Online learning under delayed feedback. In ICML, 2013. Joulani et al. (2016) Joulani, P., Gyorgy, A., and Szepesvári, C. Delay-tolerant online convex optimization: Unified analysis and adaptive-gradient algorithms. In AAAI, 2016. Li et al. (2019) Li, B., Chen, T., and Giannakis, G. B. Bandit online learning with unknown delays. In AISTATS, 2019. McMahan & Streeter (2014) McMahan, B. and Streeter, M. Delay-tolerant algorithms for asynchronous distributed online learning. In NeurIPS, 2014. Mertikopoulos et al. (2019) Mertikopoulos, P., Lecouat, B., Zenati, H., Foo, C.-S., Chandrasekhar, V., and Piliouras, G. Optimistic mirror descent in saddle-point problems: Going the extra (gradient) mile. In ICLR, 2019. Mokhtari et al. (2020) Mokhtari, A., Ozdaglar, A., and Pattathil, S. A unified analysis of extra-gradient and optimistic gradient methods for saddle point problems: Proximal point approach. In AISTATS, 2020. Neu et al. (2010) Neu, G., Antos, A., György, A., and Szepesvári, C. Online markov decision processes under bandit feedback. In NeurIPS, 2010. Pike-Burke et al. (2018) Pike-Burke, C., Agrawal, S., Szepesvari, C., and Grunewalder, S. Bandits with delayed, aggregated anonymous feedback. In ICML, 2018. Piliouras et al. (2022) Piliouras, G., Sim, R., and Skoulakis, S. Beyond time-average convergence: Near-optimal uncoupled online learning via clairvoyant multiplicative weights update. In NeurIPS, 2022. Quanrud & Khashabi (2015) Quanrud, K. and Khashabi, D. Online learning with adversarial delays. In NeurIPS, 2015. Rakhlin & Sridharan (2013) Rakhlin, S. and Sridharan, K. Optimization, learning, and games with predictable sequences. In NeurIPS, 2013. Shamir & Szlak (2017) Shamir, O. and Szlak, L. Online learning with local permutations and delayed feedback. In ICML, 2017. Syrgkanis et al. (2015) Syrgkanis, V., Agarwal, A., Luo, H., and Schapire, R. E. Fast convergence of regularized learning in games. In NeurIPS, 2015. Vernade et al. (2017) Vernade, C., Cappé, O., and Perchet, V. Stochastic bandit models for delayed conversions. In UAI, 2017. Wei et al. (2021) Wei, C.-Y., Lee, C.-W., Zhang, M., and Luo, H. Linear last-iterate convergence in constrained saddle-point optimization. In ICLR, 2021. Weinberger & Ordentlich (2002) Weinberger, M. J. and Ordentlich, E. On delayed prediction of individual sequences. IEEE Transactions on Information Theory, 48(7):1959–1976, 2002. Yasui et al. (2020) Yasui, S., Morishita, G., Komei, F., and Shibata, M. A feedback shift correction in predicting conversion rates under delayed feedback. In W, 2020. Yoshikawa & Imai (2018) Yoshikawa, Y. and Imai, Y. A nonparametric delayed feedback model for conversion rate prediction. arXiv preprint arXiv:1802.00255, 2018. Zheng et al. (2017) Zheng, S., Meng, Q., Wang, T., Chen, W., Yu, N., Ma, Z.-M., and Liu, T.-Y. Asynchronous stochastic gradient descent with delay compensation. In ICML, 2017. Zhou et al. (2017) Zhou, Z., Mertikopoulos, P., Bambos, N., Glynn, P. W., and Tomlin, C. Countering feedback delays in multi-agent learning. In NeurIPS, 2017. Zinkevich et al. (2009) Zinkevich, M., Langford, J., and Smola, A. Slow learners are fast. In NeurIPS, 2009. Appendix Appendix A Flowchart of the lemmas and theorems Figure A 1: Flowchart of the lemmas and theorems. In §5.1, Lemma 5.1 captures the dynamics of EPP, and 5.2 analyzes them. In §5.2, Lemma 5.3 captures the dynamics of the error between WOGDA and EPP, and Lemma 5.4 analyzes them. In §5.3, Theorem 5.5 analyzes WOGDA by combining the convergence term by EPP and the error term. It leads to Theorem 4.1, providing the rate of linear convergence by next-step prediction, and Theorem 4.2, providing the rate of linear convergence by extra prediction. Appendix B Proof of Lemma 5.1 Proof. The dynamics of EPP are rewritten as (−nη)t+1†=(−(n−1)η)t. ( I-nη A) z _t+1=( I-(n-1)η A) z_t. (A1) Since A is skew-symmetric matrix (T=− A^T=- A), +α I+α A has its inverse matrix for all α∈ℝα . Furthermore, for all α,α′∈ℝα,α , (+α)−1( I+α A)^-1 and (+α′)( I+α A) are commutative. Therefore, we obtain t+1†=(−nη)−1(−(n−1)η)t=(−(n−1)η)(−nη)−1t. z _t+1=( I-nη A)^-1( I-(n-1)η A) z_t=( I-(n-1)η A)( I-nη A)^-1 z_t. (A2) Since the inverse matrix of the denominator exists and it can be commutative with the numerator, it is acceptable to abuse the following notation. t+1†=−(n−1)η−nηt. z _t+1= I-(n-1)η A I-nη A z_t. (A3) Finally, we obtain ‖t+1†‖2 \| z _t+1\|^2 =atTT−(n−1)ηT−nηT−(n−1)η−nηt a= z_t^T I^T-(n-1)η A^T I^T-nη A^T I-(n-1)η A I-nη A z_t (A4) =btT+(n−1)η+nη−(n−1)η−nηt b= z_t^T I+(n-1)η A I+nη A I-(n-1)η A I-nη A z_t (A5) =tT−(n−1)2η22−n2η22t = z_t^T I-(n-1)^2η^2 A^2 I-n^2η^2 A^2 z_t (A6) =ctT+(n−1)2η2¯2+n2η2¯2t. c= z_t^T I+(n-1)^2η^2 A^2 I+n^2η^2 A^2 z_t. (A7) In (a), we used the transpose of Eq. (A3). In (b), we used T= I^T= I and T=− A^T=- A. In (c), we used 2=−¯2 A^2=- A^2. ∎ Appendix C Proof of Lemma 5.4 By substituting Eq. (8) recursively j∈ℕj times, we obtain Δt z_t =ηt−m+(n+m)ηΔt−m−1 =η A z_t-m+(n+m)η A z_t-m-1 (A8) =ηt−m+(n+m)η(ηt−2m−1+(n+m)ηΔt−2m−2) =η A z_t-m+(n+m)η A(η A z_t-2m-1+(n+m)η A z_t-2m-2) (A9) =⋯=∑k=1j(n+m)k−1ηkkt−k(m+1)+1+(n+m)jηjjΔt−j(m+1). =·s= _k=1^j(n+m)^k-1η^k A^k z_t-k(m+1)+1+(n+m)^jη^j A^j z_t-j(m+1). (A10) Also, Δ2t ^2 z_t is evaluated as Δ2t=a ^2 z_t a= ∑k=1j(n+m)k−1ηkkΔt−k(m+1)+1+(n+m)jηjjΔ2t−j(m+1) \ _k=1^j(n+m)^k-1η^k A^k z_t-k(m+1)+1+(n+m)^jη^j A^j ^2 z_t-j(m+1) (A11) =b b= ∑k=1j(n+m)k−1ηkk(∑l=1j(n+m)l−1ηllt−(k+l)(m+1)+2+(n+m)jηjjΔt−(k+j)(m+1)+1) \ _k=1^j(n+m)^k-1η^k A^k ( _l=1^j(n+m)^l-1η^l A^l z_t-(k+l)(m+1)+2+(n+m)^jη^j A^j z_t-(k+j)(m+1)+1 ) (A12) +(n+m)jηjj(∑k=1j(n+m)k−1ηkkΔt−(j+k)(m+1)+1+(n+m)jηjjΔ2t−2j(m+1)) +(n+m)^jη^j A^j ( _k=1^j(n+m)^k-1η^k A^k z_t-(j+k)(m+1)+1+(n+m)^jη^j A^j ^2 z_t-2j(m+1) ) (A13) = = ∑k=1j∑l=1j(n+m)k+l−2ηk+lk+lt−(k+l)(m+1)+2 \ _k=1^j _l=1^j(n+m)^k+l-2η^k+l A^k+l z_t-(k+l)(m+1)+2 (A14) +2∑k=1j(n+m)j+kηj+kj+kΔt−(j+k)(m+1)+1+(n+m)2jη2j2jΔ2t−2j(m+1). +2 _k=1^j(n+m)^j+kη^j+k A^j+k z_t-(j+k)(m+1)+1+(n+m)^2jη^2j A^2j ^2 z_t-2j(m+1). (A15) In (a) and (b), we applied Eq. (A10) repeatedly. Suppose sufficiently small step size η≤1/(2(n+m)λmax)η≤ 1/(2(n+m) _ ), then we obtain ‖Δ2t‖ \| ^2Z_t\| (A16) ≤a((n+m2)(m+1)∑k=1j∑l=1j(n+m)k+l−2ηk+lλmaxk+l+4(n+m)∑k=1j(n+m)j+k−1ηj+kλmaxj+k a≤ ( (n+ m2 )(m+1) _k=1^j _l=1^j(n+m)^k+l-2η^k+l _ ^k+l+4(n+m) _k=1^j(n+m)^j+k-1η^j+k _ ^j+k . +2(2n+m+1)(n+m)2jη2jλmax2j)max2m≤s≤2j(m+1)∥t−s∥ 17.07182pt .+2(2n+m+1)(n+m)^2jη^2j _ ^2j ) _2m≤ s≤ 2j(m+1)\| z_t-s\| (A17) =b((n+m2)(m+1)η2λmax2(1−(n+m)jηjλmaxj1−(n+m)ηλmax)2+4(n+m)(n+m)jηj+1λmaxj+11−(n+m)jηjλmaxj1−(n+m)ηλmax b= ( (n+ m2 )(m+1)η^2 _ ^2 ( 1-(n+m)^jη^j _ ^j1-(n+m)η _ )^2+4(n+m)(n+m)^jη^j+1 _ ^j+1 1-(n+m)^jη^j _ ^j1-(n+m)η _ . +2(2n+m+1)(n+m)2jη2jλmax2j)max2m≤s≤2j(m+1)∥t−s∥ 17.07182pt .+2(2n+m+1)(n+m)^2jη^2j _ ^2j ) _2m≤ s≤ 2j(m+1)\| z_t-s\| (A18) ≤c(2(2n+m)(m+1)η2λmax2+8(n+m)j+1ηj+1λmaxj+1+2(2n+m+1)(n+m)2jη2jλmax2j)max2m≤s≤2j(m+1)‖t−s‖. c≤ (2(2n+m)(m+1)η^2 _ ^2+8(n+m)^j+1η^j+1 _ ^j+1+2(2n+m+1)(n+m)^2jη^2j _ ^2j ) _2m≤ s≤ 2j(m+1)\| z_t-s\|. (A19) In (a), we upper-bounded A by λmax _ and also upper-bounded t z_t, Δt z_t, and Δ2t ^2 z_t in Δ2t ^2 Z_t as ‖n∑s=1m+1t−s+∑s=2m+1∑r=sm+1t−r‖ \|n _s=1^m+1 z_t-s+ _s=2^m+1 _r=s^m+1 z_t-r \| ≤n∑s=1m+1‖t−s‖+∑s=2m+1∑r=sm+1‖t−r‖ ≤ n _s=1^m+1\| z_t-s\|+ _s=2^m+1 _r=s^m+1\| z_t-r\| (A20) ≤(n+m2)(m+1)max1≤s≤m+1‖t−s‖, ≤ (n+ m2 )(m+1) _1≤ s≤ m+1\| z_t-s\|, (A21) ‖n∑s=1m+1Δt−s+∑s=2m+1∑r=sm+1Δt−r‖ \|n _s=1^m+1 z_t-s+ _s=2^m+1 _r=s^m+1 z_t-r \| =‖n(t−t−(m+1))+∑s=2m+1(t−s+1−t−(m+1))‖ = \|n( z_t- z_t-(m+1))+ _s=2^m+1( z_t-s+1- z_t-(m+1)) \| (A22) ≤n(‖t‖+‖t−(m+1)‖)+∑s=2m+1(‖t−s+1‖+‖t−(m+1)‖) ≤ n(\| z_t\|+\| z_t-(m+1)\|)+ _s=2^m+1(\| z_t-s+1\|+\| z_t-(m+1)\|) (A23) ≤2(n+m)max0≤s≤m+1‖t−s‖, ≤ 2(n+m) _0≤ s≤ m+1\| z_t-s\|, (A24) ‖n∑s=1m+1Δ2t−s+∑s=2m+1∑r=sm+1Δ2t−r‖ \|n _s=1^m+1 ^2 z_t-s+ _s=2^m+1 _r=s^m+1 ^2 z_t-r \| =‖n(t+1−t)+(t−t−m)−(n+m)(t−m−t−(m+1))‖ = \|n( z_t+1- z_t)+( z_t- z_t-m)-(n+m)( z_t-m- z_t-(m+1)) \| (A25) ≤n(‖t+1‖+‖t‖)+(‖t‖+‖t−m‖)+(n+m)(‖t−m‖+‖t−(m+1)‖) ≤ n(\| z_t+1\|+\| z_t\|)+(\| z_t\|+\| z_t-m\|)+(n+m)(\| z_t-m\|+\| z_t-(m+1)\|) (A26) ≤2(2n+m+1)max−1≤s≤m+1‖t−s‖. ≤ 2(2n+m+1) _-1≤ s≤ m+1\| z_t-s\|. (A27) In (b), we summed up the geometric series. In (c), we used η≤1/(2(n+m)λmax)η≤ 1/(2(n+m) _ ). Finally, by Lemma 5.3 ‖t+1†−t+1‖2 \| z _t+1- z_t+1\|^2 =Δ2tTη2¯2+n2η2¯2Δ2t = ^2 Z_t^T η^2 A^2 I+n^2η^2 A^2 ^2 Z_t (A28) ≤η2λmax21+n2η2λmax2‖Δ2t‖2 ≤ η^2 _ ^21+n^2η^2 _ ^2\| ^2 Z_t\|^2 (A29) ≤η2λmax2‖Δ2t‖2 ≤η^2 _ ^2\| ^2 Z_t\|^2 (A30) ≤ER(j,n)2‖Δ2t‖2. (j,n)^2\| ^2 Z_t\|^2. (A31) Appendix D Proof of Theorem 4.1 By substituting n=1n=1 and j=2j=2, we obtain linear convergence rate as LCRWOGDA(2,1)= _WOGDA(2,1)= 1−12η2λmin2+12η4λmin4+2(m+2)(m+1)η3λmax3 \ 1- 12η^2 _ ^2+ 12η^4 _ ^4+2(m+2)(m+1)η^3 _ ^3 (A32) +8(m+1)3η4λmax4+2(m+3)(m+1)4η5λmax5. +8(m+1)^3η^4 _ ^4+2(m+3)(m+1)^4η^5 _ ^5. (A33) For η=1/56(m+1)2κ2λmaxη=1/56(m+1)^2κ^2 _ , this convergence rate is upper-bounded as LCRWOGDA(2,1)= _WOGDA(2,1)= 1−12η2λmin2+12η4λmin4+2(m+2)(m+1)η3λmax3 \ 1- 12η^2 _ ^2+ 12η^4 _ ^4+2(m+2)(m+1)η^3 _ ^3 (A34) +8(m+1)3η4λmax4+2(m+3)(m+1)4η5λmax5 +8(m+1)^3η^4 _ ^4+2(m+3)(m+1)^4η^5 _ ^5 (A35) ≤ ≤ 1−12η2λmin2+15612η2λmin2+4η2λmin2+8η2λmin2+6η2λmin2 \ 1- 12η^2 _ ^2+ 156 \ 12η^2 _ ^2+4η^2 _ ^2+8η^2 _ ^2+6η^2 _ ^2 \ (A36) ≤ ≤ 1−16η2λmin2 \ 1- 16η^2 _ ^2 (A37) = = 1−16⋅562κ6(m+1)4. \ 1- 16· 56^2κ^6(m+1)^4. (A38) By the definition of Eq. (27), this immediately derives ‖t+1‖ \| z_t+1\| ≤(1−16⋅562κ6(m+1)4)max0≤s≤4(m+1)‖t−s‖ ≤ (1- 16· 56^2κ^6(m+1)^4 ) _0≤ s≤ 4(m+1)\| z_t-s\| (A39) ≤exp(−t6⋅562κ6(m+1)4)max0≤s≤4(m+1)‖t−s‖. ≤ (- t6· 56^2κ^6(m+1)^4 ) _0≤ s≤ 4(m+1)\| z_t-s\|. (A40) By applying this t times and defining ‖~0‖=max0≤s≤4(m+1)‖s‖\| z_0\|= _0≤ s≤ 4(m+1)\| z_s\|, we obtain ‖t‖ \| z_t\| ≤exp(−t6⋅562κ6(m+1)4×14(m+1))‖~0‖ ≤ (- t6· 56^2κ^6(m+1)^4× 14(m+1) )\| z_0\| (A41) =exp(−t4⋅6⋅562κ6(m+1)5)‖~0‖. = (- t4· 6· 56^2κ^6(m+1)^5 )\| z_0\|. (A42) This results in Eq. (9) with positive constant c=4⋅6⋅562c=4· 6· 56^2. Appendix E Proof of Theorem 4.2 By substituting n=m/2+1n=m/2+1, we obtain linear convergence rate as LCRWOGDA(j,m2+1)= _WOGDA(j, m2+1)= 1−12(m+1)η2λmin2+12(m2+1)2(m+1)η4λmin4 \ 1- 12(m+1)η^2 _ ^2+ 12 ( m2+1 )^2(m+1)η^4 _ ^4 (A43) +4(m+1)2η3λmax3+8(3m2+1)j+1ηj+2λmaxj+2+2(m2+3)(3m2+1)2jη2j+1λmax2j+1. +4(m+1)^2η^3 _ ^3+8 ( 3m2+1 )^j+1η^j+2 _ ^j+2+2 ( m2+3 ) ( 3m2+1 )^2jη^2j+1 _ ^2j+1. (A44) For η=1/(93(m+1)2j2j−1κ2λmax)η=1/(93(m+1) 2j2j-1κ^2 _ ), this convergence rate is upper-bounded as LCRWOGDA(j,m2+1)= _WOGDA(j, m2+1)= 1−12(m+1)η2λmin2+12(m2+1)2(m+1)η4λmin4+4(m+1)2η3λmax3 \ 1- 12(m+1)η^2 _ ^2+ 12 ( m2+1 )^2(m+1)η^4 _ ^4+4(m+1)^2η^3 _ ^3 (A45) +8(3m2+1)j+1ηj+2λmaxj+2+2(2m+3)(3m2+1)2jη2j+1λmax2j+1 +8 ( 3m2+1 )^j+1η^j+2 _ ^j+2+2 (2m+3 ) ( 3m2+1 )^2jη^2j+1 _ ^2j+1 (A46) ≤ ≤ 1−12(m+1)η2λmin2+16212(m+1)η2λmin2+4(m+1)η2λmin2 \ 1- 12(m+1)η^2 _ ^2+ 162 \ 12(m+1)η^2 _ ^2+4(m+1)η^2 _ ^2 (A47) +8(3m2+1)η2λmin2+2(2m+3)η2λmin2 +8 ( 3m2+1 )η^2 _ ^2+2 (2m+3 )η^2 _ ^2 \ (A48) ≤ ≤ 1−16(m+1)η2λmin2 \ 1- 16(m+1)η^2 _ ^2 (A49) = = 1−16⋅932κ6(m+1)1+22j−1. \ 1- 16· 93^2κ^6(m+1)^1+ 22j-1. (A50) By substituting j=⌊log(m+1)⌋+2j= (m+1) +2, we obtain LCRWOGDA(⌊log(m+1)⌋+2,m2+1) _WOGDA( (m+1) +2, m2+1) ≤1−16⋅932κ6(m+1)1+22⌊log(m+1)⌋+3 ≤ 1- 16· 93^2κ^6(m+1)^1+ 22 (m+1) +3 (A51) ≤1−16⋅932κ6(m+1)1+1log(m+1) ≤ 1- 16· 93^2κ^6(m+1)^1+ 1 (m+1) (A52) =1−16⋅932eκ6(m+1). =1- 16· 93^2eκ^6(m+1). (A53) By the definition of Eq. (27), this immediately derives ‖t+1‖≤(1−16⋅932eκ6(m+1))max0≤s≤2(⌊log(m+1)⌋+2)(m+1)‖t−s‖. \| z_t+1\|≤ (1- 16· 93^2eκ^6(m+1) ) _0≤ s≤ 2( (m+1) +2)(m+1)\| z_t-s\|. (A54) By applying this t times and defining ‖~0‖=max0≤s≤2(m+1)(log(m+1)+2)‖s‖\| z_0\|= _0≤ s≤ 2(m+1)( (m+1)+2)\| z_s\|, we obtain ‖t‖ \| z_t\| ≤exp(−t6⋅932eκ6(m+1)×12(⌊log(m+1)⌋+2)(m+1))‖~0‖ ≤ (- t6· 93^2eκ^6(m+1)× 12( (m+1) +2)(m+1) )\| z_0\| (A55) ≤exp(−t6⋅932eκ6(m+1)×12(log(m+1)+2)(m+1))‖~0‖ ≤ (- t6· 93^2eκ^6(m+1)× 12( (m+1)+2)(m+1) )\| z_0\| (A56) ≤exp(−t2⋅6⋅932eκ6(m+1)2(log(m+1)+2))‖~0‖. ≤ (- t2· 6· 93^2eκ^6(m+1)^2( (m+1)+2) )\| z_0\|. (A57) This results in Eq. (11) with positive constant c=2⋅6⋅932ec=2· 6· 93^2e.