Search papers, labs, and topics across Lattice.
This paper analyzes the convergence rate of Weighted Optimistic Gradient Descent-Ascent (WOGDA) in unconstrained bilinear games with delayed feedback. It demonstrates that WOGDA, interpreted as an approximation of the Extra Proximal Point (EPP) method, achieves linear convergence to the equilibrium. The key result is that employing "extra optimism" (predicting farther future rewards) significantly accelerates the convergence rate compared to standard optimism, achieving a rate of $\exp(-Θ(t/(m^{2}\log m)))$ for delay $m$.
Counterintuitively, predicting *farther* into the future can dramatically accelerate convergence in multi-agent learning with delayed feedback, achieving exponential speedups.
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(-Θ(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/(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.
