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.
Code (1)
Tasks
Image GenerationSimilar Papers 제목 키워드 기반
Near-optimal Local Convergence of Alternating Gradient Descent-Ascent for Minimax Optimization
Smooth minimax games often proceed by simultaneous or alternating gradient updates. Although algorithms with alternating updates are commonly used in practice, the majority of existing theoretical analyses focus on simul…
Accelerated Proximal Alternating Gradient-Descent-Ascent for Nonconvex Minimax Machine Learning
Alternating gradient-descent-ascent (AltGDA) is an optimization algorithm that has been widely used for model training in various machine learning applications, which aims to solve a nonconvex minimax optimization proble…
BIG-bench Machine LearningIterative Minimax Games with Coupled Linear Constraints
The study of nonconvex minimax games has gained significant momentum in machine learning and decision science communities due to their fundamental connections to adversarial training scenarios. This work develops a prima…
FedNest: Federated Bilevel, Minimax, and Compositional Optimization
Standard federated optimization methods successfully apply to stochastic problems with single-level structure. However, many contemporary ML problems -- including adversarial robustness, hyperparameter tuning, and actor-…
Adversarial RobustnessHyperparameter OptimizationRepresentation LearningNeural Network Training via Stochastic Alternating Minimization with Trainable Step Sizes
The training of deep neural networks is inherently a nonconvex optimization problem, yet standard approaches such as stochastic gradient descent (SGD) require simultaneous updates to all parameters, often leading to unst…