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

Authors Xuan Zhang, N. S. Aybat, Mert Gürbüzbalaban

Publication date 30 May 2022

Abstract: We propose a new stochastic method SAPD+ for solving nonconvex-concave minimax problems of the form

m i n m a x m a t h c a l L (x, y) = f (x) + P h i (x, y) - g (y)

, where

f, g

are closed convex and

P h i (x, y)

is a smooth function that is weakly convex in

x

, (strongly) concave in

y

. For both strongly concave and merely concave settings, SAPD+ achieves the best known oracle complexities of

m a t h c a l O (L k a p p a_{y} e p s i l o n^{- 4})

and

m a t h c a l O (L^{3} e p s i l o n^{- 6})

, respectively, without assuming compactness of the problem domain, where

k a p p a_{y}

is the condition number and

L

is the Lipschitz constant. We also propose SAPD+ with variance reduction, which enjoys the best known oracle complexity of

m a t h c a l O (L k a p p a_{y}^{2} e p s i l o n^{- 3})

for weakly convex-strongly concave setting. We demonstrate the efficiency of SAPD+ on a distributionally robust learning problem with a weakly convex cost and also on a multi-class classification problem in deep learning.

This page was built for publication: SAPD+: An Accelerated Stochastic Method for Nonconvex-Concave Minimax Problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6400555)