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 -