Local linear convergence of ISTA and FISTA on the LASSO problem

Research output: Contribution to journalArticlepeer-review

28 Scopus citations

Abstract

We use a model LASSO problem to analyze the convergence behavior of the ISTA and FISTA iterations, showing that both iterations satisfy local linear convergence rate bound when close enough to the solution. Using the observation that FISTA is an accelerated ISTA process, and a spectral analysis of the associated matrix operators, we show that FISTA's convergence rate can slow down as it proceeds, eventually becoming slower than ISTA. This observation leads to a proposed heuristic algorithm to take an ISTA step if it shows more progress compared to FISTA, as measured by the decrease in the objective function. We illustrate the results with some synthetic numerical examples.

Original languageEnglish (US)
Pages (from-to)313-336
Number of pages24
JournalSIAM Journal on Optimization
Volume26
Issue number1
DOIs
StatePublished - 2016

Bibliographical note

Publisher Copyright:
© 2016 Society for Industrial and Applied Mathematics.

Keywords

  • First order algorithms
  • LASSO
  • Linear convergence
  • Local convergence analysis

Fingerprint

Dive into the research topics of 'Local linear convergence of ISTA and FISTA on the LASSO problem'. Together they form a unique fingerprint.

Cite this