Lazifying Conditional Gradient Algorithms
arXiv:1610.05120
Abstract
Conditional gradient algorithms (also often called Frank-Wolfe algorithms) are popular due to their simplicity of only requiring a linear optimization oracle and more recently they also gained significant traction for online learning. While simple in principle, in many cases the actual implementation of the linear optimization oracle is costly. We show a general method to lazify various conditional gradient algorithms, which in actual computations leads to several orders of magnitude of speedup in wall-clock time. This is achieved by using a faster separation oracle instead of a linear optimization oracle, relying only on few linear optimization oracle calls.
25 pages and 31 pages of computational results
References in corpus (5)
- On the Global Linear Convergence of Frank-Wolfe Optimization Variants
- Block-Coordinate Frank-Wolfe Optimization for Structural SVMs
- Minding the Gaps for Block Frank-Wolfe Optimization of Structured SVMs
- Solving Combinatorial Games using Products, Projections and Lexicographically Optimal Bases
- A Multi-Plane Block-Coordinate Frank-Wolfe Algorithm for Training Structural SVMs with a Costly max-Oracle