2 citations · 4 across the 13 of their papers we have counts for
15 papers
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…
Approximating Latent Manifolds in Neural Networks via Vanishing Ideals
Nico Pelleriti, Max Zimmer, Elias Wirth +1
Deep neural networks have reshaped modern machine learning by learning powerful latent representations that often align with the manifold hypothesis: high-dimensional data lie on l…
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…
Approximate Vanishing Ideal Computations at Scale
Elias Wirth, Hiroshi Kera, Sebastian Pokutta
The vanishing ideal of a set of points is the set of polynomials that evaluate to over all points $\mathbf{x}…
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…
Conditional Gradients for the Approximate Vanishing Ideal
Elias Wirth, Sebastian Pokutta
The vanishing ideal of a set of points is the set of polynomials that evaluate to over all points and admits an efficient represent…
SoS certification for symmetric quadratic functions and its connection to constrained Boolean hypercube optimization
Adam Kurpisz, Aaron Potechin, Elias Samuel Wirth
We study the rank of the Sum of Squares (SoS) hierarchy over the Boolean hypercube for Symmetric Quadratic Functions (SQFs) in variables with roots placed in points and $…
Efficient Online-Bandit Strategies for Minimax Learning Problems
Christophe Roux, Elias Wirth, Sebastian Pokutta +1
Several learning problems involve solving min-max problems, e.g., empirical distributional robust learning or learning with non-standard aggregated losses. More specifically, these…