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
| CREATOR | Meng Li, Paul Grigas |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 169 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2602-23727