Model identification and local linear convergence of coordinate descent
This work addresses the theoretical gap in model identification for coordinate descent methods, which is incremental as it extends known results to a broader class of functions.
The paper tackled the problem of model identification and local linear convergence for cyclic coordinate descent in composite nonsmooth optimization, showing that it achieves model identification in finite time and proving explicit local linear convergence rates, with experiments confirming these rates match empirical results on real datasets.
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.