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 = {Sébastien Bubeck and Ronen Eldan}, booktitle = {Proceedings of The 28th Conference on Learning Theory}, pages = {279--279}, year = {2015}, editor = {Peter Grünwald and Elad Hazan and Satyen Kale}, 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 = {http://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 %J Proceedings of Machine Learning Research %P 279--279 %U http://proceedings.mlr.press %V 40 %W PMLR %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 PY - 2015/06/26 DA - 2015/06/26 ED - Peter Grünwald ED - Elad Hazan ED - Satyen Kale ID - pmlr-v40-Bubeck15b PB - PMLR SP - 279 DP - PMLR EP - 279 L1 - http://proceedings.mlr.press/v40/Bubeck15b.pdf UR - http://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 PMLR 40:279-279

Related Material