Fast Convergence of Frank-Wolfe Algorithms on Polytopes

• 成果类型: Article; Early Access
• 署名作者: Wirth, Elias; Pena, Javier; Pokutta, Sebastian
• 署名单位: Technical University of Berlin; Carnegie Mellon University; Zuse Institute Berlin
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2024.0580
• 发表日期: 2025
• 关键词: rates

摘要

We provide a template to derive affine-invariant convergence rates for the following popular versions of the Frank-Wolfe algorithm on polytopes: vanilla Frank-Wolfe, Frank-Wolfe with away steps, Frank-Wolfe with blended pairwise steps, and Frank-Wolfe with in-face directions. Our template shows how the convergence rates follow from two affine-invariant properties of the problem, namely, error bound and extended curvature. These properties depend solely on the polytope and objective function but not on any affinedependent object like norms. For each one of the above algorithms, we derive rates of convergence ranging from sublinear to linear depending on the degree of the error bound.