{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,31]],"date-time":"2025-12-31T00:16:26Z","timestamp":1767140186115,"version":"build-2238731810"},"reference-count":47,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2025,1,6]],"date-time":"2025-01-06T00:00:00Z","timestamp":1736121600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,1,6]],"date-time":"2025-01-06T00:00:00Z","timestamp":1736121600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["390685689"],"award-info":[{"award-number":["390685689"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2025,11]]},"abstract":"Abstract<\/jats:title>\n \n Recent papers have shown that the Frank\u2013Wolfe algorithm () with open-loop step-sizes exhibits rates of convergence faster than the iconic\n \n \n $$\\mathcal {O}(t^{-1})$$<\/jats:tex-math>\n \n \n O<\/mml:mi>\n (<\/mml:mo>\n \n t<\/mml:mi>\n \n -<\/mml:mo>\n 1<\/mml:mn>\n <\/mml:mrow>\n <\/mml:msup>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n rate. In particular, when the minimizer of a strongly convex function over a polytope lies on the boundary of the polytope, the algorithm with open-loop step-sizes\n \n \n $$\\eta _t = \\frac{\\ell }{t+\\ell }$$<\/jats:tex-math>\n \n \n \n \u03b7<\/mml:mi>\n t<\/mml:mi>\n <\/mml:msub>\n =<\/mml:mo>\n \n \u2113<\/mml:mi>\n \n t<\/mml:mi>\n +<\/mml:mo>\n \u2113<\/mml:mi>\n <\/mml:mrow>\n <\/mml:mfrac>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n for\n \n \n $$\\ell \\in \\mathbb {N}_{\\ge 2}$$<\/jats:tex-math>\n \n \n \u2113<\/mml:mi>\n \u2208<\/mml:mo>\n \n N<\/mml:mi>\n \n \u2265<\/mml:mo>\n 2<\/mml:mn>\n <\/mml:mrow>\n <\/mml:msub>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n has accelerated convergence\n \n \n $$\\mathcal {O}(t^{-2})$$<\/jats:tex-math>\n \n \n O<\/mml:mi>\n (<\/mml:mo>\n \n t<\/mml:mi>\n \n -<\/mml:mo>\n 2<\/mml:mn>\n <\/mml:mrow>\n <\/mml:msup>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n in contrast to the rate\n \n \n $$\\Omega (t^{-1-\\epsilon })$$<\/jats:tex-math>\n \n \n \u03a9<\/mml:mi>\n (<\/mml:mo>\n \n t<\/mml:mi>\n \n -<\/mml:mo>\n 1<\/mml:mn>\n -<\/mml:mo>\n \u03f5<\/mml:mi>\n <\/mml:mrow>\n <\/mml:msup>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n attainable with more complex line-search or short-step step-sizes. Given the relevance of this scenario in data science problems, research has grown to explore the settings enabling acceleration in open-loop . However, despite \u2019s well-known affine invariance, existing acceleration results for open-loop are affine-dependent. This paper remedies this gap in the literature, by merging two recent research trajectories: affine invariance (Pe\u00f1a in SIAM J. Optim. 33(4):2654\u20132674, 2023) and open-loop step-sizes (Wirth et al. in Proceedings of the International Conference on Artificial Intelligence and Statistics, 2023). In particular, we extend all known non-affine-invariant convergence rates for with open-loop step-sizes to affine-invariant results.\n <\/jats:p>","DOI":"10.1007\/s10107-024-02180-2","type":"journal-article","created":{"date-parts":[[2025,1,6]],"date-time":"2025-01-06T08:51:02Z","timestamp":1736153462000},"page":"201-245","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Accelerated affine-invariant convergence rates of the Frank\u2013Wolfe algorithm with open-loop step-sizes"],"prefix":"10.1007","volume":"214","author":[{"given":"Elias","family":"Wirth","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5698-1918","authenticated-orcid":false,"given":"Javier","family":"Pe\u00f1a","sequence":"additional","affiliation":[]},{"given":"Sebastian","family":"Pokutta","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,1,6]]},"reference":[{"issue":"4","key":"2180_CR1","doi-asserted-by":"publisher","first-page":"1251","DOI":"10.1137\/21M1397349","volume":"3","author":"F Bach","year":"2021","unstructured":"Bach, F.: On the effectiveness of Richardson extrapolation in data science. SIAM J. Math. Data Sci. 3(4), 1251\u20131277 (2021)","journal-title":"SIAM J. Math. Data Sci."},{"key":"2180_CR2","unstructured":"Bach, F., Lacoste-Julien, S., Obozinski, G.: On the equivalence between herding and conditional gradient algorithms. In: Proceedings of the International Conference on Machine Learning, pp. 1355\u20131362. PMLR (2012)"},{"key":"2180_CR3","unstructured":"Braun, G., Carderera, A., Combettes, C.W., Hassani, H., Karbasi, A., Mokhtari, A., Pokutta, S.: Conditional gradient methods. arXiv preprintarXiv:2211.14103 (2022)"},{"key":"2180_CR4","unstructured":"Braun, G., Pokutta, S., Tu, D., Wright, S.: Blended conditonal gradients. In: Proceedings of the International Conference on Machine Learning, pp. 735\u2013743. PMLR (2019)"},{"key":"2180_CR5","unstructured":"Bugg, C. X., Chen, C., Aswani, A.: Nonnegative tensor completion via integer optimization. In: Alice H. H., Alekh, A., Danielle, B., Kyunghyun, C. (eds.) Proceedings of Advances in Neural Information Processing Systems (2022)"},{"key":"2180_CR6","unstructured":"Carderera, A., Pokutta, S., Sch\u00fctte, C., Weiser, M.: CINDy: conditional gradient-based identification of non-linear dynamics\u2013noise-robust recovery. arXiv preprintarXiv:2101.02630 (2021)"},{"issue":"4","key":"2180_CR7","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1824777.1824783","volume":"6","author":"KL Clarkson","year":"2010","unstructured":"Clarkson, K.L.: Coresets, sparse greedy approximation, and the Frank\u2013Wolfe algorithm. ACM Trans. Algorithms 6(4), 1\u201330 (2010)","journal-title":"ACM Trans. Algorithms"},{"issue":"9","key":"2180_CR8","doi-asserted-by":"publisher","first-page":"1853","DOI":"10.1109\/TPAMI.2016.2615921","volume":"39","author":"N Courty","year":"2016","unstructured":"Courty, N., Flamary, R., Tuia, D., Rakotomamonjy, A.: Optimal transport for domain adaptation. IEEE Trans. Pattern Anal. Mach. Intell. 39(9), 1853\u20131865 (2016)","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"issue":"2","key":"2180_CR9","doi-asserted-by":"publisher","first-page":"432","DOI":"10.1016\/0022-247X(78)90137-3","volume":"62","author":"JC Dunn","year":"1978","unstructured":"Dunn, J.C., Harshbarger, S.: Conditional gradient algorithms with open loop step size rules. J. Math. Anal. Appl. 62(2), 432\u2013444 (1978)","journal-title":"J. Math. Anal. Appl."},{"issue":"1\u20132","key":"2180_CR10","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1002\/nav.3800030109","volume":"3","author":"M Frank","year":"1956","unstructured":"Frank, M., Wolfe, P.: An algorithm for quadratic programming. Naval Res. Logist. Q. 3(1\u20132), 95\u2013110 (1956)","journal-title":"Naval Res. Logist. Q."},{"issue":"1","key":"2180_CR11","doi-asserted-by":"publisher","first-page":"727","DOI":"10.1137\/18M1233170","volume":"31","author":"D Garber","year":"2021","unstructured":"Garber, D.: On the convergence of projected-gradient methods with low-rank projections for smooth convex minimization over trace-norm balls and related problems. SIAM J. Optim. 31(1), 727\u2013753 (2021)","journal-title":"SIAM J. Optim."},{"key":"2180_CR12","unstructured":"Garber, D., Hazan, E.: Faster rates for the Frank-Wolfe method over strongly-convex sets. In: Proceedings of the International Conference on Machine Learning. PMLR (2015)"},{"key":"2180_CR13","unstructured":"Garber, D., Meshi, O.: Linear-memory and decomposition-invariant linearly convergent conditional gradient algorithm for structured polytopes. In: Proceedings of the International Conference on Neural Information Processing Systems, pp. 1009\u20131017. PMLR (2016)"},{"key":"2180_CR14","unstructured":"Garber, D., Sabach, S., Kaplan, A.: Fast generalized conditional gradient method with applications to matrix recovery problems. arXiv preprintarXiv:1802.05581, 3 (2018)"},{"key":"2180_CR15","doi-asserted-by":"publisher","first-page":"431","DOI":"10.1007\/s10107-017-1225-5","volume":"173","author":"S Ghadimi","year":"2019","unstructured":"Ghadimi, S.: Conditional gradient type methods for composite nonlinear and stochastic optimization. Math. Program. 173, 431\u2013464 (2019)","journal-title":"Math. Program."},{"issue":"1","key":"2180_CR16","doi-asserted-by":"publisher","first-page":"110","DOI":"10.1007\/BF01589445","volume":"35","author":"J Gu\u00e9lat","year":"1986","unstructured":"Gu\u00e9lat, J., Marcotte, P.: Some comments on Wolfe\u2019s \u2018away step\u2019. Math. Program. 35(1), 110\u2013119 (1986)","journal-title":"Math. Program."},{"key":"2180_CR17","doi-asserted-by":"crossref","unstructured":"Guo, X., Yao, Q., Kwok, J.: Efficient sparse low-rank tensor completion using the Frank\u2013Wolfe algorithm. In: Proceedings of the AAAI Conference on Artificial Intelligence, volume\u00a031 (2017)","DOI":"10.1609\/aaai.v31i1.10886"},{"key":"2180_CR18","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1007\/s10107-020-01510-4","volume":"188","author":"DH Gutman","year":"2021","unstructured":"Gutman, D.H., Pena, J.F.: The condition number of a function relative to a set. Math. Program. 188, 255\u2013294 (2021)","journal-title":"Math. Program."},{"issue":"Mar","key":"2180_CR19","first-page":"1157","volume":"3","author":"I Guyon","year":"2003","unstructured":"Guyon, I., Elisseeff, A.: An introduction to variable and feature selection. J. Mach. Learn. Res. 3(Mar), 1157\u20131182 (2003)","journal-title":"J. Mach. Learn. Res."},{"issue":"3","key":"2180_CR20","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1007\/BF02589410","volume":"3","author":"O Hanner","year":"1956","unstructured":"Hanner, O.: On the uniform convexity of l p and l p. Ark. Mat. 3(3), 239\u2013244 (1956)","journal-title":"Ark. Mat."},{"issue":"4","key":"2180_CR21","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2827872","volume":"5","author":"F Maxwell Harper","year":"2015","unstructured":"Maxwell Harper, F., Konstan, J.A.: The movielens datasets: history and context. ACM Trans. Interact. Intell. Syst. 5(4), 1\u201319 (2015)","journal-title":"ACM Trans. Interact. Intell. Syst."},{"key":"2180_CR22","volume-title":"Fundamentals of Convex Analysis","author":"J-B Hiriart-Urruty","year":"2004","unstructured":"Hiriart-Urruty, J.-B., Lemar\u00e9chal, C.: Fundamentals of Convex Analysis. Springer, Berlin (2004)"},{"issue":"1","key":"2180_CR23","doi-asserted-by":"publisher","first-page":"14","DOI":"10.1007\/BF01580219","volume":"6","author":"CA Holloway","year":"1974","unstructured":"Holloway, C.A.: An extension of the Frank and Wolfe method of feasible directions. Math. Program. 6(1), 14\u201327 (1974)","journal-title":"Math. Program."},{"key":"2180_CR24","doi-asserted-by":"crossref","unstructured":"Huber, P.J.: Robust estimation of a location parameter. Breakthroughs in statistics: methodology and distribution, pp 492\u2013518 (1992)","DOI":"10.1007\/978-1-4612-4380-9_35"},{"key":"2180_CR25","unstructured":"Jaggi, M.: Revisiting Frank\u2013Wolfe: projection-free sparse convex optimization. In: Proceedings of the International Conference on Machine Learning, pp. 427\u2013435. PMLR (2013)"},{"key":"2180_CR26","doi-asserted-by":"crossref","unstructured":"Joulin, A., Tang, K., Fei-Fei, L.: Efficient image and video co-localization with Frank\u2013Wolfe algorithm. In: Computer Vision\u2014ECCV 2014, pp. 253\u2013268. Springer, Cham (2014)","DOI":"10.1007\/978-3-319-10599-4_17"},{"key":"2180_CR27","unstructured":"Kerdreux, T., d\u2019Aspremont, A., Pokutta, S.: Projection-free optimization on uniformly convex sets. In: Proceedings of the International Conference on Artificial Intelligence and Statistics, pp. 19\u201327. PMLR (2021)"},{"key":"2180_CR28","unstructured":"Kerdreux, T., Liu, L., Lacoste-Julien, S., Scieur, D.: Affine invariant analysis of Frank\u2013Wolfe on strongly convex sets. In: Proceedings of the International Conference on Machine Learning, pp. 5398\u20135408. PMLR (2021)"},{"key":"2180_CR29","unstructured":"Lacoste-Julien, S., Jaggi, M.: An affine invariant linear convergence analysis for Frank\u2013Wolfe algorithms. arXiv preprintarXiv:1312.7864 (2013)"},{"key":"2180_CR30","unstructured":"Lacoste-Julien, S., Jaggi, M.: On the global linear convergence of Frank\u2013Wolfe optimization variants. In: Proceedings of Advances in Neural Information Processing Systems, pp. 496\u2013504 (2015)"},{"issue":"5","key":"2180_CR31","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0041-5553(66)90114-5","volume":"6","author":"ES Levitin","year":"1966","unstructured":"Levitin, E.S., Polyak, B.T.: Constrained minimization methods. USSR Comput. Math. Math. Phys. 6(5), 1\u201350 (1966)","journal-title":"USSR Comput. Math. Math. Phys."},{"key":"2180_CR32","doi-asserted-by":"publisher","first-page":"3597","DOI":"10.1109\/TSP.2021.3087910","volume":"69","author":"B Li","year":"2021","unstructured":"Li, B., Coutino, M., Giannakis, G.B., Leus, G.: A momentum-guided Frank\u2013Wolfe algorithm. IEEE Trans. Signal Process. 69, 3597\u20133611 (2021)","journal-title":"IEEE Trans. Signal Process."},{"key":"2180_CR33","unstructured":"Macdonald, J., Besan\u00e7on, M.E., Pokutta, S.: Interpretable neural networks with Frank\u2013Wolfe: sparse relevance maps and relevance orderings. In: Proceedings of the International Conference on Machine Learning, pp. 14699\u201314716. PMLR (2022)"},{"key":"2180_CR34","doi-asserted-by":"crossref","unstructured":"Matsuoka, Y.: An elementary proof of the formula $$\\backslash \\text{sum}^\\wedge \\text{ k }=11\/\\text{k}^\\wedge \\,2=\\pi ^\\wedge \\,2\/6$$. Am. Math. Mon. 68(5), 485\u2013487 (1961)","DOI":"10.2307\/2311110"},{"key":"2180_CR35","doi-asserted-by":"crossref","unstructured":"Mehta, B., Hofmann, T., Nejdl, W.: Robust collaborative filtering. In: Proceedings of the ACM Conference on Recommender Systems, pp. 49\u201356 (2007)","DOI":"10.1145\/1297231.1297240"},{"issue":"5","key":"2180_CR36","doi-asserted-by":"publisher","first-page":"A3291","DOI":"10.1137\/15M101628X","volume":"38","author":"M Cun","year":"2016","unstructured":"Cun, M., Zhang, Y., Wright, J., Goldfarb, D.: Scalable robust matrix recovery: Frank\u2013Wolfe meets proximal methods. SIAM J. Sci. Comput. 38(5), A3291\u2013A3317 (2016)","journal-title":"SIAM J. Sci. Comput."},{"issue":"1\u20132","key":"2180_CR37","doi-asserted-by":"publisher","first-page":"311","DOI":"10.1007\/s10107-017-1188-6","volume":"171","author":"Yu Nesterov","year":"2018","unstructured":"Nesterov, Yu.: Complexity bounds for primal-dual methods minimizing the model of objective function. Math. Program. 171(1\u20132), 311\u2013330 (2018)","journal-title":"Math. Program."},{"key":"2180_CR38","unstructured":"Paty, F.-P., Cuturi, M.: Subspace robust wasserstein distances. In: Proceedings of the International Conference on Machine Learning, pp. 5072\u20135081. PMLR (2019)"},{"key":"2180_CR39","unstructured":"Pedregosa, F., Askari, A., Negiar, G., Jaggi, M.: Step-size adaptivity in projection-free optimization. arXiv preprintarXiv:1806.05123 (2018)"},{"issue":"4","key":"2180_CR40","doi-asserted-by":"publisher","first-page":"2654","DOI":"10.1137\/21M1465263","volume":"33","author":"JF Pe\u00f1a","year":"2023","unstructured":"Pe\u00f1a, J.F.: Affine invariant convergence rates of the conditional gradient method. SIAM J. Optim. 33(4), 2654\u20132674 (2023)","journal-title":"SIAM J. Optim."},{"key":"2180_CR41","unstructured":"Pokutta, S.: The Frank\u2013Wolfe algorithm: a short introduction. arXiv preprintarXiv:2311.05313 (2023)"},{"key":"2180_CR42","unstructured":"Ravi, S.N., Dinh, T., Lokhande, V., Vikas, S.: Constrained deep learning using conditional gradient and applications in computer vision. arXiv preprintarXiv:1803.06453 (2018)"},{"key":"2180_CR43","unstructured":"Tsuji, K.K., Tanaka, K., Pokutta, S.: Pairwise conditional gradients without swap steps and sparser kernel herding. In: Proceedings of the International Conference on Machine Learning, pp. 21864\u201321883. PMLR (2022)"},{"key":"2180_CR44","unstructured":"Wirth, E., Kera, H., Pokutta, S.: Approximate vanishing ideal computations at scale. In: Proceedings of the International Conference on Learning Representations (2023)"},{"key":"2180_CR45","unstructured":"Wirth, E., Kerdreux, T., Pokutta, S.: Acceleration of Frank\u2013Wolfe algorithms with open-loop step-sizes. In: Proceedings of the International Conference on Artificial Intelligence and Statistics, pp. 77\u2013100. PMLR (2023)"},{"key":"2180_CR46","unstructured":"Wirth, E., Pokutta, S..: Conditional gradients for the approximately vanishing ideal. In: Proceedings of the International Conference on Artificial Intelligence and Statistics, pp. 2191\u20132209. PMLR (2022)"},{"key":"2180_CR47","unstructured":"Wolfe, P.: Convergence theory in nonlinear programming. In Abadie, J. (ed.) Integer and Nonlinear Programming. North-Holland, Amsterdam (1970)"}],"updated-by":[{"DOI":"10.1007\/s10107-025-02214-3","type":"correction","label":"Correction","source":"publisher","updated":{"date-parts":[[2025,3,13]],"date-time":"2025-03-13T00:00:00Z","timestamp":1741824000000}}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-024-02180-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-024-02180-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-024-02180-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,12,1]],"date-time":"2025-12-01T07:42:21Z","timestamp":1764574941000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-024-02180-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,1,6]]},"references-count":47,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2025,11]]}},"alternative-id":["2180"],"URL":"https:\/\/doi.org\/10.1007\/s10107-024-02180-2","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,1,6]]},"assertion":[{"value":"9 October 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 December 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 January 2025","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 March 2025","order":5,"name":"change_date","label":"Change Date","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"Update","order":6,"name":"change_type","label":"Change Type","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"The original online version of this article was revised, because the words covariance and covariant in Definition 1.1 were incorrect. The correct words should be covariant and invariant respectively. The correct sentence should be \"Instead, when an algorithm is affine covariant, some key features such as its convergence rate, must be affine invariant.\"","order":7,"name":"change_details","label":"Change Details","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 March 2025","order":8,"name":"change_date","label":"Change Date","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"Correction","order":9,"name":"change_type","label":"Change Type","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"A Correction to this paper has been published:","order":10,"name":"change_details","label":"Change Details","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"https:\/\/doi.org\/10.1007\/s10107-025-02214-3","URL":"https:\/\/doi.org\/10.1007\/s10107-025-02214-3","order":11,"name":"change_details","label":"Change Details","group":{"name":"ArticleHistory","label":"Article History"}}]}}