# Contractivity and linear convergence in bilinear saddle-point problems: An operator-theoretic approach

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 40 of its 81 references that are in the map.
- First posted on arXiv 18 Oct 2024.

## Builds on (most cited first, 30 of 40)

- [Training GANs with Optimism](https://mlsanity.com/paper/1711.00141/) (2017)
- [A Variational Inequality Perspective on Generative Adversarial Networks](https://mlsanity.com/paper/1802.10551/) (2018)
- [A Unified Analysis of Extra-gradient and Optimistic Gradient Methods for Saddle Point Problems: Proximal Point Approach](https://mlsanity.com/paper/1901.08511/) (2019)
- [Interaction Matters: A Note on Non-asymptotic Local Convergence of Generative Adversarial Networks](https://mlsanity.com/paper/1802.06132/) (2018)
- [Stochastic Variance Reduction Methods for Saddle-Point Problems](https://mlsanity.com/paper/1605.06398/) (2016)
- [Stochastic Variance Reduction Methods for Policy Evaluation](https://mlsanity.com/paper/1702.07944/) (2017)
- [Optimal and Practical Algorithms for Smooth and Strongly Convex Decentralized Optimization](https://mlsanity.com/paper/2006.11773/) (2020)
- [Improved Algorithms for Convex-Concave Minimax Optimization](https://mlsanity.com/paper/2006.06359/) (2020)
- [Stochastic Primal-Dual Coordinate Method for Regularized Empirical Risk Minimization](https://mlsanity.com/paper/1409.3257/) (2014)
- [Near-optimal Local Convergence of Alternating Gradient Descent-Ascent for Minimax Optimization](https://mlsanity.com/paper/2102.09468/) (2021)
- [Linear Convergence of the Primal-Dual Gradient Method for Convex-Concave Saddle Point Problems without Strong Convexity](https://mlsanity.com/paper/1802.01504/) (2018)
- [Correlation in Extensive-Form Games: Saddle-Point Formulation and Benchmarks](https://mlsanity.com/paper/1905.12564/) (2019)
- [Accelerated Proximal Stochastic Dual Coordinate Ascent for Regularized Loss Minimization](https://mlsanity.com/paper/1309.2375/) (2013)
- [Communication Acceleration of Local Gradient Methods via an Accelerated Primal-Dual Algorithm with Inexact Prox](https://mlsanity.com/paper/2207.03957/) (2022)
- [Proximal Splitting Algorithms for Convex Optimization: A Tour of Recent Advances, with New Twists](https://mlsanity.com/paper/1912.00137/) (2019)
- [Accelerated Primal-Dual Gradient Method for Smooth and Convex-Concave Saddle-Point Problems with Bilinear Coupling](https://mlsanity.com/paper/2112.15199/) (2021)
- [Distributed Algorithms for Composite Optimization: Unified Framework and Convergence Analysis](https://mlsanity.com/paper/2002.11534/) (2020)
- [Lifted Primal-Dual Method for Bilinearly Coupled Smooth Minimax Optimization](https://mlsanity.com/paper/2201.07427/) (2022)
- [On the Exponential Stability of Primal-Dual Gradient Dynamics](https://mlsanity.com/paper/1803.01825/) (2018)
- [Linear Convergence of Primal-Dual Gradient Methods and their Performance in Distributed Optimization](https://mlsanity.com/paper/1904.01196/) (2019)
- [Exploiting Strong Convexity from Data with Primal-Dual First-Order Algorithms](https://mlsanity.com/paper/1703.02624/) (2017)
- [An Optimal Algorithm for Strongly Convex Minimization under Affine Constraints](https://mlsanity.com/paper/2102.11079/) (2021)
- [DSCOVR: Randomized Primal-Dual Block Coordinate Algorithms for Asynchronous Distributed Optimization](https://mlsanity.com/paper/1710.05080/) (2017)
- [Geometric Convergence of Gradient Play Algorithms for Distributed Nash Equilibrium Seeking](https://mlsanity.com/paper/1809.07383/) (2018)
- [Time-Varying Convex Optimization: A Contraction and Equilibrium Tracking Approach](https://mlsanity.com/paper/2305.15595/) (2023)
- [An inertial forward-backward algorithm for monotone inclusions](https://mlsanity.com/paper/1403.3522/) (2014)
- [A forward-backward view of some primal-dual optimization methods in image recovery](https://mlsanity.com/paper/1406.5439/) (2014)
- [Scaled Relative Graph: Nonexpansive operators via 2D Euclidean Geometry](https://mlsanity.com/paper/1902.09788/) (2019)
- [Distributed and time-varying primal-dual dynamics via contraction analysis](https://mlsanity.com/paper/2003.12665/) (2020)
- [Dualize, Split, Randomize: Toward Fast Nonsmooth Optimization Algorithms](https://mlsanity.com/paper/2004.02635/) (2020)

## Abstract (arXiv)

We study the convex-concave bilinear saddle-point problem minx maxy f(x) + y^top Ax - g(y), where both, only one, or none of the functions f and g are strongly convex, and suitable rank conditions on the matrix A hold. The solution of this problem is at the core of many machine learning tasks. By employing tools from monotone operator theory, we systematically prove the contractivity (in turn, the linear convergence) of several first-order primal-dual algorithms, including the Chambolle-Pock method. Our approach results in concise proofs, and it yields new convergence guarantees and tighter bounds compared to known results.