On Matching Pursuit and Coordinate Descent

Understand

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.