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

We propose a stochastic GDA (gradient descent ascent) method with backtracking (SGDA-B) to solve nonconvex-(strongly) concave (NCC) minimax problems minₓ maxy ∑ᵢ₌₁N gᵢ(xᵢ)+f(x,y)-h(y), where h and gᵢ for i = 1, …, N are closed, convex functions, f is L-smooth and μ-strongly concave in y for some μ≥ 0. We consider two scenarios: (i) the deterministic setting where we assume one can compute ∇ f exactly, and (ii) the stochastic setting where we have only access to ∇ f through an unbiased stochastic oracle with a finite variance. While most of the existing methods assume knowledge of the Lipschitz constant L, SGDA-B is agnostic to L. Moreover, SGDA-B can support random block-coordinate updates. In the deterministic setting, SGDA-B can compute an ε-stationary point within O(Lκ²/ε²) and O(L³/ε⁴) gradient calls when μ>0 and μ=0, respectively, where κ=L/μ. In the stochastic setting, for any p ∈ (0, 1) and ε >0, it can compute an ε-stationary point with high probability, which requires O(Lκ³ε⁻⁴log(1/p)) and Õ(L⁴ε⁻⁷log(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. 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.