TY - CHAP A1 - Hendrych, Deborah A1 - Besançon, Mathieu A1 - Pokutta, Sebastian T1 - Solving the optimal experiment design problem with mixed-integer convex methods T2 - 22nd International Symposium on Experimental Algorithms (SEA 2024) N2 - We tackle the Optimal Experiment Design Problem, which consists of choosing experiments to run or observations to select from a finite set to estimate the parameters of a system. The objective is to maximize some measure of information gained about the system from the observations, leading to a convex integer optimization problem. We leverage Boscia.jl, a recent algorithmic framework, which is based on a nonlinear branch-and-bound algorithm with node relaxations solved to approximate optimality using Frank-Wolfe algorithms. One particular advantage of the method is its efficient utilization of the polytope formed by the original constraints which is preserved by the method, unlike alternative methods relying on epigraph-based formulations. We assess our method against both generic and specialized convex mixed-integer approaches. Computational results highlight the performance of our proposed method, especially on large and challenging instances. Y1 - 2024 U6 - https://doi.org/10.4230/LIPIcs.SEA.2024.16 VL - 301 SP - 16:1 EP - 16:22 ER - TY - CHAP A1 - Kiem, Aldo A1 - Pokutta, Sebastian A1 - Spiegel, Christoph T1 - Categorification of Flag Algebras T2 - Discrete Mathematics Days 2024 Y1 - 2024 U6 - https://doi.org/10.37536/TYSP5643 SP - 259 EP - 264 ER - TY - CHAP A1 - Kiem, Aldo A1 - Pokutta, Sebastian A1 - Spiegel, Christoph T1 - The Four-Color Ramsey Multiplicity of Triangles T2 - Discrete Mathematics Days 2024 Y1 - 2024 U6 - https://doi.org/10.37536/TYSP5643 SP - 13 EP - 18 ER - TY - JOUR A1 - Hahn-Klimroth, Max A1 - Parczyk, Olaf A1 - Person, Yury T1 - Minimum degree conditions for containing an r-regular r-connected spanning subgraph JF - European Journal of Combinatorics Y1 - 2024 U6 - https://doi.org/10.1016/j.ejc.2024.103940 VL - 118 SP - 103940 ER - TY - JOUR A1 - Mundinger, Konrad A1 - Pokutta, Sebastian A1 - Spiegel, Christoph A1 - Zimmer, Max T1 - Extending the Continuum of Six-Colorings JF - Geombinatorics Quarterly Y1 - 2024 VL - 34 IS - 1 SP - 20 EP - 29 ER - TY - CHAP A1 - Mundinger, Konrad A1 - Pokutta, Sebastian A1 - Spiegel, Christoph A1 - Zimmer, Max T1 - Extending the Continuum of Six-Colorings T2 - Discrete Mathematics Days 2024 Y1 - 2024 U6 - https://doi.org/10.37536/TYSP5643 SP - 178 EP - 183 ER - TY - CHAP A1 - Martínez-Rubio, David A1 - Roux, Christophe A1 - Pokutta, Sebastian T1 - Convergence and Trade-Offs in Riemannian Gradient Descent and Riemannian Proximal Point T2 - Proceedings of the 41st International Conference on Machine Learning N2 - In this work, we analyze two of the most fundamental algorithms in geodesically convex optimization: Riemannian gradient descent and (possibly inexact) Riemannian proximal point. We quantify their rates of convergence and produce different variants with several trade-offs. Crucially, we show the iterates naturally stay in a ball around an optimizer, of radius depending on the initial distance and, in some cases, on the curvature. Previous works simply assumed bounded iterates, resulting in rates that were not fully quantified. We also provide an implementable inexact proximal point algorithm and prove several new useful properties of Riemannian proximal methods: they work when positive curvature is present, the proximal operator does not move points away from any optimizer, and we quantify the smoothness of its induced Moreau envelope. Further, we explore beyond our theory with empirical tests. Y1 - 2024 UR - https://raw.githubusercontent.com/mlresearch/v235/main/assets/marti-nez-rubio24a/marti-nez-rubio24a.pdf VL - 235 SP - 34920 EP - 34948 ER - TY - JOUR A1 - Gebhard, Oliver A1 - Hahn-Klimroth, Max A1 - Penschuck, Manuel A1 - Rolvien, Maurice A1 - Scarlett, Jonathan A1 - Tan, Nelvin A1 - Parczyk, Olaf T1 - Near optimal sparsity-constrained group testing: improved bounds JF - IEEE Transactions on Information Theory Y1 - 2022 ER - TY - JOUR A1 - Parczyk, Olaf A1 - Pokutta, Sebastian A1 - Spiegel, Christoph A1 - Szabó, Tibor T1 - New Ramsey multiplicity bounds and search heuristics JF - Foundations of Computational Mathematics Y1 - 2024 U6 - https://doi.org/10.1007/s10208-024-09675-6 ER - TY - JOUR A1 - Allen, Peter A1 - Pfenninger, Vincent A1 - Parczyk, Olaf T1 - Resilience for tight Hamiltonicity JF - Combinatorial Theory Y1 - 2024 U6 - https://doi.org/10.5070/C64163846 VL - 4 IS - 1 ER -