Local Linear Convergence of Forward-Backward under Partial Smoothness

Abstract

In this paper, we consider the Forward--Backward proximal splitting algorithm to minimize the sum of two proper convex functions, one of which having a Lipschitz continuous gradient and the other being partly smooth relative to an active manifold $\mathcal{M}$. We propose a generic framework under which we show that the Forward--Backward (i) correctly identifies the active manifold $\mathcal{M}$ in a finite number of iterations, and then (ii) enters a local linear convergence regime that we characterize precisely. This gives a grounded and unified explanation to the typical behaviour that has been observed numerically for many problems encompassed in our framework, including the Lasso, the group Lasso, the fused Lasso and the nuclear norm regularization to name a few. These results may have numerous applications including in signal/image processing processing, sparse recovery and machine learning.

arXiv comment14 pages, 1 figure

References in corpus (3)

• Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
• Consistency of trace norm minimization
• Trace Lasso: a trace norm regularization for correlated designs

Cited by in corpus (12)

• Convergence of the Forward-Backward Algorithm: Beyond the Worst Case with the Help of Geometry
• Block-proximal methods with spatially adapted acceleration
• Trajectory of Alternating Direction Method of Multipliers and Adaptive Acceleration
• Geometry of First-Order Methods and Adaptive Acceleration
• Best Pair Formulation & Accelerated Scheme for Non-convex Principal Component Pursuit
• Thresholding gradient methods in Hilbert spaces: support identification and linear convergence
• Learning step sizes for unfolded sparse coding
• Identifiability, the KL property in metric spaces, and subgradient curves
• Implicit Differentiation for Hyperparameter Tuning the Weighted Graphical Lasso
• Sparse Multiple Kernel Learning: Support Identification via Mirror Stratifiability
• Optimization of Graph Total Variation via Active-Set-based Combinatorial Reconditioning
• Activity Identification and Local Linear Convergence of Douglas--Rachford/ADMM under Partial Smoothness