Convergence of the Forward-Backward Algorithm: Beyond the Worst Case with the Help of Geometry

Abstract

We provide a comprehensive study of the convergence of the forward-backward algorithm under suitable geometric conditions, such as conditioning or Łojasiewicz properties. These geometrical notions are usually local by nature, and may fail to describe the fine geometry of objective functions relevant in inverse problems and signal processing, that have a nice behaviour on manifolds, or sets open with respect to a weak topology. Motivated by this observation, we revisit those geometric notions over arbitrary sets. In turn, this allows us to present several new results as well as collect in a unified view a variety of results scattered in the literature. Our contributions include the analysis of infinite dimensional convex minimization problems, showing the first Łojasiewicz inequality for a quadratic function associated to a compact operator, and the derivation of new linear rates for problems arising from inverse problems with low-complexity priors. Our approach allows to establish unexpected connections between geometry and a priori conditions in inverse problems, such as source conditions, or restricted isometry properties.

After peer-review, the paper has been significantly modified: i) Section 3.3 has been completely rewritten, and contains a new sum rule (Theorem 3.15) ii) The end of Section 4.2 and Section 5.2 have been rewritten to include mirror-stratifiable problems iii) The Annex contains new proofs for small-but-not-trivial claims made throughout the paper iv) Theorems, Examples etc have been renumbered

References in corpus (5)

• Calculus of the exponent of Kurdyka-Łojasiewicz inequality and its applications to linear convergence of first-order methods
• Second-order growth, tilt stability, and metric regularity of the subdifferential
• Local Linear Convergence of Forward-Backward under Partial Smoothness
• Accelerated iterative regularization via dual diagonal descent
• Thresholding gradient methods in Hilbert spaces: support identification and linear convergence

Cited by in corpus (7)

• Time-Varying Convex Optimization via Time-Varying Averaged Operators
• Sampling as optimization in the space of measures: The Langevin dynamics as a composite optimization problem
• New Analysis of Linear Convergence of Gradient-type Methods via Unifying Error Bound Conditions
• Thresholding gradient methods in Hilbert spaces: support identification and linear convergence
• Beating SGD Saturation with Tail-Averaging and Minibatching
• Optimization of Graph Total Variation via Active-Set-based Combinatorial Reconditioning
• Proximal-Like Incremental Aggregated Gradient Method with Linear Convergence under Bregman Distance Growth Conditions