On the Global Linear Convergence of Frank-Wolfe Optimization Variants

By Simon Lacoste-Julien, Martin Jaggi. 2015

450 citations recorded by the source corpus.

The Frank-Wolfe (FW) optimization algorithm has lately re-gained popularity thanks in particular to its ability to nicely handle the structured constraints appearing in machine learning applications. However, its convergence rate is known to be slow (sublinear) when the solution lies at the boundary. A simple less-known fix is to add the possibility to take 'away steps' during optimization, an operation that importantly does not require a feasibility oracle. In this paper, we highlight and clarify several variants of the Frank-Wolfe optimization algorithm that have been successfully applied in practice: away-steps FW, pairwise FW, fully-corrective FW and Wolfe's minimum norm point algorithm, and prove for the first time that they all enjoy global linear convergence, under a weaker condition than strong convexity of the objective. The constant in the convergence rate has an elegant interpretation as the product of the (classical) condition number of the function with a novel geometric quantity that plays the role of a 'condition number' of the constraint set. We provide pointers to where these algorithms have made a difference in practice, in particular with the flow polytope, the marginal polytope and the base polytope for submodular optimization.

Subfields: Artificial Intelligence, Computational Mechanics, 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 Optimization & Training

Citations in the corpus

Affine Invariant Analysis of Frank-Wolfe on Strongly Convex Sets (2020, background): “For instance, corrective variants of Frank-Wolfe exhibit (affine invariant) linear convergence rates when the constraint set is a polytope [24, 25] and the objective function is (generally) strongly convex.”
Frank-Wolfe Splitting via Augmented Lagrangian Method (2018, methodology): “Algorithm 1 Away-step Frank-Wolfe (one non-drop step) : (Lacoste-Julien and Jaggi, 2015)”
Joint Discovery of Object States and Manipulation Actions (2017, background): “When dealing with a constrained optimization problem for which it is easy to solve linear programs but difficult to project on the feasible set, the Frank-Wolfe algorithm is an excellent choice [23, 29].”
Frank-Wolfe Algorithms for Saddle Point Problems (2016, methodology): “Finally, a straightforward saddle point generalization for the pairwise Frank-Wolfe (PFW) algorithm (Lacoste-Julien and Jaggi, 2015) is given in Alg.”
Minding the Gaps for Block Frank-Wolfe Optimization of Structured SVMs (2016, methodology): “Lacoste-Julien & Jaggi (2015) showed that the largest possible pyramidal width of a polytope in dimension m (for a fixed diameter) is achieved by the probability simplex and is Θ(1/ √ m).”
Barrier Frank-Wolfe for Marginal Inference (2015, methodology): “…FW direction) 12: else 13: dk := dAk , and γmax := αvk (1−αvk ) (choose away direction; maximum feasible step-size) 14: end if 15: Line-search: γk ∈ arg min γ∈[0,γmax] f ( x(k) + γdk ) 16: Update x(k+1) := x(k) + γkdk 17: Update coordinates α(k+1) accordingly (see Lacoste-Julien and Jaggi (2015)).”
Unsupervised Learning from Narrated Instruction Videos (2015, background): “In contrast, we show in the appendix of the paper [2] that the multiple sequence alignment problem given by (1) can be reformulated as an integer quadratic program with combinatorial constraints, for which the FrankWolfe optimization algorithm has been used recently with increasing success [5, 14, 1”
Towards Practical Differentially Private Convex Optimization (2019, background): “The Frank-Wolfe algorithm [25] has also seen a resurgence lately [26], [27], [28], [29].”
Automated Scalable Bayesian Inference via Hilbert Coresets (2017, methodology): “…investigating different choices of weighting function, obtaining tighter bounds on the quality of the random projection result, and using variants of the Frank–Wolfe algorithm (e.g. away-step, pairwise, and fully-corrective FW (Lacoste-Julien and Jaggi, 2015)) with stronger convergence guarantees.”
The Frank-Wolfe Algorithm: A Short Introduction (2023, unknown): “…of modiﬁcations to these methods, addressing many of their historical limitations (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.…”
Greedy Direction Method of Multiplier for MAP Inference of Large Output Domain (2017, methodology): “Theorem 1 and 2 are based on the analysis framework of [22] for the Augmented Lagrangian Method, as well as the recent results on the linear convergence of Frank-Wolfe variants [23] and Greedy Coordinate Descent for non-strongly convex functions of the form (13) [24, 25].”
Parallel and Distributed Block-Coordinate Frank-Wolfe Algorithms (2014, background): “, regularized FW [6, 17, 41], linearly convergent special cases [16, 23], stochastic/online versions [18, 25, 34], and a randomized block-coordinate FW [24].”
Stochastic Frank-Wolfe methods for nonconvex optimization (2016, background): “There have been several recent works on improving the convergence rates under additional assumptions [7], [16].”
Linear-Memory and Decomposition-Invariant Linearly Convergent Conditional Gradient Algorithm for Structured Polytopes (2016, methodology): “In a later work, Lacoste-Julien and Jaggi [16] gave a refined affine-invariant analysis of an algorithm presented in [9] which also uses away steps, and showed that it also converges exponentially fast in the same setting as the Garber-Hazan result.”
Blended Conditional Gradients: the unconditioning of conditional gradients (2018, methodology): “[Lacoste-Julien and Jaggi, 2015, Theorem 6 and Eq.”
Fast Cluster Detection in Networks by First Order Optimization (2021, background): “, [12], [19], [23], [21] and references therein) thanks to their sparse approximation properties, their weaker requirement of a linear minimization oracle instead of a projection oracle with respect to proximal gradient like methods, and their ability to quickly identify the support of a solution.”
Frank-Wolfe with Subsampling Oracle (2018, methodology): “The proof simply adapts that of (Lacoste-Julien & Jaggi, 2015, Th. 11) to our setting.”
Compiling Combinatorial Prediction Games (2018, methodology): “…step can be approximated in low polynomial time, by exploiting the Pairwise Conditional Gradient (PCG) method, a variant of the Frank-Wolfe convex optimization algorithm, whose convergence rate has been analyzed in (Lacoste-Julien & Jaggi, 2015; Garber & Meshi, 2016; Bashiri & Zhang, 2017).”