mlsanityData to 7 Oct 2026

Sarah Frank-Wolfe: Methods for Constrained Optimization with Best Rates and Practical Features

arXiv 2304.11737 ↗First posted 23 Apr 2023math.OC cs.LG stat.MLcited by 6

Not on the map. Why?

Abstract (arXiv)

The Frank-Wolfe (FW) method is a popular approach for solving optimization problems with structured constraints that arise in machine learning applications. In recent years, stochastic versions of FW have gained popularity, motivated by large datasets for which the computation of the full gradient is prohibitively expensive. In this paper, we present two new variants of the FW algorithms for stochastic finite-sum minimization. Our algorithms have the best convergence guarantees of existing stochastic FW approaches for both convex and non-convex objective functions. Our methods do not have the issue of permanently collecting large batches, which is common to many stochastic projection-free approaches. Moreover, our second approach does not require either large batches or full deterministic gradients, which is a typical weakness of many techniques for finite-sum problems. The faster theoretical rates of our approaches are confirmed experimentally.

Key facts. Cited by 6 papers in the map (data through 7 Oct 2026). Builds on 37 of its 63 references that are in the map. First posted on arXiv 23 Apr 2023.

Builds on

37 of 63 references.

References · 37

  1. 2014SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectivescited by 401
  2. 2019Momentum-Based Variance Reduction in Non-Convex SGDcited by 302
  3. 2018SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimatorcited by 283
  4. 2017SARAH: A Novel Method for Machine Learning Problems Using Stochastic Recursive Gradientcited by 218
  5. 2013Minimizing Finite Sums with the Stochastic Average Gradientcited by 164
  6. 2016Katyusha: The First Direct Acceleration of Stochastic Gradient Methodscited by 134
  7. 2021EF21: A New, Simpler, Theoretically Better, and Practically Faster Error Feedbackcited by 131
  8. 2020PAGE: A Simple and Optimal Probabilistic Gradient Estimator for Nonconvex Optimizationcited by 116
  9. 2019Unified Optimal Analysis of the (Stochastic) Gradient Methodcited by 81
  10. 2021MARINA: Faster Non-Convex Distributed Learning with Compressioncited by 77
  11. 2015On the Global Linear Convergence of Frank-Wolfe Optimization Variantscited by 76
  12. 2016Variance Reduction for Faster Non-Convex Optimizationcited by 72
25 more
  1. 2019Don't Jump Through Hoops and Remove Those Loops: SVRG and Katyusha are Better Without the Outer Loopcited by 68
  2. 2016Convergence Rate of Frank-Wolfe for Non-Convex Objectivescited by 59
  3. 2014Weakly Supervised Action Labeling in Videos Under Ordering Constraintscited by 48
  4. 2018Stochastic Conditional Gradient Methods: From Convex Minimization to Submodular Maximizationcited by 47
  5. 2016Variance-Reduced and Projection-Free Stochastic Optimizationcited by 40
  6. 2016Stochastic Frank-Wolfe Methods for Nonconvex Optimizationcited by 40
  7. 2015Improved SVRG for Non-Strongly-Convex or Sum-of-Non-Convex Objectivescited by 38
  8. 2014Incremental Majorization-Minimization Optimization with Application to Large-Scale Machine Learningcited by 35
  9. 2019One Sample Stochastic Frank-Wolfecited by 32
  10. 2021ZeroSARAH: Efficient Nonconvex Finite-Sum Optimization with Zero Full Gradient Computationcited by 28
  11. 2021Lower Complexity Bounds of Finite-Sum Optimization Problems: The Results and Constructioncited by 22
  12. 2017Stochastic Recursive Gradient Algorithm for Nonconvex Optimizationcited by 20
  13. 2014A Stochastic PCA and SVD Algorithm with an Exponential Convergence Ratecited by 18
  14. 2015Fast and Simple PCA via Convex Optimizationcited by 16
  15. 2022Conditional Gradient Methodscited by 16
  16. 2020Stochastic Frank-Wolfe for Constrained Finite-Sum Minimizationcited by 14
  17. 2017Non-convex Conditional Gradient Slidingcited by 12
  18. 2018Inexact SARAH Algorithm for Stochastic Optimizationcited by 12
  19. 2015Barrier Frank-Wolfe for Marginal Inferencecited by 10
  20. 2019SAGA with Arbitrary Samplingcited by 10
  21. 2018Generalized Stochastic Frank-Wolfe Algorithm with Stochastic "Substitute" Gradient for Structured Convex Optimizationcited by 8
  22. 2014A Distributed Frank-Wolfe Algorithm for Communication-Efficient Sparse Learningcited by 7
  23. 2017Learning from Video and Text via Large-Scale Discriminative Clusteringcited by 6
  24. 2019Accelerating Mini-batch SARAH by Step Size Rulescited by 4
  25. 2022Distributed Momentum-based Frank-Wolfe Algorithm for Stochastic Optimizationcited by 1

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 1; 2024: 0; 2025: 2; 2026: 3.

6 papers.

  1. 2025Lions and Muons: Optimization via Stochastic Frank-Wolfe under Heavy-Tailed Noisecited by 38
  2. 2023Projection-Free Methods for Stochastic Simple Bilevel Optimization with Convex Lower-level Problemcited by 13
  3. 2025Provable Model-Parallel Distributed Principal Component Analysis with Parallel Deflationcited by 1
  4. 2026Randomized Feasibility Methods for Constrained Optimization with Adaptive Step Sizescited by 1
  5. 2026Adaptive Lipschitz-Free Conditional Gradient Methods for Stochastic Composite Nonconvex Optimizationcited by 1
  6. 2026Accelerating LMO-Based Optimization via Implicit Gradient Transportcited by 0