# Lower complexity bounds of first-order methods for convex-concave bilinear saddle-point problems

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

## Key facts

- Cited by 76 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Aug 2018.

## Built on by (most cited first, 30 of 76)

- [Stochastic Variance Reduction for Variational Inequality Methods](https://mlsanity.com/paper/2102.08352/) (2021)
- [Lower Bounds and Accelerated Algorithms for Bilevel Optimization](https://mlsanity.com/paper/2102.03926/) (2021)
- [The Complexity of Nonconvex-Strongly-Concave Minimax Optimization](https://mlsanity.com/paper/2103.15888/) (2021)
- [Local Stochastic Gradient Descent Ascent: Convergence Analysis and Communication Efficiency](https://mlsanity.com/paper/2102.13152/) (2021)
- [Federated Minimax Optimization: Improved Convergence Analyses and Algorithms](https://mlsanity.com/paper/2203.04850/) (2022)
- [Complexity Lower Bounds for Nonconvex-Strongly-Concave Min-Max Optimization](https://mlsanity.com/paper/2104.08708/) (2021)
- [Accelerated Single-Call Methods for Constrained Min-Max Optimization](https://mlsanity.com/paper/2210.03096/) (2022)
- [Lower Complexity Bounds of Finite-Sum Optimization Problems: The Results and Construction](https://mlsanity.com/paper/2103.08280/) (2021)
- [No-Regret Dynamics in the Fenchel Game: A Unified Framework for Algorithmic Convex Optimization](https://mlsanity.com/paper/2111.11309/) (2021)
- [Accelerated Algorithms for Constrained Nonconvex-Nonconcave Min-Max Optimization and Comonotone Inclusion](https://mlsanity.com/paper/2206.05248/) (2022)
- [Faster Algorithm and Sharper Analysis for Constrained Markov Decision Process](https://mlsanity.com/paper/2110.10351/) (2021)
- [Stochastic Halpern Iteration with Variance Reduction for Stochastic Monotone Inclusions](https://mlsanity.com/paper/2203.09436/) (2022)
- [Accelerated and instance-optimal policy evaluation with linear function approximation](https://mlsanity.com/paper/2112.13109/) (2021)
- [Near Optimal Stochastic Algorithms for Finite-Sum Unbalanced Convex-Concave Minimax Optimization](https://mlsanity.com/paper/2106.01761/) (2021)
- [Doubly Optimal No-Regret Learning in Monotone Games](https://mlsanity.com/paper/2301.13120/) (2023)
- [Lifted Primal-Dual Method for Bilinearly Coupled Smooth Minimax Optimization](https://mlsanity.com/paper/2201.07427/) (2022)
- [Beyond the Golden Ratio for Variational Inequality Algorithms](https://mlsanity.com/paper/2212.13955/) (2022)
- [Stochastic Distributed Optimization under Average Second-order Similarity: Algorithms and Analysis](https://mlsanity.com/paper/2304.07504/) (2023)
- [Variance Reduced Halpern Iteration for Finite-Sum Monotone Inclusions](https://mlsanity.com/paper/2310.02987/) (2023)
- [Efficient Algorithms for Empirical Group Distributionally Robust Optimization and Beyond](https://mlsanity.com/paper/2403.03562/) (2024)
- [Variance Reduction via Primal-Dual Accelerated Dual Averaging for Nonsmooth Convex Finite-Sums](https://mlsanity.com/paper/2102.13643/) (2021)
- [Coordinate Linear Variance Reduction for Generalized Linear Programming](https://mlsanity.com/paper/2111.01842/) (2021)
- [Quasi-Newton Methods for Saddle Point Problems and Beyond](https://mlsanity.com/paper/2111.02708/) (2021)
- [Optimal Gradient Sliding and its Application to Distributed Optimization Under Similarity](https://mlsanity.com/paper/2205.15136/) (2022)
- [Smooth Monotone Stochastic Variational Inequalities and Saddle Point Problems: A Survey](https://mlsanity.com/paper/2208.13592/) (2022)
- [Convex-Concave Min-Max Stackelberg Games](https://mlsanity.com/paper/2110.05192/) (2021)
- [Sion's Minimax Theorem in Geodesic Metric Spaces and a Riemannian Extragradient Algorithm](https://mlsanity.com/paper/2202.06950/) (2022)
- [First-Order Algorithms for Nonlinear Generalized Nash Equilibrium Problems](https://mlsanity.com/paper/2204.03132/) (2022)
- [On Convergence of Gradient Descent Ascent: A Tight Local Analysis](https://mlsanity.com/paper/2207.00957/) (2022)
- [Randomized Block-Coordinate Optimistic Gradient Algorithms for Root-Finding Problems](https://mlsanity.com/paper/2301.03113/) (2023)

## Abstract (arXiv)

On solving a convex-concave bilinear saddle-point problem (SPP), there have been many works studying the complexity results of first-order methods. These results are all about upper complexity bounds, which can determine at most how many efforts would guarantee a solution of desired accuracy. In this paper, we pursue the opposite direction by deriving lower complexity bounds of first-order methods on large-scale SPPs. Our results apply to the methods whose iterates are in the linear span of past first-order information, as well as more general methods that produce their iterates in an arbitrary manner based on first-order information. We first work on the affinely constrained smooth convex optimization that is a special case of SPP. Different from gradient method on unconstrained problems, we show that first-order methods on affinely constrained problems generally cannot be accelerated from the known convergence rate O(1/t) to O(1/t2), and in addition, O(1/t) is optimal for convex problems. Moreover, we prove that for strongly convex problems, O(1/t2) is the best possible convergence rate, while it is known that gradient methods can have linear convergence on unconstrained problems. Then we extend these results to general SPPs. It turns out that our lower complexity bounds match with several established upper complexity bounds in the literature, and thus they are tight and indicate the optimality of several existing first-order methods.