TY - CHAP A1 - Sofranac, Boro A1 - Gleixner, Ambros A1 - Pokutta, Sebastian T1 - An Algorithm-Independent Measure of Progress for Linear Constraint Propagation T2 - 27th International Conference on Principles and Practice of Constraint Programming (CP 2021) N2 - Propagation of linear constraints has become a crucial sub-routine in modern Mixed-Integer Programming (MIP) solvers. In practice, iterative algorithms with tolerance-based stopping criteria are used to avoid problems with slow or infinite convergence. However, these heuristic stopping criteria can pose difficulties for fairly comparing the efficiency of different implementations of iterative propagation algorithms in a real-world setting. Most significantly, the presence of unbounded variable domains in the problem formulation makes it difficult to quantify the relative size of reductions performed on them. In this work, we develop a method to measure -- independently of the algorithmic design -- the progress that a given iterative propagation procedure has made at a given point in time during its execution. Our measure makes it possible to study and better compare the behavior of bounds propagation algorithms for linear constraints. We apply the new measure to answer two questions of practical relevance: (i) We investigate to what extent heuristic stopping criteria can lead to premature termination on real-world MIP instances. (ii) We compare a GPU-parallel propagation algorithm against a sequential state-of-the-art implementation and show that the parallel version is even more competitive in a real-world setting than originally reported. Y1 - 2021 U6 - https://doi.org/10.4230/LIPIcs.CP.2021.52 VL - 210 SP - 52:1 EP - 52:17 ER - TY - CHAP A1 - Sofranac, Boro A1 - Gleixner, Ambros A1 - Pokutta, Sebastian T1 - Accelerating Domain Propagation: an Efficient GPU-Parallel Algorithm over Sparse Matrices T2 - 2020 IEEE/ACM 10th Workshop on Irregular Applications: Architectures and Algorithms (IA3) N2 - Fast domain propagation of linear constraints has become a crucial component of today's best algorithms and solvers for mixed integer programming and pseudo-boolean optimization to achieve peak solving performance. Irregularities in the form of dynamic algorithmic behaviour, dependency structures, and sparsity patterns in the input data make efficient implementations of domain propagation on GPUs and, more generally, on parallel architectures challenging. This is one of the main reasons why domain propagation in state-of-the-art solvers is single thread only. In this paper, we present a new algorithm for domain propagation which (a) avoids these problems and allows for an efficient implementation on GPUs, and is (b) capable of running propagation rounds entirely on the GPU, without any need for synchronization or communication with the CPU. We present extensive computational results which demonstrate the effectiveness of our approach and show that ample speedups are possible on practically relevant problems: on state-of-the-art GPUs, our geometric mean speed-up for reasonably-large instances is around 10x to 20x and can be as high as 195x on favorably-large instances. Y1 - 2020 U6 - https://doi.org/10.1109/IA351965.2020.00007 N1 - URL of the Slides: https://app.box.com/s/qy0pjmhtbm7shk2ypxjxlh2sj4nudvyu N1 - URL of the Abstract: http://www.pokutta.com/blog/research/2020/09/20/gpu-prob.html SP - 1 EP - 11 ER - TY - JOUR A1 - Šofranac, Boro A1 - Gleixner, Ambros A1 - Pokutta, Sebastian T1 - Accelerating domain propagation: An efficient GPU-parallel algorithm over sparse matrices JF - Parallel Computing N2 - • Currently, domain propagation in state-of-the-art MIP solvers is single thread only. • The paper presents a novel, efficient GPU algorithm to perform domain propagation. • Challenges are dynamic algorithmic behavior, dependency structures, sparsity patterns. • The algorithm is capable of running entirely on the GPU with no CPU involvement. • We achieve speed-ups of around 10x to 20x, up to 180x on favorably-large instances. Y1 - 2022 U6 - https://doi.org/10.1016/j.parco.2021.102874 VL - 109 SP - 102874 ER - TY - JOUR A1 - Ramin, Elham A1 - Bestuzheva, Ksenia A1 - Gargalo, Carina A1 - Ramin, Danial A1 - Schneider, Carina A1 - Ramin, Pedram A1 - Flores-Alsina, Xavier A1 - Andersen, Maj M. A1 - Gernaey, Krist V. T1 - Incremental design of water symbiosis networks with prior knowledge: The case of an industrial park in Kenya JF - Science of the Total Environment N2 - Industrial parks have a high potential for recycling and reusing resources such as water across companies by creating symbiosis networks. In this study, we introduce a mathematical optimization framework for the design of water network integration in industrial parks formulated as a large-scale standard mixed-integer non-linear programming (MINLP) problem. The novelty of our approach relies on i) developing a multi-level incremental optimization framework for water network synthesis, ii) including prior knowledge of demand growth and projected water scarcity to evaluate the significance of water-saving solutions, iii) incorporating a comprehensive formulation of water network synthesis problem including multiple pollutants and different treatment units and iv) performing a multi-objective optimization of the network including freshwater savings and relative cost of the network. The significance of the proposed optimization framework is illustrated by applying it to an existing industrial park in a water-scarce region in Kenya. Firstly, we illustrated the benefits of including prior knowledge to prevent an over-design of the network at the early stages. In the case study, we achieved a more flexible and expandable water network with 36% lower unit cost at the early stage and 15% lower unit cost at later stages for the overall maximum freshwater savings of 25%. Secondly, multi-objective analysis suggests an optimum freshwater savings of 14% to reduce the unit cost of network by half. Moreover, the significance of symbiosis networks is highlighted by showing that intra-company connections can only achieve a maximum freshwater savings of 17% with significantly higher unit cost (+45%). Finally, we showed that the values of symbiosis connectivity index in the Pareto front correspond to higher freshwater savings, indicating the significant role of the symbiosis network in the industrial park under study. This is the first study, where all the above elements have been taken into account simultaneously for the design of a water reuse network. Y1 - 2021 U6 - https://doi.org/https://doi.org/10.1016/j.scitotenv.2020.141706 VL - 751 ER - TY - CHAP A1 - Criado, Francisco A1 - Martínez-Rubio, David A1 - Pokutta, Sebastian T1 - Fast Algorithms for Packing Proportional Fairness and its Dual T2 - Proceedings of the Conference on Neural Information Processing Systems N2 - The proportional fair resource allocation problem is a major problem studied in flow control of networks, operations research, and economic theory, where it has found numerous applications. This problem, defined as the constrained maximization of sum_i log x_i, is known as the packing proportional fairness problem when the feasible set is defined by positive linear constraints and x ∈ R≥0. In this work, we present a distributed accelerated first-order method for this problem which improves upon previous approaches. We also design an algorithm for the optimization of its dual problem. Both algorithms are width-independent. Y1 - 2022 VL - 36 ER - TY - JOUR A1 - Kerdreux, Thomas A1 - d'Aspremont, Alexandre A1 - Pokutta, Sebastian T1 - Local and Global Uniform Convexity Conditions N2 - We review various characterizations of uniform convexity and smoothness on norm balls in finite-dimensional spaces and connect results stemming from the geometry of Banach spaces with scaling inequalities used in analysing the convergence of optimization methods. In particular, we establish local versions of these conditions to provide sharper insights on a recent body of complexity results in learning theory, online learning, or offline optimization, which rely on the strong convexity of the feasible set. While they have a significant impact on complexity, these strong convexity or uniform convexity properties of feasible sets are not exploited as thoroughly as their functional counterparts, and this work is an effort to correct this imbalance. We conclude with some practical examples in optimization and machine learning where leveraging these conditions and localized assumptions lead to new complexity results. Y1 - 2021 ER - TY - JOUR A1 - Bärmann, Andreas A1 - Martin, Alexander A1 - Pokutta, Sebastian A1 - Schneider, Oskar T1 - An Online-Learning Approach to Inverse Optimization Y1 - 2018 ER - TY - JOUR A1 - Bienenstock, Daniel A1 - Muñoz, Gonzalo A1 - Pokutta, Sebastian T1 - Principled Deep Neural Network Training through Linear Programming N2 - Deep Learning has received significant attention due to its impressive performance in many state-of-the-art learning tasks. Unfortunately, while very powerful, Deep Learning is not well understood theoretically and in particular only recently results for the complexity of training deep neural networks have been obtained. In this work we show that large classes of deep neural networks with various architectures (e.g., DNNs, CNNs, Binary Neural Networks, and ResNets), activation functions (e.g., ReLUs and leaky ReLUs), and loss functions (e.g., Hinge loss, Euclidean loss, etc) can be trained to near optimality with desired target accuracy using linear programming in time that is exponential in the input data and parameter space dimension and polynomial in the size of the data set; improvements of the dependence in the input dimension are known to be unlikely assuming P≠NP, and improving the dependence on the parameter space dimension remains open. In particular, we obtain polynomial time algorithms for training for a given fixed network architecture. Our work applies more broadly to empirical risk minimization problems which allows us to generalize various previous results and obtain new complexity results for previously unstudied architectures in the proper learning setting. Y1 - 2018 ER - TY - CHAP A1 - Kerdreux, Thomas A1 - d'Aspremont, Alexandre A1 - Pokutta, Sebastian T1 - Projection-Free Optimization on Uniformly Convex Sets T2 - To Appear in Proceedings of AISTATS Y1 - 2020 ER - TY - GEN A1 - Lenz, Ralf A1 - Serrano, Felipe T1 - Tight Convex Relaxations for the Expansion Planning Problem N2 - Secure energy transport is considered as highly relevant for the basic infrastructure of nowadays society and economy. To satisfy increasing demands and to handle more diverse transport situations, operators of energy networks regularly expand the capacity of their network by building new network elements, known as the expansion planning problem. A key constraint function in expansion planning problems is a nonlinear and nonconvex potential loss function. In order to improve the algorithmic performance of state-of-the-art MINLP solvers, this paper presents an algebraic description for the convex envelope of this function. Through a thorough computational study, we show that this tighter relaxation tremendously improve the performance of the MINLP solver SCIP on a large test set of practically relevant instances for the expansion planning problem. In particular, the results show that our achievements lead to an improvement of the solver performance for a development version by up to 58%. T3 - ZIB-Report - 21-05 KW - Convex envelopes KW - Mixed-Integer Nonlinear Programming KW - Expansion planning of energy networks Y1 - 2021 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-81459 SN - 1438-0064 ER - TY - JOUR A1 - Pokutta, Sebastian A1 - Spiegel, Christoph A1 - Zimmer, Max T1 - Deep Neural Network Training with Frank-Wolfe N2 - This paper studies the empirical efficacy and benefits of using projection-free first-order methods in the form of Conditional Gradients, a.k.a. Frank-Wolfe methods, for training Neural Networks with constrained parameters. We draw comparisons both to current state-of-the-art stochastic Gradient Descent methods as well as across different variants of stochastic Conditional Gradients. In particular, we show the general feasibility of training Neural Networks whose parameters are constrained by a convex feasible region using Frank-Wolfe algorithms and compare different stochastic variants. We then show that, by choosing an appropriate region, one can achieve performance exceeding that of unconstrained stochastic Gradient Descent and matching state-of-the-art results relying on L2-regularization. Lastly, we also demonstrate that, besides impacting performance, the particular choice of constraints can have a drastic impact on the learned representations. Y1 - 2020 ER - TY - JOUR A1 - Cryille W., Combettes A1 - Spiegel, Christoph A1 - Pokutta, Sebastian T1 - Projection-Free Adaptive Gradients for Large-Scale Optimization N2 - The complexity in large-scale optimization can lie in both handling the objective function and handling the constraint set. In this respect, stochastic Frank-Wolfe algorithms occupy a unique position as they alleviate both computational burdens, by querying only approximate first-order information from the objective and by maintaining feasibility of the iterates without using projections. In this paper, we improve the quality of their first-order information by blending in adaptive gradients. We derive convergence rates and demonstrate the computational advantage of our method over the state-of-the-art stochastic Frank-Wolfe algorithms on both convex and nonconvex objectives. The experiments further show that our method can improve the performance of adaptive gradient algorithms for constrained optimization. Y1 - 2020 ER - TY - THES A1 - Pedersen, Jaap T1 - Multiperiod Optimal Power Flow Problem In Distribution System Planning N2 - Growing demand, distributed generation, such as renewable energy sources (RES), and the increasing role of storage systems to mitigate the volatility of RES on a medium voltage level, push existing distribution grids to their limits. Therefore, necessary network expansion needs to be evaluated to guarantee a safe and reliable electricity supply in the future taking these challenges into account. This problem is formulated as an optimal power flow (OPF) problem which combines network expansion, volatile generation and storage systems, minimizing network expansion and generation costs. As storage systems introduce a temporal coupling into the system, a multiperiod OPF problem is needed and analysed in this thesis. To reduce complexity, the network expansion problem is represented in a continuous nonlinear programming formulation by using fundamental properties of electrical engeneering. This formulation is validated succesfully against a common mixed integer programming approach on a 30 and 57 bus network with respect to solution and computing time. As the OPF problem is, in general, a nonconvex, nonlinear problem and, thus, hard to solve, convex relaxations of the power flow equations have gained increasing interest. Sufficient conditions are represented which guarantee exactness of a second-order cone (SOC) relaxation of an operational OPF in radial networks. In this thesis, these conditions are enhanced for the network expansion planning problem. Additionally, nonconvexities introduced by the choice of network expansion variables are relaxed by using McCormick envelopes. These relaxations are then applied on the multiperiod OPF and compared to the original problem on a 30 and a 57 bus network. In particular, the computational time is decreased by an order up to 10^2 by the SOC relaxation while it provides either an exact solution or a sufficient lower bound on the original problem. Finally, a sensitivity study is performed on weights of network expansion costs showing strong dependency of both the solution of performed expansion and solution time on the chosen weights. KW - multiperiod optimal power flow, distribution network planning, battery storage Y1 - 2020 ER - TY - GEN A1 - Bestuzheva, Ksenia A1 - Gleixner, Ambros A1 - Vigerske, Stefan T1 - A Computational Study of Perspective Cuts N2 - The benefits of cutting planes based on the perspective function are well known for many specific classes of mixed-integer nonlinear programs with on/off structures. However, we are not aware of any empirical studies that evaluate their applicability and computational impact over large, heterogeneous test sets in general-purpose solvers. This paper provides a detailed computational study of perspective cuts within a linear programming based branch-and-cut solver for general mixed-integer nonlinear programs. Within this study, we extend the applicability of perspective cuts from convex to nonconvex nonlinearities. This generalization is achieved by applying a perspective strengthening to valid linear inequalities which separate solutions of linear relaxations. The resulting method can be applied to any constraint where all variables appearing in nonlinear terms are semi-continuous and depend on at least one common indicator variable. Our computational experiments show that adding perspective cuts for convex constraints yields a consistent improvement of performance, and adding perspective cuts for nonconvex constraints reduces branch-and-bound tree sizes and strengthens the root node relaxation, but has no significant impact on the overall mean time. T3 - ZIB-Report - 21-07 KW - perspective cuts, mixed-integer nonlinear programming, nonconvex optimization, computational study Y1 - 2021 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-81821 SN - 1438-0064 ER - TY - JOUR A1 - Csizmadia, Zsolt A1 - Berthold, Timo T1 - The confined primal integral: a measure to benchmark heuristic MINLP solvers against global MINLP solvers JF - Mathematical Programming N2 - It is a challenging task to fairly compare local solvers and heuristics against each other and against global solvers. How does one weigh a faster termination time against a better quality of the found solution? In this paper, we introduce the confined primal integral, a new performance measure that rewards a balance of speed and solution quality. It emphasizes the early part of the solution process by using an exponential decay. Thereby, it avoids that the order of solvers can be inverted by choosing an arbitrarily large time limit. We provide a closed analytic formula to compute the confined primal integral a posteriori and an incremental update formula to compute it during the run of an algorithm. For the latter, we show that we can drop one of the main assumptions of the primal integral, namely the knowledge of a fixed reference solution to compare against. Furthermore, we prove that the confined primal integral is a transitive measure when comparing local solves with different final solution values. Finally, we present a computational experiment where we compare a local MINLP solver that uses certain classes of cutting planes against a solver that does not. Both versions show very different tendencies w.r.t. average running time and solution quality, and we use the confined primal integral to argue which of the two is the preferred setting. Y1 - 2020 U6 - https://doi.org/10.1007/s10107-020-01547-5 ER - TY - JOUR A1 - Witzig, Jakob A1 - Berthold, Timo T1 - Conflict Analysis for MINLP JF - INFORMS Journal on Computing N2 - The generalization of MIP techniques to deal with nonlinear, potentially non-convex, constraints have been a fruitful direction of research for computational MINLP in the last decade. In this paper, we follow that path in order to extend another essential subroutine of modern MIP solvers towards the case of nonlinear optimization: the analysis of infeasible subproblems for learning additional valid constraints. To this end, we derive two different strategies, geared towards two different solution approaches. These are using local dual proofs of infeasibility for LP-based branch-and-bound and the creation of nonlinear dual proofs for NLP-based branch-and-bound, respectively. We discuss implementation details of both approaches and present an extensive computational study, showing that both techniques can significantly enhance performance when solving MINLPs to global optimality. Y1 - 2021 U6 - https://doi.org/10.1287/ijoc.2020.1050 VL - 33 IS - 2 SP - 421 EP - 435 ER - TY - JOUR A1 - Gamrath, Gerald A1 - Berthold, Timo A1 - Salvagnin, Domenico T1 - An exploratory computational analysis of dual degeneracy in mixed-integer programming JF - EURO Journal on Computational Optimization N2 - Dual degeneracy, i.e., the presence of multiple optimal bases to a linear programming (LP) problem, heavily affects the solution process of mixed integer programming (MIP) solvers. Different optimal bases lead to different cuts being generated, different branching decisions being taken and different solutions being found by primal heuristics. Nevertheless, only a few methods have been published that either avoid or exploit dual degeneracy. The aim of the present paper is to conduct a thorough computational study on the presence of dual degeneracy for the instances of well-known public MIP instance collections. How many instances are affected by dual degeneracy? How degenerate are the affected models? How does branching affect degeneracy: Does it increase or decrease by fixing variables? Can we identify different types of degenerate MIPs? As a tool to answer these questions, we introduce a new measure for dual degeneracy: the variable–constraint ratio of the optimal face. It provides an estimate for the likelihood that a basic variable can be pivoted out of the basis. Furthermore, we study how the so-called cloud intervals—the projections of the optimal face of the LP relaxations onto the individual variables—evolve during tree search and the implications for reducing the set of branching candidates. Y1 - 2020 U6 - https://doi.org/10.1007/s13675-020-00130-z IS - 8 SP - 241 EP - 246 ER - TY - JOUR A1 - Devriendt, Jo A1 - Gleixner, Ambros A1 - Nordström, Jakob T1 - Learn to Relax: Integrating 0-1 Integer Linear Programming with Pseudo-Boolean Conflict-Driven Search JF - Constraints N2 - Conflict-driven pseudo-Boolean solvers optimize 0-1 integer linear programs by extending the conflict-driven clause learning (CDCL) paradigm from SAT solving. Though pseudo-Boolean solvers have the potential to be exponentially more efficient than CDCL solvers in theory, in practice they can sometimes get hopelessly stuck even when the linear programming (LP) relaxation is infeasible over the reals. Inspired by mixed integer programming (MIP), we address this problem by interleaving incremental LP solving with cut generation within the conflict-driven pseudo-Boolean search. This hybrid approach, which for the first time combines MIP techniques with full-blown conflict analysis operating directly on linear inequalities using the cutting planes method, significantly improves performance on a wide range of benchmarks, approaching a "best-of-both-worlds" scenario between SAT-style conflict-driven search and MIP-style branch-and-cut. Y1 - 2021 U6 - https://doi.org/10.1007/s10601-020-09318-x VL - 26 SP - 26 EP - 55 ER - TY - CHAP A1 - Shinano, Yuji A1 - Tateiwa, N. A1 - Nakamura, S. A1 - Yoshida, A. A1 - Yasuda, M. A1 - Kaji, S. A1 - Fujisawa, K. T1 - Massive Parallelization for Finding Shortest Lattice Vectors Based on Ubiquity Generator Framework T2 - 2020 SC20: International Conference for High Performance Computing, Networking, Storage and Analysis (SC) N2 - Lattice-based cryptography has received attention as a next-generation encryption technique, because it is believed to be secure against attacks by classical and quantum computers. Its essential security depends on the hardness of solving the shortest vector problem (SVP). In the cryptography, to determine security levels, it is becoming significantly more important to estimate the hardness of the SVP by high-performance computing. In this study, we develop the world’s first distributed and asynchronous parallel SVP solver, the MAssively Parallel solver for SVP (MAP-SVP). It can parallelize algorithms for solving the SVP by applying the Ubiquity Generator framework, which is a generic framework for branch-and-bound algorithms. The MAP-SVP is suitable for massive-scale parallelization, owing to its small memory footprint, low communication overhead, and rapid checkpoint and restart mechanisms. We demonstrate its performance and scalability of the MAP-SVP by using up to 100,032 cores to solve instances of the Darmstadt SVP Challenge. Y1 - 2020 U6 - https://doi.org/10.1109/SC41405.2020.00064 SP - 834 EP - 848 ER - TY - JOUR A1 - Yokoyama, Ryohei A1 - Shinano, Yuji A1 - Wakayama, Yuki A1 - Wakui, Tetsuya T1 - Model reduction by time aggregation for optimal design of energy supply systems by an MILP hierarchical branch and bound method JF - Energy N2 - Mixed-integer linear programming (MILP) methods have been applied widely to optimal design of energy supply systems in consideration of multi-period operation. A hierarchical MILP method has been proposed to solve such optimal design problems efficiently. An original problem has been solved by dividing it into a relaxed optimal design problem at the upper level and optimal operation problems which are independent of one another at the lower level. In addition, some strategies have been proposed to enhance the computation efficiency furthermore. In this paper, a method of reducing model by time aggregation is proposed as a novel strategy to search design candidates efficiently in the relaxed optimal design problem at the upper level. In addition, the previous strategies are modified in accordance with the novel strategy. This method is realized only by clustering periods and averaging energy demands for clustered periods, while it guarantees to derive the optimal solution. Thus, it may decrease the computation time at the upper level. Through a case study on the optimal design of a gas turbine cogeneration system, it is clarified how the model reduction is effective to enhance the computation efficiency in comparison and combination with the modified previous strategies. Y1 - 2019 U6 - https://doi.org/https://doi.org/10.1016/j.energy.2019.04.066 VL - 181 SP - 782 EP - 792 ER - TY - CHAP A1 - Pfetsch, Marc A1 - Pokutta, Sebastian T1 - IPBoost – Non-Convex Boosting via Integer Programming T2 - Proceedings of ICML Y1 - 2020 N1 - URL of the Code: https://www2.mathematik.tu-darmstadt.de/~pfetsch/ipboost.html N1 - URL of the Slides: https://app.box.com/s/8dpvmls88suouy11bkpwufhu7iiz6dxl N1 - URL of the Abstract: http://www.pokutta.com/blog/research/2020/02/13/ipboost-abstract.html ER - TY - CHAP A1 - Pokutta, Sebastian A1 - Singh, M. A1 - Torrico, A. T1 - On the Unreasonable Effectiveness of the Greedy Algorithm: Greedy Adapts to Sharpness T2 - Proceedings of ICML Y1 - 2020 N1 - URL of the Poster: https://app.box.com/s/24vbh1s2vib11upqyepzen3lzdl13skr N1 - URL of the Slides: https://app.box.com/s/fmjxhfdpiqubm28upf563ohy8t8fgl3a N1 - URL of the Abstract: http://www.pokutta.com/blog/research/2020/06/03/unreasonable-abstract.html N1 - https://www.youtube.com/watch?v=VB1e0HrDmVo ER - TY - CHAP A1 - Diakonikolas, Jelena A1 - Carderera, Alejandro A1 - Pokutta, Sebastian T1 - Locally Accelerated Conditional Gradients T2 - Proceedings of AISTATS Y1 - 2020 N1 - URL of the Code: https://colab.research.google.com/drive/1ejjfCan7xnEhWWJXCIzb03CwQRG9iW_O N1 - URL of the PDF: http://proceedings.mlr.press/v108/diakonikolas20a/diakonikolas20a.pdf N1 - URL of the Slides: https://app.box.com/s/gphkhapso7d1vrfnzqykkb3vx0agxh8w N1 - URL of the Abstract: http://www.pokutta.com/blog/research/2019/07/04/LaCG-abstract.html N1 - https://slideslive.com/38930107/locally-accelerated-conditional-gradients?ref=account-folder-52123-folders ER - TY - JOUR A1 - Anari, N. A1 - Haghtalab, N. A1 - Naor, S. A1 - Pokutta, Sebastian A1 - Singh, M. A1 - Torrico, A. T1 - Structured Robust Submodular Maximization: Offline and Online Algorithms JF - INFORMS Journal on Computing Y1 - 2020 ER - TY - CHAP A1 - Combettes, Cyrille W. A1 - Pokutta, Sebastian T1 - Boosting Frank-Wolfe by Chasing Gradients T2 - Proceedings of ICML Y1 - 2020 N1 - Additional Note: github code: https://github.com/cyrillewcombettes/boostfw N1 - URL of the Code: https://colab.research.google.com/drive/1TSOVjDFF1X2ADBo_adHLsUVrblSutRKw N1 - URL of the Slides: https://app.box.com/s/wwj247r5d456q0778p9b9y1jm6txuifb N1 - URL of the Abstract: http://www.pokutta.com/blog/research/2020/03/16/boostFW.html N1 - https://www.youtube.com/watch?v=BfyV0C5FRbE ER - TY - CHAP A1 - Mortagy, Hassan A1 - Gupta, Swati A1 - Pokutta, Sebastian T1 - Walking in the Shadow: A New Perspective on Descent Directions for Constrained Minimization T2 - Proceedings of NeurIPS Y1 - 2020 N1 - URL of the Code: https://github.com/pokutta/Walking-in-the-Shadow N1 - URL of the Poster: https://app.box.com/s/y266djezdjdidsswaopvdcnsnkp8774i N1 - URL of the Slides: https://app.box.com/s/wjhpe4nh8kv5pw6vl5jbp902v3mksivs ER - TY - CHAP A1 - Pokutta, Sebastian T1 - Restarting Algorithms: Sometimes there is Free Lunch T2 - Proceedings of CPAIOR Y1 - 2020 N1 - URL of the Slides: https://app.box.com/s/8ps8bhjv2phhy182xn55iurk9t3o1xc3 N1 - https://www.youtube.com/watch?v=v3Xzoda2_gQ ER - TY - JOUR A1 - Kossen, Tabea A1 - Hirzel, Manuel A. A1 - Madai, Vince I. A1 - Boenisch, Franziska A1 - Hennemuth, Anja A1 - Hildebrand, Kristian A1 - Pokutta, Sebastian A1 - Sharma, Kartikey A1 - Hilbert, Adam A1 - Sobesky, Jan A1 - Galinovic, Ivana A1 - Khalil, Ahmed A. A1 - Fiebach, Jochen B. A1 - Frey, Dietmar T1 - Towards Sharing Brain Images: Differentially Private TOF-MRA Images with Segmentation Labels Using Generative Adversarial Networks JF - Frontiers in Artificial Intelligence N2 - 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é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. Y1 - 2022 U6 - https://doi.org/https://doi.org/10.3389/frai.2022.813842 ER - TY - CHAP A1 - Wirth, Elias A1 - Pokutta, Sebastian T1 - Conditional Gradients for the Approximately Vanishing Ideal T2 - Proceedings of The 25th International Conference on Artificial Intelligence and Statistics N2 - 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. Y1 - 2022 UR - https://proceedings.mlr.press/v151/wirth22a.html VL - 151 SP - 2191 EP - 2209 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 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 - Kamčev, Nina A1 - Spiegel, Christoph T1 - Another note on intervals in the Hales-Jewett theorem JF - Electronic Journal of Combinatorics N2 - The Hales-Jewett Theorem states that any r-colouring of [m]ⁿ contains a monochromatic combinatorial line if n is large enough. Shelah's proof of the theorem implies that for m = 3 there always exists a monochromatic combinatorial line whose set of active coordinates is the union of at most r intervals. For odd r, Conlon and Kamčev constructed r–colourings for which it cannot be fewer than r intervals. However, we show that for even r and large n, any r–colouring of [3]ⁿ contains a monochromatic combinatorial line whose set of active coordinates is the union of at most r−1 intervals. This is optimal and extends a result of Leader and Räty for r=2. Y1 - 2022 U6 - https://doi.org/10.37236/6730 VL - 29 IS - 1 SP - P1.62 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 -