Improved algorithms and novel applications of the FrankWolfe.jl library
Mathieu Besançon [email protected], Sébastien Designolle [email protected], Jannis Halbey [email protected], Deborah Hendrych [email protected], Dominik Kuzinowicz [email protected], Sebastian Pokutta [email protected], Hannah Troppens [email protected], Daniel Viladrich Herrmannsdoerfer viladrich@zib. · 2025
Read Improved algorithms and novel applications of the FrankWolfe.jl library by Mathieu Besançon [email protected], Sébastien Designolle [email protected], Jannis Halbey [email protected], Deborah Hendrych [email protected], Dominik Kuzinowicz [email protected], Sebastian Pokutta [email protected], Hannah Troppens [email protected], Daniel Viladrich Herrmannsdoerfer viladrich@zib. (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2501-14613.txt.
Introduction
Besancon and co-authors summarize, in a 2025 paper, recent progress in a software library for Frank-Wolfe optimization methods. These methods solve constrained optimization problems by moving toward extreme points, and they shine on large scale problems where other methods are costly. The library, written in the Julia language, gathers fast implementations of the leading variants.
The package was built with two purposes. It aims to be the standard toolbox for practitioners who apply these methods. And it offers a modular playground for algorithm designers testing their own variants and building blocks. The paper reviews recent uses of the library in the literature, matching those two purposes. It then benchmarks several variants on important problem classes. Curated experiments show the performance on offer. The authors present the library as shared infrastructure for the optimization community.
Catalog record
| CREATOR | Mathieu Besançon [email protected], Sébastien Designolle [email protected], Jannis Halbey [email protected], Deborah Hendrych [email protected], Dominik Kuzinowicz [email protected], Sebastian Pokutta [email protected], Hannah Troppens [email protected], Daniel Viladrich Herrmannsdoerfer viladrich@zib. |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 90 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2501-14613
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Improved algorithms and novel applications of the FrankWolfe.jl library Mathieu Besançon [email protected], Sébastien Designolle [email protected], Jannis Halbey [email protected], Deborah Hendrych [email protected], Dominik Kuzinowicz [email protected], Sebastian Pokutta [email protected], Hannah Troppens [email protected], Daniel Viladrich Herrmannsdoerfer [email protected], Elias Wirth [email protected] Abstract Frank-Wolfe (FW) algorithms have emerged as an essential class of methods for constrained optimization, especially on large-scale problems. In this paper, we summarize the algorithmic design choices and progress made in the last years of the development of FrankWolfe.jl, a Julia package gathering high-performance implementations of state-of-the-art FW variants. We review key use cases of the library in the recent literature, which match its original dual purpose: first, becoming the de-facto toolbox for practitioners applying FW methods to their problem, and second, offering a modular ecosystem to algorithm designers who experiment with their own variants and implementations of algorithmic blocks. Finally, we demonstrate the performance of several FW variants on important problem classes in several experiments, which we curated in a separate repository for continuous benchmarking. 1 Introduction In the last decade, Frank-Wolfe (FW) algorithms have gained significant traction in various applications at the intersection of constrained and nonlinear optimization. We present a summary of progress made over the last years of the FrankWolfe.jl package, including recent advances in FW algorithms that have been integrated into the package, its extensions developed as companion packages, and selected applications from the literature that leveraged FrankWolfe.jl for computational experiments or further development of other software libraries. FrankWolfe.jl was initially introduced in Besançon et al. (2022) after its release in 2021 and we refer interested readers to this article for prominent features of the first releases. In this paper, we will primarily highlight progress made after this initial publication and available in the 0.4.7 version. The rest of this paper is structured as follows. Section 2 introduces the new FW-based algorithms implemented in the package, Section 3 reviews the different step-size strategies introduced from the literature, Section 4 details new feasible regions and corresponding linear minimization oracles. Section 5 presents the new active set abstraction and different implementations for specific use cases. Section 6 introduces mechanisms to dynamically modify the algorithm run. The appendix contains the pseudo-code for the main new FW variants, a selection of recent applications of the package in the literature, and a benchmark suite and results we developed to monitor the performance of the different algorithms. Throughout the paper and unless specified otherwise, we will consider optimization problems of the form: \displaystyle\min_{\mathbf{x}\in{\mathcal{X}}{}}\; \displaystyle f(\mathbf{x}), with {\mathcal{X}}{} a closed, convex subset of a Hilbert space and f:{\mathcal{X}}{}\rightarrow\mathbb{R} a differentiable objective function. The iteration count of algorithms will be denoted with t and the iterate at the current iteration as \mathbf{x}_{t} . For n\in\mathbb{N} , we also note [n]:=\{1,\dots,n\} . We denote the unit simplex in \mathbb{R}^{n} as \Delta_{n} . We will now briefly outline the algorithmic improvements and developments in FrankWolfe.jl, including new algorithms, step-size strategies, and oracles. 2 New Frank-Wolfe algorithms In the following, we provide an overview of new FW variants implemented in FrankWolfe.jl. For details on the algorithms and theoretical guarantees, we refer the interested reader to the original papers. The pseudo-code for the different algorithms are presented in Appendix A . 2.1 Blended Pairwise Conditional Gradients (BPCG) The Blended Pairwise Conditional Gradients (BPCG) algorithm from Tsuji et al. (2022) is an improved variant of the Pairwise Conditional Gradients (PCG) method. Unlike PCG, BPCG eliminates swap steps, which may hinder primal progress and limit applicability in infinite-dimensional settings. BPCG combines PCG with the blending criterion from the Blended Conditional Gradients (BCG) algorithm ( Braun et al., 2019a ) , leading to better convergence rates and improved performance. It is straightforward to implement, avoids complex gradient alignment procedures (such as the ones, e.g., in Rinaldi & Zeffiro (2020) ; Rinaldi & Zeffiro (2023) ), and ensures solutions are sparse, making it particularly effective for applications like sparse signal recovery and kernel herding. Numerical experiments in Tsuji et al. (2022) demonstrate that BPCG produces sparser solutions than PCG, offering significant advantages in computational efficiency and performance, which is in line with the performance evaluation of our implementation in FrankWolfe.jl and of the benchmarks presented in Appendix C . The pseudo-code is provided in Algorithm 2 in Appendix A . The implementation in FrankWolfe.jl uses the relaxed criterion with \kappa=2.0 from ( Tsuji et al., 2022 , Section 3.4) in Line ( 8 ) instead of \kappa=1.0 , for significantly enhanced sparsity while maintaining almost identical convergence speed in iteration and time. In the description of Algorithm 2 we use c[\mathbf{x}_{t}](\mathbf{a}_{t}) to denote the weight of \mathbf{a}_{t} in the convex decomposition of \mathbf{x}_{t} that the algorithm maintains. This is the current default FW variant if an active set can be maintained. We highlight that sparsity of the active set provides multiple algorithmic advantages, including faster convergence (see Section 6.2 ) and lower iteration costs, since active set operations usually have a cost linear in the number of vertices. 2.2 Pairwise Conditional Gradients (PCG) We added an implementation of the Pairwise Conditional Gradients (PCG) from Lacoste-Julien & Jaggi (2015) similar to the Away-step Frank-Wolfe algorithm in FrankWolfe.jl. PCG performs a pairwise step which consists in a direction \mathbf{d}_{t}:=\mathbf{a}_{t}-\mathbf{v}_{t} following notation of Algorithm 2 . The algorithm also features an optional lazification mechanism introduced in Braun et al. (2019b) similar to the other ones, i.e., the possibility to avoid expensive calls to the exact linear minimization oracle (LMO) at every iteration, using vertices readily available for directions and maintaining an estimate of the dual gap. 2.3 Decomposition-Invariant Conditional Gradients (DICG) The Decomposition-Invariant Conditional Gradients (DICG) corresponds to the algorithm defined in Garber & Meshi (2016) for the case of “simplex-like” polytopes and Bashiri & Zhang (2017) for general polytopes. The motivation for the algorithm is two-fold. First, typically fast FW variants on polytopes rely on an active set which induces a storage cost at least proportional to the active set complexity of the optimal solution and to the size of the in-memory representation of the vertices. Second, the evolution of the convex decomposition of the iterates throughout the algorithm depends on the steps that are performed and the set of directions available for local steps (i.e., steps depending on the active set) depends on the current convex decomposition. DICG thus aims at building decomposition-invariant iterations that do not rely on storage nor exploitation of a set of active vertices. We consider the case of polytopes inscribed in the 0-1 hypercube for simplicity of exposure. We will denote the current face of the iterate \mathbf{x} : \displaystyle{\mathcal{F}(\mathbf{x})}=\{\mathbf{y}\in{\mathcal{X}},y_{i}=x_{i}\penalty\ \forall i\in[n],x_{i}\in\{0,1\}\}. The key aspect of DICG is considering “extended” linear minimization oracles that can compute extreme points of a face of the polytope. In many cases, such a restricted oracle is not computationally more expensive than the original oracle and will reduce the algorithm complexity compared to the original LMO. As an example, the standard LMO for the Birkhoff polytope consists of performing the Hungarian algorithm with the costs provided by the gradient. The decomposition-invariant oracle also requires being able to fix a variable to zero, which consists in forbidding a row/column pair in the Hungarian algorithm, or to fix a variable to one, which removes a row