On Matching Pursuit and Coordinate Descent
This work addresses optimization challenges for researchers and practitioners in machine learning and numerical computing, offering improved theoretical guarantees for widely used algorithms, though it is incremental in refining existing methods.
The paper tackles the problem of analyzing first-order optimization methods by providing a unified analysis of coordinate descent and matching pursuit algorithms, achieving affine invariant sublinear O(1/t) rates on smooth objectives and linear convergence on strongly convex objectives, with the tightest known rates for steepest coordinate descent and the first accelerated O(1/t^2) rate for matching pursuit and steepest coordinate descent on convex objectives.
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.