Near Optimal Stochastic Algorithms for Finite-Sum Unbalanced Convex-Concave Minimax Optimization

Abstract

This paper considers stochastic first-order algorithms for convex-concave minimax problems of the form ${\min }_{\mathbf{x}}{\max }_{\mathbf{y}}f(\mathbf{x},\mathbf{y})$, where $f$ can be presented by the average of $n$ individual components which are $L$-average smooth. For ${\mu }_x$-strongly-convex-${\mu }_y$-strongly-concave setting, we propose a new method which could find a $\epsilon$-saddle point of the problem in $\tilde{\mathcal{O}}(\sqrt{n(\sqrt{n}+{\kappa }_x)(\sqrt{n}+{\kappa }_y)}\log (1/\epsilon ))$ stochastic first-order complexity, where ${\kappa }_x\triangleq L/{\mu }_x$ and ${\kappa }_y\triangleq L/{\mu }_y$. This upper bound is near optimal with respect to $\epsilon$, $n$, ${\kappa }_x$ and ${\kappa }_y$ simultaneously. In addition, the algorithm is easily implemented and works well in practical. Our methods can be extended to solve more general unbalanced convex-concave minimax problems and the corresponding upper complexity bounds are also near optimal.

References in corpus (7)

• Efficient Algorithms for Smooth Minimax Optimization
• Stochastic Variance Reduction for Variational Inequality Methods
• Improved Algorithms for Convex-Concave Minimax Optimization
• Communication-Efficient Distributed Stochastic AUC Maximization with Deep Neural Networks
• Lower Complexity Bounds of Finite-Sum Optimization Problems: The Results and Construction
• Lower Bounds for Smooth Nonconvex Finite-Sum Optimization
• DIPPA: An improved Method for Bilinear Saddle Point Problems

Cited by in corpus (1)

• Smooth Monotone Stochastic Variational Inequalities and Saddle Point Problems: A Survey