The entropic barrier: a simple and optimal universal self-concordant barrier
author: Sébastien Bubeck,
Department of Operations Research and Financial Engineering, Princeton University
published: Aug. 20, 2015, recorded: July 2015, views: 2666
published: Aug. 20, 2015, recorded: July 2015, views: 2666
Related content
Report a problem or upload files
If you have found a problem with this lecture or would like to send us extra material, articles, exercises, etc., please use our ticket system to describe your request and upload the data.Enter your e-mail into the 'Cc' field, and we will keep you updated with your request's status.
Description
We prove that the Fenchel dual of the log-Laplace transform of the uniform measure on a convex body in $\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.
Link this page
Would you like to put a link to this lecture on your homepage?Go ahead! Copy the HTML snippet !
Write your own review or comment: