New Analysis and Results for the Frank-Wolfe Method

Abstract

We present new results for the Frank-Wolfe method (also known as the conditional gradient 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 FW gaps. Lastly, we present complexity bounds in the presence of approximate computation of gradients and/or linear optimization subproblem solutions.

Changed the name of the method from "conditional gradient" to "Frank-Wolfe"

Cited by in corpus (3)

• A Frank-Wolfe Based Branch-and-Bound Algorithm for Mean-Risk Optimization
• Filtering with State-Observation Examples via Kernel Monte Carlo Filter
• A Scalable Frank-Wolfe based Augmented Lagrangian Method for Linearly Constrained Composite Convex Programming