Min-Max Optimization under Delays
Authors:
- Arman AdibiAAArman Adibi
- Aritra MitraAMAritra Mitra
- Hamed HassaniHHHamed Hassani
Preprint
Abstract
Delays and asynchrony are inevitable in large-scale machine-learning problems where communication plays a key role. As such, several works have extensively analyzed stochastic optimization with delayed gradients. However, as far as we are aware, no analogous theory is available for min-max optimization, a topic that has gained recent popularity due to applications in adversarial robustness, game theory, and reinforcement learning. Motivated by this gap, we examine the performance of standard min-max optimization algorithms with delayed gradient updates. First, we show (empirically) that even small delays can cause prominent algorithms like Extra-gradient (\texttt{EG}) to diverge on simple instances for which \texttt{EG} guarantees convergence in the absence of delays. Our empirical study thus suggests the need for a careful analysis of delayed versions of min-max optimization algorithms. Accordingly, under suitable technical assumptions, we prove that Gradient Descent-Ascent (\texttt{GDA}) and \texttt{EG} with delayed updates continue to guarantee convergence to saddle points for convex-concave and strongly convex-strongly concave settings. Our complexity bounds reveal, in a transparent manner, the slow-down in convergence caused by delays.Keywords
All Related Versions
This publication has 5 references indexed in Scilit:
- Convergence Rate of $\mathcal{O}(1/k)$ for Optimistic Gradient and Extragradient Methods in Smooth Convex-Concave Saddle Point ProblemsSIAM Journal on Optimization, 2020
- On the Convergence Rate of Distributed Gradient Methods for Finite-Sum Optimization under Communication DelaysProceedings of the ACM on Measurement and Analysis of Computing Systems, 2017
- On the Convergence Rate of Incremental Aggregated Gradient AlgorithmsSIAM Journal on Optimization, 2017
- Subgradient Methods for Saddle-Point ProblemsJournal of Optimization Theory and Applications, 2009
- Prox-Method with Rate of Convergence O(1/t) for Variational Inequalities with Lipschitz Continuous Monotone Operators and Smooth Convex-Concave Saddle Point ProblemsSIAM Journal on Optimization, 2004