A Linearly Convergent Conditional Gradient Algorithm with Applications to Online and Stochastic Optimization

By Dan Garber, Elad Hazan. 2013

100 citations recorded by the source corpus.

Linear optimization is many times algorithmically simpler than non-linear convex optimization. Linear optimization over matroid polytopes, matching polytopes and path polytopes are example of problems for which we have simple and efficient combinatorial algorithms, but whose non-linear convex counterpart is harder and admits significantly less efficient algorithms. This motivates the computational model of convex optimization, including the offline, online and stochastic settings, using a linear optimization oracle. In this computational model we give several new results that improve over the previous state-of-the-art. Our main result is a novel conditional gradient algorithm for smooth and strongly convex optimization over polyhedral sets that performs only a single linear optimization step over the domain on each iteration and enjoys a linear convergence rate. This gives an exponential improvement in convergence rate over previous results. Based on this new conditional gradient algorithm we give the first algorithms for online convex optimization over polyhedral sets that perform only a single linear optimization step over the domain while having optimal regret guarantees, answering an open question of Kalai and Vempala, and Hazan and Kale. Our online algorithms also imply conditional gradient algorithms for non-smooth and stochastic convex optimization with the same convergence rates as projected (sub)gradient methods.

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

Barrier Frank-Wolfe for Marginal Inference (2015, methodology): “In a manner akin to barrier methods and to Garber and Hazan (2013)’s local linear oracle, our proposed solution maintains the iterates within a contraction of the polytope.”
Projection-Free Optimization on Uniformly Convex Sets (2020, background): “…mechanisms (Guélat and Marcotte, 1986; Hearn et al., 1987) that lead to linear convergence rates under appropriate structures of the objective function (Garber and Hazan, 2013a; Lacoste-Julien and Jaggi, 2013, 2015; Beck and Shtern, 2017; Gutman and Pena, 2018; Pena and Rodriguez, 2018).”
Linearly Convergent Frank-Wolfe with Backtracking Line-Search. (2018, background): “In the case of a polytope domain, it was recently shown to enjoy a linear convergence rate for strongly convex objectives (Garber and Hazan, 2013; Lacoste-Julien and Jaggi, 2015).”
Linearly convergent away-step conditional gradient for non-strongly convex functions (2015, methodology): “tances, and speciﬁcally for certain types of polyhedral sets, obtaining such a linear-oracle can be done more eﬃciently than computing the orthogonal projection onto the feasible set (see examples in [9]), and therefore the CG algorithm has an advantage over projection-based algorithms. The original”
Semi-Proximal Mirror-Prox for Nonsmooth Composite Minimization (2015, background): “(1)Related research extended such approaches to stochastic or online settings [10, 8, 15]; such settings are beyond the scope of this work.”
Complexity bounds for primal-dual methods minimizing the model of objective function (2017, background): “Motivation Inthelastyears,wecanseeanincreasinginteresttoFrank–Wolfealgorithm [2,3,12], which sometimes is called Conditional Gradient Method (CGM) [5,8–10].”
Blended Conditional Gradients: the unconditioning of conditional gradients (2018, unknown): “Linearly convergent variants of CG were studied as early as Guélat and Marcotte [1986] for special cases and Garber and Hazan [2013] for the general case (thoughthe latter work involvesvery large constants).”
Lazifying Conditional Gradient Algorithms (2016, methodology): “3 Lazy Local Conditional Gradients In this section we provide a lazy version (Algorithm3) of the conditional gradient algorithmfrom Garber and Hazan [2013]. Let P ⊆ Rn be any polytope, D denote an upper bound on the l2-diameter of P, and μ ≥ 1 be the affine invariant of P from Garber and Hazan [2013”
The Complexity of Large-scale Convex Programming under a Linear Optimization Oracle (2013, background): “Some discussions about strongly convex problems are included in Subsection 3.4.”
Frank-Wolfe with Subsampling Oracle (2018, background): “In the case of a polytope domain, it was recently shown to have much better convergence properties, such as linear (i.e. exponential) convergence rates for generally-strongly convex objectives (Garber & Hazan, 2013; Beck & Tetruashvili, 2013; Lacoste-Julien & Jaggi, 2015).”
Linear-Memory and Decomposition-Invariant Linearly Convergent Conditional Gradient Algorithm for Structured Polytopes (2016, background): “…positive semidefinite matrices, or the nuclear ball that are central to many machine learning problems, such as matrix completion, for which linear optimization amounts to computing the leading eigenvector or leading pair of singular vectors, whereas, algorithms for non-linear convex…”
Parallel and Distributed Block-Coordinate Frank-Wolfe Algorithms (2014, background): “Its wide applicability and practical appeal have spurred several extensions, including to regularized optimization [34, 6, 13], to linearly convergent algorithms [21, 12], to stochastic/online versions [28, 14], and to a powerful randomized blockcoordinate version [22].”