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

Colin Dirren, Mattia Bianchi, Panagiotis D. Grontas, John Lygeros, Florian Dörfler
10/18/2024
math.OCcs.LG

No confident code implementation found for this paper.

Abstract

We study the convex-concave bilinear saddle-point problem $\min_x \max_y 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.

View on arXivView PDF

Code Implementations

No confident code match yet

We couldn't find an author-owned or strongly-evidenced community implementation for this paper. Any repos shown below are weak matches — verify before relying on them.

No code implementations found yet.

Know of an implementation? Let us know in the comments below!

Similar Papers

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

87% match2024

Fixed-Time Convergence for a Class of Nonconvex-Nonconcave Min-Max Problems

81% match2022

Auto-conditioned primal-dual hybrid gradient method and alternating direction method of multipliers

79% match2024

Efficient Uncoupled Learning Dynamics with $\tilde{O}\!\left(T^{-1/4}\right)$ Last-Iterate Convergence in Bilinear Saddle-Point Problems over Convex Sets under Bandit Feedback

79% match2026

Last-Iterate Convergence of Optimistic Multiplicative Weight Update

78% match2026

Communication Acceleration of Local Gradient Methods via an Accelerated Primal-Dual Algorithm with Inexact Prox

78% match2022

Cite this paper

@article{dirren2024contractivity,
  title  = {Contractivity and linear convergence in bilinear saddle-point problems: An operator-theoretic approach},
  author = {Colin Dirren and Mattia Bianchi and Panagiotis D. Grontas and John Lygeros and Florian Dörfler},
  year   = {2024},
  eprint = {2410.14592},
  archivePrefix = {arXiv},
  url    = {http://arxiv.org/abs/2410.14592v2}
}

Add a badge to your README

Shows whether official code is linked for this paper.

Code of Paper badge
[![Code of Paper](https://codeofpaper.com/badge/2410.14592.svg)](https://codeofpaper.com/paper/2410.14592)

Discussion