mlsanityData to 7 Oct 2026

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

arXiv 2410.14592 ↗First posted 18 Oct 2024math.OC cs.LGcited by 0

Not on the map. Why?

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.

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

Builds on

40 of 81 references.

References · 40

  1. 2017Training GANs with Optimismcited by 217
  2. 2018A Variational Inequality Perspective on Generative Adversarial Networkscited by 144
  3. 2019A Unified Analysis of Extra-gradient and Optimistic Gradient Methods for Saddle Point Problems: Proximal Point Approachcited by 142
  4. 2018Interaction Matters: A Note on Non-asymptotic Local Convergence of Generative Adversarial Networkscited by 68
  5. 2016Stochastic Variance Reduction Methods for Saddle-Point Problemscited by 57
  6. 2017Stochastic Variance Reduction Methods for Policy Evaluationcited by 56
  7. 2020Optimal and Practical Algorithms for Smooth and Strongly Convex Decentralized Optimizationcited by 43
  8. 2020Improved Algorithms for Convex-Concave Minimax Optimizationcited by 34
  9. 2021Near-optimal Local Convergence of Alternating Gradient Descent-Ascent for Minimax Optimizationcited by 31
  10. 2014Stochastic Primal-Dual Coordinate Method for Regularized Empirical Risk Minimizationcited by 30
  11. 2018Linear Convergence of the Primal-Dual Gradient Method for Convex-Concave Saddle Point Problems without Strong Convexitycited by 28
  12. 2019Correlation in Extensive-Form Games: Saddle-Point Formulation and Benchmarkscited by 23
28 more
  1. 2013Accelerated Proximal Stochastic Dual Coordinate Ascent for Regularized Loss Minimizationcited by 19
  2. 2022Communication Acceleration of Local Gradient Methods via an Accelerated Primal-Dual Algorithm with Inexact Proxcited by 19
  3. 2021Accelerated Primal-Dual Gradient Method for Smooth and Convex-Concave Saddle-Point Problems with Bilinear Couplingcited by 16
  4. 2019Proximal Splitting Algorithms for Convex Optimization: A Tour of Recent Advances, with New Twistscited by 15
  5. 2020Distributed Algorithms for Composite Optimization: Unified Framework and Convergence Analysiscited by 15
  6. 2022Lifted Primal-Dual Method for Bilinearly Coupled Smooth Minimax Optimizationcited by 13
  7. 2018On the Exponential Stability of Primal-Dual Gradient Dynamicscited by 12
  8. 2019Linear Convergence of Primal-Dual Gradient Methods and their Performance in Distributed Optimizationcited by 11
  9. 2017Exploiting Strong Convexity from Data with Primal-Dual First-Order Algorithmscited by 8
  10. 2021An Optimal Algorithm for Strongly Convex Minimization under Affine Constraintscited by 8
  11. 2017DSCOVR: Randomized Primal-Dual Block Coordinate Algorithms for Asynchronous Distributed Optimizationcited by 7
  12. 2018Geometric Convergence of Gradient Play Algorithms for Distributed Nash Equilibrium Seekingcited by 6
  13. 2023Time-Varying Convex Optimization: A Contraction and Equilibrium Tracking Approachcited by 6
  14. 2014An inertial forward-backward algorithm for monotone inclusionscited by 5
  15. 2014A forward-backward view of some primal-dual optimization methods in image recoverycited by 5
  16. 2019Scaled Relative Graph: Nonexpansive operators via 2D Euclidean Geometrycited by 5
  17. 2020Distributed and time-varying primal-dual dynamics via contraction analysiscited by 5
  18. 2020Dualize, Split, Randomize: Toward Fast Nonsmooth Optimization Algorithmscited by 5
  19. 2022Convergence rate analysis of the gradient descent-ascent method for convex-concave saddle-point problemscited by 5
  20. 2016A Generic online acceleration scheme for Optimization algorithms via Relaxation and Inertiacited by 3
  21. 2021Degenerate Preconditioned Proximal Point algorithmscited by 3
  22. 2022Distributed saddle point problems for strongly concave-convex functionscited by 3
  23. 2013A Primal Dual Active Set Algorithm with Continuation for Compressed Sensingcited by 2
  24. 2019On compositions of special cases of Lipschitz continuous operatorscited by 2
  25. 2020Fast generalized Nash equilibrium seeking under partial-decision informationcited by 2
  26. 2022Chambolle-Pock's Primal-Dual Method with Mismatched Adjointcited by 2
  27. 2019Contraction Analysis on Primal-Dual Gradient Optimizationcited by 1
  28. 2022A Unified Primal-Dual Algorithm Framework for Inequality Constrained Problemscited by 1

Built on by

Not cited yet.