Make FISTA Faster Again


Jingwei Liang, University of Cambridge


2018.12.20 15:00-16:00


601 Pao Yue-Kong Library


The “fast iterative shrinkage-thresholding algorithm’’, a.k.a. FISTA, probably is the most well-known first-order optimisation scheme in the literature, as it achieves the worst-case $O(1/k^2)$ optimal convergence speed for the objective function value. However, despite its optimal theoretical rate, in practice the (local) oscillatory behaviour damps the efficiency of the algorithm. Over the past years, different modifications of FISTA are proposed in the literature in order to improve its practical performance, such as monotone FISTA and restarting FISTA. In this paper, we propose a simple yet effective modification to FISTA, such modification has mainly two advantages: 1) it enables us to prove the convergence of the generated sequence; 2) it allows to design a so-called ``lazy-start’’ strategy which can be significantly faster than the original scheme. Moreover, adaptive and greedy strategies are proposed, the performance of the resulted schemes outperforms the state-of-the-art schemes in the literature.