@inproceedings{PokuttaSchmaltz, author = {Pokutta, Sebastian and Schmaltz, Christian}, title = {Optimal degree of centralization of liquidity management}, series = {Proceedings of 22nd Australasian Finance and Banking Conference}, booktitle = {Proceedings of 22nd Australasian Finance and Banking Conference}, language = {en} } @inproceedings{LanPokuttaZhouetal., author = {Lan, G. and Pokutta, Sebastian and Zhou, Y. and Zink, Daniel}, title = {Conditional Accelerated Lazy Stochastic Gradient Descent}, series = {Proceedings of the International Conference on Machine Learning (ICML)}, booktitle = {Proceedings of the International Conference on Machine Learning (ICML)}, language = {en} } @inproceedings{InanlouganjiPedrielliFainekosetal., author = {Inanlouganji, A. and Pedrielli, G. and Fainekos, G. and Pokutta, Sebastian}, title = {Continuous Simulation Optimization with Model Mismatch Using Gaussian Process Regression}, series = {Proceedings of the 2018 Winter Simulation Conference}, booktitle = {Proceedings of the 2018 Winter Simulation Conference}, language = {en} } @inproceedings{PokuttaSinghTorrico, author = {Pokutta, Sebastian and Singh, M. and Torrico, A.}, title = {Efficient algorithms for robust submodular maximization under matroid constraints}, series = {ICML Workshop Paper}, booktitle = {ICML Workshop Paper}, language = {en} } @inproceedings{BraunPokuttaTuetal., author = {Braun, G{\´a}bor and Pokutta, Sebastian and Tu, Dan and Wright, Stephen}, title = {Blended Conditional Gradients: the unconditioning of conditional gradients}, series = {Proceedings of ICML}, booktitle = {Proceedings of ICML}, language = {en} } @inproceedings{DiakonikolasCardereraPokutta, author = {Diakonikolas, Jelena and Carderera, Alejandro and Pokutta, Sebastian}, title = {Breaking the Curse of Dimensionality (Locally) to Accelerate Conditional Gradients}, series = {OPTML Workshop Paper}, booktitle = {OPTML Workshop Paper}, language = {en} } @inproceedings{CombettesPokutta, author = {Combettes, Cyrille W. and Pokutta, Sebastian}, title = {Blended Matching Pursuit}, series = {Proceedings of NeurIPS}, booktitle = {Proceedings of NeurIPS}, language = {en} } @inproceedings{Kerdreuxd’AspremontPokutta, author = {Kerdreux, T. and d'Aspremont, A. and Pokutta, Sebastian}, title = {Restarting Frank-Wolfe}, series = {Proceedings of AISTATS}, booktitle = {Proceedings of AISTATS}, language = {en} } @inproceedings{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 = {Proceedings of AISTATS}, booktitle = {Proceedings of AISTATS}, 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 = {OPTML Workshop Paper}, booktitle = {OPTML Workshop Paper}, language = {en} } @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} }