Randomized Interior Point Methods for Sampling and Optimization

Опубликовано 21 июня 2016, 23:54

We present a Markov Chain, "Dikin walk", for sampling from a convex body equipped with a self-concordant barrier. This Markov Chain corresponds to a natural random walk with respect to a Riemannian metric defined using the Hessian of the barrier function. For every convex set of dimension n, there exists a self-concordant barrier whose self-concordance parameter is O(n). Consequently, a rapidly mixing Markov Chain of the kind we describe can be defined (but not always be efficiently implemented) on any convex set. We use these results to design an algorithm consisting of a single random walk for optimizing a linear function on a convex set. This talk includes joint work with Ravi Kannan and Alexander Rakhlin.