mlsanityData to 14 Oct 2026

Linear Convergence of the Frank-Wolfe Algorithm over Product Polytopes

arXiv 2505.11259 ↗First posted 16 May 2025math.OC cs.LGcited by 0

Not on the map. Why?

Abstract (arXiv)

We study the linear convergence of Frank-Wolfe algorithms over product polytopes. We analyze two condition numbers for the product polytope, namely the pyramidal width and the vertex-facet distance, based on the condition numbers of individual polytope components. As a result, for convex objectives that are μ-Polyak-Lojasiewicz, we show linear convergence rates quantified in terms of the resulting condition numbers. We apply our results to the problem of approximately finding a feasible point in a polytope intersection in high-dimensions, and demonstrate the practical efficiency of our algorithms through empirical results.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 27 of its 52 references that are in the map. First posted on arXiv 16 May 2025.

Builds on

27 of 52 references.

References · 27

  1. 2016Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Conditioncited by 539
  2. 2015On the Global Linear Convergence of Frank-Wolfe Optimization Variantscited by 77
  3. 2014Faster Rates for the Frank-Wolfe Method over Strongly-Convex Setscited by 44
  4. 2013A Linearly Convergent Conditional Gradient Algorithm with Applications to Online and Stochastic Optimizationcited by 18
  5. 2022Conditional Gradient Methodscited by 17
  6. 2015Linearly Convergent Away-Step Conditional Gradient for Non-strongly Convex Functionscited by 12
  7. 2015Polytope conditioning and linear convergence of the Frank-Wolfe algorithmcited by 10
  8. 2018Frank-Wolfe Splitting via Augmented Lagrangian Methodcited by 7
  9. 2022Approximate Vanishing Ideal Computations at Scalecited by 6
  10. 2013An Affine Invariant Linear Convergence Analysis for Frank-Wolfe Algorithmscited by 5
  11. 2018Efficient Optimization Algorithms for Robust Principal Component Analysis and Its Variantscited by 5
  12. 2025Beyond Short Steps in Frank-Wolfe Algorithmscited by 4
15 more
  1. 2014Transversality and alternating projections for nonconvex setscited by 3
  2. 2015The Cyclic Block Conditional Gradient Method for Convex Optimization Problemscited by 3
  3. 2023Square distance functions are Polyak-Lojasiewicz and vice-versacited by 3
  4. 2023Efficient Learning in Polyhedral Games via Best Response Oraclescited by 3
  5. 2024The Pivoting Framework: Frank-Wolfe Algorithms with Active Set Size Controlcited by 3
  6. 2015On the von Neumann and Frank-Wolfe Algorithms with Away Stepscited by 2
  7. 2021Affine invariant convergence rates of the conditional gradient methodcited by 2
  8. 2023Accelerated Affine-Invariant Convergence Rates of the Frank-Wolfe Algorithm with Open-Loop Step-Sizescited by 2
  9. 2020Infeasibility and error bound imply finite convergence of alternating projectionscited by 1
  10. 2020A Note on the Finite Convergence of Alternating Projectionscited by 1
  11. 2020The smoothed complexity of Frank-Wolfe methods via conditioning of random matrices and polytopescited by 1
  12. 2022Acceleration of Frank-Wolfe Algorithms with Open-Loop Step-Sizescited by 1
  13. 2022Alternating Linear Minimization: Revisiting von Neumann's alternating projectionscited by 1
  14. 2023Projection free methods on product domainscited by 1
  15. 2024Fast convergence of Frank-Wolfe algorithms on polytopescited by 1

Built on by

Not cited yet.