FISTA Restart Using an Automatic Estimation of the Growth Parameter

In this paper, we propose a restart scheme for FISTA (Fast Iterative Shrinking-Threshold Algorithm) [6]. This method which is a generalisation of Nesterov’s accelerated gradient algorithm [23] is widely used in the field of large-scale convex optimization problems as it ensures a quadratic decrease $$o\left( 1/k^2\right) $$ o 1 / k 2 of the error for convex functions [3, 12]. When considering a function that satisfies stronger assumptions such as strong convexity or quadratic growth, several methods provide faster convergence rates by taking advantage of this geometry property, including FISTA restart schemes. In particular, the schemes that provide the fastest theoretical convergence rates rely on the growth parameter of the function, which is generally difficult to estimate. Recent works [1, 2] show that restarting FISTA can ensure a fast convergence for functions having a quadratic growth without requiring any knowledge on the growth parameter. We improve these restart schemes by providing a better asymptotical convergence rate and by requiring a lower computational cost. We illustrate our theoretical results with some numerical examples.