@inproceedings{XieLiPokutta2015, author = {Xie, Y. and Li, Q. and Pokutta, Sebastian}, title = {Supervised Online Subspace Tracking}, booktitle = {Proceedings of Asilomar Conference on Signals, Systems, and Computers}, year = {2015}, language = {en} } @inproceedings{RoyPokutta2016, author = {Roy, Aurko and Pokutta, Sebastian}, title = {Hierarchical Clustering via Spreading Metrics}, booktitle = {Proceedings of NIPS}, arxiv = {http://arxiv.org/abs/1610.09269}, year = {2016}, language = {en} } @inproceedings{BraunRoyPokutta2016, author = {Braun, G{\´a}bor and Roy, Aurko and Pokutta, Sebastian}, title = {Stronger Reductions for Extended Formulations}, booktitle = {Proceedings of IPCO}, arxiv = {http://arxiv.org/abs/1512.04932}, year = {2016}, language = {en} } @inproceedings{BraunBrownCohenHuqetal.2016, author = {Braun, G{\´a}bor and Brown-Cohen, Jonah and Huq, Arefin and Pokutta, Sebastian and Raghavendra, Prasad and Weitz, Benjamin and Zink, Daniel}, title = {The matching problem has no small symmetric SDP}, booktitle = {Proceddings of SODA 2016}, arxiv = {http://arxiv.org/abs/1504.00703}, year = {2016}, language = {en} } @inproceedings{RoyXuPokutta2017, author = {Roy, Aurko and Xu, Huan and Pokutta, Sebastian}, title = {Reinforcement Learning under Model Mismatch}, booktitle = {Proceedings of NIPS}, arxiv = {http://arxiv.org/abs/1706.04711}, year = {2017}, language = {en} } @inproceedings{BaermannPokuttaSchneider2017, author = {B{\"a}rmann, Andreas and Pokutta, Sebastian and Schneider, Oskar}, title = {Emulating the Expert: Inverse Optimization through Online Learning}, booktitle = {Proceedings of the International Conference on Machine Learning (ICML)}, arxiv = {http://arxiv.org/abs/1810.12997}, year = {2017}, language = {en} } @inproceedings{SofranacGleixnerPokutta2021, author = {Sofranac, Boro and Gleixner, Ambros and Pokutta, Sebastian}, title = {An Algorithm-Independent Measure of Progress for Linear Constraint Propagation}, volume = {210}, booktitle = {27th International Conference on Principles and Practice of Constraint Programming (CP 2021)}, doi = {10.4230/LIPIcs.CP.2021.52}, pages = {52:1 -- 52:17}, year = {2021}, abstract = {Propagation of linear constraints has become a crucial sub-routine in modern Mixed-Integer Programming (MIP) solvers. In practice, iterative algorithms with tolerance-based stopping criteria are used to avoid problems with slow or infinite convergence. However, these heuristic stopping criteria can pose difficulties for fairly comparing the efficiency of different implementations of iterative propagation algorithms in a real-world setting. Most significantly, the presence of unbounded variable domains in the problem formulation makes it difficult to quantify the relative size of reductions performed on them. In this work, we develop a method to measure -- independently of the algorithmic design -- the progress that a given iterative propagation procedure has made at a given point in time during its execution. Our measure makes it possible to study and better compare the behavior of bounds propagation algorithms for linear constraints. We apply the new measure to answer two questions of practical relevance: (i) We investigate to what extent heuristic stopping criteria can lead to premature termination on real-world MIP instances. (ii) We compare a GPU-parallel propagation algorithm against a sequential state-of-the-art implementation and show that the parallel version is even more competitive in a real-world setting than originally reported.}, language = {en} } @article{CardereraPokutta2020, author = {Carderera, Alejandro and Pokutta, Sebastian}, title = {Second-order Conditional Gradient Sliding}, year = {2020}, abstract = {Constrained second-order convex optimization algorithms are the method of choice when a high accuracy solution to a problem is needed, due to their local quadratic convergence. These algorithms require the solution of a constrained quadratic subproblem at every iteration. We present the \emph{Second-Order Conditional Gradient Sliding} (SOCGS) algorithm, which uses a projection-free algorithm to solve the constrained quadratic subproblems inexactly. When the feasible region is a polytope the algorithm converges quadratically in primal gap after a finite number of linearly convergent iterations. Once in the quadratic regime the SOCGS algorithm requires O(log(log1/ε)) first-order and Hessian oracle calls and O(log(1/ε)log(log1/ε)) linear minimization oracle calls to achieve an ε-optimal solution. This algorithm is useful when the feasible region can only be accessed efficiently through a linear optimization oracle, and computing first-order information of the function, although possible, is costly.}, language = {en} } @article{MathieuCardereraPokutta2022, author = {Mathieu, Besan{\c{c}}on and Carderera, Alejandro and Pokutta, Sebastian}, title = {FrankWolfe.jl: a high-performance and flexible toolbox for Frank-Wolfe algorithms and Conditional Gradients}, volume = {34}, journal = {INFORMS Journal on Computing}, number = {5}, doi = {10.1287/ijoc.2022.1191}, pages = {2383 -- 2865}, year = {2022}, abstract = {We present FrankWolfe.jl, an open-source implementation of several popular Frank-Wolfe and conditional gradients variants for first-order constrained optimization. The package is designed with flexibility and high performance in mind, allowing for easy extension and relying on few assumptions regarding the user-provided functions. It supports Julia's unique multiple dispatch feature, and it interfaces smoothly with generic linear optimization formulations using MathOptInterface.jl.}, language = {en} } @article{AbbasAmbainisAugustinoetal.2024, author = {Abbas, Amira and Ambainis, Andris and Augustino, Brandon and B{\"a}rtschi, Andreas and Buhrman, Harry and Coffrin, Carleton and Cortiana, Giorgio and Dunjko, Vedran and Egger, Daniel J. and Elmegreen, Bruce G. and Franco, Nicola and Fratini, Filippo and Fuller, Bryce and Gacon, Julien and Gonciulea, Constantin and Gribling, Sander and Gupta, Swati and Hadfield, Stuart and Heese, Raoul and Kircher, Gerhard and Kleinert, Thomas and Koch, Thorsten and Korpas, Georgios and Lenk, Steve and Marecek, Jakub and Markov, Vanio and Mazzola, Guglielmo and Mensa, Stefano and Mohseni, Naeimeh and Nannicini, Giacomo and O'Meara, Corey and Tapia, Elena Pe{\~n}a and Pokutta, Sebastian and Proissl, Manuel and Rebentrost, Patrick and Sahin, Emre and Symons, Benjamin C. B. and Tornow, Sabine and Valls, V{\´i}ctor and Woerner, Stefan and Wolf-Bauwens, Mira L. and Yard, Jon and Yarkoni, Sheir and Zechiel, Dirk and Zhuk, Sergiy and Zoufal, Christa}, title = {Challenges and opportunities in quantum optimization}, volume = {6}, journal = {Nature Reviews Physics}, publisher = {Springer Science and Business Media LLC}, issn = {2522-5820}, arxiv = {http://arxiv.org/abs/2312.02279}, doi = {10.1038/s42254-024-00770-9}, pages = {718 -- 735}, year = {2024}, language = {en} } @inproceedings{SofranacGleixnerPokutta2020, author = {Sofranac, Boro and Gleixner, Ambros and Pokutta, Sebastian}, title = {Accelerating Domain Propagation: an Efficient GPU-Parallel Algorithm over Sparse Matrices}, booktitle = {2020 IEEE/ACM 10th Workshop on Irregular Applications: Architectures and Algorithms (IA3)}, arxiv = {http://arxiv.org/abs/2009.07785}, doi = {10.1109/IA351965.2020.00007}, pages = {1 -- 11}, year = {2020}, abstract = {Fast domain propagation of linear constraints has become a crucial component of today's best algorithms and solvers for mixed integer programming and pseudo-boolean optimization to achieve peak solving performance. Irregularities in the form of dynamic algorithmic behaviour, dependency structures, and sparsity patterns in the input data make efficient implementations of domain propagation on GPUs and, more generally, on parallel architectures challenging. This is one of the main reasons why domain propagation in state-of-the-art solvers is single thread only. In this paper, we present a new algorithm for domain propagation which (a) avoids these problems and allows for an efficient implementation on GPUs, and is (b) capable of running propagation rounds entirely on the GPU, without any need for synchronization or communication with the CPU. We present extensive computational results which demonstrate the effectiveness of our approach and show that ample speedups are possible on practically relevant problems: on state-of-the-art GPUs, our geometric mean speed-up for reasonably-large instances is around 10x to 20x and can be as high as 195x on favorably-large instances.}, language = {en} } @article{ŠofranacGleixnerPokutta2022, author = {Šofranac, Boro and Gleixner, Ambros and Pokutta, Sebastian}, title = {Accelerating domain propagation: An efficient GPU-parallel algorithm over sparse matrices}, volume = {109}, journal = {Parallel Computing}, doi = {10.1016/j.parco.2021.102874}, pages = {102874}, year = {2022}, abstract = {• Currently, domain propagation in state-of-the-art MIP solvers is single thread only. • The paper presents a novel, efficient GPU algorithm to perform domain propagation. • Challenges are dynamic algorithmic behavior, dependency structures, sparsity patterns. • The algorithm is capable of running entirely on the GPU with no CPU involvement. • We achieve speed-ups of around 10x to 20x, up to 180x on favorably-large instances.}, language = {en} } @inproceedings{DiakonikolasCardereraPokutta2019, author = {Diakonikolas, Jelena and Carderera, Alejandro and Pokutta, Sebastian}, title = {Breaking the Curse of Dimensionality (Locally) to Accelerate Conditional Gradients}, booktitle = {OPTML Workshop Paper}, arxiv = {http://arxiv.org/abs/1906.07867}, year = {2019}, language = {en} } @inproceedings{CombettesPokutta2019, author = {Combettes, Cyrille W. and Pokutta, Sebastian}, title = {Blended Matching Pursuit}, booktitle = {Proceedings of NeurIPS}, arxiv = {http://arxiv.org/abs/1904.12335}, year = {2019}, language = {en} } @inproceedings{PokuttaSinghTorrico2019, author = {Pokutta, Sebastian and Singh, M. and Torrico, A.}, title = {On the Unreasonable Effectiveness of the Greedy Algorithm: Greedy Adapts to Sharpness}, booktitle = {OPTML Workshop Paper}, year = {2019}, language = {en} } @inproceedings{CriadoMartinezRubioPokutta2022, author = {Criado, Francisco and Mart{\´i}nez-Rubio, David and Pokutta, Sebastian}, title = {Fast Algorithms for Packing Proportional Fairness and its Dual}, volume = {36}, booktitle = {Proceedings of the Conference on Neural Information Processing Systems}, year = {2022}, abstract = {The proportional fair resource allocation problem is a major problem studied in flow control of networks, operations research, and economic theory, where it has found numerous applications. This problem, defined as the constrained maximization of sum_i log x_i, is known as the packing proportional fairness problem when the feasible set is defined by positive linear constraints and x ∈ R≥0. In this work, we present a distributed accelerated first-order method for this problem which improves upon previous approaches. We also design an algorithm for the optimization of its dual problem. Both algorithms are width-independent.}, language = {en} } @inproceedings{CardereraPokuttaMathieu2021, author = {Carderera, Alejandro and Pokutta, Sebastian and Mathieu, Besan{\c{c}}on}, title = {Simple steps are all you need: Frank-Wolfe and generalized self-concordant functions}, booktitle = {Thirty-fifth Conference on Neural Information Processing Systems, NeurIPS 2021}, year = {2021}, abstract = {Generalized self-concordance is a key property present in the objective function of many important learning problems. We establish the convergence rate of a simple Frank-Wolfe variant that uses the open-loop step size strategy 𝛾𝑡 = 2/(𝑡 + 2), obtaining a O (1/𝑡) convergence rate for this class of functions in terms of primal gap and Frank-Wolfe gap, where 𝑡 is the iteration count. This avoids the use of second-order information or the need to estimate local smoothness parameters of previous work. We also show improved convergence rates for various common cases, e.g., when the feasible region under consideration is uniformly convex or polyhedral.}, language = {en} } @article{Kerdreuxd'AspremontPokutta2021, author = {Kerdreux, Thomas and d'Aspremont, Alexandre and Pokutta, Sebastian}, title = {Local and Global Uniform Convexity Conditions}, year = {2021}, abstract = {We review various characterizations of uniform convexity and smoothness on norm balls in finite-dimensional spaces and connect results stemming from the geometry of Banach spaces with scaling inequalities used in analysing the convergence of optimization methods. In particular, we establish local versions of these conditions to provide sharper insights on a recent body of complexity results in learning theory, online learning, or offline optimization, which rely on the strong convexity of the feasible set. While they have a significant impact on complexity, these strong convexity or uniform convexity properties of feasible sets are not exploited as thoroughly as their functional counterparts, and this work is an effort to correct this imbalance. We conclude with some practical examples in optimization and machine learning where leveraging these conditions and localized assumptions lead to new complexity results.}, language = {en} } @inproceedings{ZimmerSpiegelPokutta2023, author = {Zimmer, Max and Spiegel, Christoph and Pokutta, Sebastian}, title = {How I Learned to Stop Worrying and Love Retraining}, booktitle = {Proceedings of International Conference on Learning Representations}, year = {2023}, language = {en} } @inproceedings{WirthKerdreuxPokutta2023, author = {Wirth, Elias and Kerdreux, Thomas and Pokutta, Sebastian}, title = {Acceleration of Frank-Wolfe Algorithms with Open Loop Step-sizes}, booktitle = {Proceedings of International Conference on Artificial Intelligence and Statistics}, year = {2023}, language = {en} } @inproceedings{WirthKeraPokutta2023, author = {Wirth, Elias and Kera, and Pokutta, Sebastian}, title = {Approximate Vanishing Ideal Computations at Scale}, booktitle = {Proceedings of International Conference on Learning Representations}, year = {2023}, language = {en} } @article{BienstockMunozPokutta2023, author = {Bienstock, Daniel and Mu{\~n}oz, Gonzalo and Pokutta, Sebastian}, title = {Principled Deep Neural Network Training Through Linear Programming}, volume = {49}, journal = {Discrete Optimization}, doi = {10.1016/j.disopt.2023.100795}, year = {2023}, abstract = {Deep learning has received much attention lately due to the impressive empirical performance achieved by training algorithms. Consequently, a need for a better theoretical understanding of these problems has become more evident and multiple works in recent years have focused on this task. In this work, using a unified framework, we show that there exists a polyhedron that simultaneously encodes, in its facial structure, all possible deep neural network training problems that can arise from a given architecture, activation functions, loss function, and sample size. Notably, the size of the polyhedral representation depends only linearly on the sample size, and a better dependency on several other network parameters is unlikely. Using this general result, we compute the size of the polyhedral encoding for commonly used neural network architectures. Our results provide a new perspective on training problems through the lens of polyhedral theory and reveal strong structure arising from these problems.}, language = {en} } @inproceedings{GłuchTuranNagarajanetal.2025, author = {Głuch, Grzegorz and Turan, Berkant and Nagarajan, Sai Ganesh and Pokutta, Sebastian}, title = {The Good, the Bad and the Ugly: Meta-Analysis of Watermarks, Transferable Attacks and Adversarial Defenses}, booktitle = {Proceedings of the Conference on Neural Information Processing Systems}, year = {2025}, language = {en} } @inproceedings{KeraPelleritiIshiharaetal.2025, author = {Kera, Hiroshi and Pelleriti, Nico and Ishihara, Yuki and Zimmer, Max and Pokutta, Sebastian}, title = {Computational Algebra with Attention: Transformer Oracles for Border Basis Algorithms}, booktitle = {Proceedings of the Conference on Neural Information Processing Systems}, year = {2025}, language = {en} } @article{HendrychTroppensBesanconetal.2025, author = {Hendrych, Deborah and Troppens, Hannah and Besan{\c{c}}on, Mathieu and Pokutta, Sebastian}, title = {Convex mixed-integer optimization with Frank-Wolfe methods}, volume = {17}, journal = {Mathematical Programming Computation}, doi = {10.1007/s12532-025-00288-w}, pages = {731 -- 757}, year = {2025}, language = {en} } @inproceedings{HendrychBesanconMartinezRubioetal.2025, author = {Hendrych, Deborah and Besan{\c{c}}on, Mathieu and Mart{\´i}nez-Rubio, David and Pokutta, Sebastian}, title = {Secant line search for Frank-Wolfe algorithms}, volume = {267}, booktitle = {Proceedings of the 42nd International Conference on Machine Learning}, arxiv = {http://arxiv.org/abs/2501.18775}, pages = {23005 -- 23029}, year = {2025}, language = {en} } @inproceedings{PaulsZimmerTuranetal.2025, author = {Pauls, Jan and Zimmer, Max and Turan, Berkant and Saatchi, Sassan and Ciais, Philippe and Pokutta, Sebastian and Gieseke, Fabian}, title = {Capturing Temporal Dynamics in Large-Scale Canopy Tree Height Estimation}, volume = {267}, booktitle = {Proceedings of the 42nd International Conference on Machine Learning}, arxiv = {http://arxiv.org/abs/2501.19328}, pages = {48422 -- 48438}, year = {2025}, language = {en} } @inproceedings{MundingerZimmerKiemetal.2025, author = {Mundinger, Konrad and Zimmer, Max and Kiem, Aldo and Spiegel, Christoph and Pokutta, Sebastian}, title = {Neural Discovery in Mathematics: Do Machines Dream of Colored Planes?}, volume = {267}, booktitle = {Proceedings of the 42nd International Conference on Machine Learning}, arxiv = {http://arxiv.org/abs/2501.18527}, pages = {45236 -- 45255}, year = {2025}, language = {en} } @inproceedings{PelleritiZimmerWirthetal.2025, author = {Pelleriti, Nico and Zimmer, Max and Wirth, Elias and Pokutta, Sebastian}, title = {Approximating Latent Manifolds in Neural Networks via Vanishing Ideals}, volume = {267}, booktitle = {Proceedings of the 42nd International Conference on Machine Learning}, arxiv = {http://arxiv.org/abs/2502.15051}, pages = {48734 -- 48761}, year = {2025}, language = {en} } @inproceedings{RouxMartinezRubioPokutta2025, author = {Roux, Christophe and Mart{\´i}nez-Rubio, David and Pokutta, Sebastian}, title = {Implicit Riemannian optimism with applications to min-max problems}, volume = {267}, booktitle = {Proceedings of the 42nd International Conference on Machine Learning}, arxiv = {http://arxiv.org/abs/2501.18381}, pages = {52139 -- 52172}, year = {2025}, language = {en} } @inproceedings{TuranAsadullaSteinmannetal.2025, author = {Turan, Berkant and Asadulla, Suhrab and Steinmann, David and Stammer, Wolfgang and Pokutta, Sebastian}, title = {Neural Concept Verifier: Scaling Prover-Verifier Games via Concept Encodings}, booktitle = {Proceedings of the ICML Workshop on Actionable Interpretability}, year = {2025}, language = {en} } @article{CardereraBesanconPokutta2024, author = {Carderera, Alejandro and Besan{\c{c}}on, Mathieu and Pokutta, Sebastian}, title = {Scalable Frank-Wolfe on generalized self-concordant functions via simple steps}, volume = {34}, journal = {SIAM Journal on Optimization}, number = {3}, doi = {10.1137/23M1616789}, year = {2024}, language = {en} } @article{ParczykPokuttaSpiegeletal.2024, author = {Parczyk, Olaf and Pokutta, Sebastian and Spiegel, Christoph and Szab{\´o}, Tibor}, title = {New Ramsey multiplicity bounds and search heuristics}, journal = {Foundations of Computational Mathematics}, doi = {10.1007/s10208-024-09675-6}, year = {2024}, language = {en} } @inproceedings{PaulsZimmerKellyetal.2024, author = {Pauls, Jan and Zimmer, Max and Kelly, Una M and Schwartz, Martin and Saatchi, Sassan and Ciais, Philippe and Pokutta, Sebastian and Brandt, Martin and Gieseke, Fabian}, title = {Estimating canopy height at scale}, volume = {235}, booktitle = {Proceedings of the 41st International Conference on Machine Learning}, pages = {39972 -- 39988}, year = {2024}, abstract = {We propose a framework for global-scale canopy height estimation based on satellite data. Our model leverages advanced data preprocessing techniques, resorts to a novel loss function designed to counter geolocation inaccuracies inherent in the ground-truth height measurements, and employs data from the Shuttle Radar Topography Mission to effectively filter out erroneous labels in mountainous regions, enhancing the reliability of our predictions in those areas. A comparison between predictions and ground-truth labels yields an MAE/RMSE of 2.43 / 4.73 (meters) overall and 4.45 / 6.72 (meters) for trees taller than five meters, which depicts a substantial improvement compared to existing global-scale products. The resulting height map as well as the underlying framework will facilitate and enhance ecological analyses at a global scale, including, but not limited to, large-scale forest and biomass monitoring.}, language = {en} } @inproceedings{HendrychBesanconPokutta2024, author = {Hendrych, Deborah and Besan{\c{c}}on, Mathieu and Pokutta, Sebastian}, title = {Solving the optimal experiment design problem with mixed-integer convex methods}, volume = {301}, booktitle = {22nd International Symposium on Experimental Algorithms (SEA 2024)}, doi = {10.4230/LIPIcs.SEA.2024.16}, pages = {16:1 -- 16:22}, year = {2024}, abstract = {We tackle the Optimal Experiment Design Problem, which consists of choosing experiments to run or observations to select from a finite set to estimate the parameters of a system. The objective is to maximize some measure of information gained about the system from the observations, leading to a convex integer optimization problem. We leverage Boscia.jl, a recent algorithmic framework, which is based on a nonlinear branch-and-bound algorithm with node relaxations solved to approximate optimality using Frank-Wolfe algorithms. One particular advantage of the method is its efficient utilization of the polytope formed by the original constraints which is preserved by the method, unlike alternative methods relying on epigraph-based formulations. We assess our method against both generic and specialized convex mixed-integer approaches. Computational results highlight the performance of our proposed method, especially on large and challenging instances.}, language = {en} } @inproceedings{KiemPokuttaSpiegel2024, author = {Kiem, Aldo and Pokutta, Sebastian and Spiegel, Christoph}, title = {Categorification of Flag Algebras}, booktitle = {Discrete Mathematics Days 2024}, doi = {10.37536/TYSP5643}, pages = {259 -- 264}, year = {2024}, language = {en} } @inproceedings{KiemPokuttaSpiegel2024, author = {Kiem, Aldo and Pokutta, Sebastian and Spiegel, Christoph}, title = {The Four-Color Ramsey Multiplicity of Triangles}, booktitle = {Discrete Mathematics Days 2024}, doi = {10.37536/TYSP5643}, pages = {13 -- 18}, year = {2024}, language = {en} } @article{MundingerPokuttaSpiegeletal.2024, author = {Mundinger, Konrad and Pokutta, Sebastian and Spiegel, Christoph and Zimmer, Max}, title = {Extending the Continuum of Six-Colorings}, volume = {34}, journal = {Geombinatorics Quarterly}, number = {1}, arxiv = {http://arxiv.org/abs/2404.05509}, pages = {20 -- 29}, year = {2024}, language = {en} } @inproceedings{MundingerPokuttaSpiegeletal.2024, author = {Mundinger, Konrad and Pokutta, Sebastian and Spiegel, Christoph and Zimmer, Max}, title = {Extending the Continuum of Six-Colorings}, booktitle = {Discrete Mathematics Days 2024}, doi = {10.37536/TYSP5643}, pages = {178 -- 183}, year = {2024}, language = {en} } @inproceedings{MartinezRubioRouxPokutta2024, author = {Mart{\´i}nez-Rubio, David and Roux, Christophe and Pokutta, Sebastian}, title = {Convergence and Trade-Offs in Riemannian Gradient Descent and Riemannian Proximal Point}, volume = {235}, booktitle = {Proceedings of the 41st International Conference on Machine Learning}, pages = {34920 -- 34948}, year = {2024}, abstract = {In this work, we analyze two of the most fundamental algorithms in geodesically convex optimization: Riemannian gradient descent and (possibly inexact) Riemannian proximal point. We quantify their rates of convergence and produce different variants with several trade-offs. Crucially, we show the iterates naturally stay in a ball around an optimizer, of radius depending on the initial distance and, in some cases, on the curvature. Previous works simply assumed bounded iterates, resulting in rates that were not fully quantified. We also provide an implementable inexact proximal point algorithm and prove several new useful properties of Riemannian proximal methods: they work when positive curvature is present, the proximal operator does not move points away from any optimizer, and we quantify the smoothness of its induced Moreau envelope. Further, we explore beyond our theory with empirical tests.}, language = {en} } @article{DezaPokuttaPournin2024, author = {Deza, Antoine and Pokutta, Sebastian and Pournin, Lionel}, title = {The complexity of geometric scaling}, volume = {52}, journal = {Operations Research Letters}, doi = {10.1016/j.orl.2023.11.010}, pages = {107057}, year = {2024}, language = {en} } @article{Pokutta2024, author = {Pokutta, Sebastian}, title = {The Frank-Wolfe algorithm: a short introduction}, volume = {126}, journal = {Jahresbericht der Deutschen Mathematiker-Vereinigung}, doi = {10.1365/s13291-023-00275-x}, pages = {3 -- 35}, year = {2024}, language = {en} } @inproceedings{WaeldchenSharmaTuranetal.2024, author = {W{\"a}ldchen, Stephan and Sharma, Kartikey and Turan, Berkant and Zimmer, Max and Pokutta, Sebastian}, title = {Interpretability Guarantees with Merlin-Arthur Classifiers}, volume = {238}, booktitle = {Proceedings of The 27th International Conference on Artificial Intelligence and Statistics}, pages = {1963 -- 1971}, year = {2024}, abstract = {We propose an interactive multi-agent classifier that provides provable interpretability guarantees even for complex agents such as neural networks. These guarantees consist of lower bounds on the mutual information between selected features and the classification decision. Our results are inspired by the Merlin-Arthur protocol from Interactive Proof Systems and express these bounds in terms of measurable metrics such as soundness and completeness. Compared to existing interactive setups, we rely neither on optimal agents nor on the assumption that features are distributed independently. Instead, we use the relative strength of the agents as well as the new concept of Asymmetric Feature Correlation which captures the precise kind of correlations that make interpretability guarantees difficult. We evaluate our results on two small-scale datasets where high mutual information can be verified explicitly.}, language = {en} } @inproceedings{ZimmerSpiegelPokutta2024, author = {Zimmer, Max and Spiegel, Christoph and Pokutta, Sebastian}, title = {Sparse Model Soups}, booktitle = {12th International Conference on Learning Representations (ICLR 2024)}, publisher = {Curran Associates, Inc.}, isbn = {9781713898658}, year = {2024}, language = {en} } @article{StenglGelssKlusetal.2024, author = {Stengl, Steven-Marian and Gelß, Patrick and Klus, Stefan and Pokutta, Sebastian}, title = {Existence and uniqueness of solutions of the Koopman--von Neumann equation on bounded domains}, volume = {57}, journal = {Journal of Physics A: Mathematical and Theoretical}, number = {39}, doi = {10.1088/1751-8121/ad6f7d}, year = {2024}, language = {en} } @article{DezaOnnPokuttaetal.2024, author = {Deza, Antoine and Onn, Shmuel and Pokutta, Sebastian and Pournin, Lionel}, title = {Kissing polytopes}, volume = {38}, journal = {SIAM Journal on Discrete Mathematics}, number = {4}, doi = {10.1137/24M1640859}, year = {2024}, abstract = {We investigate the following question: How close can two disjoint lattice polytopes contained in a fixed hypercube be? This question stems from various contexts where the minimal distance between such polytopes appears in complexity bounds of optimization algorithms. We provide nearly matching bounds on this distance and discuss its exact computation. We also give similar bounds for disjoint rational polytopes whose binary encoding length is prescribed.}, language = {en} } @article{Kerdreuxd'AspremontPokutta2022, author = {Kerdreux, Thomas and d'Aspremont, Alexandre and Pokutta, Sebastian}, title = {Restarting Frank-Wolfe: Faster Rates under H{\"o}lderian Error Bounds}, journal = {Journal of Optimization Theory and Applications}, year = {2022}, language = {en} } @article{CombettesPokutta2023, author = {Combettes, Cyrille and Pokutta, Sebastian}, title = {Revisiting the Approximate Carath{\´e}odory Problem via the Frank-Wolfe Algorithm}, volume = {197}, journal = {Mathematical Programming A}, doi = {10.1007/s10107-021-01735-x}, pages = {191 -- 214}, year = {2023}, language = {en} } @article{Vu‐HanSunkaraBermudez‐Schettinoetal.2025, author = {Vu-Han, Tu-Lan and Sunkara, Vikram and Bermudez-Schettino, Rodrigo and Schwechten, Jakob and Runge, Robin and Perka, Carsten and Winkler, Tobias and Pokutta, Sebastian and Weiß, Claudia and Pumberger, Matthias}, title = {Feature Engineering for the Prediction of Scoliosis in 5q-Spinal Muscular Atrophy}, volume = {16}, journal = {Journal of Cachexia, Sarcopenia and Muscle}, number = {1}, doi = {10.1002/jcsm.13599}, pages = {e13599}, year = {2025}, language = {en} } @inproceedings{TroppensBesanconWilkenetal.2025, author = {Troppens, Hannah and Besan{\c{c}}on, Mathieu and Wilken, St. Elmo and Pokutta, Sebastian}, title = {Mixed-Integer Optimization for Loopless Flux Distributions in Metabolic Networks}, volume = {338}, booktitle = {23rd International Symposium on Experimental Algorithms (SEA 2025)}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"u}r Informatik}, doi = {10.4230/LIPIcs.SEA.2025.26}, pages = {26:1 -- 26:18}, year = {2025}, language = {en} } @inproceedings{GłuchTuranNagarajanetal.2025, author = {Głuch, Grzegorz and Turan, Berkant and Nagarajan, Sai Ganesh and Pokutta, Sebastian}, title = {The good, the bad and the ugly: watermarks, transferable attacks and adversarial defenses}, booktitle = {1st Workshop on GenAI Watermarking, collocated with ICLR 2025}, year = {2025}, language = {en} } @inproceedings{BesanconPokuttaWirth2025, author = {Besan{\c{c}}on, Mathieu and Pokutta, Sebastian and Wirth, Elias}, title = {The Pivoting Framework: Frank-Wolfe Algorithms with Active Set Size Control}, volume = {258}, booktitle = {Proceedings of The 28th International Conference on Artificial Intelligence and Statistics}, pages = {271 -- 279}, year = {2025}, language = {en} }