How Does Momentum Help Frank Wolfe?

Abstract

We unveil the connections between Frank Wolfe (FW) type algorithms and the momentum in Accelerated Gradient Methods (AGM). On the negative side, these connections illustrate why momentum is unlikely to be effective for FW type algorithms. The encouraging message behind this link, on the other hand, is that momentum is useful for FW on a class of problems. In particular, we prove that a momentum variant of FW, that we term accelerated Frank Wolfe (AFW), converges with a faster rate $\tilde{\mathcal{O}}(\frac{1}{k^2})$ on certain constraint sets despite the same $\mathcal{O}(\frac{1}{k})$ rate as FW on general cases. Given the possible acceleration of AFW at almost no extra cost, it is thus a competitive alternative to FW. Numerical experiments on benchmarked machine learning tasks further validate our theoretical findings.

References in corpus (10)

• A Differential Equation for Modeling Nesterov's Accelerated Gradient Method: Theory and Insights
• A Universal Catalyst for First-Order Optimization
• Even Faster Accelerated Coordinate Descent Using Non-Uniform Sampling
• Faster Rates for the Frank-Wolfe Method over Strongly-Convex Sets
• The Complexity of Large-scale Convex Programming under a Linear Optimization Oracle
• Estimate Sequences for Variance-Reduced Stochastic Composite Optimization
• Blended Conditional Gradients: the unconditioning of conditional gradients
• Linearly Convergent Frank-Wolfe with Backtracking Line-Search
• On the Effectiveness of Richardson Extrapolation in Machine Learning
• Boosting Frank-Wolfe by Chasing Gradients