EUVIMEDEUVIMED entdecken
Crossref

Generalized Optimistic Methods for Convex-Concave Saddle Point Problems

Ruichen Jiang, Aryan Mokhtari

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Infokarte | EUVIMED

Artikeldaten derzeit nicht verfügbar.

Recherche