  We propose new restarting strategies for accelerated gradient and accelerated
coordinate descent methods. Our main contribution is to show that the restarted
method has a geometric rate of convergence for any restarting frequency, and so
it allows us to take profit of restarting even when we do not know the strong
convexity coefficient. The scheme can be combined with adaptive restarting,
leading to the first provable convergence for adaptive restarting schemes with
accelerated gradient methods. Finally, we illustrate the properties of the
algorithm on a regularized logistic regression problem and on a Lasso problem.
