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