A stochastic GDA method with backtracking for solving nonconvex (strongly) concave minimax problems

Qiushui Xu; Xuan Zhang; Necdet Serhat Aybat; Mert Gürbüzbalaban

Publications · Preprint · arXiv 2024

A stochastic GDA method with backtracking for solving nonconvex (strongly) concave minimax problems

Qiushui Xu, Xuan Zhang, Necdet Serhat Aybat, Mert Gürbüzbalaban

arXiv preprint, 2024.

arXiv:2403.07806

In brief

Gradient descent-ascent for minimax problems that are non-convex in the minimizing variable and concave or strongly concave in the maximizing one, with stochastic gradients and a backtracking rule that adapts the stepsizes to the local smoothness instead of requiring it to be known; the paper establishes oracle-complexity guarantees for the resulting method.

Topics

Minimax & primal–dual

Cite

@misc{xu2024gda,
  title   = {A stochastic GDA method with backtracking for solving nonconvex (strongly) concave minimax problems},
  author  = {Qiushui Xu and Xuan Zhang and Necdet Serhat Aybat and Mert Gürbüzbalaban},
  year    = {2024},
  howpublished = {arXiv preprint arXiv:2403.07806},
}

Relatedsame topics

An accelerated primal–dual algorithm with backtracking for decentralized constrained optimization (J. Nonlinear Var. Anal., 2026)
High probability and risk-averse guarantees for a stochastic accelerated primal-dual method (J. Mach. Learn. Res., 2024)
High-probability complexity bounds for stochastic non-convex minimax optimization (NeurIPS, 2024)
Robust accelerated primal-dual methods for computing saddle points (SIAM J. Optim., 2024)
A variance-reduced stochastic accelerated primal–dual algorithm (arXiv, 2023)

← All publications · Research program · Mert Gürbüzbalaban