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 (18)

• SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator
• On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems
• A Variational Inequality Perspective on Generative Adversarial Networks
• A Unified Analysis of Extra-gradient and Optimistic Gradient Methods for Saddle Point Problems: Proximal Point Approach
• Multi-Agent Reinforcement Learning via Double Averaging Primal-Dual Optimization
• Reducing Noise in GAN Training with Variance Reduced Extragradient
• Stochastic Recursive Gradient Descent Ascent for Stochastic Nonconvex-Strongly-Concave Minimax Problems
• Stochastic AUC Maximization with Deep Neural Networks
• Efficient Algorithms for Smooth Minimax Optimization
• Linear Lower Bounds and Conditioning of Differentiable Games
• Stochastic Variance Reduction for Variational Inequality Methods
• Communication-Efficient Distributed Stochastic AUC Maximization with Deep Neural Networks
• Improved Algorithms for Convex-Concave Minimax Optimization
• Lower Complexity Bounds of Finite-Sum Optimization Problems: The Results and Construction
• A Stochastic Proximal Point Algorithm for Saddle-Point Problems
• Lower Bounds for Smooth Nonconvex Finite-Sum Optimization
• Towards More Efficient Stochastic Decentralized Learning: Faster Convergence and Sparse Communication
• 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