Revisiting Decomposition-Invariant Conditional Gradient Methods for Polytopes

DOI10.48550/arXiv.2608.01243MaRDI QIDQ7284563arXivFDO

Authors Dan Garber

Publication date 2 August 2026

Published in arXiv

Tldr We revisit Decomposition-Invariant Conditional Gradient methods and design new methods for minimizing convex functions over polytopes. For 2-level polytopes we obtain linear convergence with a dimension-free step-size rule, while for general polytopes our method scales with the optimal face dimension rather than ambient dimension.

Full work available at URL https://doi.org/10.48550/arXiv.2608.01243

arXiv classification

math.NAmath.OC

Cites work

• A Linearly Convergent Variant of the Conditional Gradient Algorithm under Strong Convexity, with Applications to Online and Stochastic Optimization
• Conditional Gradient Methods
• Conditional gradient methods. From core principles to AI applications
• Fast Convergence of Frank-Wolfe algorithms on polytopes
• Linear convergence of first order methods for non-strongly convex optimization
• Linear-memory and Decomposition-invariant Linearly Convergent Conditional Gradient Algorithm for Structured Polytopes
• On the Global Linear Convergence of Frank-Wolfe Optimization Variants
• Playing non-linear games with linear oracles
• Revisiting Frank-Wolfe for Polytopes: Strict Complementarity and Sparsity
• Some comments on Wolfe's ‘away step’

This page was built for publication: Revisiting Decomposition-Invariant Conditional Gradient Methods for Polytopes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7284563)