mlsanityData to 7 Oct 2026

Complexity of Linear Minimization and Projection on Some Sets

arXiv 2101.10040 ↗First posted 25 Jan 2021math.OC cs.DS cs.LGcited by 19

Not on the map. Why?

Abstract (arXiv)

The Frank-Wolfe algorithm is a method for constrained optimization that relies on linear minimizations, as opposed to projections. Therefore, a motivation put forward in a large body of work on the Frank-Wolfe algorithm is the computational advantage of solving linear minimizations instead of projections. However, the discussions supporting this advantage are often too succinct or incomplete. In this paper, we review the complexity bounds for both tasks on several sets commonly used in optimization. Projection methods onto the ℓp-ball, p∈left]1,2right[cupleft]2,+∞right[, and the Birkhoff polytope are also proposed.

Key facts. Cited by 19 papers in the map (data through 7 Oct 2026). Builds on 16 of its 57 references that are in the map. First posted on arXiv 25 Jan 2021.

Builds on

16 of 57 references.

References · 16

  1. 2015On the Global Linear Convergence of Frank-Wolfe Optimization Variantscited by 76
  2. 2016Convergence Rate of Frank-Wolfe for Non-Convex Objectivescited by 59
  3. 2014Faster Rates for the Frank-Wolfe Method over Strongly-Convex Setscited by 42
  4. 2016Stochastic Frank-Wolfe Methods for Nonconvex Optimizationcited by 40
  5. 2019One Sample Stochastic Frank-Wolfecited by 32
  6. 2018A Frank-Wolfe Framework for Efficient and Effective Adversarial Attackscited by 29
  7. 2019Sinkhorn Barycenters with Free Support via Frank-Wolfe Algorithmcited by 27
  8. 2019Efficient Projection-Free Online Methods with Stochastic Recursive Gradientcited by 19
  9. 2015An Extended Frank-Wolfe Method with "In-Face" Directions, and its Application to Low-Rank Matrix Completioncited by 15
  10. 2019Revisiting the Approximate Carath'eodory Problem via the Frank-Wolfe Algorithmcited by 11
  11. 2016Linear-memory and Decomposition-invariant Linearly Convergent Conditional Gradient Algorithm for Structured Polytopescited by 9
  12. 2020Boosting Frank-Wolfe by Chasing Gradientscited by 9
4 more
  1. 2016Lazifying Conditional Gradient Algorithmscited by 8
  2. 2020Projection-Free Adaptive Gradients for Large-Scale Optimizationcited by 6
  3. 2014Faster convergence rates of relaxed Peaceman-Rachford and ADMM under regularity assumptionscited by 3
  4. 2015First order constrained optimization algorithms with feasibility updatescited by 1

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 5; 2022: 1; 2023: 2; 2024: 2; 2025: 6; 2026: 3.

19 papers.

Sort:

  1. 2025Lions and Muons: Optimization via Stochastic Frank-Wolfe under Heavy-Tailed Noisecited by 38
  2. 2021No-Regret Dynamics in the Fenchel Game: A Unified Framework for Algorithmic Convex Optimizationcited by 20
  3. 2022Compression-aware Training of Neural Networks using Frank-Wolfecited by 16
  4. 2021Linear Bandits on Uniformly Convex Setscited by 6
  5. 2021Parameter-free Locally Accelerated Conditional Gradientscited by 5
  6. 2021Interpretable Neural Networks with Frank-Wolfe: Sparse Relevance Maps and Relevance Orderingscited by 5
  7. 2023Linearization Algorithms for Fully Composite Optimizationcited by 2
  8. 2024Stochastic Constrained Decentralized Optimization for Machine Learning with Fewer Data Oracles: a Gradient Sliding Approachcited by 2
  9. 2025Revisiting Frank-Wolfe for Structured Nonconvex Optimizationcited by 2
  10. 2024Structured Regularization for Constrained Optimization on the SPD Manifoldcited by 1
  11. 2025Scalable DC Optimization via Adaptive Frank-Wolfe Algorithmscited by 1
  12. 2025Don't Be Greedy, Just Relax! Pruning LLMs via Frank-Wolfecited by 1
7 more
  1. 2021Approximate Frank-Wolfe Algorithms over Graph-structured Support Setscited by 0
  2. 2023Nonsmooth Projection-Free Optimization with Functional Constraintscited by 0
  3. 2025Adaptive Conditional Gradient Descentcited by 0
  4. 2025Accelerated Frank-Wolfe Algorithms: Complementarity Conditions and Sparsitycited by 0
  5. 2026Constrained Variable Projection for Structured Problemscited by 0
  6. 2026Complexities of Weak Proximal Oracle Methods for Composite Convex Optimizationcited by 0
  7. 2026Local LMO is Secretly a Projection Method!cited by 0