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

Abstract

We prove that the Cramér 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.

15 pages

References in corpus (1)

• Towards minimax policies for online linear optimization with bandit feedback

Cited by in corpus (2)

• Regret Analysis for Continuous Dueling Bandit
• Contextual Pandora's Box