Near Optimal Stochastic Algorithms for Finite-Sum Unbalanced Convex-Concave Minimax Optimization
This work addresses efficient optimization for unbalanced minimax problems in machine learning, offering a near-optimal algorithm that is incremental in improving complexity bounds for a specific setting.
The paper tackles stochastic convex-concave minimax optimization problems with finite-sum structure, proposing a new algorithm that achieves a near-optimal stochastic first-order complexity of ̃O(√n(√n+κ_x)(√n+κ_y) log(1/ε)) for finding an ε-saddle point, with concrete bounds depending on problem parameters like n, κ_x, and κ_y.
This paper considers stochastic first-order algorithms for convex-concave minimax problems of the form $\min_{\bf x}\max_{\bf y}f(\bf x, \bf y)$, where $f$ can be presented by the average of $n$ individual components which are $L$-average smooth. For $μ_x$-strongly-convex-$μ_y$-strongly-concave setting, we propose a new method which could find a $\varepsilon$-saddle point of the problem in $\tilde{\mathcal O} \big(\sqrt{n(\sqrt{n}+κ_x)(\sqrt{n}+κ_y)}\log(1/\varepsilon)\big)$ stochastic first-order complexity, where $κ_x\triangleq L/μ_x$ and $κ_y\triangleq L/μ_y$. This upper bound is near optimal with respect to $\varepsilon$, $n$, $κ_x$ and $κ_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.