TY - CHAP A1 - Pokutta, Sebastian A1 - Schmaltz, Christian T1 - A network model for bank lending capacity T2 - Proceedings of Systemic Risk, Basel III, Financial Stability and Regulation Y1 - 2011 UR - http://papers.ssrn.com/sol3/papers.cfm?abstract_id=1773964 ER - TY - CHAP A1 - Braun, Gábor A1 - Pokutta, Sebastian T1 - The matching polytope does not admit fully-polynomial size relaxation schemes T2 - Proceeedings of SODA Y1 - 2015 ER - TY - CHAP A1 - Braun, Gábor A1 - Pokutta, Sebastian A1 - Zink, Daniel T1 - Inapproximability of combinatorial problems via small LPs and SDPs T2 - Proceeedings of STOC Y1 - 2015 ER - TY - CHAP A1 - Pokutta, Sebastian T1 - Information Theory and Polyhedral Combinatorics T2 - Proceedings of 53rd Annual Allerton Conference on Communication, Control, and Computing Y1 - 2015 N1 - Additional Note: http://ieeexplore.ieee.org/abstract/document/7447134/ N1 - URL of the PDF: http://ieeexplore.ieee.org/abstract/document/7447134/ ER - TY - CHAP A1 - Song, R. A1 - Xie, Y. A1 - Pokutta, Sebastian T1 - Sequential Sensing with Model Mismatch T2 - Proceedings of ISIT Y1 - 2015 ER - TY - CHAP A1 - Xie, Y. A1 - Li, Q. A1 - Pokutta, Sebastian T1 - Supervised Online Subspace Tracking T2 - Proceedings of Asilomar Conference on Signals, Systems, and Computers Y1 - 2015 ER - TY - CHAP A1 - Roy, Aurko A1 - Pokutta, Sebastian T1 - Hierarchical Clustering via Spreading Metrics T2 - Proceedings of NIPS Y1 - 2016 N1 - Additional Note: http://https://papers.nips.cc/paper/by-source-2016-1199 https://arxiv.org/abs/1610.09269 N1 - URL of the PDF: https://papers.nips.cc/paper/by-source-2016-1199 ER - TY - CHAP A1 - Braun, Gábor A1 - Roy, Aurko A1 - Pokutta, Sebastian T1 - Stronger Reductions for Extended Formulations T2 - Proceedings of IPCO Y1 - 2016 ER - TY - CHAP A1 - Braun, Gábor A1 - Brown-Cohen, Jonah A1 - Huq, Arefin A1 - Pokutta, Sebastian A1 - Raghavendra, Prasad A1 - Weitz, Benjamin A1 - Zink, Daniel T1 - The matching problem has no small symmetric SDP T2 - Proceddings of SODA 2016 Y1 - 2016 N1 - URL of the PDF: http://ieeexplore.ieee.org/abstract/document/7447134/ ER - TY - CHAP A1 - Roy, Aurko A1 - Xu, Huan A1 - Pokutta, Sebastian T1 - Reinforcement Learning under Model Mismatch T2 - Proceedings of NIPS Y1 - 2017 N1 - Additional Note: http://https://papers.nips.cc/paper/by-source-2016-1199 https://arxiv.org/abs/1610.09269 ER - TY - CHAP A1 - Bärmann, Andreas A1 - Pokutta, Sebastian A1 - Schneider, Oskar T1 - Emulating the Expert: Inverse Optimization through Online Learning T2 - Proceedings of the International Conference on Machine Learning (ICML) Y1 - 2017 N1 - URL of the PDF: http://proceedings.mlr.press/v70/barmann17a.html N1 - URL of the Poster: https://app.box.com/s/h3ychkv99il7oyzw7sym8la5lhit3elg N1 - URL of the Slides: https://app.box.com/s/7ti8sz8mf5s2znn1qo32in4jxy5gjnn1 N1 - URL of the Abstract: http://www.pokutta.com/blog/research/2018/11/25/expertLearning-abstract.html ER - TY - CHAP A1 - Sofranac, Boro A1 - Gleixner, Ambros A1 - Pokutta, Sebastian T1 - An Algorithm-Independent Measure of Progress for Linear Constraint Propagation T2 - 27th International Conference on Principles and Practice of Constraint Programming (CP 2021) N2 - 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. Y1 - 2021 U6 - https://doi.org/10.4230/LIPIcs.CP.2021.52 VL - 210 SP - 52:1 EP - 52:17 ER - TY - JOUR A1 - Carderera, Alejandro A1 - Pokutta, Sebastian T1 - Second-order Conditional Gradient Sliding N2 - 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. Y1 - 2020 ER - TY - JOUR A1 - Mathieu, Besançon A1 - Carderera, Alejandro A1 - Pokutta, Sebastian T1 - FrankWolfe.jl: a high-performance and flexible toolbox for Frank-Wolfe algorithms and Conditional Gradients JF - INFORMS Journal on Computing N2 - We present FrankWolfe.jl, an open-source implementation of several popular Frank–Wolfe and conditional gradients variants for first-order constrained optimization. The package is designed with flexibility and high performance in mind, allowing for easy extension and relying on few assumptions regarding the user-provided functions. It supports Julia’s unique multiple dispatch feature, and it interfaces smoothly with generic linear optimization formulations using MathOptInterface.jl. Y1 - 2022 U6 - https://doi.org/10.1287/ijoc.2022.1191 VL - 34 IS - 5 SP - 2383 EP - 2865 ER - TY - JOUR A1 - Abbas, Amira A1 - Ambainis, Andris A1 - Augustino, Brandon A1 - Bärtschi, Andreas A1 - Buhrman, Harry A1 - Coffrin, Carleton A1 - Cortiana, Giorgio A1 - Dunjko, Vedran A1 - Egger, Daniel J. A1 - Elmegreen, Bruce G. A1 - Franco, Nicola A1 - Fratini, Filippo A1 - Fuller, Bryce A1 - Gacon, Julien A1 - Gonciulea, Constantin A1 - Gribling, Sander A1 - Gupta, Swati A1 - Hadfield, Stuart A1 - Heese, Raoul A1 - Kircher, Gerhard A1 - Kleinert, Thomas A1 - Koch, Thorsten A1 - Korpas, Georgios A1 - Lenk, Steve A1 - Marecek, Jakub A1 - Markov, Vanio A1 - Mazzola, Guglielmo A1 - Mensa, Stefano A1 - Mohseni, Naeimeh A1 - Nannicini, Giacomo A1 - O’Meara, Corey A1 - Tapia, Elena Peña A1 - Pokutta, Sebastian A1 - Proissl, Manuel A1 - Rebentrost, Patrick A1 - Sahin, Emre A1 - Symons, Benjamin C. B. A1 - Tornow, Sabine A1 - Valls, Víctor A1 - Woerner, Stefan A1 - Wolf-Bauwens, Mira L. A1 - Yard, Jon A1 - Yarkoni, Sheir A1 - Zechiel, Dirk A1 - Zhuk, Sergiy A1 - Zoufal, Christa T1 - Challenges and opportunities in quantum optimization JF - Nature Reviews Physics Y1 - 2024 U6 - https://doi.org/10.1038/s42254-024-00770-9 SN - 2522-5820 VL - 6 SP - 718 EP - 735 PB - Springer Science and Business Media LLC ER - TY - CHAP A1 - Sofranac, Boro A1 - Gleixner, Ambros A1 - Pokutta, Sebastian T1 - Accelerating Domain Propagation: an Efficient GPU-Parallel Algorithm over Sparse Matrices T2 - 2020 IEEE/ACM 10th Workshop on Irregular Applications: Architectures and Algorithms (IA3) N2 - Fast domain propagation of linear constraints has become a crucial component of today's best algorithms and solvers for mixed integer programming and pseudo-boolean optimization to achieve peak solving performance. Irregularities in the form of dynamic algorithmic behaviour, dependency structures, and sparsity patterns in the input data make efficient implementations of domain propagation on GPUs and, more generally, on parallel architectures challenging. This is one of the main reasons why domain propagation in state-of-the-art solvers is single thread only. In this paper, we present a new algorithm for domain propagation which (a) avoids these problems and allows for an efficient implementation on GPUs, and is (b) capable of running propagation rounds entirely on the GPU, without any need for synchronization or communication with the CPU. We present extensive computational results which demonstrate the effectiveness of our approach and show that ample speedups are possible on practically relevant problems: on state-of-the-art GPUs, our geometric mean speed-up for reasonably-large instances is around 10x to 20x and can be as high as 195x on favorably-large instances. Y1 - 2020 U6 - https://doi.org/10.1109/IA351965.2020.00007 N1 - URL of the Slides: https://app.box.com/s/qy0pjmhtbm7shk2ypxjxlh2sj4nudvyu N1 - URL of the Abstract: http://www.pokutta.com/blog/research/2020/09/20/gpu-prob.html SP - 1 EP - 11 ER - TY - JOUR A1 - Šofranac, Boro A1 - Gleixner, Ambros A1 - Pokutta, Sebastian T1 - Accelerating domain propagation: An efficient GPU-parallel algorithm over sparse matrices JF - Parallel Computing N2 - • Currently, domain propagation in state-of-the-art MIP solvers is single thread only. • The paper presents a novel, efficient GPU algorithm to perform domain propagation. • Challenges are dynamic algorithmic behavior, dependency structures, sparsity patterns. • The algorithm is capable of running entirely on the GPU with no CPU involvement. • We achieve speed-ups of around 10x to 20x, up to 180x on favorably-large instances. Y1 - 2022 U6 - https://doi.org/10.1016/j.parco.2021.102874 VL - 109 SP - 102874 ER - TY - CHAP A1 - Diakonikolas, Jelena A1 - Carderera, Alejandro A1 - Pokutta, Sebastian T1 - Breaking the Curse of Dimensionality (Locally) to Accelerate Conditional Gradients T2 - OPTML Workshop Paper Y1 - 2019 N1 - URL of the Code: https://colab.research.google.com/drive/1ejjfCan7xnEhWWJXCIzb03CwQRG9iW_O N1 - URL of the PDF: https://opt-ml.org/papers/2019/paper_26.pdf N1 - URL of the Poster: https://app.box.com/s/d7p038u7df422q4jsccbmj15mngqv2ws N1 - URL of the Slides: https://app.box.com/s/gphkhapso7d1vrfnzqykkb3vx0agxh8w N1 - URL of the Abstract: http://www.pokutta.com/blog/research/2019/07/04/LaCG-abstract.html ER - TY - CHAP A1 - Combettes, Cyrille W. A1 - Pokutta, Sebastian T1 - Blended Matching Pursuit T2 - Proceedings of NeurIPS Y1 - 2019 N1 - URL of the Code: https://colab.research.google.com/drive/17XYIxnCcJjKswba9mAaXFWnNGVZdsaXQ N1 - URL of the PDF: https://papers.nips.cc/paper/8478-blended-matching-pursuit N1 - URL of the Poster: https://app.box.com/s/j6lbh49udjd45krhxcypufxwdofw6br8 N1 - URL of the Slides: https://app.box.com/s/8lfktq6h3dqp9t2gqydu2tp8h2uxgz7m N1 - URL of the Abstract: http://www.pokutta.com/blog/research/2019/05/27/bmp-abstract.html ER - TY - CHAP A1 - Pokutta, Sebastian A1 - Singh, M. A1 - Torrico, A. T1 - On the Unreasonable Effectiveness of the Greedy Algorithm: Greedy Adapts to Sharpness T2 - OPTML Workshop Paper Y1 - 2019 N1 - URL of the PDF: https://opt-ml.org/papers/2019/paper_16.pdf N1 - URL of the Poster: https://app.box.com/s/24vbh1s2vib11upqyepzen3lzdl13skr ER - TY - CHAP A1 - Criado, Francisco A1 - Martínez-Rubio, David A1 - Pokutta, Sebastian T1 - Fast Algorithms for Packing Proportional Fairness and its Dual T2 - Proceedings of the Conference on Neural Information Processing Systems N2 - 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. Y1 - 2022 VL - 36 ER - TY - CHAP A1 - Carderera, Alejandro A1 - Pokutta, Sebastian A1 - Mathieu, Besançon T1 - Simple steps are all you need: Frank-Wolfe and generalized self-concordant functions T2 - Thirty-fifth Conference on Neural Information Processing Systems, NeurIPS 2021 N2 - Generalized self-concordance is a key property present in the objective function of many important learning problems. We establish the convergence rate of a simple Frank-Wolfe variant that uses the open-loop step size strategy 𝛾𝑡 = 2/(𝑡 + 2), obtaining a O (1/𝑡) convergence rate for this class of functions in terms of primal gap and Frank-Wolfe gap, where 𝑡 is the iteration count. This avoids the use of second-order information or the need to estimate local smoothness parameters of previous work. We also show improved convergence rates for various common cases, e.g., when the feasible region under consideration is uniformly convex or polyhedral. Y1 - 2021 ER - TY - JOUR A1 - Kerdreux, Thomas A1 - d'Aspremont, Alexandre A1 - Pokutta, Sebastian T1 - Local and Global Uniform Convexity Conditions N2 - 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. Y1 - 2021 ER - TY - CHAP A1 - Zimmer, Max A1 - Spiegel, Christoph A1 - Pokutta, Sebastian T1 - How I Learned to Stop Worrying and Love Retraining T2 - Proceedings of International Conference on Learning Representations Y1 - 2023 ER -