@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} } @inproceedings{MartinezRubioRouxCriscitielloetal.2025, author = {Mart{\´i}nez-Rubio, David and Roux, Christophe and Criscitiello, Christopher and Pokutta, Sebastian}, title = {Accelerated Methods for Riemannian Min-Max Optimization Ensuring Bounded Geometric Penalties}, volume = {258}, booktitle = {Proceedings of The 28th International Conference on Artificial Intelligence and Statistics}, pages = {280 -- 288}, year = {2025}, language = {en} } @inproceedings{SadikuWagnerPokutta2025, author = {Sadiku, Shpresim and Wagner, Moritz and Pokutta, Sebastian}, title = {GSE: Group-wise sparse and explainable adversarial attacks}, booktitle = {13th International Conference on Learning Representations (ICLR 2025)}, arxiv = {http://arxiv.org/abs/2311.17434}, year = {2025}, language = {en} } @article{WirthPenaPokutta2025, author = {Wirth, Elias and Pena, Javier and Pokutta, Sebastian}, title = {Correction: Accelerated affine-invariant convergence rates of the Frank-Wolfe algorithm with open-loop step-sizes}, volume = {214}, journal = {Mathematical Programming}, doi = {10.1007/s10107-025-02214-3}, pages = {941 -- 942}, year = {2025}, language = {en} } @inproceedings{RouxZimmerPokutta2025, author = {Roux, Christophe and Zimmer, Max and Pokutta, Sebastian}, title = {On the byzantine-resilience of distillation-based federated learning}, booktitle = {13th International Conference on Learning Representations (ICLR 2025)}, arxiv = {http://arxiv.org/abs/2402.12265}, year = {2025}, abstract = {Federated Learning (FL) algorithms using Knowledge Distillation (KD) have received increasing attention due to their favorable properties with respect to privacy, non-i.i.d. data and communication cost. These methods depart from transmitting model parameters and instead communicate information about a learning task by sharing predictions on a public dataset. In this work, we study the performance of such approaches in the byzantine setting, where a subset of the clients act in an adversarial manner aiming to disrupt the learning process. We show that KD-based FL algorithms are remarkably resilient and analyze how byzantine clients can influence the learning process. Based on these insights, we introduce two new byzantine attacks and demonstrate their ability to break existing byzantine-resilient methods. Additionally, we propose a novel defence method which enhances the byzantine resilience of KD-based FL algorithms. Finally, we provide a general framework to obfuscate attacks, making them significantly harder to detect, thereby improving their effectiveness.}, language = {en} } @inproceedings{SadikuWagnerNagarajanetal.2025, author = {Sadiku, Shpresim and Wagner, Moritz and Nagarajan, Sai Ganesh and Pokutta, Sebastian}, title = {S-CFE: Simple Counterfactual Explanations}, volume = {258}, booktitle = {Proceedings of The 28th International Conference on Artificial Intelligence and Statistics}, pages = {172 -- 180}, year = {2025}, language = {en} } @inproceedings{MartinezRubioWirthPokutta2023, author = {Mart{\´i}nez-Rubio, David and Wirth, Elias and Pokutta, Sebastian}, title = {Accelerated and Sparse Algorithms for Approximate Personalized PageRank and Beyond}, volume = {195}, booktitle = {Proceedings of Machine Learning Research}, pages = {1 -- 35}, year = {2023}, abstract = {It has recently been shown that ISTA, an unaccelerated optimization method, presents sparse updates for the ℓ1-regularized undirected personalized PageRank problem (Fountoulakis et al., 2019), leading to cheap iteration complexity and providing the same guarantees as the approximate personalized PageRank algorithm (APPR) (Andersen et al., 2006). In this work, we design an accelerated optimization algorithm for this problem that also performs sparse updates, providing an affirmative answer to the COLT 2022 open question of Fountoulakis and Yang (2022). Acceleration provides a reduced dependence on the condition number, while the dependence on the sparsity in our updates differs from the ISTA approach. Further, we design another algorithm by using conjugate directions to achieve an exact solution while exploiting sparsity. Both algorithms lead to faster convergence for certain parameter regimes. Our findings apply beyond PageRank and work for any quadratic objective whose Hessian is a positive-definite 푀-matrix.}, 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}, doi = {10.1007/s10107-021-01735-x}, pages = {191 -- 214}, year = {2023}, language = {en} } @incollection{ZimmerSpiegelPokutta2025, author = {Zimmer, Max and Spiegel, Christoph and Pokutta, Sebastian}, title = {Compression-aware training of neural networks using Frank-Wolfe}, booktitle = {Mathematical Optimization for Machine Learning: Proceedings of the MATH+ Thematic Einstein Semester 2023}, editor = {Fackeldey, K.}, publisher = {De Gruyter}, doi = {10.1515/9783111376776-010}, pages = {137 -- 168}, year = {2025}, language = {en} } @article{BaermannMartinPokuttaetal.2018, author = {B{\"a}rmann, Andreas and Martin, Alexander and Pokutta, Sebastian and Schneider, Oskar}, title = {An Online-Learning Approach to Inverse Optimization}, year = {2018}, language = {en} } @inproceedings{CardereraDiakonikolasLinetal.2021, author = {Carderera, Alejandro and Diakonikolas, Jelena and Lin, Cheuk Yin and Pokutta, Sebastian}, title = {Parameter-free Locally Accelerated Conditional Gradients}, booktitle = {ICML 2021}, year = {2021}, abstract = {Projection-free conditional gradient (CG) methods are the algorithms of choice for constrained optimization setups in which projections are often computationally prohibitive but linear optimization over the constraint set remains computationally feasible. Unlike in projection-based methods, globally accelerated convergence rates are in general unattainable for CG. However, a very recent work on Locally accelerated CG (LaCG) has demonstrated that local acceleration for CG is possible for many settings of interest. The main downside of LaCG is that it requires knowledge of the smoothness and strong convexity parameters of the objective function. We remove this limitation by introducing a novel, Parameter-Free Locally accelerated CG (PF-LaCG) algorithm, for which we provide rigorous convergence guarantees. Our theoretical results are complemented by numerical experiments, which demonstrate local acceleration and showcase the practical improvements of PF-LaCG over non-accelerated algorithms, both in terms of iteration count and wall-clock time.}, language = {en} } @article{BienenstockMunozPokutta2018, author = {Bienenstock, Daniel and Mu{\~n}oz, Gonzalo and Pokutta, Sebastian}, title = {Principled Deep Neural Network Training through Linear Programming}, year = {2018}, abstract = {Deep Learning has received significant attention due to its impressive performance in many state-of-the-art learning tasks. Unfortunately, while very powerful, Deep Learning is not well understood theoretically and in particular only recently results for the complexity of training deep neural networks have been obtained. In this work we show that large classes of deep neural networks with various architectures (e.g., DNNs, CNNs, Binary Neural Networks, and ResNets), activation functions (e.g., ReLUs and leaky ReLUs), and loss functions (e.g., Hinge loss, Euclidean loss, etc) can be trained to near optimality with desired target accuracy using linear programming in time that is exponential in the input data and parameter space dimension and polynomial in the size of the data set; improvements of the dependence in the input dimension are known to be unlikely assuming P≠NP, and improving the dependence on the parameter space dimension remains open. In particular, we obtain polynomial time algorithms for training for a given fixed network architecture. Our work applies more broadly to empirical risk minimization problems which allows us to generalize various previous results and obtain new complexity results for previously unstudied architectures in the proper learning setting.}, language = {en} } @inproceedings{Kerdreuxd'AspremontPokutta2020, author = {Kerdreux, Thomas and d'Aspremont, Alexandre and Pokutta, Sebastian}, title = {Projection-Free Optimization on Uniformly Convex Sets}, booktitle = {To Appear in Proceedings of AISTATS}, year = {2020}, language = {en} } @article{RouxPokuttaWirthetal.2021, author = {Roux, Christophe and Pokutta, Sebastian and Wirth, Elias and Kerdreux, Thomas}, title = {Efficient Online-Bandit Strategies for Minimax Learning Problems}, year = {2021}, abstract = {Several learning problems involve solving min-max problems, e.g., empirical distributional robust learning [Namkoong and Duchi, 2016, Curi et al., 2020] or learning with non-standard aggregated losses [Shalev- Shwartz and Wexler, 2016, Fan et al., 2017]. More specifically, these problems are convex-linear problems where the minimization is carried out over the model parameters w ∈ W and the maximization over the empirical distribution p ∈ K of the training set indexes, where K is the simplex or a subset of it. To design efficient methods, we let an online learning algorithm play against a (combinatorial) bandit algorithm. We argue that the efficiency of such approaches critically depends on the structure of K and propose two properties of K that facilitate designing efficient algorithms. We focus on a specific family of sets Sn,k encompassing various learning applications and provide high-probability convergence guarantees to the minimax values.}, language = {en} } @article{KerdreuxRouxd'Aspremontetal.2021, author = {Kerdreux, Thomas and Roux, Christophe and d'Aspremont, Alexandre and Pokutta, Sebastian}, title = {Linear Bandits on Uniformly Convex Sets}, volume = {22}, journal = {Journal of Machine Learning Research}, number = {284}, pages = {1 -- 23}, year = {2021}, abstract = {Linear bandit algorithms yield O~(n√T) pseudo-regret bounds on compact convex action sets K⊂Rn and two types of structural assumptions lead to better pseudo-regret bounds. When K is the simplex or an ℓp ball with p∈]1,2], there exist bandits algorithms with O~(√n√T) pseudo-regret bounds. Here, we derive bandit algorithms for some strongly convex sets beyond ℓp balls that enjoy pseudo-regret bounds of O~(√n√T), which answers an open question from [BCB12, \S5.5.]. Interestingly, when the action set is uniformly convex but not necessarily strongly convex, we obtain pseudo-regret bounds with a dimension dependency smaller than O(√n). However, this comes at the expense of asymptotic rates in T varying between O(√T) and O(T).}, language = {en} } @article{CardereraPokuttaSchuetteetal.2021, author = {Carderera, Alejandro and Pokutta, Sebastian and Sch{\"u}tte, Christof and Weiser, Martin}, title = {An efficient first-order conditional gradient algorithm in data-driven sparse identification of nonlinear dynamics to solve sparse recovery problems under noise}, journal = {Journal of Computational and Applied Mathematics}, arxiv = {http://arxiv.org/abs/2101.02630}, year = {2021}, abstract = {Governing equations are essential to the study of nonlinear dynamics, often enabling the prediction of previously unseen behaviors as well as the inclusion into control strategies. The discovery of governing equations from data thus has the potential to transform data-rich fields where well-established dynamical models remain unknown. This work contributes to the recent trend in data-driven sparse identification of nonlinear dynamics of finding the best sparse fit to observational data in a large library of potential nonlinear models. We propose an efficient first-order Conditional Gradient algorithm for solving the underlying optimization problem. In comparison to the most prominent alternative algorithms, the new algorithm shows significantly improved performance on several essential issues like sparsity-induction, structure-preservation, noise robustness, and sample efficiency. We demonstrate these advantages on several dynamics from the field of synchronization, particle dynamics, and enzyme chemistry.}, language = {en} } @article{PokuttaSpiegelZimmer2020, author = {Pokutta, Sebastian and Spiegel, Christoph and Zimmer, Max}, title = {Deep Neural Network Training with Frank-Wolfe}, arxiv = {http://arxiv.org/abs/2010.07243}, year = {2020}, abstract = {This paper studies the empirical efficacy and benefits of using projection-free first-order methods in the form of Conditional Gradients, a.k.a. Frank-Wolfe methods, for training Neural Networks with constrained parameters. We draw comparisons both to current state-of-the-art stochastic Gradient Descent methods as well as across different variants of stochastic Conditional Gradients. In particular, we show the general feasibility of training Neural Networks whose parameters are constrained by a convex feasible region using Frank-Wolfe algorithms and compare different stochastic variants. We then show that, by choosing an appropriate region, one can achieve performance exceeding that of unconstrained stochastic Gradient Descent and matching state-of-the-art results relying on L2-regularization. Lastly, we also demonstrate that, besides impacting performance, the particular choice of constraints can have a drastic impact on the learned representations.}, language = {en} } @article{CryilleWSpiegelPokutta2020, author = {Cryille W., Combettes and Spiegel, Christoph and Pokutta, Sebastian}, title = {Projection-Free Adaptive Gradients for Large-Scale Optimization}, arxiv = {http://arxiv.org/abs/2009.14114}, year = {2020}, abstract = {The complexity in large-scale optimization can lie in both handling the objective function and handling the constraint set. In this respect, stochastic Frank-Wolfe algorithms occupy a unique position as they alleviate both computational burdens, by querying only approximate first-order information from the objective and by maintaining feasibility of the iterates without using projections. In this paper, we improve the quality of their first-order information by blending in adaptive gradients. We derive convergence rates and demonstrate the computational advantage of our method over the state-of-the-art stochastic Frank-Wolfe algorithms on both convex and nonconvex objectives. The experiments further show that our method can improve the performance of adaptive gradient algorithms for constrained optimization.}, language = {en} } @inproceedings{PfetschPokutta2020, author = {Pfetsch, Marc and Pokutta, Sebastian}, title = {IPBoost - Non-Convex Boosting via Integer Programming}, booktitle = {Proceedings of ICML}, arxiv = {http://arxiv.org/abs/2002.04679}, year = {2020}, language = {en} } @inproceedings{PokuttaSinghTorrico2020, author = {Pokutta, Sebastian and Singh, M. and Torrico, A.}, title = {On the Unreasonable Effectiveness of the Greedy Algorithm: Greedy Adapts to Sharpness}, booktitle = {Proceedings of ICML}, arxiv = {http://arxiv.org/abs/2002.04063}, year = {2020}, language = {en} } @inproceedings{DiakonikolasCardereraPokutta2020, author = {Diakonikolas, Jelena and Carderera, Alejandro and Pokutta, Sebastian}, title = {Locally Accelerated Conditional Gradients}, booktitle = {Proceedings of AISTATS}, arxiv = {http://arxiv.org/abs/1906.07867}, year = {2020}, language = {en} } @article{FaenzaMunozPokutta2020, author = {Faenza, Yuri and Mu{\~n}oz, Gonzalo and Pokutta, Sebastian}, title = {New Limits of Treewidth-based tractability in Optimization}, volume = {191}, journal = {Mathematical Programming}, arxiv = {http://arxiv.org/abs/1807.02551}, doi = {10.1007/s10107-020-01563-5}, pages = {559 -- 594}, year = {2020}, language = {en} } @article{AnariHaghtalabNaoretal.2020, author = {Anari, N. and Haghtalab, N. and Naor, S. and Pokutta, Sebastian and Singh, M. and Torrico, A.}, title = {Structured Robust Submodular Maximization: Offline and Online Algorithms}, journal = {INFORMS Journal on Computing}, arxiv = {http://arxiv.org/abs/1710.04740}, year = {2020}, language = {en} } @inproceedings{CombettesPokutta2020, author = {Combettes, Cyrille W. and Pokutta, Sebastian}, title = {Boosting Frank-Wolfe by Chasing Gradients}, booktitle = {Proceedings of ICML}, arxiv = {http://arxiv.org/abs/2003.06369}, year = {2020}, language = {en} } @inproceedings{MortagyGuptaPokutta2020, author = {Mortagy, Hassan and Gupta, Swati and Pokutta, Sebastian}, title = {Walking in the Shadow: A New Perspective on Descent Directions for Constrained Minimization}, booktitle = {Proceedings of NeurIPS}, arxiv = {http://arxiv.org/abs/2006.08426}, year = {2020}, language = {en} } @inproceedings{Pokutta2020, author = {Pokutta, Sebastian}, title = {Restarting Algorithms: Sometimes there is Free Lunch}, booktitle = {Proceedings of CPAIOR}, arxiv = {http://arxiv.org/abs/2006.14810}, year = {2020}, language = {en} } @article{KossenHirzelMadaietal.2022, author = {Kossen, Tabea and Hirzel, Manuel A. and Madai, Vince I. and Boenisch, Franziska and Hennemuth, Anja and Hildebrand, Kristian and Pokutta, Sebastian and Sharma, Kartikey and Hilbert, Adam and Sobesky, Jan and Galinovic, Ivana and Khalil, Ahmed A. and Fiebach, Jochen B. and Frey, Dietmar}, title = {Towards Sharing Brain Images: Differentially Private TOF-MRA Images with Segmentation Labels Using Generative Adversarial Networks}, journal = {Frontiers in Artificial Intelligence}, doi = {https://doi.org/10.3389/frai.2022.813842}, year = {2022}, abstract = {Sharing labeled data is crucial to acquire large datasets for various Deep Learning applications. In medical imaging, this is often not feasible due to privacy regulations. Whereas anonymization would be a solution, standard techniques have been shown to be partially reversible. Here, synthetic data using a Generative Adversarial Network (GAN) with differential privacy guarantees could be a solution to ensure the patient's privacy while maintaining the predictive properties of the data. In this study, we implemented a Wasserstein GAN (WGAN) with and without differential privacy guarantees to generate privacy-preserving labeled Time-of-Flight Magnetic Resonance Angiography (TOF-MRA) image patches for brain vessel segmentation. The synthesized image-label pairs were used to train a U-net which was evaluated in terms of the segmentation performance on real patient images from two different datasets. Additionally, the Fr{\´e}chet Inception Distance (FID) was calculated between the generated images and the real images to assess their similarity. During the evaluation using the U-Net and the FID, we explored the effect of different levels of privacy which was represented by the parameter ϵ. With stricter privacy guarantees, the segmentation performance and the similarity to the real patient images in terms of FID decreased. Our best segmentation model, trained on synthetic and private data, achieved a Dice Similarity Coefficient (DSC) of 0.75 for ϵ = 7.4 compared to 0.84 for ϵ = ∞ in a brain vessel segmentation paradigm (DSC of 0.69 and 0.88 on the second test set, respectively). We identified a threshold of ϵ <5 for which the performance (DSC <0.61) became unstable and not usable. Our synthesized labeled TOF-MRA images with strict privacy guarantees retained predictive properties necessary for segmenting the brain vessels. Although further research is warranted regarding generalizability to other imaging modalities and performance improvement, our results mark an encouraging first step for privacy-preserving data sharing in medical imaging.}, language = {en} } @inproceedings{WirthPokutta2022, author = {Wirth, Elias and Pokutta, Sebastian}, title = {Conditional Gradients for the Approximately Vanishing Ideal}, volume = {151}, booktitle = {Proceedings of The 25th International Conference on Artificial Intelligence and Statistics}, pages = {2191 -- 2209}, year = {2022}, abstract = {The vanishing ideal of a set of points X is the set of polynomials that evaluate to 0 over all points x in X and admits an efficient representation by a finite set of polynomials called generators. To accommodate the noise in the data set, we introduce the Conditional Gradients Approximately Vanishing Ideal algorithm (CGAVI) for the construction of the set of generators of the approximately vanishing ideal. The constructed set of generators captures polynomial structures in data and gives rise to a feature map that can, for example, be used in combination with a linear classifier for supervised learning. In CGAVI, we construct the set of generators by solving specific instances of (constrained) convex optimization problems with the Pairwise Frank-Wolfe algorithm (PFW). Among other things, the constructed generators inherit the LASSO generalization bound and not only vanish on the training but also on out-sample data. Moreover, CGAVI admits a compact representation of the approximately vanishing ideal by constructing few generators with sparse coefficient vectors.}, language = {en} } @inproceedings{MartinezRubioPokutta2023, author = {Mart{\´i}nez-Rubio, David and Pokutta, Sebastian}, title = {Accelerated Riemannian Optimization: Handling Constraints with a Prox to Bound Geometric Penalties}, volume = {195}, booktitle = {Proceedings of Thirty Sixth Conference on Learning Theory}, pages = {359 -- 393}, year = {2023}, abstract = {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 achieve the same convergence rates as Nesterov's accelerated gradient descent, up to a multiplicative geometric penalty and log factors. Crucially, we can enforce our method to stay within a compact set we define. Prior fully accelerated works \emph{resort to assuming} that the iterates of their algorithms stay in some pre-specified compact set, except for two previous methods of limited applicability. For our manifolds, this solves the open question in (Kim and Yang, 2022) about obtaining global general acceleration without iterates assumptively staying in the feasible set.In our solution, we design an accelerated Riemannian inexact proximal point algorithm, which is a result that was unknown even with exact access to the proximal operator, and is of independent interest. For smooth functions, we show we can implement the prox step inexactly with first-order methods in Riemannian balls of certain diameter that is enough for global accelerated optimization.}, language = {en} } @article{ŠofranacGleixnerPokutta2022, author = {Šofranac, Boro and Gleixner, Ambros and Pokutta, Sebastian}, title = {An Algorithm-independent Measure of Progress for Linear Constraint Propagation}, volume = {27}, journal = {Constraints}, doi = {10.1007/s10601-022-09338-9}, pages = {432 -- 455}, year = {2022}, language = {en} } @inproceedings{ParczykPokuttaSpiegeletal.2022, author = {Parczyk, Olaf and Pokutta, Sebastian and Spiegel, Christoph and Szab{\´o}, Tibor}, title = {New Ramsey Multiplicity Bounds and Search Heuristics}, booktitle = {Discrete Mathematics Days}, year = {2022}, abstract = {We study two related problems concerning the number of monochromatic cliques in two-colorings of the complete graph that go back to questions of Erdős. Most notably, we improve the 25-year-old upper bounds of Thomason on the Ramsey multiplicity of K4 and K5 and we settle the minimum number of independent sets of size 4 in graphs with clique number at most 4. Motivated by the elusiveness of the symmetric Ramsey multiplicity problem, we also introduce an off-diagonal variant and obtain tight results when counting monochromatic K4 or K5 in only one of the colors and triangles in the other. The extremal constructions for each problem turn out to be blow-ups of a finite graph and were found through search heuristics. They are complemented by lower bounds and stability results established using Flag Algebras, resulting in a fully computer-assisted approach. More broadly, these problems lead us to the study of the region of possible pairs of clique and independent set densities that can be realized as the limit of some sequence of graphs.}, language = {en} } @inproceedings{ParczykPokuttaSpiegeletal.2023, author = {Parczyk, Olaf and Pokutta, Sebastian and Spiegel, Christoph and Szab{\´o}, Tibor}, title = {Fully Computer-assisted Proofs in Extremal Combinatorics}, volume = {37}, booktitle = {Proceedings of the AAAI Conference on Artificial Intelligence}, number = {10}, doi = {10.1609/aaai.v37i10.26470}, pages = {12482 -- 12490}, year = {2023}, abstract = {We present a fully computer-assisted proof system for solving a particular family of problems in Extremal Combinatorics. Existing techniques using Flag Algebras have proven powerful in the past, but have so far lacked a computational counterpart to derive matching constructive bounds. We demonstrate that common search heuristics are capable of finding constructions far beyond the reach of human intuition. Additionally, the most obvious downside of such heuristics, namely a missing guarantee of global optimality, can often be fully eliminated in this case through lower bounds and stability results coming from the Flag Algebra approach. To illustrate the potential of this approach, we study two related and well-known problems in Extremal Graph Theory that go back to questions of Erdős from the 60s. Most notably, we present the first major improvement in the upper bound of the Ramsey multiplicity of the complete graph on 4 vertices in 25 years, precisely determine the first off-diagonal Ramsey multiplicity number, and settle the minimum number of independent sets of size four in graphs with clique number strictly less than five.}, language = {en} } @article{HunkenschroederPokuttaWeismantel2022, author = {Hunkenschr{\"o}der, Christoph and Pokutta, Sebastian and Weismantel, Robert}, title = {Optimizing a low-dimensional convex function over a high-dimensional cub}, journal = {SIAM Journal on Optimization}, year = {2022}, language = {en} } @inproceedings{MacDonaldBesanconPokutta2022, author = {MacDonald, Jan and Besan{\c{c}}on, Mathieu and Pokutta, Sebastian}, title = {Interpretable Neural Networks with Frank-Wolfe: Sparse Relevance Maps and Relevance Orderings}, booktitle = {Proceedings of the International Conference on Machine Learning}, year = {2022}, language = {en} } @inproceedings{TsujiTanakaPokutta2022, author = {Tsuji, Kazuma and Tanaka, Ken'ichiro and Pokutta, Sebastian}, title = {Pairwise Conditional Gradients without Swap Steps and Sparser Kernel Herding}, booktitle = {Proceedings of the International Conference on Machine Learning}, year = {2022}, language = {en} } @inproceedings{WaeldchenHuberPokutta2022, author = {W{\"a}ldchen, Stephan and Huber, Felix and Pokutta, Sebastian}, title = {Training Characteristic Functions with Reinforcement Learning: XAI-methods Play Connect Four}, booktitle = {Proceedings of the International Conference on Machine Learning}, year = {2022}, language = {en} } @inproceedings{SharmaHendrychBesanconetal.2024, author = {Sharma, Kartikey and Hendrych, Deborah and Besan{\c{c}}on, Mathieu and Pokutta, Sebastian}, title = {Network Design for the Traffic Assignment Problem with Mixed-Integer Frank-Wolfe}, booktitle = {Proceedings of INFORMS Optimization Society Conference}, year = {2024}, language = {en} } @article{BraunGuzmanPokutta2024, author = {Braun, G{\´a}bor and Guzm{\´a}n, Crist{\´o}bal and Pokutta, Sebastian}, title = {Corrections to "Lower Bounds on the Oracle Complexity of Nonsmooth Convex Optimization via Information Theory"}, volume = {70}, journal = {IEEE Transactions on Information Theory}, number = {7}, doi = {10.1109/TIT.2024.3357200}, pages = {5408 -- 5409}, year = {2024}, abstract = {This note closes a gap in the proof of Theorem VI.3 from the article "Lower Bounds on the Oracle Complexity of Nonsmooth Convex Optimization via Information Theory" (2017).}, language = {en} } @article{KreimeierPokuttaWaltheretal., author = {Kreimeier, Timo and Pokutta, Sebastian and Walther, Andrea and Woodstock, Zev}, title = {On a Frank-Wolfe approach for abs-smooth functions}, journal = {Optimization Methods and Software}, doi = {10.1080/10556788.2023.2296985}, language = {en} } @article{HunkenschroederPokuttaWeismantel2022, author = {Hunkenschr{\"o}der, Christoph and Pokutta, Sebastian and Weismantel, Robert}, title = {Optimizing a low-dimensional convex function over a high-dimensional cube}, journal = {SIAM Journal on Optimization}, year = {2022}, language = {en} } @inproceedings{ThuerckSofranacPfetschetal.2023, author = {Thuerck, Daniel and Sofranac, Boro and Pfetsch, Marc and Pokutta, Sebastian}, title = {Learning cuts via enumeration oracles}, booktitle = {Proceedings of Conference on Neural Information Processing Systems}, year = {2023}, language = {en} } @inproceedings{MartinezRubioPokutta2022, author = {Mart{\´i}nez-Rubio, David and Pokutta, Sebastian}, title = {Accelerated Riemannian optimization: Handling constraints with a prox to bound geometric penalties}, booktitle = {Proceedings of Optimization for Machine Learning (NeurIPS Workshop OPT 2022)}, year = {2022}, language = {en} } @inproceedings{MartinezRubioRouxCriscitielloetal.2023, author = {Mart{\´i}nez-Rubio, David and Roux, Christophe and Criscitiello, Christopher and Pokutta, Sebastian}, title = {Accelerated Riemannian Min-Max Optimization Ensuring Bounded Geometric Penalties}, booktitle = {Proceedings of Optimization for Machine Learning (NeurIPS Workshop OPT 2023)}, year = {2023}, language = {en} } @article{DesignolleVertesiPokutta2024, author = {Designolle, S{\´e}bastien and V{\´e}rtesi, Tam{\´a}s and Pokutta, Sebastian}, title = {Symmetric multipartite Bell inequalities via Frank-Wolfe algorithms}, volume = {109}, journal = {Physics Review A}, number = {2}, doi = {10.1103/PhysRevA.109.022205}, year = {2024}, abstract = {In multipartite Bell scenarios, we study the nonlocality robustness of the Greenberger-Horne-Zeilinger (GHZ) state. When each party performs planar measurements forming a regular polygon, we exploit the symmetry of the resulting correlation tensor to drastically accelerate the computation of (i) a Bell inequality via Frank-Wolfe algorithms and (ii) the corresponding local bound. The Bell inequalities obtained are facets of the symmetrized local polytope and they give the best-known upper bounds on the nonlocality robustness of the GHZ state for three to ten parties. Moreover, for four measurements per party, we generalize our facets and hence show, for any number of parties, an improvement on Mermin's inequality in terms of noise robustness. We also compute the detection efficiency of our inequalities and show that some give rise to the activation of nonlocality in star networks, a property that was only shown with an infinite number of measurements.}, language = {en} } @inproceedings{ChmielaKhalilGleixneretal.2021, author = {Chmiela, Antonia and Khalil, Elias B. and Gleixner, Ambros and Lodi, Andrea and Pokutta, Sebastian}, title = {Learning to Schedule Heuristics in Branch and Bound}, booktitle = {Thirty-fifth Conference on Neural Information Processing Systems, NeurIPS 2021}, arxiv = {http://arxiv.org/abs/2103.10294}, year = {2021}, abstract = {Primal heuristics play a crucial role in exact solvers for Mixed Integer Programming (MIP). While solvers are guaranteed to find optimal solutions given sufficient time, real-world applications typically require finding good solutions early on in the search to enable fast decision-making. While much of MIP research focuses on designing effective heuristics, the question of how to manage multiple MIP heuristics in a solver has not received equal attention. Generally, solvers follow hard-coded rules derived from empirical testing on broad sets of instances. Since the performance of heuristics is instance-dependent, using these general rules for a particular problem might not yield the best performance. In this work, we propose the first data-driven framework for scheduling heuristics in an exact MIP solver. By learning from data describing the performance of primal heuristics, we obtain a problem-specific schedule of heuristics that collectively find many solutions at minimal cost. We provide a formal description of the problem and propose an efficient algorithm for computing such a schedule. Compared to the default settings of a state-of-the-art academic MIP solver, we are able to reduce the average primal integral by up to 49\% on a class of challenging instances.}, language = {en} } @inproceedings{ChmielaGleixnerLichockietal.2023, author = {Chmiela, Antonia and Gleixner, Ambros and Lichocki, Pawel and Pokutta, Sebastian}, title = {Online Learning for Scheduling MIP Heuristics}, volume = {13884}, booktitle = {Integration of Constraint Programming, Artificial Intelligence, and Operations Research}, publisher = {Springer, Cham}, doi = {10.1007/978-3-031-33271-5_8}, pages = {114 -- 123}, year = {2023}, abstract = {Mixed Integer Programming (MIP) is NP-hard, and yet modern solvers often solve large real-world problems within minutes. This success can partially be attributed to heuristics. Since their behavior is highly instance-dependent, relying on hard-coded rules derived from empirical testing on a large heterogeneous corpora of benchmark instances might lead to sub-optimal performance. In this work, we propose an online learning approach that adapts the application of heuristics towards the single instance at hand. We replace the commonly used static heuristic handling with an adaptive framework exploiting past observations about the heuristic's behavior to make future decisions. In particular, we model the problem of controlling Large Neighborhood Search and Diving - two broad and complex classes of heuristics - as a multi-armed bandit problem. Going beyond existing work in the literature, we control two different classes of heuristics simultaneously by a single learning agent. We verify our approach numerically and show consistent node reductions over the MIPLIB 2017 Benchmark set. For harder instances that take at least 1000 seconds to solve, we observe a speedup of 4\%.}, language = {en} } @inproceedings{GasseBowlyCappartetal.2022, author = {Gasse, Maxime and Bowly, Simon and Cappart, Quentin and Charfreitag, Jonas and Charlin, Laurent and Ch{\´e}telat, Didier and Chmiela, Antonia and Dumouchelle, Justin and Gleixner, Ambros and Kazachkov, Aleksandr M. and Khalil, Elias and Lichocki, Pawel and Lodi, Andrea and Lubin, Miles and Maddison, Chris J. and Christopher, Morris and Papageorgiou, Dimitri J. and Parjadis, Augustin and Pokutta, Sebastian and Prouvost, Antoine and Scavuzzo, Lara and Zarpellon, Giulia and Yang, Linxin and Lai, Sha and Wang, Akang and Luo, Xiaodong and Zhou, Xiang and Huang, Haohan and Shao, Shengcheng and Zhu, Yuanming and Zhang, Dong and Quan, Tao and Cao, Zixuan and Xu, Yang and Huang, Zhewei and Zhou, Shuchang and Binbin, Chen and Minggui, He and Hao, Hao and Zhiyu, Zhang and Zhiwu, An and Kun, Mao}, title = {The Machine Learning for Combinatorial Optimization Competition (ML4CO): results and insights}, booktitle = {Proceedings of Conference on Neural Information Processing Systems}, year = {2022}, language = {en} } @article{CardereraPokuttaSchuetteetal.2025, author = {Carderera, Alejandro and Pokutta, Sebastian and Sch{\"u}tte, Christof and Weiser, Martin}, title = {An efficient first-order conditional gradient algorithm in data-driven sparse identification of nonlinear dynamics to solve sparse recovery problems under noise}, volume = {470}, journal = {Journal of Computational and Applied Mathematics}, doi = {10.1016/j.cam.2025.116675}, year = {2025}, abstract = {Governing equations are essential to the study of nonlinear dynamics, often enabling the prediction of previously unseen behaviors as well as the inclusion into control strategies. The discovery of governing equations from data thus has the potential to transform data-rich fields where well-established dynamical models remain unknown. This work contributes to the recent trend in data-driven sparse identification of nonlinear dynamics of finding the best sparse fit to observational data in a large library of potential nonlinear models. We propose an efficient first-order Conditional Gradient algorithm for solving the underlying optimization problem. In comparison to the most prominent alternative framework, the new framework shows significantly improved performance on several essential issues like sparsity-induction, structure-preservation, noise robustness, and sample efficiency. We demonstrate these advantages on several dynamics from the field of synchronization, particle dynamics, and enzyme chemistry.}, language = {en} } @inproceedings{LasbyZimmerPokuttaetal.2025, author = {Lasby, Mike and Zimmer, Max and Pokutta, Sebastian and Schultheis, Erik}, title = {Compressed sparse tiles for memory-efficient unstructured and semi-structured sparsity}, booktitle = {Proceedings of the ICLR Workshop on Sparsity in LLMs}, year = {2025}, language = {en} } @inproceedings{HaaseHanelPokutta2025, author = {Haase, Jennifer and Hanel, Paul H. P. and Pokutta, Sebastian}, title = {S-DAT: a multilingual, GenAI-driven framework for automated divergent thinking assessment}, volume = {8}, booktitle = {Proceedings of the AAAI/ACM Conference on AI, Ethics, and Society (AIES)}, pages = {1194 -- 1205}, year = {2025}, language = {en} } @article{WirthPenaPokutta2025, author = {Wirth, Elias and Pe{\~n}a, Javier and Pokutta, Sebastian}, title = {Fast convergence of Frank-Wolfe algorithms on polytopes}, journal = {INFORMS Journal on Mathematics of Operations Research}, doi = {10.1287/moor.2024.0580}, year = {2025}, language = {en} } @article{WoodstockPokutta2025, author = {Woodstock, Zev and Pokutta, Sebastian}, title = {Splitting the conditional gradient algorithm}, volume = {35}, journal = {SIAM Journal on Optimization}, number = {1}, doi = {10.1137/24M1638008}, pages = {347 -- 368}, year = {2025}, language = {en} } @article{GonnermannMuellerHaaseLeinsetal.2026, author = {Gonnermann-M{\"u}ller, Jana and Haase, Jennifer and Leins, Nicolas and Igel, Moritz and Fackeldey, Konstantin and Pokutta, Sebastian}, title = {FACET: Multi-Agent AI Supporting Teachers in Scaling Differentiated Learning for Diverse Students}, journal = {arXiv}, arxiv = {http://arxiv.org/abs/2601.22788}, doi = {https://arxiv.org/abs/2601.22788}, year = {2026}, abstract = {Classrooms are becoming increasingly heterogeneous, comprising learners with diverse performance and motivation levels, language proficiencies, and learning differences such as dyslexia and ADHD. While teachers recognize the need for differentiated instruction, growing workloads create substantial barriers, making differentiated instruction an ideal that is often unrealized in practice. Current AI educational tools, which promise differentiated materials, are predominantly student-facing and performance-centric, ignoring other aspects that shape learning outcomes. We introduce FACET, a teacher-facing multi-agent framework designed to address these gaps by supporting differentiation that accounts for motivation, performance, and learning differences. Developed with educational stakeholders from the outset, the framework coordinates four specialized agents, including learner simulation, diagnostic assessment, material generation, and evaluation within a teacher-in-the-loop design. School principals (N = 30) shaped system requirements through participatory workshops, while in-service K-12 teachers (N = 70) evaluated material quality. Mixed-methods evaluation demonstrates strong perceived value for inclusive differentiation. Practitioners emphasized both the urgent need arising from classroom heterogeneity and the importance of maintaining pedagogical autonomy as a prerequisite for adoption. We discuss implications for future school deployment and outline partnerships for longitudinal classroom implementation.}, language = {en} } @article{GonnermannMuellerHaaseFackeldeyetal.2025, author = {Gonnermann-M{\"u}ller, Jana and Haase, Jennifer and Fackeldey, Konstantin and Pokutta, Sebastian}, title = {FACET: Teacher-Centred LLM-Based Multi-Agent Systems-Towards Personalized Educational Worksheets}, arxiv = {http://arxiv.org/abs/2508.11401}, year = {2025}, abstract = {The increasing heterogeneity of student populations poses significant challenges for teachers, particularly in mathematics education, where cognitive, motivational, and emotional differences strongly influence learning outcomes. While AI-driven personalization tools have emerged, most remain performance-focused, offering limited support for teachers and neglecting broader pedagogical needs. This paper presents the FACET framework, a teacher-facing, large language model (LLM)-based multi-agent system designed to generate individualized classroom materials that integrate both cognitive and motivational dimensions of learner profiles. The framework comprises three specialized agents: (1) learner agents that simulate diverse profiles incorporating topic proficiency and intrinsic motivation, (2) a teacher agent that adapts instructional content according to didactical principles, and (3) an evaluator agent that provides automated quality assurance. We tested the system using authentic grade 8 mathematics curriculum content and evaluated its feasibility through a) automated agent-based assessment of output quality and b) exploratory feedback from K-12 in-service teachers. Results from ten internal evaluations highlighted high stability and alignment between generated materials and learner profiles, and teacher feedback particularly highlighted structure and suitability of tasks. The findings demonstrate the potential of multi-agent LLM architectures to provide scalable, context-aware personalization in heterogeneous classroom settings, and outline directions for extending the framework to richer learner profiles and real-world classroom trials.}, language = {en} }