Restart of accelerated first order methods with linear convergence for non-strongly convex optimization

Accelerated first order methods, also called fast gradient methods, are popular optimization methods in the field of convex optimization. However, they are prone to suffer from oscillatory behaviour that slows their convergence when medium to high accuracy is desired. In order to address this, restart schemes have been proposed in the literature, which seek to improve the practical convergence by suppressing the oscillatory behaviour. This paper presents a restart scheme applicable to a broad class of accelerated first order methods. Under a quadratic functional growth condition, linear convergence rate is proved for a large class of non-strongly convex functions. Moreover, the worst-case convergence rate is comparable to the one obtained using a (generally non-implementable) optimal fixed-rate restart strategy. We show numerical results comparing the proposed algorithm with other restart schemes.