Title
FISTA: Achieving a rate of convergence proportional to k−3 for small/medium values of K
Date Issued
01 September 2019
Access level
metadata only access
Resource Type
conference paper
Author(s)
SILVA OBREGON, GUSTAVO MANUEL
Lima P.
RODRIGUEZ VALDERRAMA, PAUL ANTONIO
Publisher(s)
European Signal Processing Conference, EUSIPCO
Abstract
The fast iterative shrinkage-thresholding algorithm (FISTA) is a widely used procedure for minimizing the sum of two convex functions, such that one has a L-Lipschitz continuous gradient and the other is possible nonsmooth. While FISTA's theoretical rate of convergence (RoC) is pro-1 portional to αkt2k , and it is related to (i) its extragradient rule / inertial sequence, which depends on sequence tk, and (ii) the stepsize αk, which estimates L, its worst-case complexity results in O(k−2) since, originally, (i) by construction tk ≥ k+12 , and (ii) the condition αk ≥ αk+1 was imposed. Attempts to improve FISTA's RoC include alternative inertial sequences, and intertwining the selection of the inertial sequence and the step-size. In this paper, we show that if a bounded and non-decreasing step-size sequence (αk ≤ αk+1, decoupled from the inertial sequence) can be generated via some adaptive scheme, then FISTA can achieve a RoC proportional to k−3 for the indexes where the step-size exhibits an approximate linear growth, with the default O(k−2) behavior when the step-size's bound is reached. Furthermore, such exceptional step-size sequence can be easily generated, and it indeed boots FISTA's practical performance.
Volume
2019-September
Language
English
OCDE Knowledge area
Otras ingenierías y tecnologías
Scopus EID
2-s2.0-85075618245
ISBN
9789082797039
Source
European Signal Processing Conference
ISSN of the container
22195491
Sources of information: Directorio de Producción Científica Scopus