The entropic barrier: a simple and optimal universal self-concordant barrier

Sébastien Bubeck, Ronen Eldan
Proceedings of The 28th Conference on Learning Theory, PMLR 40:279-279, 2015.

Abstract

We prove that the Fenchel dual of the log-Laplace transform of the uniform measure on a convex body in \mathbbR^n is a (1+o(1)) n-self-concordant barrier, improving a seminal result of Nesterov and Nemirovski. This gives the first explicit construction of a universal barrier for convex bodies with optimal self-concordance parameter. The proof is based on basic geometry of log-concave distributions, and elementary duality in exponential families. The result also gives a new perspective on the minimax regret for the linear bandit problem.

Cite this Paper

BibTeX
@InProceedings{pmlr-v40-Bubeck15b, title = {The entropic barrier: a simple and optimal universal self-concordant barrier}, author = {Bubeck, Sébastien and Eldan, Ronen}, booktitle = {Proceedings of The 28th Conference on Learning Theory}, pages = {279--279}, year = {2015}, editor = {Grünwald, Peter and Hazan, Elad and Kale, Satyen}, volume = {40}, series = {Proceedings of Machine Learning Research}, address = {Paris, France}, month = {03--06 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v40/Bubeck15b.pdf}, url = {https://proceedings.mlr.press/v40/Bubeck15b.html}, abstract = {We prove that the Fenchel dual of the log-Laplace transform of the uniform measure on a convex body in \mathbbR^n is a (1+o(1)) n-self-concordant barrier, improving a seminal result of Nesterov and Nemirovski. This gives the first explicit construction of a universal barrier for convex bodies with optimal self-concordance parameter. The proof is based on basic geometry of log-concave distributions, and elementary duality in exponential families. The result also gives a new perspective on the minimax regret for the linear bandit problem.} }
Endnote
%0 Conference Paper %T The entropic barrier: a simple and optimal universal self-concordant barrier %A Sébastien Bubeck %A Ronen Eldan %B Proceedings of The 28th Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2015 %E Peter Grünwald %E Elad Hazan %E Satyen Kale %F pmlr-v40-Bubeck15b %I PMLR %P 279--279 %U https://proceedings.mlr.press/v40/Bubeck15b.html %V 40 %X We prove that the Fenchel dual of the log-Laplace transform of the uniform measure on a convex body in \mathbbR^n is a (1+o(1)) n-self-concordant barrier, improving a seminal result of Nesterov and Nemirovski. This gives the first explicit construction of a universal barrier for convex bodies with optimal self-concordance parameter. The proof is based on basic geometry of log-concave distributions, and elementary duality in exponential families. The result also gives a new perspective on the minimax regret for the linear bandit problem.
RIS
TY - CPAPER TI - The entropic barrier: a simple and optimal universal self-concordant barrier AU - Sébastien Bubeck AU - Ronen Eldan BT - Proceedings of The 28th Conference on Learning Theory DA - 2015/06/26 ED - Peter Grünwald ED - Elad Hazan ED - Satyen Kale ID - pmlr-v40-Bubeck15b PB - PMLR DP - Proceedings of Machine Learning Research VL - 40 SP - 279 EP - 279 L1 - http://proceedings.mlr.press/v40/Bubeck15b.pdf UR - https://proceedings.mlr.press/v40/Bubeck15b.html AB - We prove that the Fenchel dual of the log-Laplace transform of the uniform measure on a convex body in \mathbbR^n is a (1+o(1)) n-self-concordant barrier, improving a seminal result of Nesterov and Nemirovski. This gives the first explicit construction of a universal barrier for convex bodies with optimal self-concordance parameter. The proof is based on basic geometry of log-concave distributions, and elementary duality in exponential families. The result also gives a new perspective on the minimax regret for the linear bandit problem. ER -
APA
Bubeck, S. & Eldan, R.. (2015). The entropic barrier: a simple and optimal universal self-concordant barrier. Proceedings of The 28th Conference on Learning Theory, in Proceedings of Machine Learning Research 40:279-279 Available from https://proceedings.mlr.press/v40/Bubeck15b.html.

Related Material