Home Page

Papers

Submissions

News

Editorial Board

Announcements

Proceedings

Open Source Software

Search

Login



RSS Feed

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

Sébastien Bubeck, Ronen Eldan
Proceedings of The 28th Conference on Learning Theory, pp. 279–279, 2015

Abstract

We prove that the Fenchel dual of the log-Laplace 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. The result also gives a new perspective on the minimax regret for the linear bandit problem.

Related Material