Gábor Braun
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Gábor Braun has a total of 16 co-authors. Here are the top co-authors by number of shared publications:
- Sebastian Pokutta
Zuse Institute Berlin
14 shared publications - Lutz Strüngmann
Institute of Mathematical Biology, Faculty for Computer Sciences, Mannheim University of Applied Sciences, Mannheim, Germany
4 shared publications Aurko Roy
Georgia Institute of Technology
2 shared publications- Samuel Fiorini
Universite Libre de Bruxelles
2 shared publications - Aurko Roy
College of Computing Georgia Institute of Technology Atlanta GA USA
1 shared publication - Brendan Goldsmith
Dublin Institute of Technology
1 shared publication
Latest Publications
- 1 June 2019
- Published by Elsevier in Journal of Algebra
- Vol. 528, 72-84
Decompositions of torsion-free abelian groups
- 1 June 2019
- Published by Elsevier in Journal of Algebra
- Vol. 528, 72-84
Decompositions of torsion-free abelian groups
- Open Access
Blended Conditional Gradients: the unconditioning of conditional gradients
We present a blended conditional gradient approach for minimizing a smooth convex function over a polytope P, combining the Frank--Wolfe algorithm (also called conditional gradient) with gradient-based steps, different from away steps and pairwise steps, but still achieving linear convergence for strongly convex functions, along with good practical performance. Our approach retains all favorable properties of conditional gradient algorithms, notably avoidance of projections onto P and maintenance of iterates as sparse convex combinations of a limited number of extreme points of P. The algorithm is lazy, making use of inexpensive inexact solutions of the linear programming subproblem that characterizes the conditional gradient approach. It decreases measures of optimality (primal and dual gaps) rapidly, both in the number of iterations and in wall-clock time, outperforming even the lazy conditional gradient algorithms of [arXiv:1410.8816]. We also present a streamlined version of the algorithm for the probability simplex.
Open AccessBlended Conditional Gradients: the unconditioning of conditional gradients
We present a blended conditional gradient approach for minimizing a smooth convex function over a polytope P, combining the Frank--Wolfe algorithm (also called conditional gradient) with gradient-based steps, different from away steps and pairwise steps, but still achieving linear convergence for strongly convex functions, along with good practical performance. Our approach retains all favorable properties of conditional gradient algorithms, notably avoidance of projections onto P and maintenance of iterates as sparse convex combinations of a limited number of extreme points of P. The algorithm is lazy, making use of inexpensive inexact solutions of the linear programming subproblem that characterizes the conditional gradient approach. It decreases measures of optimality (primal and dual gaps) rapidly, both in the number of iterations and in wall-clock time, outperforming even the lazy conditional gradient algorithms of [arXiv:1410.8816]. We also present a streamlined version of the algorithm for the probability simplex.
- 2 April 2019
- Published by Elsevier in Journal of Algebra
- Vol. 529, 114-123
Some transitivity-like concepts in Abelian groups
- 2 April 2019
- Published by Elsevier in Journal of Algebra
- Vol. 529, 114-123
Some transitivity-like concepts in Abelian groups
- Open Access
Decompositions of torsion-free abelian groups
It is known that every torsion-free abelian group of finite rank has a maximal completely decomposable summand that is unique up to isomorphism. We show that groups of infinite rank need not have maximal completely decomposable summands, but when they do, this summand is unique up to isomorphism.
Open AccessDecompositions of torsion-free abelian groups
It is known that every torsion-free abelian group of finite rank has a maximal completely decomposable summand that is unique up to isomorphism. We show that groups of infinite rank need not have maximal completely decomposable summands, but when they do, this summand is unique up to isomorphism.
- 25 August 2018
- Published by Springer Nature in Mathematical Programming
- Vol. 172 (1-2) , 591-620
Strong reductions for extended formulations
- 25 August 2018
- Published by Springer Nature in Mathematical Programming
- Vol. 172 (1-2) , 591-620
Strong reductions for extended formulations
- 4 June 2017
- Published by Springer Nature
- p. 69-81
Rigid ℵ1-Free Abelian Groups with Prescribed Factors and Their Role in the Theory of Cellular Covers
- 4 June 2017
- Published by Springer Nature
- p. 69-81
Rigid ℵ1-Free Abelian Groups with Prescribed Factors and Their Role in the Theory of Cellular Covers
- Open Access
An efficient high-probability algorithm for Linear Bandits
For the linear bandit problem, we extend the analysis of algorithm CombEXP from [R. Combes, M. S. Talebi Mazraeh Shahi, A. Proutiere, and M. Lelarge. Combinatorial bandits revisited. In C. Cortes, N. D. Lawrence, D. D. Lee, M. Sugiyama, and R. Garnett, editors, Advances in Neural Information Processing Systems 28, pages 2116--2124. Curran Associates, Inc., 2015. URL http://papers.nips.cc/paper/5831-combinatorial-bandits-revisited.pdf] to the high-probability case against adaptive adversaries, allowing actions to come from an arbitrary polytope. We prove a high-probability regret of \(O(T^{2/3})\) for time horizon \(T\). While this bound is weaker than the optimal \(O(\sqrt{T})\) bound achieved by GeometricHedge in [P. L. Bartlett, V. Dani, T. Hayes, S. Kakade, A. Rakhlin, and A. Tewari. High-probability regret bounds for bandit online linear optimization. In 21th Annual Conference on Learning Theory (COLT 2008), July 2008. http://eprints.qut.edu.au/45706/1/30-Bartlett.pdf], CombEXP is computationally efficient, requiring only an efficient linear optimization oracle over the convex hull of the actions.Open AccessAn efficient high-probability algorithm for Linear Bandits
For the linear bandit problem, we extend the analysis of algorithm CombEXP from [R. Combes, M. S. Talebi Mazraeh Shahi, A. Proutiere, and M. Lelarge. Combinatorial bandits revisited. In C. Cortes, N. D. Lawrence, D. D. Lee, M. Sugiyama, and R. Garnett, editors, Advances in Neural Information Processing Systems 28, pages 2116--2124. Curran Associates, Inc., 2015. URL http://papers.nips.cc/paper/5831-combinatorial-bandits-revisited.pdf] to the high-probability case against adaptive adversaries, allowing actions to come from an arbitrary polytope. We prove a high-probability regret of \(O(T^{2/3})\) for time horizon \(T\). While this bound is weaker than the optimal \(O(\sqrt{T})\) bound achieved by GeometricHedge in [P. L. Bartlett, V. Dani, T. Hayes, S. Kakade, A. Rakhlin, and A. Tewari. High-probability regret bounds for bandit online linear optimization. In 21th Annual Conference on Learning Theory (COLT 2008), July 2008. http://eprints.qut.edu.au/45706/1/30-Bartlett.pdf], CombEXP is computationally efficient, requiring only an efficient linear optimization oracle over the convex hull of the actions. - 23 May 2016
- Published by Springer Nature in computational complexity
- Vol. 26 (1) , 147-197
Information-theoretic approximations of the nonnegative rank
- 23 May 2016
- Published by Springer Nature in computational complexity
- Vol. 26 (1) , 147-197
Information-theoretic approximations of the nonnegative rank
- 25 March 2016
- Published by Springer Nature in Mathematical Programming
- Vol. 160 (1-2) , 407-431
Average case polyhedral complexity of the maximum stable set problem
- 25 March 2016
- Published by Springer Nature in Mathematical Programming
- Vol. 160 (1-2) , 407-431
Average case polyhedral complexity of the maximum stable set problem