Heavy Ball Momentum for Conditional Gradient
arXiv:2110.04243
Abstract
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.
arXiv commentAccepted to NeurIPS 2021
References in corpus (5)
- Faster Rates for the Frank-Wolfe Method over Strongly-Convex Sets
- The Complexity of Large-scale Convex Programming under a Linear Optimization Oracle
- The Approximate Duality Gap Technique: A Unified Theory of First-Order Methods
- Randomized Block Frank-Wolfe for Convergent Large-Scale Learning
- Memory-Efficient Convex Optimization for Self-Dictionary Separable Nonnegative Matrix Factorization: A Frank-Wolfe Approach