# A Unified Optimization View on Generalized Matching Pursuit and Frank-Wolfe

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

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 21 Feb 2017.

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

- [ASIF: Coupled Data Turns Unimodal Models to Multimodal Without Training](https://mlsanity.com/paper/2210.01738/) (2022)
- [Breaking the Linear Iteration Cost Barrier for Some Well-known Conditional Gradient Methods Using MaxIP Data-structures](https://mlsanity.com/paper/2111.15139/) (2021)
- [Regularized Frank-Wolfe for Dense CRFs: Generalizing Mean Field and Beyond](https://mlsanity.com/paper/2110.14759/) (2021)
- [Efficient Numerical Integration in Reproducing Kernel Hilbert Spaces via Leverage Scores Sampling](https://mlsanity.com/paper/2311.13548/) (2023)
- [Robust Gaussian Processes via Relevance Pursuit](https://mlsanity.com/paper/2410.24222/) (2024)
- [A Stochastic Bundle Method for Interpolating Networks](https://mlsanity.com/paper/2201.12678/) (2022)
- [Faster Maximum Inner Product Search in High Dimensions](https://mlsanity.com/paper/2212.07551/) (2022)
- [Adaptive Conditional Gradient Descent](https://mlsanity.com/paper/2510.11440/) (2025)
- [Boosting Variational Inference With Locally Adaptive Step-Sizes](https://mlsanity.com/paper/2105.09240/) (2021)
- [Approximate Frank-Wolfe Algorithms over Graph-structured Support Sets](https://mlsanity.com/paper/2107.00472/) (2021)
- [Lloyd's K-Means Clustering Algorithm Is Frank-Wolfe in Disguise](https://mlsanity.com/paper/2607.25190/) (2026)
- [Self-Supervised Combinatorial Optimization with Constraints via Frank-Wolfe](https://mlsanity.com/paper/2609.25728/) (2026)
- [Recall What Is Missing: Composing Evidence from Long-Term Agent Memory](https://mlsanity.com/paper/2610.15642/) (2026)

## Abstract (arXiv)

Two of the most fundamental prototypes of greedy optimization are the matching pursuit and Frank-Wolfe algorithms. In this paper, we take a unified view on both classes of methods, leading to the first explicit convergence rates of matching pursuit methods in an optimization sense, for general sets of atoms. We derive sublinear (1/t) convergence for both classes on general smooth objectives, and linear convergence on strongly convex objectives, as well as a clear correspondence of algorithm variants. Our presented algorithms and rates are affine invariant, and do not need any incoherence or sparsity assumptions.