FISTA is an automatic geometrically optimized algorithm for strongly convex functions
Langue
en
Document de travail - Pré-publication
Résumé en anglais
In this work, we are interested in the famous FISTA algorithm. We show that FISTA is an automatic geometrically optimized algorithm for functions satisfying a quadratic growth assumption. This explains why FISTA works ...Lire la suite >
In this work, we are interested in the famous FISTA algorithm. We show that FISTA is an automatic geometrically optimized algorithm for functions satisfying a quadratic growth assumption. This explains why FISTA works better than the standard Forward-Backward algorithm (FB) in such a case, although FISTA is known to have a polynomial asymptotical convergence rate while FB is exponential. We provide a simple rule to tune the α parameter within the FISTA algorithm to reach an ε-solution with an optimal number of iterations. These new results highlight the efficiency of FISTA algorithms, and they rely on new non asymptotic bounds for FISTA.< Réduire
Mots clés en anglais
Nesterov acceleration
ODE
first order scheme
optimization
Origine
Importé de halUnités de recherche