On the $O(1/T)$ Convergence of Alternating Gradient Descent–Ascent in Bilinear Games

Core task: convergence analysis of alternating gradient descent-ascent in bilinear games. The field organizes around several complementary perspectives on minimax optimization. Alternating update schemes form a central branch, examining how players take turns updating their strategies and the resulting convergence guarantees in bilinear and broader game settings. Simultaneous and optimistic gradient methods explore synchronous updates and lookahead mechanisms that can stabilize dynamics. Nonconvex-nonconcave minimax optimization tackles settings beyond the classical convex-concave regime, while Markov games and sequential decision settings extend the analysis to multi-agent reinforcement learning. Specialized algorithmic variants introduce momentum, variance reduction, and acceleration techniques, and theoretical frameworks develop tools such as performance estimation problems and co-coercivity conditions. Application-driven branches address constrained optimization and robust formulations that arise in practice. Within alternating update schemes, a particularly active line of work investigates convergence rates in bilinear settings, where the minimax objective decomposes into a simple bilinear form. Alternating GDA Bilinear[0] contributes to this cluster by analyzing how alternating updates behave in such structured games, complementing earlier studies like Local Alternating GDA[3] that examined local convergence properties and Alternating Updates Benefit[4] that highlighted advantages of the alternating schedule. These works contrast with optimistic methods such as Optimistic GDA Bilinear[7] and extragradient approaches like Unified Extragradient Analysis[5], which use lookahead or correction steps to achieve faster or more stable convergence. A recurring theme across these branches is the trade-off between algorithmic simplicity and convergence speed: alternating schemes are often straightforward to implement but may exhibit oscillatory behavior, whereas optimistic and simultaneous methods can offer improved rates at the cost of additional gradient evaluations or memory.