Header Image

Continuous Optimization

conditional gradient algorithms; non-smooth optimization; block-iterative and distributed optimization algorithms; accelerated methods; online learning algorithms

13
5
50

What we are interested in

We research and develop algorithms for continuous optimization, with a particular emphasis on solving high-dimensional optimization problems with first-order methods. We prove convergence rates and guarantees for a variety of settings, such as: Conditional gradient aka Frank-Wolfe methods, which perform constrained optimization by accessing the feasible set via a linear optimization oracle. Proximal methods, which yield efficient algorithms for nonsmooth optimization and practically reshape smooth ones. Online learning algorithms which consist of playing a sequential game in which the algorithms predict and receive a loss in an online way and try to minimize overall regret; they have numerous applications to optimization via reductions. Accelerated methods which combine online learning tools with other optimization techniques to exploit and improve convergence of other more simple algorithms, often to optimality. And block-iterative algorithms which leverage parallelism and distributed computation for faster algorithmic performance.

🧑‍🎓 Members

Sebastian Pokutta
Department Head
pokutta (at) zib.de
David MartĂ­nez-Rubio
Research Area Lead
martinez-rubio (at) zib.de
Zev Woodstock
Research Area Lead
woodstock (at) zib.de
Gábor Braun
braun (at) zib.de
Christophe Roux
roux (at) zib.de
Elias Wirth
wirth (at) zib.de
Jannis Halbey
halbey (at) zib.de
Gabriele Iommazzo
iommazzo (at) zib.de
Deborah Hendrych
hendrych (at) zib.de
Garam Kim
garam (at) zib.de
Dominik Kuzinowicz
kuzinowicz (at) zib.de
Saurabh Srivastava
srivastava (at) zib.de

🔬 Projects

On a Frank-Wolfe Approach for Abs-smooth Optimization

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.

MATH+ EF1-23
Apr 2023 to Mar 2026
4
2
Convex Solver Adaptivity for Mixed-integer Optimization

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.

MATH+ AA3-15
Apr 2023 to Mar 2026
4
2
Decision-making for Energy Network Dynamics

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.

MATH+ AA4-7
Jun 2021 to May 2024
4
Sparsity and Sample-size Efficiency in Structured Learning

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.

MATH+ AA5-1
Jan 2022 to Dec 2023
2
7
Beyond the Worst-case: Data-dependent Rates in Learning and Optimization

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.

MATH+ AA3-7
Jan 2021 to Dec 2022
2
1

đź’¬ Talks and posters

Conference and workshop talks

Nov 2023
Bounding Geometric Penalties in First-order Riemannian Optimization by Christophe Roux
Seminar "Modern Methods in Applied Stochastics and Nonparametric Statistics", Berlin

đź“ť Publications and preprints

  1. 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]
    @article{CBP2021,
  year = {2024},
  journal = {SIAM Journal on Optimization},
  month = sep,
  volume = {34},
  number = {3},
  pages = {2231-2258},
  doi = {10.1137/23M1616789},
  author = {Carderera, Alejandro and Besançon, Mathieu and Pokutta, Sebastian},
  title = {Scalable Frank-Wolfe on Generalized Self-concordant Functions Via Simple Steps},
  code = {https://doi.org/10.5281/zenodo.4836009},
  poster = {https://pokutta.com/slides/20211120_poster_NeurIPS21_lSimple_steps_are_all_you_need.pdf},
  slides = {https://pokutta.com/slides/20210710_FW-simpleSteps-SelfConcordance.pdf},
  summary = {https://pokutta.com/blog/research/2021/10/09/self-concordant-abstract.html}
}
  2. 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]
    @article{Braun2013lowerCO_corr,
  year = {2024},
  journal = {IEEE Transactions on Information Theory},
  month = jul,
  volume = {70},
  pages = {5408-5409},
  doi = {10.1109/TIT.2024.3357200},
  author = {Braun, Gábor and Guzmán, Cristóbal and Pokutta, Sebastian},
  title = {Corrections to “Lower Bounds on the Oracle Complexity of Nonsmooth Convex Optimization Via Information Theory”}
}
  3. Deza, A., Onn, S., Pokutta, S., and Pournin, L. (2024). Kissing Polytopes. SIAM Journal on Discrete Mathematics. [arXiv]
    [BibTeX]
    @article{kissing_polytopes_2023,
  year = {2024},
  journal = {SIAM Journal on Discrete Mathematics},
  archiveprefix = {arXiv},
  eprint = {2305.18597},
  primaryclass = {math.MG},
  author = {Deza, Antoine and Onn, Shmuel and Pokutta, Sebastian and Pournin, Lionel},
  title = {Kissing Polytopes}
}
  4. 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]
    @inproceedings{mrp_tradeoffs_riemannian_gradient_descent_23,
  year = {2024},
  booktitle = {Proceedings of International Conference on Machine Learning},
  archiveprefix = {arXiv},
  eprint = {2403.10429},
  primaryclass = {math.OC},
  author = {MartĂ­nez-Rubio, David and Roux, Christophe and Pokutta, Sebastian},
  title = {Convergence and Trade-offs in Riemannian Gradient Descent and Riemannian Proximal Point}
}
  5. Besançon, M., Garcia, J. D., Legat, B., and Sharma, A. (2023). Flexible Differentiable Optimization Via Model Transformations. INFORMS Journal on Computing. DOI: 10.1287/ijoc.2022.0283 [URL] [arXiv]
    [BibTeX]
    @article{diffopt_23,
  year = {2023},
  journal = {INFORMS Journal on Computing},
  month = aug,
  doi = {10.1287/ijoc.2022.0283},
  url = {https://pubsonline.informs.org/doi/epdf/10.1287/ijoc.2022.0283},
  archiveprefix = {arXiv},
  eprint = {2206.06135},
  primaryclass = {cs.LG},
  author = {Besançon, Mathieu and Garcia, Joaquim Dias and Legat, Benoît and Sharma, Akshay},
  title = {Flexible Differentiable Optimization Via Model Transformations}
}
  6. 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]
    @misc{FWopenLoopAccelerate2023,
  archiveprefix = {arXiv},
  eprint = {2310.04096},
  primaryclass = {math.OC},
  year = {2023},
  author = {Wirth, Elias and Pena, Javier and Pokutta, Sebastian},
  title = {Accelerated Affine-invariant Convergence Rates of the Frank-Wolfe Algorithm with Open-loop Step-sizes}
}
  7. 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]
    @article{abssmooth-fw_2023,
  year = {2023},
  journal = {Optimization Methods and Software},
  archiveprefix = {arXiv},
  eprint = {2303.09881},
  primaryclass = {math.OC},
  author = {Kreimeier, Timo and Pokutta, Sebastian and Walther, Andrea and Woodstock, Zev},
  title = {On a Frank-Wolfe Approach for Abs-smooth Functions}
}
  8. Criscitiello, C., MartĂ­nez-Rubio, D., and Boumal, N. (2023). Open Problem: Polynomial Linearly-convergent Method for G-convex Optimization? Proceedings of Annual Conference on Learning Theory. [arXiv]
    [BibTeX]
    @inproceedings{cmb_open_problem_polynomial_linearly_convergent_method_for_gconvex_optimization_23,
  year = {2023},
  booktitle = {Proceedings of Annual Conference on Learning Theory},
  archiveprefix = {arXiv},
  eprint = {2307.12743},
  primaryclass = {math.OC},
  author = {Criscitiello, Christopher and MartĂ­nez-Rubio, David and Boumal, Nicolas},
  title = {Open Problem: Polynomial Linearly-convergent Method for G-convex Optimization?}
}
  9. 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]
    @inproceedings{mp_acceleratedriemannian_22,
  year = {2023},
  booktitle = {Proceedings of Annual Conference on Learning Theory},
  url = {https://proceedings.mlr.press/v195/martinez-rubio23a/martinez-rubio23a.pdf},
  archiveprefix = {arXiv},
  eprint = {2211.14645},
  primaryclass = {math.OC},
  author = {MartĂ­nez-Rubio, David and Pokutta, Sebastian},
  title = {Accelerated Riemannian Optimization: Handling Constraints with a Prox to Bound Geometric Penalties},
  poster = {https://pokutta.com/slides/20221203_poster_neurips_riemannian.pdf}
}
  10. MartĂ­nez-Rubio, D., Roux, C., Criscitiello, C., and Pokutta, S. (2023). Accelerated Riemannian Min-Max Optimization Ensuring Bounded Geometric Penalties. [arXiv]
    [BibTeX]
    @misc{mrp_accelerated_minmax_riemannian_23,
  archiveprefix = {arXiv},
  eprint = {2305.16186},
  primaryclass = {math.OC},
  year = {2023},
  author = {MartĂ­nez-Rubio, David and Roux, Christophe and Criscitiello, Christopher and Pokutta, Sebastian},
  title = {Accelerated Riemannian Min-Max Optimization Ensuring Bounded Geometric Penalties}
}
  11. 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]
    @inproceedings{mwp_accelerated_sparse_pagerank_23,
  year = {2023},
  booktitle = {Proceedings of Annual Conference on Learning Theory},
  archiveprefix = {arXiv},
  eprint = {2303.12875},
  primaryclass = {math.OC},
  author = {MartĂ­nez-Rubio, David and Wirth, Elias and Pokutta, Sebastian},
  title = {Accelerated and Sparse Algorithms for Approximate Personalized PageRank and Beyond}
}
  12. Scieur, D., Kerdreux, T., Martínez-Rubio, D., d’Aspremont, A., and Pokutta, S. (2023). Strong Convexity of Sets in Riemannian Manifolds. [arXiv]
    [BibTeX]
    @misc{skmap_strong_convexity_of_sets_in_riemannian_manifolds_23,
  archiveprefix = {arXiv},
  eprint = {2312.03583},
  primaryclass = {math.OC},
  year = {2023},
  author = {Scieur, Damien and Kerdreux, Thomas and MartĂ­nez-Rubio, David and d'Aspremont, Alexandre and Pokutta, Sebastian},
  title = {Strong Convexity of Sets in Riemannian Manifolds}
}
  13. Woodstock, Z., and Pokutta, S. (2023). Splitting the Conditional Gradient Algorithm. [arXiv]
    [BibTeX]
    @misc{splitcg2023,
  archiveprefix = {arXiv},
  eprint = {2311.05381},
  primaryclass = {math.OC},
  year = {2023},
  author = {Woodstock, Zev and Pokutta, Sebastian},
  title = {Splitting the Conditional Gradient Algorithm}
}
  14. 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]
    @inproceedings{wkp_openloop_22,
  year = {2023},
  booktitle = {Proceedings of International Conference on Artificial Intelligence and Statistics},
  archiveprefix = {arXiv},
  eprint = {2205.12838},
  primaryclass = {math.OC},
  author = {Wirth, Elias and Kerdreux, Thomas and Pokutta, Sebastian},
  title = {Acceleration of Frank-Wolfe Algorithms with Open Loop Step-sizes}
}
  15. Wirth, E., Kera, H., and Pokutta, S. (2023). Approximate Vanishing Ideal Computations at Scale. Proceedings of International Conference on Learning Representations. [arXiv] [slides]
    [BibTeX]
    @inproceedings{wkp_vanishingideal_22,
  year = {2023},
  booktitle = {Proceedings of International Conference on Learning Representations},
  archiveprefix = {arXiv},
  eprint = {2207.01236},
  primaryclass = {cs.LG},
  author = {Wirth, Elias and Kera, Hiroshi and Pokutta, Sebastian},
  title = {Approximate Vanishing Ideal Computations at Scale},
  slides = {https://pokutta.com/slides/20220915_avi_at_scale.pdf}
}
  16. Wilken, S. E., Besançon, M., Kratochvíl, M., Kuate, C. A. F., Trefois, C., Gu, W., and Ebenhöh, O. (2022). Interrogating the Effect of Enzyme Kinetics on Metabolism Using Differentiable Constraint-based Models. Metabolic Engineering.
    [BibTeX]
    @article{enzymekinetics22,
  year = {2022},
  journal = {Metabolic Engineering},
  month = nov,
  author = {Wilken, St. Elmo and Besançon, Mathieu and Kratochvíl, Miroslav and Kuate, Chilperic Armel Foko and Trefois, Christophe and Gu, Wei and Ebenhöh, Oliver},
  title = {Interrogating the Effect of Enzyme Kinetics on Metabolism Using Differentiable Constraint-based Models}
}
  17. Búi, M. N., Combettes, P. L., and Woodstock, Z. (2022). Block-activated Algorithms for Multicomponent Fully Nonsmooth Minimization. Proceedings of ICASSP 2022 - 2022 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), 5428–5432. DOI: 10.1109/ICASSP43922.2022.9747479 [URL]
    [BibTeX]
    @inproceedings{Block22,
  year = {2022},
  booktitle = {Proceedings of ICASSP 2022 - 2022 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)},
  month = may,
  pages = {5428-5432},
  doi = {10.1109/ICASSP43922.2022.9747479},
  url = {https://zevwoodstock.github.io/media/publications/icassp2022-2.pdf},
  author = {BĂşi, M. N. and Combettes, P. L. and Woodstock, Zev},
  title = {Block-activated Algorithms for Multicomponent Fully Nonsmooth Minimization}
}
  18. 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]
    @article{besanccon2022frankwolfe,
  year = {2022},
  journal = {INFORMS Journal on Computing},
  month = feb,
  archiveprefix = {arXiv},
  eprint = {2104.06675},
  primaryclass = {math.OC},
  author = {Besançon, Mathieu and Carderera, Alejandro and Pokutta, Sebastian},
  title = {FrankWolfe.jl: A High-Performance and Flexible Toolbox for Frank-Wolfe Algorithms and Conditional Gradients},
  code = {https://github.com/ZIB-IOL/FrankWolfe.jl},
  slides = {https://pokutta.com/slides/20210710_FW-simpleSteps-SelfConcordance.pdf},
  summary = {https://pokutta.com/blog/research/2021/04/20/FrankWolfejl.html}
}
  19. Braun, G., Pokutta, S., and Weismantel, R. (2022). Alternating Linear Minimization: Revisiting von Neumann’s Alternating Projections. [arXiv] [slides] [video]
    [BibTeX]
    @misc{alternating_lmo_2022,
  archiveprefix = {arXiv},
  eprint = {2212.02933},
  primaryclass = {math.OC},
  year = {2022},
  author = {Braun, Gábor and Pokutta, Sebastian and Weismantel, Robert},
  title = {Alternating Linear Minimization: Revisiting von Neumann’s Alternating Projections},
  slides = {https://pokutta.com/slides/20230327-icerm.pdf},
  video = {https://icerm.brown.edu/programs/sp-s23/w2/#schedule-item-4945}
}
  20. 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]
    @inproceedings{cmp_packing_proportional_fairness_22,
  year = {2022},
  booktitle = {Proceedings of Conference on Neural Information Processing Systems},
  archiveprefix = {arXiv},
  eprint = {2109.03678},
  primaryclass = {math.OC},
  author = {Criado, Francisco and MartĂ­nez-Rubio, David and Pokutta, Sebastian},
  title = {Fast Algorithms for Packing Proportional Fairness and Its Dual},
  poster = {https://pokutta.com/slides/20211105_fairpacking-poster.pdf}
}
  21. Braun, G., Carderera, A., Combettes, C., Hassani, H., Karbasi, A., Mokhtari, A., and Pokutta, S. (2022). Conditional Gradient Methods. [arXiv]
    [BibTeX]
    @misc{fw_survey_2022,
  archiveprefix = {arXiv},
  eprint = {2211.14103},
  primaryclass = {math.OC},
  year = {2022},
  author = {Braun, Gábor and Carderera, Alejandro and Combettes, Cyrille and Hassani, Hamed and Karbasi, Amin and Mokhtari, Aryan and Pokutta, Sebastian},
  title = {Conditional Gradient Methods}
}
  22. 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]
    @article{hpw_lowhigh_22,
  year = {2022},
  journal = {SIAM Journal on Optimization},
  archiveprefix = {arXiv},
  eprint = {2204.05266},
  primaryclass = {math.OC},
  author = {Hunkenschröder, Christoph and Pokutta, Sebastian and Weismantel, Robert},
  title = {Optimizing a Low-dimensional Convex Function Over a High-dimensional Cube}
}
  23. 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]
    @inproceedings{mbp_interpretfw_22,
  year = {2022},
  booktitle = {Proceedings of International Conference on Machine Learning},
  archiveprefix = {arXiv},
  eprint = {2110.08105},
  primaryclass = {cs.lG},
  author = {Macdonald, Jan and Besançon, Mathieu and Pokutta, Sebastian},
  title = {Interpretable Neural Networks with Frank-Wolfe: Sparse Relevance Maps and Relevance Orderings},
  poster = {https://pokutta.com/slides/20220712_icml_poster_interpretable_rde.pdf},
  video = {https://slideslive.com/38983588}
}
  24. 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]
    @inproceedings{wp_approxvanideal_22,
  year = {2022},
  booktitle = {Proceedings of International Conference on Artificial Intelligence and Statistics},
  archiveprefix = {arXiv},
  eprint = {2202.03349},
  primaryclass = {cs.LG},
  author = {Wirth, Elias and Pokutta, Sebastian},
  title = {Conditional Gradients for the Approximately Vanishing Ideal},
  code = {https://github.com/ZIB-IOL/cgavi/},
  poster = {https://pokutta.com/slides/20220223_CGAVI_poster.pdf},
  summary = {https://pokutta.com/blog/research/2022/02/20/CGAVI.html}
}
  25. 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]
    @inproceedings{CBP2021:1,
  year = {2021},
  booktitle = {Proceedings of Conference on Neural Information Processing Systems},
  month = may,
  volume = {34},
  pages = {5390–5401},
  url = {https://proceedings.neurips.cc/paper_files/paper/2021/file/2b323d6eb28422cef49b266557dd31ad-Paper.pdf},
  author = {Carderera, Alejandro and Besançon, Mathieu and Pokutta, Sebastian},
  title = {Simple Steps Are All You Need: Frank-Wolfe and Generalized Self-concordant Functions},
  code = {https://doi.org/10.5281/zenodo.4836009},
  poster = {https://pokutta.com/slides/20211120_poster_NeurIPS21_lSimple_steps_are_all_you_need.pdf},
  slides = {https://pokutta.com/slides/20210710_FW-simpleSteps-SelfConcordance.pdf},
  summary = {https://pokutta.com/blog/research/2021/10/09/self-concordant-abstract.html}
}
  26. 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]
    @article{KRAP2021,
  year = {2021},
  journal = {Journal of Machine Learning Research},
  month = mar,
  volume = {22},
  number = {284},
  pages = {1–23},
  url = {http://jmlr.org/papers/v22/21-0277.html},
  archiveprefix = {arXiv},
  eprint = {2103.05907},
  primaryclass = {cs.LG},
  author = {Kerdreux, Thomas and Roux, Christophe and d'Aspremont, Alexandre and Pokutta, Sebastian},
  title = {Linear Bandits on Uniformly Convex Sets},
  summary = {https://www.pokutta.com/blog/research/2021/04/03/linearBandits.html}
}
  27. Braun, G., and Pokutta, S. (2021). Dual Prices for Frank–Wolfe Algorithms. [arXiv]
    [BibTeX]
    @misc{dual_prices_FW_2021,
  archiveprefix = {arXiv},
  eprint = {2101.02087},
  primaryclass = {math.OC},
  year = {2021},
  author = {Braun, Gábor and Pokutta, Sebastian},
  title = {Dual Prices for Frank–Wolfe Algorithms}
}
  28. Roux, C., Wirth, E., Pokutta, S., and Kerdreux, T. (2021). Efficient Online-bandit Strategies for Minimax Learning Problems. [arXiv]
    [BibTeX]
    @misc{online.bandit-minimax_2021,
  archiveprefix = {arXiv},
  eprint = {2105.13939},
  primaryclass = {cs.LG},
  year = {2021},
  author = {Roux, Christophe and Wirth, Elias and Pokutta, Sebastian and Kerdreux, Thomas},
  title = {Efficient Online-bandit Strategies for Minimax Learning Problems}
}
  29. 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]
    @article{Braun2015LP-SDP,
  year = {2019},
  journal = {Mathematical Programming},
  volume = {173},
  pages = {281–312},
  doi = {10.1007/s10107-017-1221-9},
  archiveprefix = {arXiv},
  eprint = {1410.8816},
  primaryclass = {cs.CC},
  author = {Braun, Gábor and Pokutta, Sebastian and Zink, Daniel},
  title = {Affine Reductions for LPs and SDPs}
}
  30. 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]
    @article{Braun2017lazyCG,
  year = {2019},
  journal = {The Journal of Machine Learning Research},
  volume = {20},
  number = {71},
  pages = {1–42},
  url = {https://jmlr.org/papers/v20/18-114.html},
  archiveprefix = {arXiv},
  eprint = {1610.05120},
  primaryclass = {cs.DS},
  author = {Braun, Gábor and Pokutta, Sebastian and Zink, Daniel},
  title = {Lazifying Conditional Gradient Algorithms}
}
  31. 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]
    @inproceedings{Braun2018blendedCG,
  year = {2019},
  booktitle = {Proceedings of International Conference on Machine Learning},
  volume = {97},
  pages = {735–743},
  url = {https://proceedings.mlr.press/v97/braun19a},
  archiveprefix = {arXiv},
  eprint = {1805.07311},
  primaryclass = {math.OC},
  author = {Braun, Gábor and Pokutta, Sebastian and Tu, Dan and Wright, Stephen},
  title = {Blended Conditional Gradients: the Unconditioning of Conditional Gradients},
  code = {https://github.com/pokutta/bcg},
  poster = {https://app.box.com/s/nmmm671jd72i397nysa8emfnzh1hn6hf},
  slides = {https://app.box.com/s/xbx3z7ws6dxvl3rzgj4jp6forigycooe},
  summary = {https://pokutta.com/blog/research/2019/02/18/bcg-abstract.html}
}
  32. 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]
    @article{BPR2015,
  year = {2018},
  journal = {Mathematical Programming},
  month = nov,
  volume = {172},
  pages = {591–620},
  doi = {10.1007/s10107-018-1316-y},
  archiveprefix = {arXiv},
  eprint = {1512.04932},
  primaryclass = {cs.CC},
  author = {Braun, Gábor and Pokutta, Sebastian and Roy, Aurko},
  title = {Strong Reductions for Extended Formulations}
}
  33. 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]
    @article{Braun2016matching-symmetricSDP,
  year = {2017},
  journal = {Mathematical Programming},
  month = oct,
  volume = {165},
  pages = {643–662},
  doi = {10.1007/s10107-016-1098-z},
  archiveprefix = {arXiv},
  eprint = {1504.00703},
  primaryclass = {cs.CC},
  author = {Braun, Gábor and Brown-Cohen, Jonah and Huq, Arefin and Pokutta, Sebastian and Raghavendra, Prasad and Roy, Aurko and Weitz, Benjamin and Zink, Daniel},
  title = {The Matching Problem Has No Small Symmetric SDP}
}
  34. 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]
    @article{Braun2013lowerCO,
  year = {2017},
  journal = {IEEE Transactions on Information Theory},
  month = jul,
  volume = {63},
  number = {7},
  pages = {4709-4724},
  doi = {10.1109/TIT.2017.2701343},
  archiveprefix = {arXiv},
  eprint = {1407.5144},
  primaryclass = {math.OC},
  author = {Braun, Gábor and Guzmán, Cristóbal and Pokutta, Sebastian},
  title = {Unifying Lower Bounds on the Oracle Complexity of Nonsmooth Convex Optimization}
}
  35. 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]
    @article{Braun2017info-nonnegative-rank,
  year = {2017},
  journal = {Computational Complexity},
  volume = {26},
  pages = {147–197},
  doi = {10.1007/s00037-016-0125-z},
  url = {https://eccc.weizmann.ac.il/report/2013/158},
  author = {Braun, Gábor and Jain, Rahul and Lee, Troy and Pokutta, Sebastian},
  title = {Information-theoretic Approximations of the Nonnegative Rank}
}
  36. 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]
    @inproceedings{Braun2017lazyCG:1,
  year = {2017},
  booktitle = {Proceedings of International Conference on Machine Learning},
  volume = {70},
  pages = {566–575},
  url = {https://proceedings.mlr.press/v70/braun17a},
  archiveprefix = {arXiv},
  eprint = {1610.05120},
  primaryclass = {cs.DS},
  author = {Braun, Gábor and Pokutta, Sebastian and Zink, Daniel},
  title = {Lazifying Conditional Gradient Algorithms},
  poster = {https://app.box.com/s/lysscdg17ytpz7mqr0tu2djffyqvkl6a},
  slides = {https://app.box.com/s/zsp0hixjz2ha23u1vuyosijjkjdh8k}
}
  37. 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]
    @inproceedings{BPR2015:1,
  year = {2016},
  booktitle = {Proceedings of Conference on Integer Programming and Combinatorial Optimization},
  month = jun,
  volume = {9682},
  pages = {350–361},
  doi = {10.1007/978-3-319-33461-5_29},
  archiveprefix = {arXiv},
  eprint = {1512.04932},
  primaryclass = {cs.CC},
  author = {Braun, Gábor and Pokutta, Sebastian and Roy, Aurko},
  title = {Strong Reductions for Extended Formulations}
}
  38. 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]
    @article{Braun2013stable,
  year = {2016},
  journal = {Mathematical Programming},
  month = mar,
  volume = {160},
  number = {1},
  pages = {407–431},
  doi = {10.1007/s10107-016-0989-3},
  archiveprefix = {arXiv},
  eprint = {1311.4001},
  primaryclass = {cs.CC},
  author = {Braun, Gábor and Firorini, Samuel and Pokutta, Sebastian},
  title = {Average Case Polyhedral Complexity of the Maximum Stable Set Problem}
}
  39. 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]
    @article{Braun2013info-disjoint,
  year = {2016},
  journal = {Algorithmica},
  month = feb,
  volume = {76},
  number = {3},
  pages = {597–629},
  doi = {10.1007/s00453-016-0132-0},
  url = {https://eccc.weizmann.ac.il/report/2013/056},
  author = {Braun, Gábor and Pokutta, Sebastian},
  title = {Common Information and Unique Disjointness}
}
  40. Braun, G., and Pokutta, S. (2016). An Efficient High-probability Algorithm for Linear Bandits. [arXiv]
    [BibTeX]
    @misc{Braun2016bandit,
  archiveprefix = {arXiv},
  eprint = {1610.02072},
  primaryclass = {cs.DS},
  year = {2016},
  author = {Braun, Gábor and Pokutta, Sebastian},
  title = {An Efficient High-probability Algorithm for Linear Bandits}
}
  41. 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]
    @inproceedings{Braun2016matching-symmetricSDP:1,
  year = {2016},
  booktitle = {Proceedings of Symposium on Discrete Algorithms},
  pages = {1067–1078},
  doi = {10.1137/1.9781611974331.ch75},
  archiveprefix = {arXiv},
  eprint = {1504.00703},
  primaryclass = {cs.CC},
  author = {Braun, Gábor and Brown-Cohen, Jonah and Huq, Arefin and Pokutta, Sebastian and Raghavendra, Prasad and Roy, Aurko and Weitz, Benjamin and Zink, Daniel},
  title = {The Matching Problem Has No Small Symmetric SDP}
}
  42. 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]
    @article{Braun2012UDISJ,
  year = {2015},
  journal = {Mathematics of Operations Research},
  month = aug,
  volume = {40},
  number = {3},
  pages = {756-772},
  doi = {10.1287/moor.2014.0694},
  archiveprefix = {arXiv},
  eprint = {1204.0957},
  primaryclass = {c.CC},
  author = {Braun, Gábor and Firorini, Samuel and Pokutta, Sebastian and Steurer, David},
  title = {Approximation Limits of Linear Programs (beyond Hierarchies)}
}
  43. 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]
    @article{Braun2014info-greedy,
  year = {2015},
  journal = {IEEE Journal of Selected Topics in Signal Processing},
  month = jun,
  volume = {9},
  number = {4},
  pages = {601–611},
  doi = {10.1109/JSTSP.2015.2400428},
  archiveprefix = {arXiv},
  eprint = {1407.0731},
  primaryclass = {cs.IT},
  author = {Braun, Gábor and Pokutta, Sebastian and Xie, Yao},
  title = {Info-greedy Sequential Adaptive Compressed Sensing}
}
  44. 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]
    @inproceedings{Braun2015LP-SDP:1,
  year = {2015},
  booktitle = {Proceedings of Annual Symposium on Theory of Computing},
  month = jun,
  pages = {107–116},
  doi = {10.1145/2746539.2746550},
  archiveprefix = {arXiv},
  eprint = {1410.8816},
  primaryclass = {cs.CC},
  author = {Braun, Gábor and Pokutta, Sebastian and Zink, Daniel},
  title = {Inapproximability of Combinatorial Problems Via Small LPs and SDPs},
  video = {https://youtu.be/MxLEticZ8RY}
}
  45. 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]
    @inproceedings{Braun2014matching,
  year = {2015},
  booktitle = {Proceedings of Symposium on Discrete Algorithms},
  pages = {837-846},
  doi = {10.1137/1.9781611973730.57},
  archiveprefix = {arXiv},
  eprint = {1403.6710},
  primaryclass = {cs.CC},
  author = {Braun, Gábor and Pokutta, Sebastian},
  title = {The Matching Polytope Does Not Admit Fully-polynomial Size Relaxation Schemes}
}
  46. 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]
    @inproceedings{Braun2013stable:1,
  year = {2014},
  booktitle = {Proceedings of Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques},
  month = sep,
  volume = {28},
  pages = {515–530},
  doi = {10.4230/LIPIcs.APPROX-RANDOM.2014.515},
  url = {https://drops.dagstuhl.de/opus/volltexte/2014/4720},
  archiveprefix = {arXiv},
  eprint = {1311.4001},
  primaryclass = {cs.CC},
  author = {Braun, Gábor and Firorini, Samuel and Pokutta, Sebastian},
  title = {Average Case Polyhedral Complexity of the Maximum Stable Set Problem}
}
  47. 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]
    @inproceedings{Braun2014info-greedy:1,
  year = {2014},
  booktitle = {Proceedings of Allerton Conference on Communication, Control, and Computing (Allerton)},
  pages = {858–865},
  doi = {10.1109/ALLERTON.2014.7028544},
  archiveprefix = {arXiv},
  eprint = {1407.0731},
  primaryclass = {cs.IT},
  author = {Braun, Gábor and Pokutta, Sebastian and Xie, Yao},
  title = {Info-greedy Sequential Adaptive Compressed Sensing}
}
  48. Braun, G., and Pokutta, S. (2013). Common Information and Unique Disjointness. Proceedings of Annual Symposium on Foundations of Computer Science, 688–697. [URL]
    [BibTeX]
    @inproceedings{Braun2013info-disjoint:1,
  year = {2013},
  booktitle = {Proceedings of Annual Symposium on Foundations of Computer Science},
  pages = {688–697},
  url = {https://eccc.weizmann.ac.il/report/2013/056},
  author = {Braun, Gábor and Pokutta, Sebastian},
  title = {Common Information and Unique Disjointness}
}
  49. 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]
    @inproceedings{Braun2012symEF,
  year = {2012},
  booktitle = {Proceedings of International Symposium on Combinatorial Optimization},
  month = apr,
  volume = {7422},
  pages = {141–152},
  doi = {10.1007/978-3-642-32147-4_14},
  archiveprefix = {arXiv},
  eprint = {1206.6318},
  primaryclass = {cs.CC},
  author = {Braun, Gábor and Pokutta, Sebastian},
  title = {An Algebraic Approach to Symmetric Extended Formulations}
}
  50. 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]
    @inproceedings{Braun2012UDISJ:1,
  year = {2012},
  booktitle = {Proceedings of Annual Symposium on Foundations of Computer Science},
  pages = {480–489},
  doi = {10.1109/FOCS.2012.10},
  archiveprefix = {arXiv},
  eprint = {1204.0957},
  primaryclass = {c.CC},
  author = {Braun, Gábor and Firorini, Samuel and Pokutta, Sebastian and Steurer, David},
  title = {Approximation Limits of Linear Programs (beyond Hierarchies)}
}