# A Randomized Linearly Convergent Frank-Wolfe-type Method for Smooth Convex Minimization over the Spectrahedron

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 15 of its 35 references that are in the map.
- First posted on arXiv 3 Mar 2025.

## Builds on (most cited first, 15 of 15)

- [On the Global Linear Convergence of Frank-Wolfe Optimization Variants](https://mlsanity.com/paper/1511.05932/) (2015)
- [Error bounds, quadratic growth, and linear convergence of proximal methods](https://mlsanity.com/paper/1602.06661/) (2016)
- [A Unified Approach to Error Bounds for Structured Convex Optimization Problems](https://mlsanity.com/paper/1512.03518/) (2015)
- [An Extended Frank-Wolfe Method with "In-Face" Directions, and its Application to Low-Rank Matrix Completion](https://mlsanity.com/paper/1511.02204/) (2015)
- [Linear Convergence of a Frank-Wolfe Type Algorithm over Trace-Norm Balls](https://mlsanity.com/paper/1708.02105/) (2017)
- [Sketchy Decisions: Convex Low-Rank Matrix Optimization with Optimal Storage](https://mlsanity.com/paper/1702.06838/) (2017)
- [A Conditional Gradient-Based Augmented Lagrangian Framework](https://mlsanity.com/paper/1901.04013/) (2019)
- [Revisiting Frank-Wolfe for Polytopes: Strict Complementarity and Sparsity](https://mlsanity.com/paper/2006.00558/) (2020)
- [Robust Estimation of Structured Covariance Matrix for Heavy-Tailed Elliptical Distributions](https://mlsanity.com/paper/1506.05215/) (2015)
- [Faster Projection-free Convex Optimization over the Spectrahedron](https://mlsanity.com/paper/1605.06203/) (2016)
- [On the Convergence of Projected-Gradient Methods with Low-Rank Projections for Smooth Convex Minimization over Trace-Norm Balls and Related Problems](https://mlsanity.com/paper/1902.01644/) (2019)
- [Spectral Frank-Wolfe Algorithm: Strict Complementarity and Linear Convergence](https://mlsanity.com/paper/2006.01719/) (2020)
- [Frank-Wolfe Splitting via Augmented Lagrangian Method](https://mlsanity.com/paper/1804.03176/) (2018)
- [Linear Convergence of Frank-Wolfe for Rank-One Matrix Recovery Without Strong Convexity](https://mlsanity.com/paper/1912.01467/) (2019)
- [Frank-Wolfe-based Algorithms for Approximating Tyler's M-estimator](https://mlsanity.com/paper/2206.09370/) (2022)

## Abstract (arXiv)

We consider the problem of minimizing a smooth and convex function over the n-dimensional spectrahedron -- the set of real symmetric n× n positive semidefinite matrices with unit trace, which underlies numerous applications in statistics, machine learning and additional domains. Standard first-order methods often require high-rank matrix computations which are prohibitive when the dimension n is large. The well-known Frank-Wolfe method on the other hand only requires efficient rank-one matrix computations, however, suffers from worst-case slow convergence, even under conditions that enable linear convergence rates for standard methods. In this work we present the first Frank-Wolfe-based algorithm that only applies efficient rank-one matrix computations and, assuming quadratic growth and strict complementarity conditions, is guaranteed, after a finite number of iterations, to converge linearly, in expectation, and independently of the ambient dimension.