FISTA is an automatic geometrically optimized algorithm for strongly convex functions

• 成果类型: Article
• 署名作者: Aujol, J. -F.; Dossal, Ch.; Rondepierre, A.
• 署名单位: Universite de Bordeaux; Centre National de la Recherche Scientifique (CNRS); Universite Federale Toulouse Midi-Pyrenees (ComUE); Universite de Toulouse; Institut National des Sciences Appliquees de Toulouse; Universite Toulouse III - Paul Sabatier; Universite de Toulouse; Centre National de la Recherche Scientifique (CNRS)
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-023-01960-6
• 发表日期: 2024
• 页码: 449-491
• 关键词: CONVERGENCE-RATES; gradient methods

摘要

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 asymptotic convergence rate while FB is exponential. We provide a simple rule to tune the alpha parameter within the FISTA algorithm to reach an epsilon-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.