# Spectral Frank-Wolfe Algorithm: Strict Complementarity and Linear Convergence

arXiv: https://arxiv.org/abs/2006.01719 · HTML: https://mlsanity.com/paper/2006.01719/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 Jun 2020.

## Built on by (most cited first, 8 of 8)

- [Frank-Wolfe with a Nearest Extreme Point Oracle](https://mlsanity.com/paper/2102.02029/) (2021)
- [Low-Rank Extragradient Method for Nonsmooth and Low-Rank Matrix Optimization Problems](https://mlsanity.com/paper/2202.04026/) (2022)
- [Efficiency of First-Order Methods for Low-Rank Tensor Recovery with the Tensor Nuclear Norm Under Strict Complementarity](https://mlsanity.com/paper/2308.01677/) (2023)
- [Local Linear Convergence of Gradient Methods for Subspace Optimization via Strict Complementarity](https://mlsanity.com/paper/2202.04020/) (2022)
- [Low-Rank Mirror-Prox for Nonsmooth and Low-Rank Matrix Optimization Problems](https://mlsanity.com/paper/2206.11523/) (2022)
- [Scalable High-Dimensional Multivariate Linear Regression for Feature-Distributed Data](https://mlsanity.com/paper/2307.03410/) (2023)
- [A Randomized Linearly Convergent Frank-Wolfe-type Method for Smooth Convex Minimization over the Spectrahedron](https://mlsanity.com/paper/2503.01441/) (2025)
- [Accelerated Frank-Wolfe Algorithms: Complementarity Conditions and Sparsity](https://mlsanity.com/paper/2511.02821/) (2025)

## Abstract (arXiv)

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.