Linear-Memory and Decomposition-Invariant Linearly Convergent Conditional Gradient Algorithm for Structured Polytopes

By Dan Garber, Ofer Meshi. 2016

58 citations recorded by the source corpus.

Recently, several works have shown that natural modifications of the classical conditional gradient method (aka Frank-Wolfe algorithm) for constrained convex optimization, provably converge with a linear rate when: i) the feasible set is a polytope, and ii) the objective is smooth and strongly-convex. However, all of these results suffer from two significant shortcomings: large memory requirement due to the need to store an explicit convex decomposition of the current iterate, and as a consequence, large running-time overhead per iteration, and worst case convergence rate that depends unfavorably on the dimension. In this work we present a new conditional gradient variant and a corresponding analysis that improves on both of the above shortcomings. In particular: both memory and computation overheads are only linear in the dimension. Moreover, in case the optimal solution is sparse, the new convergence rate replaces a factor which is at least linear in the dimension in previous works, with a linear dependence on the number of non-zeros in the optimal solution. At the heart of our method, and corresponding analysis, is a novel way to compute decomposition-invariant away-steps. While our theoretical guarantees do not apply to any polytope, they apply to several important structured polytopes that capture central concepts such as paths in graphs, perfect matchings in bipartite graphs, marginal distributions that arise in structured prediction tasks, and more. Our theoretical findings are complemented by empirical evidence which shows that our method delivers state-of-the-art performance.

Subfields: Computational Theory and Mathematics, Computer Graphics and Computer-Aided Design, 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 Computational Theory and Mathematics

In Computer Graphics and Computer-Aided Design

In Numerical Analysis

In Optimization & Training

Citations in the corpus

Frank-Wolfe Splitting via Augmented Lagrangian Method (2018, methodology): “On the other hand, if X is a polytope and f a generalized strongly convex function, recent advances on FW proposed global linear convergence rates using FW with away steps (Lacoste-Julien and Jaggi, 2015; Garber and Meshi, 2016).”
SparseMAP: Differentiable Sparse Structured Inference (2018, background): “More sophisticated variants have been proposed (Garber & Meshi, 2016) which can provide sparse solutions when optimizing over a polytope.”
Second-order Conditional Gradients (2020, methodology): “Figure 1 shows the performance of Algorithm 1 when the DICG algorithm (Garber & Meshi, 2016) is used, and the matrix exact hessian is used, i.e., H k = ∇ 2 f ( x k ) (denoted by SOCG DICG ), and also when an L-BFGS and BFGS method is used to generate H k (denoted by SOCG DICG (L-BFGS) and SOCG DICG…”
Blended Conditional Gradients: the unconditioning of conditional gradients (2018, unknown): “Tocompareourexperimentstopreviouswork,weusedproblemsandinstancessimilartothoseinLacoste-Julien and Jaggi [2015], Garber and Meshi [2016], Rao et al. [2015], Braun et al. [2017], Lan et al. [2017].”
Walking in the Shadow: A New Perspective on Descent Directions for Constrained Minimization (2020, background): “In 2016, Garber and Meshi [16] showed that pairwise-steps (over 0/1 polytopes) with respect to non-zero components of the gradient are enough for linear convergence, i.”
Boosting Frank-Wolfe by Chasing Gradients (2020, methodology): “Lastly, note that BoostFW does not need to maintain the decomposition of the iterates, which is very favorable in practice (Garber & Meshi, 2016).”
Compiling Combinatorial Prediction Games (2018, methodology): “…we used for η and γ the values determined by our theoretical analysis; the step-sizes {ηt} of PCG were computed from binary search as advocated by Garber & Meshi (2016) in their experiments, and the value of δ was fixed to 1/ln d in order to keep a quadratic runtime complexity for…”
Lazifying Conditional Gradient Algorithms (2016, methodology): “We exemplify our approach by providing lazy versions of the vanilla Frank-Wolfe algorithm as well as of the conditional gradient methods in [Hazan and Kale, 2012, Garber and Hazan, 2013, Garber and Meshi, 2016].”