Local Linear Convergence of Forward–Backward under Partial Smoothness

  • Jalal Fadili
  • Jingwei Liang
  • Gabriel Peyré
    • Categories Convex and Nonsmooth Optimization, Convex Optimization, Nonsmooth Optimization Tags , , , Short URL: https://optimization-online.org/?p=12966

    In this paper, we consider the Forward–Backward proximal splitting algorithm to minimize the sum of two proper closed convex functions, one of which having a Lipschitz–continuous gradient and the other being partly smooth relatively to an active manifold $\mathcal{M}$. We propose a unified framework in 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 explains 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.

    Citation

    GREYC CNRS UMR 6072, ENSICAEN 6, Bd du Maréchal Juin 14050 Caen Cedex, France

    Article

    Download

    View Local Linear Convergence of Forward–Backward under Partial Smoothness