# On Linear Convergence in Smooth Convex-Concave Bilinearly-Coupled Saddle-Point Optimization: Lower Bounds and Optimal Algorithms

arXiv: https://arxiv.org/abs/2411.14601 · HTML: https://mlsanity.com/paper/2411.14601/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 21 Nov 2024.

## Built on by (most cited first, 6 of 6)

- [SGD with Adaptive Preconditioning: Unified Analysis and Momentum Acceleration](https://mlsanity.com/paper/2506.23803/) (2025)
- [Negative Stepsizes Make Gradient-Descent-Ascent Converge](https://mlsanity.com/paper/2505.01423/) (2025)
- [Nesterov Finds GRAAL: Optimal and Adaptive Gradient Method for Convex Optimization](https://mlsanity.com/paper/2507.09823/) (2025)
- [A Tale of Two Geometries: Adaptive Optimizers and Non-Euclidean Descent](https://mlsanity.com/paper/2511.20584/) (2025)
- [Optimal Projection-Free Adaptive SGD for Matrix Optimization](https://mlsanity.com/paper/2604.02505/) (2026)
- [Decentralized Optimization with Cross-Coupled Mixed Affine Constraints](https://mlsanity.com/paper/2609.33021/) (2026)

## Abstract (arXiv)

We revisit the smooth convex-concave bilinearly-coupled saddle-point problem of the form minxmaxy f(x) + langle y,B xrangle - g(y). In the highly specific case where each of the functions f(x) and g(y) is either affine or strongly convex, there exist lower bounds on the number of gradient evaluations and matrix-vector multiplications required to solve the problem, as well as matching optimal algorithms. A notable aspect of these algorithms is that they are able to attain linear convergence, i.e., the number of iterations required to solve the problem is proportional to log(1/ε). However, the class of bilinearly-coupled saddle-point problems for which linear convergence is possible is much wider and can involve smooth non-strongly convex functions f(x) and g(y). Therefore, we develop the first lower complexity bounds and matching optimal linearly converging algorithms for this problem class. Our lower complexity bounds are much more general, but they cover and unify the existing results in the literature. On the other hand, our algorithm implements the separation of complexities, which, for the first time, enables the simultaneous achievement of both optimal gradient evaluation and matrix-vector multiplication complexities, resulting in the best theoretical performance to date.