On the Global Linear Convergence of Frank-Wolfe Optimization Variants
arXiv:1511.05932
Abstract
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.
Appears in: Advances in Neural Information Processing Systems 28 (NIPS 2015). 26 pages
References in corpus (3)
Cited by in corpus (41)
- Convergence Rate of Frank-Wolfe for Non-Convex Objectives
- Binary Quadratic Programing for Online Tracking of Hundreds of People in Extremely Crowded Scenes
- Quantum Differentially Private Sparse Regression Learning
- Submodular Functions: from Discrete to Continous Domains
- Escaping the Curse of Dimensionality in Similarity Learning: Efficient Frank-Wolfe Algorithm and Generalization Bounds
- Data-Driven Adaptive Network Slicing for Multi-Tenant Networks
- A Distributed Frank-Wolfe Framework for Learning Low-Rank Matrices with the Trace Norm
- HardCoRe-NAS: Hard Constrained diffeRentiable Neural Architecture Search
- Blended Conditional Gradients: the unconditioning of conditional gradients
- Bayesian Coreset Construction via Greedy Iterative Geodesic Ascent
- Distributed Multi-Task Learning with Shared Representation
- Generalized Conditional Gradient with Augmented Lagrangian for Composite Minimization
- Primal-Dual Rates and Certificates
- Partial Optimal Transport with Applications on Positive-Unlabeled Learning
- Online data assimilation in distributionally robust optimization
- Frank-Wolfe Method is Automatically Adaptive to Error Bound Condition
- The Method of Pairwise Variations with Tolerances for Linearly Constrained Optimization Problems
- Joint Discovery of Object States and Manipulation Actions
- Lazifying Conditional Gradient Algorithms
- The condition of a function relative to a polytope
- Safe Screening for the Generalized Conditional Gradient Method
- Data assimilation and online optimization with performance guarantees
- Re-identification of Humans in Crowds using Personal, Social and Environmental Constraints
- An efficient high-probability algorithm for Linear Bandits
- Greedy Algorithms for Cone Constrained Optimization with Convergence Guarantees
- An algorithm to compute the Hoffman constant of a system of linear constraints
- First-order methods for the convex hull membership problem
- Faster Unbalanced Optimal Transport: Translation invariant Sinkhorn and 1-D Frank-Wolfe
- Projection Free Rank-Drop Steps
- Greedy Frank-Wolfe Algorithm for Exemplar Selection
- Robust Seriation and Applications to Cancer Genomics
- On the von Neumann and Frank-Wolfe Algorithms with Away Steps
- Searching equillibriums in large transport networks
- Stochastic In-Face Frank-Wolfe Methods for Non-Convex Optimization and Sparse Neural Network Training
- Learning the effect of latent variables in Gaussian Graphical models with unobserved variables
- On the Frank-Wolfe algorithm for non-compact constrained optimization problems
- Pursuits in Structured Non-Convex Matrix Factorizations
- Non accelerated efficient numerical methods for sparse quadratic optimization problems and its generalizations
- Deep Graph Matching under Quadratic Constraint
- Subquadratic Submodular Function Minimization
- Adaptively Transforming Graph Matching