FW: A Frank-Wolfe style algorithm with stronger subproblem oracles
arXiv:2006.16142
Abstract
This paper proposes a new variant of Frank-Wolfe (FW), called FW. Standard FW suffers from slow convergence: iterates often zig-zag as update directions oscillate around extreme points of the constraint set. The new variant, FW, overcomes this problem by using two stronger subproblem oracles in each iteration. The first is a linear optimization oracle (LOO) that computes the best update directions (rather than just one). The second is a direction search (DS) that minimizes the objective over a constraint set represented by the best update directions and the previous iterate. When the problem solution admits a sparse representation, both oracles are easy to compute, and FW converges quickly for smooth convex objectives and several interesting constraint sets: FW achieves finite convergence on polytopes and group norm balls, and linear convergence on spectrahedra and nuclear norm balls. Numerical experiments validate the effectiveness of FW and demonstrate an order-of-magnitude speedup over existing approaches.
arXiv comment20 pages main text, 10 figures
References in corpus (13)
- Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
- A Field Guide to Forward-Backward Splitting with a FASTA Implementation
- Faster Rates for the Frank-Wolfe Method over Strongly-Convex Sets
- Sketchy Decisions: Convex Low-Rank Matrix Optimization with Optimal Storage
- An Affine Invariant Linear Convergence Analysis for Frank-Wolfe Algorithms
- Linear-memory and Decomposition-invariant Linearly Convergent Conditional Gradient Algorithm for Structured Polytopes
- FASTA: A Generalized Implementation of Forward-Backward Splitting
- Spectral Frank-Wolfe Algorithm: Strict Complementarity and Linear Convergence
- On the Convergence of Projected-Gradient Methods with Low-Rank Projections for Smooth Convex Minimization over Trace-Norm Balls and Related Problems
- Limited Memory Kelley's Method Converges for Composite Convex and Submodular Objectives
- -best enumeration
- On the simplicity and conditioning of low rank semidefinite programs
- Parameter-free Locally Accelerated Conditional Gradients