Restarting accelerated gradient methods with a rough strong convexity estimate

Abstract

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.

References in corpus (1)

• Smooth minimization of nonsmooth functions with parallel coordinate descent methods

Cited by in corpus (10)

• Adaptive restart of accelerated gradient methods under local quadratic growth condition
• Optimal Algorithms for Distributed Optimization
• Adaptive Accelerated Gradient Converging Methods under Holderian Error Bound Condition
• Online Regularized Nonlinear Acceleration
• An accelerated randomized Bregman-Kaczmarz method for strongly convex linearly constraint optimization
• Complexity Guarantees for Polyak Steps with Momentum
• Generalized Framework for Nonlinear Acceleration
• A New Primal-Dual Algorithm for a Class of Nonlinear Compositional Convex Optimization Problems
• Generalized Self-Concordant Functions: A Recipe for Newton-Type Methods
• Proximal Gradient Algorithm with Momentum and Flexible Parameter Restart for Nonconvex Optimization