Model identification and local linear convergence of coordinate descent

Abstract

For composite nonsmooth optimization problems, Forward-Backward algorithm achieves model identification (e.g. support identification for the Lasso) after a finite number of iterations, provided the objective function is regular enough. Results concerning coordinate descent are scarcer and model identification has only been shown for specific estimators, the support-vector machine for instance. In this work, we show that cyclic coordinate descent achieves model identification in finite time for a wide class of functions. In addition, we prove explicit local linear convergence rates for coordinate descent. Extensive experiments on various estimators and on real datasets demonstrate that these rates match well empirical results.

References in corpus (7)

• Scikit-learn: Machine Learning in Python
• Pathwise coordinate optimization
• A Primer on Coordinate Descent Algorithms
• Implicit differentiation of Lasso-type models for hyperparameter optimization
• Improved Iteration Complexity Bounds of Cyclic Block Coordinate Descent for Convex Problems
• Local Convergence Properties of SAGA/Prox-SVRG and Acceleration
• Dual Extrapolation for Sparse Generalized Linear Models

Cited by in corpus (2)

• Implicit differentiation for fast hyperparameter selection in non-smooth convex learning
• Anderson acceleration of coordinate descent