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 $\mathcal{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 $\mathcal{O}(1/t^2)$ for matching pursuit
and steepest coordinate descent on convex objectives.
