# On Matching Pursuit and Coordinate Descent

arXiv: https://arxiv.org/abs/1803.09539 · HTML: https://mlsanity.com/paper/1803.09539/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 Mar 2018.

## Built on by (most cited first, 7 of 7)

- [ASIF: Coupled Data Turns Unimodal Models to Multimodal Without Training](https://mlsanity.com/paper/2210.01738/) (2022)
- [Robust Gaussian Processes via Relevance Pursuit](https://mlsanity.com/paper/2410.24222/) (2024)
- [Sparse Bayesian Learning via Stepwise Regression](https://mlsanity.com/paper/2106.06095/) (2021)
- [Glocal Smoothness: Line search and adaptive step sizes can help in theory too!](https://mlsanity.com/paper/2506.12648/) (2025)
- [Dynamic Scoring with Enhanced Semantics for Training-Free Human-Object Interaction Detection](https://mlsanity.com/paper/2507.17456/) (2025)
- [Adaptive Conditional Gradient Descent](https://mlsanity.com/paper/2510.11440/) (2025)
- [Approximate Frank-Wolfe Algorithms over Graph-structured Support Sets](https://mlsanity.com/paper/2107.00472/) (2021)

## Abstract (arXiv)

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/t2) for matching pursuit and steepest coordinate descent on convex objectives.