Restarting the accelerated coordinate descent method with a rough strong convexity estimate
Preprint
Abstract
We propose new restarting strategies for the accelerated coordinate descent method. Our main contribution is to show that for a well chosen sequence of restarting times, the restarted method has a nearly geometric rate of convergence. A major feature of the method is that it can take profit of the local quadratic error bound of the objective function without knowing the actual value of the error bound. We also show that under the more restrictive assumption that the objective function is strongly convex, any fixed restart period leads to a geometric rate of convergence. Finally, we illustrate the properties of the algorithm on a regularized logistic regression problem and on a Lasso problem.Keywords
All Related Versions
This publication has 7 references indexed in Scilit:
- Adaptive restart of accelerated gradient methods under local quadratic growth conditionIMA Journal of Numerical Analysis, 2019
- Smooth Minimization of Nonsmooth Functions with Parallel Coordinate Descent Methods2019
- Coordinate descent with arbitrary sampling II: expected separable overapproximationOptimization Methods and Software, 2016
- Parallel coordinate descent methods for big data optimizationMathematical Programming, 2015
- Accelerated, Parallel, and Proximal Coordinate DescentSIAM Journal on Optimization, 2015
- An adaptive accelerated proximal gradient method and its homotopy continuation for sparse optimizationComputational Optimization and Applications, 2014
- Iteration complexity of randomized block-coordinate descent methods for minimizing a composite functionMathematical Programming, 2012