Restarting the accelerated coordinate descent method with a rough strong convexity estimate

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.

Document type :
Journal articles
Complete list of metadatas

https://hal.telecom-paristech.fr/hal-02287842
Contributor : Telecomparis Hal <>
Submitted on : Friday, September 13, 2019 - 5:25:07 PM
Last modification on : Thursday, October 17, 2019 - 12:37:03 PM

Identifiers

  • HAL Id : hal-02287842, version 1

Citation

Olivier Fercoq, Zheng Qu. Restarting the accelerated coordinate descent method with a rough strong convexity estimate. Computational Optimization and Applications, 2018. ⟨hal-02287842⟩

Share

Metrics

Record views

5