On Matching Pursuit and Coordinate Descent

Two popular examples of first-order optimization methods over linear spaces are coordinate descent and matching pursuit algorithms, with their randomized variants. While the former targets the optimization by moving along coordinates, the latter considers a generalized notion of directions. Exploiting the connection between the two algorithms, we present a unified analysis of both, providing affine invariant sublinear O(1/t) rates on smooth objectives and linear convergence on strongly convex objectives. As a byproduct of our affine invariant analysis of matching pursuit, our rates for steepest coordinate descent are the tightest known. Furthermore, we show the first accelerated convergence rate O(1/t^2) for matching pursuit and steepest coordinate descent on convex objectives.

Published in:
ICML 2018 - Proceedings of the 35th International Conference on Machine Learning
Presented at:
ICML 2018 - 35th International Conference on Machine Learning
May 01 2018

Note: The status of this file is: Anyone

 Record created 2018-05-14, last modified 2020-04-20

Download fulltext

Rate this document:

Rate this document:
(Not yet reviewed)