SAPD+: An Accelerated Stochastic Method for Nonconvex-Concave Minimax Problems

We propose a new stochastic method SAPD+ for solving nonconvex-concave minimax problems of the form minmaxL(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 δ2 denote the variance bound for the unbiased stochastic oracle used within SAPD+ to estimate nablaPhi. When δ>0, for both strongly concave and merely concave settings, SAPD+ achieves the best known oracle complexities: OBig(kappaymaxBig1,fracδ2ε2BigfracLG0ε2Big) for the strongly concave case without assuming compactness of the problem domain, and OBig(fracL3Dy2G0ε4Big(1+fracδ2ε2Big)Big) for the merely concave case, where kappay≥ 1 is the condition number, L is the Lipschitz constant of nabla Phi, G0 is the primal-dual gap of the initial point, and Dy=sup|y|: y∈dom g. We also propose SAPD+ with variance reduction, which enjoys OBig(maxBigkappay,√fracδεBig· (1+kappayfracδε)fracLG0ε2Big) 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.