Linear Convergence of the Frank-Wolfe Algorithm over Product Polytopes
Gabriele Iommazzo, David Martínez-Rubio, Francisco Criado, Elias Wirth, Sebastian Pokutta · 2025
Read Linear Convergence of the Frank-Wolfe Algorithm over Product Polytopes by Gabriele Iommazzo, David Martínez-Rubio, Francisco Criado, Elias Wirth, Sebastian Pokutta (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-2505-11259.txt.
Introduction
Gabriele Iommazzo and co-authors prove fast convergence for the Frank-Wolfe algorithm on product polytopes in this 2025 paper. Frank-Wolfe solves smooth optimization problems using only linear steps. Its speed depends on the shape of the feasible region. Product polytopes arise when several simple regions are combined into one larger problem.
Two shape measures are analyzed for products, the pyramidal width and the vertex facet distance. Both are bounded from the measures of the parts. For objectives with a Polyak-Lojasiewicz property, linear convergence rates follow from those bounds. A test problem asks for a feasible point in a high dimensional polytope intersection. Experiments confirm the theory runs efficiently in practice. The work extends known fast rates to combined domains.
Catalog record
| CREATOR | Gabriele Iommazzo, David Martínez-Rubio, Francisco Criado, Elias Wirth, Sebastian Pokutta |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 76 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2505-11259
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Linear Convergence of the Frank-Wolfe Algorithm over Product Polytopes Gabriele Iommazzo, David Martínez-Rubio, Francisco Criado, Elias Wirth, Sebastian Pokutta 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. 1 Introduction Frank-Wolfe algorithms ( FW ), also known as Conditional Gradient methods, are widely used first-order optimization algorithms. They are particularly suited for constrained convex problems \min_{x\in\mathcal{X}}f(x) , for a convex compact set \mathcal{X} , where linear minimization over \mathcal{X} is used to keep the iterates feasible. The simplicity of this family of methods, along with its projection-free nature, make it especially appealing in large-scale settings, where projections can be costly. This is often the case when the feasible set is a polytope [ BCC+22 ] . More concretely, FW methods compute iterates as combinations of extreme points in the feasible set \mathcal{X} returned by a linear minimization oracle ( LMO ): g\mapsto\argmin_{x\in\mathcal{X}}\left\langle g,x\right\rangle (LMO) on \mathcal{X} , where g is some vector, usually the current gradient of the objective function or an approximation thereof. After computing ( LMO ), the standard FW method takes a step from the current iterate in the direction of the LMO solution. In many scenarios, ( LMO ) is a cheaper alternative to the quadratic optimization problem that projections consist of, cf. [ Jag13 ] , and can be computed even when \mathcal{X} is defined implicitly, such as a convex hull of a set of points. The convergence behavior of Frank-Wolfe methods is strongly influenced by the geometry of the constraint set, that of the function, and the location of the unconstrained minimizer. While sublinear rates are typical in general convex and smooth settings, it is known that linear convergence can be achieved under additional assumptions, such as global optimizers being in the interior of \mathcal{X} [ Wol70 , GM86 ] , strong convexity of the feasible set along with all global optimizers being outside of it [ LP66 ] , or strong convexity of f for \mathcal{X} being a polytope having some positive condition number. This last assumption holds for one of several different notions of conditioning that have been defined [ LJ13 , GH15 , LJ15 , BS15 , PRS16 , PR18 ] , among which there is the pyramidal width and the vertex-facet distance that we use in this paper, cf. Section 4 . A few works extend the applicability of the algorithms to larger classes of functions such as the ones satisfying the Polyak-Łojasiewicz ( PL ) condition, as opposed to strong convexity [ BS15 , BCC+22 ] . We quantify the implications of our condition number results in terms of linear convergence rates for our applications. Importantly, we note that much of the aforementioned theory remains confined to the setting of single polytopes, with limited understanding of how favorable properties like good condition numbers might extend and compose in more structured domains. In this work, we focus on optimization over product polytopes . This setting arises naturally in machine learning applications, specially via the feasibility problem for the intersection of several feasible sets, such as in image representation in computerized tomography [ CCC+12 ] , compressed sensing [ CCG12 ] , and including signal processing and statistical estimation [ SYY98 , CP11 ] , image recovery [ Com96 ] , absolute value equations [ ACT23 ] , matrix completion [ RSV12 ] and robust PCA [ MA18 ] , SVMs [ LJS+13 ] and clustering [ BRZ24 ] . A natural question is whether the good conditioning of individual polytopes can be lifted to the product domain in a way that still allows for linear convergence guarantees. We provide a surprising positive answer as the main contribution of this work: the product of well-conditioned polytopes inherits a form of good conditioning , that enables linear convergence of FW algorithms for smooth, convex, PL -objectives by using either the pyramidal width or the vertex-facet distance. Positive polytope condition numbers, such as the pyramidal width or the vertex-facet distance, typically capture how well the directions found by the LMO in the polytope align with the idealized direction x^{\ast}-x_{t} (from an iterate x_{t} towards a minimizer x^{\ast} ) relative to the direction of the gradient that was used for the LMO , cf. Section A.4 . Our findings imply that this alignment does not degrade much when considering a product polytope, with respect to the individual components. We apply our results to the aforementioned important primitive in large-scale optimization: approximately finding a feasible point in the intersection of several polytopes or certifying that such intersection is empty. In other words, the problem of interest is, given k\geq 2 polytopes \mathcal{P}_{i} , \text{find }x\in\bigcap_{i=1}^{k}\mathcal{P}_{i}\,, (P) if it exists, or determine that the intersection is empty. An \varepsilon -approximate solution of ( P ) consists of finding a point whose Euclidean distance to the intersection is less than \varepsilon , or determining that no such point exists. Finding an approximate feasible point in the intersection of k polytopes can be turned into an approximate solver for linear programming over such intersection as feasible set, by performing a binary search objective value, see, e.g., [ DVZ22 ] and references therein. For the above task, we consider the Away Frank-Wolfe ( AFW ) algorithm [ GM86a ] (see Algorithm 1 in Appendix B ) over the Cartesian product, where we have a variable for each polytope and minimize an objective that penalizes each of the pairwise distances between the k variables, cf. ( 4 ). Our objective is convex, smooth and satisfies the PL inequality. Naturally, this approach uses the LMO of the resulting product polytope that is the product of the corresponding LMO outputs for each polytope component, that can be computed in parallel. Our technical contributions are the following. Contributions • Regarding polytope condition numbers, we show that, if the pyramidal widths of two polytopes \mathcal{P}_{1} and \mathcal{P}_{2} are \delta_{\mathcal{P}_{1}} and \delta_{\mathcal{P}_{2}} , that of the product is exactly \delta_{\mathcal{P}_{1}}\delta_{\mathcal{P}_{2}}/\sqrt{\delta_{\mathcal{P}_{1}}^{2}+\delta_{\mathcal{P}_{2}}^{2}} . This yields a pyramidal width \delta_{\mathcal{P}}=\Omega(\frac{1}{\sqrt{k}}\min_{i\in[k]}\delta_{\mathcal{P}_{i}}) for the product \mathcal{P}=\prod_{i\in[k]}\mathcal{P}_{i} of k polytopes. Our proof uses the affine pyramidal width , which we introduce as a new equivalent characterization of the pyramidal width that is easier to work with in our proofs. Similarly, for the vertex-facet distance , we show \mathsf{vf}_{\mathcal{P}}=\min_{i\in[k]}\mathsf{vf}_{\mathcal{P}_{i}} . • As a consequence of studying these two polytope condition numbers, we can quantify linear rates of convergence for the AFW algorithm optimizing convex, smooth functions satisfying the PL inequality over a product polytope, which inherits its conditioning from the components. • We apply our results to the problem of approximately finding a feasible point in the intersection of several polytopes, by minimizing ( 4 ), a convex, smooth and PL objective. • We substantiate our theoretical findings