An Affine Invariant Linear Convergence Analysis for Frank-Wolfe Algorithms

By Simon Lacoste-Julien, Martin Jaggi. 2013

76 citations recorded by the source corpus.

We study the linear convergence of variants of the Frank-Wolfe algorithms for some classes of strongly convex problems, using only affine-invariant quantities. As in Guelat & Marcotte (1986), we show the linear convergence of the standard Frank-Wolfe algorithm when the solution is in the interior of the domain, but with affine invariant constants. We also show the linear convergence of the away-steps variant of the Frank-Wolfe algorithm, but with constants which only depend on the geometry of the domain, and not any property of the location of the optimal solution. Running these algorithms does not require knowing any problem specific parameters.

Subfields: Artificial Intelligence, Computational Mechanics, Computational Theory and Mathematics, 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 Computational Theory and Mathematics

In Optimization & Training

Citations in the corpus

Frank-Wolfe Algorithms for Saddle Point Problems (2016, methodology): “If we assume that X and Y are the convex hulls of two finite sets of pointsA and B, we can also extend the awaystep Frank-Wolfe (AFW) algorithm (Guélat and Marcotte, 1986; Lacoste-Julien and Jaggi, 2015) to saddle point problems. As for AFW, this new algorithm can choose an away direction dA to remo”
Towards Practical Differentially Private Convex Optimization (2019, background): “The Frank-Wolfe algorithm [25] has also seen a resurgence lately [26], [27], [28], [29].”
A Linearly Convergent Conditional Gradient Algorithm with Applications to Online and Stochastic Optimization (2013, unknown): “After our work first appeared [11], Jaggi and Lacoste-Julien [24] presented a refined analysis of a variant of the conditional gradient algorithm with away steps from [12] that achieves a linear convergence rate without the assumption on the location of the optimum as in the original work of [12].”
Frank-Wolfe with Subsampling Oracle (2018, background): “This approach has proven to be highly successful on specific problems such as structured SVMs (Lacoste-Julien et al., 2013) and l1-constrained regression (Frandi et al.”
A Distributed Frank-Wolfe Algorithm for Communication-Efficient Sparse Learning (2014, background): “(3)Note that the dependency on can be improved to O(n log(1/ )) for strongly convex functions by using so-called away-steps (see for instance (Lacoste-Julien and Jaggi, 2013)).”
Linearly convergent away-step conditional gradient for non-strongly convex functions (2015, methodology): “In this work, our starting point and main motivation are the results of Jaggi and Lacoste-Julien [16].”
Efficient Image and Video Co-localization with Frank-Wolfe Algorithm (2014, background): “This version of Frank-Wolfe has been shown to have better convergence rates [18, 25].”
Linear-Memory and Decomposition-Invariant Linearly Convergent Conditional Gradient Algorithm for Structured Polytopes (2016, background): “Our theoretical findings are complemented by empirical evidence which shows that our method delivers state-of-the-art performance.”
The Cyclic Block Conditional Gradient Method for Convex Optimization Problems (2015, background): “CG is known to converge linearly when the optimum is in the relative interior of the feasible set [15, 20] or when the feasible set is strongly convex and the gradient of the smooth part of the objective is non-zero on the feasible set [21].”
Frank-Wolfe Method is Automatically Adaptive to Error Bound Condition (2018, methodology): “…of the FW method and its variants (Levitin and Polyak, 1966; Demyanov and Rubinov, 1970; Dunn, 1979; Gu´elat and Marcotte, 1986; Beck and Teboulle, 2004; Garber and Hazan, 2013; Lan, 2013; Lacoste-Julien and Jaggi, 2013; Garber and Hazan, 2015; Lacoste-Julien and Jaggi, 2015; Lan and Zhou, 2016).”
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].”
Projection-Free Optimization on Uniformly Convex Sets (2020, methodology): “…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).”