# Accelerated Frank-Wolfe Algorithms: Complementarity Conditions and Sparsity

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 13 of its 28 references that are in the map.
- First posted on arXiv 4 Nov 2025.

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

- [On the Global Linear Convergence of Frank-Wolfe Optimization Variants](https://mlsanity.com/paper/1511.05932/) (2015)
- [The Complexity of Large-scale Convex Programming under a Linear Optimization Oracle](https://mlsanity.com/paper/1309.5550/) (2013)
- [Complexity of Linear Minimization and Projection on Some Sets](https://mlsanity.com/paper/2101.10040/) (2021)
- [Linear Convergence of a Frank-Wolfe Type Algorithm over Trace-Norm Balls](https://mlsanity.com/paper/1708.02105/) (2017)
- [Revisiting Frank-Wolfe for Polytopes: Strict Complementarity and Sparsity](https://mlsanity.com/paper/2006.00558/) (2020)
- [Linear-memory and Decomposition-invariant Linearly Convergent Conditional Gradient Algorithm for Structured Polytopes](https://mlsanity.com/paper/1605.06492/) (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)
- [Locally Accelerated Conditional Gradients](https://mlsanity.com/paper/1906.07867/) (2019)
- [Spectral Frank-Wolfe Algorithm: Strict Complementarity and Linear Convergence](https://mlsanity.com/paper/2006.01719/) (2020)
- [Linear Convergence of Frank-Wolfe for Rank-One Matrix Recovery Without Strong Convexity](https://mlsanity.com/paper/1912.01467/) (2019)
- [kFW: A Frank-Wolfe style algorithm with stronger subproblem oracles](https://mlsanity.com/paper/2006.16142/) (2020)
- [Improved Complexities of Conditional Gradient-Type Methods with Applications to Robust Matrix Recovery Problems](https://mlsanity.com/paper/1802.05581/) (2018)
- [Parameter-free Locally Accelerated Conditional Gradients](https://mlsanity.com/paper/2102.06806/) (2021)

## Abstract (arXiv)

We develop new accelerated first-order algorithms in the Frank-Wolfe (FW) family for minimizing smooth convex functions over compact convex sets, with a focus on two prominent constraint classes: (1) polytopes and (2) matrix domains given by the spectrahedron and nuclear-norm balls. A key technical ingredient is a complementarity condition that captures solution sparsity---face dimension for polytopes and rank for matrices. We present two algorithms: (1) a purely linear optimization oracle (LOO) method for polytopes that has optimal worst-case first-order (FO) oracle complexity and, aside of a finite burn-in phase and up to a logarithmic factor, has LOO complexity that scales with r/√ε, where ε is the target accuracy and r is the solution sparsity (independently of the ambient dimension), and (2) a hybrid scheme that combines FW with a sparse projection oracle (e.g., low-rank SVDs for matrix domains with low-rank solutions), which also has optimal FO oracle complexity, and after a finite burn-in phase, only requires O(1/√ε) sparse projections and LOO calls (independently of both the ambient dimension and the sparsity level of optimal solutions). Our results close a gap on how to accelerate recent advancements in linearly-converging FW algorithms for strongly convex optimization, without paying the price of the dimension.