Direct Spectral Acceleration of First-Order Methods for Saddle Point Problems with Bilinear Coupling

Meng Li, Paul Grigas · 2026

Read Direct Spectral Acceleration of First-Order Methods for Saddle Point Problems with Bilinear Coupling by Meng Li, Paul Grigas (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2602-23727.txt.

Description

Meng Li and one co-author propose direct spectral speedup of first-order methods for saddle point problems with two-linear coupling. Such problems cover limited convex tuning and more general models via a prox-friendly term in the dual goal. In steady-gain regimes, the team maps how spectral traits of the coupling matrix and goal shape set the best linear rates.

The new speedup applies to first-order primal-dual methods for two-linear-coupled saddle point problems, including affine-limited smooth strongly convex tuning and spinoffs. The final methods split goal-led and coupling-led regimes and attain best linear gains without inner loops. Random block extensions in the affine-limited case with split goals are built, with best linear rates matching the block lower bound. For fixed and random methods, matching worst-case lower bounds are given via set finite-dim hard cases.

Catalog record

CREATORMeng Li, Paul Grigas
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE169 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2602-23727

Browse the full library · About the Tower of Babel