# Stochastic Frank-Wolfe: Unified Analysis and Zoo of Special Cases

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Jun 2024.

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

- [Lions and Muons: Optimization via Stochastic Frank-Wolfe under Heavy-Tailed Noise](https://mlsanity.com/paper/2506.04192/) (2025)
- [Leveraging Coordinate Momentum in SignSGD and Muon: Memory-Optimized Zero-Order](https://mlsanity.com/paper/2506.04430/) (2025)
- [Provable Benefit of SignGD: A Minimal Model Under Heavy-Tailed Class Imbalance](https://mlsanity.com/paper/2512.00763/) (2025)
- [Randomized Feasibility Methods for Constrained Optimization with Adaptive Step Sizes](https://mlsanity.com/paper/2601.20076/) (2026)
- [Variance-Reduced Conditional Gradient Methods under Markovian Sampling for Nonconvex Composite Optimization](https://mlsanity.com/paper/2607.25785/) (2026)

## Abstract (arXiv)

The Conditional Gradient (or Frank-Wolfe) method is one of the most well-known methods for solving constrained optimization problems appearing in various machine learning tasks. The simplicity of iteration and applicability to many practical problems helped the method to gain popularity in the community. In recent years, the Frank-Wolfe algorithm received many different extensions, including stochastic modifications with variance reduction and coordinate sampling for training of huge models or distributed variants for big data problems. In this paper, we present a unified convergence analysis of the Stochastic Frank-Wolfe method that covers a large number of particular practical cases that may have completely different nature of stochasticity, intuitions and application areas. Our analysis is based on a key parametric assumption on the variance of the stochastic gradients. But unlike most works on unified analysis of other methods, such as SGD, we do not assume an unbiasedness of the real gradient estimation. We conduct analysis for convex and non-convex problems due to the popularity of both cases in machine learning. With this general theoretical framework, we not only cover rates of many known methods, but also develop numerous new methods. This shows the flexibility of our approach in developing new algorithms based on the Conditional Gradient approach. We also demonstrate the properties of the new methods through numerical experiments.