# Heavy Ball Momentum for Conditional Gradient

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 39 references that are in the map.
- First posted on arXiv 8 Oct 2021.

## Builds on (most cited first, 16 of 16)

- [On the Global Linear Convergence of Frank-Wolfe Optimization Variants](https://mlsanity.com/paper/1511.05932/) (2015)
- [Good Subnetworks Provably Exist: Pruning via Greedy Forward Selection](https://mlsanity.com/paper/2003.01794/) (2020)
- [Global convergence of the Heavy-ball method for convex optimization](https://mlsanity.com/paper/1412.7457/) (2014)
- [Stochastic Conditional Gradient Methods: From Convex Minimization to Submodular Maximization](https://mlsanity.com/paper/1804.09554/) (2018)
- [Faster Rates for the Frank-Wolfe Method over Strongly-Convex Sets](https://mlsanity.com/paper/1406.1305/) (2014)
- [One Sample Stochastic Frank-Wolfe](https://mlsanity.com/paper/1910.04322/) (2019)
- [The Complexity of Large-scale Convex Programming under a Linear Optimization Oracle](https://mlsanity.com/paper/1309.5550/) (2013)
- [The Approximate Duality Gap Technique: A Unified Theory of First-Order Methods](https://mlsanity.com/paper/1712.02485/) (2017)
- [Sinkhorn Barycenters with Free Support via Frank-Wolfe Algorithm](https://mlsanity.com/paper/1905.13194/) (2019)
- [Sequential Kernel Herding: Frank-Wolfe Optimization for Particle Filtering](https://mlsanity.com/paper/1501.02056/) (2015)
- [New Analysis and Results for the Frank-Wolfe Method](https://mlsanity.com/paper/1307.0873/) (2013)
- [An Extended Frank-Wolfe Method with "In-Face" Directions, and its Application to Low-Rank Matrix Completion](https://mlsanity.com/paper/1511.02204/) (2015)
- [Linear Convergence of a Frank-Wolfe Type Algorithm over Trace-Norm Balls](https://mlsanity.com/paper/1708.02105/) (2017)
- [Conditional Gradient Algorithms for Norm-Regularized Smooth Convex Optimization](https://mlsanity.com/paper/1302.2325/) (2013)
- [Memory-Efficient Convex Optimization for Self-Dictionary Separable Nonnegative Matrix Factorization: A Frank-Wolfe Approach](https://mlsanity.com/paper/2109.11135/) (2021)
- [Randomized Block Frank-Wolfe for Convergent Large-Scale Learning](https://mlsanity.com/paper/1612.08461/) (2016)

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

- [Lions and Muons: Optimization via Stochastic Frank-Wolfe under Heavy-Tailed Noise](https://mlsanity.com/paper/2506.04192/) (2025)
- [Enhancing Sharpness-Aware Optimization Through Variance Suppression](https://mlsanity.com/paper/2309.15639/) (2023)
- [Scaling Up Differentially Private LASSO Regularized Logistic Regression via Faster Frank-Wolfe Iterations](https://mlsanity.com/paper/2310.19978/) (2023)
- [Provable Benefit of SignGD: A Minimal Model Under Heavy-Tailed Class Imbalance](https://mlsanity.com/paper/2512.00763/) (2025)
- [VASSO: Variance Suppression for Sharpness-Aware Minimization](https://mlsanity.com/paper/2509.02433/) (2025)
- [Adaptive Lipschitz-Free Conditional Gradient Methods for Stochastic Composite Nonconvex Optimization](https://mlsanity.com/paper/2603.06369/) (2026)
- [Conic Descent Redux for Memory-Efficient Optimization](https://mlsanity.com/paper/2308.07343/) (2023)

## Abstract (arXiv)

Conditional gradient, aka Frank Wolfe (FW) algorithms, have well-documented merits in machine learning and signal processing applications. Unlike projection-based methods, momentum cannot improve the convergence rate of FW, in general. This limitation motivates the present work, which deals with heavy ball momentum, and its impact to FW. Specifically, it is established that heavy ball offers a unifying perspective on the primal-dual (PD) convergence, and enjoys a tighter per iteration PD error rate, for multiple choices of step sizes, where PD error can serve as the stopping criterion in practice. In addition, it is asserted that restart, a scheme typically employed jointly with Nesterov's momentum, can further tighten this PD error bound. Numerical results demonstrate the usefulness of heavy ball momentum in FW iterations.