181 citations · 620 across the 171 of their papers we have counts for
15 papers · 1 filter
Alternating Linear Minimization: Revisiting von Neumann's alternating projections
Gábor Braun, Sebastian Pokutta, Robert Weismantel
In 1933 von Neumann proved a beautiful result that one can approximate a point in the intersection of two convex sets by alternating projections, i.e., successively projecting on o…
Accelerated Riemannian Optimization: Handling Constraints with a Prox to Bound Geometric Penalties
David Martínez-Rubio, Sebastian Pokutta
We propose a globally-accelerated, first-order method for the optimization of smooth and (strongly or not) geodesically-convex functions in a wide class of Hadamard manifolds. We a…
Conditional Gradient Methods
Gábor Braun, Alejandro Carderera, Cyrille W. Combettes +4
The purpose of this survey is to serve both as a gentle introduction and a coherent overview of state-of-the-art Frank--Wolfe algorithms, also called conditional gradient algorithm…
Convex mixed-integer optimization with Frank-Wolfe methods
Deborah Hendrych, Hannah Troppens, Mathieu Besançon +1
Mixed-integer nonlinear optimization encompasses a broad class of problems that present both theoretical and computational challenges. We propose a new type of method to solve thes…
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}…
New Ramsey Multiplicity Bounds and Search Heuristics
Olaf Parczyk, Sebastian Pokutta, Christoph Spiegel +1
We study two related problems concerning the number of homogeneous subsets of given size in graphs that go back to questions of Erdős. Most notably, we improve the upper bounds on…
Interpretability Guarantees with Merlin-Arthur Classifiers
Stephan Wäldchen, Kartikey Sharma, Berkant Turan +2
We propose an interactive multi-agent classifier that provides provable interpretability guarantees even for complex agents such as neural networks. These guarantees consist of low…
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…
Compression-aware Training of Neural Networks using Frank-Wolfe
Max Zimmer, Christoph Spiegel, Sebastian Pokutta
Many existing Neural Network pruning approaches rely on either retraining or inducing a strong bias in order to converge to a sparse solution throughout training. A third paradigm,…
Low-rank tensor decompositions of quantum circuits
Patrick Gelß, Stefan Klus, Sebastian Knebel +2
Quantum computing is arguably one of the most revolutionary and disruptive technologies of this century. Due to the ever-increasing number of potential applications as well as the…
The complexity of geometric scaling
Antoine Deza, Sebastian Pokutta, Lionel Pournin
Geometric scaling, introduced by Schulz and Weismantel in 2002, solves the integer optimization problem by means of primal au…
Minimizing a low-dimensional convex function over a high-dimensional cube
Christoph Hunkenschröder, Sebastian Pokutta, Robert Weismantel
For a matrix , , and a convex function , we are interested in minimizing over the se…
The Machine Learning for Combinatorial Optimization Competition (ML4CO): Results and Insights
Maxime Gasse, Quentin Cappart, Jonas Charfreitag +38
Combinatorial optimization is a well-established area in operations research and computer science. Until recently, its methods have focused on solving problem instances in isolatio…
Training Characteristic Functions with Reinforcement Learning: XAI-methods play Connect Four
Stephan Wäldchen, Felix Huber, Sebastian Pokutta
One of the goals of Explainable AI (XAI) is to determine which input components were relevant for a classifier decision. This is commonly know as saliency attribution. Characterist…
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…