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

Guillaume Garrigos, Lorenzo Rosasco, Silvia Villa

Published 2017-03-28Version 1

We provide a comprehensive study of the convergence of forward-backward algorithm under suitable geometric conditions leading to fast rates. We present several new results and collect in a unified view a variety of results scattered in the literature, often providing simplified proofs. Novel contributions include the analysis of infinite dimensional convex minimization problems, allowing the case where minimizers might not exist. Further, we analyze the relation between different geometric conditions, and discuss novel connections with a priori conditions in linear inverse problems, including source conditions, restricted isometry properties and partial smoothness.