# Stochastic Frank-Wolfe Methods for Nonconvex Optimization

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

## Key facts

- Cited by 41 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Jul 2016.

## Built on by (most cited first, 30 of 41)

- [Chain of LoRA: Efficient Fine-tuning of Language Models via Residual Learning](https://mlsanity.com/paper/2401.04151/) (2024)
- [Lions and Muons: Optimization via Stochastic Frank-Wolfe under Heavy-Tailed Noise](https://mlsanity.com/paper/2506.04192/) (2025)
- [Enhancing Sharpness-Aware Optimization Through Variance Suppression](https://mlsanity.com/paper/2309.15639/) (2023)
- [Scalable Optimal Transport Methods in Machine Learning: A Contemporary Survey](https://mlsanity.com/paper/2305.05080/) (2023)
- [A Stochastic Sequential Quadratic Optimization Algorithm for Nonlinear Equality Constrained Optimization with Rank-Deficient Jacobians](https://mlsanity.com/paper/2106.13015/) (2021)
- [Complexity of Linear Minimization and Projection on Some Sets](https://mlsanity.com/paper/2101.10040/) (2021)
- [Breaking the Linear Iteration Cost Barrier for Some Well-known Conditional Gradient Methods Using MaxIP Data-structures](https://mlsanity.com/paper/2111.15139/) (2021)
- [Escaping from Zero Gradient: Revisiting Action-Constrained Reinforcement Learning via Frank-Wolfe Policy Optimization](https://mlsanity.com/paper/2102.11055/) (2021)
- [Compression-aware Training of Neural Networks using Frank-Wolfe](https://mlsanity.com/paper/2205.11921/) (2022)
- [Efficient Approximation of Gromov-Wasserstein Distance Using Importance Sparsification](https://mlsanity.com/paper/2205.13573/) (2022)
- [Projection-Free Algorithm for Stochastic Bi-level Optimization](https://mlsanity.com/paper/2110.11721/) (2021)
- [A Projection-free Algorithm for Constrained Stochastic Multi-level Composition Optimization](https://mlsanity.com/paper/2202.04296/) (2022)
- [CrAM: A Compression-Aware Minimizer](https://mlsanity.com/paper/2207.14200/) (2022)
- [Sarah Frank-Wolfe: Methods for Constrained Optimization with Best Rates and Practical Features](https://mlsanity.com/paper/2304.11737/) (2023)
- [Zeroth and First Order Stochastic Frank-Wolfe Algorithms for Constrained Optimization](https://mlsanity.com/paper/2107.06534/) (2021)
- [Constrained Stochastic Nonconvex Optimization with State-dependent Markov Data](https://mlsanity.com/paper/2206.11346/) (2022)
- [Interpretable Neural Networks with Frank-Wolfe: Sparse Relevance Maps and Relevance Orderings](https://mlsanity.com/paper/2110.08105/) (2021)
- [Distributionally Robust Optimization with Markovian Data](https://mlsanity.com/paper/2106.06741/) (2021)
- [Shift of Pairwise Similarities for Data Clustering](https://mlsanity.com/paper/2110.13103/) (2021)
- [Optimal Exploration is no harder than Thompson Sampling](https://mlsanity.com/paper/2310.06069/) (2023)
- [Variance-Reduced Conservative Policy Iteration](https://mlsanity.com/paper/2212.06283/) (2022)
- [EsaCL: Efficient Continual Learning of Sparse Models](https://mlsanity.com/paper/2401.05667/) (2024)
- [Projection-Free Variance Reduction Methods for Stochastic Constrained Multi-Level Compositional Optimization](https://mlsanity.com/paper/2406.03787/) (2024)
- [A General Online Algorithm for Optimizing Complex Performance Metrics](https://mlsanity.com/paper/2406.14743/) (2024)
- [Don't Be Greedy, Just Relax! Pruning LLMs via Frank-Wolfe](https://mlsanity.com/paper/2510.13713/) (2025)
- [BLADE: Scalable Bi-level Adaptive Data Selection for LLM Training](https://mlsanity.com/paper/2606.18650/) (2026)
- [Faster One-Sample Stochastic Conditional Gradient Method for Composite Convex Minimization](https://mlsanity.com/paper/2202.13212/) (2022)
- [An Efficient Local Search Approach for Polarized Community Discovery in Signed Networks](https://mlsanity.com/paper/2502.02197/) (2025)
- [VASSO: Variance Suppression for Sharpness-Aware Minimization](https://mlsanity.com/paper/2509.02433/) (2025)
- [Iterative Sampling Methods for Sinkhorn Distributionally Robust Optimization](https://mlsanity.com/paper/2512.12550/) (2025)

## Abstract (arXiv)

We study Frank-Wolfe methods for nonconvex stochastic and finite-sum optimization problems. Frank-Wolfe methods (in the convex case) have gained tremendous recent interest in machine learning and optimization communities due to their projection-free property and their ability to exploit structured constraints. However, our understanding of these algorithms in the nonconvex setting is fairly limited. In this paper, we propose nonconvex stochastic Frank-Wolfe methods and analyze their convergence properties. For objective functions that decompose into a finite-sum, we leverage ideas from variance reduction techniques for convex optimization to obtain new variance reduced nonconvex Frank-Wolfe methods that have provably faster convergence than the classical Frank-Wolfe method. Finally, we show that the faster convergence rates of our variance reduced methods also translate into improved convergence rates for the stochastic setting.