New analysis and results for the Frank–Wolfe method

By Robert M. Freund, Paul Grigas. 2013

160 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Numerical Analysis, Mathematical Optimization

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

In Numerical Analysis

In Mathematical Optimization

Citations in the corpus

Sequential Kernel Herding: Frank-Wolfe Optimization for Particle Filtering (2015, background): “This translates to a slower O(1/ √ k) rate on ‖gk − µp‖ (with √ δ precision), but note that at least it does not have the log(k) factor from the rate by Freund and Grigas (2013).”
Filtering with State-Observation Examples via Kernel Monte Carlo Filter (2013, methodology): “h et al., 2012) that Kernel Herding can be seen as the Frank-Wolfe optimization method with step size 1=(‘+ 1) for the ‘-th iteration. For details of the Frank-Wolfe method, we refer to Jaggi (2013); Freund and Grigas (2014) and references therein. Fix the samples Z 1;:::;Z N. Let M Nbe the convex h”
A Lyapunov Analysis of Momentum Methods in Optimization (2016, methodology): “This interest has inspired several different analyses [10, 1] of the algorithm.”
Frank-Wolfe Method is Automatically Adaptive to Error Bound Condition (2018, methodology): “In recent years, the FW method has gained an increasing interest in large-scale optimization and machine learning (e.g., (Garber and Hazan, 2015; Freund and Grigas, 2016; Nesterov, 2018; Narasimhan, 2018)).”
The Complexity of Large-scale Convex Programming under a Linear Optimization Oracle (2013, background): “(1.12) Clearly, if f satisﬁes (1.5), then (1.13) Notice that the constant L in (1.5) and (1.13) depends on · .”
Parallel and Distributed Block-Coordinate Frank-Wolfe Algorithms (2014, methodology): “To add perspective, we compare our methods to closely related works below; we refer the reader to Freund & Grigas (2014); Jaggi (2013); Lacoste-Julien et al. (2013); Zhang et al. (2012) for additional notes and references.”
Blended Conditional Gradients: the unconditioning of conditional gradients (2018, unknown): “Related work There has been an extensive body of work on conditional gradient algorithms; see the excellent overview of Jaggi [2013]. Here we review only those papers most closely related to our work.”
Generalized conditional subgradient and generalized mirror descent: duality, convergence, and symmetry (2019, methodology): “3 Traditional conditional gradient context Assumption 1 and Assumption 2 readily hold in the usual set up of the conditional gradient algorithm [11, 15].”
A Distributed Frank-Wolfe Algorithm for Communication-Efficient Sparse Learning (2014, methodology): “Then the first claim follows from the analysis of Freund and Grigas (2013).”