Structure-Adaptive Accelerated Coordinate Descent

Junqi Tang (1) , Mohammad Golbabaee (2) , Francis Bach (3, 4) , Mike E. Davies (1)

1 School of Engineering [Edinburgh]
2 University of Bath [Bath]
3 LIENS - Laboratoire d'informatique de l'école normale supérieure
4 SIERRA - Statistical Machine Learning and Parsimony

In this work we explore the fundamental structure-adaptiveness of accelerated randomized coordinate descent algorithms on regularized empirical risk minimization tasks, where the solution has intrinsic low-dimensional structure such as sparsity and low-rank, enforced by non-smooth regularization. We propose and analyze a two-stage accelerated coordinate descent algorithm ("two-stage APCG") utilizing the restricted strong-convexity framework. We provide the convergence analysis showing that the proposed method have a local accelerated linear convergence rate with respect to the low-dimensional structure of the solution. We also propose an adaptive variant of the two-stage APCG which does not need to foreknow the restricted strong convexity parameter beforehand, but estimates it on the fly. In our numerical experiments we test the proposed method on a number of machine learning datasets and demonstrate the effectiveness of our approach.

Domaines: Optimisation et contrôle [math.OC]; Apprentissage [cs.LG]

Junqi Tang, Mohammad Golbabaee, Francis Bach, Mike E. Davies. Structure-Adaptive Accelerated Coordinate Descent. 2018. ⟨hal-01889990v2⟩