Fundamental Benefit of Alternating Updates in Minimax Optimization

arXiv:2402.10475v1 Announce Type: cross
Abstract: The Gradient Descent-Ascent (GDA) algorithm, designed to solve minimax optimization problems, takes the descent and ascent steps either simultaneously (Sim-GDA) or alternately (Alt-GDA). While Alt-GDA is commonly observed to converge faster, the performance gap between the two is not yet well understood theoretically, especially in terms of global convergence rates. To address this theory-practice gap, we present fine-grained convergence analyses of both algorithms for strongly-convex-strongly-concave and Lipschitz-gradient objectives. Our new iteration complexity upper bound of …

abstract algorithm arxiv benefit converge cs.lg faster gap gda gradient math.oc minimax optimization performance sim solve terms type updates