An Affine Invariant Linear Convergence Analysis for Frank-Wolfe Algorithms

Abstract

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.

appeared at the NIPS 2013 Workshop on Greedy Algorithms, Frank-Wolfe and Friends (v2: added acknowledgements)

References in corpus (1)

• The Complexity of Large-scale Convex Programming under a Linear Optimization Oracle

Cited by in corpus (17)

• On the Global Linear Convergence of Frank-Wolfe Optimization Variants
• Faster Rates for the Frank-Wolfe Method over Strongly-Convex Sets
• Frank-Wolfe Algorithms for Saddle Point Problems
• Linear Convergence of a Frank-Wolfe Type Algorithm over Trace-Norm Balls
• Projection-Free Optimization on Uniformly Convex Sets
• Frank-Wolfe Method is Automatically Adaptive to Error Bound Condition
• A Distributed Frank-Wolfe Algorithm for Communication-Efficient Sparse Learning
• Affine Invariant Analysis of Frank-Wolfe on Strongly Convex Sets
• Efficient Projection-Free Algorithms for Saddle Point Problems
• Generating Structured Adversarial Attacks Using Frank-Wolfe Method
• A Frank-Wolfe Based Branch-and-Bound Algorithm for Mean-Risk Optimization
• $k$FW: A Frank-Wolfe style algorithm with stronger subproblem oracles
• Fast and Scalable Lasso via Stochastic Frank-Wolfe Methods with a Convergence Guarantee
• Approximate and Stochastic Greedy Optimization
• The Cyclic Block Conditional Gradient Method for Convex Optimization Problems
• Trace-Norm Adversarial Examples
• Semi-Stochastic Frank-Wolfe Algorithms with Away-Steps for Block-Coordinate Structure Problems