@inproceedings{SharmaHendrychBesanconetal., author = {Sharma, Kartikey and Hendrych, Deborah and Besan{\c{c}}on, Mathieu and Pokutta, Sebastian}, title = {Network Design for the Traffic Assignment Problem with Mixed-Integer Frank-Wolfe}, series = {Proceedings of INFORMS Optimization Society Conference}, booktitle = {Proceedings of INFORMS Optimization Society Conference}, language = {en} } @article{KreimeierPokuttaWaltheretal., author = {Kreimeier, Timo and Pokutta, Sebastian and Walther, Andrea and Woodstock, Zev}, title = {On a Frank-Wolfe approach for abs-smooth functions}, series = {Optimization Methods and Software}, journal = {Optimization Methods and Software}, doi = {10.1080/10556788.2023.2296985}, language = {en} } @article{DesignolleVertesiPokutta, author = {Designolle, S{\´e}bastien and V{\´e}rtesi, Tam{\´a}s and Pokutta, Sebastian}, title = {Symmetric multipartite Bell inequalities via Frank-Wolfe algorithms}, series = {Physics Review A}, volume = {109}, journal = {Physics Review A}, number = {2}, doi = {10.1103/PhysRevA.109.022205}, abstract = {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.}, language = {en} } @article{DezaPokuttaPournin, author = {Deza, Antoine and Pokutta, Sebastian and Pournin, Lionel}, title = {The complexity of geometric scaling}, series = {Operations Research Letters}, volume = {52}, journal = {Operations Research Letters}, doi = {10.1016/j.orl.2023.11.010}, pages = {107057}, language = {en} } @inproceedings{WaeldchenSharmaTuranetal., author = {W{\"a}ldchen, Stephan and Sharma, Kartikey and Turan, Berkant and Zimmer, Max and Pokutta, Sebastian}, title = {Interpretability Guarantees with Merlin-Arthur Classifiers}, series = {Proceedings of International Conference on Artificial Intelligence and Statistics}, booktitle = {Proceedings of International Conference on Artificial Intelligence and Statistics}, abstract = {We propose an interactive multi-agent classifier that provides provable interpretability guarantees even for complex agents such as neural networks. These guarantees consist of lower bounds on the mutual information between selected features and the classification decision. Our results are inspired by the Merlin-Arthur protocol from Interactive Proof Systems and express these bounds in terms of measurable metrics such as soundness and completeness. Compared to existing interactive setups, we rely neither on optimal agents nor on the assumption that features are distributed independently. Instead, we use the relative strength of the agents as well as the new concept of Asymmetric Feature Correlation which captures the precise kind of correlations that make interpretability guarantees difficult. We evaluate our results on two small-scale datasets where high mutual information can be verified explicitly.}, language = {en} } @article{BraunGuzmanPokutta, author = {Braun, G{\´a}bor and Guzm{\´a}n, Crist{\´o}bal and Pokutta, Sebastian}, title = {Corrections to "Lower Bounds on the Oracle Complexity of Nonsmooth Convex Optimization via Information Theory"}, series = {IEEE Transactions on Information Theory}, volume = {70}, journal = {IEEE Transactions on Information Theory}, number = {7}, doi = {10.1109/TIT.2024.3357200}, pages = {5408 -- 5409}, abstract = {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).}, language = {en} } @inproceedings{MartinezRubioRouxPokutta, author = {Mart{\´i}nez-Rubio, David and Roux, Christophe and Pokutta, Sebastian}, title = {Convergence and trade-offs in riemannian gradient descent and riemannian proximal point}, series = {Proceedings of International Conference on Machine Learning}, booktitle = {Proceedings of International Conference on Machine Learning}, language = {en} } @inproceedings{MundingerPokuttaSpiegeletal., author = {Mundinger, Konrad and Pokutta, Sebastian and Spiegel, Christoph and Zimmer, Max}, title = {Extending the Continuum of Six-Colorings}, series = {Proceedings of Discrete Mathematics Days}, booktitle = {Proceedings of Discrete Mathematics Days}, language = {en} } @article{MundingerPokuttaSpiegeletal., author = {Mundinger, Konrad and Pokutta, Sebastian and Spiegel, Christoph and Zimmer, Max}, title = {Extending the Continuum of Six-Colorings}, series = {Geombinatorics Quarterly}, journal = {Geombinatorics Quarterly}, language = {en} } @article{ParczykPokuttaSpiegeletal., author = {Parczyk, Olaf and Pokutta, Sebastian and Spiegel, Christoph and Szab{\´o}, Tibor}, title = {New Ramsey multiplicity bounds and search heuristics}, series = {Foundations of Computational Mathematics}, journal = {Foundations of Computational Mathematics}, language = {en} } @inproceedings{PaulsZimmerKellyetal., author = {Pauls, Jan and Zimmer, Max and Kelly, Una M and Schwartz, Martin and Saatchi, Sassan and Ciais, Philippe and Pokutta, Sebastian and Brandt, Martin and Gieseke, Fabian}, title = {Estimating canopy height at scale}, series = {Proceedings of International Conference on Machine Learning}, booktitle = {Proceedings of International Conference on Machine Learning}, language = {en} } @inproceedings{KiemPokuttaSpiegel, author = {Kiem, Aldo and Pokutta, Sebastian and Spiegel, Christoph}, title = {The 4-color Ramsey multiplicity of triangles}, series = {Proceedings of Discrete Mathematics Days}, booktitle = {Proceedings of Discrete Mathematics Days}, language = {en} } @inproceedings{KiemPokuttaSpiegel, author = {Kiem, Aldo and Pokutta, Sebastian and Spiegel, Christoph}, title = {Categorification of Flag Algebras}, series = {Proceedings of Discrete Mathematics Days}, booktitle = {Proceedings of Discrete Mathematics Days}, language = {en} } @article{CardereraBesanconPokutta, author = {Carderera, Alejandro and Besan{\c{c}}on, Mathieu and Pokutta, Sebastian}, title = {Scalable Frank-Wolfe on generalized self-concordant functions via simple steps}, series = {SIAM Journal on Optimization}, volume = {34}, journal = {SIAM Journal on Optimization}, number = {3}, doi = {10.1137/23M1616789}, language = {en} } @inproceedings{HendrychBesanconPokutta, author = {Hendrych, Deborah and Besan{\c{c}}on, Mathieu and Pokutta, Sebastian}, title = {Solving the optimal experiment design problem with mixed-integer convex methods}, series = {22nd International Symposium on Experimental Algorithms (SEA 2024)}, volume = {301}, booktitle = {22nd International Symposium on Experimental Algorithms (SEA 2024)}, doi = {10.4230/LIPIcs.SEA.2024.16}, pages = {16:1 -- 16:22}, abstract = {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.}, language = {en} }