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
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
Subjects
Scopus EID
2-s2.0-85075618245
PubMed ID
ISBN
9789082797039
Source
European Signal Processing Conference
ISSN of the container
22195491
Sources of information:
Directorio de Producción Científica
Scopus