Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward–backward splitting, and regularized Gauss–Seidel methods

By Hédy Attouch, Jérôme Bolte, Benar Fux Svaiter. 2013

1,743 citations recorded by the source corpus.

Subfields: Computational Mechanics, Mathematical Physics, 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 Mathematical Physics

In Numerical Analysis

Citations in the corpus

Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Łojasiewicz Condition (2016, methodology): “The proof is given in Appendix H and although it is more complicated than the proofs of Theorems 4 and 5, it is arguably still simpler than existing proofs for proximal coordinate descent under SC [Richtárik and Takáč, 2014], KL [Attouch et al., 2013], or QG [Zhang, 2016].”
Accelerated Proximal Gradient Methods for Nonconvex Programming (2015, methodology): “Method name Assumption Accelerate (CP) converge (NCP) GD [16, 17] f + g: KL No Yes iPiano [18] nonconvex f , convex g No Yes GIST [19] nonconvex f , g = g1 − g2, g1, g2 convex No Yes GDPA [20] nonconvex f , g = g1 − g2, g1, g2 convex No Yes IR [8, 21] special f and g No Yes IFB [22] nonconvex f , no”
A Globally Convergent Algorithm for Nonconvex Optimization Based on Block Coordinate Update (2014, background): “A more general result is [5, Lemma 2.6], where three conditions for global convergence are given and are met by methods including averaged projection, proximal point, and forward-backward splitting.”
Modern regularization methods for inverse problems (2018, background): “It is important to emphasize that even for nonsmooth, nonconvex optimization there is a vast amount of recent publications, ranging from forward-backward, respectively proximaltype, schemes [8, 9, 10, 49, 50], over linearized proximal schemes [365, 47, 366, 298], to inertial methods [299, 309], prim”
Fusing Hyperspectral and Multispectral Images via Coupled Sparse Tensor Factorization (2018, methodology): “Under these conditions, the proof is a direct application of [46, Th. 6.2] by noting that Algorithm 2 is an instance of algorithm (61)-(62)-(63) shown in [46] with B i = β I with β > 0 (see [46, Remark 6.1]).”
A unifying framework for the analysis of projection-free first-order methods under a sufficient slope condition (2020, background): “, [4], [10], [36]), with a few simple adaptations to our smooth constrained projection-free setting.”
An introduction to continuous optimization for imaging (2016, background): “In general, block coordinate (or Gauss–Seidel) descent schemes can be implemented in many ways, and many generalizations involving non-smooth terms are proved to converge in the literature (Grippo and Sciandrone 2000, Auslender 1976, Attouch et al. 2013).”
Dynamical systems and forward–backward algorithms associated with the sum of a convex subdifferential and a monotone cocoercive operator (2014, methodology): “To cite some of these topics, in [22] the convergence of the classical forward–backward method, in a nonconvex nonsmooth framework, has been proved for functions satisfying the Kurdyka-Lojasiewiz inequality, a large class containing the semi-algebraic functions.”
Gradient Descent Only Converges to Minimizers (2016, background): “The Lojasiewicz inequality is very general as discussed in Bolte et al. (2010); Attouch et al. (2010, 2013).”
Global Convergence of Splitting Methods for Nonconvex Composite Optimization (2014, positive): “We would like to point out that our analysis is adapted from [3], and we cannot directly apply the results there since some of their assumptions are not satisfied in our settings.”
Gradient Descent Converges to Minimizers (2016, background): “The Lojasiewicz inequality is very general as discussed in [7, 4, 5].”
On Convergence of Model Parallel Proximal Gradient Algorithm for Stale Synchronous Parallel System (2016, background): “Then, inspired by the recent KurdykaLojasiewicz (K L) inequality [3, 5, 9, 11, 20], we further prove in Theorem 2 that the whole sequence of msPG in fact converges to a critical point, under mild technical assumptions that we verify for many familiar examples.”
Forward–backward quasi-Newton methods for nonsmooth optimization problems (2016, methodology): “Convergence of the iterates of FBS to a critical point of problem (1.1) has been shown, in the general nonconvex case, for functions ϕ having the Kurdyka-(cid:32)Lojasiewicz property [4–7].”
Global Convergence of ADMM in Nonconvex Nonsmooth Optimization (2015, background): “In addition, if Lβ is a KurdykaLojasiewicz (K L) function [29,4,1], then (x , y, w) converges globally to the unique limit point (x∗, y∗, w∗).”