摘要

梯度下降-上升算法（Gradient Descent-Ascent, GDA）旨在求解极小极大优化问题，其迭代过程可采用同步方式（Sim-GDA）或交替方式（Alt-GDA）执行下降与上升步骤。尽管在实践中观察到Alt-GDA通常具有更快的收敛速度，但二者在全局收敛速率方面的理论性能差距尚未得到充分理解。为弥合这一理论与实践之间的鸿沟，本文对强凸-强凹以及梯度利普希茨连续的目标函数，分别给出了Sim-GDA与Alt-GDA的精细化收敛性分析。我们提出的Alt-GDA的新迭代复杂度上界严格小于Sim-GDA的下界，从而首次从理论上证明了Alt-GDA具有更快的收敛速度。此外，本文提出一种通用算法框架——交替外推梯度下降-上升算法（Alternating-Extrapolation GDA, Alex-GDA），该框架统一了Sim-GDA与Alt-GDA。其核心思想是：在迭代过程中，交替地基于迭代点的外推值计算梯度。我们证明，Alex-GDA具有更优的迭代复杂度上界，该上界与外梯度法（Extra-gradient method）一致，同时所需梯度计算次数更少。进一步地，我们证明在双线性问题下，Alex-GDA可实现线性收敛，而Sim-GDA与Alt-GDA均无法收敛，从而凸显了Alex-GDA在结构化问题中的优越性。