Linear Convergence of the Frank-Wolfe Algorithm over Product Polytopes

Gabriele Iommazzo, David Martínez-Rubio, Francisco Criado, Elias Samuel Wirth, Sebastian Pokutta
Proceedings of The 29th International Conference on Artificial Intelligence and Statistics, PMLR 300:1063-1071, 2026.

Abstract

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 $\mu$-Polyak-{Ł}ojasiewicz, 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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v300-iommazzo26a, title = { Linear Convergence of the Frank-Wolfe Algorithm over Product Polytopes }, author = {Iommazzo, Gabriele and Mart{\'i}nez-Rubio, David and Criado, Francisco and Wirth, Elias Samuel and Pokutta, Sebastian}, booktitle = {Proceedings of The 29th International Conference on Artificial Intelligence and Statistics}, pages = {1063--1071}, year = {2026}, editor = {Khan, Emtiyaz and Li, Yingzhen and Solin, Arno and Ramdas, Aaditya}, volume = {300}, series = {Proceedings of Machine Learning Research}, month = {02--05 May}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v300/main/assets/iommazzo26a/iommazzo26a.pdf}, url = {https://proceedings.mlr.press/v300/iommazzo26a.html}, abstract = { 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 $\mu$-Polyak-{Ł}ojasiewicz, 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. } }
Endnote
%0 Conference Paper %T Linear Convergence of the Frank-Wolfe Algorithm over Product Polytopes %A Gabriele Iommazzo %A David Martínez-Rubio %A Francisco Criado %A Elias Samuel Wirth %A Sebastian Pokutta %B Proceedings of The 29th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2026 %E Emtiyaz Khan %E Yingzhen Li %E Arno Solin %E Aaditya Ramdas %F pmlr-v300-iommazzo26a %I PMLR %P 1063--1071 %U https://proceedings.mlr.press/v300/iommazzo26a.html %V 300 %X 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 $\mu$-Polyak-{Ł}ojasiewicz, 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.
APA
Iommazzo, G., Martínez-Rubio, D., Criado, F., Wirth, E.S. & Pokutta, S.. (2026). Linear Convergence of the Frank-Wolfe Algorithm over Product Polytopes . Proceedings of The 29th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 300:1063-1071 Available from https://proceedings.mlr.press/v300/iommazzo26a.html.

Related Material