Contractivity and linear convergence in bilinear saddle-point problems: An operator-theoretic approach
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866916697348243456 |
|---|---|
| author | Dirren, Colin Bianchi, Mattia Grontas, Panagiotis D. Lygeros, John Dörfler, Florian |
| author_facet | Dirren, Colin Bianchi, Mattia Grontas, Panagiotis D. Lygeros, John Dörfler, Florian |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_14592 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Contractivity and linear convergence in bilinear saddle-point problems: An operator-theoretic approach Dirren, Colin Bianchi, Mattia Grontas, Panagiotis D. Lygeros, John Dörfler, Florian Optimization and Control Machine Learning 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. |
| title | Contractivity and linear convergence in bilinear saddle-point problems: An operator-theoretic approach |
| topic | Optimization and Control Machine Learning |
| url | https://arxiv.org/abs/2410.14592 |