{
  "id": "2403.07806",
  "version": "v1",
  "published": "2024-03-12T16:43:55.000Z",
  "updated": "2024-03-12T16:43:55.000Z",
  "title": "A Stochastic GDA Method With Backtracking For Solving Nonconvex (Strongly) Concave Minimax Problems",
  "authors": [
    "Qiushui Xu",
    "Xuan Zhang",
    "Necdet Serhat Aybat",
    "Mert Gürbüzbalaban"
  ],
  "categories": [
    "math.OC"
  ],
  "abstract": "We propose a stochastic GDA (gradient descent ascent) method with backtracking (SGDA-B) to solve nonconvex-(strongly) concave (NCC) minimax problems $\\min_x \\max_y \\sum_{i=1}^N g_i(x_i)+f(x,y)-h(y)$, where $h$ and $g_i$ for $i = 1, \\ldots, N$ are closed, convex functions, $f$ is $L$-smooth and $\\mu$-strongly concave in $y$ for some $\\mu\\geq 0$. We consider two scenarios: (i) the deterministic setting where we assume one can compute $\\nabla f$ exactly, and (ii) the stochastic setting where we have only access to $\\nabla 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 $\\epsilon$-stationary point within $\\mathcal{O}(L\\kappa^2/\\epsilon^2)$ and $\\mathcal{O}(L^3/\\epsilon^4)$ gradient calls when $\\mu>0$ and $\\mu=0$, respectively, where $\\kappa=L/\\mu$. In the stochastic setting, for any $p \\in (0, 1)$ and $\\epsilon >0$, it can compute an $\\epsilon$-stationary point with high probability, which requires $\\mathcal{O}(L\\kappa^3\\epsilon^{-4}\\log(1/p))$ and $\\tilde{\\mathcal{O}}(L^4\\epsilon^{-7}\\log(1/p))$ stochastic oracle calls, with probability at least $1-p$, when $\\mu>0$ and $\\mu=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.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2024-03-12T16:43:55.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "stochastic gda method",
      "concave minimax problems",
      "solving nonconvex",
      "robust learning problem illustrating",
      "backtracking"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}