Restarting accelerated gradient methods with a rough strong convexity estimate

Understand

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.