Blended Conditional Gradients: the unconditioning of conditional gradients

Abstract

We present a blended conditional gradient approach for minimizing a smooth convex function over a polytope P, combining the Frank--Wolfe algorithm (also called conditional gradient) with gradient-based steps, different from away steps and pairwise steps, but still achieving linear convergence for strongly convex functions, along with good practical performance. Our approach retains all favorable properties of conditional gradient algorithms, notably avoidance of projections onto P and maintenance of iterates as sparse convex combinations of a limited number of extreme points of P. The algorithm is lazy, making use of inexpensive inexact solutions of the linear programming subproblem that characterizes the conditional gradient approach. It decreases measures of optimality (primal and dual gaps) rapidly, both in the number of iterations and in wall-clock time, outperforming even the lazy conditional gradient algorithms of [arXiv:1410.8816]. We also present a streamlined version of the algorithm for the probability simplex.

33 pages + 12 figures; fixed typos in v4

References in corpus (7)

• On the Global Linear Convergence of Frank-Wolfe Optimization Variants
• Forward - Backward Greedy Algorithms for Atomic Norm Regularization
• A Linearly Convergent Conditional Gradient Algorithm with Applications to Online and Stochastic Optimization
• Linear-memory and Decomposition-invariant Linearly Convergent Conditional Gradient Algorithm for Structured Polytopes
• Conditional Accelerated Lazy Stochastic Gradient Descent
• Improved Complexities of Conditional Gradient-Type Methods with Applications to Robust Matrix Recovery Problems
• The condition of a function relative to a polytope

Cited by in corpus (10)

• Boosting Frank-Wolfe by Chasing Gradients
• Affine Invariant Analysis of Frank-Wolfe on Strongly Convex Sets
• Sparser Kernel Herding with Pairwise Conditional Gradients without Swap Steps
• How Does Momentum Help Frank Wolfe?
• Locally Accelerated Conditional Gradients
• Parameter-free Locally Accelerated Conditional Gradients
• Stochastic In-Face Frank-Wolfe Methods for Non-Convex Optimization and Sparse Neural Network Training
• Generalized conditional subgradient and generalized mirror descent: duality, convergence, and symmetry
• A Unifying Perspective on Descent Directions for Constrained Minimization and Switching Criteria
• One-sided Frank-Wolfe algorithms for saddle problems