New Analysis and Results for the Conditional Gradient Method
Robert M. Freund, Paul Grigas · 2013
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 av-eraging and constant step-sizes. We also develop step-size rules and complexity bounds that depend naturally on the warm-start quality of the initial (and sub-sequent) iterates. Our results include complexity bounds for optimality bound gap and the Wolfe gap. Lastly, we present complexity bounds in the presence of approximate computation of gradients and/or linear optimization subproblem solutions. The results herein are mostly a condensation of the paper [1]. 1