{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,8]],"date-time":"2026-05-08T21:56:46Z","timestamp":1778277406785,"version":"3.51.4"},"reference-count":26,"publisher":"Institute for Operations Research and the Management Sciences (INFORMS)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Mathematics of OR"],"published-print":{"date-parts":[[2026,5]]},"abstract":"<jats:p>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 affine-dependent 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.<\/jats:p>\n                  <jats:p>Funding: Research reported in this paper was partially supported by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) under Germany\u2019s Excellence Strategy\u2014The Berlin Mathematics Research Center MATH (EXC-2046\/1, project ID 390685689, BMS Stipend). Research reported in this paper was also partially supported by the Bajaj Family Chair at the Tepper School of Business, Carnegie Mellon University.<\/jats:p>","DOI":"10.1287\/moor.2024.0580","type":"journal-article","created":{"date-parts":[[2025,5,29]],"date-time":"2025-05-29T11:51:23Z","timestamp":1748519483000},"page":"1463-1485","source":"Crossref","is-referenced-by-count":1,"title":["Fast Convergence of Frank-Wolfe Algorithms on Polytopes"],"prefix":"10.1287","volume":"51","author":[{"ORCID":"https:\/\/orcid.org\/0009-0008-8957-8736","authenticated-orcid":false,"given":"Elias","family":"Wirth","sequence":"first","affiliation":[{"name":"Technical University of Berlin, 10623 Berlin, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5698-1918","authenticated-orcid":false,"given":"Javier","family":"Pe\u00f1a","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, Pennsylvania 15213"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7365-3000","authenticated-orcid":false,"given":"Sebastian","family":"Pokutta","sequence":"additional","affiliation":[{"name":"Technical University of Berlin, 10623 Berlin, Germany; and Zuse Institute Berlin, 14195 Berlin, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"109","reference":[{"key":"B1","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-016-1069-4"},{"key":"B2","doi-asserted-by":"publisher","DOI":"10.1137\/130919052"},{"key":"B3","unstructured":"Carderera A, Pokutta S, Sch\u00fctte C, Weiser M (2021) CINDy: Conditional gradient-based identification of non-linear dynamics\u2013noise-robust recovery. Preprint, submitted January 7, https:\/\/arxiv.org\/abs\/2101.02630."},{"key":"B4","volume-title":"Approximate Methods in Optimization Problems, Modern Analytic and Computational Methods in Science and Mathematics","volume":"32","author":"Demianov VF","year":"1970"},{"key":"B5","doi-asserted-by":"publisher","DOI":"10.1137\/0317015"},{"key":"B6","doi-asserted-by":"publisher","DOI":"10.1137\/15M104726X"},{"key":"B7","unstructured":"Garber D (2020) Revisiting Frank-Wolfe for polytopes: Strict complementarity and sparsity. Larochelle H, Ranzato M, Hadsell R, Balcan MF, Lin H, eds.\n                      Adv. Neural Inform. Processing Systems (NeurIPS 2020)\n                      , vol. 33 (MIT Press, Cambridge, MA), 18883\u201318893."},{"key":"B8","unstructured":"Garber D, Hazan E (2015) Faster rates for the Frank-Wolfe method over strongly-convex sets. Bach F, Blei D, eds.\n                      Proc. 32nd Internat. Conf. Machine Learn.\n                      , vol. 37 (Machine Learning Research Inc. New York), 541\u2013549."},{"key":"B9","unstructured":"Garber D, Meshi O (2016) Linear-memory and decomposition-invariant linearly convergent conditional gradient algorithm for structured polytopes. Lee DD, von Luxburg U, Garnett R, Sugiyama M, Guyon I, eds.\n                      NIPS \u201816 Proc. 30th Internat. Conf. Neural Inform. Processing Systems\n                      (Curran Associates, Red Hook, NY), 1009\u20131017."},{"key":"B10","doi-asserted-by":"publisher","DOI":"10.1007\/BF01589445"},{"key":"B11","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-020-01510-4"},{"key":"B12","doi-asserted-by":"publisher","DOI":"10.1007\/BF01580219"},{"key":"B13","unstructured":"Jaggi M (2013) Revisiting Frank-Wolfe: Projection-free sparse convex optimization. Dasgupta S, McAllester D, eds.\n                      Proc. 30th Internat. Conf. Machine Learn.\n                      , vol. 28, no. 1 (PMLR, New York), 427\u2013435."},{"key":"B14","doi-asserted-by":"crossref","unstructured":"Joulin A, Tang K, Fei-Fei L (2014) Efficient image and video co-localization with Frank-Wolfe algorithm. Fleet D, Pajdla T, Schiele B, Tuytelaars T, eds.\n                      Comput. Vision ECCV 2014\n                      (Springer, Cham, Switzerland), 253\u2013268.","DOI":"10.1007\/978-3-319-10599-4_17"},{"key":"B15","unstructured":"Kerdreux T, d\u2019Aspremont A, Pokutta S (2021) Projection-free optimization on uniformly convex sets. Banerjee A, Fukumizu K, eds.\n                      Proc. 24th Internat. Conf. Artificial Intelligence Statist.\n                      , vol. 130 (PMLR, New York), 19\u201327."},{"key":"B16","unstructured":"Lacoste-Julien S, Jaggi M (2015) On the global linear convergence of Frank-Wolfe optimization variants. Cortes C, Lee DD, Sugiyama M, Garnett R, eds.\n                      NIPS \u201815 Proc. 29th Internat. Conf. Neural Inform. Processing Systems\n                      , vol. 1 (MIT Press, Cambridge, MA), 496\u2013504."},{"key":"B17","doi-asserted-by":"publisher","DOI":"10.1016\/0041-5553(66)90114-5"},{"key":"B18","doi-asserted-by":"publisher","DOI":"10.1137\/21M1465263"},{"issue":"1","key":"B19","first-page":"1","volume":"44","author":"Pe\u00f1a J","year":"2018","journal-title":"Math. Oper. Res."},{"key":"B20","volume-title":"Introduction to Optimization","author":"Polyak BT","year":"1987"},{"key":"B21","doi-asserted-by":"publisher","DOI":"10.1111\/j.2517-6161.1996.tb02080.x"},{"key":"B22","unstructured":"Tsuji KK, Tanaka K, Pokutta S (2022) Pairwise conditional gradients without swap steps and sparser kernel herding. Chaudhuri K, Jegelka S, Song L, Szepesvari C, Niu G, Sabato S, eds.\n                      Proc. 39th Internat. Conf. Machine Learn.\n                      , vol. 162 (PMLR, New York), 21864\u201321883."},{"key":"B23","unstructured":"Wirth E, Kera H, Pokutta S (2023) Approximate vanishing ideal computations at scale.\n                      Proc. Internat. Conf. Learn. Representations\n                      (ICLR, Appleton, WI)."},{"key":"B24","unstructured":"Wirth E, Kerdreux T, Pokutta S (2023) Acceleration of Frank-Wolfe algorithms with open-loop step-sizes. Ruiz F, Dy J, van de Meent J-W, eds.\n                      Proc. 26th Internat. Conf. Artificial Intelligence Statist.\n                      , vol. 206 (PMLR, New York), 77\u2013100."},{"key":"B25","author":"Wirth E","year":"2025","journal-title":"Math. Programming"},{"key":"B26","first-page":"1","volume-title":"Integer and Nonlinear Programming","author":"Wolfe P","year":"1970"}],"container-title":["Mathematics of Operations Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/pubsonline.informs.org\/doi\/pdf\/10.1287\/moor.2024.0580","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,5,8]],"date-time":"2026-05-08T08:27:09Z","timestamp":1778228829000},"score":1,"resource":{"primary":{"URL":"https:\/\/pubsonline.informs.org\/doi\/10.1287\/moor.2024.0580"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,5]]},"references-count":26,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2026,5]]}},"alternative-id":["10.1287\/moor.2024.0580"],"URL":"https:\/\/doi.org\/10.1287\/moor.2024.0580","relation":{},"ISSN":["0364-765X","1526-5471"],"issn-type":[{"value":"0364-765X","type":"print"},{"value":"1526-5471","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,5]]}}}