Improving ``fast iterative shrinkage-thresholding algorithm: faster, smarter, and greedier

DOI10.1137/21M1395685zbMATH Open1492.65163arXiv1811.01430OpenAlexW2990168768MaRDI QIDQ5075693FDOQ5075693

Authors: Jingwei Liang, Tao Luo, Carola-Bibiane Schönlieb 

Publication date: 11 May 2022

Published in: SIAM Journal on Scientific Computing (Search for Journal in Brave)

Abstract: The "fast iterative shrinkage-thresholding algorithm", a.k.a. FISTA, is one of the most well-known first-order optimisation scheme in the literature, as it achieves the worst-case $O(1/k^2)$ optimal convergence rate in terms of objective function value. However, despite such an optimal theoretical convergence rate, in practice the (local) oscillatory behaviour of FISTA often damps its efficiency. Over the past years, various efforts are made in the literature to improve the practical performance of FISTA, such as monotone FISTA, restarting FISTA and backtracking strategies. In this paper, we propose a simple yet effective modification to the original FISTA scheme which has two advantages: it allows us to 1) prove the convergence of generated sequence; 2) design a so-called "lazy-start" strategy which can up to an order faster than the original scheme. Moreover, by exploring the properties of FISTA scheme, we propose novel adaptive and greedy strategies which probes the limit of the algorithm. The advantages of the proposed schemes are tested through problems arising from inverse problem, machine learning and signal/image processing.

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

Recommendations

• scientific article; zbMATH DE number 7753352
• Some modified fast iterative shrinkage thresholding algorithms with a new adaptive non-monotone stepsize strategy for nonsmooth and convex minimization problems
• Over-relaxation of the fast iterative shrinkage-thresholding algorithm with variable stepsize
• Another look at the fast iterative shrinkage/thresholding algorithm (FISTA)
• A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems

zbMATH Keywords

adaptive and greedy accelerationfast iterative shrinkage-thresholding algorithm (FISTA)inertial forward-backwardlazy-start strategy

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Convex programming (90C25) Sensitivity, stability, parametric optimization (90C31)

Cites Work

• A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems
• Nonlinear total variation based noise removal algorithms
• Splitting Algorithms for the Sum of Two Nonlinear Operators
• Introductory lectures on convex optimization. A basic course.
• Adaptive restart for accelerated gradient schemes
• Robust principal component analysis?
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Signal Recovery by Proximal Forward-Backward Splitting
• Weak convergence of the sequence of successive approximations for nonexpansive mappings
• Convergence of a splitting inertial proximal method for monotone operators
• An inertial proximal method for maximal monotone operators via discretization of a nonlinear oscillator with damping
• Convergence rates with inexact non-expansive operators
• Some methods of speeding up the convergence of iteration methods
• An inertial forward-backward algorithm for monotone inclusions
• On the convergence of the iterates of the ``fast iterative shrinkage/thresholding algorithm
• An introduction to continuous optimization for imaging
• Backtracking Strategies for Accelerated Descent Methods with Smooth Composite Objectives
• Inertial forward-backward algorithms with perturbations: application to Tikhonov regularization
• Fast convergence of inertial dynamics and algorithms with asymptotic vanishing viscosity
• The rate of convergence of Nesterov's accelerated forward-backward method is actually faster than \(1/k^2\)
• Activity identification and local linear convergence of forward-backward-type methods
• Adaptive restart of the optimized gradient method for convex optimization
• Convergence rates of inertial forward-backward algorithms
• Convergence rates of forward-Douglas-Rachford splitting method
• Inertial, Corrected, Primal-Dual Proximal Splitting

Cited In (18)

• A fast inertial primal-dual algorithm to composite optimization models with application to image restoration problems
• A class of modified accelerated proximal gradient methods for nonsmooth and nonconvex minimization problems
• Forward-reflected-backward splitting algorithms with momentum: weak, linear and strong convergence results
• Fast gradient method for low-rank matrix estimation
• Over-relaxation of the fast iterative shrinkage-thresholding algorithm with variable stepsize
• ``FISTA in Banach spaces with adaptive discretisations
• Computable centering methods for spiraling algorithms and their duals, with motivations from the theory of Lyapunov functions
• Another look at the fast iterative shrinkage/thresholding algorithm (FISTA)
• Title not available (Why is that?)
• Parameter-free FISTA by adaptive restart and backtracking
• On the convergence of the iterates of the ``fast iterative shrinkage/thresholding algorithm
• Linearly-convergent FISTA variant for composite optimization with duality
• An improved parameterized fast iterative shrinkage-thresholding algorithm with adaptive step size and its applications
• Polynomial preconditioners for regularized linear inverse problems
• On FISTA with a relative error rule
• Improving first-order threshold implementations of \textsf{SKINNY}
• New proximal type algorithms for convex minimization and its application to image deblurring
• Approximation method for monotone inclusion problems in real Banach spaces with applications

This page was built for publication: Improving ``fast iterative shrinkage-thresholding algorithm: faster, smarter, and greedier

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