The Pivoting Framework: Frank-Wolfe Algorithms with Active Set Size Control

Mathieu Besançon, Sebastian Pokutta, Elias Samuel Wirth
Proceedings of The 28th International Conference on Artificial Intelligence and Statistics, PMLR 258:271-279, 2025.

Abstract

We propose the pivoting meta algorithm (PM) to enhance optimization algorithms that generate iterates as convex combinations of vertices of a feasible region $C\subseteq \mathbb{R}^n$, including Frank-Wolfe (FW) variants. PM guarantees that the active set (the set of vertices in the convex combination) of the modified algorithm remains as small as $dim(C)+1$ as stipulated by Carath{é}odory’s theorem. PM achieves this by reformulating the active set expansion task into an equivalent linear program, which can be efficiently solved using a single pivot step akin to the primal simplex algorithm; the convergence rate of the original algorithms are maintained. Furthermore, we establish the connection between PM and active set identification, in particular showing under mild assumptions that PM applied to the away-step Frank-Wolfe algorithm or the blended pairwise Frank-Wolfe algorithm bounds the active set size by the dimension of the optimal face plus $1$. We provide numerical experiments to illustrate practicality and efficacy on active set size reduction.

Cite this Paper

BibTeX
@InProceedings{pmlr-v258-besancon25a, title = {The Pivoting Framework: Frank-Wolfe Algorithms with Active Set Size Control}, author = {Besan{\c{c}}on, Mathieu and Pokutta, Sebastian and Wirth, Elias Samuel}, booktitle = {Proceedings of The 28th International Conference on Artificial Intelligence and Statistics}, pages = {271--279}, year = {2025}, editor = {Li, Yingzhen and Mandt, Stephan and Agrawal, Shipra and Khan, Emtiyaz}, volume = {258}, series = {Proceedings of Machine Learning Research}, month = {03--05 May}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v258/main/assets/besancon25a/besancon25a.pdf}, url = {https://proceedings.mlr.press/v258/besancon25a.html}, abstract = {We propose the pivoting meta algorithm (PM) to enhance optimization algorithms that generate iterates as convex combinations of vertices of a feasible region $C\subseteq \mathbb{R}^n$, including Frank-Wolfe (FW) variants. PM guarantees that the active set (the set of vertices in the convex combination) of the modified algorithm remains as small as $dim(C)+1$ as stipulated by Carath{é}odory’s theorem. PM achieves this by reformulating the active set expansion task into an equivalent linear program, which can be efficiently solved using a single pivot step akin to the primal simplex algorithm; the convergence rate of the original algorithms are maintained. Furthermore, we establish the connection between PM and active set identification, in particular showing under mild assumptions that PM applied to the away-step Frank-Wolfe algorithm or the blended pairwise Frank-Wolfe algorithm bounds the active set size by the dimension of the optimal face plus $1$. We provide numerical experiments to illustrate practicality and efficacy on active set size reduction.} }
Endnote
%0 Conference Paper %T The Pivoting Framework: Frank-Wolfe Algorithms with Active Set Size Control %A Mathieu Besançon %A Sebastian Pokutta %A Elias Samuel Wirth %B Proceedings of The 28th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2025 %E Yingzhen Li %E Stephan Mandt %E Shipra Agrawal %E Emtiyaz Khan %F pmlr-v258-besancon25a %I PMLR %P 271--279 %U https://proceedings.mlr.press/v258/besancon25a.html %V 258 %X We propose the pivoting meta algorithm (PM) to enhance optimization algorithms that generate iterates as convex combinations of vertices of a feasible region $C\subseteq \mathbb{R}^n$, including Frank-Wolfe (FW) variants. PM guarantees that the active set (the set of vertices in the convex combination) of the modified algorithm remains as small as $dim(C)+1$ as stipulated by Carath{é}odory’s theorem. PM achieves this by reformulating the active set expansion task into an equivalent linear program, which can be efficiently solved using a single pivot step akin to the primal simplex algorithm; the convergence rate of the original algorithms are maintained. Furthermore, we establish the connection between PM and active set identification, in particular showing under mild assumptions that PM applied to the away-step Frank-Wolfe algorithm or the blended pairwise Frank-Wolfe algorithm bounds the active set size by the dimension of the optimal face plus $1$. We provide numerical experiments to illustrate practicality and efficacy on active set size reduction.
APA
Besançon, M., Pokutta, S. & Wirth, E.S.. (2025). The Pivoting Framework: Frank-Wolfe Algorithms with Active Set Size Control. Proceedings of The 28th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 258:271-279 Available from https://proceedings.mlr.press/v258/besancon25a.html.

Related Material