  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.
