Sebastian Pokutta
My group is interested in Artificial Intelligence, Optimization, and Machine Learning. We develop new methodologies (e.g., new optimization and learning algorithms), work on combining learning and decision-making, as well as design AI Systems for real-world deployment in various application contexts.
📬 Contact
- office
- Room 3026 at
ZIB
Room MA 606 at TUB - pokutta (at) zib.de
pokutta (at) math.tu-berlin.de - homepage
- pokutta.com
🎓 Curriculum vitae
- since 2019
- Professor at TUB
- since 2019
- Department Head at ZIB
- since 2019
- Vice President at ZIB
- 2005
- Ph.D. in Mathematics at DUE
- 2003
- Diploma in Mathematics at DUE
đź“ť Publications and preprints
Preprints
- Braun, G., Pokutta, S., and Woodstock, Z. (2024). Flexible Block-iterative Analysis for the Frank-Wolfe Algorithm.
[arXiv]
[BibTeX]
- Wirth, E., Pena, J., and Pokutta, S. (2024). Fast Convergence of Frank-Wolfe Algorithms on Polytopes.
[arXiv]
[BibTeX]
- Mundinger, K., Zimmer, M., and Pokutta, S. (2024). Neural Parameter Regression for Explicit Representations of PDE Solution Operators.
[arXiv]
[BibTeX]
- Roux, C., Zimmer, M., and Pokutta, S. (2024). On the Byzantine-resilience of Distillation-based Federated Learning.
[arXiv]
[BibTeX]
- Göß, A., Martin, A., Pokutta, S., and Sharma, K. (2024). Norm-induced Cuts: Optimization with Lipschitzian Black-box Functions.
[URL]
[arXiv]
[BibTeX]
- Wirth, E., Besançon, M., and Pokutta, S. (2024). The Pivoting Framework: Frank-Wolfe Algorithms with Active Set Size Control.
[arXiv]
[BibTeX]
- Wirth, E., Pena, J., and Pokutta, S. (2023). Accelerated Affine-invariant Convergence Rates of the Frank-Wolfe Algorithm with Open-loop Step-sizes.
[arXiv]
[BibTeX]
- Sadiku, S., Wagner, M., and Pokutta, S. (2023). Group-wise Sparse and Explainable Adversarial Attacks.
[arXiv]
[BibTeX]
- MartĂnez-Rubio, D., Roux, C., Criscitiello, C., and Pokutta, S. (2023). Accelerated Riemannian Min-Max Optimization Ensuring Bounded Geometric Penalties.
[arXiv]
[BibTeX]
- Scieur, D., Kerdreux, T., MartĂnez-Rubio, D., d’Aspremont, A., and Pokutta, S. (2023). Strong Convexity of Sets in Riemannian Manifolds.
[arXiv]
[BibTeX]
- Woodstock, Z., and Pokutta, S. (2023). Splitting the Conditional Gradient Algorithm.
[arXiv]
[BibTeX]
- Zimmer, M., Andoni, M., Spiegel, C., and Pokutta, S. (2023). PERP: Rethinking the Prune-Retrain Paradigm in the Era of LLMs.
[arXiv]
[code]
[BibTeX]
- Braun, G., Pokutta, S., and Weismantel, R. (2022). Alternating Linear Minimization: Revisiting von Neumann’s Alternating Projections.
[arXiv]
[slides]
[video]
[BibTeX]
- Braun, G., Carderera, A., Combettes, C., Hassani, H., Karbasi, A., Mokhtari, A., and Pokutta, S. (2022). Conditional Gradient Methods.
[arXiv]
[BibTeX]
- GelĂź, P., Klus, S., Shakibaei, Z., and Pokutta, S. (2022). Low-rank Tensor Decompositions of Quantum Circuits.
[arXiv]
[BibTeX]
- Hendrych, D., Troppens, H., Besançon, M., and Pokutta, S. (2022). Convex Integer Optimization with Frank-Wolfe Methods.
[arXiv]
[slides]
[code]
[BibTeX]
- Zimmer, M., Spiegel, C., and Pokutta, S. (2022). Compression-aware Training of Neural Networks Using Frank-Wolfe.
[arXiv]
[BibTeX]
- Kerdreux, T., d’Aspremont, A., and Pokutta, S. (2021). Local and Global Uniform Convexity Conditions. Preprint.
[arXiv]
[BibTeX]
- Carderera, A., Pokutta, S., Schütte, C., and Weiser, M. (2021). CINDy: Conditional gradient-based Identification of Non-linear Dynamics – Noise-robust recovery. Preprint.
[arXiv]
[summary]
[BibTeX]
- Braun, G., and Pokutta, S. (2021). Dual Prices for Frank–Wolfe Algorithms.
[arXiv]
[BibTeX]
- Roux, C., Wirth, E., Pokutta, S., and Kerdreux, T. (2021). Efficient Online-bandit Strategies for Minimax Learning Problems.
[arXiv]
[BibTeX]
- Combettes, C., Spiegel, C., and Pokutta, S. (2020). Projection-free Adaptive Gradients for Large-scale Optimization.
[arXiv]
[summary]
[code]
[BibTeX]
- Pokutta, S., Spiegel, C., and Zimmer, M. (2020). Deep Neural Network Training with Frank-Wolfe.
[arXiv]
[summary]
[code]
[BibTeX]
- Carderera, A., and Pokutta, S. (2020). Second-order Conditional Gradient Sliding. Preprint.
[arXiv]
[summary]
[code]
[BibTeX]
- Bärmann, A., Martin, A., Pokutta, S., and Schneider, O. (2018). An Online-Learning Approach to Inverse Optimization. Submitted.
[arXiv]
[summary]
[slides]
[BibTeX]
- Braun, G., and Pokutta, S. (2016). An Efficient High-probability Algorithm for Linear Bandits.
[arXiv]
[BibTeX]
- Braun, G., and Pokutta, S. (2015). An Information Diffusion Fano Inequality.
[arXiv]
[BibTeX]
- Designolle, S., VĂ©rtesi, T., and Pokutta, S. Better Bounds on Grothendieck Constants of Finite Orders.
[arXiv]
[BibTeX]
Conference proceedings
- Sharma, K., Hendrych, D., Besançon, M., and Pokutta, S. (2024). Network Design for the Traffic Assignment Problem with Mixed-Integer Frank-Wolfe. Proceedings of INFORMS Optimization Society Conference.
[arXiv]
[BibTeX]
- Pauls, J., Zimmer, M., Kelly, U. M., Schwartz, M., Saatchi, S., Ciais, P., Pokutta, S., Brandt, M., and Gieseke, F. (2024). Estimating Canopy Height at Scale. Proceedings of International Conference on Machine Learning.
[arXiv]
[code]
[BibTeX]
- Hendrych, D., Besançon, M., and Pokutta, S. (2024). Solving the Optimal Experiment Design Problem with Mixed-integer Convex Methods. Proceedings of Symposium on Experimental Algorithms.
DOI: 10.4230/LIPIcs.SEA.2024.16
[arXiv]
[code]
[BibTeX]
- Kiem, A., Pokutta, S., and Spiegel, C. (2024). Categorification of Flag Algebras. Proceedings of Discrete Mathematics Days.
[URL]
[BibTeX]
- Kiem, A., Pokutta, S., and Spiegel, C. (2024). The 4-color Ramsey Multiplicity of Triangles. Proceedings of Discrete Mathematics Days.
[URL]
[arXiv]
[code]
[BibTeX]
- Mundinger, K., Pokutta, S., Spiegel, C., and Zimmer, M. (2024). Extending the Continuum of Six-Colorings. Proceedings of Discrete Mathematics Days.
[URL]
[arXiv]
[BibTeX]
- MartĂnez-Rubio, D., Roux, C., and Pokutta, S. (2024). Convergence and Trade-offs in Riemannian Gradient Descent and Riemannian Proximal Point. Proceedings of International Conference on Machine Learning.
[arXiv]
[BibTeX]
- Wäldchen, S., Sharma, K., Turan, B., Zimmer, M., and Pokutta, S. (2024). Interpretability Guarantees with Merlin-Arthur Classifiers. Proceedings of International Conference on Artificial Intelligence and Statistics.
[arXiv]
[BibTeX]
- Zimmer, M., Spiegel, C., and Pokutta, S. (2024). Sparse Model Soups: A Recipe for Improved Pruning Via Model Averaging. Proceedings of International Conference on Learning Representations.
[URL]
[arXiv]
[BibTeX]
- Chmiela, A., Gleixner, A., Lichocki, P., and Pokutta, S. (2023). Online Learning for Scheduling MIP Heuristics. Proceedings of International Conference on the Integration of Constraint Programming, Artificial Intelligence, and Operations Research, 114–123.
DOI: 10.1007/978-3-031-33271-5_8
[BibTeX]
- Thuerck, D., Sofranac, B., Pfetsch, M., and Pokutta, S. (2023). Learning Cuts Via Enumeration Oracles. Proceedings of Conference on Neural Information Processing Systems.
[arXiv]
[BibTeX]
- MartĂnez-Rubio, D., and Pokutta, S. (2023). Accelerated Riemannian Optimization: Handling Constraints with a Prox to Bound Geometric Penalties. Proceedings of Annual Conference on Learning Theory.
[URL]
[arXiv]
[poster]
[BibTeX]
- MartĂnez-Rubio, D., Wirth, E., and Pokutta, S. (2023). Accelerated and Sparse Algorithms for Approximate Personalized PageRank and Beyond. Proceedings of Annual Conference on Learning Theory.
[arXiv]
[BibTeX]
- Parczyk, O., Pokutta, S., Spiegel, C., and SzabĂł, T. (2023). Fully Computer-assisted Proofs in Extremal Combinatorics. Proceedings of AAAI Conference on Artificial Intelligence.
DOI: 10.1609/aaai.v37i10.26470
[URL]
[arXiv]
[code]
[BibTeX]
- Wirth, E., Kerdreux, T., and Pokutta, S. (2023). Acceleration of Frank-Wolfe Algorithms with Open Loop Step-sizes. Proceedings of International Conference on Artificial Intelligence and Statistics.
[arXiv]
[BibTeX]
- Wirth, E., Kera, H., and Pokutta, S. (2023). Approximate Vanishing Ideal Computations at Scale. Proceedings of International Conference on Learning Representations.
[arXiv]
[slides]
[BibTeX]
- Zimmer, M., Spiegel, C., and Pokutta, S. (2023). How I Learned to Stop Worrying and Love Retraining. Proceedings of International Conference on Learning Representations.
[URL]
[arXiv]
[code]
[BibTeX]
- Gasse, M., Bowly, S., Cappart, Q., Charfreitag, J., Charlin, L., Chételat, D., Chmiela, A., Dumouchelle, J., Gleixner, A., Kazachkov, A. M., Khalil, E., Lichocki, P., Lodi, A., Lubin, M., Maddison, C. J., Christopher, M., Papageorgiou, D. J., Parjadis, A., Pokutta, S., … Kun, M. (2022). The Machine Learning for Combinatorial Optimization Competition (ML4CO): Results and Insights. Proceedings of Conference on Neural Information Processing Systems, 176, 220–231.
[URL]
[arXiv]
[BibTeX]
- Criado, F., MartĂnez-Rubio, D., and Pokutta, S. (2022). Fast Algorithms for Packing Proportional Fairness and Its Dual. Proceedings of Conference on Neural Information Processing Systems.
[arXiv]
[poster]
[BibTeX]
- Macdonald, J., Besançon, M., and Pokutta, S. (2022). Interpretable Neural Networks with Frank-Wolfe: Sparse Relevance Maps and Relevance Orderings. Proceedings of International Conference on Machine Learning.
[arXiv]
[poster]
[video]
[BibTeX]
- Parczyk, O., Pokutta, S., Spiegel, C., and SzabĂł, T. (2022). New Ramsey Multiplicity Bounds and Search Heuristics. Proceedings of Discrete Mathematics Days.
[arXiv]
[code]
[BibTeX]
- Tsuji, K., Tanaka, K., and Pokutta, S. (2022). Pairwise Conditional Gradients without Swap Steps and Sparser Kernel Herding. Proceedings of International Conference on Machine Learning.
[arXiv]
[summary]
[slides]
[code]
[video]
[BibTeX]
- Wäldchen, S., Huber, F., and Pokutta, S. (2022). Training Characteristic Functions with Reinforcement Learning: XAI-methods Play Connect Four. Proceedings of International Conference on Machine Learning.
[arXiv]
[poster]
[video]
[BibTeX]
- Wirth, E., and Pokutta, S. (2022). Conditional Gradients for the Approximately Vanishing Ideal. Proceedings of International Conference on Artificial Intelligence and Statistics.
[arXiv]
[summary]
[poster]
[code]
[BibTeX]
- Carderera, A., Besançon, M., and Pokutta, S. (2021). Simple Steps Are All You Need: Frank-Wolfe and Generalized Self-concordant Functions. Proceedings of Conference on Neural Information Processing Systems, 34, 5390–5401.
[URL]
[summary]
[slides]
[poster]
[code]
[BibTeX]
- Chmiela, A., Khalil, E. B., Gleixner, A., Lodi, A., and Pokutta, S. (2021). Learning to Schedule Heuristics in Branch-and-bound. Proceedings of Conference on Neural Information Processing Systems, 34, 24235–24246.
[URL]
[arXiv]
[poster]
[BibTeX]
- Carderera, A., Diakonikolas, J., Lin, C. Y., and Pokutta, S. (2021). Parameter-free Locally Accelerated Conditional Gradients. Proceedings of ICML.
[arXiv]
[slides]
[BibTeX]
- Sofranac, B., Gleixner, A., and Pokutta, S. (2021). An Algorithm-independent Measure of Progress for Linear Constraint Propagation. Proceedings of International Conference on Principles and Practice of Constraint Programming, 52:1–17.
DOI: 10.4230/LIPIcs.CP.2021.52
[URL]
[arXiv]
[video]
[BibTeX]
- Mortagy, H., Gupta, S., and Pokutta, S. (2020). Walking in the Shadow: A New Perspective on Descent Directions for Constrained Minimization. Proceedings of NeurIPS.
[arXiv]
[slides]
[poster]
[code]
[video]
[BibTeX]
- Combettes, C. W., and Pokutta, S. (2020). Boosting Frank-Wolfe by Chasing Gradients. Proceedings of ICML.
[PDF]
[arXiv]
[summary]
[slides]
[code]
[video]
[BibTeX]
- Sofranac, B., Gleixner, A., and Pokutta, S. (2020). Accelerating Domain Propagation: An Efficient GPU-parallel Algorithm Over Sparse Matrices. Proceedings of 10th IEEE/ACM Workshop on Irregular Applications: Architectures and Algorithms, IA3 2020, 1–11.
DOI: 10.1109/IA351965.2020.00007
[arXiv]
[summary]
[slides]
[video]
[BibTeX]
- Diakonikolas, J., Carderera, A., and Pokutta, S. (2020). Locally Accelerated Conditional Gradients. Proceedings of AISTATS.
[PDF]
[arXiv]
[summary]
[slides]
[code]
[video]
[BibTeX]
- Braun, G., Pokutta, S., Tu, D., and Wright, S. (2019). Blended Conditional Gradients: the Unconditioning of Conditional Gradients. Proceedings of International Conference on Machine Learning, 97, 735–743.
[URL]
[arXiv]
[summary]
[slides]
[poster]
[code]
[BibTeX]
- Diakonikolas, J., Carderera, A., and Pokutta, S. (2019). Breaking the Curse of Dimensionality (Locally) to Accelerate Conditional Gradients. OPTML Workshop Paper.
[PDF]
[arXiv]
[summary]
[slides]
[poster]
[code]
[BibTeX]
- Combettes, C. W., and Pokutta, S. (2019). Blended Matching Pursuit. Proceedings of NeurIPS.
[PDF]
[arXiv]
[summary]
[slides]
[poster]
[code]
[BibTeX]
- Braun, G., Pokutta, S., and Zink, D. (2017). Lazifying Conditional Gradient Algorithms. Proceedings of International Conference on Machine Learning, 70, 566–575.
[URL]
[arXiv]
[slides]
[poster]
[BibTeX]
- Roy, A., Xu, H., and Pokutta, S. (2017). Reinforcement Learning under Model Mismatch. Proceedings of NIPS.
[arXiv]
[BibTeX]
- Bärmann, A., Pokutta, S., and Schneider, O. (2017). Emulating the Expert: Inverse Optimization through Online Learning. Proceedings of the International Conference on Machine Learning (ICML).
[PDF]
[arXiv]
[summary]
[slides]
[poster]
[video]
[BibTeX]
- Braun, G., Pokutta, S., and Roy, A. (2016). Strong Reductions for Extended Formulations. Proceedings of Conference on Integer Programming and Combinatorial Optimization, 9682, 350–361.
DOI: 10.1007/978-3-319-33461-5_29
[arXiv]
[BibTeX]
- Braun, G., Brown-Cohen, J., Huq, A., Pokutta, S., Raghavendra, P., Roy, A., Weitz, B., and Zink, D. (2016). The Matching Problem Has No Small Symmetric SDP. Proceedings of Symposium on Discrete Algorithms, 1067–1078.
DOI: 10.1137/1.9781611974331.ch75
[arXiv]
[BibTeX]
- Roy, A., and Pokutta, S. (2016). Hierarchical Clustering via Spreading Metrics. Proceedings of NIPS.
[URL]
[arXiv]
[BibTeX]
- Braun, G., Pokutta, S., and Zink, D. (2015). Inapproximability of Combinatorial Problems Via Small LPs and SDPs. Proceedings of Annual Symposium on Theory of Computing, 107–116.
DOI: 10.1145/2746539.2746550
[arXiv]
[video]
[BibTeX]
- Braun, G., and Pokutta, S. (2015). The Matching Polytope Does Not Admit Fully-polynomial Size Relaxation Schemes. Proceedings of Symposium on Discrete Algorithms, 837–846.
DOI: 10.1137/1.9781611973730.57
[arXiv]
[BibTeX]
- Braun, G., Firorini, S., and Pokutta, S. (2014). Average Case Polyhedral Complexity of the Maximum Stable Set Problem. Proceedings of Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 28, 515–530.
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2014.515
[URL]
[arXiv]
[BibTeX]
- Braun, G., Pokutta, S., and Xie, Y. (2014). Info-greedy Sequential Adaptive Compressed Sensing. Proceedings of Allerton Conference on Communication, Control, and Computing (Allerton), 858–865.
DOI: 10.1109/ALLERTON.2014.7028544
[arXiv]
[BibTeX]
- Braun, G., and Pokutta, S. (2013). Common Information and Unique Disjointness. Proceedings of Annual Symposium on Foundations of Computer Science, 688–697.
[URL]
[BibTeX]
- Schmaltz, C., Pokutta, S., Heidorn, T., and Andrae, S. (2013). How to make regulators and shareholders happy under Basel III. Proceedings of the 26th Australasian Finance and Banking Conference.
DOI: 10.1016/j.jbankfin.2014.05.031
[URL]
[BibTeX]
- Briët, J., Dadush, D., and Pokutta, S. (2013). On the existence of 0/1 polytopes with high semidefinite extension complexity. Proceedings of ESA.
[arXiv]
[BibTeX]
- Braun, G., and Pokutta, S. (2012). An Algebraic Approach to Symmetric Extended Formulations. Proceedings of International Symposium on Combinatorial Optimization, 7422, 141–152.
DOI: 10.1007/978-3-642-32147-4_14
[arXiv]
[BibTeX]
- Braun, G., Firorini, S., Pokutta, S., and Steurer, D. (2012). Approximation Limits of Linear Programs (beyond Hierarchies). Proceedings of Annual Symposium on Foundations of Computer Science, 480–489.
DOI: 10.1109/FOCS.2012.10
[arXiv]
[BibTeX]
- Braun, G., and Pokutta, S. (2010). Rank of Random Half-integral Polytopes. Proceedings of Electronic Notes in Discrete Mathematics, 36, 415–422.
DOI: 10.1016/j.endm.2010.05.053
[URL]
[BibTeX]
Full articles
- Carderera, A., Besançon, M., and Pokutta, S. (2024). Scalable Frank-Wolfe on Generalized Self-concordant Functions Via Simple Steps. SIAM Journal on Optimization, 34(3), 2231–2258.
DOI: 10.1137/23M1616789
[summary]
[slides]
[poster]
[code]
[BibTeX]
- Braun, G., Guzmán, C., and Pokutta, S. (2024). Corrections to “Lower Bounds on the Oracle Complexity of Nonsmooth Convex Optimization Via Information Theory.” IEEE Transactions on Information Theory, 70, 5408–5409.
DOI: 10.1109/TIT.2024.3357200
[BibTeX]
- Pokutta, S. (2024). The Frank-Wolfe Algorithm: a Short Introduction. Jahresbericht Der Deutschen Mathematiker-Vereinigung, 126(1), 3–35.
DOI: 10.1365/s13291-023-00275-x
[URL]
[arXiv]
[BibTeX]
- Stengl, S.-M., Gelß, P., Klus, S., and Pokutta, S. (2024). Existence and Uniqueness of Solutions of the Koopman–von Neumann Equation on Bounded Domains. Journal of Physics A: Mathematical and Theoretical.
DOI: 10.1088/1751-8121/ad6f7d
[URL]
[arXiv]
[BibTeX]
- Deza, A., Pokutta, S., and Pournin, L. (2024). The Complexity of Geometric Scaling. Operations Research Letters, 52.
DOI: 10.1016/j.orl.2023.11.010
[arXiv]
[BibTeX]
- Deza, A., Onn, S., Pokutta, S., and Pournin, L. (2024). Kissing Polytopes. SIAM Journal on Discrete Mathematics.
[arXiv]
[BibTeX]
- Mundinger, K., Pokutta, S., Spiegel, C., and Zimmer, M. (2024). Extending the Continuum of Six-Colorings. Geombinatorics Quarterly, XXXIV.
[URL]
[arXiv]
[BibTeX]
- Parczyk, O., Pokutta, S., Spiegel, C., and SzabĂł, T. (2024). New Ramsey Multiplicity Bounds and Search Heuristics. Foundations of Computational Mathematics.
DOI: 10.1007/s10208-024-09675-6
[arXiv]
[code]
[BibTeX]
- Designolle, S., VĂ©rtesi, T., and Pokutta, S. (2024). Symmetric Multipartite Bell Inequalities Via Frank-Wolfe Algorithms. Physics Review A.
[arXiv]
[BibTeX]
- Designolle, S., Iommazzo, G., Besançon, M., Knebel, S., Gelß, P., and Pokutta, S. (2023). Improved Local Models and New Bell Inequalities Via Frank-Wolfe Algorithms. Physical Review Research, 5(4).
DOI: 10.1103/PhysRevResearch.5.043059
[arXiv]
[slides]
[code]
[BibTeX]
- Kevin-Martin, A., Bärmann, A., Braun, K., Liers, F., Pokutta, S., Schneider, O., Sharma, K., and Tschuppik, S. (2023). Data-driven Distributionally Robust Optimization Over Time. INFORMS Journal on Optimization.
[arXiv]
[BibTeX]
- Kreimeier, T., Pokutta, S., Walther, A., and Woodstock, Z. (2023). On a Frank-Wolfe Approach for Abs-smooth Functions. Optimization Methods and Software.
[arXiv]
[BibTeX]
- Bienstock, D., Muñoz, G., and Pokutta, S. (2023). Principled Deep Neural Network Training Through Linear Programming. Discrete Optimization.
[URL]
[arXiv]
[summary]
[BibTeX]
- Combettes, C. W., and Pokutta, S. (2023). Revisiting the Approximate Carathéodory Problem via the Frank-Wolfe Algorithm. Mathematical Programming A, 197, 191–214.
DOI: 10.1007/s10107-021-01735-x
[PDF]
[arXiv]
[summary]
[slides]
[code]
[video]
[BibTeX]
- Besançon, M., Carderera, A., and Pokutta, S. (2022). FrankWolfe.jl: A High-Performance and Flexible Toolbox for Frank-Wolfe Algorithms and Conditional Gradients. INFORMS Journal on Computing.
[arXiv]
[summary]
[slides]
[code]
[BibTeX]
- Sofranac, B., Gleixner, A., and Pokutta, S. (2022). Accelerating Domain Propagation: An Efficient GPU-parallel Algorithm Over Sparse Matrices. Parallel Computing, 109, 102874.
DOI: 10.1016/j.parco.2021.102874
[arXiv]
[summary]
[BibTeX]
- Sofranac, B., Gleixner, A., and Pokutta, S. (2022). An Algorithm-independent Measure of Progress for Linear Constraint Propagation. Constraints, 27, 432–455.
DOI: 10.1007/s10601-022-09338-9
[arXiv]
[BibTeX]
- Hunkenschröder, C., Pokutta, S., and Weismantel, R. (2022). Optimizing a Low-dimensional Convex Function Over a High-dimensional Cube. SIAM Journal on Optimization.
[arXiv]
[BibTeX]
- Kossen, T., Hirzel, M. A., Madai, V. I., Boenisch, F., Hennemuth, A., Hildebrand, K., Pokutta, S., Sharma, K., Hilbert, A., Sobesky, J., Galinovic, I., Khalil, A. A., Fiebach, J. B., and Frey, D. (2022). Towards Sharing Brain Images: Differentially Private TOF-MRA Images with Segmentation Labels Using Generative Adversarial Networks. Frontiers in Artificial Intelligence.
DOI: 10.3389/frai.2022.813842
[BibTeX]
- Faenza, Y., Muñoz, G., and Pokutta, S. (2022). New Limits of Treewidth-based tractability in Optimization. Mathematical Programming A, 191, 559–594.
[PDF]
[arXiv]
[summary]
[BibTeX]
- Combettes, C. W., and Pokutta, S. (2021). Complexity of Linear Minimization and Projection on Some Sets. Operations Research Letters, 49(4).
[arXiv]
[code]
[BibTeX]
- Kerdreux, T., Roux, C., d’Aspremont, A., and Pokutta, S. (2021). Linear Bandits on Uniformly Convex Sets. Journal of Machine Learning Research, 22(284), 1–23.
[URL]
[arXiv]
[summary]
[BibTeX]
- Braun, G., Pokutta, S., and Zink, D. (2019). Affine Reductions for LPs and SDPs. Mathematical Programming, 173, 281–312.
DOI: 10.1007/s10107-017-1221-9
[arXiv]
[BibTeX]
- Braun, G., Pokutta, S., and Zink, D. (2019). Lazifying Conditional Gradient Algorithms. The Journal of Machine Learning Research, 20(71), 1–42.
[URL]
[arXiv]
[BibTeX]
- Braun, G., Pokutta, S., and Roy, A. (2018). Strong Reductions for Extended Formulations. Mathematical Programming, 172, 591–620.
DOI: 10.1007/s10107-018-1316-y
[arXiv]
[BibTeX]
- Braun, G., Brown-Cohen, J., Huq, A., Pokutta, S., Raghavendra, P., Roy, A., Weitz, B., and Zink, D. (2017). The Matching Problem Has No Small Symmetric SDP. Mathematical Programming, 165, 643–662.
DOI: 10.1007/s10107-016-1098-z
[arXiv]
[BibTeX]
- Braun, G., Guzmán, C., and Pokutta, S. (2017). Unifying Lower Bounds on the Oracle Complexity of Nonsmooth Convex Optimization. IEEE Transactions on Information Theory, 63(7), 4709–4724.
DOI: 10.1109/TIT.2017.2701343
[arXiv]
[BibTeX]
- Braun, G., Jain, R., Lee, T., and Pokutta, S. (2017). Information-theoretic Approximations of the Nonnegative Rank. Computational Complexity, 26, 147–197.
DOI: 10.1007/s00037-016-0125-z
[URL]
[BibTeX]
- Roy, A., and Pokutta, S. (2017). Hierarchical Clustering via Spreading Metrics. Journal of Machine Learning Research (JMLR), 18, 1–35.
[URL]
[arXiv]
[BibTeX]
- Bodur, M., Del Pia, A., Dey, S. S., Molinaro, M., and Pokutta, S. (2017). Aggregation-based cutting-planes for packing and covering Integer Programs. To Appear in Mathematical Programming A.
DOI: 10.1007/s10107-017-1192-x
[arXiv]
[BibTeX]
- Martin, A., Müller, J., Pape, S., Peter, A., Pokutta, S., and Winter, T. (2017). Pricing and clearing combinatorial markets with singleton and swap orders. Mathematical Methods of Operations Research, 85(2), 155–177.
[arXiv]
[BibTeX]
- Gatzert, N., Pokutta, S., and Vogl, N. (2016+). Convergence of Capital and Insurance Markets: Pricing Aspects of Index-Linked Catastrophic Loss Instruments. To Appear in Journal of Risk and Insurance.
[arXiv]
[BibTeX]
- Braun, G., Firorini, S., and Pokutta, S. (2016). Average Case Polyhedral Complexity of the Maximum Stable Set Problem. Mathematical Programming, 160(1), 407–431.
DOI: 10.1007/s10107-016-0989-3
[arXiv]
[BibTeX]
- Braun, G., and Pokutta, S. (2016). Common Information and Unique Disjointness. Algorithmica, 76(3), 597–629.
DOI: 10.1007/s00453-016-0132-0
[URL]
[BibTeX]
- Braun, G., and Pokutta, S. (2016). A Polyhedral Characterization of Border Bases. SIAM Journal on Discrete Mathematics, 30(1), 239–265.
DOI: 10.1137/140977990
[arXiv]
[BibTeX]
- Bärmann, A., Heidt, A., Martin, A., Pokutta, S., and Thurner, C. (2016). Polyhedral Approximation of Ellipsoidal Uncertainty Sets via Extended Formulations - a computational case study. Computational Management Science, 13(2), 151–193.
[PDF]
[arXiv]
[BibTeX]
- Braun, G., Firorini, S., Pokutta, S., and Steurer, D. (2015). Approximation Limits of Linear Programs (beyond Hierarchies). Mathematics of Operations Research, 40(3), 756–772.
DOI: 10.1287/moor.2014.0694
[arXiv]
[BibTeX]
- Braun, G., Pokutta, S., and Xie, Y. (2015). Info-greedy Sequential Adaptive Compressed Sensing. IEEE Journal of Selected Topics in Signal Processing, 9(4), 601–611.
DOI: 10.1109/JSTSP.2015.2400428
[arXiv]
[BibTeX]
- Briët, J., Dadush, D., and Pokutta, S. (2015). On the existence of 0/1 polytopes with high semidefinite extension complexity. Mathematical Programming B, 153(1), 179–199.
[arXiv]
[BibTeX]
- Braun, G., and Pokutta, S. (2014). A Short Proof for the Polyhedrality of the Chvátal-Gomory Closure of a Compact Convex Set. Operations Research Letters, 42(5), 307–310.
DOI: 10.1016/j.orl.2014.05.004
[arXiv]
[BibTeX]
- Schmaltz, C., Pokutta, S., Heidorn, T., and Andrae, S. (2014). How to make regulators and shareholders happy under Basel III. Journal of Banking and Finance, 311–325.
[PDF]
[arXiv]
[BibTeX]
- Braun, G., and Pokutta, S. (2012). Rigid Abelian Groups and the Probabilistic Method. Contemporary Mathematcs, 576, 17–30.
DOI: 10.1090/conm/576
[arXiv]
[BibTeX]
- Braun, G., and Pokutta, S. (2011). Random Half-integral Polytopes. Operations Research Letters, 39(3), 204–207.
DOI: 10.1016/j.orl.2011.03.003
[URL]
[BibTeX]
🔬 Projects
Preserving forests is crucial for climate adaptation and mitigation. Accurate, up-to-date forest health data is essential. AI4Forest aims to develop advanced AI methods to monitor forests using satellite, radar, and LiDAR data. The project will create scalable techniques for detailed, high-resolution forest maps, updated weekly across Europe and globally.
In this project, we study domain decomposition approaches for optimal control in gas transport networks. Our goal is to couple space-time-domain decomposition with machine learning and mixed-integer programming. We will develop NeTI (Network Tearing and Interconnection), a data-driven and physics-informed algorithm combining mixed-integer nonlinear programming, surrogate model learning, and graph decomposition strategies.
Existing approaches for interpreting Neural Network classifiers that highlight features relevant for a decision are based solely on heuristics. We introduce a theory that allows us to bound the quality of the features without assumptions on the classifier model by relating classification to Interactive Proof Systems.
Motivated by nonsmooth problems in machine learning, we solve the problem of minimizing an abs-smooth function subject to closed convex constraints. New theory and algorithms are developed using linear minimization oracles to enforce constraints and abs-linearization methods to handle nonsmoothness.
We will investigate mixed-integer optimization with convex objectives using error-adaptive convex solvers in branch-and-bound. Focusing on improving lower bounds and balancing computational costs, we aim to develop a faster branch-and-bound methodology by leveraging modern MILP techniques and error-adaptive methods. Key aspects include warm-starting and controlled inexactness in early termination.
We will apply a Frank-Wolfe-based approach for separability certification and entanglement detection of multipartite quantum states. The method will be further exploited to derive entanglement witnesses in the case, often encountered in experiments, of incomplete characterisation of the quantum state.
Formal proof verification can both ensure proof correctness and provide new tools and insights to mathematicians. The goals of this project include creating resources for students and researchers, verifying relevant results, improving proof tactics, and exploring Machine Learning approaches.
This project aims to obtain new bounds in Extremal Combinatorics through an application of flag algebras. The goal is to both improve the underlying computational aspects for existing problems as well as to further develop the theory of flag algebras to extend it to new areas of application.
Computational devices and quantum mechanics revolutionized the 20th century. Quantum computation merges these fields to solve optimization problems faster than classical computers. This project aims to develop new quantum algorithms for general-purpose and specific applications, including optimization, mixed-integer programs, and uses in machine learning, logistics, big data, and physics. We will explore quantum dynamic programming, graph sparsification, and QAOA-type algorithms for small quantum computers.
This project will explore to what extent near-term quantum computing may potentially provide better approximations to combinatorial optimization problems, bringing together expertise from quantum computing and applied mathematics. It is a collaborative effort within the Einstein Research Unit on Quantum Devices, involving the Freie Universität Berlin (FU Berlin), the Weierstrass Institute for Applied Analysis and Stochastics (WIAS), and the Zuse Institute Berlin (ZIB).
Extremal Combinatorics focuses on the maximum or minimum sizes of discrete structures with specific properties, posing significant challenges due to their complexity. Traditional computational approaches often fail due to exponential growth in search spaces, but recent AI advancements, especially in Reinforcement Learning, offer new potential. Applying these AI methods could provide insights into combinatorial problems while also enhancing the understanding of AI techniques in complex, sparse reward environments.
We develop theory and algorithms for 0-1 decision making in optimization problems constrained by partial differential equations. By exploring extended formulations, we achieve new stationarity concepts through sequential exact and approximative relaxation of adjoint-based primal-dual optimality conditions.
MiniMIP is an open source, machine learning oriented Mixed-Integer Programming (MIP) solver. We provide a range of interfaces for all aspects of solving MIPs (e.g. heuristics, cut generators, LP solvers), supplying users with a constant view of the internal state and allowing them to propose modifications that are integrated into the global state internally.
In this project, we study algorithms that promote sparsity. We develop PageRank optimization algorithms that scale with solution sparsity and investigate Riemannian optimization using manifold geometry. Additionally, we develop algorithms for efficient fair resource allocation based on established fairness axioms.
Heuristics play a crucial role in exact solvers for Mixed Integer Programming (MIP). However, the question of how to manage multiple MIP heuristics in a solver has not received sufficient attention. This project addresses the strategic management of primal heuristics in MIP solvers, aiming to replace static, hard-coded rules with dynamic, self-improving procedures.
Deep learning is revolutionizing real-world applications and science, replacing or complementing classical model-based methods in solving mathematical problems. Despite successes, deep neural networks lack strong theoretical-mathematical foundations. This program aims to develop a comprehensive theoretical foundation of deep learning from three perspectives: statistical, application, and mathematical-methodological. The research is interdisciplinary, combining mathematics, statistics, and theoretical computer science to address complex questions.
The performance of modern mixed-integer program solvers is highly dependent on a number of interdependent individual components. Using tools from machine learning, we intend to develop an integrated framework that is able to capture interactions of individual decisions made in these components with the ultimate goal to improve performance.
Worst-case complexity bounds are increasingly insufficient to explain the (often superior) real-world performance of optimization and learning algorithms. We consider data-dependent rates, approximation guarantees, and complexity bounds to provide guarantees much more in line with actual performance.
Airplane data quality is uneven due to varied sources and sensor limitations. This project aims to create data processing services for Component Spotting to help airlines optimize business processes and improve customer satisfaction. We will develop methods for modeling and evaluating data quality, creating a semantic and uniform description for processing models. Using AI algorithms, we will handle inaccuracies and uncertainties to form an analysis-friendly information model.
Training artificial neural networks is a key optimization task in deep learning. To improve generalization, robustness, and explainability, we aim to compute globally optimal solutions. We will use integer programming methods, exploiting mixed-integer nonlinear programming and enhancing solving techniques like spatial branch-and-cut. Additionally, we'll leverage symmetry to reduce computational burden and ensure symmetry in solutions, and incorporate true sparsity using a mixed-integer nonlinear programming framework.
Quantum computing has the potential to occupy an important position in the field of computing in the long term. In the short to medium term, however, we can expect the emergence of so-called "Noisy Intermediate-Scale Quantum algorithms" and "Quantum Approximate Optimization Algorithms" in an initial phase. These algorithms can often solve a special subclass of problems approximately and very quickly using quantum computing and are significantly easier to implement technically. In this pilot project, a workflow will be tested, ranging from the design of hybrid quantum-classical algorithms to their simulation using quantum simulators on HPC hardware.
đź’¬ Talks and posters
Conference and workshop talks
- Jul 2024
- German <-> Japanese Supercomputing - a Success Story
16th JHPCN Symposium, Tokyo [PDF] - Jul 2024
- Extending the Continuum of Six-Colorings
Conference on Discrete Optimization and Machine Learning, Tokyo [PDF] - Jun 2024
- Cargo-Kult Trifft Auf GroĂźe Sprachmodelle: Entmystifizierung von KI?
Lange Nacht Der Wissenschaften, Berlin - Mar 2024
- The Cargo Cult Meets Large Language Models: Demystifying AI Sentiments?
Hong Kong Analytics Community Meeting, Hong Kong - Mar 2024
- Alternating Linear Minimization: Revisiting von Neumann's Alternating Projections
CUHK-Shenzhen Seminar, Shenzhen [PDF]
View More / Less
- Mar 2024
- Conditional Gradients in Machine Learning
International Workshop on Image Processing and Machine Learning, Beijing [PDF] - Feb 2024
- Conditional Gradients in Machine Learning
NUS Math Seminar, Singapore [PDF] - Jan 2024
- The New AI World Order
Conti AI Vision - Nov 2023
- Conditional Gradients in Machine Learning
Workshop on Geometry and Machine Learning, Leipzig [PDF] - Sep 2023
- The Approximate Carathéodory Problem and an Application to Quantum Mechanics
7th Workshop on Future Algorithms and Applications, Berlin - Aug 2023
- Alternating Linear Minimization: Revisiting von Neumann's Alternating Projections
ICIAM 2023 Minisymposium: Advances in Optimization I, Tokyo [PDF] - Aug 2023
- Improved Local Models and New Bell Inequalities Via Frank-Wolfe Algorithms
5th DOxML Conference, Tokyo [PDF] - Jul 2023
- Alternating Linear Minimization: Revisiting von Neumann's Alternating Projections
Jon-Shmuel Halfway to Twelfty [PDF] - Jun 2023
- Möglichkeiten Und Grenzen Künstlicher Intelligenz
Lange Nacht Der Wissenschaften, Berlin - Mar 2023
- Alternating Linear Minimization: Revisiting von Neumann's Alternating Projections
ICERM Workshop: Combinatorics and Optimization, Providence [PDF] - Mar 2023
- Conditional Gradients -- an Overview
2nd Vienna Workshop on Computational Optimization, Vienna [PDF] - Mar 2023
- Alternating Linear Minimization: Revisiting von Neumann's Alternating Projections
Optimization and ML Workshop, Waischenfeld [PDF] - Dec 2022
- Alternating Linear Minimization: Revisiting von Neumann's Alternating Projections
Fields Workshop on Recent Advances in Optimization, Toronto [PDF] - Sep 2022
- Convex Integer Optimization with Frank-Wolfe Methods
Advances in Classical and Quantum Algorithms for Optimization and Machine Learning, Tokyo [PDF] - Jul 2022
- Structured ML Training Via Conditional Gradients
Workshop on Algorithmic Optimization and Data Science, Trier [PDF] - Nov 2021
- Discrete Optimization in Machine Learning - an (informal) Overview
Oberwolfach Workshop on Combinatorial Optimization, Oberwolfach [PDF] - Oct 2021
- Fast Algorithms for 1-fair Packing (and Its Dual)
HIM Workshop: Continuous Approaches to Discrete Optimization, Bonn [PDF] - Apr 2021
- Learning From Little Data
Google University Visit @ TU Berlin [PDF] - Feb 2021
- Structured ML Training Via Conditional Gradients
IPAM Deep Learning and Combinatorial Optimization Workshop [PDF] - Nov 2020
- AI And-for-with-against Humanity?
Human-centric Artificial Intelligence: 2nd French-German-Japanese Symposium [PDF] - Sep 2020
- Restarting Algorithms: Sometimes There Is Free Lunch
CPAIOR 2020 [PDF] - Sep 2020
- Robust ML Training with Conditional Gradients
4th CO@Work, Berlin [PDF] - May 2020
- Beyond Worst-case Rates: Data-dependent Rates in Learning and Optimization
MIP Workshop [PDF] - Mar 2020
- KĂĽnstliche Intelligence Im Arbeitsalltag
Künstliche Intelligenz: Verständlich @ TH Wildau, Wildau [PDF] - Sep 2019
- Smooth Constraint Convex Minimization Via Conditional Gradients
19th French-German-Swiss Conference on Optimization, Nice [PDF] - Sep 2019
- Mirror Descent and Related Methods in Linear and Discrete Optimization
Cargese Workshop on Combinatorial Optimization, Cargese [PDF] - Jan 2019
- Smooth Constraint Convex Minimization Via Conditional Gradients
INFORMS Computing Society Conference, Knoxville [PDF] - Nov 2018
- When the AI God Fails: Recent Adventures in AI Hacking, Security, and Fairness
Hong Kong Analytics Community Meeting, Hong Kong [PDF] - Nov 2018
- Blended Conditional Gradients
Oberwolfach Workshop on Combinatorial Optimization, Oberwolfach [PDF] - Apr 2018
- Emulating the Expert: Inverse Optimization Through Online Learning
Optimization and Discrete Geometry Workshop, Tel Aviv [PDF]
Research seminar talks
- May 2023
- Alternating Linear Minimization: Revisiting von Neumann's Alternating Projections
University of Magdeburg MathCoRe Lecture, Magdeburg [PDF] - Apr 2023
- Conditional Gradients in Machine Learning
Yale Statistics and Data Science Seminar Series, New Haven [PDF] - Mar 2023
- Structured ML Training Via Conditional Gradients
Columbia IEOR Seminar Series, New York [PDF] - Apr 2022
- Conditional Gradients in Machine Learning and Optimization
IST ELLIS Seminar Series, Klosterneuburg [PDF] - Sep 2021
- Conditional Gradients - a Tour D'horizon
AI Campus Berlin Tech Lunch Talk [PDF]
View More / Less
- May 2021
- Conditional Gradients in Machine Learning and Optimization
Math+ Friday Colloquium - Nov 2020
- Conditional Gradients: Overview and Recent Advances
RWTH Aachen Mathematical Colloquium [PDF] - Jul 2019
- Locally Accelerated Conditional Gradients
Research Institute for Mathematical Sciences Seminar, Kyoto University, Kyoto [PDF]