Fundamental Benefit of Alternating Updates in Minimax Optimization
<|reference_start|>Fundamental Benefit of Alternating Updates in Minimax Optimization: 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 Alt-GDA is strictly smaller than the lower bound of Sim-GDA; i.e., Alt-GDA is provably faster. Moreover, we propose Alternating-Extrapolation GDA (Alex-GDA), a general algorithmic framework that subsumes Sim-GDA and Alt-GDA, for which the main idea is to alternately take gradients from extrapolations of the iterates. We show that Alex-GDA satisfies a smaller iteration complexity bound, identical to that of the Extra-gradient method, while requiring less gradient computations. We also prove that Alex-GDA enjoys linear convergence for bilinear problems, for which both Sim-GDA and Alt-GDA fail to converge at all.<|reference_end|>
@article{lee2024fundamental,
    title={Fundamental Benefit of Alternating Updates in Minimax Optimization},
    author={Jaewook Lee, Hanseul Cho, Chulhee Yun},
    journal={arXiv preprint arXiv:2402.10475},
    year={2024},
    archivePrefix={arXiv},
    eprint={2402.10475},
    primaryClass={math.OC cs.LG}
}