A Stochastic GDA Method With Backtracking For Solving Nonconvex Concave Minimax Problems

We propose a stochastic GDA (gradient descent ascent) method with backtracking (SGDA-B) to solve nonconvex-concave (NCC) minimax problems of the form: minx maxy sumi=1N gi(xi)+f(x,y)-h(y), where h and gi for i=1,cdots,N are closed, convex functions, and for some L,μ≥ 0, f is L-smooth and f(x,·) is μ-strongly concave for all x in the problem domain. We consider the stochastic setting where one only has an access to an unbiased stochastic oracle of nabla f with a finite variance bound σ2. While most of the existing methods assume knowledge of L, μ and/or σ2, SGDA-B is agnostic to all of these problem parameters. Moreover, SGDA-B can support random block-coordinate updates. In the deterministic setting, i.e., σ2=0 and one can compute nabla f exactly, SGDA-B can compute an ε-stationary point within O(Lkappa2/ε2) and O(L3/ε4) gradient calls when μ>0 and μ=0, respectively, where kappatriangleq L/μ. In the stochastic setting, i.e., σ2>0, for any p∈(0,1) and ε>0, it can compute an ε-stationary point with high probability, which requires O(L kappa3 ε-4 log2(1/p)) and tildeO(L4ε-7log2(1/p)) stochastic oracle calls, with probability at least 1-p, when μ>0 and μ=0, respectively. To our knowledge, SGDA-B is the first GDA-type method with backtracking to solve NCC minimax problems and achieves the best complexity among the methods that are agnostic to L, μ and σ2. We also provide numerical results for SGDA-B on a distributionally robust learning problem illustrating the potential performance gains that can be achieved by SGDA-B.