@article{DesignolleBesanconIommazzoetal.2023, 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}, volume = {5}, journal = {Physical Review Research}, doi = {10.1103/PhysRevResearch.5.043059}, pages = {043059}, year = {2023}, 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{KevinMartinBaermannBraunetal.2023, 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}, volume = {5}, journal = {INFORMS Journal on Optimization}, number = {4}, doi = {10.1287/ijoo.2023.0091}, pages = {376 -- 394}, year = {2023}, 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{GelssKlusKnebeletal.2022, author = {Gelß, Patrick and Klus, Stefan and Knebel, Sebastian and Shakibaei, Zarin and Pokutta, Sebastian}, title = {Low-Rank Tensor Decompositions of Quantum Circuits}, journal = {Journal of Computational Physics}, arxiv = {http://arxiv.org/abs/2205.09882}, year = {2022}, 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{DesignolleIommazzoBesanconetal.2023, 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}, volume = {5}, journal = {Physical Review Research}, doi = {10.1103/PhysRevResearch.5.043059}, pages = {043059}, year = {2023}, 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{KnuevenOstrowskiPokutta2017, author = {Knueven, B. and Ostrowski, J. and Pokutta, Sebastian}, title = {Detecting Almost Symmetries in Graphs}, journal = {to appear in Mathematical Programming C}, year = {2017}, language = {en} } @article{BraunBrownCohenHuqetal.2017, 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}, volume = {165}, journal = {Mathematical Programming A}, number = {2}, arxiv = {http://arxiv.org/abs/1504.00703}, pages = {643 -- 662}, year = {2017}, language = {en} } @article{Le BodicPfetschPavelkaetal.2018, author = {Le Bodic, P. and Pfetsch, Marc and Pavelka, J. and Pokutta, Sebastian}, title = {Solving MIPs via Scaling-based Augmentation}, volume = {27}, journal = {Discrete Optimization}, arxiv = {http://arxiv.org/abs/1509.03206}, pages = {1 -- 25}, year = {2018}, language = {en} } @article{BraunRoyPokutta2018, author = {Braun, G{\´a}bor and Roy, Aurko and Pokutta, Sebastian}, title = {Stronger Reductions for Extended Formulations}, journal = {to appear in Mathematical Programming B}, arxiv = {http://arxiv.org/abs/1512.04932}, year = {2018}, language = {en} } @article{SongXiePokutta2018, author = {Song, R. and Xie, Y. and Pokutta, Sebastian}, title = {On the effect of model mismatch for sequential Info-Greedy Sensing}, journal = {EURASIP Journal on Advances in Signal Processing}, year = {2018}, language = {en} } @article{BraunPokuttaZink2019, author = {Braun, G{\´a}bor and Pokutta, Sebastian and Zink, Daniel}, title = {Affine Reductions for LPs and SDPs}, volume = {173}, journal = {Mathematical Programming A}, number = {1}, arxiv = {http://arxiv.org/abs/1410.8816}, pages = {281 -- 312}, year = {2019}, language = {en} } @article{BraunPokuttaZink2019, author = {Braun, G{\´a}bor and Pokutta, Sebastian and Zink, Daniel}, title = {Lazifying Conditional Gradient Algorithms}, volume = {20}, journal = {Journal of Machine Learning Research (JMLR)}, number = {71}, arxiv = {http://arxiv.org/abs/1610.05120}, pages = {1 -- 42}, year = {2019}, language = {en} } @article{BraunPokutta2016, author = {Braun, G{\´a}bor and Pokutta, Sebastian}, title = {Common information and unique disjointness}, volume = {76}, journal = {Algorithmica}, number = {3}, pages = {597 -- 629}, year = {2016}, language = {en} } @article{GatzertPokuttaVogl2016, author = {Gatzert, Nadine and Pokutta, Sebastian and Vogl, Nikolai}, title = {Convergence of Capital and Insurance Markets: Pricing Aspects of Index-Linked Catastrophic Loss Instruments}, journal = {to appear in Journal of Risk and Insurance}, year = {2016}, language = {en} } @article{BaermannHeidtMartinetal.2016, 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}, volume = {13}, journal = {Computational Management Science}, number = {2}, pages = {151 -- 193}, year = {2016}, language = {en} } @article{RoyPokutta2017, author = {Roy, Aurko and Pokutta, Sebastian}, title = {Hierarchical Clustering via Spreading Metrics}, volume = {18}, journal = {Journal of Machine Learning Research (JMLR)}, arxiv = {http://arxiv.org/abs/1610.09269}, pages = {1 -- 35}, year = {2017}, language = {en} } @article{BodurDel PiaDeyetal.2017, 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}, journal = {to appear in Mathematical Programming A}, arxiv = {http://arxiv.org/abs/1606.08951}, year = {2017}, language = {en} } @article{BazziFioriniPokuttaetal.2017, 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}, journal = {to appear in Mathematics of Operations Research}, arxiv = {http://arxiv.org/abs/1503.00753}, year = {2017}, language = {en} } @article{BraunGuzmanPokutta2017, 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}, volume = {63}, journal = {IEEE Transactions of Information Theory}, number = {7}, arxiv = {http://arxiv.org/abs/1407.5144}, pages = {4709 -- 4724}, year = {2017}, language = {en} } @article{BraunJainLeeetal.2017, author = {Braun, G{\´a}bor and Jain, R. and Lee, T. and Pokutta, Sebastian}, title = {Information-theoretic approximations of the nonnegative rank}, volume = {26}, journal = {Computational Complexity}, number = {1}, pages = {147 -- 197}, year = {2017}, language = {en} } @article{ChristensenKhanPokuttaetal.2017, author = {Christensen, H. and Khan, A. and Pokutta, Sebastian and Tetali, P.}, title = {Multidimensional Bin Packing and Other Related Problems: A survey}, journal = {to appear in Computer Science Review}, year = {2017}, language = {en} } @article{MartinMuellerPapeetal.2017, 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}, volume = {85}, journal = {Mathematical Methods of Operations Research}, number = {2}, arxiv = {http://arxiv.org/abs/1404.6546}, pages = {155 -- 177}, year = {2017}, language = {en} } @inproceedings{BraunPokuttaZink2017, author = {Braun, G{\´a}bor and Pokutta, Sebastian and Zink, Daniel}, title = {Lazifying Conditional Gradient Algorithms}, booktitle = {Proceedings of the International Conference on Machine Learning (ICML)}, arxiv = {http://arxiv.org/abs/1610.05120}, year = {2017}, language = {en} } @inproceedings{ArumugamKadampotTahmasbietal.2017, 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}, booktitle = {Proceedings of IEEE DySPAN}, year = {2017}, language = {en} } @inproceedings{LanPokuttaZhouetal.2017, author = {Lan, G. and Pokutta, Sebastian and Zhou, Y. and Zink, Daniel}, title = {Conditional Accelerated Lazy Stochastic Gradient Descent}, booktitle = {Proceedings of the International Conference on Machine Learning (ICML)}, arxiv = {http://arxiv.org/abs/1703.05840}, year = {2017}, language = {en} } @inproceedings{InanlouganjiPedrielliFainekosetal.2018, author = {Inanlouganji, A. and Pedrielli, G. and Fainekos, G. and Pokutta, Sebastian}, title = {Continuous Simulation Optimization with Model Mismatch Using Gaussian Process Regression}, booktitle = {Proceedings of the 2018 Winter Simulation Conference}, year = {2018}, language = {en} } @inproceedings{PokuttaSinghTorrico2018, author = {Pokutta, Sebastian and Singh, M. and Torrico, A.}, title = {Efficient algorithms for robust submodular maximization under matroid constraints}, booktitle = {ICML Workshop Paper}, arxiv = {http://arxiv.org/abs/1807.09405}, year = {2018}, language = {en} } @inproceedings{BraunPokuttaTuetal.2019, author = {Braun, G{\´a}bor and Pokutta, Sebastian and Tu, Dan and Wright, Stephen}, title = {Blended Conditional Gradients: the unconditioning of conditional gradients}, booktitle = {Proceedings of ICML}, arxiv = {http://arxiv.org/abs/1805.07311}, year = {2019}, language = {en} } @inproceedings{Kerdreuxd’AspremontPokutta2019, author = {Kerdreux, T. and d'Aspremont, A. and Pokutta, Sebastian}, title = {Restarting Frank-Wolfe}, booktitle = {Proceedings of AISTATS}, arxiv = {http://arxiv.org/abs/1810.02429}, year = {2019}, language = {en} } @inproceedings{AnariHaghtalabNaoretal.2019, 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}, booktitle = {Proceedings of AISTATS}, arxiv = {http://arxiv.org/abs/1710.04740}, year = {2019}, language = {en} } @article{PokuttaSchmaltz2011, author = {Pokutta, Sebastian and Schmaltz, Christian}, title = {Managing liquidity: Optimal degree of centralization}, volume = {35}, journal = {Journal of Banking and Finance}, issn = {0378-4266}, doi = {DOI: 10.1016/j.jbankfin.2010.07.001}, pages = {627 -- 638}, year = {2011}, language = {en} } @article{PokuttaStauffer2011, author = {Pokutta, Sebastian and Stauffer, G.}, title = {Lower bounds for the Chv{\´a}tal-Gomory rank in the 0/1 cube}, volume = {39}, journal = {Operations Research Letters}, number = {3}, pages = {200-203}, year = {2011}, language = {en} } @article{BraunPokutta2012, author = {Braun, G{\´a}bor and Pokutta, Sebastian}, title = {Rigid abelian groups and the probabilistic method}, volume = {576}, journal = {Contemporary Mathematics}, arxiv = {http://arxiv.org/abs/1107.2325}, pages = {17 -- 30}, year = {2012}, language = {en} } @article{GoebelPokutta2012, author = {G{\"o}bel, R. and Pokutta, Sebastian}, title = {Absolutely rigid fields and Shelah's absolutely rigid trees}, volume = {576}, journal = {Contemporary Mathematics}, pages = {105 -- 128}, year = {2012}, language = {en} } @article{PokuttaSchmaltz2012, author = {Pokutta, Sebastian and Schmaltz, Christian}, title = {Optimal Planning under Basel III Regulations}, volume = {34}, journal = {Cass-Capco Institute Paper Series on Risk}, year = {2012}, language = {en} } @article{KrollPokutta2013, author = {Kroll, C. and Pokutta, Sebastian}, title = {Just a perfect day: developing a happiness optimised day schedule}, volume = {34}, journal = {Journal of Economic Psychology}, pages = {210 -- 217}, year = {2013}, language = {en} } @article{PokuttaVanVyve2013, author = {Pokutta, Sebastian and VanVyve, M.}, title = {A note on the extension complexity of the knapsack polytope}, volume = {41}, journal = {Operations Research Letters}, pages = {347 -- 350}, year = {2013}, language = {en} } @article{SchmaltzPokuttaHeidornetal.2014, author = {Schmaltz, Christian and Pokutta, Sebastian and Heidorn, Thomas and Andrae, Silvio}, title = {How to make regulators and shareholders happy under Basel III}, journal = {Journal of Banking and Finance}, pages = {311 -- 325}, year = {2014}, language = {en} } @article{BraunPokutta2014, 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}, volume = {42}, journal = {Operations Research Letters}, arxiv = {http://arxiv.org/abs/1207.4884}, pages = {307 -- 310}, year = {2014}, language = {en} } @article{DeyPokutta2014, author = {Dey, Santanu Sabush and Pokutta, Sebastian}, title = {Design and verify: a new scheme for generating cutting-planes}, volume = {145}, journal = {Mathematical Programming A}, pages = {199 -- 222}, year = {2014}, language = {en} } @article{PokuttaStruengmann2007, author = {Pokutta, Sebastian and Str{\"u}ngmann, L.}, title = {The Chase radical and reduced products}, volume = {211}, journal = {Journal of Pure and Applied Algebra}, pages = {532 -- 540}, year = {2007}, language = {en} } @article{DrosteGoebelPokutta2008, author = {Droste, M. and G{\"o}bel, R. and Pokutta, Sebastian}, title = {Absolute graphs with prescribed endomorphism monoid}, volume = {76}, journal = {Semigroup Forum}, pages = {256 -- 267}, year = {2008}, language = {en} } @article{GoebelPokutta2008, author = {G{\"o}bel, R. and Pokutta, Sebastian}, title = {Construction of dual modules using Martin's axiom}, volume = {320}, journal = {Journal of Algebra}, pages = {2388 -- 2404}, year = {2008}, language = {en} } @article{HeldtKreuzerPokuttaetal.2009, author = {Heldt, D. and Kreuzer, M. and Pokutta, Sebastian and Poulisse, H.}, title = {Approximate Computation of zero-dimensional polynomial ideals}, volume = {44}, journal = {Journal of Symbolic Computation}, pages = {1566 -- 1591}, year = {2009}, language = {en} } @article{PokuttaStauffer2009, author = {Pokutta, Sebastian and Stauffer, G.}, title = {France Telecom Workforce Scheduling Problem: a challenge}, journal = {RAIRO-Operations Research}, number = {43}, pages = {375 -- 386}, year = {2009}, language = {en} } @article{BraunPokutta2011, author = {Braun, G{\´a}bor and Pokutta, Sebastian}, title = {Random half-integral polytopes}, volume = {39}, journal = {Operations Research Letters}, number = {3}, pages = {204 -- 207}, year = {2011}, language = {en} } @article{HausHemmeckePokutta2011, author = {Haus, Utz-Uwe and Hemmecke, R. and Pokutta, Sebastian}, title = {Reconstructing biochemical cluster networks}, volume = {49}, journal = {Journal of Mathematical Chemistry}, number = {10}, arxiv = {http://arxiv.org/abs/0906.1342v2}, pages = {2441 -- 2456}, year = {2011}, language = {en} } @article{LetchfordPokuttaSchulz2011, author = {Letchford, A.N. and Pokutta, Sebastian and Schulz, A.S.}, title = {On the membership problem for the 0,1/2-closure}, volume = {39}, journal = {Operations Research Letters}, number = {5}, pages = {301 -- 304}, year = {2011}, language = {en} } @article{PokuttaSchulz2011, author = {Pokutta, Sebastian and Schulz, A.S.}, title = {Integer-empty polytopes in the 0/1-cube with maximal Gomory-Chv{\´a}tal rank}, volume = {39}, journal = {Operations Research Letters}, number = {6}, pages = {457 -- 460}, year = {2011}, language = {en} } @article{DrewesPokutta2014, author = {Drewes, S. and Pokutta, Sebastian}, title = {Computing discrete expected utility maximizing portfolios}, volume = {23}, journal = {Journal of Investing}, number = {4}, pages = {121 -- 132}, year = {2014}, language = {en} } @article{DrewesPokutta2014, author = {Drewes, S. and Pokutta, Sebastian}, title = {Symmetry-exploiting cuts for a class of mixed-0/1 second order cone programs}, volume = {13}, journal = {Discrete Optimization}, pages = {23 -- 35}, year = {2014}, language = {en} } @article{MartinMuellerPokutta2014, author = {Martin, Alexander and M{\"u}ller, J. and Pokutta, Sebastian}, title = {Strict linear prices in non-convex European day-ahead electricity markets}, volume = {29}, journal = {Optimization Methods and Software}, number = {1}, pages = {189 -- 221}, year = {2014}, language = {en} }