@article{PokuttaStruengmann, author = {Pokutta, Sebastian and Str{\"u}ngmann, L.}, title = {The Chase radical and reduced products}, series = {Journal of Pure and Applied Algebra}, volume = {211}, journal = {Journal of Pure and Applied Algebra}, pages = {532 -- 540}, language = {en} } @article{DrosteGoebelPokutta, author = {Droste, M. and G{\"o}bel, R. and Pokutta, Sebastian}, title = {Absolute graphs with prescribed endomorphism monoid}, series = {Semigroup Forum}, volume = {76}, journal = {Semigroup Forum}, pages = {256 -- 267}, language = {en} } @article{GoebelPokutta, author = {G{\"o}bel, R. and Pokutta, Sebastian}, title = {Construction of dual modules using Martin's axiom}, series = {Journal of Algebra}, volume = {320}, journal = {Journal of Algebra}, pages = {2388 -- 2404}, language = {en} } @article{HeldtKreuzerPokuttaetal., author = {Heldt, D. and Kreuzer, M. and Pokutta, Sebastian and Poulisse, H.}, title = {Approximate Computation of zero-dimensional polynomial ideals}, series = {Journal of Symbolic Computation}, volume = {44}, journal = {Journal of Symbolic Computation}, pages = {1566 -- 1591}, language = {en} } @article{PokuttaStauffer, author = {Pokutta, Sebastian and Stauffer, G.}, title = {France Telecom Workforce Scheduling Problem: a challenge}, series = {RAIRO-Operations Research}, journal = {RAIRO-Operations Research}, number = {43}, pages = {375 -- 386}, language = {en} } @article{BraunPokutta, author = {Braun, G{\´a}bor and Pokutta, Sebastian}, title = {Random half-integral polytopes}, series = {Operations Research Letters}, volume = {39}, journal = {Operations Research Letters}, number = {3}, pages = {204 -- 207}, language = {en} } @article{HausHemmeckePokutta, author = {Haus, Utz-Uwe and Hemmecke, R. and Pokutta, Sebastian}, title = {Reconstructing biochemical cluster networks}, series = {Journal of Mathematical Chemistry}, volume = {49}, journal = {Journal of Mathematical Chemistry}, number = {10}, pages = {2441 -- 2456}, language = {en} } @article{LetchfordPokuttaSchulz, author = {Letchford, A.N. and Pokutta, Sebastian and Schulz, A.S.}, title = {On the membership problem for the 0,1/2-closure}, series = {Operations Research Letters}, volume = {39}, journal = {Operations Research Letters}, number = {5}, pages = {301 -- 304}, language = {en} } @article{PokuttaSchulz, author = {Pokutta, Sebastian and Schulz, A.S.}, title = {Integer-empty polytopes in the 0/1-cube with maximal Gomory-Chv{\´a}tal rank}, series = {Operations Research Letters}, volume = {39}, journal = {Operations Research Letters}, number = {6}, pages = {457 -- 460}, language = {en} } @article{PokuttaSchmaltz, author = {Pokutta, Sebastian and Schmaltz, Christian}, title = {Managing liquidity: Optimal degree of centralization}, series = {Journal of Banking and Finance}, volume = {35}, journal = {Journal of Banking and Finance}, issn = {0378-4266}, doi = {DOI: 10.1016/j.jbankfin.2010.07.001}, pages = {627 -- 638}, language = {en} } @article{PokuttaStauffer, author = {Pokutta, Sebastian and Stauffer, G.}, title = {Lower bounds for the Chv{\´a}tal-Gomory rank in the 0/1 cube}, series = {Operations Research Letters}, volume = {39}, journal = {Operations Research Letters}, number = {3}, pages = {200-203}, language = {en} } @inproceedings{BraunPokutta, author = {Braun, G{\´a}bor and Pokutta, Sebastian}, title = {Rank of random half-integral polytopes}, series = {Electronic Notes in Discrete Mathematics}, volume = {36}, booktitle = {Electronic Notes in Discrete Mathematics}, pages = {415 -- 422}, language = {en} } @inproceedings{DrewesPokutta, author = {Drewes, S. and Pokutta, Sebastian}, title = {Cutting-planes for weakly-coupled 0/1 second order cone programs}, series = {Electronic Notes in Discrete Mathematics}, volume = {36}, booktitle = {Electronic Notes in Discrete Mathematics}, pages = {735 -- 742}, language = {en} } @inproceedings{DrewesPokutta, author = {Drewes, S. and Pokutta, Sebastian}, title = {Geometric mean maximization in the presence of discrete decisions}, series = {Proceedings of 23rd Australasian Finance and Banking Conference}, booktitle = {Proceedings of 23rd Australasian Finance and Banking Conference}, language = {en} } @inproceedings{MartinMuellerPokutta, author = {Martin, Alexander and M{\"u}ller, J. and Pokutta, Sebastian}, title = {On clearing coupled day-ahead electricity markets}, series = {Proceedings of 23rd Australasian Finance and Banking Conference}, booktitle = {Proceedings of 23rd Australasian Finance and Banking Conference}, language = {en} } @inproceedings{PokuttaSchulz, author = {Pokutta, Sebastian and Schulz, A.S.}, title = {On the rank of generic cutting-plane proof systems}, series = {Proceedings of IPCO, Lecture Notes in Computer Science}, volume = {6080}, booktitle = {Proceedings of IPCO, Lecture Notes in Computer Science}, pages = {450 -- 463}, language = {en} } @inproceedings{HelmkeGluchshenkoMartinetal., author = {Helmke, H. and Gluchshenko, O. and Martin, Alexander and Peter, A. and Pokutta, Sebastian and Siebert, U.}, title = {Optimal Mixed-Mode Runway Scheduling}, series = {Proceedings of DACS}, booktitle = {Proceedings of DACS}, language = {en} } @inproceedings{PokuttaSchmaltz, author = {Pokutta, Sebastian and Schmaltz, Christian}, title = {A network model for bank lending capacity}, series = {Proceedings of Systemic Risk, Basel III, Financial Stability and Regulation}, booktitle = {Proceedings of Systemic Risk, Basel III, Financial Stability and Regulation}, language = {en} } @inproceedings{PokuttaSchmaltz, author = {Pokutta, Sebastian and Schmaltz, Christian}, title = {Optimal Planning under Basel III Regulations}, series = {Proceedings of 24th Australasian Finance and Banking Conference}, booktitle = {Proceedings of 24th Australasian Finance and Banking Conference}, language = {en} } @inproceedings{BraunFioriniPokuttaetal., author = {Braun, G{\´a}bor and Fiorini, Samuel and Pokutta, Sebastian and Steurer, D.}, title = {Approximation Limits of Linear Programs (Beyond Hierarchies)}, series = {Proceedings of FOCS}, booktitle = {Proceedings of FOCS}, language = {en} } @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} } @article{BraunPokutta, 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}, series = {Operations Research Letters}, volume = {42}, journal = {Operations Research Letters}, pages = {307 -- 310}, language = {en} } @article{DrewesPokutta, author = {Drewes, S. and Pokutta, Sebastian}, title = {Computing discrete expected utility maximizing portfolios}, series = {Journal of Investing}, volume = {23}, journal = {Journal of Investing}, number = {4}, pages = {121 -- 132}, language = {en} } @article{DrewesPokutta, author = {Drewes, S. and Pokutta, Sebastian}, title = {Symmetry-exploiting cuts for a class of mixed-0/1 second order cone programs}, series = {Discrete Optimization}, volume = {13}, journal = {Discrete Optimization}, pages = {23 -- 35}, language = {en} } @article{MartinMuellerPokutta, author = {Martin, Alexander and M{\"u}ller, J. and Pokutta, Sebastian}, title = {Strict linear prices in non-convex European day-ahead electricity markets}, series = {Optimization Methods and Software}, volume = {29}, journal = {Optimization Methods and Software}, number = {1}, pages = {189 -- 221}, language = {en} } @article{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 = {Mathematical Programming B}, volume = {153}, journal = {Mathematical Programming B}, number = {1}, pages = {179 -- 199}, language = {en} } @article{BraunFioriniPokuttaetal., author = {Braun, G{\´a}bor and Fiorini, Samuel and Pokutta, Sebastian and Steurer, D.}, title = {Approximation Limits of Linear Programs (Beyond Hierarchies)}, series = {Mathematics of Operations Research}, volume = {40}, journal = {Mathematics of Operations Research}, number = {3}, pages = {179 -- 199}, language = {en} } @article{BraunPokutta, author = {Braun, G{\´a}bor and Pokutta, Sebastian}, title = {The matching polytope does not admit fully-polynomial size relaxation schemes}, series = {IEEE Transactions on Information Theory}, volume = {61}, journal = {IEEE Transactions on Information Theory}, number = {10}, pages = {1 -- 11}, language = {en} } @article{BraunPokuttaXie, author = {Braun, G{\´a}bor and Pokutta, Sebastian and Xie, Y.}, title = {Info-Greedy Sequential Adaptive Compressed Sensing}, series = {IEEE Journal of Selected Topics in Signal Processing}, volume = {9}, journal = {IEEE Journal of Selected Topics in Signal Processing}, number = {4}, pages = {601 -- 611}, language = {en} } @article{FioriniMassarPokuttaetal., 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}, series = {Journal of the ACM}, volume = {62}, journal = {Journal of the ACM}, number = {2}, pages = {1 -- 17}, language = {en} } @article{BraunFioriniPokutta, author = {Braun, G{\´a}bor and Fiorini, Samuel and Pokutta, Sebastian}, title = {Average case polyhedral complexity of the maximum stable set problem}, series = {Mathematical Programming A}, volume = {160}, journal = {Mathematical Programming A}, number = {1}, pages = {407 -- 431}, language = {en} } @article{BraunPokutta, author = {Braun, G{\´a}bor and Pokutta, Sebastian}, title = {A polyhedral characterization of Border Bases}, series = {SIAM Journal on Discrete Mathematics}, volume = {30}, journal = {SIAM Journal on Discrete Mathematics}, number = {1}, pages = {239 -- 265}, language = {en} } @article{BraunPokutta, author = {Braun, G{\´a}bor and Pokutta, Sebastian}, title = {Common information and unique disjointness}, series = {Algorithmica}, volume = {76}, journal = {Algorithmica}, number = {3}, pages = {597 -- 629}, language = {en} } @article{GatzertPokuttaVogl, author = {Gatzert, Nadine and Pokutta, Sebastian and Vogl, Nikolai}, title = {Convergence of Capital and Insurance Markets: Pricing Aspects of Index-Linked Catastrophic Loss Instruments}, series = {to appear in Journal of Risk and Insurance}, journal = {to appear in Journal of Risk and Insurance}, language = {en} } @inproceedings{CardereraDiakonikolasLinetal., author = {Carderera, Alejandro and Diakonikolas, Jelena and Lin, Cheuk Yin and Pokutta, Sebastian}, title = {Parameter-free Locally Accelerated Conditional Gradients}, series = {ICML 2021}, booktitle = {ICML 2021}, abstract = {Projection-free conditional gradient (CG) methods are the algorithms of choice for constrained optimization setups in which projections are often computationally prohibitive but linear optimization over the constraint set remains computationally feasible. Unlike in projection-based methods, globally accelerated convergence rates are in general unattainable for CG. However, a very recent work on Locally accelerated CG (LaCG) has demonstrated that local acceleration for CG is possible for many settings of interest. The main downside of LaCG is that it requires knowledge of the smoothness and strong convexity parameters of the objective function. We remove this limitation by introducing a novel, Parameter-Free Locally accelerated CG (PF-LaCG) algorithm, for which we provide rigorous convergence guarantees. Our theoretical results are complemented by numerical experiments, which demonstrate local acceleration and showcase the practical improvements of PF-LaCG over non-accelerated algorithms, both in terms of iteration count and wall-clock time.}, language = {en} } @article{BienenstockMunozPokutta, author = {Bienenstock, Daniel and Mu{\~n}oz, Gonzalo and Pokutta, Sebastian}, title = {Principled Deep Neural Network Training through Linear Programming}, abstract = {Deep Learning has received significant attention due to its impressive performance in many state-of-the-art learning tasks. Unfortunately, while very powerful, Deep Learning is not well understood theoretically and in particular only recently results for the complexity of training deep neural networks have been obtained. In this work we show that large classes of deep neural networks with various architectures (e.g., DNNs, CNNs, Binary Neural Networks, and ResNets), activation functions (e.g., ReLUs and leaky ReLUs), and loss functions (e.g., Hinge loss, Euclidean loss, etc) can be trained to near optimality with desired target accuracy using linear programming in time that is exponential in the input data and parameter space dimension and polynomial in the size of the data set; improvements of the dependence in the input dimension are known to be unlikely assuming P≠NP, and improving the dependence on the parameter space dimension remains open. In particular, we obtain polynomial time algorithms for training for a given fixed network architecture. Our work applies more broadly to empirical risk minimization problems which allows us to generalize various previous results and obtain new complexity results for previously unstudied architectures in the proper learning setting.}, language = {en} } @inproceedings{Kerdreuxd'AspremontPokutta, author = {Kerdreux, Thomas and d'Aspremont, Alexandre and Pokutta, Sebastian}, title = {Projection-Free Optimization on Uniformly Convex Sets}, series = {To Appear in Proceedings of AISTATS}, booktitle = {To Appear in Proceedings of AISTATS}, language = {en} } @article{CardereraPokutta, author = {Carderera, Alejandro and Pokutta, Sebastian}, title = {Second-order Conditional Gradient Sliding}, 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{Kerdreuxd'AspremontPokutta, author = {Kerdreux, Thomas and d'Aspremont, Alexandre and Pokutta, Sebastian}, title = {Local and Global Uniform Convexity Conditions}, 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} } @article{BaermannMartinPokuttaetal., author = {B{\"a}rmann, Andreas and Martin, Alexander and Pokutta, Sebastian and Schneider, Oskar}, title = {An Online-Learning Approach to Inverse Optimization}, language = {en} } @inproceedings{ParczykPokuttaSpiegeletal., author = {Parczyk, Olaf and Pokutta, Sebastian and Spiegel, Christoph and Szab{\´o}, Tibor}, title = {New Ramsey Multiplicity Bounds and Search Heuristics}, series = {Discrete Mathematics Days}, booktitle = {Discrete Mathematics Days}, abstract = {We study two related problems concerning the number of monochromatic cliques in two-colorings of the complete graph that go back to questions of Erdős. Most notably, we improve the 25-year-old upper bounds of Thomason on the Ramsey multiplicity of K4 and K5 and we settle the minimum number of independent sets of size 4 in graphs with clique number at most 4. Motivated by the elusiveness of the symmetric Ramsey multiplicity problem, we also introduce an off-diagonal variant and obtain tight results when counting monochromatic K4 or K5 in only one of the colors and triangles in the other. The extremal constructions for each problem turn out to be blow-ups of a finite graph and were found through search heuristics. They are complemented by lower bounds and stability results established using Flag Algebras, resulting in a fully computer-assisted approach. More broadly, these problems lead us to the study of the region of possible pairs of clique and independent set densities that can be realized as the limit of some sequence of graphs.}, language = {en} } @article{HunkenschroederPokuttaWeismantel, author = {Hunkenschr{\"o}der, Christoph and Pokutta, Sebastian and Weismantel, Robert}, title = {Optimizing a low-dimensional convex function over a high-dimensional cub}, series = {SIAM Journal on Optimization}, journal = {SIAM Journal on Optimization}, language = {en} } @inproceedings{WaeldchenHuberPokutta, author = {W{\"a}ldchen, Stephan and Huber, Felix and Pokutta, Sebastian}, title = {Training Characteristic Functions with Reinforcement Learning: XAI-methods Play Connect Four}, series = {Proceedings of the International Conference on Machine Learning}, booktitle = {Proceedings of the International Conference on Machine Learning}, language = {en} } @inproceedings{TsujiTanakaPokutta, author = {Tsuji, Kazuma and Tanaka, Ken'ichiro and Pokutta, Sebastian}, title = {Pairwise Conditional Gradients without Swap Steps and Sparser Kernel Herding}, series = {Proceedings of the International Conference on Machine Learning}, booktitle = {Proceedings of the International Conference on Machine Learning}, language = {en} } @article{RouxPokuttaWirthetal., author = {Roux, Christophe and Pokutta, Sebastian and Wirth, Elias and Kerdreux, Thomas}, title = {Efficient Online-Bandit Strategies for Minimax Learning Problems}, abstract = {Several learning problems involve solving min-max problems, e.g., empirical distributional robust learning [Namkoong and Duchi, 2016, Curi et al., 2020] or learning with non-standard aggregated losses [Shalev- Shwartz and Wexler, 2016, Fan et al., 2017]. More specifically, these problems are convex-linear problems where the minimization is carried out over the model parameters w ∈ W and the maximization over the empirical distribution p ∈ K of the training set indexes, where K is the simplex or a subset of it. To design efficient methods, we let an online learning algorithm play against a (combinatorial) bandit algorithm. We argue that the efficiency of such approaches critically depends on the structure of K and propose two properties of K that facilitate designing efficient algorithms. We focus on a specific family of sets Sn,k encompassing various learning applications and provide high-probability convergence guarantees to the minimax values.}, language = {en} } @article{KossenHirzelMadaietal., author = {Kossen, Tabea and Hirzel, Manuel A. and Madai, Vince I. and Boenisch, Franziska and Hennemuth, Anja and Hildebrand, Kristian and Pokutta, Sebastian and Sharma, Kartikey and Hilbert, Adam and Sobesky, Jan and Galinovic, Ivana and Khalil, Ahmed A. and Fiebach, Jochen B. and Frey, Dietmar}, title = {Towards Sharing Brain Images: Differentially Private TOF-MRA Images with Segmentation Labels Using Generative Adversarial Networks}, series = {Frontiers in Artificial Intelligence}, journal = {Frontiers in Artificial Intelligence}, doi = {https://doi.org/10.3389/frai.2022.813842}, abstract = {Sharing labeled data is crucial to acquire large datasets for various Deep Learning applications. In medical imaging, this is often not feasible due to privacy regulations. Whereas anonymization would be a solution, standard techniques have been shown to be partially reversible. Here, synthetic data using a Generative Adversarial Network (GAN) with differential privacy guarantees could be a solution to ensure the patient's privacy while maintaining the predictive properties of the data. In this study, we implemented a Wasserstein GAN (WGAN) with and without differential privacy guarantees to generate privacy-preserving labeled Time-of-Flight Magnetic Resonance Angiography (TOF-MRA) image patches for brain vessel segmentation. The synthesized image-label pairs were used to train a U-net which was evaluated in terms of the segmentation performance on real patient images from two different datasets. Additionally, the Fr{\´e}chet Inception Distance (FID) was calculated between the generated images and the real images to assess their similarity. During the evaluation using the U-Net and the FID, we explored the effect of different levels of privacy which was represented by the parameter ϵ. With stricter privacy guarantees, the segmentation performance and the similarity to the real patient images in terms of FID decreased. Our best segmentation model, trained on synthetic and private data, achieved a Dice Similarity Coefficient (DSC) of 0.75 for ϵ = 7.4 compared to 0.84 for ϵ = ∞ in a brain vessel segmentation paradigm (DSC of 0.69 and 0.88 on the second test set, respectively). We identified a threshold of ϵ <5 for which the performance (DSC <0.61) became unstable and not usable. Our synthesized labeled TOF-MRA images with strict privacy guarantees retained predictive properties necessary for segmenting the brain vessels. Although further research is warranted regarding generalizability to other imaging modalities and performance improvement, our results mark an encouraging first step for privacy-preserving data sharing in medical imaging.}, language = {en} } @inproceedings{CriadoMartinezRubioPokutta, author = {Criado, Francisco and Mart{\´i}nez-Rubio, David and Pokutta, Sebastian}, title = {Fast Algorithms for Packing Proportional Fairness and its Dual}, series = {Proceedings of the Conference on Neural Information Processing Systems}, volume = {36}, booktitle = {Proceedings of the Conference on Neural Information Processing Systems}, 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} } @article{CardereraPokuttaSchuetteetal., author = {Carderera, Alejandro and Pokutta, Sebastian and Sch{\"u}tte, Christof and Weiser, Martin}, title = {CINDy: Conditional gradient-based Identification of Non-linear Dynamics - Noise-robust recovery}, series = {Journal of Computational and Applied Mathematics}, journal = {Journal of Computational and Applied Mathematics}, abstract = {Governing equations are essential to the study of nonlinear dynamics, often enabling the prediction of previously unseen behaviors as well as the inclusion into control strategies. The discovery of governing equations from data thus has the potential to transform data-rich fields where well-established dynamical models remain unknown. This work contributes to the recent trend in data-driven sparse identification of nonlinear dynamics of finding the best sparse fit to observational data in a large library of potential nonlinear models. We propose an efficient first-order Conditional Gradient algorithm for solving the underlying optimization problem. In comparison to the most prominent alternative algorithms, the new algorithm shows significantly improved performance on several essential issues like sparsity-induction, structure-preservation, noise robustness, and sample efficiency. We demonstrate these advantages on several dynamics from the field of synchronization, particle dynamics, and enzyme chemistry.}, language = {en} } @article{CombettesPokutta, author = {Combettes, Cyrille and Pokutta, Sebastian}, title = {Revisiting the Approximate Carath{\´e}odory Problem via the Frank-Wolfe Algorithm}, series = {Mathematical Programming}, volume = {197}, journal = {Mathematical Programming}, doi = {10.1007/s10107-021-01735-x}, pages = {191 -- 214}, language = {en} } @inproceedings{SofranacGleixnerPokutta, author = {Sofranac, Boro and Gleixner, Ambros and Pokutta, Sebastian}, title = {An Algorithm-Independent Measure of Progress for Linear Constraint Propagation}, series = {27th International Conference on Principles and Practice of Constraint Programming (CP 2021)}, 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}, 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} } @inproceedings{ChmielaGleixnerLichockietal., author = {Chmiela, Antonia and Gleixner, Ambros and Lichocki, Pawel and Pokutta, Sebastian}, title = {Online Learning for Scheduling MIP Heuristics}, series = {Integration of Constraint Programming, Artificial Intelligence, and Operations Research}, volume = {13884}, booktitle = {Integration of Constraint Programming, Artificial Intelligence, and Operations Research}, publisher = {Springer, Cham}, doi = {10.1007/978-3-031-33271-5_8}, pages = {114 -- 123}, abstract = {Mixed Integer Programming (MIP) is NP-hard, and yet modern solvers often solve large real-world problems within minutes. This success can partially be attributed to heuristics. Since their behavior is highly instance-dependent, relying on hard-coded rules derived from empirical testing on a large heterogeneous corpora of benchmark instances might lead to sub-optimal performance. In this work, we propose an online learning approach that adapts the application of heuristics towards the single instance at hand. We replace the commonly used static heuristic handling with an adaptive framework exploiting past observations about the heuristic's behavior to make future decisions. In particular, we model the problem of controlling Large Neighborhood Search and Diving - two broad and complex classes of heuristics - as a multi-armed bandit problem. Going beyond existing work in the literature, we control two different classes of heuristics simultaneously by a single learning agent. We verify our approach numerically and show consistent node reductions over the MIPLIB 2017 Benchmark set. For harder instances that take at least 1000 seconds to solve, we observe a speedup of 4\%.}, language = {en} }