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 - 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 - CHAP A1 - Bestuzheva, Ksenia A1 - Gleixner, Ambros A1 - Völker, Helena T1 - Strengthening SONC Relaxations with Constraints Derived from Variable Bounds T2 - Proceedings of the Hungarian Global Optimization Workshop HUGO 2022 N2 - Certificates of polynomial nonnegativity can be used to obtain tight dual bounds for polynomial optimization problems. We consider Sums of Nonnegative Circuit (SONC) polynomials certificates, which are well suited for sparse problems since the computational cost depends only on the number of terms in the polynomials and does not depend on the degrees of the polynomials. This work is a first step to integrating SONC-based relaxations of polynomial problems into a branch-and-bound algorithm. To this end, the SONC relaxation for constrained optimization problems is extended in order to better utilize variable bounds, since this property is key for the success of a relaxation in the context of branch-and-bound. Computational experiments show that the proposed extension is crucial for making the SONC relaxations applicable to most constrained polynomial optimization problems and for integrating the two approaches. Y1 - 2022 SP - 41 EP - 44 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 - 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 - TY - CHAP A1 - Wirth, Elias A1 - Kerdreux, Thomas A1 - Pokutta, Sebastian T1 - Acceleration of Frank-Wolfe Algorithms with Open Loop Step-sizes T2 - Proceedings of International Conference on Artificial Intelligence and Statistics Y1 - 2023 ER - TY - CHAP A1 - Wirth, Elias A1 - Kera, A1 - Pokutta, Sebastian T1 - Approximate Vanishing Ideal Computations at Scale T2 - Proceedings of International Conference on Learning Representations Y1 - 2023 ER - TY - CHAP A1 - Głuch, Grzegorz A1 - Turan, Berkant A1 - Nagarajan, Sai Ganesh A1 - Pokutta, Sebastian T1 - The Good, the Bad and the Ugly: Meta-Analysis of Watermarks, Transferable Attacks and Adversarial Defenses T2 - Proceedings of the Conference on Neural Information Processing Systems Y1 - 2025 ER - TY - CHAP A1 - Kera, Hiroshi A1 - Pelleriti, Nico A1 - Ishihara, Yuki A1 - Zimmer, Max A1 - Pokutta, Sebastian T1 - Computational Algebra with Attention: Transformer Oracles for Border Basis Algorithms T2 - Proceedings of the Conference on Neural Information Processing Systems Y1 - 2025 ER - TY - CHAP A1 - Gonnermann-Müller, Jana A1 - Brandenburger, Bonny A1 - Vladova, Gergana A1 - Gronau, Norbert T1 - To What Extent Can Individualisation in Terms of Different Types of Mode Improve Learning Outcomes and Learner Satisfaction? A Pre-study T2 - Proceedings of the Hawaii International Conference on System Sciences Y1 - 2023 ER - TY - CHAP A1 - Gonnermann-Müller, Jana A1 - Leins, Nicolas A1 - Gronau, Norbert A1 - Kosch, Thomas T1 - Value by design: Reducing Cognitive Load by Using Visual Guidance in Augmented RealityAn Eye-Tracking Study T2 - Proceedings of the International Conference on Information Systems Y1 - 2024 ER - TY - CHAP A1 - Hendrych, Deborah A1 - Besançon, Mathieu A1 - Martínez-Rubio, David A1 - Pokutta, Sebastian T1 - Secant line search for Frank-Wolfe algorithms T2 - Proceedings of the 42nd International Conference on Machine Learning Y1 - 2025 UR - https://raw.githubusercontent.com/mlresearch/v267/main/assets/hendrych25a/hendrych25a.pdf VL - 267 SP - 23005 EP - 23029 ER -