# Boosting Frank-Wolfe by Chasing Gradients

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Mar 2020.

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

- [Complexity of Linear Minimization and Projection on Some Sets](https://mlsanity.com/paper/2101.10040/) (2021)
- [On Constraints in First-Order Optimization: A View from Non-Smooth Dynamical Systems](https://mlsanity.com/paper/2107.08225/) (2021)
- [Accelerated First-Order Optimization under Nonlinear Constraints](https://mlsanity.com/paper/2302.00316/) (2023)
- [Sparse solutions of the kernel herding algorithm by improved gradient approximation](https://mlsanity.com/paper/2105.07900/) (2021)
- [Linearization Algorithms for Fully Composite Optimization](https://mlsanity.com/paper/2302.12808/) (2023)
- [Conditional Gradients for the Approximate Vanishing Ideal](https://mlsanity.com/paper/2202.03349/) (2022)
- [Scalable DC Optimization via Adaptive Frank-Wolfe Algorithms](https://mlsanity.com/paper/2507.17545/) (2025)
- [PACE: Prune-And-Compress Ensemble Models](https://mlsanity.com/paper/2605.06278/) (2026)
- [Approximate Frank-Wolfe Algorithms over Graph-structured Support Sets](https://mlsanity.com/paper/2107.00472/) (2021)
- [Guarded Block Transfers for Polytope Distance: Linear Convergence with Explicit Constants and Gap-Certified Screening for SVM Training](https://mlsanity.com/paper/2610.15829/) (2026)

## Abstract (arXiv)

The Frank-Wolfe algorithm has become a popular first-order optimization algorithm for it is simple and projection-free, and it has been successfully applied to a variety of real-world problems. Its main drawback however lies in its convergence rate, which can be excessively slow due to naive descent directions. We propose to speed up the Frank-Wolfe algorithm by better aligning the descent direction with that of the negative gradient via a subroutine. This subroutine chases the negative gradient direction in a matching pursuit-style while still preserving the projection-free property. Although the approach is reasonably natural, it produces very significant results. We derive convergence rates O(1/t) to O(e-ω t) of our method and we demonstrate its competitive advantage both per iteration and in CPU time over the state-of-the-art in a series of computational experiments.