The Entropic Barrier: A Simple and Optimal Universal Self-Concordant Barrier
Abstract
We prove that the Cramer transform of the uniform measure on a convex body in $\mathbb{R}^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.
Cite
Text
Bubeck and Eldan. "The Entropic Barrier: A Simple and Optimal Universal Self-Concordant Barrier." Annual Conference on Computational Learning Theory, 2015.Markdown
[Bubeck and Eldan. "The Entropic Barrier: A Simple and Optimal Universal Self-Concordant Barrier." Annual Conference on Computational Learning Theory, 2015.](https://mlanthology.org/colt/2015/bubeck2015colt-entropic/)BibTeX
@inproceedings{bubeck2015colt-entropic,
title = {{The Entropic Barrier: A Simple and Optimal Universal Self-Concordant Barrier}},
author = {Bubeck, Sébastien and Eldan, Ronen},
booktitle = {Annual Conference on Computational Learning Theory},
year = {2015},
pages = {279},
url = {https://mlanthology.org/colt/2015/bubeck2015colt-entropic/}
}