TY - JOUR A1 - Designolle, Sébastien A1 - Besançon, Mathieu A1 - Iommazzo, Gabriele A1 - Knebel, Sebastian A1 - Gelß, Patrick A1 - Pokutta, Sebastian T1 - Improved Local Models and New Bell Inequalities Via Frank-Wolfe Algorithms JF - Physical Review Research N2 - 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. Y1 - 2023 U6 - https://doi.org/10.1103/PhysRevResearch.5.043059 VL - 5 SP - 043059 ER - TY - JOUR A1 - Kevin-Martin, Aigner A1 - Bärmann, Andreas A1 - Braun, Kristin A1 - Liers, Frauke A1 - Pokutta, Sebastian A1 - Schneider, Oskar A1 - Sharma, Kartikey A1 - Tschuppik, Sebastian T1 - Data-driven Distributionally Robust Optimization over Time JF - INFORMS Journal on Optimization N2 - 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. Y1 - 2023 U6 - https://doi.org/10.1287/ijoo.2023.0091 VL - 5 IS - 4 SP - 376 EP - 394 ER - TY - JOUR A1 - Gelß, Patrick A1 - Klus, Stefan A1 - Knebel, Sebastian A1 - Shakibaei, Zarin A1 - Pokutta, Sebastian T1 - Low-Rank Tensor Decompositions of Quantum Circuits JF - Journal of Computational Physics N2 - 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. Y1 - 2022 ER - TY - JOUR A1 - Designolle, Sébastien A1 - Iommazzo, Gabriele A1 - Besançon, Mathieu A1 - Knebel, Sebastian A1 - Gelß, Patrick A1 - Pokutta, Sebastian T1 - Improved local models and new Bell inequalities via Frank-Wolfe algorithms JF - Physical Review Research N2 - 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. Y1 - 2023 U6 - https://doi.org/10.1103/PhysRevResearch.5.043059 VL - 5 SP - 043059 ER - TY - JOUR A1 - Knueven, B. A1 - Ostrowski, J. A1 - Pokutta, Sebastian T1 - Detecting Almost Symmetries in Graphs JF - to appear in Mathematical Programming C Y1 - 2017 UR - http://www.optimization-online.org/DB_HTML/2015/09/5117.html N1 - URL of the PDF: http://link.springer.com/article/10.1007/s12532-017-0124-3 ER - TY - JOUR A1 - Braun, Gábor A1 - Brown-Cohen, Jonah A1 - Huq, Arefin A1 - Pokutta, Sebastian A1 - Raghavendra, Prasad A1 - Weitz, Benjamin A1 - Zink, Daniel T1 - The matching problem has no small symmetric SDP JF - Mathematical Programming A Y1 - 2017 N1 - Additional Note: DOI 10.1007/s10107-016-1098-z N1 - URL of the PDF: http://dx.doi.org/10.1007/s10107-016-1098-z VL - 165 IS - 2 SP - 643 EP - 662 ER - TY - JOUR A1 - Le Bodic, P. A1 - Pfetsch, Marc A1 - Pavelka, J. A1 - Pokutta, Sebastian T1 - Solving MIPs via Scaling-based Augmentation JF - Discrete Optimization Y1 - 2018 N1 - Additional Note: doi: 10.1016/j.disopt.2017.08.004 N1 - URL of the PDF: http://dx.doi.org/10.1016/j.disopt.2017.08.004 VL - 27 SP - 1 EP - 25 ER - TY - JOUR A1 - Braun, Gábor A1 - Roy, Aurko A1 - Pokutta, Sebastian T1 - Stronger Reductions for Extended Formulations JF - to appear in Mathematical Programming B Y1 - 2018 N1 - Additional Note: available at \url{http://arxiv.org/abs/1512.04932} ER - TY - JOUR A1 - Song, R. A1 - Xie, Y. A1 - Pokutta, Sebastian T1 - On the effect of model mismatch for sequential Info-Greedy Sensing JF - EURASIP Journal on Advances in Signal Processing Y1 - 2018 N1 - URL of the PDF: https://asp-eurasipjournals.springeropen.com/articles/10.1186/s13634-018-0551-y ER - TY - JOUR A1 - Braun, Gábor A1 - Pokutta, Sebastian A1 - Zink, Daniel T1 - Affine Reductions for LPs and SDPs JF - Mathematical Programming A Y1 - 2019 N1 - URL of the PDF: http://rdcu.be/EPf9 VL - 173 IS - 1 SP - 281 EP - 312 ER - TY - JOUR A1 - Braun, Gábor A1 - Pokutta, Sebastian A1 - Zink, Daniel T1 - Lazifying Conditional Gradient Algorithms JF - Journal of Machine Learning Research (JMLR) Y1 - 2019 N1 - URL of the PDF: http://jmlr.org/papers/v20/18-114.html N1 - URL of the Slides: https://app.box.com/s/zsp0hixjz2ha23u1vuyosijjkjdh8kj7 VL - 20 IS - 71 SP - 1 EP - 42 ER - TY - JOUR A1 - Braun, Gábor A1 - Pokutta, Sebastian T1 - Common information and unique disjointness JF - Algorithmica Y1 - 2016 UR - http://eccc.hpi-web.de/report/2013/056 N1 - URL of the PDF: https://rdcu.be/6b9u VL - 76 IS - 3 SP - 597 EP - 629 ER - TY - JOUR A1 - Gatzert, Nadine A1 - Pokutta, Sebastian A1 - Vogl, Nikolai T1 - Convergence of Capital and Insurance Markets: Pricing Aspects of Index-Linked Catastrophic Loss Instruments JF - to appear in Journal of Risk and Insurance Y1 - 2016 UR - http://papers.ssrn.com/sol3/papers.cfm?abstract_id=2320370 ER - TY - JOUR A1 - Bärmann, Andreas A1 - Heidt, Andreas A1 - Martin, Alex A1 - er, A1 - Pokutta, Sebastian A1 - Thurner, Christoph T1 - Polyhedral Approximation of Ellipsoidal Uncertainty Sets via Extended Formulations - a computational case study JF - Computational Management Science Y1 - 2016 UR - http://www.optimization-online.org/DB_HTML/2014/02/4245.html N1 - Additional Note: http://link.springer.com/article/10.1007/s10287-015-0243-0 DOI:10.1007/s10287-015-0243-0 N1 - URL of the PDF: http://link.springer.com/article/10.1007/s10287-015-0243-0 VL - 13 IS - 2 SP - 151 EP - 193 ER - TY - JOUR A1 - Roy, Aurko A1 - Pokutta, Sebastian T1 - Hierarchical Clustering via Spreading Metrics JF - Journal of Machine Learning Research (JMLR) Y1 - 2017 N1 - Additional Note: http://https://papers.nips.cc/paper/by-source-2016-1199 N1 - URL of the PDF: http://jmlr.org/papers/v18/17-081.html VL - 18 SP - 1 EP - 35 ER - TY - JOUR A1 - Bodur, Merve A1 - Del Pia, Alberto A1 - Dey, Santanu Sabush A1 - Molinaro, Marco A1 - Pokutta, Sebastian T1 - Aggregation-based cutting-planes for packing and covering Integer Programs JF - to appear in Mathematical Programming A Y1 - 2017 N1 - Additional Note: doi:10.1007/s10107-017-1192-x N1 - URL of the PDF: http://dx.doi.org/10.1007/s10107-017-1192-x ER - TY - JOUR A1 - Bazzi, Abbas A1 - Fiorini, Samuel A1 - Pokutta, Sebastian A1 - Svensson, Ola T1 - Small linear programs cannot approximate Vertex Cover within a factor of 2 - epsilon JF - to appear in Mathematics of Operations Research Y1 - 2017 N1 - URL of the Slides: https://app.box.com/s/00aqupo722bbpmdcyzwt8xmfqzyu14iy ER - TY - JOUR A1 - Braun, Gábor A1 - Guzmán, C. A1 - Pokutta, Sebastian T1 - Unifying Lower Bounds on the Oracle Complexity of Nonsmooth Convex Optimization JF - IEEE Transactions of Information Theory Y1 - 2017 N1 - Additional Note: doi:10.1109/TIT.2017.2701343 http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=7919238 N1 - URL of the PDF: http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=7919238 VL - 63 IS - 7 SP - 4709 EP - 4724 ER - TY - JOUR A1 - Braun, Gábor A1 - Jain, R. A1 - Lee, T. A1 - Pokutta, Sebastian T1 - Information-theoretic approximations of the nonnegative rank JF - Computational Complexity Y1 - 2017 UR - http://eccc.hpi-web.de/report/2013/158 VL - 26 IS - 1 SP - 147 EP - 197 ER - TY - JOUR A1 - Christensen, H. A1 - Khan, A. A1 - Pokutta, Sebastian A1 - Tetali, P. T1 - Multidimensional Bin Packing and Other Related Problems: A survey JF - to appear in Computer Science Review Y1 - 2017 N1 - Additional Note: http://www.sciencedirect.com/science/article/pii/S1574013716301356 http://www.sciencedirect.com/science/article/pii/S1574013716301356 N1 - URL of the PDF: http://www.sciencedirect.com/science/article/pii/S1574013716301356 ER -