Improved Algorithms for Convex-Concave Minimax Optimization

Abstract

This paper studies minimax optimization problems ${\min }_x{\max }_{y}f(x,y)$, where $f(x,y)$ is $m_x$-strongly convex with respect to $x$, $m_y$-strongly concave with respect to $y$ and $(L_x,L_{xy},L_y)$-smooth. Zhang et al. provided the following lower bound of the gradient complexity for any first-order method: $\Omega (\sqrt{\frac{L_x}{m_x}+\frac{L_{xy}^2}{m_x{m}_y}+\frac{L_y}{m_y}}\ln (1/\epsilon )).$ This paper proposes a new algorithm with gradient complexity upper bound $\tilde{O}\left(\sqrt{\frac{L_x}{m_x}+\frac{L\cdot L_{xy}}{m_x{m}_y}+\frac{L_y}{m_y}}\ln \left(1/\epsilon \right)\right),$ where $L=\max \{L_x,L_{xy},L_y\}$. This improves over the best known upper bound $\tilde{O}\left(\sqrt{\frac{L^2}{m_x{m}_y}}{\ln }^3\left(1/\epsilon \right)\right)$ by Lin et al. Our bound achieves linear convergence rate and tighter dependency on condition numbers, especially when $L_{xy}\ll L$ (i.e., when the interaction between $x$ and $y$ is weak). Via reduction, our new bound also implies improved bounds for strongly convex-concave and convex-concave minimax optimization problems. When $f$ is quadratic, we can further improve the upper bound, which matches the lower bound up to a small sub-polynomial factor.

References in corpus (13)

• Certifying Some Distributional Robustness with Principled Adversarial Training
• On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems
• The Numerics of GANs
• A Variational Inequality Perspective on Generative Adversarial Networks
• Solving a Class of Non-Convex Min-Max Games Using Iterative First Order Methods
• SBEED: Convergent Reinforcement Learning with Nonlinear Function Approximation
• Online Learning with Predictable Sequences
• Hybrid Block Successive Approximation for One-Sided Non-Convex Min-Max Problems: Algorithms and Applications
• DualDICE: Behavior-Agnostic Estimation of Discounted Stationary Distribution Corrections
• Stochastic Variance Reduction Methods for Policy Evaluation
• Last-iterate convergence rates for min-max optimization
• Efficient Algorithms for Smooth Minimax Optimization
• Variance Reduction for Matrix Games

Cited by in corpus (9)

• On the Suboptimality of Negative Momentum for Minimax Optimization
• Nonconvex-Nonconcave Min-Max Optimization with a Small Maximization Domain
• Near Optimal Stochastic Algorithms for Finite-Sum Unbalanced Convex-Concave Minimax Optimization
• Solving strongly convex-concave composite saddle point problems with a small dimension of one of the variables
• Convex optimization
• Primal-Dual First-Order Methods for Affinely Constrained Multi-Block Saddle Point Problems
• On solving convex min-min problems with smoothness and strong convexity in one variable group and small dimension of the other
• MIMO Radar Waveform-Filter Design for Extended Target Detection from a View of Games
• Robust MIMO Radar Waveform-Filter Design for Extended Target Detection in the Presence of Multipath