Key points are not available for this paper at this time.
We propose a stochastic GDA (gradient descent ascent) method with backtracking (SGDA-B) to solve nonconvex- (strongly) concave (NCC) minimax problems ₓ ᵧ ₈=₁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³^-4 (1/p) ) and O (L⁴^-7 (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.
Xu et al. (Tue,) studied this question.