# Convergence Rate of Frank-Wolfe for Non-Convex Objectives

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

## Key facts

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

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

- [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)
- [Online Graph Dictionary Learning](https://mlsanity.com/paper/2102.06555/) (2021)
- [Low-Rank Adaptation for Foundation Models: A Comprehensive Review](https://mlsanity.com/paper/2501.00365/) (2024)
- [Semi-relaxed Gromov-Wasserstein divergence with applications on graphs](https://mlsanity.com/paper/2110.02753/) (2021)
- [Complexity of Linear Minimization and Projection on Some Sets](https://mlsanity.com/paper/2101.10040/) (2021)
- [Template based Graph Neural Network with Optimal Transport Distances](https://mlsanity.com/paper/2205.15733/) (2022)
- [C2M3: Cycle-Consistent Multi-Model Merging](https://mlsanity.com/paper/2405.17897/) (2024)
- [Escaping from Zero Gradient: Revisiting Action-Constrained Reinforcement Learning via Frank-Wolfe Policy Optimization](https://mlsanity.com/paper/2102.11055/) (2021)
- [A Conditional Gradient-based Method for Simple Bilevel Optimization with Convex Lower-level Problem](https://mlsanity.com/paper/2206.08868/) (2022)
- [PPO-Clip Attains Global Optimality: Towards Deeper Understandings of Clipping](https://mlsanity.com/paper/2312.12065/) (2023)
- [Compression-aware Training of Neural Networks using Frank-Wolfe](https://mlsanity.com/paper/2205.11921/) (2022)
- [Projection-Free Methods for Stochastic Simple Bilevel Optimization with Convex Lower-level Problem](https://mlsanity.com/paper/2308.07536/) (2023)
- [Distributional Reduction: Unifying Dimensionality Reduction and Clustering with Gromov-Wasserstein](https://mlsanity.com/paper/2402.02239/) (2024)
- [Non-Euclidean Gradient Descent Operates at the Edge of Stability](https://mlsanity.com/paper/2603.05002/) (2026)
- [Projection-Free Algorithm for Stochastic Bi-level Optimization](https://mlsanity.com/paper/2110.11721/) (2021)
- [Curriculum-based Asymmetric Multi-task Reinforcement Learning](https://mlsanity.com/paper/2211.03352/) (2022)
- [Sarah Frank-Wolfe: Methods for Constrained Optimization with Best Rates and Practical Features](https://mlsanity.com/paper/2304.11737/) (2023)
- [Boosting Gradient Ascent for Continuous DR-submodular Maximization](https://mlsanity.com/paper/2401.08330/) (2024)
- [Interpretable Neural Networks with Frank-Wolfe: Sparse Relevance Maps and Relevance Orderings](https://mlsanity.com/paper/2110.08105/) (2021)
- [LeanVec: Searching vectors faster by making them fit](https://mlsanity.com/paper/2312.16335/) (2023)
- [Projected Forward Gradient-Guided Frank-Wolfe Algorithm via Variance Reduction](https://mlsanity.com/paper/2403.12511/) (2024)
- [FW-Merging: Scaling Model Merging with Frank-Wolfe Optimization](https://mlsanity.com/paper/2503.12649/) (2025)
- [Distributionally Robust Optimization with Markovian Data](https://mlsanity.com/paper/2106.06741/) (2021)
- [Subspace Detours Meet Gromov-Wasserstein](https://mlsanity.com/paper/2110.10932/) (2021)
- [Revisiting Counterfactual Regression through the Lens of Gromov-Wasserstein Information Bottleneck](https://mlsanity.com/paper/2405.15505/) (2024)
- [Frank-Wolfe-based Algorithms for Approximating Tyler's M-estimator](https://mlsanity.com/paper/2206.09370/) (2022)
- [Difference of Submodular Minimization via DC Programming](https://mlsanity.com/paper/2305.11046/) (2023)
- [Large-Scale Non-convex Stochastic Constrained Distributionally Robust Optimization](https://mlsanity.com/paper/2404.01200/) (2024)
- [Minimizing low-rank models of high-order tensors: Hardness, span, tight relaxation, and applications](https://mlsanity.com/paper/2210.11413/) (2022)

## Abstract (arXiv)

We give a simple proof that the Frank-Wolfe algorithm obtains a stationary point at a rate of O(1/√t) on non-convex objectives with a Lipschitz continuous gradient. Our analysis is affine invariant and is the first, to the best of our knowledge, giving a similar rate to what was already proven for projected gradient methods (though on slightly different measures of stationarity).