Spectral Frank-Wolfe Algorithm: Strict Complementarity and Linear Convergence

Abstract

We develop a novel variant of the classical Frank-Wolfe algorithm, which we call spectral Frank-Wolfe, for convex optimization over a spectrahedron. The spectral Frank-Wolfe algorithm has a novel ingredient: it computes a few eigenvectors of the gradient and solves a small-scale SDP in each iteration. Such procedure overcomes slow convergence of the classical Frank-Wolfe algorithm due to ignoring eigenvalue coalescence. We demonstrate that strict complementarity of the optimization problem is key to proving linear convergence of various algorithms, such as the spectral Frank-Wolfe algorithm as well as the projected gradient method and its accelerated version.

The main text has nine pages. Reading the first three sections should give a good understanding of the paper and should take around 15 minutes. Published in proceedings of the 37th International Conference on Machine Learning, online, PMLR 119, 2020

References in corpus (6)

• Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
• A Field Guide to Forward-Backward Splitting with a FASTA Implementation
• Sketchy Decisions: Convex Low-Rank Matrix Optimization with Optimal Storage
• FASTA: A Generalized Implementation of Forward-Backward Splitting
• Faster Projection-free Convex Optimization over the Spectrahedron
• On the Convergence of Projected-Gradient Methods with Low-Rank Projections for Smooth Convex Minimization over Trace-Norm Balls and Related Problems

Cited by in corpus (4)

• On the Efficient Implementation of the Matrix Exponentiated Gradient Algorithm for Low-Rank Matrix Optimization
• Understanding Modern Techniques in Optimization: Frank-Wolfe, Nesterov's Momentum, and Polyak's Momentum
• Frank-Wolfe with a Nearest Extreme Point Oracle
• $k$FW: A Frank-Wolfe style algorithm with stronger subproblem oracles