Local Linear Convergence of ISTA and FISTA on the LASSO Problem

DOI10.1137/151004549zbMATH Open1358.90101arXiv1501.02888OpenAlexW1495241813MaRDI QIDQ2954397FDOQ2954397

Authors: Shaozhe Tao, Daniel Boley, Shuzhong Zhang 

Publication date: 13 January 2017

Published in: SIAM Journal on Optimization (Search for Journal in Brave)

Abstract: We establish local linear convergence bounds for the ISTA and FISTA iterations on the model LASSO problem. We show that FISTA can be viewed as an accelerated ISTA process. Using a spectral analysis, we show that, when close enough to the solution, both iterations converge linearly, but FISTA slows down compared to ISTA, making it advantageous to switch to ISTA toward the end of the iteration processs. We illustrate the results with some synthetic numerical examples.

Full work available at URL: https://arxiv.org/abs/1501.02888

Recommendations

• scientific article; zbMATH DE number 6477533
• An iterative reduction FISTA algorithm for large-scale LASSO
• An improved linear convergence of FISTA for the LASSO problem with application to CT image reconstruction
• On tight bounds for the Lasso
• Strong convergence of a modified proximal algorithm for solving the lasso
• Fast exact conformalization of the Lasso using piecewise linear homotopy
• Some rates of convergence for the selected Lasso estimator
• A globally convergent algorithm for Lasso-penalized mixture of linear regression models
• Folded concave penalized sparse linear regression: sparsity, statistical performance, and algorithmic theory for local solutions

zbMATH Keywords

LASSOfirst-order algorithmslinear convergencelocal convergence analysis

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Convex programming (90C25) Computational methods for problems pertaining to operations research and mathematical programming (90-08)

Cited In (22)

• Robust reservoir rock fracture recognition based on a new sparse feature learning and data training method
• Sparse approximate reconstruction decomposed by two optimization problems
• Local linear convergence analysis of primal-dual splitting methods
• ``FISTA in Banach spaces with adaptive discretisations
• Activity identification and local linear convergence of forward-backward-type methods
• Sensitivity analysis for mirror-stratifiable convex functions
• Linear convergence of proximal gradient algorithm with extrapolation for a class of nonconvex nonsmooth minimization problems
• Linear convergence of inexact descent method and inexact proximal gradient algorithms for lower-order regularization problems
• Backtracking strategies for accelerated descent methods with smooth composite objectives
• Accelerating \(\ell^1\)-\(\ell^2\) deblurring using wavelet expansions of operators
• Local and global convergence of a general inertial proximal splitting scheme for minimizing composite functions
• Local linear convergence of proximal coordinate descent algorithm
• Perturbation techniques for convergence analysis of proximal gradient method and other first-order algorithms via variational analysis
• On the linear convergence of forward-backward splitting method. I: Convergence analysis
• Quadratic growth conditions and uniqueness of optimal solution to Lasso
• Evaluating visual properties via robust HodgeRank
• An improved linear convergence of FISTA for the LASSO problem with application to CT image reconstruction
• Iterative positive thresholding algorithm for non-negative sparse optimization
• A generic online acceleration scheme for optimization algorithms via relaxation and inertia
• Some modified fast iterative shrinkage thresholding algorithms with a new adaptive non-monotone stepsize strategy for nonsmooth and convex minimization problems
• A wonderful triangle in compressed sensing
• A convex relaxation framework consisting of a primal-dual alternative algorithm for solving \(\ell_0\) sparsity-induced optimization problems with application to signal recovery based image restoration

This page was built for publication: Local Linear Convergence of ISTA and FISTA on the LASSO Problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2954397)