Robust accelerated primal-dual methods for computing saddle points

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

doi:10.1137/21M1462775

Journal article, 2024

Robust accelerated primal-dual methods for computing saddle points

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

SIAM Journal on Optimization, 34(1), pp. 1097–1130, 2024.

Publisher (DOI)

In brief

Accelerated primal–dual methods solve saddle-point problems quickly but, like momentum methods, amplify gradient errors. For strongly convex–strongly concave problems the paper quantifies that amplification as a robustness measure, computes it for the accelerated primal–dual family, and shows how to choose parameters on the speed–robustness frontier — the saddle-point counterpart of the trade-off for momentum methods.

Go further

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.

Topics

Minimax & primal–dual Risk & robustness Momentum & acceleration

Cite

@article{zhang2024rapd,
  title   = {Robust accelerated primal-dual methods for computing saddle points},
  author  = {Xuan Zhang and Necdet Serhat Aybat and Mert Gürbüzbalaban},
  year    = {2024},
  journal = {SIAM Journal on Optimization},
  volume  = {34(1)},
  pages   = {1097--1130},
  doi     = {10.1137/21M1462775},
}