TY - JOUR A1 - Hendrych, Deborah A1 - Troppens, Hannah A1 - Besançon, Mathieu A1 - Pokutta, Sebastian T1 - Convex mixed-integer optimization with Frank-Wolfe methods JF - Mathematical Programming Computation Y1 - 2025 U6 - https://doi.org/10.1007/s12532-025-00288-w VL - 17 SP - 731 EP - 757 ER - TY - CHAP A1 - Hendrych, Deborah A1 - Besançon, Mathieu A1 - Martínez-Rubio, David A1 - Pokutta, Sebastian T1 - Secant line search for Frank-Wolfe algorithms T2 - Proceedings of the 42nd International Conference on Machine Learning Y1 - 2025 UR - https://raw.githubusercontent.com/mlresearch/v267/main/assets/hendrych25a/hendrych25a.pdf VL - 267 SP - 23005 EP - 23029 ER - TY - CHAP A1 - Pauls, Jan A1 - Zimmer, Max A1 - Turan, Berkant A1 - Saatchi, Sassan A1 - Ciais, Philippe A1 - Pokutta, Sebastian A1 - Gieseke, Fabian T1 - Capturing Temporal Dynamics in Large-Scale Canopy Tree Height Estimation T2 - Proceedings of the 42nd International Conference on Machine Learning Y1 - 2025 UR - https://raw.githubusercontent.com/mlresearch/v267/main/assets/pauls25a/pauls25a.pdf VL - 267 SP - 48422 EP - 48438 ER - TY - CHAP A1 - Mundinger, Konrad A1 - Zimmer, Max A1 - Kiem, Aldo A1 - Spiegel, Christoph A1 - Pokutta, Sebastian T1 - Neural Discovery in Mathematics: Do Machines Dream of Colored Planes? T2 - Proceedings of the 42nd International Conference on Machine Learning Y1 - 2025 UR - https://raw.githubusercontent.com/mlresearch/v267/main/assets/mundinger25a/mundinger25a.pdf VL - 267 SP - 45236 EP - 45255 ER - TY - CHAP A1 - Pelleriti, Nico A1 - Zimmer, Max A1 - Wirth, Elias A1 - Pokutta, Sebastian T1 - Approximating Latent Manifolds in Neural Networks via Vanishing Ideals T2 - Proceedings of the 42nd International Conference on Machine Learning Y1 - 2025 UR - https://raw.githubusercontent.com/mlresearch/v267/main/assets/pelleriti25a/pelleriti25a.pdf VL - 267 SP - 48734 EP - 48761 ER - TY - CHAP A1 - Roux, Christophe A1 - Martínez-Rubio, David A1 - Pokutta, Sebastian T1 - Implicit Riemannian optimism with applications to min-max problems T2 - Proceedings of the 42nd International Conference on Machine Learning Y1 - 2025 UR - https://raw.githubusercontent.com/mlresearch/v267/main/assets/roux25a/roux25a.pdf VL - 267 SP - 52139 EP - 52172 ER - TY - CHAP A1 - Turan, Berkant A1 - Asadulla, Suhrab A1 - Steinmann, David A1 - Stammer, Wolfgang A1 - Pokutta, Sebastian T1 - Neural Concept Verifier: Scaling Prover-Verifier Games via Concept Encodings T2 - Proceedings of the ICML Workshop on Actionable Interpretability Y1 - 2025 ER - TY - JOUR A1 - Carderera, Alejandro A1 - Besançon, Mathieu A1 - Pokutta, Sebastian T1 - Scalable Frank-Wolfe on generalized self-concordant functions via simple steps JF - SIAM Journal on Optimization Y1 - 2024 U6 - https://doi.org/10.1137/23M1616789 VL - 34 IS - 3 ER - TY - JOUR A1 - Parczyk, Olaf A1 - Pokutta, Sebastian A1 - Spiegel, Christoph A1 - Szabó, Tibor T1 - New Ramsey multiplicity bounds and search heuristics JF - Foundations of Computational Mathematics Y1 - 2024 U6 - https://doi.org/10.1007/s10208-024-09675-6 ER - TY - CHAP A1 - Pauls, Jan A1 - Zimmer, Max A1 - Kelly, Una M A1 - Schwartz, Martin A1 - Saatchi, Sassan A1 - Ciais, Philippe A1 - Pokutta, Sebastian A1 - Brandt, Martin A1 - Gieseke, Fabian T1 - Estimating canopy height at scale T2 - Proceedings of the 41st International Conference on Machine Learning N2 - We propose a framework for global-scale canopy height estimation based on satellite data. Our model leverages advanced data preprocessing techniques, resorts to a novel loss function designed to counter geolocation inaccuracies inherent in the ground-truth height measurements, and employs data from the Shuttle Radar Topography Mission to effectively filter out erroneous labels in mountainous regions, enhancing the reliability of our predictions in those areas. A comparison between predictions and ground-truth labels yields an MAE/RMSE of 2.43 / 4.73 (meters) overall and 4.45 / 6.72 (meters) for trees taller than five meters, which depicts a substantial improvement compared to existing global-scale products. The resulting height map as well as the underlying framework will facilitate and enhance ecological analyses at a global scale, including, but not limited to, large-scale forest and biomass monitoring. Y1 - 2024 UR - https://raw.githubusercontent.com/mlresearch/v235/main/assets/pauls24a/pauls24a.pdf VL - 235 SP - 39972 EP - 39988 ER - TY - CHAP A1 - Hendrych, Deborah A1 - Besançon, Mathieu A1 - Pokutta, Sebastian T1 - Solving the optimal experiment design problem with mixed-integer convex methods T2 - 22nd International Symposium on Experimental Algorithms (SEA 2024) N2 - 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. Y1 - 2024 U6 - https://doi.org/10.4230/LIPIcs.SEA.2024.16 VL - 301 SP - 16:1 EP - 16:22 ER - TY - CHAP A1 - Kiem, Aldo A1 - Pokutta, Sebastian A1 - Spiegel, Christoph T1 - Categorification of Flag Algebras T2 - Discrete Mathematics Days 2024 Y1 - 2024 U6 - https://doi.org/10.37536/TYSP5643 SP - 259 EP - 264 ER - TY - CHAP A1 - Kiem, Aldo A1 - Pokutta, Sebastian A1 - Spiegel, Christoph T1 - The Four-Color Ramsey Multiplicity of Triangles T2 - Discrete Mathematics Days 2024 Y1 - 2024 U6 - https://doi.org/10.37536/TYSP5643 SP - 13 EP - 18 ER - TY - JOUR A1 - Mundinger, Konrad A1 - Pokutta, Sebastian A1 - Spiegel, Christoph A1 - Zimmer, Max T1 - Extending the Continuum of Six-Colorings JF - Geombinatorics Quarterly Y1 - 2024 VL - 34 IS - 1 SP - 20 EP - 29 ER - TY - CHAP A1 - Mundinger, Konrad A1 - Pokutta, Sebastian A1 - Spiegel, Christoph A1 - Zimmer, Max T1 - Extending the Continuum of Six-Colorings T2 - Discrete Mathematics Days 2024 Y1 - 2024 U6 - https://doi.org/10.37536/TYSP5643 SP - 178 EP - 183 ER - TY - CHAP A1 - Martínez-Rubio, David A1 - Roux, Christophe A1 - Pokutta, Sebastian T1 - Convergence and Trade-Offs in Riemannian Gradient Descent and Riemannian Proximal Point T2 - Proceedings of the 41st International Conference on Machine Learning N2 - In this work, we analyze two of the most fundamental algorithms in geodesically convex optimization: Riemannian gradient descent and (possibly inexact) Riemannian proximal point. We quantify their rates of convergence and produce different variants with several trade-offs. Crucially, we show the iterates naturally stay in a ball around an optimizer, of radius depending on the initial distance and, in some cases, on the curvature. Previous works simply assumed bounded iterates, resulting in rates that were not fully quantified. We also provide an implementable inexact proximal point algorithm and prove several new useful properties of Riemannian proximal methods: they work when positive curvature is present, the proximal operator does not move points away from any optimizer, and we quantify the smoothness of its induced Moreau envelope. Further, we explore beyond our theory with empirical tests. Y1 - 2024 UR - https://raw.githubusercontent.com/mlresearch/v235/main/assets/marti-nez-rubio24a/marti-nez-rubio24a.pdf VL - 235 SP - 34920 EP - 34948 ER - TY - JOUR A1 - Deza, Antoine A1 - Pokutta, Sebastian A1 - Pournin, Lionel T1 - The complexity of geometric scaling JF - Operations Research Letters Y1 - 2024 U6 - https://doi.org/10.1016/j.orl.2023.11.010 VL - 52 SP - 107057 ER - TY - JOUR A1 - Pokutta, Sebastian T1 - The Frank-Wolfe algorithm: a short introduction JF - Jahresbericht der Deutschen Mathematiker-Vereinigung Y1 - 2024 U6 - https://doi.org/10.1365/s13291-023-00275-x VL - 126 SP - 3 EP - 35 ER - TY - CHAP A1 - Wäldchen, Stephan A1 - Sharma, Kartikey A1 - Turan, Berkant A1 - Zimmer, Max A1 - Pokutta, Sebastian T1 - Interpretability Guarantees with Merlin-Arthur Classifiers T2 - Proceedings of The 27th International Conference on Artificial Intelligence and Statistics N2 - 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. Y1 - 2024 UR - https://proceedings.mlr.press/v238/waldchen24a/waldchen24a.pdf VL - 238 SP - 1963 EP - 1971 ER - TY - CHAP A1 - Zimmer, Max A1 - Spiegel, Christoph A1 - Pokutta, Sebastian T1 - Sparse Model Soups T2 - 12th International Conference on Learning Representations (ICLR 2024) Y1 - 2024 SN - 9781713898658 PB - Curran Associates, Inc. ER - TY - JOUR A1 - Stengl, Steven-Marian A1 - Gelß, Patrick A1 - Klus, Stefan A1 - Pokutta, Sebastian T1 - Existence and uniqueness of solutions of the Koopman--von Neumann equation on bounded domains JF - Journal of Physics A: Mathematical and Theoretical Y1 - 2024 U6 - https://doi.org/10.1088/1751-8121/ad6f7d VL - 57 IS - 39 ER - TY - JOUR A1 - Deza, Antoine A1 - Onn, Shmuel A1 - Pokutta, Sebastian A1 - Pournin, Lionel T1 - Kissing polytopes JF - SIAM Journal on Discrete Mathematics N2 - We investigate the following question: How close can two disjoint lattice polytopes contained in a fixed hypercube be? This question stems from various contexts where the minimal distance between such polytopes appears in complexity bounds of optimization algorithms. We provide nearly matching bounds on this distance and discuss its exact computation. We also give similar bounds for disjoint rational polytopes whose binary encoding length is prescribed. Y1 - 2024 U6 - https://doi.org/10.1137/24M1640859 VL - 38 IS - 4 ER - TY - JOUR A1 - Kerdreux, Thomas A1 - d'Aspremont, Alexandre A1 - Pokutta, Sebastian T1 - Restarting Frank-Wolfe: Faster Rates under Hölderian Error Bounds JF - Journal of Optimization Theory and Applications Y1 - 2022 ER - TY - JOUR A1 - Combettes, Cyrille A1 - Pokutta, Sebastian T1 - Revisiting the Approximate Carathéodory Problem via the Frank-Wolfe Algorithm JF - Mathematical Programming A Y1 - 2023 U6 - https://doi.org/10.1007/s10107-021-01735-x VL - 197 SP - 191 EP - 214 ER - TY - JOUR A1 - Vu‐Han, Tu‐Lan A1 - Sunkara, Vikram A1 - Bermudez‐Schettino, Rodrigo A1 - Schwechten, Jakob A1 - Runge, Robin A1 - Perka, Carsten A1 - Winkler, Tobias A1 - Pokutta, Sebastian A1 - Weiß, Claudia A1 - Pumberger, Matthias T1 - Feature Engineering for the Prediction of Scoliosis in 5q‐Spinal Muscular Atrophy JF - Journal of Cachexia, Sarcopenia and Muscle Y1 - 2025 U6 - https://doi.org/10.1002/jcsm.13599 VL - 16 IS - 1 SP - e13599 ER - TY - CHAP A1 - Troppens, Hannah A1 - Besançon, Mathieu A1 - Wilken, St. Elmo A1 - Pokutta, Sebastian T1 - Mixed-Integer Optimization for Loopless Flux Distributions in Metabolic Networks T2 - 23rd International Symposium on Experimental Algorithms (SEA 2025) Y1 - 2025 U6 - https://doi.org/10.4230/LIPIcs.SEA.2025.26 VL - 338 SP - 26:1 EP - 26:18 PB - Schloss Dagstuhl – Leibniz-Zentrum für Informatik ER - TY - CHAP A1 - Głuch, Grzegorz A1 - Turan, Berkant A1 - Nagarajan, Sai Ganesh A1 - Pokutta, Sebastian T1 - The good, the bad and the ugly: watermarks, transferable attacks and adversarial defenses T2 - 1st Workshop on GenAI Watermarking, collocated with ICLR 2025 Y1 - 2025 UR - https://openreview.net/pdf?id=rUs5ryYqZe ER - TY - CHAP A1 - Besançon, Mathieu A1 - Pokutta, Sebastian A1 - Wirth, Elias T1 - The Pivoting Framework: Frank-Wolfe Algorithms with Active Set Size Control T2 - Proceedings of The 28th International Conference on Artificial Intelligence and Statistics Y1 - 2025 UR - https://raw.githubusercontent.com/mlresearch/v258/main/assets/besancon25a/besancon25a.pdf VL - 258 SP - 271 EP - 279 ER - TY - CHAP A1 - Martínez-Rubio, David A1 - Roux, Christophe A1 - Criscitiello, Christopher A1 - Pokutta, Sebastian T1 - Accelerated Methods for Riemannian Min-Max Optimization Ensuring Bounded Geometric Penalties T2 - Proceedings of The 28th International Conference on Artificial Intelligence and Statistics Y1 - 2025 UR - https://raw.githubusercontent.com/mlresearch/v258/main/assets/martinez-rubio25a/martinez-rubio25a.pdf VL - 258 SP - 280 EP - 288 ER - TY - CHAP A1 - Sadiku, Shpresim A1 - Wagner, Moritz A1 - Pokutta, Sebastian T1 - GSE: Group-wise sparse and explainable adversarial attacks T2 - 13th International Conference on Learning Representations (ICLR 2025) Y1 - 2025 UR - https://openreview.net/pdf?id=d54fIsAbff ER - TY - JOUR A1 - Wirth, Elias A1 - Pena, Javier A1 - Pokutta, Sebastian T1 - Correction: Accelerated affine-invariant convergence rates of the Frank-Wolfe algorithm with open-loop step-sizes JF - Mathematical Programming Y1 - 2025 U6 - https://doi.org/10.1007/s10107-025-02214-3 VL - 214 SP - 941 EP - 942 ER - TY - CHAP A1 - Roux, Christophe A1 - Zimmer, Max A1 - Pokutta, Sebastian T1 - On the byzantine-resilience of distillation-based federated learning T2 - 13th International Conference on Learning Representations (ICLR 2025) N2 - Federated Learning (FL) algorithms using Knowledge Distillation (KD) have received increasing attention due to their favorable properties with respect to privacy, non-i.i.d. data and communication cost. These methods depart from transmitting model parameters and instead communicate information about a learning task by sharing predictions on a public dataset. In this work, we study the performance of such approaches in the byzantine setting, where a subset of the clients act in an adversarial manner aiming to disrupt the learning process. We show that KD-based FL algorithms are remarkably resilient and analyze how byzantine clients can influence the learning process. Based on these insights, we introduce two new byzantine attacks and demonstrate their ability to break existing byzantine-resilient methods. Additionally, we propose a novel defence method which enhances the byzantine resilience of KD-based FL algorithms. Finally, we provide a general framework to obfuscate attacks, making them significantly harder to detect, thereby improving their effectiveness. Y1 - 2025 UR - https://openreview.net/pdf?id=of6EuHT7de ER - TY - CHAP A1 - Sadiku, Shpresim A1 - Wagner, Moritz A1 - Nagarajan, Sai Ganesh A1 - Pokutta, Sebastian T1 - S-CFE: Simple Counterfactual Explanations T2 - Proceedings of The 28th International Conference on Artificial Intelligence and Statistics Y1 - 2025 UR - https://raw.githubusercontent.com/mlresearch/v258/main/assets/sadiku25a/sadiku25a.pdf VL - 258 SP - 172 EP - 180 ER - TY - CHAP A1 - Martínez-Rubio, David A1 - Wirth, Elias A1 - Pokutta, Sebastian T1 - Accelerated and Sparse Algorithms for Approximate Personalized PageRank and Beyond T2 - Proceedings of Machine Learning Research N2 - It has recently been shown that ISTA, an unaccelerated optimization method, presents sparse updates for the ℓ1-regularized undirected personalized PageRank problem (Fountoulakis et al., 2019), leading to cheap iteration complexity and providing the same guarantees as the approximate personalized PageRank algorithm (APPR) (Andersen et al., 2006). In this work, we design an accelerated optimization algorithm for this problem that also performs sparse updates, providing an affirmative answer to the COLT 2022 open question of Fountoulakis and Yang (2022). Acceleration provides a reduced dependence on the condition number, while the dependence on the sparsity in our updates differs from the ISTA approach. Further, we design another algorithm by using conjugate directions to achieve an exact solution while exploiting sparsity. Both algorithms lead to faster convergence for certain parameter regimes. Our findings apply beyond PageRank and work for any quadratic objective whose Hessian is a positive-definite 푀-matrix. Y1 - 2023 UR - https://proceedings.mlr.press/v195/martinez-rubio23a/martinez-rubio23a.pdf VL - 195 SP - 1 EP - 35 ER - TY - JOUR A1 - Combettes, Cyrille A1 - Pokutta, Sebastian T1 - Revisiting the Approximate Carathéodory Problem via the Frank-Wolfe Algorithm JF - Mathematical Programming Y1 - 2023 U6 - https://doi.org/10.1007/s10107-021-01735-x VL - 197 SP - 191 EP - 214 ER - TY - CHAP A1 - Zimmer, Max A1 - Spiegel, Christoph A1 - Pokutta, Sebastian ED - Fackeldey, K. T1 - Compression-aware training of neural networks using Frank-Wolfe T2 - Mathematical Optimization for Machine Learning: Proceedings of the MATH+ Thematic Einstein Semester 2023 Y1 - 2025 U6 - https://doi.org/10.1515/9783111376776-010 SP - 137 EP - 168 PB - De Gruyter 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 - CHAP A1 - Carderera, Alejandro A1 - Diakonikolas, Jelena A1 - Lin, Cheuk Yin A1 - Pokutta, Sebastian T1 - Parameter-free Locally Accelerated Conditional Gradients T2 - ICML 2021 N2 - Projection-free conditional gradient (CG) methods are the algorithms of choice for constrained optimization setups in which projections are often computationally prohibitive but linear optimization over the constraint set remains computationally feasible. Unlike in projection-based methods, globally accelerated convergence rates are in general unattainable for CG. However, a very recent work on Locally accelerated CG (LaCG) has demonstrated that local acceleration for CG is possible for many settings of interest. The main downside of LaCG is that it requires knowledge of the smoothness and strong convexity parameters of the objective function. We remove this limitation by introducing a novel, Parameter-Free Locally accelerated CG (PF-LaCG) algorithm, for which we provide rigorous convergence guarantees. Our theoretical results are complemented by numerical experiments, which demonstrate local acceleration and showcase the practical improvements of PF-LaCG over non-accelerated algorithms, both in terms of iteration count and wall-clock time. Y1 - 2021 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 - JOUR A1 - Roux, Christophe A1 - Pokutta, Sebastian A1 - Wirth, Elias A1 - Kerdreux, Thomas T1 - Efficient Online-Bandit Strategies for Minimax Learning Problems N2 - Several learning problems involve solving min-max problems, e.g., empirical distributional robust learning [Namkoong and Duchi, 2016, Curi et al., 2020] or learning with non-standard aggregated losses [Shalev- Shwartz and Wexler, 2016, Fan et al., 2017]. More specifically, these problems are convex-linear problems where the minimization is carried out over the model parameters w ∈ W and the maximization over the empirical distribution p ∈ K of the training set indexes, where K is the simplex or a subset of it. To design efficient methods, we let an online learning algorithm play against a (combinatorial) bandit algorithm. We argue that the efficiency of such approaches critically depends on the structure of K and propose two properties of K that facilitate designing efficient algorithms. We focus on a specific family of sets Sn,k encompassing various learning applications and provide high-probability convergence guarantees to the minimax values. Y1 - 2021 ER - TY - JOUR A1 - Kerdreux, Thomas A1 - Roux, Christophe A1 - d'Aspremont, Alexandre A1 - Pokutta, Sebastian T1 - Linear Bandits on Uniformly Convex Sets JF - Journal of Machine Learning Research N2 - Linear bandit algorithms yield O~(n√T) pseudo-regret bounds on compact convex action sets K⊂Rn and two types of structural assumptions lead to better pseudo-regret bounds. When K is the simplex or an ℓp ball with p∈]1,2], there exist bandits algorithms with O~(√n√T) pseudo-regret bounds. Here, we derive bandit algorithms for some strongly convex sets beyond ℓp balls that enjoy pseudo-regret bounds of O~(√n√T), which answers an open question from [BCB12, §5.5.]. Interestingly, when the action set is uniformly convex but not necessarily strongly convex, we obtain pseudo-regret bounds with a dimension dependency smaller than O(√n). However, this comes at the expense of asymptotic rates in T varying between O(√T) and O(T). Y1 - 2021 UR - https://www.jmlr.org/papers/v22/21-0277.html VL - 22 IS - 284 SP - 1 EP - 23 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 algorithms, the new algorithm 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 - 2021 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 - 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 - Faenza, Yuri A1 - Muñoz, Gonzalo A1 - Pokutta, Sebastian T1 - New Limits of Treewidth-based tractability in Optimization JF - Mathematical Programming Y1 - 2020 U6 - https://doi.org/10.1007/s10107-020-01563-5 N1 - URL of the PDF: http://link.springer.com/article/10.1007/s10107-020-01563-5 N1 - URL of the Abstract: http://www.pokutta.com/blog/research/2018/09/22/treewidth-abstract.html VL - 191 SP - 559 EP - 594 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 -