Generalized Optimistic Methods for Convex-Concave Saddle Point Problems
SIAM Journal on Optimization · 30.09.2025 · 35 (3) · 2066-2097
DOI: 10.1137/24m1630475 ↗Kurz gefasst
Fachartikel in der Zeitschrift SIAM Journal on Optimization, online erschienen am 16.09.2025. Verfasst von Ruichen Jiang und 1 weiteren Autor:innen. Die Arbeit wurde bisher 3-mal zitiert (Crossref) und nennt 55 Literaturangaben. Gefördert von: National Science Foundation.
Abstract (Originalsprache)
The optimistic gradient method has seen increasing popularity as an efficient first-order method for solving convex-concave saddle point problems. To analyze its iteration complexity, a recent work [A. Mokhtari, A. E. Ozdaglar, and S. Pattathil, SIAM J. Optim., 30 (2020), pp. 3230–3251] proposed an interesting perspective that interprets the optimistic gradient method as an approximation to the proximal point method. In this paper, we follow this approach and distill the underlying idea of optimism to propose a generalized optimistic method, which encompasses the optimistic gradient method as a special case. Our general framework can handle constrained saddle point problems with composite objective functions. Moreover, we also develop a backtracking line search scheme to select the step sizes without knowledge of the smoothness coefficients. By instantiating our general framework with a second-order oracle, we propose a second-order optimistic method and prove a complexity bound of [Formula: see text] in terms of the primal-dual gap in the convex-concave setting and a complexity bound of [Formula: see text] in terms of the distance to the optimal solution in the strongly-convex-strongly-concave setting, where [Formula: see text] is the Lipschitz constant of the Jacobian, [Formula: see text] is the strong convexity parameter, and [Formula: see text] is the initial Euclidean distance to the saddle point. We also establish convergence rates in terms of the tangent residual, which generalizes the operator norm as a metric in the unconstrained setting. Moreover, our line search scheme provably only requires a constant number of calls to a subproblem solver per iteration on average.
Förderung
- National Science Foundation
Zitieren
APA
Jiang, R., & Mokhtari, A. (2025). Generalized Optimistic Methods for Convex-Concave Saddle Point Problems. SIAM Journal on Optimization, 35(3), 2066-2097. https://doi.org/10.1137/24m1630475
Vancouver
Jiang R, Mokhtari A. Generalized Optimistic Methods for Convex-Concave Saddle Point Problems. SIAM Journal on Optimization. 2025;35(3):2066-2097. doi:10.1137/24m1630475
BibTeX
@article{Jiang2025,
author = {Jiang, Ruichen and Mokhtari, Aryan},
title = {Generalized Optimistic Methods for Convex-Concave Saddle Point Problems},
journal = {SIAM Journal on Optimization},
year = {2025},
volume = {35},
number = {3},
pages = {2066--2097},
doi = {10.1137/24m1630475}
}
EUVIMED