FISTA: Achieving a rate of convergence proportional to k3 for small/medium values of K

Gustavo Silva, Paul Rodriguez, Peru Lima

Producción científica: Capítulo del libro/informe/acta de congresoContribución a la conferenciarevisión exhaustiva

3 Citas (Scopus)

Resumen

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(k2) since, originally, (i) by construction tkk+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 k3 for the indexes where the step-size exhibits an approximate linear growth, with the default O(k2) 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.

Idioma originalInglés
Título de la publicación alojadaEUSIPCO 2019 - 27th European Signal Processing Conference
EditorialEuropean Signal Processing Conference, EUSIPCO
ISBN (versión digital)9789082797039
DOI
EstadoPublicada - set. 2019
Evento27th European Signal Processing Conference, EUSIPCO 2019 - A Coruna, Espana
Duración: 2 set. 20196 set. 2019

Serie de la publicación

NombreEuropean Signal Processing Conference
Volumen2019-September
ISSN (versión impresa)2219-5491

Conferencia

Conferencia27th European Signal Processing Conference, EUSIPCO 2019
País/TerritorioEspana
CiudadA Coruna
Período2/09/196/09/19

Huella

Profundice en los temas de investigación de 'FISTA: Achieving a rate of convergence proportional to k3 for small/medium values of K'. En conjunto forman una huella única.

Citar esto