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

Ronen Eldan and I have just uploaded our new paper on the arxiv (it should appear tomorrow, for the moment you can see it here). The abstract reads as follows:

We prove that the Fenchel dual of the log-Laplace transform of the uniform measure on a convex body in is a -self-concordant barrier. This gives the first 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.

Let me briefly put this in context. As you know if you are a reader of this blog, Interior Point Methods are based on self-concordant barriers, and a basic result in this theory is Nesterov and Nemirovski’s construction of a universal self-concordant barrier whose self-concordance parameter is always , see this blog post for instance. As I said at the time of writing the latter post, “this is a difficult theorem, which we state without a proof”. Similarly, in James Renegar’s book on IPM (which I highly recommend) he qualifies this as “a most impressive and theoretically important result”, but he also says “I have yet to find a relatively transparent proof of this result, and hence a proof is not contained in this book”. We hope our paper remedies this issue. In fact, our construction, which is quite different from the Nesterov-Nemirovski’s barrier, has a few advantages:

– The new barrier has a very simple interpretation as the differential entropy of a certain element in a canonical exponential family on the convex body of interest, hence the name entropic barrier.

– Its self-concordance parameter is optimal (up to the second order term). Indeed Nesterov and Nemirovski proved that on a simplex, the self-concordance parameter is at least , and we obtain a parameter for any convex body.

– The proof is reasonably easy. For instance the self-concordance follows immediately from the fact that higher order moments of a log-concave distribution are controlled by the second order moment. (In fairness getting the tight constant requires a little bit of work, but proving  a bound of is simpler.)

– Mirror Descent with the entropic barrier as a mirror map is equivalent to Cover’s continuous exponential weights, which is kind of interesting.

I would like to conclude with a comment on a result by Roland Hildebrand: he proves that for convex cones, there exists a self-concordant barrier with parameter smaller than (yes I mean ). This is quite amazing, and better than what we obtain since we get . However his result has two caveats: (i) as far as I understand his barrier is defined only implicitely, as the unique convex solution to a certain PDE, and (ii) while convex cones are “universal” for convex optimization, there are actually other applications where it is important to have barriers on convex bodies, see for instance some of the papers by Sasha Rakhlin. [Edit: thanks to an email by Francois Glineur we realized that a side result of our analysis is an alternative proof of Hildebrand’s bound for homogeneous cones by using a deep result of Guler. This is very mysterious and we don’t quite understand the full extent of the implication of this yet.]