New Analysis and Results for the Conditional Gradient Method
Preprint
Abstract
We present new results for the conditional gradient method (also known as the Frank-Wolfe method). We derive computational guarantees for arbitrary step-size sequences, which are then applied to various step-size rules, including simple averaging and constant step-sizes. We also develop step-size rules and computational guarantees that depend naturally on the warm-start quality of the initial (and subsequent) iterates. Our results include computational guarantees for both duality/bound gaps and the so-called Wolfe gaps. Lastly, we present complexity bounds in the presence of approximate computation of gradients and/or linear optimization subproblem solutions.Keywords
All Related Versions
This publication has 6 references indexed in Scilit:
- Conditional gradient algorithms for norm-regularized smooth convex optimizationMathematical Programming, 2014
- First-order methods of smooth convex optimization with inexact oracleMathematical Programming, 2013
- Primal-dual subgradient methods for convex problemsMathematical Programming, 2007
- Smooth minimization of non-smooth functionsMathematical Programming, 2004
- Rounding of Polytopes in the Real Number Model of ComputationMathematics of Operations Research, 1996
- Sparse Convex Optimization Methods for Machine Learning