Randomized Interior Point Methods for Sampling and Optimization


June 24, 2015


Hariharan Narayanan


Statistics and Mathematics departments at UW


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.


Hariharan Narayanan

Hari Narayanan received a dual degree in Electrical Engineering from IIT Bombay and Masters and PhD in Computer Science from the University of Chicago. After postdocs at MIT and Princeton, he now is jointly an assistant professor in the Statistics and Mathematics departments at UW. His current interests include randomized interior point methods and fitting low dimensional manifolds to high dimensional data.