We propose a new stochastic method SAPD+ for solving nonconvex-concave minimax problems of the form $\min\max\mathcal{ L}(x,y)=f(x)+\Phi(x,y)-g(y)$, where $f,g$ are closed convex and $\Phi(x,y)$ is a smooth function that is weakly convex in $x$, (strongly) concave in $y$. Let $\delta^2$ denote the variance bound for the unbiased stochastic oracle used within SAPD+ to estimate $\nabla\Phi$. When $\delta>0$, for both strongly concave and merely concave settings, SAPD+ achieves the best known oracle complexities: $\mathcal{ O}\Big(\kappa_y\max\Big\{ 1,\frac{ \delta^2}{ \epsilon^2}\Big\}\frac{ L\mathcal{ G}_0}{ \epsilon^{ 2}}\Big)$ for the strongly concave case without assuming compactness of the problem domain, and $\mathcal{ O}\Big(\frac{ L^3\mathcal{ D}_y^2\mathcal{ G}_0}{ \epsilon^{ 4}}\Big(1+\frac{ \delta^2}{ \epsilon^2}\Big)\Big)$ for the merely concave case, where $\kappa_y\geq 1$ is the condition number, $L$ is the Lipschitz constant of $\nabla \Phi$, $\mathcal{ G}_0$ is the primal-dual gap of the initial point, and $\mathcal{ D}_y=\sup\{ \|y\|:\ y\in\mathbf{ dom} g\}$. We also propose SAPD+ with variance reduction, which enjoys $\mathcal{ O}\Big(\max\Big\{ \kappa_y,\sqrt{ \frac{ \delta}{ \epsilon}}\Big\}\cdot (1+\kappa_y\frac{ \delta}{ \epsilon})\frac{ L\mathcal{ G}_0}{ \epsilon^2}\Big)$ oracle complexity for weakly convex-strongly concave setting --this is the best known upper complexity bound in the literature for this setting and our paper establishes it for the first time. We demonstrate the efficiency of SAPD+ on a distributionally robust learning problem with a nonconvex regularizer and also on a multi-class classification problem in deep learning.
Categories: math.OC