Header Image

Continuous Optimization

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

7
5
85

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
SĂ©bastien Designolle
Research Area Lead
designolle (at) zib.de
Gábor Braun
braun (at) zib.de
Christophe Roux
roux (at) zib.de
Jannis Halbey
halbey (at) zib.de
Deborah Hendrych
hendrych (at) zib.de
Dominik Kuzinowicz
kuzinowicz (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

Jul 2024
Solving the Optimal Design Problem with Mixed-Integer Convex Methods by Deborah Hendrych
22nd Symposium on Experimental Algorithms (SEA), Vienna
Jul 2024
Bell and Grothendieck Meet Frank-Wolfe by SĂ©bastien Designolle
25th International Symposium on Mathematical Programming (ISMP), Montréal
Nov 2023
Bounding Geometric Penalties in First-order Riemannian Optimization by Christophe Roux
Seminar "Modern Methods in Applied Stochastics and Nonparametric Statistics"
Jun 2023
Improved Local Models and New Bell Inequalities by SĂ©bastien Designolle
workshop on quantum computation and optimization, Berlin
Mar 2023
Improved Local Models and New Bell Inequalities Via Frank-Wolfe Algorithms by SĂ©bastien Designolle
15th annual meeting photonic devices, Berlin

Research seminar talks

Dec 2024
What Are the Most Incompatible Quantum Measurements? by SĂ©bastien Designolle
QINFO seminar, Lyon
Nov 2024
Bell and Grothendieck Meet Frank-Wolfe by SĂ©bastien Designolle
ICFO seminar, Castelldefels
Nov 2024
Bell and Grothendieck Meet Frank-Wolfe by SĂ©bastien Designolle
Valladolid seminar, Valladolid
Nov 2024
What Are the Most Incompatible Quantum Measurements? by SĂ©bastien Designolle
IT seminar, Lisbon
Nov 2024
Solving the Optimal Design Problem with Mixed-Integer Convex Methods by Deborah Hendrych
GHOST Research Seminar (GHOST), Grenoble
Oct 2024
Bell and Grothendieck Meet Frank-Wolfe by SĂ©bastien Designolle
quantum information & quantum computing working group seminar, Warsaw
Jul 2024
Solving the Optimal Design Problem with Mixed-Integer Convex Methods by Deborah Hendrych
NASPDE Seminar, Berlin
May 2024
Solving the Optimal Design Problem with Mixed-Integer Convex Methods by Deborah Hendrych
MATH+ Spotlight talks, Berlin
Apr 2024
Bounding Geometric Penalties in Riemannian Optimization by Christophe Roux
CISPA Research seminar, SaarbrĂĽcken
Dec 2023
Solving the Optimal Experiment Design Problems with Mixed-Integer Frank-Wolfe-based Methods by Deborah Hendrych
IOL Research Seminar (IOL), Berlin
Nov 2023
Frank-Wolfe Algorithms for Bell Nonlocality by SĂ©bastien Designolle
IRIF seminar, Paris
Nov 2023
Frank-Wolfe Algorithms for Bell Nonlocality by SĂ©bastien Designolle
QAT seminar, Paris
Nov 2023
Frank-Wolfe Algorithms for Bell Nonlocality by SĂ©bastien Designolle
SIERRA seminar, Paris
Nov 2023
Frank-Wolfe Algorithms for Bell Nonlocality by SĂ©bastien Designolle
PhiQus seminar, Palaiseau
Nov 2023
Frank-Wolfe Algorithms for Bell Nonlocality by SĂ©bastien Designolle
LIP6 seminar, Paris
Oct 2023
Frank-Wolfe Algorithms for Bell Nonlocality by SĂ©bastien Designolle
QINFO seminar, Lyon
Mar 2023
Improved Local Models and New Bell Inequalities Via Frank-Wolfe Algorithms by SĂ©bastien Designolle
JQIT seminar, Krakow
Feb 2023
Improved Local Models and New Bell Inequalities Via Frank-Wolfe Algorithms by SĂ©bastien Designolle
Atomki seminar, Debrecen
Feb 2023
Improved Local Models and New Bell Inequalities Via Frank-Wolfe Algorithms by SĂ©bastien Designolle
IQOQI seminar, Vienna

Poster presentations

Jul 2024
Convergence and Trade-Offs in Riemannian Gradient Descent and Riemannian Proximal Point by Christophe Roux
41st International Conference on Machine Learning (ICML), Vienna
Apr 2024
Convex Solver Adaptivity for Mixed-Integer Optimization by Deborah Hendrych
5th Women in Optimization 2024 (WiO), Erlangen

đź“ť 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 [arXiv] [summary] [slides] [poster] [code]
    [BibTeX]
    @article{2024_CardereraBesanconPokutta_Scalablefrankwolfe,
  year = {2024},
  journal = {SIAM Journal on Optimization},
  month = sep,
  volume = {34},
  number = {3},
  pages = {2231-2258},
  doi = {10.1137/23M1616789},
  archiveprefix = {arXiv},
  eprint = {2105.13913},
  primaryclass = {math.OC},
  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{2024_BraunGuzmanPokutta_Oraclecomplexity,
  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. 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]
    @article{2023_Pokutta_Frankwolfealgorithm,
  year = {2024},
  journal = {Jahresbericht der Deutschen Mathematiker-Vereinigung},
  month = mar,
  volume = {126},
  number = {1},
  pages = {3–35},
  doi = {10.1365/s13291-023-00275-x},
  url = {https://link.springer.com/article/10.1365/s13291-023-00275-x/fulltext.html},
  archiveprefix = {arXiv},
  eprint = {2311.05313},
  primaryclass = {math.OC},
  author = {Pokutta, Sebastian},
  title = {The Frank-Wolfe Algorithm: a Short Introduction}
}
  4. Designolle, S., VĂ©rtesi, T., and Pokutta, S. (2024). Better Bounds on Grothendieck Constants of Finite Orders. [arXiv]
    [BibTeX]
    @misc{2023_DesignolleVertesiPokutta_Grothendieckconstants,
  archiveprefix = {arXiv},
  eprint = {2409.03739},
  primaryclass = {math.OC},
  year = {2024},
  author = {Designolle, Sébastien and Vértesi, Tamás and Pokutta, Sebastian},
  title = {Better Bounds on Grothendieck Constants of Finite Orders}
}
  5. Deza, A., Onn, S., Pokutta, S., and Pournin, L. (2024). Kissing Polytopes. SIAM Journal on Discrete Mathematics. [arXiv]
    [BibTeX]
    @article{2023_DezaShmuelPokuttaPournin_Kissingpolytopes,
  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}
}
  6. Braun, G., Pokutta, S., and Woodstock, Z. (2024). Flexible Block-iterative Analysis for the Frank-Wolfe Algorithm. [arXiv]
    [BibTeX]
    @misc{2024_BraunPokuttaWoodstock_Blockiterativeanalysis,
  archiveprefix = {arXiv},
  eprint = {2409.06931},
  primaryclass = {math.OC},
  year = {2024},
  author = {Braun, Gábor and Pokutta, Sebastian and Woodstock, Zev},
  title = {Flexible Block-iterative Analysis for the Frank-Wolfe Algorithm}
}
  7. Designolle, S., VĂ©rtesi, T., and Pokutta, S. (2024). Symmetric Multipartite Bell Inequalities Via Frank-Wolfe Algorithms. Physics Review A. [arXiv]
    [BibTeX]
    @article{2024_DesignolleVertesiPokutta_SymmetricBellinequalities,
  year = {2024},
  journal = {Physics Review A},
  archiveprefix = {arXiv},
  eprint = {2310.20677},
  primaryclass = {quant-ph},
  author = {Designolle, Sébastien and Vértesi, Tamás and Pokutta, Sebastian},
  title = {Symmetric Multipartite Bell Inequalities Via Frank-Wolfe Algorithms}
}
  8. MartĂ­nez-Rubio, D., Roux, C., and Pokutta, S. (2024). Convergence and Trade-offs in Riemannian Gradient Descent and Riemannian Proximal Point. Proceedings of the International Conference on Machine Learning. [URL] [arXiv]
    [BibTeX]
    @inproceedings{2024_MartinezrubioRouxPokutta_Riemanniangradientdescent,
  year = {2024},
  booktitle = {Proceedings of the International Conference on Machine Learning},
  url = {https://proceedings.mlr.press/v235/marti-nez-rubio24a.html},
  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}
}
  9. Wirth, E., Besançon, M., and Pokutta, S. (2024). The Pivoting Framework: Frank-Wolfe Algorithms with Active Set Size Control. [arXiv]
    [BibTeX]
    @misc{2024_WirthBesanconPokutta_Pivotingframework,
  archiveprefix = {arXiv},
  eprint = {2407.11760},
  primaryclass = {math.OC},
  year = {2024},
  author = {Wirth, Elias and Besançon, Mathieu and Pokutta, Sebastian},
  title = {The Pivoting Framework: Frank-Wolfe Algorithms with Active Set Size Control}
}
  10. Wirth, E., Pena, J., and Pokutta, S. (2024). Fast Convergence of Frank-Wolfe Algorithms on Polytopes. [arXiv]
    [BibTeX]
    @misc{2024_WirthJavierPokutta_Frankwolfeconvergence,
  archiveprefix = {arXiv},
  eprint = {2406.18789},
  primaryclass = {math.OC},
  year = {2024},
  author = {Wirth, Elias and Pena, Javier and Pokutta, Sebastian},
  title = {Fast Convergence of Frank-Wolfe Algorithms on Polytopes}
}
  11. 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]
    @article{2023_DesignolleEtAl_LocalmodelsBellinequalities,
  year = {2023},
  journal = {Physical Review Research},
  month = oct,
  volume = {5},
  number = {4},
  doi = {10.1103/PhysRevResearch.5.043059},
  archiveprefix = {arXiv},
  eprint = {2302.04721},
  primaryclass = {quant-ph},
  author = {Designolle, Sébastien and Iommazzo, Gabriele and Besançon, Mathieu and Knebel, Sebastian and Gelß, Patrick and Pokutta, Sebastian},
  title = {Improved Local Models and New Bell Inequalities Via Frank-Wolfe Algorithms},
  code = {https://github.com/ZIB-IOL/BellPolytopes.jl},
  slides = {https://www.pokutta.com/slides/20230808-tokyo-bell.pdf}
}
  12. 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{2022_BesanconJoaquimBenotAkshay_Differentiableoptimization,
  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}
}
  13. Hunkenschröder, C., Pokutta, S., and Weismantel, R. (2023). Minimizing a Low-dimensional Convex Function Over a High-dimensional Cube. SIAM Journal on Optimization, 33(2), 538–552. DOI: 10.1137/22M1489988 [arXiv]
    [BibTeX]
    @article{2022_HunkenschrderPokuttaWeismantel_Convexoptimization,
  year = {2023},
  journal = {SIAM Journal on Optimization},
  month = jun,
  volume = {33},
  number = {2},
  pages = {538-552},
  doi = {10.1137/22M1489988},
  archiveprefix = {arXiv},
  eprint = {2204.05266},
  primaryclass = {math.OC},
  author = {Hunkenschröder, Christoph and Pokutta, Sebastian and Weismantel, Robert},
  title = {Minimizing a Low-dimensional Convex Function Over a High-dimensional Cube}
}
  14. Kerdreux, T., Scieur, D., d’Aspremont, A., and Pokutta, S. (2023). Strong Convexity of Feasible Sets in Riemannian Manifolds. [arXiv]
    [BibTeX]
    @misc{2022_KerdreuxScieurDaspremontPokutta_StrongconvexityRiemannianmanifolds,
  archiveprefix = {arXiv},
  eprint = {2312.03583},
  primaryclass = {math.OC},
  year = {2023},
  author = {Kerdreux, Thomas and Scieur, Damien and d'Aspremont, Alexandre and Pokutta, Sebastian},
  title = {Strong Convexity of Feasible Sets in Riemannian Manifolds}
}
  15. MartĂ­nez-Rubio, D., and Pokutta, S. (2023). Accelerated Riemannian Optimization: Handling Constraints with a Prox to Bound Geometric Penalties. Proceedings of the Conference on Learning Theory. [URL] [arXiv] [poster]
    [BibTeX]
    @inproceedings{2022_MartinezrubioPokutta_Acceleratedriemannian,
  year = {2023},
  booktitle = {Proceedings of the 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}
}
  16. Wirth, E., Kera, H., and Pokutta, S. (2023). Approximate Vanishing Ideal Computations at Scale. Proceedings of the International Conference on Learning Representations. [arXiv] [slides]
    [BibTeX]
    @inproceedings{2022_WirthKeraPokutta_Approximatevanishingideal,
  year = {2023},
  booktitle = {Proceedings of the 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}
}
  17. Wirth, E., Kerdreux, T., and Pokutta, S. (2023). Acceleration of Frank-Wolfe Algorithms with Open Loop Step-sizes. Proceedings of the International Conference on Artificial Intelligence and Statistics. [arXiv]
    [BibTeX]
    @inproceedings{2022_WirthKerdreuxPokutta_Frankwolfeacceleration,
  year = {2023},
  booktitle = {Proceedings of the 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}
}
  18. Combettes, C., 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 [URL] [arXiv] [slides] [code] [video]
    [BibTeX]
    @article{2023_CombettesPokutta_RevisitingApproximateCaratheodory,
  year = {2023},
  journal = {Mathematical Programming A},
  volume = {197},
  pages = {191-214},
  doi = {10.1007/s10107-021-01735-x},
  url = {https://rdcu.be/cCnPL},
  archiveprefix = {arXiv},
  eprint = {1911.04415},
  primaryclass = {math.OC},
  author = {Combettes, Cyrille and Pokutta, Sebastian},
  title = {Revisiting the Approximate Carathéodory Problem Via the Frank-Wolfe Algorithm},
  code = {https://colab.research.google.com/drive/1GLGRTc2jFYy9CqqoVnZgIFVQgAC0c3aZ},
  slides = {https://app.box.com/s/f0zuvr45qa6etidd06i1wart58o7bc8t},
  video = {https://youtube.com/watch?v=VB1e0HrDmVo}
}
  19. Criscitiello, C., MartĂ­nez-Rubio, D., and Boumal, N. (2023). Open Problem: Polynomial Linearly-convergent Method for G-convex Optimization? Proceedings of the Conference on Learning Theory. [arXiv]
    [BibTeX]
    @inproceedings{2023_CriscitielloMartinezrubioBoumal_Polynomialconvergence,
  year = {2023},
  booktitle = {Proceedings of the 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?}
}
  20. 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{2023_KreimeierPokuttaWaltherWoodstock_Frankwolfeabssmooth,
  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}
}
  21. MartĂ­nez-Rubio, D., Roux, C., Criscitiello, C., and Pokutta, S. (2023). Accelerated Riemannian Min-Max Optimization Ensuring Bounded Geometric Penalties. [arXiv]
    [BibTeX]
    @misc{2023_MartinezrubioRouxCriscitielloPokutta_Riemannianminmax,
  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}
}
  22. MartĂ­nez-Rubio, D., Wirth, E., and Pokutta, S. (2023). Accelerated and Sparse Algorithms for Approximate Personalized PageRank and Beyond. Proceedings of the Conference on Learning Theory. [arXiv]
    [BibTeX]
    @inproceedings{2023_MartinezrubioWirthPokutta_Sparseapproximatepagerank,
  year = {2023},
  booktitle = {Proceedings of the 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}
}
  23. 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{2023_ScieurEtAl_StrongconvexityRiemannianmanifolds,
  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}
}
  24. 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{2023_WirthJavierPokutta_Affineinvariantconvergence,
  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}
}
  25. Woodstock, Z., and Pokutta, S. (2023). Splitting the Conditional Gradient Algorithm. [arXiv]
    [BibTeX]
    @misc{2023_WoodstockPokutta_Conditionalgradientnonconvex,
  archiveprefix = {arXiv},
  eprint = {2311.05381},
  primaryclass = {math.OC},
  year = {2023},
  author = {Woodstock, Zev and Pokutta, Sebastian},
  title = {Splitting the Conditional Gradient Algorithm}
}
  26. 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{2022_ElmoEtAl_Enzymekineticsmetabolism,
  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}
}
  27. Búi, M. N., Combettes, P. L., and Woodstock, Z. (2022). Block-activated Algorithms for Multicomponent Fully Nonsmooth Minimization. Proceedings of the ICASSP 2022 - 2022 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), 5428–5432. DOI: 10.1109/ICASSP43922.2022.9747479 [URL] [arXiv]
    [BibTeX]
    @inproceedings{2022_BiCombettesWoodstock_Blockactivatedminimization,
  year = {2022},
  booktitle = {Proceedings of the 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},
  archiveprefix = {arXiv},
  eprint = {2103.00520},
  primaryclass = {math.OC},
  author = {BĂşi, M. N. and Combettes, Patrick L. and Woodstock, Zev},
  title = {Block-activated Algorithms for Multicomponent Fully Nonsmooth Minimization}
}
  28. 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{2021_BesanconCardereraPokutta_Frankwolfetoolbox,
  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}
}
  29. Kerdreux, T., d’Aspremont, A., and Pokutta, S. (2022). Restarting Frank-Wolfe. Journal of Optimization Theory and Applications, 192, 799–829. DOI: 10.1007/s10957-021-01989-7 [URL] [arXiv] [slides]
    [BibTeX]
    @article{2019_KerdrexDaspremontPokutta_RestartingFrankWolfe,
  year = {2022},
  journal = {Journal of Optimization Theory and Applications},
  volume = {192},
  pages = {799-829},
  doi = {10.1007/s10957-021-01989-7},
  url = {https://dx.doi.org/10.1007/s10957-021-01989-7},
  archiveprefix = {arXiv},
  eprint = {1810.02429},
  primaryclass = {math.OC},
  author = {Kerdreux, Thomas and d'Aspremont, Alexandre and Pokutta, Sebastian},
  title = {Restarting Frank-Wolfe},
  slides = {https://app.box.com/s/prd32r6xmuef2k4gah23rd0egllz9rv5}
}
  30. Criado, F., MartĂ­nez-Rubio, D., and Pokutta, S. (2022). Fast Algorithms for Packing Proportional Fairness and Its Dual. Proceedings of the Conference on Neural Information Processing Systems. [arXiv] [poster]
    [BibTeX]
    @inproceedings{2021_CriadoMartinezrubioPokutta_Packingproportionalfairness,
  year = {2022},
  booktitle = {Proceedings of the 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}
}
  31. Macdonald, J., Besançon, M., and Pokutta, S. (2022). Interpretable Neural Networks with Frank-Wolfe: Sparse Relevance Maps and Relevance Orderings. Proceedings of the International Conference on Machine Learning. [arXiv] [poster] [video]
    [BibTeX]
    @inproceedings{2021_MacdonaldBesanconPokutta_Interpretableneuralnetworks,
  year = {2022},
  booktitle = {Proceedings of the 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}
}
  32. Braun, G., Carderera, A., Combettes, C., Hassani, H., Karbasi, A., Mokhtari, A., and Pokutta, S. (2022). Conditional Gradient Methods. [arXiv]
    [BibTeX]
    @misc{2022_BraunEtAl_Conditionalgradient,
  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}
}
  33. Braun, G., Pokutta, S., and Weismantel, R. (2022). Alternating Linear Minimization: Revisiting von Neumann’s Alternating Projections. [arXiv] [slides] [video]
    [BibTeX]
    @misc{2022_BraunPokuttaWeismantel_Alternatingminimization,
  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}
}
  34. Wirth, E., and Pokutta, S. (2022). Conditional Gradients for the Approximately Vanishing Ideal. Proceedings of the International Conference on Artificial Intelligence and Statistics. [arXiv] [summary] [poster] [code]
    [BibTeX]
    @inproceedings{2022_WirthPokutta_Conditionalgradients,
  year = {2022},
  booktitle = {Proceedings of the 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}
}
  35. Combettes, C., and Pokutta, S. (2021). Complexity of Linear Minimization and Projection on Some Sets. Operations Research Letters, 49(4). [arXiv] [code]
    [BibTeX]
    @article{2021_CombettesPokutta_ComplexityLinearMinimization,
  year = {2021},
  journal = {Operations Research Letters},
  month = jul,
  volume = {49},
  number = {4},
  archiveprefix = {arXiv},
  eprint = {2101.10040},
  primaryclass = {math.OC},
  author = {Combettes, Cyrille and Pokutta, Sebastian},
  title = {Complexity of Linear Minimization and Projection on Some Sets},
  code = {https://github.com/cyrillewcombettes/complexity}
}
  36. Carderera, A., Besançon, M., and Pokutta, S. (2021). Simple Steps Are All You Need: Frank-Wolfe and Generalized Self-concordant Functions. Proceedings of the Conference on Neural Information Processing Systems, 34, 5390–5401. [URL] [arXiv] [summary] [slides] [poster] [code]
    [BibTeX]
    @inproceedings{2024_CardereraBesanconPokutta_Scalablefrankwolfe:1,
  year = {2021},
  booktitle = {Proceedings of the 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},
  archiveprefix = {arXiv},
  eprint = {2105.13913},
  primaryclass = {math.OC},
  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}
}
  37. 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{2021_KerdreuxRouxDaspremontPokutta_Linearbandits,
  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}
}
  38. Carderera, A., Diakonikolas, J., Lin, C. Y., and Pokutta, S. (2021, February). Parameter-free Locally Accelerated Conditional Gradients. Proceedings of the International Conference on Machine Learning. [arXiv] [slides]
    [BibTeX]
    @inproceedings{2021_CardereraDiakonikolasLinPokutta_ParameterfreeLocallyAccelerated,
  year = {2021},
  booktitle = {Proceedings of the International Conference on Machine Learning},
  month = feb,
  archiveprefix = {arXiv},
  eprint = {2102.06806},
  primaryclass = {math.OC},
  author = {Carderera, Alejandro and Diakonikolas, Jelena and Lin, Cheuk Yin and Pokutta, Sebastian},
  title = {Parameter-free Locally Accelerated Conditional Gradients},
  slides = {https://pokutta.com/slides/20210716_PF_LaCG_Poster.pdf}
}
  39. Kerdreux, T., d’Aspremont, A., and Pokutta, S. (2021, January). Projection-Free Optimization on Uniformly Convex Sets. Proceedings of the International Conference on Artificial Intelligence and Statistics. [arXiv] [slides]
    [BibTeX]
    @inproceedings{2021_KerdrexDaspremontPokutta_ProjectionFreeOptimization,
  year = {2021},
  booktitle = {Proceedings of the International Conference on Artificial Intelligence and Statistics},
  month = jan,
  archiveprefix = {arXiv},
  eprint = {2004.11053},
  primaryclass = {math.OC},
  author = {Kerdreux, Thomas and d'Aspremont, Alexandre and Pokutta, Sebastian},
  title = {Projection-Free Optimization on Uniformly Convex Sets},
  slides = {https://app.box.com/s/36wj0o8le96rrfdxec774wk7rrdp2vlm}
}
  40. Anari, N., Haghtalab, N., Naor, S., Pokutta, S., Singh, M., and Torrico Palacios, A. (2021). Structured Robust Submodular Maximization: Offline and Online Algorithms. INFORMS Journal on Computing, 33(4), 1259–1684. [URL] [arXiv]
    [BibTeX]
    @article{2019_AnariHaghtalabNaorPokuttaSinghTorrico_StructuredRobustSubmodular,
  year = {2021},
  journal = {INFORMS Journal on Computing},
  volume = {33},
  number = {4},
  pages = {1259-1684},
  url = {https://pubsonline.informs.org/doi/abs/10.1287/ijoc.2020.0998},
  archiveprefix = {arXiv},
  eprint = {1710.04740},
  primaryclass = {cs.DS},
  author = {Anari, N. and Haghtalab, N. and Naor, S. and Pokutta, Sebastian and Singh, Mohit and Torrico Palacios, Alfredo},
  title = {Structured Robust Submodular Maximization: Offline and Online Algorithms}
}
  41. Braun, G., and Pokutta, S. (2021). Dual Prices for Frank–Wolfe Algorithms. [arXiv]
    [BibTeX]
    @misc{2021_BraunPokutta_DualpricesFrankwolfe,
  archiveprefix = {arXiv},
  eprint = {2101.02087},
  primaryclass = {math.OC},
  year = {2021},
  author = {Braun, Gábor and Pokutta, Sebastian},
  title = {Dual Prices for Frank–Wolfe Algorithms}
}
  42. Carderera, A., Pokutta, S., Schütte, C., and Weiser, M. (2021). CINDy: Conditional Gradient-based Identification of Non-linear Dynamics – Noise-robust Recovery. [arXiv]
    [BibTeX]
    @misc{2021_CardereraPokuttaSchutteWeiser_CINDy,
  archiveprefix = {arXiv},
  eprint = {2101.02630},
  primaryclass = {math.DS},
  year = {2021},
  author = {Carderera, Alejandro and Pokutta, Sebastian and SchĂĽtte, Christof and Weiser, Martin},
  title = {CINDy: Conditional Gradient-based Identification of Non-linear Dynamics -- Noise-robust Recovery}
}
  43. Kerdreux, T., d’Aspremont, A., and Pokutta, S. (2021). Local and Global Uniform Convexity Conditions. [arXiv]
    [BibTeX]
    @misc{2021_KerdrexDaspremontPokutta_LocalGlobalUniform,
  archiveprefix = {arXiv},
  eprint = {2102.05134},
  primaryclass = {math.OC},
  year = {2021},
  author = {Kerdreux, Thomas and d'Aspremont, Alexandre and Pokutta, Sebastian},
  title = {Local and Global Uniform Convexity Conditions}
}
  44. Roux, C., Wirth, E., Pokutta, S., and Kerdreux, T. (2021). Efficient Online-bandit Strategies for Minimax Learning Problems. [arXiv]
    [BibTeX]
    @misc{2021_RouxWirthPokuttaKerdreux_Onlinebanditminimax,
  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}
}
  45. Combettes, C., and Pokutta, S. (2020, March). Boosting Frank-Wolfe by Chasing Gradients. Proceedings of the International Conference on Machine Learning. [URL] [arXiv] [slides] [code] [video]
    [BibTeX]
    @inproceedings{2020_CombettesPokutta_BoostingFrankWolfe,
  year = {2020},
  booktitle = {Proceedings of the International Conference on Machine Learning},
  month = mar,
  url = {https://proceedings.mlr.press/v119/combettes20a.html},
  archiveprefix = {arXiv},
  eprint = {2003.06369},
  primaryclass = {math.OC},
  author = {Combettes, Cyrille and Pokutta, Sebastian},
  title = {Boosting Frank-Wolfe by Chasing Gradients},
  code = {https://github.com/cyrillewcombettes/boostfw},
  slides = {https://app.box.com/s/wwj247r5d456q0778p9b9y1jm6txuifb},
  video = {https://youtube.com/watch?v=BfyV0C5FRbE}
}
  46. Diakonikolas, J., Carderera, A., and Pokutta, S. (2020). Locally Accelerated Conditional Gradients. Proceedings of the International Conference on Artificial Intelligence and Statistics. [URL] [arXiv] [slides] [code]
    [BibTeX]
    @inproceedings{2019_DiakonikolasCardereraPokutta_BreakingCurse:1,
  year = {2020},
  booktitle = {Proceedings of the International Conference on Artificial Intelligence and Statistics},
  url = {https://proceedings.mlr.press/v108/diakonikolas20a/diakonikolas20a.pdf},
  archiveprefix = {arXiv},
  eprint = {1906.07867},
  primaryclass = {math.OC},
  author = {Diakonikolas, Jelena and Carderera, Alejandro and Pokutta, Sebastian},
  title = {Locally Accelerated Conditional Gradients},
  code = {https://colab.research.google.com/drive/1ejjfCan7xnEhWWJXCIzb03CwQRG9iW_O},
  slides = {https://app.box.com/s/gphkhapso7d1vrfnzqykkb3vx0agxh8w}
}
  47. Pokutta, S., Singh, M., and Torrico Palacios, A. (2020). On the Unreasonable Effectiveness of the Greedy Algorithm: Greedy Adapts to Sharpness. Proceedings of the International Conference on Machine Learning. [arXiv] [slides] [video]
    [BibTeX]
    @inproceedings{2019_PokuttaSinghTorrico_UnreasonableEffectiveness:1,
  year = {2020},
  booktitle = {Proceedings of the International Conference on Machine Learning},
  archiveprefix = {arXiv},
  eprint = {2002.04063},
  primaryclass = {cs.DS},
  author = {Pokutta, Sebastian and Singh, Mohit and Torrico Palacios, Alfredo},
  title = {On the Unreasonable Effectiveness of the Greedy Algorithm: Greedy Adapts to Sharpness},
  slides = {https://app.box.com/s/fmjxhfdpiqubm28upf563ohy8t8fgl3a},
  video = {https://youtube.com/watch?v=VB1e0HrDmVo}
}
  48. Carderera, A., and Pokutta, S. (2020). Second-order Conditional Gradient Sliding. [arXiv] [code]
    [BibTeX]
    @misc{2020_CarderaPokutta_SecondOrderConditional,
  archiveprefix = {arXiv},
  eprint = {2002.08907},
  primaryclass = {math.OC},
  year = {2020},
  author = {Carderera, Alejandro and Pokutta, Sebastian},
  title = {Second-order Conditional Gradient Sliding},
  code = {https://github.com/pokutta/Second-order-Conditional-Gradients}
}
  49. Combettes, C., Spiegel, C., and Pokutta, S. (2020). Projection-free Adaptive Gradients for Large-scale Optimization. [arXiv] [summary] [code]
    [BibTeX]
    @misc{2020_CombettesSpiegelPokutta_Projectionfreeadaptivegradients,
  archiveprefix = {arXiv},
  eprint = {2009.14114},
  primaryclass = {math.OC},
  year = {2020},
  author = {Combettes, Cyrille and Spiegel, Christoph and Pokutta, Sebastian},
  title = {Projection-free Adaptive Gradients for Large-scale Optimization},
  code = {https://github.com/ZIB-IOL/StochasticFrankWolfe},
  summary = {https://pokutta.com/blog/research/2020/10/21/adasfw.html}
}
  50. 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{2014_BraunPokuttaZink_Affinereductions,
  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}
}
  51. 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{2016_BraunPokuttaZink_Lazifyinggradientalgorithms,
  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}
}
  52. Braun, G., Pokutta, S., Tu, D., and Wright, S. (2019). Blended Conditional Gradients: the Unconditioning of Conditional Gradients. Proceedings of the International Conference on Machine Learning, 97, 735–743. [URL] [arXiv] [summary] [slides] [poster] [code]
    [BibTeX]
    @inproceedings{2018_BraunPokuttaTuStephen_Blendedconditionalgradients,
  year = {2019},
  booktitle = {Proceedings of the 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}
}
  53. Anari, N., Haghtalab, N., Naor, S., Pokutta, S., Singh, M., and Torrico Palacios, A. (2019). Structured Robust Submodular Maximization: Offline and Online Algorithms. Proceedings of the International Conference on Artificial Intelligence and Statistics. [URL] [arXiv]
    [BibTeX]
    @inproceedings{2019_AnariHaghtalabNaorPokuttaSinghTorrico_StructuredRobustSubmodular:1,
  year = {2019},
  booktitle = {Proceedings of the International Conference on Artificial Intelligence and Statistics},
  url = {https://proceedings.mlr.press/v89/anari19a/anari19a.pdf},
  archiveprefix = {arXiv},
  eprint = {1710.04740},
  primaryclass = {cs.DS},
  author = {Anari, N. and Haghtalab, N. and Naor, S. and Pokutta, Sebastian and Singh, Mohit and Torrico Palacios, Alfredo},
  title = {Structured Robust Submodular Maximization: Offline and Online Algorithms}
}
  54. Combettes, C., and Pokutta, S. (2019). Blended Matching Pursuit. Proceedings of the Conference on Neural Information Processing Systems. [URL] [arXiv] [slides] [code]
    [BibTeX]
    @inproceedings{2019_CombettesPokutta_BlendedMatching,
  year = {2019},
  booktitle = {Proceedings of the Conference on Neural Information Processing Systems},
  url = {https://papers.nips.cc/paper/8478-blended-matching-pursuit},
  archiveprefix = {arXiv},
  eprint = {1904.12335},
  primaryclass = {math.OC},
  author = {Combettes, Cyrille and Pokutta, Sebastian},
  title = {Blended Matching Pursuit},
  code = {https://colab.research.google.com/drive/17XYIxnCcJjKswba9mAaXFWnNGVZdsaXQ},
  slides = {https://app.box.com/s/8lfktq6h3dqp9t2gqydu2tp8h2uxgz7m}
}
  55. Diakonikolas, J., Carderera, A., and Pokutta, S. (2019). Breaking the Curse of Dimensionality (Locally) to Accelerate Conditional Gradients. Proceedings of the OPTML Workshop Paper. [URL] [arXiv] [slides] [code]
    [BibTeX]
    @inproceedings{2019_DiakonikolasCardereraPokutta_BreakingCurse,
  year = {2019},
  booktitle = {Proceedings of the OPTML Workshop Paper},
  url = {https://opt-ml.org/papers/2019/paper_26.pdf},
  archiveprefix = {arXiv},
  eprint = {1906.07867},
  primaryclass = {math.OC},
  author = {Diakonikolas, Jelena and Carderera, Alejandro and Pokutta, Sebastian},
  title = {Breaking the Curse of Dimensionality (Locally) to Accelerate Conditional Gradients},
  code = {https://colab.research.google.com/drive/1ejjfCan7xnEhWWJXCIzb03CwQRG9iW_O},
  slides = {https://app.box.com/s/gphkhapso7d1vrfnzqykkb3vx0agxh8w}
}
  56. Kerdreux, T., d’Aspremont, A., and Pokutta, S. (2019). Restarting Frank-Wolfe. Proceedings of the International Conference on Artificial Intelligence and Statistics. [URL] [arXiv] [slides]
    [BibTeX]
    @inproceedings{2019_KerdrexDaspremontPokutta_RestartingFrankWolfe:1,
  year = {2019},
  booktitle = {Proceedings of the International Conference on Artificial Intelligence and Statistics},
  url = {https://proceedings.mlr.press/v89/kerdreux19a/kerdreux19a.pdf},
  archiveprefix = {arXiv},
  eprint = {1810.02429},
  primaryclass = {math.OC},
  author = {Kerdreux, Thomas and d'Aspremont, Alexandre and Pokutta, Sebastian},
  title = {Restarting Frank-Wolfe},
  slides = {https://app.box.com/s/prd32r6xmuef2k4gah23rd0egllz9rv5}
}
  57. Pokutta, S., Singh, M., and Torrico Palacios, A. (2019). On the Unreasonable Effectiveness of the Greedy Algorithm: Greedy Adapts to Sharpness. Proceedings of the OPTML Workshop Paper. [URL] [arXiv] [slides] [video]
    [BibTeX]
    @inproceedings{2019_PokuttaSinghTorrico_UnreasonableEffectiveness,
  year = {2019},
  booktitle = {Proceedings of the OPTML Workshop Paper},
  url = {https://opt-ml.org/papers/2019/paper_16.pdf},
  archiveprefix = {arXiv},
  eprint = {2002.04063},
  primaryclass = {cs.DS},
  author = {Pokutta, Sebastian and Singh, Mohit and Torrico Palacios, Alfredo},
  title = {On the Unreasonable Effectiveness of the Greedy Algorithm: Greedy Adapts to Sharpness},
  slides = {https://app.box.com/s/fmjxhfdpiqubm28upf563ohy8t8fgl3a},
  video = {https://youtube.com/watch?v=VB1e0HrDmVo}
}
  58. 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{2015_BraunPokuttaRoy_Strongreductions,
  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}
}
  59. Le Bodic, P., Pfetsch, M., Pavelka, J., and Pokutta, S. (2018). Solving MIPs Via Scaling-based Augmentation. Discrete Optimization, 27, 1–25. DOI: 10.1016/j.disopt.2017.08.004 [arXiv]
    [BibTeX]
    @article{2018_LebodicPfetschPavelkaPokutta_SolvingMIPs,
  year = {2018},
  journal = {Discrete Optimization},
  volume = {27},
  pages = {1-25},
  doi = {10.1016/j.disopt.2017.08.004},
  archiveprefix = {arXiv},
  eprint = {1509.03206},
  primaryclass = {math.OC},
  author = {Le Bodic, P. and Pfetsch, Marc and Pavelka, Jeff and Pokutta, Sebastian},
  title = {Solving MIPs Via Scaling-based Augmentation}
}
  60. Pokutta, S., Singh, M., and Torrico Palacios, A. (2018). Efficient Algorithms for Robust Submodular Maximization Under Matroid Constraints. Proceedings of the ICML Workshop Paper. [URL] [arXiv]
    [BibTeX]
    @inproceedings{2018_PokuttaSinghTorrico_EfficientAlgorithms,
  year = {2018},
  booktitle = {Proceedings of the ICML Workshop Paper},
  url = {https://sites.google.com/view/icml2018nonconvex/papers},
  archiveprefix = {arXiv},
  eprint = {1807.09405},
  primaryclass = {cs.DS},
  author = {Pokutta, Sebastian and Singh, Mohit and Torrico Palacios, Alfredo},
  title = {Efficient Algorithms for Robust Submodular Maximization Under Matroid Constraints}
}
  61. 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{2015_BraunEtAl_MatchingproblemSdp,
  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}
}
  62. 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{2014_BraunGuzmanPokutta_Lowerboundsoraclecomplexity,
  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}
}
  63. Braun, G., Pokutta, S., and Zink, D. (2017). Lazifying Conditional Gradient Algorithms. Proceedings of the International Conference on Machine Learning, 70, 566–575. [URL] [arXiv] [slides] [poster]
    [BibTeX]
    @inproceedings{2016_BraunPokuttaZink_Lazifyinggradientalgorithms:1,
  year = {2017},
  booktitle = {Proceedings of the 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}
}
  64. 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{2017_BraunRahulTroyPokutta_Informationtheoreticnonnegativerank,
  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}
}
  65. Lan, G., Pokutta, S., Zhou, Y., and Zink, D. (2017). Conditional Accelerated Lazy Stochastic Gradient Descent. Proceedings of the International Conference on Machine Learning. [URL] [arXiv]
    [BibTeX]
    @inproceedings{2017_LanPokuttaZhouZink_ConditionalAccelerated,
  year = {2017},
  booktitle = {Proceedings of the International Conference on Machine Learning},
  url = {https://proceedings.mlr.press/v70/lan17a.html},
  archiveprefix = {arXiv},
  eprint = {1703.05840},
  primaryclass = {cs.LG},
  author = {Lan, G. and Pokutta, Sebastian and Zhou, Y and Zink, Daniel},
  title = {Conditional Accelerated Lazy Stochastic Gradient Descent}
}
  66. Roy, A., and Pokutta, S. (2017). Hierarchical Clustering Via Spreading Metrics. Journal of Machine Learning Research, 18, 1–35. [URL] [arXiv]
    [BibTeX]
    @article{2017_RoyPokutta_HierarchicalClustering,
  year = {2017},
  journal = {Journal of Machine Learning Research},
  volume = {18},
  pages = {1-35},
  url = {https://jmlr.org/papers/v18/17-081.html},
  archiveprefix = {arXiv},
  eprint = {1610.09269},
  primaryclass = {cs.LG},
  author = {Roy, Aurko and Pokutta, Sebastian},
  title = {Hierarchical Clustering Via Spreading Metrics}
}
  67. Braun, G., Pokutta, S., and Roy, A. (2016). Strong Reductions for Extended Formulations. Proceedings of the Conference on Integer Programming and Combinatorial Optimization, 9682, 350–361. DOI: 10.1007/978-3-319-33461-5_29 [arXiv]
    [BibTeX]
    @inproceedings{2015_BraunPokuttaRoy_Strongreductions:1,
  year = {2016},
  booktitle = {Proceedings of the 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}
}
  68. 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{2013_BraunSamuelPokutta_Averagepolyhedralcomplexity,
  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}
}
  69. 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{2016_BraunPokutta_CommoninformationDisjointness,
  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}
}
  70. 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]
    @article{2009_BraunPokutta_BorderbasesOrderidealsPolyhedral,
  year = {2016},
  journal = {SIAM Journal on Discrete Mathematics},
  volume = {30},
  number = {1},
  pages = {239–265},
  doi = {10.1137/140977990},
  archiveprefix = {arXiv},
  eprint = {0912.1502},
  primaryclass = {math.AC},
  author = {Braun, Gábor and Pokutta, Sebastian},
  title = {A Polyhedral Characterization of Border Bases}
}
  71. 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 the Symposium on Discrete Algorithms, 1067–1078. DOI: 10.1137/1.9781611974331.ch75 [arXiv]
    [BibTeX]
    @inproceedings{2015_BraunEtAl_MatchingproblemSdp:1,
  year = {2016},
  booktitle = {Proceedings of the 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}
}
  72. Braun, G., and Pokutta, S. (2016). An Efficient High-probability Algorithm for Linear Bandits. [arXiv]
    [BibTeX]
    @misc{2016_BraunPokutta_Highprobabilitylinearbandits,
  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}
}
  73. Roy, A., and Pokutta, S. (2016). Hierarchical Clustering Via Spreading Metrics. Proceedings of the Conference on Neural Information Processing Systems. [URL] [arXiv]
    [BibTeX]
    @inproceedings{2017_RoyPokutta_HierarchicalClustering:1,
  year = {2016},
  booktitle = {Proceedings of the Conference on Neural Information Processing Systems},
  url = {https://papers.nips.cc/paper/by-source-2016-1199},
  archiveprefix = {arXiv},
  eprint = {1610.09269},
  primaryclass = {cs.LG},
  author = {Roy, Aurko and Pokutta, Sebastian},
  title = {Hierarchical Clustering Via Spreading Metrics}
}
  74. 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{2012_BraunSamuelPokuttaSteurer_Approximationlimits,
  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 = {cs.CC},
  author = {Braun, Gábor and Firorini, Samuel and Pokutta, Sebastian and Steurer, David},
  title = {Approximation Limits of Linear Programs (beyond Hierarchies)}
}
  75. 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{2014_BraunPokuttaYao_Infogreedycompressedsensing,
  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}
}
  76. Braun, G., Pokutta, S., and Zink, D. (2015). Inapproximability of Combinatorial Problems Via Small LPs and SDPs. Proceedings of the Annual Symposium on Theory of Computing, 107–116. DOI: 10.1145/2746539.2746550 [arXiv] [video]
    [BibTeX]
    @inproceedings{2014_BraunPokuttaZink_Affinereductions:1,
  year = {2015},
  booktitle = {Proceedings of the 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}
}
  77. Braun, G., and Pokutta, S. (2015). The Matching Polytope Does Not Admit Fully-polynomial Size Relaxation Schemes. Proceedings of the Symposium on Discrete Algorithms, 837–846. DOI: 10.1137/1.9781611973730.57 [arXiv]
    [BibTeX]
    @inproceedings{2014_BraunPokutta_Matchingpolytope,
  year = {2015},
  booktitle = {Proceedings of the 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}
}
  78. Braun, G., Firorini, S., and Pokutta, S. (2014). Average Case Polyhedral Complexity of the Maximum Stable Set Problem. Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 28, 515–530. DOI: 10.4230/LIPIcs.APPROX-RANDOM.2014.515 [URL] [arXiv]
    [BibTeX]
    @inproceedings{2013_BraunSamuelPokutta_Averagepolyhedralcomplexity:1,
  year = {2014},
  booktitle = {Proceedings of the 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}
}
  79. Braun, G., Pokutta, S., and Xie, Y. (2014). Info-greedy Sequential Adaptive Compressed Sensing. Proceedings of the Allerton Conference on Communication, Control, and Computing (Allerton), 858–865. DOI: 10.1109/ALLERTON.2014.7028544 [arXiv]
    [BibTeX]
    @inproceedings{2014_BraunPokuttaYao_Infogreedycompressedsensing:1,
  year = {2014},
  booktitle = {Proceedings of the 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}
}
  80. Braun, G., and Pokutta, S. (2013). Common Information and Unique Disjointness. Proceedings of the IEEE Symposium on Foundations of Computer Science, 688–697. [URL]
    [BibTeX]
    @inproceedings{2016_BraunPokutta_CommoninformationDisjointness:1,
  year = {2013},
  booktitle = {Proceedings of the IEEE 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}
}
  81. Braun, G., and Pokutta, S. (2012). An Algebraic Approach to Symmetric Extended Formulations. Proceedings of the International Symposium on Combinatorial Optimization, 7422, 141–152. DOI: 10.1007/978-3-642-32147-4_14 [arXiv]
    [BibTeX]
    @inproceedings{2012_BraunPokutta_Algebraicsymmetricformulations,
  year = {2012},
  booktitle = {Proceedings of the 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}
}
  82. Braun, G., Firorini, S., Pokutta, S., and Steurer, D. (2012). Approximation Limits of Linear Programs (beyond Hierarchies). Proceedings of the IEEE Symposium on Foundations of Computer Science, 480–489. DOI: 10.1109/FOCS.2012.10 [arXiv]
    [BibTeX]
    @inproceedings{2012_BraunSamuelPokuttaSteurer_Approximationlimits:1,
  year = {2012},
  booktitle = {Proceedings of the IEEE Symposium on Foundations of Computer Science},
  pages = {480–489},
  doi = {10.1109/FOCS.2012.10},
  archiveprefix = {arXiv},
  eprint = {1204.0957},
  primaryclass = {cs.CC},
  author = {Braun, Gábor and Firorini, Samuel and Pokutta, Sebastian and Steurer, David},
  title = {Approximation Limits of Linear Programs (beyond Hierarchies)}
}
  83. 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]
    @article{2011_BraunPokutta_Randomhalfintegralpolytopes,
  year = {2011},
  journal = {Operations Research Letters},
  month = may,
  volume = {39},
  number = {3},
  pages = {204–207},
  doi = {10.1016/j.orl.2011.03.003},
  url = {https://optimization-online.org/2010/11/2813},
  author = {Braun, Gábor and Pokutta, Sebastian},
  title = {Random Half-integral Polytopes}
}
  84. Braun, G., and Pokutta, S. (2010). Rank of Random Half-integral Polytopes. Electronic Notes in Discrete Mathematics, 36, 415–422. DOI: 10.1016/j.endm.2010.05.053 [URL]
    [BibTeX]
    @article{2011_BraunPokutta_Randomhalfintegralpolytopes:1,
  year = {2010},
  journal = {Electronic Notes in Discrete Mathematics},
  month = aug,
  volume = {36},
  pages = {415–422},
  doi = {10.1016/j.endm.2010.05.053},
  url = {https://optimization-online.org/2010/11/2813},
  author = {Braun, Gábor and Pokutta, Sebastian},
  title = {Rank of Random Half-integral Polytopes}
}
  85. Braun, G., and Pokutta, S. (2009). A Polyhedral Approach to Computing Border Bases. [arXiv]
    [BibTeX]
    @misc{2010_BraunPokutta_PolyhedralApproach,
  archiveprefix = {arXiv},
  eprint = {0911.0859},
  primaryclass = {math.AC},
  year = {2009},
  author = {Braun, Gábor and Pokutta, Sebastian},
  title = {A Polyhedral Approach to Computing Border Bases}
}