The Entropic Barrier: A Simple and Optimal Universal Self-Concordant Barrier

  • Sébastien Bubeck ,
  • Ronen Eldan

|

Publication

We prove that the Cram\’er transform of the uniform measure on a convex body in Rn 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.