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