@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} } @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} }