TY - CHAP A1 - Martínez-Rubio, David A1 - Pokutta, Sebastian T1 - Accelerated Riemannian Optimization: Handling Constraints with a Prox to Bound Geometric Penalties T2 - Proceedings of Thirty Sixth Conference on Learning Theory N2 - We propose a globally-accelerated, first-order method for the optimization of smooth and (strongly or not) geodesically-convex functions in a wide class of Hadamard manifolds. We achieve the same convergence rates as Nesterov’s accelerated gradient descent, up to a multiplicative geometric penalty and log factors. Crucially, we can enforce our method to stay within a compact set we define. Prior fully accelerated works \emph{resort to assuming} that the iterates of their algorithms stay in some pre-specified compact set, except for two previous methods of limited applicability. For our manifolds, this solves the open question in (Kim and Yang, 2022) about obtaining global general acceleration without iterates assumptively staying in the feasible set.In our solution, we design an accelerated Riemannian inexact proximal point algorithm, which is a result that was unknown even with exact access to the proximal operator, and is of independent interest. For smooth functions, we show we can implement the prox step inexactly with first-order methods in Riemannian balls of certain diameter that is enough for global accelerated optimization. Y1 - 2023 UR - https://proceedings.mlr.press/v195/martinez-rubio23a.html VL - 195 SP - 359 EP - 393 ER - TY - JOUR A1 - Šofranac, Boro A1 - Gleixner, Ambros A1 - Pokutta, Sebastian T1 - An Algorithm-independent Measure of Progress for Linear Constraint Propagation JF - Constraints Y1 - 2022 U6 - https://doi.org/10.1007/s10601-022-09338-9 VL - 27 SP - 432 EP - 455 ER - TY - CHAP A1 - Parczyk, Olaf A1 - Pokutta, Sebastian A1 - Spiegel, Christoph A1 - Szabó, Tibor T1 - New Ramsey Multiplicity Bounds and Search Heuristics T2 - Discrete Mathematics Days N2 - 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. Y1 - 2022 ER - TY - CHAP A1 - Parczyk, Olaf A1 - Pokutta, Sebastian A1 - Spiegel, Christoph A1 - Szabó, Tibor T1 - Fully Computer-assisted Proofs in Extremal Combinatorics T2 - Proceedings of the AAAI Conference on Artificial Intelligence N2 - We present a fully computer-assisted proof system for solving a particular family of problems in Extremal Combinatorics. Existing techniques using Flag Algebras have proven powerful in the past, but have so far lacked a computational counterpart to derive matching constructive bounds. We demonstrate that common search heuristics are capable of finding constructions far beyond the reach of human intuition. Additionally, the most obvious downside of such heuristics, namely a missing guarantee of global optimality, can often be fully eliminated in this case through lower bounds and stability results coming from the Flag Algebra approach. To illustrate the potential of this approach, we study two related and well-known problems in Extremal Graph Theory that go back to questions of Erdős from the 60s. Most notably, we present the first major improvement in the upper bound of the Ramsey multiplicity of the complete graph on 4 vertices in 25 years, precisely determine the first off-diagonal Ramsey multiplicity number, and settle the minimum number of independent sets of size four in graphs with clique number strictly less than five. Y1 - 2023 U6 - https://doi.org/10.1609/aaai.v37i10.26470 VL - 37 IS - 10 SP - 12482 EP - 12490 ER - TY - JOUR A1 - Hunkenschröder, Christoph A1 - Pokutta, Sebastian A1 - Weismantel, Robert T1 - Optimizing a low-dimensional convex function over a high-dimensional cub JF - SIAM Journal on Optimization Y1 - 2022 ER - TY - CHAP A1 - MacDonald, Jan A1 - Besançon, Mathieu A1 - Pokutta, Sebastian T1 - Interpretable Neural Networks with Frank-Wolfe: Sparse Relevance Maps and Relevance Orderings T2 - Proceedings of the International Conference on Machine Learning Y1 - 2022 ER - TY - CHAP A1 - Tsuji, Kazuma A1 - Tanaka, Ken'ichiro A1 - Pokutta, Sebastian T1 - Pairwise Conditional Gradients without Swap Steps and Sparser Kernel Herding T2 - Proceedings of the International Conference on Machine Learning Y1 - 2022 ER - TY - CHAP A1 - Wäldchen, Stephan A1 - Huber, Felix A1 - Pokutta, Sebastian T1 - Training Characteristic Functions with Reinforcement Learning: XAI-methods Play Connect Four T2 - Proceedings of the International Conference on Machine Learning Y1 - 2022 ER - TY - CHAP A1 - Sharma, Kartikey A1 - Hendrych, Deborah A1 - Besançon, Mathieu A1 - Pokutta, Sebastian T1 - Network Design for the Traffic Assignment Problem with Mixed-Integer Frank-Wolfe T2 - Proceedings of INFORMS Optimization Society Conference Y1 - 2024 ER - TY - JOUR A1 - Braun, Gábor A1 - Guzmán, Cristóbal A1 - Pokutta, Sebastian T1 - Corrections to “Lower Bounds on the Oracle Complexity of Nonsmooth Convex Optimization via Information Theory” JF - IEEE Transactions on Information Theory N2 - This note closes a gap in the proof of Theorem VI.3 from the article “Lower Bounds on the Oracle Complexity of Nonsmooth Convex Optimization via Information Theory” (2017). Y1 - 2024 U6 - https://doi.org/10.1109/TIT.2024.3357200 VL - 70 IS - 7 SP - 5408 EP - 5409 ER - TY - JOUR A1 - Kreimeier, Timo A1 - Pokutta, Sebastian A1 - Walther, Andrea A1 - Woodstock, Zev T1 - On a Frank-Wolfe approach for abs-smooth functions JF - Optimization Methods and Software Y1 - U6 - https://doi.org/10.1080/10556788.2023.2296985 ER - TY - JOUR A1 - Hunkenschröder, Christoph A1 - Pokutta, Sebastian A1 - Weismantel, Robert T1 - Optimizing a low-dimensional convex function over a high-dimensional cube JF - SIAM Journal on Optimization Y1 - 2022 ER - TY - CHAP A1 - Thuerck, Daniel A1 - Sofranac, Boro A1 - Pfetsch, Marc A1 - Pokutta, Sebastian T1 - Learning cuts via enumeration oracles T2 - Proceedings of Conference on Neural Information Processing Systems Y1 - 2023 ER - TY - CHAP A1 - Martínez-Rubio, David A1 - Pokutta, Sebastian T1 - Accelerated Riemannian optimization: Handling constraints with a prox to bound geometric penalties T2 - Proceedings of Optimization for Machine Learning (NeurIPS Workshop OPT 2022) Y1 - 2022 ER - TY - CHAP A1 - Martínez-Rubio, David A1 - Roux, Christophe A1 - Criscitiello, Christopher A1 - Pokutta, Sebastian T1 - Accelerated Riemannian Min-Max Optimization Ensuring Bounded Geometric Penalties T2 - Proceedings of Optimization for Machine Learning (NeurIPS Workshop OPT 2023) Y1 - 2023 ER - TY - JOUR A1 - Designolle, Sébastien A1 - Vértesi, Tamás A1 - Pokutta, Sebastian T1 - Symmetric multipartite Bell inequalities via Frank-Wolfe algorithms JF - Physics Review A N2 - In multipartite Bell scenarios, we study the nonlocality robustness of the Greenberger-Horne-Zeilinger (GHZ) state. When each party performs planar measurements forming a regular polygon, we exploit the symmetry of the resulting correlation tensor to drastically accelerate the computation of (i) a Bell inequality via Frank-Wolfe algorithms and (ii) the corresponding local bound. The Bell inequalities obtained are facets of the symmetrized local polytope and they give the best-known upper bounds on the nonlocality robustness of the GHZ state for three to ten parties. Moreover, for four measurements per party, we generalize our facets and hence show, for any number of parties, an improvement on Mermin's inequality in terms of noise robustness. We also compute the detection efficiency of our inequalities and show that some give rise to the activation of nonlocality in star networks, a property that was only shown with an infinite number of measurements. Y1 - 2024 U6 - https://doi.org/10.1103/PhysRevA.109.022205 VL - 109 IS - 2 ER - TY - CHAP A1 - Chmiela, Antonia A1 - Khalil, Elias B. A1 - Gleixner, Ambros A1 - Lodi, Andrea A1 - Pokutta, Sebastian T1 - Learning to Schedule Heuristics in Branch and Bound T2 - Thirty-fifth Conference on Neural Information Processing Systems, NeurIPS 2021 N2 - Primal heuristics play a crucial role in exact solvers for Mixed Integer Programming (MIP). While solvers are guaranteed to find optimal solutions given sufficient time, real-world applications typically require finding good solutions early on in the search to enable fast decision-making. While much of MIP research focuses on designing effective heuristics, the question of how to manage multiple MIP heuristics in a solver has not received equal attention. Generally, solvers follow hard-coded rules derived from empirical testing on broad sets of instances. Since the performance of heuristics is instance-dependent, using these general rules for a particular problem might not yield the best performance. In this work, we propose the first data-driven framework for scheduling heuristics in an exact MIP solver. By learning from data describing the performance of primal heuristics, we obtain a problem-specific schedule of heuristics that collectively find many solutions at minimal cost. We provide a formal description of the problem and propose an efficient algorithm for computing such a schedule. Compared to the default settings of a state-of-the-art academic MIP solver, we are able to reduce the average primal integral by up to 49% on a class of challenging instances. Y1 - 2021 ER - TY - CHAP A1 - Chmiela, Antonia A1 - Gleixner, Ambros A1 - Lichocki, Pawel A1 - Pokutta, Sebastian T1 - Online Learning for Scheduling MIP Heuristics T2 - Integration of Constraint Programming, Artificial Intelligence, and Operations Research N2 - 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%. Y1 - 2023 U6 - https://doi.org/10.1007/978-3-031-33271-5_8 VL - 13884 SP - 114 EP - 123 PB - Springer, Cham ER - TY - CHAP A1 - Gasse, Maxime A1 - Bowly, Simon A1 - Cappart, Quentin A1 - Charfreitag, Jonas A1 - Charlin, Laurent A1 - Chételat, Didier A1 - Chmiela, Antonia A1 - Dumouchelle, Justin A1 - Gleixner, Ambros A1 - Kazachkov, Aleksandr M. A1 - Khalil, Elias A1 - Lichocki, Pawel A1 - Lodi, Andrea A1 - Lubin, Miles A1 - Maddison, Chris J. A1 - Christopher, Morris A1 - Papageorgiou, Dimitri J. A1 - Parjadis, Augustin A1 - Pokutta, Sebastian A1 - Prouvost, Antoine A1 - Scavuzzo, Lara A1 - Zarpellon, Giulia A1 - Yang, Linxin A1 - Lai, Sha A1 - Wang, Akang A1 - Luo, Xiaodong A1 - Zhou, Xiang A1 - Huang, Haohan A1 - Shao, Shengcheng A1 - Zhu, Yuanming A1 - Zhang, Dong A1 - Quan, Tao A1 - Cao, Zixuan A1 - Xu, Yang A1 - Huang, Zhewei A1 - Zhou, Shuchang A1 - Binbin, Chen A1 - Minggui, He A1 - Hao, Hao A1 - Zhiyu, Zhang A1 - Zhiwu, An A1 - Kun, Mao T1 - The Machine Learning for Combinatorial Optimization Competition (ML4CO): results and insights T2 - Proceedings of Conference on Neural Information Processing Systems Y1 - 2022 ER - TY - JOUR A1 - Carderera, Alejandro A1 - Pokutta, Sebastian A1 - Schütte, Christof A1 - Weiser, Martin T1 - An efficient first-order conditional gradient algorithm in data-driven sparse identification of nonlinear dynamics to solve sparse recovery problems under noise JF - Journal of Computational and Applied Mathematics N2 - 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 framework, the new framework 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. Y1 - 2025 U6 - https://doi.org/10.1016/j.cam.2025.116675 VL - 470 ER -