2 citations · 4 across the 13 of their papers we have counts for
10 papers · 1 filter
Facial distance and diameter
Antoine Deza, David Martínez-Rubio, Javier Peña +1
The facial distance of a polytope, equivalently its pyramidal width, is a geometric condition measure that appears in the convergence bounds for Frank--Wolfe algorithms. Peña and W…
Calculus of the Facial Distance
Javier Pena, Elias Wirth
We develop a few calculus rules to compute or lower bound the facial distance of a polytope. We illustrate our calculus rules on various popular polytopes. In particular, we provid…
Adaptive Open-Loop Step-Sizes for Accelerated Convergence Rates of the Frank-Wolfe Algorithm
Elias Wirth, Javier Peña, Sebastian Pokutta
Recent work has shown that in certain settings, the Frank-Wolfe algorithm (FW) with open-loop step-sizes for a fixed parameter $\ell \in \mathbb{N},\, \…
Linear Convergence of the Frank-Wolfe Algorithm over Product Polytopes
Gabriele Iommazzo, David Martínez-Rubio, Francisco Criado +2
We study the linear convergence of Frank-Wolfe algorithms over product polytopes. We analyze two condition numbers for the product polytope, namely the \emph{pyramidal width} and t…
Improved algorithms and novel applications of the FrankWolfe.jl library
Mathieu Besançon, Sébastien Designolle, Jannis Halbey +6
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 algorith…
The Pivoting Framework: Frank-Wolfe Algorithms with Active Set Size Control
Elias Wirth, Mathieu Besançon, Sebastian Pokutta
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}…
Fast convergence of Frank-Wolfe algorithms on polytopes
Elias Wirth, Javier Pena, Sebastian Pokutta
We provide a template to derive convergence rates for the following popular versions of the Frank-Wolfe algorithm on polytopes: vanilla Frank-Wolfe, Frank-Wolfe with away steps, Fr…
Accelerated Affine-Invariant Convergence Rates of the Frank-Wolfe Algorithm with Open-Loop Step-Sizes
Elias Wirth, Javier Pena, Sebastian Pokutta
Recent papers have shown that the Frank-Wolfe algorithm (FW) with open-loop step-sizes exhibits rates of convergence faster than the iconic rate. In particula…
Accelerated and Sparse Algorithms for Approximate Personalized PageRank and Beyond
David Martínez-Rubio, Elias Wirth, Sebastian Pokutta
It has recently been shown that ISTA, an unaccelerated optimization method, presents sparse updates for the -regularized personalized PageRank problem, leading to cheap ite…
Acceleration of Frank-Wolfe Algorithms with Open-Loop Step-Sizes
Elias Wirth, Thomas Kerdreux, Sebastian Pokutta
Frank-Wolfe algorithms (FW) are popular first-order methods for solving constrained convex optimization problems that rely on a linear minimization oracle instead of potentially ex…