Lazifying Conditional Gradient Algorithms

By Gábor Braun, Sebastian Pokutta, Daniel Zink. 2016

59 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computational Mechanics, Management Science and Operations Research, Optimization & Training

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 Mechanics

In Management Science and Operations Research

In Optimization & Training

Citations in the corpus

Affine Invariant Analysis of Frank-Wolfe on Strongly Convex Sets (2020, background): “…2015b; Courty et al. 2016; Paty et al. 2019; Luise et al. 2019]; however, many open questions remain in designing such optimal algorithmic schemes ( e.g. [Braun et al. 2017; Kerdreux et al. 2018b; Braun et al. 2018; Cyrille W Combettes et al. 2020b; Carderera et al. 2020; Mortagy et al. 2020;…”
A unifying framework for the analysis of projection-free first-order methods under a sufficient slope condition (2020, background): “Different approaches to avoid computations of those solutions have been discussed in [12] , [11] for convex optimization over polytopes.”
Blended Conditional Gradients: the unconditioning of conditional gradients (2018, unknown): “Building on (Braun et al., 2017), BCG uses a “weak-separation oracle” to find a vertex of P for which the linear objective attains some fraction of the reduction in f promised by the LP oracle, typically by searching among the current set of active vertices.”
Walking in the Shadow: A New Perspective on Descent Directions for Constrained Minimization (2020, background): “In fact, many recent papers [10, 3, 37, 38, 20, 19, 39, 16, 40, 41] use a similar way of showing convergence by bounding the number of such ‘bad’ steps with dimension reduction arguments, which crucially rely on maintaining iterates as a convex combination of vertices.”
Second-order Conditional Gradients (2020, methodology): “…by FW ), the Away-Step and Pairwise-Step Conditional Gradients algorithms ( AFW and PFW ), the Lazy Away-Step Conditional Gradients algorithm (Braun et al., 2017) (AFW (L)), the aforementioned DICG algorithm, the Stochastic Variance-Reduced Conditional Gradients algorithm (Hazan & Luo, 2016)…”
Boosting Frank-Wolfe by Chasing Gradients (2020, background): “It could also be interesting to investigate how to make each oracle call cheaper via, e.g., lazification (Braun et al., 2017) or subsampling (Kerdreux et al., 2018).”
The Frank-Wolfe Algorithm: A Short Introduction (2023, unknown): “…(see, e.g., Freund et al. [35], Lacoste-Julien and Jaggi [53], Garber and Hazan [37, 38], Lan et al. [56], Braun et al. [12], Braun et al. [14], Braun et al. [13], Combettes and Pokutta [23], Tsuji et al. [78]) and there is an intricate connection between Frank-Wolfe methods and…”
Frank-Wolfe with Subsampling Oracle (2018, methodology): “A different technique to alleviate the cost of the linear oracle was recently proposed by Braun et al. (2017).”