Continuous Optimization

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

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

David Martínez-Rubio
martinez-rubio (at) zib.de

Zev Woodstock
woodstock (at) zib.de

Christophe Roux
roux (at) zib.de

Deborah Hendrych
hendrych (at) zib.de

Dominik Kuzinowicz
kuzinowicz (at) zib.de

Elias Wirth
wirth (at) zib.de

Garam Kim
garam (at) zib.de

Gábor Braun
braun (at) zib.de

Hannah Troppens
troppens (at) zib.de

Jannis Halbey
halbey (at) zib.de

Priyanshi Chandra
i19ma012 (at) amhd.svnit.ac.in

Projects

Sparsity and Sample-size Efficiency in Structured Learning (MATH+ AA5-1)
On a Frank-Wolfe Approach for Abs-smooth Optimization (MATH+ EF1-23)
Beyond the Worst-case: Data-dependent Rates in Learning and Optimization (MATH+ AA3-7)
Theoretical Foundations of Deep Learning (SPP 2298, project number 441826958)
Decision-making for Energy Network Dynamics (MATH+ AA4-7)

Publications

Braun, G., Guzmán, C., and Pokutta, S. (2024). Corrigendum in “Lower Bounds on the Oracle Complexity of Nonsmooth Convex Optimization Via Information Theory.” IEEE Transactions on Information Theory. DOI: 10.1109/TIT.2024.3357200

[BibTeX]

@article{Braun2013lowerCO_corr,
  year = {2024},
  journal = {IEEE Transactions on Information Theory},
  doi = {10.1109/TIT.2024.3357200},
  author = {Braun, Gábor and Guzmán, Cristóbal and Pokutta, Sebastian},
  title = {Corrigendum in “Lower Bounds on the Oracle Complexity of Nonsmooth Convex Optimization Via Information Theory”}
}

Carderera, A., Besançon, M., and Pokutta, S. (2024). Scalable Frank-Wolfe on Generalized Self-concordant Functions Via Simple Steps. SIAM Journal on Optimization. [summary] [slides] [poster] [code]

[BibTeX]

@article{CBP2021,
  year = {2024},
  journal = {SIAM Journal on Optimization},
  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}
}

Martínez-Rubio, D., Roux, C., and Pokutta, S. (2024). Convergence and Trade-offs in Riemannian Gradient Descent and Riemannian Proximal Point. [arXiv]

[BibTeX]

@misc{mrp_tradeoffs_riemannian_gradient_descent_23,
  archiveprefix = {arXiv},
  eprint = {2403.10429},
  primaryclass = {math.OC},
  year = {2024},
  author = {Martínez-Rubio, David and Roux, Christophe and Pokutta, Sebastian},
  title = {Convergence and Trade-offs in Riemannian Gradient Descent and Riemannian Proximal Point}
}

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}
}

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}
}

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}
}

Criscitiello, C., Martínez-Rubio, D., and Boumal, N. (2023). Open Problem: Polynomial Linearly-convergent Method for G-convex Optimization? Proceedings of Annual Workshop on Computational Learning Theory. [arXiv]

[BibTeX]

@inproceedings{cmb_open_problem_polynomial_linearly_convergent_method_for_gconvex_optimization_23,
  year = {2023},
  booktitle = {Proceedings of Annual Workshop on Computational 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?}
}

Deza, A., Onn, S., Pokutta, S., and Pournin, L. (2023). Kissing Polytopes. [arXiv]

[BibTeX]

@misc{kissing_polytopes_2023,
  archiveprefix = {arXiv},
  eprint = {2305.18597},
  primaryclass = {math.MG},
  year = {2023},
  author = {Deza, Antoine and Onn, Shmuel and Pokutta, Sebastian and Pournin, Lionel},
  title = {Kissing Polytopes}
}

Martínez-Rubio, D., Roux, C., Criscitiello, C., and Pokutta, S. (2023). Accelerated Riemannian Min-Max Optimization Ensuring Bounded Geometric Penalties. Proceedings of Optimization for Machine Learning (NeurIPS Workshop OPT 2023). [arXiv]

[BibTeX]

@inproceedings{mrp_accelerated_minmax_riemannian_23,
  year = {2023},
  booktitle = {Proceedings of Optimization for Machine Learning (NeurIPS Workshop OPT 2023)},
  archiveprefix = {arXiv},
  eprint = {2305.16186},
  primaryclass = {math.OC},
  author = {Martínez-Rubio, David and Roux, Christophe and Criscitiello, Christopher and Pokutta, Sebastian},
  title = {Accelerated Riemannian Min-Max Optimization Ensuring Bounded Geometric Penalties}
}

Martínez-Rubio, D., Wirth, E., and Pokutta, S. (2023). Accelerated and Sparse Algorithms for Approximate Personalized PageRank and Beyond. Proceedings of Annual Workshop on Computational Learning Theory. [arXiv]

[BibTeX]

@inproceedings{mwp_accelerated_sparse_pagerank_23,
  year = {2023},
  booktitle = {Proceedings of Annual Workshop on Computational 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}
}

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}
}

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}
}

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}
}

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}
}

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}
}

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}
}

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}
}

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}
}

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}
}

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}
}

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}
}

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}
}

Martínez-Rubio, D., and Pokutta, S. (2022). Accelerated Riemannian Optimization: Handling Constraints with a Prox to Bound Geometric Penalties. Proceedings of Optimization for Machine Learning (NeurIPS Workshop OPT 2022). [URL] [arXiv] [poster]

[BibTeX]

@inproceedings{mp_acceleratedriemannian_22,
  year = {2022},
  booktitle = {Proceedings of Optimization for Machine Learning (NeurIPS Workshop OPT 2022)},
  url = {https://opt-ml.org/papers/2022/paper27.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}
}

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}
}

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}
}

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}
}

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}
}

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}
}

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}
}

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}
}

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}
}

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}
}

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}
}

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}
}

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}
}

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}
}

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}
}

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)}
}

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}
}

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}
}

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}
}