On the ergodic convergence rates of a first-order primal–dual algorithm

By Antonin Chambolle, Thomas Pock. 2016

557 citations recorded by the source corpus.

Subfields: Computational Mechanics, Computational Theory and Mathematics, Numerical Analysis

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mechanics

In Computational Theory and Mathematics

In Numerical Analysis

Citations in the corpus

Distributed Fixed Point Methods with Compressed Iterates (2019, methodology): “The PDHG algorithm [7,8], Primal–Dual 3 Operators (PD3O) and Primal–Dual Davis–Yin (PDDY) splitting The PD3O [47] and the PDDY [39] algorithms are similar to the Condat–”
Techniques for Gradient-Based Bilevel Optimization with Non-smooth Lower Level Problems (2016, methodology): “Since the primal–dual algorithm with Bregman proximity functions from [9] provides us with a flexible tool,”
Solving a Class of Non-Convex Min-Max Games Using Iterative First Order Methods (2019, methodology): “This failure of simple gradient descent-ascent for bilinear games was overcome by optimistic mirror descent and primal-dual methods proposed by [9, 13].”
A Conditional Gradient-based Method for Simple Bilevel Optimization with Convex Lower-level Problem (2022, methodology): “Since it is a convex program with linear constraints, we can implement a first-order primal-dual method (see, e.g., (Chambolle and Pock, 2016)) to find g0 such that |g0 − g∗| ≤ g/4 within at most O(Lg+‖A‖ g ) iterations 1.”
A New Primal–Dual Algorithm for Minimizing the Sum of Three Functions with a Linear Operator (2016, background): “Even for primal-dual algorithms, there are accelerated versions available [6].”
Randomized First-Order Methods for Saddle Point Optimization (2014, unknown): “It is worth noting that Chambolle and Pock [6] had also released their results on the convergence of the ergodic means for deterministic primal-dual methods shortly after we released the initial version of the current paper in Sep.”
A note on the inertial proximal point method (2015, background): “See also the latest references [11, 21, 14, 12, 13], which analyzed the convergence properties of inertial type algorithms for maximal monotone inclusion problem, variational inequality and structured convex optimization, and demonstrated their performance numerically on some imaging and data analys”
Distributed Linearized Alternating Direction Method of Multipliers for Composite Convex Consensus Optimization (2015, methodology): “Note that PG-ADMM is more general than PDAs in [12], [13] in the sense that it can also deal with noisy gradients while PDAs cannot.”
Distributed Proximal Splitting Algorithms with Rates and Acceleration (2020, unknown): “Even for the existing accelerated Chambolle–Pock algorithm [2,3], which we recover as a particular case but with a different stepsize rule, our O(1/k2) rate is on the last iterate, improving upon the best known result, which is ergodic [3].”
Linear convergence of primal-dual gradient methods and their performance in distributed optimization (2019, background): “Similarly, the works [21], [22] also establish linear convergence of general saddle-point problems with conditions on both primal and dual functions; moreover, the recursion of the algorithm requires the proximal mappings of both J(.”
Scaling Algorithms for Unbalanced Transport Problems (2016, methodology): “The most simple one is the proximal point algorithm [31], but most proximal splitting schemes have been extended to this setting, such as for instance ADMM [78], primal-dual schemes [23] and forward-backward [54].”
Convergence results of two-step inertial proximal point algorithm (2022, methodology): “The primal-dual hybrid gradient (PDHG) method (see, for example, [18,29]) is one of the popular methods for solving problem (58) and it is a preconditioned proximal point algorithm with λ = 1 for the saddle subdifferential operator of φ given in (53) (see, [19,34]).”