Conference paper, 2022
SAPD+: an accelerated stochastic method for nonconvex-concave minimax problems
Advances in Neural Information Processing Systems (NeurIPS), 2022.
Extends the stochastic accelerated primal–dual method beyond the convex–concave case. SAPD+ wraps SAPD inside an inexact proximal-point scheme for weakly-convex–strongly-concave and weakly-convex–merely-concave minimax problems, with oracle-complexity bounds that match or improve the best known ones and a variance-reduced variant; the method handles the non-convex minimax problems that arise in robust and adversarial learning. Recent work showed that SAPD+ is an optimal method: its dependence on the condition number cannot be improved in the stochastic nonconvex–strongly-concave setting.
The playground Three ways to reach a saddle point lets you try the ideas of this paper in the browser.
The research note Three ways to reach a saddle point explains the paper informally.
@inproceedings{zhang2022sapdplus,
title = {SAPD+: an accelerated stochastic method for nonconvex-concave minimax problems},
author = {Xuan Zhang and Necdet Serhat Aybat and Mert Gürbüzbalaban},
year = {2022},
booktitle = {Advances in Neural Information Processing Systems (NeurIPS)},
url = {http://papers.nips.cc/paper_files/paper/2022/hash/880d8999c07a8efc9bbbeb0c38f50765-Abstract-Conference.html},
}Return to all publications, the research program, or the home page.