@article{AnariHaghtalabNaoretal.2020, author = {Anari, N. and Haghtalab, N. and Naor, S. and Pokutta, Sebastian and Singh, M. and Torrico, A.}, title = {Structured Robust Submodular Maximization: Offline and Online Algorithms}, journal = {INFORMS Journal on Computing}, arxiv = {http://arxiv.org/abs/1710.04740}, year = {2020}, language = {en} } @inproceedings{CombettesPokutta2020, author = {Combettes, Cyrille W. and Pokutta, Sebastian}, title = {Boosting Frank-Wolfe by Chasing Gradients}, booktitle = {Proceedings of ICML}, arxiv = {http://arxiv.org/abs/2003.06369}, year = {2020}, language = {en} } @inproceedings{MortagyGuptaPokutta2020, author = {Mortagy, Hassan and Gupta, Swati and Pokutta, Sebastian}, title = {Walking in the Shadow: A New Perspective on Descent Directions for Constrained Minimization}, booktitle = {Proceedings of NeurIPS}, arxiv = {http://arxiv.org/abs/2006.08426}, year = {2020}, language = {en} } @inproceedings{Pokutta2020, author = {Pokutta, Sebastian}, title = {Restarting Algorithms: Sometimes there is Free Lunch}, booktitle = {Proceedings of CPAIOR}, arxiv = {http://arxiv.org/abs/2006.14810}, year = {2020}, language = {en} } @article{KossenHirzelMadaietal.2022, author = {Kossen, Tabea and Hirzel, Manuel A. and Madai, Vince I. and Boenisch, Franziska and Hennemuth, Anja and Hildebrand, Kristian and Pokutta, Sebastian and Sharma, Kartikey and Hilbert, Adam and Sobesky, Jan and Galinovic, Ivana and Khalil, Ahmed A. and Fiebach, Jochen B. and Frey, Dietmar}, title = {Towards Sharing Brain Images: Differentially Private TOF-MRA Images with Segmentation Labels Using Generative Adversarial Networks}, journal = {Frontiers in Artificial Intelligence}, doi = {https://doi.org/10.3389/frai.2022.813842}, year = {2022}, abstract = {Sharing labeled data is crucial to acquire large datasets for various Deep Learning applications. In medical imaging, this is often not feasible due to privacy regulations. Whereas anonymization would be a solution, standard techniques have been shown to be partially reversible. Here, synthetic data using a Generative Adversarial Network (GAN) with differential privacy guarantees could be a solution to ensure the patient's privacy while maintaining the predictive properties of the data. In this study, we implemented a Wasserstein GAN (WGAN) with and without differential privacy guarantees to generate privacy-preserving labeled Time-of-Flight Magnetic Resonance Angiography (TOF-MRA) image patches for brain vessel segmentation. The synthesized image-label pairs were used to train a U-net which was evaluated in terms of the segmentation performance on real patient images from two different datasets. Additionally, the Fr{\´e}chet Inception Distance (FID) was calculated between the generated images and the real images to assess their similarity. During the evaluation using the U-Net and the FID, we explored the effect of different levels of privacy which was represented by the parameter ϵ. With stricter privacy guarantees, the segmentation performance and the similarity to the real patient images in terms of FID decreased. Our best segmentation model, trained on synthetic and private data, achieved a Dice Similarity Coefficient (DSC) of 0.75 for ϵ = 7.4 compared to 0.84 for ϵ = ∞ in a brain vessel segmentation paradigm (DSC of 0.69 and 0.88 on the second test set, respectively). We identified a threshold of ϵ <5 for which the performance (DSC <0.61) became unstable and not usable. Our synthesized labeled TOF-MRA images with strict privacy guarantees retained predictive properties necessary for segmenting the brain vessels. Although further research is warranted regarding generalizability to other imaging modalities and performance improvement, our results mark an encouraging first step for privacy-preserving data sharing in medical imaging.}, language = {en} } @inproceedings{WirthPokutta2022, author = {Wirth, Elias and Pokutta, Sebastian}, title = {Conditional Gradients for the Approximately Vanishing Ideal}, volume = {151}, booktitle = {Proceedings of The 25th International Conference on Artificial Intelligence and Statistics}, pages = {2191 -- 2209}, year = {2022}, abstract = {The vanishing ideal of a set of points X is the set of polynomials that evaluate to 0 over all points x in X and admits an efficient representation by a finite set of polynomials called generators. To accommodate the noise in the data set, we introduce the Conditional Gradients Approximately Vanishing Ideal algorithm (CGAVI) for the construction of the set of generators of the approximately vanishing ideal. The constructed set of generators captures polynomial structures in data and gives rise to a feature map that can, for example, be used in combination with a linear classifier for supervised learning. In CGAVI, we construct the set of generators by solving specific instances of (constrained) convex optimization problems with the Pairwise Frank-Wolfe algorithm (PFW). Among other things, the constructed generators inherit the LASSO generalization bound and not only vanish on the training but also on out-sample data. Moreover, CGAVI admits a compact representation of the approximately vanishing ideal by constructing few generators with sparse coefficient vectors.}, language = {en} } @inproceedings{MartinezRubioPokutta2023, author = {Mart{\´i}nez-Rubio, David and Pokutta, Sebastian}, title = {Accelerated Riemannian Optimization: Handling Constraints with a Prox to Bound Geometric Penalties}, volume = {195}, booktitle = {Proceedings of Thirty Sixth Conference on Learning Theory}, pages = {359 -- 393}, year = {2023}, abstract = {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.}, language = {en} } @article{ŠofranacGleixnerPokutta2022, author = {Šofranac, Boro and Gleixner, Ambros and Pokutta, Sebastian}, title = {An Algorithm-independent Measure of Progress for Linear Constraint Propagation}, volume = {27}, journal = {Constraints}, doi = {10.1007/s10601-022-09338-9}, pages = {432 -- 455}, year = {2022}, language = {en} } @inproceedings{ParczykPokuttaSpiegeletal.2022, author = {Parczyk, Olaf and Pokutta, Sebastian and Spiegel, Christoph and Szab{\´o}, Tibor}, title = {New Ramsey Multiplicity Bounds and Search Heuristics}, booktitle = {Discrete Mathematics Days}, year = {2022}, abstract = {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.}, language = {en} } @inproceedings{ParczykPokuttaSpiegeletal.2023, author = {Parczyk, Olaf and Pokutta, Sebastian and Spiegel, Christoph and Szab{\´o}, Tibor}, title = {Fully Computer-assisted Proofs in Extremal Combinatorics}, volume = {37}, booktitle = {Proceedings of the AAAI Conference on Artificial Intelligence}, number = {10}, doi = {10.1609/aaai.v37i10.26470}, pages = {12482 -- 12490}, year = {2023}, abstract = {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.}, language = {en} } @article{HunkenschroederPokuttaWeismantel2022, author = {Hunkenschr{\"o}der, Christoph and Pokutta, Sebastian and Weismantel, Robert}, title = {Optimizing a low-dimensional convex function over a high-dimensional cub}, journal = {SIAM Journal on Optimization}, year = {2022}, language = {en} } @inproceedings{MacDonaldBesanconPokutta2022, author = {MacDonald, Jan and Besan{\c{c}}on, Mathieu and Pokutta, Sebastian}, title = {Interpretable Neural Networks with Frank-Wolfe: Sparse Relevance Maps and Relevance Orderings}, booktitle = {Proceedings of the International Conference on Machine Learning}, year = {2022}, language = {en} } @inproceedings{TsujiTanakaPokutta2022, author = {Tsuji, Kazuma and Tanaka, Ken'ichiro and Pokutta, Sebastian}, title = {Pairwise Conditional Gradients without Swap Steps and Sparser Kernel Herding}, booktitle = {Proceedings of the International Conference on Machine Learning}, year = {2022}, language = {en} } @inproceedings{WaeldchenHuberPokutta2022, author = {W{\"a}ldchen, Stephan and Huber, Felix and Pokutta, Sebastian}, title = {Training Characteristic Functions with Reinforcement Learning: XAI-methods Play Connect Four}, booktitle = {Proceedings of the International Conference on Machine Learning}, year = {2022}, language = {en} } @inproceedings{SharmaHendrychBesanconetal.2024, 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}, booktitle = {Proceedings of INFORMS Optimization Society Conference}, year = {2024}, language = {en} } @article{BraunGuzmanPokutta2024, 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"}, volume = {70}, journal = {IEEE Transactions on Information Theory}, number = {7}, doi = {10.1109/TIT.2024.3357200}, pages = {5408 -- 5409}, year = {2024}, 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} } @article{KreimeierPokuttaWaltheretal., author = {Kreimeier, Timo and Pokutta, Sebastian and Walther, Andrea and Woodstock, Zev}, title = {On a Frank-Wolfe approach for abs-smooth functions}, journal = {Optimization Methods and Software}, doi = {10.1080/10556788.2023.2296985}, language = {en} } @article{HunkenschroederPokuttaWeismantel2022, author = {Hunkenschr{\"o}der, Christoph and Pokutta, Sebastian and Weismantel, Robert}, title = {Optimizing a low-dimensional convex function over a high-dimensional cube}, journal = {SIAM Journal on Optimization}, year = {2022}, language = {en} } @inproceedings{ThuerckSofranacPfetschetal.2023, author = {Thuerck, Daniel and Sofranac, Boro and Pfetsch, Marc and Pokutta, Sebastian}, title = {Learning cuts via enumeration oracles}, booktitle = {Proceedings of Conference on Neural Information Processing Systems}, year = {2023}, language = {en} } @inproceedings{MartinezRubioPokutta2022, author = {Mart{\´i}nez-Rubio, David and Pokutta, Sebastian}, title = {Accelerated Riemannian optimization: Handling constraints with a prox to bound geometric penalties}, booktitle = {Proceedings of Optimization for Machine Learning (NeurIPS Workshop OPT 2022)}, year = {2022}, language = {en} } @inproceedings{MartinezRubioRouxCriscitielloetal.2023, author = {Mart{\´i}nez-Rubio, David and Roux, Christophe and Criscitiello, Christopher and Pokutta, Sebastian}, title = {Accelerated Riemannian Min-Max Optimization Ensuring Bounded Geometric Penalties}, booktitle = {Proceedings of Optimization for Machine Learning (NeurIPS Workshop OPT 2023)}, year = {2023}, language = {en} } @article{DesignolleVertesiPokutta2024, author = {Designolle, S{\´e}bastien and V{\´e}rtesi, Tam{\´a}s and Pokutta, Sebastian}, title = {Symmetric multipartite Bell inequalities via Frank-Wolfe algorithms}, volume = {109}, journal = {Physics Review A}, number = {2}, doi = {10.1103/PhysRevA.109.022205}, year = {2024}, 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} } @inproceedings{ChmielaKhalilGleixneretal.2021, author = {Chmiela, Antonia and Khalil, Elias B. and Gleixner, Ambros and Lodi, Andrea and Pokutta, Sebastian}, title = {Learning to Schedule Heuristics in Branch and Bound}, booktitle = {Thirty-fifth Conference on Neural Information Processing Systems, NeurIPS 2021}, arxiv = {http://arxiv.org/abs/2103.10294}, year = {2021}, abstract = {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.}, language = {en} }