@article{GelssKlusKnebeletal., author = {Gelß, Patrick and Klus, Stefan and Knebel, Sebastian and Shakibaei, Zarin and Pokutta, Sebastian}, title = {Low-Rank Tensor Decompositions of Quantum Circuits}, series = {Journal of Computational Physics}, journal = {Journal of Computational Physics}, abstract = {Quantum computing is arguably one of the most revolutionary and disruptive technologies of this century. Due to the ever-increasing number of potential applications as well as the continuing rise in complexity, the development, simulation, optimization, and physical realization of quantum circuits is of utmost importance for designing novel algorithms. We show how matrix product states (MPSs) and matrix product operators (MPOs) can be used to express certain quantum states, quantum gates, and entire quantum circuits as low-rank tensors. This enables the analysis and simulation of complex quantum circuits on classical computers and to gain insight into the underlying structure of the system. We present different examples to demonstrate the advantages of MPO formulations and show that they are more efficient than conventional techniques if the bond dimensions of the wave function representation can be kept small throughout the simulation.}, language = {en} } @article{KevinMartinBaermannBraunetal., author = {Kevin-Martin, Aigner and B{\"a}rmann, Andreas and Braun, Kristin and Liers, Frauke and Pokutta, Sebastian and Schneider, Oskar and Sharma, Kartikey and Tschuppik, Sebastian}, title = {Data-driven Distributionally Robust Optimization over Time}, series = {INFORMS Journal on Optimization}, volume = {5}, journal = {INFORMS Journal on Optimization}, number = {4}, doi = {10.1287/ijoo.2023.0091}, pages = {376 -- 394}, abstract = {Stochastic optimization (SO) is a classical approach for optimization under uncertainty that typically requires knowledge about the probability distribution of uncertain parameters. Because the latter is often unknown, distributionally robust optimization (DRO) provides a strong alternative that determines the best guaranteed solution over a set of distributions (ambiguity set). In this work, we present an approach for DRO over time that uses online learning and scenario observations arriving as a data stream to learn more about the uncertainty. Our robust solutions adapt over time and reduce the cost of protection with shrinking ambiguity. For various kinds of ambiguity sets, the robust solutions converge to the SO solution. Our algorithm achieves the optimization and learning goals without solving the DRO problem exactly at any step. We also provide a regret bound for the quality of the online strategy that converges at a rate of O(log T/T--√), where T is the number of iterations. Furthermore, we illustrate the effectiveness of our procedure by numerical experiments on mixed-integer optimization instances from popular benchmark libraries and give practical examples stemming from telecommunications and routing. Our algorithm is able to solve the DRO over time problem significantly faster than standard reformulations.}, language = {en} } @article{DesignolleBesanconIommazzoetal., author = {Designolle, S{\´e}bastien and Besan{\c{c}}on, Mathieu and Iommazzo, Gabriele and Knebel, Sebastian and Gelß, Patrick and Pokutta, Sebastian}, title = {Improved Local Models and New Bell Inequalities Via Frank-Wolfe Algorithms}, series = {Physical Review Research}, volume = {5}, journal = {Physical Review Research}, doi = {10.1103/PhysRevResearch.5.043059}, pages = {043059}, abstract = {In Bell scenarios with two outcomes per party, we algorithmically consider the two sides of the membership problem for the local polytope: Constructing local models and deriving separating hyperplanes, that is, Bell inequalities. We take advantage of the recent developments in so-called Frank-Wolfe algorithms to significantly increase the convergence rate of existing methods. First, we study the threshold value for the nonlocality of two-qubit Werner states under projective measurements. Here, we improve on both the upper and lower bounds present in the literature. Importantly, our bounds are entirely analytical; moreover, they yield refined bounds on the value of the Grothendieck constant of order three: 1.4367⩽KG(3)⩽1.4546. Second, we demonstrate the efficiency of our approach in multipartite Bell scenarios, and present local models for all projective measurements with visibilities noticeably higher than the entanglement threshold. We make our entire code accessible as a julia library called BellPolytopes.jl.}, language = {en} } @article{DesignolleIommazzoBesanconetal., author = {Designolle, S{\´e}bastien and Iommazzo, Gabriele and Besan{\c{c}}on, Mathieu and Knebel, Sebastian and Gelß, Patrick and Pokutta, Sebastian}, title = {Improved local models and new Bell inequalities via Frank-Wolfe algorithms}, series = {Physical Review Research}, volume = {5}, journal = {Physical Review Research}, doi = {10.1103/PhysRevResearch.5.043059}, pages = {043059}, abstract = {In Bell scenarios with two outcomes per party, we algorithmically consider the two sides of the membership problem for the local polytope: Constructing local models and deriving separating hyperplanes, that is, Bell inequalities. We take advantage of the recent developments in so-called Frank-Wolfe algorithms to significantly increase the convergence rate of existing methods. First, we study the threshold value for the nonlocality of two-qubit Werner states under projective measurements. Here, we improve on both the upper and lower bounds present in the literature. Importantly, our bounds are entirely analytical; moreover, they yield refined bounds on the value of the Grothendieck constant of order three: 1.4367⩽KG(3)⩽1.4546. Second, we demonstrate the efficiency of our approach in multipartite Bell scenarios, and present local models for all projective measurements with visibilities noticeably higher than the entanglement threshold. We make our entire code accessible as a julia library called BellPolytopes.jl.}, language = {en} } @inproceedings{PokuttaSchmaltz, author = {Pokutta, Sebastian and Schmaltz, Christian}, title = {Optimal degree of centralization of liquidity management}, series = {Proceedings of 22nd Australasian Finance and Banking Conference}, booktitle = {Proceedings of 22nd Australasian Finance and Banking Conference}, language = {en} } @inproceedings{LanPokuttaZhouetal., author = {Lan, G. and Pokutta, Sebastian and Zhou, Y. and Zink, Daniel}, title = {Conditional Accelerated Lazy Stochastic Gradient Descent}, series = {Proceedings of the International Conference on Machine Learning (ICML)}, booktitle = {Proceedings of the International Conference on Machine Learning (ICML)}, language = {en} } @inproceedings{InanlouganjiPedrielliFainekosetal., author = {Inanlouganji, A. and Pedrielli, G. and Fainekos, G. and Pokutta, Sebastian}, title = {Continuous Simulation Optimization with Model Mismatch Using Gaussian Process Regression}, series = {Proceedings of the 2018 Winter Simulation Conference}, booktitle = {Proceedings of the 2018 Winter Simulation Conference}, language = {en} } @inproceedings{PokuttaSinghTorrico, author = {Pokutta, Sebastian and Singh, M. and Torrico, A.}, title = {Efficient algorithms for robust submodular maximization under matroid constraints}, series = {ICML Workshop Paper}, booktitle = {ICML Workshop Paper}, language = {en} } @inproceedings{BraunPokuttaTuetal., author = {Braun, G{\´a}bor and Pokutta, Sebastian and Tu, Dan and Wright, Stephen}, title = {Blended Conditional Gradients: the unconditioning of conditional gradients}, series = {Proceedings of ICML}, booktitle = {Proceedings of ICML}, language = {en} } @inproceedings{DiakonikolasCardereraPokutta, author = {Diakonikolas, Jelena and Carderera, Alejandro and Pokutta, Sebastian}, title = {Breaking the Curse of Dimensionality (Locally) to Accelerate Conditional Gradients}, series = {OPTML Workshop Paper}, booktitle = {OPTML Workshop Paper}, language = {en} } @inproceedings{CombettesPokutta, author = {Combettes, Cyrille W. and Pokutta, Sebastian}, title = {Blended Matching Pursuit}, series = {Proceedings of NeurIPS}, booktitle = {Proceedings of NeurIPS}, language = {en} } @inproceedings{Kerdreuxd’AspremontPokutta, author = {Kerdreux, T. and d'Aspremont, A. and Pokutta, Sebastian}, title = {Restarting Frank-Wolfe}, series = {Proceedings of AISTATS}, booktitle = {Proceedings of AISTATS}, language = {en} } @inproceedings{AnariHaghtalabNaoretal., 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}, series = {Proceedings of AISTATS}, booktitle = {Proceedings of AISTATS}, language = {en} } @inproceedings{PokuttaSinghTorrico, author = {Pokutta, Sebastian and Singh, M. and Torrico, A.}, title = {On the Unreasonable Effectiveness of the Greedy Algorithm: Greedy Adapts to Sharpness}, series = {OPTML Workshop Paper}, booktitle = {OPTML Workshop Paper}, language = {en} } @article{PokuttaStruengmann, author = {Pokutta, Sebastian and Str{\"u}ngmann, L.}, title = {The Chase radical and reduced products}, series = {Journal of Pure and Applied Algebra}, volume = {211}, journal = {Journal of Pure and Applied Algebra}, pages = {532 -- 540}, language = {en} } @article{DrosteGoebelPokutta, author = {Droste, M. and G{\"o}bel, R. and Pokutta, Sebastian}, title = {Absolute graphs with prescribed endomorphism monoid}, series = {Semigroup Forum}, volume = {76}, journal = {Semigroup Forum}, pages = {256 -- 267}, language = {en} } @article{GoebelPokutta, author = {G{\"o}bel, R. and Pokutta, Sebastian}, title = {Construction of dual modules using Martin's axiom}, series = {Journal of Algebra}, volume = {320}, journal = {Journal of Algebra}, pages = {2388 -- 2404}, language = {en} } @article{HeldtKreuzerPokuttaetal., author = {Heldt, D. and Kreuzer, M. and Pokutta, Sebastian and Poulisse, H.}, title = {Approximate Computation of zero-dimensional polynomial ideals}, series = {Journal of Symbolic Computation}, volume = {44}, journal = {Journal of Symbolic Computation}, pages = {1566 -- 1591}, language = {en} } @article{PokuttaStauffer, author = {Pokutta, Sebastian and Stauffer, G.}, title = {France Telecom Workforce Scheduling Problem: a challenge}, series = {RAIRO-Operations Research}, journal = {RAIRO-Operations Research}, number = {43}, pages = {375 -- 386}, language = {en} } @article{BraunPokutta, author = {Braun, G{\´a}bor and Pokutta, Sebastian}, title = {Random half-integral polytopes}, series = {Operations Research Letters}, volume = {39}, journal = {Operations Research Letters}, number = {3}, pages = {204 -- 207}, language = {en} } @article{HausHemmeckePokutta, author = {Haus, Utz-Uwe and Hemmecke, R. and Pokutta, Sebastian}, title = {Reconstructing biochemical cluster networks}, series = {Journal of Mathematical Chemistry}, volume = {49}, journal = {Journal of Mathematical Chemistry}, number = {10}, pages = {2441 -- 2456}, language = {en} } @article{LetchfordPokuttaSchulz, author = {Letchford, A.N. and Pokutta, Sebastian and Schulz, A.S.}, title = {On the membership problem for the 0,1/2-closure}, series = {Operations Research Letters}, volume = {39}, journal = {Operations Research Letters}, number = {5}, pages = {301 -- 304}, language = {en} } @article{PokuttaSchulz, author = {Pokutta, Sebastian and Schulz, A.S.}, title = {Integer-empty polytopes in the 0/1-cube with maximal Gomory-Chv{\´a}tal rank}, series = {Operations Research Letters}, volume = {39}, journal = {Operations Research Letters}, number = {6}, pages = {457 -- 460}, language = {en} } @article{PokuttaSchmaltz, author = {Pokutta, Sebastian and Schmaltz, Christian}, title = {Managing liquidity: Optimal degree of centralization}, series = {Journal of Banking and Finance}, volume = {35}, journal = {Journal of Banking and Finance}, issn = {0378-4266}, doi = {DOI: 10.1016/j.jbankfin.2010.07.001}, pages = {627 -- 638}, language = {en} } @article{PokuttaStauffer, author = {Pokutta, Sebastian and Stauffer, G.}, title = {Lower bounds for the Chv{\´a}tal-Gomory rank in the 0/1 cube}, series = {Operations Research Letters}, volume = {39}, journal = {Operations Research Letters}, number = {3}, pages = {200-203}, language = {en} } @inproceedings{BraunPokutta, author = {Braun, G{\´a}bor and Pokutta, Sebastian}, title = {Rank of random half-integral polytopes}, series = {Electronic Notes in Discrete Mathematics}, volume = {36}, booktitle = {Electronic Notes in Discrete Mathematics}, pages = {415 -- 422}, language = {en} } @inproceedings{DrewesPokutta, author = {Drewes, S. and Pokutta, Sebastian}, title = {Cutting-planes for weakly-coupled 0/1 second order cone programs}, series = {Electronic Notes in Discrete Mathematics}, volume = {36}, booktitle = {Electronic Notes in Discrete Mathematics}, pages = {735 -- 742}, language = {en} } @inproceedings{DrewesPokutta, author = {Drewes, S. and Pokutta, Sebastian}, title = {Geometric mean maximization in the presence of discrete decisions}, series = {Proceedings of 23rd Australasian Finance and Banking Conference}, booktitle = {Proceedings of 23rd Australasian Finance and Banking Conference}, language = {en} } @inproceedings{MartinMuellerPokutta, author = {Martin, Alexander and M{\"u}ller, J. and Pokutta, Sebastian}, title = {On clearing coupled day-ahead electricity markets}, series = {Proceedings of 23rd Australasian Finance and Banking Conference}, booktitle = {Proceedings of 23rd Australasian Finance and Banking Conference}, language = {en} } @inproceedings{PokuttaSchulz, author = {Pokutta, Sebastian and Schulz, A.S.}, title = {On the rank of generic cutting-plane proof systems}, series = {Proceedings of IPCO, Lecture Notes in Computer Science}, volume = {6080}, booktitle = {Proceedings of IPCO, Lecture Notes in Computer Science}, pages = {450 -- 463}, language = {en} } @inproceedings{HelmkeGluchshenkoMartinetal., author = {Helmke, H. and Gluchshenko, O. and Martin, Alexander and Peter, A. and Pokutta, Sebastian and Siebert, U.}, title = {Optimal Mixed-Mode Runway Scheduling}, series = {Proceedings of DACS}, booktitle = {Proceedings of DACS}, language = {en} } @inproceedings{PokuttaSchmaltz, author = {Pokutta, Sebastian and Schmaltz, Christian}, title = {A network model for bank lending capacity}, series = {Proceedings of Systemic Risk, Basel III, Financial Stability and Regulation}, booktitle = {Proceedings of Systemic Risk, Basel III, Financial Stability and Regulation}, language = {en} } @inproceedings{PokuttaSchmaltz, author = {Pokutta, Sebastian and Schmaltz, Christian}, title = {Optimal Planning under Basel III Regulations}, series = {Proceedings of 24th Australasian Finance and Banking Conference}, booktitle = {Proceedings of 24th Australasian Finance and Banking Conference}, language = {en} } @inproceedings{BraunFioriniPokuttaetal., author = {Braun, G{\´a}bor and Fiorini, Samuel and Pokutta, Sebastian and Steurer, D.}, title = {Approximation Limits of Linear Programs (Beyond Hierarchies)}, series = {Proceedings of FOCS}, booktitle = {Proceedings of FOCS}, language = {en} } @inproceedings{BraunPokutta, author = {Braun, G{\´a}bor and Pokutta, Sebastian}, title = {An algebraic view on symmetric extended formulations}, series = {Proceedings of ISCO, Lecture Notes in Computer Science}, volume = {7422}, booktitle = {Proceedings of ISCO, Lecture Notes in Computer Science}, number = {141--152}, language = {en} } @inproceedings{FioriniMassarPokuttaetal., author = {Fiorini, Samuel and Massar, S. and Pokutta, Sebastian and Tiwary, H.R. and de Wolf, R.}, title = {Linear vs. Semidefinite Extended Formulations: Exponential Separation and Strong Lower Bounds}, series = {Proceedings of STOC}, booktitle = {Proceedings of STOC}, language = {en} } @inproceedings{SchmaltzPokuttaHeidornetal., author = {Schmaltz, Christian and Pokutta, Sebastian and Heidorn, Thomas and Andrae, Silvio}, title = {How to make regulators and shareholders happy under Basel III}, series = {Proceedings of the 26th Australasian Finance and Banking Conference}, booktitle = {Proceedings of the 26th Australasian Finance and Banking Conference}, language = {en} } @inproceedings{BrietDadushPokutta, author = {Bri{\"e}t, Jop and Dadush, Daniel and Pokutta, Sebastian}, title = {On the existence of 0/1 polytopes with high semidefinite extension complexity}, series = {Proceedings of ESA}, booktitle = {Proceedings of ESA}, language = {en} } @inproceedings{BraunPokutta, author = {Braun, Gabor and Pokutta, Sebastian}, title = {Foundations of Computer Science (FOCS), 2013 IEEE 54th Annual Symposium}, series = {Foundations of Computer Science (FOCS), 2013 IEEE 54th Annual Symposium}, booktitle = {Foundations of Computer Science (FOCS), 2013 IEEE 54th Annual Symposium}, pages = {688 -- 697}, language = {en} } @inproceedings{BraunFioriniPokutta, author = {Braun, G{\´a}bor and Fiorini, Samuel and Pokutta, Sebastian}, title = {Average case polyhedral complexity of the maximum stable set problem}, series = {Proceedings of RANDOM}, booktitle = {Proceedings of RANDOM}, language = {en} } @inproceedings{BraunPokuttaXie, author = {Braun, G{\´a}bor and Pokutta, Sebastian and Xie, Y.}, title = {Info-Greedy Sequential Adaptive Compressed Sensing}, series = {Proceedings of 52nd Annual Allerton Conference on Communication, Control, and Computing}, booktitle = {Proceedings of 52nd Annual Allerton Conference on Communication, Control, and Computing}, language = {en} } @inproceedings{BazziFioriniPokuttaetal., author = {Bazzi, Abbas and Fiorini, Samuel and Pokutta, Sebastian and Svensson, Ola}, title = {Small linear programs cannot approximate Vertex Cover within a factor of 2 - epsilon}, series = {Proceedings of FOCS}, booktitle = {Proceedings of FOCS}, language = {en} } @inproceedings{BraunPokutta, author = {Braun, G{\´a}bor and Pokutta, Sebastian}, title = {The matching polytope does not admit fully-polynomial size relaxation schemes}, series = {Proceeedings of SODA}, booktitle = {Proceeedings of SODA}, language = {en} } @inproceedings{BraunPokuttaZink, author = {Braun, G{\´a}bor and Pokutta, Sebastian and Zink, Daniel}, title = {Inapproximability of combinatorial problems via small LPs and SDPs}, series = {Proceeedings of STOC}, booktitle = {Proceeedings of STOC}, language = {en} } @inproceedings{Pokutta, author = {Pokutta, Sebastian}, title = {Information Theory and Polyhedral Combinatorics}, series = {Proceedings of 53rd Annual Allerton Conference on Communication, Control, and Computing}, booktitle = {Proceedings of 53rd Annual Allerton Conference on Communication, Control, and Computing}, language = {en} } @inproceedings{SongXiePokutta, author = {Song, R. and Xie, Y. and Pokutta, Sebastian}, title = {Sequential Sensing with Model Mismatch}, series = {Proceedings of ISIT}, booktitle = {Proceedings of ISIT}, language = {en} } @inproceedings{XieLiPokutta, author = {Xie, Y. and Li, Q. and Pokutta, Sebastian}, title = {Supervised Online Subspace Tracking}, series = {Proceedings of Asilomar Conference on Signals, Systems, and Computers}, booktitle = {Proceedings of Asilomar Conference on Signals, Systems, and Computers}, language = {en} } @inproceedings{RoyPokutta, author = {Roy, Aurko and Pokutta, Sebastian}, title = {Hierarchical Clustering via Spreading Metrics}, series = {Proceedings of NIPS}, booktitle = {Proceedings of NIPS}, language = {en} } @inproceedings{BraunRoyPokutta, author = {Braun, G{\´a}bor and Roy, Aurko and Pokutta, Sebastian}, title = {Stronger Reductions for Extended Formulations}, series = {Proceedings of IPCO}, booktitle = {Proceedings of IPCO}, language = {en} } @inproceedings{BraunBrownCohenHuqetal., 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}, series = {Proceddings of SODA 2016}, booktitle = {Proceddings of SODA 2016}, language = {en} } @inproceedings{RoyXuPokutta, author = {Roy, Aurko and Xu, Huan and Pokutta, Sebastian}, title = {Reinforcement Learning under Model Mismatch}, series = {Proceedings of NIPS}, booktitle = {Proceedings of NIPS}, language = {en} } @inproceedings{BaermannPokuttaSchneider, author = {B{\"a}rmann, Andreas and Pokutta, Sebastian and Schneider, Oskar}, title = {Emulating the Expert: Inverse Optimization through Online Learning}, series = {Proceedings of the International Conference on Machine Learning (ICML)}, booktitle = {Proceedings of the International Conference on Machine Learning (ICML)}, language = {en} } @inproceedings{BraunPokuttaZink, author = {Braun, G{\´a}bor and Pokutta, Sebastian and Zink, Daniel}, title = {Lazifying Conditional Gradient Algorithms}, series = {Proceedings of the International Conference on Machine Learning (ICML)}, booktitle = {Proceedings of the International Conference on Machine Learning (ICML)}, language = {en} } @inproceedings{ArumugamKadampotTahmasbietal., author = {Arumugam, Keerthi Suria Kumar and Kadampot, Ishaque Ashar and Tahmasbi, Mehrdad and Shah, Shaswat and Bloch, Matthieu and Pokutta, Sebastian}, title = {Modulation Recognition Using Side Information and Hybrid Learning}, series = {Proceedings of IEEE DySPAN}, booktitle = {Proceedings of IEEE DySPAN}, language = {en} } @article{PokuttaSpiegelZimmer, author = {Pokutta, Sebastian and Spiegel, Christoph and Zimmer, Max}, title = {Deep Neural Network Training with Frank-Wolfe}, 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{CryilleWSpiegelPokutta, author = {Cryille W., Combettes and Spiegel, Christoph and Pokutta, Sebastian}, title = {Projection-Free Adaptive Gradients for Large-Scale Optimization}, 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{PfetschPokutta, author = {Pfetsch, Marc and Pokutta, Sebastian}, title = {IPBoost - Non-Convex Boosting via Integer Programming}, series = {Proceedings of ICML}, booktitle = {Proceedings of ICML}, language = {en} } @inproceedings{PokuttaSinghTorrico, author = {Pokutta, Sebastian and Singh, M. and Torrico, A.}, title = {On the Unreasonable Effectiveness of the Greedy Algorithm: Greedy Adapts to Sharpness}, series = {Proceedings of ICML}, booktitle = {Proceedings of ICML}, language = {en} } @inproceedings{DiakonikolasCardereraPokutta, author = {Diakonikolas, Jelena and Carderera, Alejandro and Pokutta, Sebastian}, title = {Locally Accelerated Conditional Gradients}, series = {Proceedings of AISTATS}, booktitle = {Proceedings of AISTATS}, language = {en} } @article{AnariHaghtalabNaoretal., 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}, series = {INFORMS Journal on Computing}, journal = {INFORMS Journal on Computing}, language = {en} } @inproceedings{CombettesPokutta, author = {Combettes, Cyrille W. and Pokutta, Sebastian}, title = {Boosting Frank-Wolfe by Chasing Gradients}, series = {Proceedings of ICML}, booktitle = {Proceedings of ICML}, language = {en} } @inproceedings{MortagyGuptaPokutta, author = {Mortagy, Hassan and Gupta, Swati and Pokutta, Sebastian}, title = {Walking in the Shadow: A New Perspective on Descent Directions for Constrained Minimization}, series = {Proceedings of NeurIPS}, booktitle = {Proceedings of NeurIPS}, language = {en} } @inproceedings{Pokutta, author = {Pokutta, Sebastian}, title = {Restarting Algorithms: Sometimes there is Free Lunch}, series = {Proceedings of CPAIOR}, booktitle = {Proceedings of CPAIOR}, language = {en} } @article{Le BodicPfetschPavelkaetal., author = {Le Bodic, P. and Pfetsch, Marc and Pavelka, J. and Pokutta, Sebastian}, title = {Solving MIPs via Scaling-based Augmentation}, series = {Discrete Optimization}, volume = {27}, journal = {Discrete Optimization}, pages = {1 -- 25}, language = {en} } @article{BraunRoyPokutta, author = {Braun, G{\´a}bor and Roy, Aurko and Pokutta, Sebastian}, title = {Stronger Reductions for Extended Formulations}, series = {to appear in Mathematical Programming B}, journal = {to appear in Mathematical Programming B}, language = {en} } @article{SongXiePokutta, author = {Song, R. and Xie, Y. and Pokutta, Sebastian}, title = {On the effect of model mismatch for sequential Info-Greedy Sensing}, series = {EURASIP Journal on Advances in Signal Processing}, journal = {EURASIP Journal on Advances in Signal Processing}, language = {en} } @article{BraunPokuttaZink, author = {Braun, G{\´a}bor and Pokutta, Sebastian and Zink, Daniel}, title = {Affine Reductions for LPs and SDPs}, series = {Mathematical Programming A}, volume = {173}, journal = {Mathematical Programming A}, number = {1}, pages = {281 -- 312}, language = {en} } @article{BraunPokuttaZink, author = {Braun, G{\´a}bor and Pokutta, Sebastian and Zink, Daniel}, title = {Lazifying Conditional Gradient Algorithms}, series = {Journal of Machine Learning Research (JMLR)}, volume = {20}, journal = {Journal of Machine Learning Research (JMLR)}, number = {71}, pages = {1 -- 42}, language = {en} } @article{BaermannHeidtMartinetal., author = {B{\"a}rmann, Andreas and Heidt, Andreas and Martin, Alex and er, and Pokutta, Sebastian and Thurner, Christoph}, title = {Polyhedral Approximation of Ellipsoidal Uncertainty Sets via Extended Formulations - a computational case study}, series = {Computational Management Science}, volume = {13}, journal = {Computational Management Science}, number = {2}, pages = {151 -- 193}, language = {en} } @article{RoyPokutta, author = {Roy, Aurko and Pokutta, Sebastian}, title = {Hierarchical Clustering via Spreading Metrics}, series = {Journal of Machine Learning Research (JMLR)}, volume = {18}, journal = {Journal of Machine Learning Research (JMLR)}, pages = {1 -- 35}, language = {en} } @article{BodurDel PiaDeyetal., author = {Bodur, Merve and Del Pia, Alberto and Dey, Santanu Sabush and Molinaro, Marco and Pokutta, Sebastian}, title = {Aggregation-based cutting-planes for packing and covering Integer Programs}, series = {to appear in Mathematical Programming A}, journal = {to appear in Mathematical Programming A}, language = {en} } @article{BazziFioriniPokuttaetal., author = {Bazzi, Abbas and Fiorini, Samuel and Pokutta, Sebastian and Svensson, Ola}, title = {Small linear programs cannot approximate Vertex Cover within a factor of 2 - epsilon}, series = {to appear in Mathematics of Operations Research}, journal = {to appear in Mathematics of Operations Research}, language = {en} } @article{BraunGuzmanPokutta, author = {Braun, G{\´a}bor and Guzm{\´a}n, C. and Pokutta, Sebastian}, title = {Unifying Lower Bounds on the Oracle Complexity of Nonsmooth Convex Optimization}, series = {IEEE Transactions of Information Theory}, volume = {63}, journal = {IEEE Transactions of Information Theory}, number = {7}, pages = {4709 -- 4724}, language = {en} } @article{BraunJainLeeetal., author = {Braun, G{\´a}bor and Jain, R. and Lee, T. and Pokutta, Sebastian}, title = {Information-theoretic approximations of the nonnegative rank}, series = {Computational Complexity}, volume = {26}, journal = {Computational Complexity}, number = {1}, pages = {147 -- 197}, language = {en} } @article{ChristensenKhanPokuttaetal., author = {Christensen, H. and Khan, A. and Pokutta, Sebastian and Tetali, P.}, title = {Multidimensional Bin Packing and Other Related Problems: A survey}, series = {to appear in Computer Science Review}, journal = {to appear in Computer Science Review}, language = {en} } @article{MartinMuellerPapeetal., author = {Martin, Alex and M{\"u}ller, J. and Pape, S. and Peter, A. and Pokutta, Sebastian and Winter, T.}, title = {Pricing and clearing combinatorial markets with singleton and swap orders}, series = {Mathematical Methods of Operations Research}, volume = {85}, journal = {Mathematical Methods of Operations Research}, number = {2}, pages = {155 -- 177}, language = {en} } @article{KnuevenOstrowskiPokutta, author = {Knueven, B. and Ostrowski, J. and Pokutta, Sebastian}, title = {Detecting Almost Symmetries in Graphs}, series = {to appear in Mathematical Programming C}, journal = {to appear in Mathematical Programming C}, language = {en} } @article{BraunBrownCohenHuqetal., 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}, series = {Mathematical Programming A}, volume = {165}, journal = {Mathematical Programming A}, number = {2}, pages = {643 -- 662}, language = {en} } @article{BraunPokutta, author = {Braun, G{\´a}bor and Pokutta, Sebastian}, title = {Rigid abelian groups and the probabilistic method}, series = {Contemporary Mathematics}, volume = {576}, journal = {Contemporary Mathematics}, pages = {17 -- 30}, language = {en} } @article{GoebelPokutta, author = {G{\"o}bel, R. and Pokutta, Sebastian}, title = {Absolutely rigid fields and Shelah's absolutely rigid trees}, series = {Contemporary Mathematics}, volume = {576}, journal = {Contemporary Mathematics}, pages = {105 -- 128}, language = {en} } @article{PokuttaSchmaltz, author = {Pokutta, Sebastian and Schmaltz, Christian}, title = {Optimal Planning under Basel III Regulations}, series = {Cass-Capco Institute Paper Series on Risk}, volume = {34}, journal = {Cass-Capco Institute Paper Series on Risk}, language = {en} } @article{KrollPokutta, author = {Kroll, C. and Pokutta, Sebastian}, title = {Just a perfect day: developing a happiness optimised day schedule}, series = {Journal of Economic Psychology}, volume = {34}, journal = {Journal of Economic Psychology}, pages = {210 -- 217}, language = {en} } @article{PokuttaVanVyve, author = {Pokutta, Sebastian and VanVyve, M.}, title = {A note on the extension complexity of the knapsack polytope}, series = {Operations Research Letters}, volume = {41}, journal = {Operations Research Letters}, pages = {347 -- 350}, language = {en} } @article{SchmaltzPokuttaHeidornetal., author = {Schmaltz, Christian and Pokutta, Sebastian and Heidorn, Thomas and Andrae, Silvio}, title = {How to make regulators and shareholders happy under Basel III}, series = {Journal of Banking and Finance}, journal = {Journal of Banking and Finance}, pages = {311 -- 325}, language = {en} } @article{BraunPokutta, author = {Braun, G{\´a}bor and Pokutta, Sebastian}, title = {A short proof for the polyhedrality of the Chv{\´a}tal-Gomory closure of a compact convex set}, series = {Operations Research Letters}, volume = {42}, journal = {Operations Research Letters}, pages = {307 -- 310}, language = {en} } @article{DrewesPokutta, author = {Drewes, S. and Pokutta, Sebastian}, title = {Computing discrete expected utility maximizing portfolios}, series = {Journal of Investing}, volume = {23}, journal = {Journal of Investing}, number = {4}, pages = {121 -- 132}, language = {en} } @article{DrewesPokutta, author = {Drewes, S. and Pokutta, Sebastian}, title = {Symmetry-exploiting cuts for a class of mixed-0/1 second order cone programs}, series = {Discrete Optimization}, volume = {13}, journal = {Discrete Optimization}, pages = {23 -- 35}, language = {en} } @article{MartinMuellerPokutta, author = {Martin, Alexander and M{\"u}ller, J. and Pokutta, Sebastian}, title = {Strict linear prices in non-convex European day-ahead electricity markets}, series = {Optimization Methods and Software}, volume = {29}, journal = {Optimization Methods and Software}, number = {1}, pages = {189 -- 221}, language = {en} } @article{BrietDadushPokutta, author = {Bri{\"e}t, Jop and Dadush, Daniel and Pokutta, Sebastian}, title = {On the existence of 0/1 polytopes with high semidefinite extension complexity}, series = {Mathematical Programming B}, volume = {153}, journal = {Mathematical Programming B}, number = {1}, pages = {179 -- 199}, language = {en} } @article{BraunFioriniPokuttaetal., author = {Braun, G{\´a}bor and Fiorini, Samuel and Pokutta, Sebastian and Steurer, D.}, title = {Approximation Limits of Linear Programs (Beyond Hierarchies)}, series = {Mathematics of Operations Research}, volume = {40}, journal = {Mathematics of Operations Research}, number = {3}, pages = {179 -- 199}, language = {en} } @article{BraunPokutta, author = {Braun, G{\´a}bor and Pokutta, Sebastian}, title = {The matching polytope does not admit fully-polynomial size relaxation schemes}, series = {IEEE Transactions on Information Theory}, volume = {61}, journal = {IEEE Transactions on Information Theory}, number = {10}, pages = {1 -- 11}, language = {en} } @article{BraunPokuttaXie, author = {Braun, G{\´a}bor and Pokutta, Sebastian and Xie, Y.}, title = {Info-Greedy Sequential Adaptive Compressed Sensing}, series = {IEEE Journal of Selected Topics in Signal Processing}, volume = {9}, journal = {IEEE Journal of Selected Topics in Signal Processing}, number = {4}, pages = {601 -- 611}, language = {en} } @article{FioriniMassarPokuttaetal., author = {Fiorini, Samuel and Massar, S. and Pokutta, Sebastian and Tiwary, H.R. and de Wolf, R.}, title = {Exponential Lower Bounds for Polytopes in Combinatorial Optimization}, series = {Journal of the ACM}, volume = {62}, journal = {Journal of the ACM}, number = {2}, pages = {1 -- 17}, language = {en} } @article{BraunFioriniPokutta, author = {Braun, G{\´a}bor and Fiorini, Samuel and Pokutta, Sebastian}, title = {Average case polyhedral complexity of the maximum stable set problem}, series = {Mathematical Programming A}, volume = {160}, journal = {Mathematical Programming A}, number = {1}, pages = {407 -- 431}, language = {en} } @article{BraunPokutta, author = {Braun, G{\´a}bor and Pokutta, Sebastian}, title = {A polyhedral characterization of Border Bases}, series = {SIAM Journal on Discrete Mathematics}, volume = {30}, journal = {SIAM Journal on Discrete Mathematics}, number = {1}, pages = {239 -- 265}, language = {en} } @article{BraunPokutta, author = {Braun, G{\´a}bor and Pokutta, Sebastian}, title = {Common information and unique disjointness}, series = {Algorithmica}, volume = {76}, journal = {Algorithmica}, number = {3}, pages = {597 -- 629}, language = {en} } @article{GatzertPokuttaVogl, author = {Gatzert, Nadine and Pokutta, Sebastian and Vogl, Nikolai}, title = {Convergence of Capital and Insurance Markets: Pricing Aspects of Index-Linked Catastrophic Loss Instruments}, series = {to appear in Journal of Risk and Insurance}, journal = {to appear in Journal of Risk and Insurance}, language = {en} } @inproceedings{CardereraDiakonikolasLinetal., author = {Carderera, Alejandro and Diakonikolas, Jelena and Lin, Cheuk Yin and Pokutta, Sebastian}, title = {Parameter-free Locally Accelerated Conditional Gradients}, series = {ICML 2021}, booktitle = {ICML 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{BienenstockMunozPokutta, author = {Bienenstock, Daniel and Mu{\~n}oz, Gonzalo and Pokutta, Sebastian}, title = {Principled Deep Neural Network Training through Linear Programming}, 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'AspremontPokutta, author = {Kerdreux, Thomas and d'Aspremont, Alexandre and Pokutta, Sebastian}, title = {Projection-Free Optimization on Uniformly Convex Sets}, series = {To Appear in Proceedings of AISTATS}, booktitle = {To Appear in Proceedings of AISTATS}, language = {en} } @article{CardereraPokutta, author = {Carderera, Alejandro and Pokutta, Sebastian}, title = {Second-order Conditional Gradient Sliding}, 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{Kerdreuxd'AspremontPokutta, author = {Kerdreux, Thomas and d'Aspremont, Alexandre and Pokutta, Sebastian}, title = {Local and Global Uniform Convexity Conditions}, 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} } @article{BaermannMartinPokuttaetal., author = {B{\"a}rmann, Andreas and Martin, Alexander and Pokutta, Sebastian and Schneider, Oskar}, title = {An Online-Learning Approach to Inverse Optimization}, language = {en} } @inproceedings{ParczykPokuttaSpiegeletal., author = {Parczyk, Olaf and Pokutta, Sebastian and Spiegel, Christoph and Szab{\´o}, Tibor}, title = {New Ramsey Multiplicity Bounds and Search Heuristics}, series = {Discrete Mathematics Days}, booktitle = {Discrete Mathematics Days}, 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} } @article{HunkenschroederPokuttaWeismantel, author = {Hunkenschr{\"o}der, Christoph and Pokutta, Sebastian and Weismantel, Robert}, title = {Optimizing a low-dimensional convex function over a high-dimensional cub}, series = {SIAM Journal on Optimization}, journal = {SIAM Journal on Optimization}, language = {en} } @inproceedings{WaeldchenHuberPokutta, author = {W{\"a}ldchen, Stephan and Huber, Felix and Pokutta, Sebastian}, title = {Training Characteristic Functions with Reinforcement Learning: XAI-methods Play Connect Four}, series = {Proceedings of the International Conference on Machine Learning}, booktitle = {Proceedings of the International Conference on Machine Learning}, language = {en} } @inproceedings{TsujiTanakaPokutta, author = {Tsuji, Kazuma and Tanaka, Ken'ichiro and Pokutta, Sebastian}, title = {Pairwise Conditional Gradients without Swap Steps and Sparser Kernel Herding}, series = {Proceedings of the International Conference on Machine Learning}, booktitle = {Proceedings of the International Conference on Machine Learning}, language = {en} } @article{RouxPokuttaWirthetal., author = {Roux, Christophe and Pokutta, Sebastian and Wirth, Elias and Kerdreux, Thomas}, title = {Efficient Online-Bandit Strategies for Minimax Learning Problems}, 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{KossenHirzelMadaietal., 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}, series = {Frontiers in Artificial Intelligence}, journal = {Frontiers in Artificial Intelligence}, doi = {https://doi.org/10.3389/frai.2022.813842}, 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{CriadoMartinezRubioPokutta, author = {Criado, Francisco and Mart{\´i}nez-Rubio, David and Pokutta, Sebastian}, title = {Fast Algorithms for Packing Proportional Fairness and its Dual}, series = {Proceedings of the Conference on Neural Information Processing Systems}, volume = {36}, booktitle = {Proceedings of the Conference on Neural Information Processing Systems}, 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} } @article{CardereraPokuttaSchuetteetal., author = {Carderera, Alejandro and Pokutta, Sebastian and Sch{\"u}tte, Christof and Weiser, Martin}, title = {CINDy: Conditional gradient-based Identification of Non-linear Dynamics - Noise-robust recovery}, series = {Journal of Computational and Applied Mathematics}, journal = {Journal of Computational and Applied Mathematics}, 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{CombettesPokutta, author = {Combettes, Cyrille and Pokutta, Sebastian}, title = {Revisiting the Approximate Carath{\´e}odory Problem via the Frank-Wolfe Algorithm}, series = {Mathematical Programming}, volume = {197}, journal = {Mathematical Programming}, doi = {10.1007/s10107-021-01735-x}, pages = {191 -- 214}, language = {en} } @inproceedings{SofranacGleixnerPokutta, author = {Sofranac, Boro and Gleixner, Ambros and Pokutta, Sebastian}, title = {An Algorithm-Independent Measure of Progress for Linear Constraint Propagation}, series = {27th International Conference on Principles and Practice of Constraint Programming (CP 2021)}, 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}, 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} } @inproceedings{ChmielaGleixnerLichockietal., author = {Chmiela, Antonia and Gleixner, Ambros and Lichocki, Pawel and Pokutta, Sebastian}, title = {Online Learning for Scheduling MIP Heuristics}, series = {Integration of Constraint Programming, Artificial Intelligence, and Operations Research}, 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}, 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} } @article{ŠofranacGleixnerPokutta, author = {Šofranac, Boro and Gleixner, Ambros and Pokutta, Sebastian}, title = {An Algorithm-independent Measure of Progress for Linear Constraint Propagation}, series = {Constraints}, volume = {27}, journal = {Constraints}, doi = {10.1007/s10601-022-09338-9}, pages = {432 -- 455}, 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}, series = {Thirty-fifth Conference on Neural Information Processing Systems, NeurIPS 2021}, booktitle = {Thirty-fifth Conference on Neural Information Processing Systems, NeurIPS 2021}, 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} } @article{ŠofranacGleixnerPokutta, author = {Šofranac, Boro and Gleixner, Ambros and Pokutta, Sebastian}, title = {Accelerating domain propagation: An efficient GPU-parallel algorithm over sparse matrices}, series = {Parallel Computing}, volume = {109}, journal = {Parallel Computing}, doi = {10.1016/j.parco.2021.102874}, pages = {102874}, 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{SofranacGleixnerPokutta, author = {Sofranac, Boro and Gleixner, Ambros and Pokutta, Sebastian}, title = {Accelerating Domain Propagation: an Efficient GPU-Parallel Algorithm over Sparse Matrices}, series = {2020 IEEE/ACM 10th Workshop on Irregular Applications: Architectures and Algorithms (IA3)}, booktitle = {2020 IEEE/ACM 10th Workshop on Irregular Applications: Architectures and Algorithms (IA3)}, doi = {10.1109/IA351965.2020.00007}, pages = {1 -- 11}, 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} } @inproceedings{MartinezRubioWirthPokutta, author = {Mart{\´i}nez-Rubio, David and Wirth, Elias and Pokutta, Sebastian}, title = {Accelerated and Sparse Algorithms for Approximate Personalized PageRank and Beyond}, series = {Proceedings of Machine Learning Research}, volume = {195}, booktitle = {Proceedings of Machine Learning Research}, pages = {1 -- 35}, 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} } @inproceedings{ParczykPokuttaSpiegeletal., author = {Parczyk, Olaf and Pokutta, Sebastian and Spiegel, Christoph and Szab{\´o}, Tibor}, title = {Fully Computer-assisted Proofs in Extremal Combinatorics}, series = {Proceedings of the AAAI Conference on Artificial Intelligence}, volume = {37}, booktitle = {Proceedings of the AAAI Conference on Artificial Intelligence}, number = {10}, doi = {10.1609/aaai.v37i10.26470}, pages = {12482 -- 12490}, 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{FaenzaMunozPokutta, author = {Faenza, Yuri and Mu{\~n}oz, Gonzalo and Pokutta, Sebastian}, title = {New Limits of Treewidth-based tractability in Optimization}, series = {Mathematical Programming}, volume = {191}, journal = {Mathematical Programming}, doi = {10.1007/s10107-020-01563-5}, pages = {559 -- 594}, language = {en} } @inproceedings{WirthPokutta, author = {Wirth, Elias and Pokutta, Sebastian}, title = {Conditional Gradients for the Approximately Vanishing Ideal}, series = {Proceedings of The 25th International Conference on Artificial Intelligence and Statistics}, volume = {151}, booktitle = {Proceedings of The 25th International Conference on Artificial Intelligence and Statistics}, pages = {2191 -- 2209}, 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} } @article{KerdreuxRouxd'Aspremontetal., author = {Kerdreux, Thomas and Roux, Christophe and d'Aspremont, Alexandre and Pokutta, Sebastian}, title = {Linear Bandits on Uniformly Convex Sets}, series = {Journal of Machine Learning Research}, volume = {22}, journal = {Journal of Machine Learning Research}, number = {284}, pages = {1 -- 23}, 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} } @inproceedings{MartinezRubioPokutta, author = {Mart{\´i}nez-Rubio, David and Pokutta, Sebastian}, title = {Accelerated Riemannian Optimization: Handling Constraints with a Prox to Bound Geometric Penalties}, series = {Proceedings of Thirty Sixth Conference on Learning Theory}, volume = {195}, booktitle = {Proceedings of Thirty Sixth Conference on Learning Theory}, pages = {359 -- 393}, 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} } @inproceedings{DeyPokutta, author = {Dey, Santanu Sabush and Pokutta, Sebastian}, title = {Design and verify: a new scheme for generating cutting-planes}, series = {Proceedings of IPCO, Lecture Notes in Computer Science}, volume = {6655}, booktitle = {Proceedings of IPCO, Lecture Notes in Computer Science}, pages = {143 -- 155}, language = {en} } @article{DeyPokutta, author = {Dey, Santanu Sabush and Pokutta, Sebastian}, title = {Design and verify: a new scheme for generating cutting-planes}, series = {Mathematical Programming A}, volume = {145}, journal = {Mathematical Programming A}, pages = {199 -- 222}, language = {en} } @article{BienstockMunozPokutta, author = {Bienstock, Daniel and Mu{\~n}oz, Gonzalo and Pokutta, Sebastian}, title = {Principled Deep Neural Network Training Through Linear Programming}, series = {Discrete Optimization}, volume = {49}, journal = {Discrete Optimization}, doi = {10.1016/j.disopt.2023.100795}, 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{CardereraPokuttaMathieu, 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}, series = {Thirty-fifth Conference on Neural Information Processing Systems, NeurIPS 2021}, booktitle = {Thirty-fifth Conference on Neural Information Processing Systems, NeurIPS 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{MathieuCardereraPokutta, 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}, series = {INFORMS Journal on Computing}, volume = {34}, journal = {INFORMS Journal on Computing}, number = {5}, doi = {10.1287/ijoc.2022.1191}, pages = {2383 -- 2865}, 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} } @inproceedings{MacDonaldBesanconPokutta, 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}, series = {Proceedings of the International Conference on Machine Learning}, booktitle = {Proceedings of the International Conference on Machine Learning}, language = {en} } @inproceedings{WirthKerdreuxPokutta, author = {Wirth, Elias and Kerdreux, Thomas and Pokutta, Sebastian}, title = {Acceleration of Frank-Wolfe Algorithms with Open Loop Step-sizes}, series = {Proceedings of International Conference on Artificial Intelligence and Statistics}, booktitle = {Proceedings of International Conference on Artificial Intelligence and Statistics}, language = {en} } @inproceedings{ZimmerSpiegelPokutta, author = {Zimmer, Max and Spiegel, Christoph and Pokutta, Sebastian}, title = {How I Learned to Stop Worrying and Love Retraining}, series = {Proceedings of International Conference on Learning Representations}, booktitle = {Proceedings of International Conference on Learning Representations}, language = {en} } @inproceedings{WaeldchenSharmaZimmeretal., author = {W{\"a}ldchen, Stephan and Sharma, Kartikey and Zimmer, Max and Turan, Berkant and Pokutta, Sebastian}, title = {Merlin-Arthur classifiers}, series = {Proceedings of International Conference on Artificial Intelligence and Statistics}, booktitle = {Proceedings of International Conference on Artificial Intelligence and Statistics}, language = {en} } @article{Pokutta, author = {Pokutta, Sebastian}, title = {The Frank-Wolfe algorithm: a short introduction}, series = {Jahresbericht der Deutschen Mathematiker-Vereinigung}, journal = {Jahresbericht der Deutschen Mathematiker-Vereinigung}, language = {en} } @inproceedings{ZimmerSpiegelPokutta, author = {Zimmer, Max and Spiegel, Christoph and Pokutta, Sebastian}, title = {Sparse Model Soups}, series = {Proceedings of International Conference on Learning Representations}, booktitle = {Proceedings of International Conference on Learning Representations}, language = {en} } @inproceedings{GasseBowlyCappartetal., 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}, series = {Proceedings of Conference on Neural Information Processing Systems}, booktitle = {Proceedings of Conference on Neural Information Processing Systems}, language = {en} } @inproceedings{WirthKeraPokutta, author = {Wirth, Elias and Kera, and Pokutta, Sebastian}, title = {Approximate Vanishing Ideal Computations at Scale}, series = {Proceedings of International Conference on Learning Representations}, booktitle = {Proceedings of International Conference on Learning Representations}, language = {en} } @inproceedings{MartinezRubioRouxCriscitielloetal., 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}, series = {Proceedings of Optimization for Machine Learning (NeurIPS Workshop OPT 2023)}, booktitle = {Proceedings of Optimization for Machine Learning (NeurIPS Workshop OPT 2023)}, language = {en} } @inproceedings{MartinezRubioPokutta, author = {Mart{\´i}nez-Rubio, David and Pokutta, Sebastian}, title = {Accelerated Riemannian optimization: Handling constraints with a prox to bound geometric penalties}, series = {Proceedings of Optimization for Machine Learning (NeurIPS Workshop OPT 2022)}, booktitle = {Proceedings of Optimization for Machine Learning (NeurIPS Workshop OPT 2022)}, language = {en} } @article{HunkenschroederPokuttaWeismantel, author = {Hunkenschr{\"o}der, Christoph and Pokutta, Sebastian and Weismantel, Robert}, title = {Optimizing a low-dimensional convex function over a high-dimensional cube}, series = {SIAM Journal on Optimization}, journal = {SIAM Journal on Optimization}, language = {en} } @inproceedings{ThuerckSofranacPfetschetal., author = {Thuerck, Daniel and Sofranac, Boro and Pfetsch, Marc and Pokutta, Sebastian}, title = {Learning cuts via enumeration oracles}, series = {Proceedings of Conference on Neural Information Processing Systems}, booktitle = {Proceedings of Conference on Neural Information Processing Systems}, language = {en} } @inproceedings{SharmaHendrychBesanconetal., 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}, series = {Proceedings of INFORMS Optimization Society Conference}, booktitle = {Proceedings of INFORMS Optimization Society Conference}, 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}, series = {Optimization Methods and Software}, journal = {Optimization Methods and Software}, doi = {10.1080/10556788.2023.2296985}, language = {en} } @article{DesignolleVertesiPokutta, author = {Designolle, S{\´e}bastien and V{\´e}rtesi, Tam{\´a}s and Pokutta, Sebastian}, title = {Symmetric multipartite Bell inequalities via Frank-Wolfe algorithms}, series = {Physics Review A}, volume = {109}, journal = {Physics Review A}, number = {2}, doi = {10.1103/PhysRevA.109.022205}, 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} } @article{DezaPokuttaPournin, author = {Deza, Antoine and Pokutta, Sebastian and Pournin, Lionel}, title = {The complexity of geometric scaling}, series = {Operations Research Letters}, volume = {52}, journal = {Operations Research Letters}, doi = {10.1016/j.orl.2023.11.010}, pages = {107057}, language = {en} } @article{BraunGuzmanPokutta, author = {Braun, G{\´a}bor and Guzm{\´a}n, Crist{\´o}bal and Pokutta, Sebastian}, title = {Corrigendum in "Lower Bounds on the Oracle Complexity of Nonsmooth Convex Optimization via Information Theory"}, series = {IEEE Transactions on Information Theory}, journal = {IEEE Transactions on Information Theory}, doi = {10.1109/TIT.2024.3357200}, language = {en} }