Blended Conditional Gradients: the unconditioning of conditional gradients

By Gábor Braun, Sebastian Pokutta, Dan Tu, Stephen J. Wright. 2018

31 citations recorded by the source corpus.

We present a blended conditional gradient approach for minimizing a smooth convex function over a polytope P, combining the Frank--Wolfe algorithm (also called conditional gradient) with gradient-based steps, different from away steps and pairwise steps, but still achieving linear convergence for strongly convex functions, along with good practical performance. Our approach retains all favorable properties of conditional gradient algorithms, notably avoidance of projections onto P and maintenance of iterates as sparse convex combinations of a limited number of extreme points of P. The algorithm is lazy, making use of inexpensive inexact solutions of the linear programming subproblem that characterizes the conditional gradient approach. It decreases measures of optimality (primal and dual gaps) rapidly, both in the number of iterations and in wall-clock time, outperforming even the lazy conditional gradient algorithms of [arXiv:1410.8816]. We also present a streamlined version of the algorithm for the probability simplex.

Subfields: Artificial Intelligence, Computational Mechanics, Numerical Analysis, 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 Numerical Analysis

In Optimization & Training

Citations in the corpus

Affine Invariant Analysis of Frank-Wolfe on Strongly Convex Sets (2020, background): “…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; Cyrille W. Combettes et al. 2020a]) and in their…”
Boosting Frank-Wolfe by Chasing Gradients (2020, methodology): “(i) O(e−ωt) when f is strongly convex and C is a polytope (Garber & Hazan, 2016; Lacoste-Julien & Jaggi, 2015; Braun et al., 2019), (ii) O(e−ωt) with constants depending on the sparsity of the solution when f is strongly convex and C is a polytope, of the form {x ∈ R | Ax = b, x > 0} with vertices i”
The condition number of a function relative to a set (2019, result): “We discuss only the linear convergence of Algorithm 2 but the same techniques yield similar results for other variants of the Frank-Wolfe algorithm as those discussed in [18] or the one recently developed in [3].”
The Frank-Wolfe Algorithm: A Short Introduction (2023, unknown): “…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 subgradients methods (Bach…”