@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} } @article{BrietDadushPokutta2015, author = {Bri{\"e}t, Jop and Dadush, Daniel and Pokutta, Sebastian}, title = {On the existence of 0/1 polytopes with high semidefinite extension complexity}, volume = {153}, journal = {Mathematical Programming B}, number = {1}, arxiv = {http://arxiv.org/abs/1305.3268}, pages = {179 -- 199}, year = {2015}, language = {en} } @article{BraunFioriniPokuttaetal.2015, author = {Braun, G{\´a}bor and Fiorini, Samuel and Pokutta, Sebastian and Steurer, D.}, title = {Approximation Limits of Linear Programs (Beyond Hierarchies)}, volume = {40}, journal = {Mathematics of Operations Research}, number = {3}, arxiv = {http://arxiv.org/abs/1204.0957}, pages = {179 -- 199}, year = {2015}, language = {en} } @article{BraunPokutta2015, author = {Braun, G{\´a}bor and Pokutta, Sebastian}, title = {The matching polytope does not admit fully-polynomial size relaxation schemes}, volume = {61}, journal = {IEEE Transactions on Information Theory}, number = {10}, arxiv = {http://arxiv.org/abs/1403.6710}, pages = {1 -- 11}, year = {2015}, language = {en} } @article{BraunPokuttaXie2015, author = {Braun, G{\´a}bor and Pokutta, Sebastian and Xie, Y.}, title = {Info-Greedy Sequential Adaptive Compressed Sensing}, volume = {9}, journal = {IEEE Journal of Selected Topics in Signal Processing}, number = {4}, arxiv = {http://arxiv.org/abs/1407.0731}, pages = {601 -- 611}, year = {2015}, language = {en} } @article{FioriniMassarPokuttaetal.2015, 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}, volume = {62}, journal = {Journal of the ACM}, number = {2}, arxiv = {http://arxiv.org/abs/1111.0837}, pages = {1 -- 17}, year = {2015}, language = {en} } @article{BraunFioriniPokutta2016, author = {Braun, G{\´a}bor and Fiorini, Samuel and Pokutta, Sebastian}, title = {Average case polyhedral complexity of the maximum stable set problem}, volume = {160}, journal = {Mathematical Programming A}, number = {1}, arxiv = {http://arxiv.org/abs/1311.4001}, pages = {407 -- 431}, year = {2016}, language = {en} } @article{BraunPokutta2016, author = {Braun, G{\´a}bor and Pokutta, Sebastian}, title = {A polyhedral characterization of Border Bases}, volume = {30}, journal = {SIAM Journal on Discrete Mathematics}, number = {1}, arxiv = {http://arxiv.org/abs/0912.1502}, pages = {239 -- 265}, year = {2016}, language = {en} } @inproceedings{PokuttaSchmaltz2011, author = {Pokutta, Sebastian and Schmaltz, Christian}, title = {Optimal Planning under Basel III Regulations}, booktitle = {Proceedings of 24th Australasian Finance and Banking Conference}, year = {2011}, language = {en} } @inproceedings{BraunFioriniPokuttaetal.2012, author = {Braun, G{\´a}bor and Fiorini, Samuel and Pokutta, Sebastian and Steurer, D.}, title = {Approximation Limits of Linear Programs (Beyond Hierarchies)}, booktitle = {Proceedings of FOCS}, arxiv = {http://arxiv.org/abs/1204.0957}, year = {2012}, language = {en} } @inproceedings{BraunPokutta2012, author = {Braun, G{\´a}bor and Pokutta, Sebastian}, title = {An algebraic view on symmetric extended formulations}, volume = {7422}, booktitle = {Proceedings of ISCO, Lecture Notes in Computer Science}, number = {141--152}, arxiv = {http://arxiv.org/abs/1206.6318}, year = {2012}, language = {en} } @inproceedings{FioriniMassarPokuttaetal.2012, 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}, booktitle = {Proceedings of STOC}, arxiv = {http://arxiv.org/abs/1111.0837}, year = {2012}, language = {en} } @inproceedings{SchmaltzPokuttaHeidornetal.2013, author = {Schmaltz, Christian and Pokutta, Sebastian and Heidorn, Thomas and Andrae, Silvio}, title = {How to make regulators and shareholders happy under Basel III}, booktitle = {Proceedings of the 26th Australasian Finance and Banking Conference}, year = {2013}, language = {en} } @inproceedings{BrietDadushPokutta2013, author = {Bri{\"e}t, Jop and Dadush, Daniel and Pokutta, Sebastian}, title = {On the existence of 0/1 polytopes with high semidefinite extension complexity}, booktitle = {Proceedings of ESA}, arxiv = {http://arxiv.org/abs/1305.3268}, year = {2013}, language = {en} } @inproceedings{BraunPokutta2013, author = {Braun, Gabor and Pokutta, Sebastian}, title = {Foundations of Computer Science (FOCS), 2013 IEEE 54th Annual Symposium}, booktitle = {Foundations of Computer Science (FOCS), 2013 IEEE 54th Annual Symposium}, pages = {688 -- 697}, year = {2013}, language = {en} } @inproceedings{BraunFioriniPokutta2014, author = {Braun, G{\´a}bor and Fiorini, Samuel and Pokutta, Sebastian}, title = {Average case polyhedral complexity of the maximum stable set problem}, booktitle = {Proceedings of RANDOM}, arxiv = {http://arxiv.org/abs/1311.4001}, year = {2014}, language = {en} } @inproceedings{BraunPokuttaXie2014, author = {Braun, G{\´a}bor and Pokutta, Sebastian and Xie, Y.}, title = {Info-Greedy Sequential Adaptive Compressed Sensing}, booktitle = {Proceedings of 52nd Annual Allerton Conference on Communication, Control, and Computing}, arxiv = {http://arxiv.org/abs/1407.0731}, year = {2014}, language = {en} } @inproceedings{BazziFioriniPokuttaetal.2015, 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}, booktitle = {Proceedings of FOCS}, arxiv = {http://arxiv.org/abs/1503.00753}, year = {2015}, language = {en} } @inproceedings{PokuttaSchmaltz2009, author = {Pokutta, Sebastian and Schmaltz, Christian}, title = {Optimal degree of centralization of liquidity management}, booktitle = {Proceedings of 22nd Australasian Finance and Banking Conference}, year = {2009}, language = {en} } @inproceedings{BraunPokutta2010, author = {Braun, G{\´a}bor and Pokutta, Sebastian}, title = {Rank of random half-integral polytopes}, volume = {36}, booktitle = {Electronic Notes in Discrete Mathematics}, pages = {415 -- 422}, year = {2010}, language = {en} } @inproceedings{DrewesPokutta2010, author = {Drewes, S. and Pokutta, Sebastian}, title = {Cutting-planes for weakly-coupled 0/1 second order cone programs}, volume = {36}, booktitle = {Electronic Notes in Discrete Mathematics}, pages = {735 -- 742}, year = {2010}, language = {en} } @inproceedings{DrewesPokutta2010, author = {Drewes, S. and Pokutta, Sebastian}, title = {Geometric mean maximization in the presence of discrete decisions}, booktitle = {Proceedings of 23rd Australasian Finance and Banking Conference}, year = {2010}, language = {en} } @inproceedings{MartinMuellerPokutta2010, author = {Martin, Alexander and M{\"u}ller, J. and Pokutta, Sebastian}, title = {On clearing coupled day-ahead electricity markets}, booktitle = {Proceedings of 23rd Australasian Finance and Banking Conference}, year = {2010}, language = {en} } @inproceedings{PokuttaSchulz2010, author = {Pokutta, Sebastian and Schulz, A.S.}, title = {On the rank of generic cutting-plane proof systems}, volume = {6080}, booktitle = {Proceedings of IPCO, Lecture Notes in Computer Science}, pages = {450 -- 463}, year = {2010}, language = {en} } @inproceedings{DeyPokutta2011, author = {Dey, Santanu Sabush and Pokutta, Sebastian}, title = {Design and verify: a new scheme for generating cutting-planes}, volume = {6655}, booktitle = {Proceedings of IPCO, Lecture Notes in Computer Science}, pages = {143 -- 155}, year = {2011}, language = {en} } @inproceedings{HelmkeGluchshenkoMartinetal.2011, author = {Helmke, H. and Gluchshenko, O. and Martin, Alexander and Peter, A. and Pokutta, Sebastian and Siebert, U.}, title = {Optimal Mixed-Mode Runway Scheduling}, booktitle = {Proceedings of DACS}, year = {2011}, language = {en} } @inproceedings{PokuttaSchmaltz2011, author = {Pokutta, Sebastian and Schmaltz, Christian}, title = {A network model for bank lending capacity}, booktitle = {Proceedings of Systemic Risk, Basel III, Financial Stability and Regulation}, year = {2011}, language = {en} } @inproceedings{BraunPokutta2015, author = {Braun, G{\´a}bor and Pokutta, Sebastian}, title = {The matching polytope does not admit fully-polynomial size relaxation schemes}, booktitle = {Proceeedings of SODA}, arxiv = {http://arxiv.org/abs/1403.6710}, year = {2015}, language = {en} } @inproceedings{BraunPokuttaZink2015, author = {Braun, G{\´a}bor and Pokutta, Sebastian and Zink, Daniel}, title = {Inapproximability of combinatorial problems via small LPs and SDPs}, booktitle = {Proceeedings of STOC}, arxiv = {http://arxiv.org/abs/1410.8816}, year = {2015}, language = {en} } @inproceedings{Pokutta2015, author = {Pokutta, Sebastian}, title = {Information Theory and Polyhedral Combinatorics}, booktitle = {Proceedings of 53rd Annual Allerton Conference on Communication, Control, and Computing}, year = {2015}, language = {en} } @inproceedings{SongXiePokutta2015, author = {Song, R. and Xie, Y. and Pokutta, Sebastian}, title = {Sequential Sensing with Model Mismatch}, booktitle = {Proceedings of ISIT}, year = {2015}, language = {en} } @inproceedings{XieLiPokutta2015, author = {Xie, Y. and Li, Q. and Pokutta, Sebastian}, title = {Supervised Online Subspace Tracking}, booktitle = {Proceedings of Asilomar Conference on Signals, Systems, and Computers}, year = {2015}, language = {en} } @inproceedings{RoyPokutta2016, author = {Roy, Aurko and Pokutta, Sebastian}, title = {Hierarchical Clustering via Spreading Metrics}, booktitle = {Proceedings of NIPS}, arxiv = {http://arxiv.org/abs/1610.09269}, year = {2016}, language = {en} } @inproceedings{BraunRoyPokutta2016, author = {Braun, G{\´a}bor and Roy, Aurko and Pokutta, Sebastian}, title = {Stronger Reductions for Extended Formulations}, booktitle = {Proceedings of IPCO}, arxiv = {http://arxiv.org/abs/1512.04932}, year = {2016}, language = {en} } @inproceedings{BraunBrownCohenHuqetal.2016, 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}, booktitle = {Proceddings of SODA 2016}, arxiv = {http://arxiv.org/abs/1504.00703}, year = {2016}, language = {en} } @inproceedings{RoyXuPokutta2017, author = {Roy, Aurko and Xu, Huan and Pokutta, Sebastian}, title = {Reinforcement Learning under Model Mismatch}, booktitle = {Proceedings of NIPS}, arxiv = {http://arxiv.org/abs/1706.04711}, year = {2017}, language = {en} } @inproceedings{BaermannPokuttaSchneider2017, author = {B{\"a}rmann, Andreas and Pokutta, Sebastian and Schneider, Oskar}, title = {Emulating the Expert: Inverse Optimization through Online Learning}, booktitle = {Proceedings of the International Conference on Machine Learning (ICML)}, arxiv = {http://arxiv.org/abs/1810.12997}, year = {2017}, language = {en} } @inproceedings{SofranacGleixnerPokutta2021, author = {Sofranac, Boro and Gleixner, Ambros and Pokutta, Sebastian}, title = {An Algorithm-Independent Measure of Progress for Linear Constraint Propagation}, 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}, year = {2021}, 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} } @article{CardereraPokutta2020, author = {Carderera, Alejandro and Pokutta, Sebastian}, title = {Second-order Conditional Gradient Sliding}, year = {2020}, 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{MathieuCardereraPokutta2022, 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}, volume = {34}, journal = {INFORMS Journal on Computing}, number = {5}, doi = {10.1287/ijoc.2022.1191}, pages = {2383 -- 2865}, year = {2022}, 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} } @article{AbbasAmbainisAugustinoetal.2024, author = {Abbas, Amira and Ambainis, Andris and Augustino, Brandon and B{\"a}rtschi, Andreas and Buhrman, Harry and Coffrin, Carleton and Cortiana, Giorgio and Dunjko, Vedran and Egger, Daniel J. and Elmegreen, Bruce G. and Franco, Nicola and Fratini, Filippo and Fuller, Bryce and Gacon, Julien and Gonciulea, Constantin and Gribling, Sander and Gupta, Swati and Hadfield, Stuart and Heese, Raoul and Kircher, Gerhard and Kleinert, Thomas and Koch, Thorsten and Korpas, Georgios and Lenk, Steve and Marecek, Jakub and Markov, Vanio and Mazzola, Guglielmo and Mensa, Stefano and Mohseni, Naeimeh and Nannicini, Giacomo and O'Meara, Corey and Tapia, Elena Pe{\~n}a and Pokutta, Sebastian and Proissl, Manuel and Rebentrost, Patrick and Sahin, Emre and Symons, Benjamin C. B. and Tornow, Sabine and Valls, V{\´i}ctor and Woerner, Stefan and Wolf-Bauwens, Mira L. and Yard, Jon and Yarkoni, Sheir and Zechiel, Dirk and Zhuk, Sergiy and Zoufal, Christa}, title = {Challenges and opportunities in quantum optimization}, volume = {6}, journal = {Nature Reviews Physics}, publisher = {Springer Science and Business Media LLC}, issn = {2522-5820}, arxiv = {http://arxiv.org/abs/2312.02279}, doi = {10.1038/s42254-024-00770-9}, pages = {718 -- 735}, year = {2024}, language = {en} } @inproceedings{SofranacGleixnerPokutta2020, author = {Sofranac, Boro and Gleixner, Ambros and Pokutta, Sebastian}, title = {Accelerating Domain Propagation: an Efficient GPU-Parallel Algorithm over Sparse Matrices}, booktitle = {2020 IEEE/ACM 10th Workshop on Irregular Applications: Architectures and Algorithms (IA3)}, arxiv = {http://arxiv.org/abs/2009.07785}, doi = {10.1109/IA351965.2020.00007}, pages = {1 -- 11}, year = {2020}, 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} } @article{ŠofranacGleixnerPokutta2022, author = {Šofranac, Boro and Gleixner, Ambros and Pokutta, Sebastian}, title = {Accelerating domain propagation: An efficient GPU-parallel algorithm over sparse matrices}, volume = {109}, journal = {Parallel Computing}, doi = {10.1016/j.parco.2021.102874}, pages = {102874}, year = {2022}, abstract = {• Currently, domain propagation in state-of-the-art MIP solvers is single thread only. • The paper presents a novel, efficient GPU algorithm to perform domain propagation. • Challenges are dynamic algorithmic behavior, dependency structures, sparsity patterns. • The algorithm is capable of running entirely on the GPU with no CPU involvement. • We achieve speed-ups of around 10x to 20x, up to 180x on favorably-large instances.}, language = {en} } @inproceedings{DiakonikolasCardereraPokutta2019, author = {Diakonikolas, Jelena and Carderera, Alejandro and Pokutta, Sebastian}, title = {Breaking the Curse of Dimensionality (Locally) to Accelerate Conditional Gradients}, booktitle = {OPTML Workshop Paper}, arxiv = {http://arxiv.org/abs/1906.07867}, year = {2019}, language = {en} } @inproceedings{CombettesPokutta2019, author = {Combettes, Cyrille W. and Pokutta, Sebastian}, title = {Blended Matching Pursuit}, booktitle = {Proceedings of NeurIPS}, arxiv = {http://arxiv.org/abs/1904.12335}, year = {2019}, language = {en} } @inproceedings{PokuttaSinghTorrico2019, author = {Pokutta, Sebastian and Singh, M. and Torrico, A.}, title = {On the Unreasonable Effectiveness of the Greedy Algorithm: Greedy Adapts to Sharpness}, booktitle = {OPTML Workshop Paper}, year = {2019}, language = {en} } @inproceedings{CriadoMartinezRubioPokutta2022, author = {Criado, Francisco and Mart{\´i}nez-Rubio, David and Pokutta, Sebastian}, title = {Fast Algorithms for Packing Proportional Fairness and its Dual}, volume = {36}, booktitle = {Proceedings of the Conference on Neural Information Processing Systems}, year = {2022}, abstract = {The proportional fair resource allocation problem is a major problem studied in flow control of networks, operations research, and economic theory, where it has found numerous applications. This problem, defined as the constrained maximization of sum_i log x_i, is known as the packing proportional fairness problem when the feasible set is defined by positive linear constraints and x ∈ R≥0. In this work, we present a distributed accelerated first-order method for this problem which improves upon previous approaches. We also design an algorithm for the optimization of its dual problem. Both algorithms are width-independent.}, language = {en} } @inproceedings{CardereraPokuttaMathieu2021, author = {Carderera, Alejandro and Pokutta, Sebastian and Mathieu, Besan{\c{c}}on}, title = {Simple steps are all you need: Frank-Wolfe and generalized self-concordant functions}, booktitle = {Thirty-fifth Conference on Neural Information Processing Systems, NeurIPS 2021}, year = {2021}, abstract = {Generalized self-concordance is a key property present in the objective function of many important learning problems. We establish the convergence rate of a simple Frank-Wolfe variant that uses the open-loop step size strategy 𝛾𝑡 = 2/(𝑡 + 2), obtaining a O (1/𝑡) convergence rate for this class of functions in terms of primal gap and Frank-Wolfe gap, where 𝑡 is the iteration count. This avoids the use of second-order information or the need to estimate local smoothness parameters of previous work. We also show improved convergence rates for various common cases, e.g., when the feasible region under consideration is uniformly convex or polyhedral.}, language = {en} } @article{Kerdreuxd'AspremontPokutta2021, author = {Kerdreux, Thomas and d'Aspremont, Alexandre and Pokutta, Sebastian}, title = {Local and Global Uniform Convexity Conditions}, year = {2021}, abstract = {We review various characterizations of uniform convexity and smoothness on norm balls in finite-dimensional spaces and connect results stemming from the geometry of Banach spaces with scaling inequalities used in analysing the convergence of optimization methods. In particular, we establish local versions of these conditions to provide sharper insights on a recent body of complexity results in learning theory, online learning, or offline optimization, which rely on the strong convexity of the feasible set. While they have a significant impact on complexity, these strong convexity or uniform convexity properties of feasible sets are not exploited as thoroughly as their functional counterparts, and this work is an effort to correct this imbalance. We conclude with some practical examples in optimization and machine learning where leveraging these conditions and localized assumptions lead to new complexity results.}, language = {en} } @inproceedings{ZimmerSpiegelPokutta2023, author = {Zimmer, Max and Spiegel, Christoph and Pokutta, Sebastian}, title = {How I Learned to Stop Worrying and Love Retraining}, booktitle = {Proceedings of International Conference on Learning Representations}, year = {2023}, language = {en} } @inproceedings{WirthKerdreuxPokutta2023, author = {Wirth, Elias and Kerdreux, Thomas and Pokutta, Sebastian}, title = {Acceleration of Frank-Wolfe Algorithms with Open Loop Step-sizes}, booktitle = {Proceedings of International Conference on Artificial Intelligence and Statistics}, year = {2023}, language = {en} } @inproceedings{WirthKeraPokutta2023, author = {Wirth, Elias and Kera, and Pokutta, Sebastian}, title = {Approximate Vanishing Ideal Computations at Scale}, booktitle = {Proceedings of International Conference on Learning Representations}, year = {2023}, language = {en} } @article{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{BienstockMunozPokutta2023, author = {Bienstock, Daniel and Mu{\~n}oz, Gonzalo and Pokutta, Sebastian}, title = {Principled Deep Neural Network Training Through Linear Programming}, volume = {49}, journal = {Discrete Optimization}, doi = {10.1016/j.disopt.2023.100795}, year = {2023}, abstract = {Deep learning has received much attention lately due to the impressive empirical performance achieved by training algorithms. Consequently, a need for a better theoretical understanding of these problems has become more evident and multiple works in recent years have focused on this task. In this work, using a unified framework, we show that there exists a polyhedron that simultaneously encodes, in its facial structure, all possible deep neural network training problems that can arise from a given architecture, activation functions, loss function, and sample size. Notably, the size of the polyhedral representation depends only linearly on the sample size, and a better dependency on several other network parameters is unlikely. Using this general result, we compute the size of the polyhedral encoding for commonly used neural network architectures. Our results provide a new perspective on training problems through the lens of polyhedral theory and reveal strong structure arising from these problems.}, language = {en} }