Randomized Interior Point Methods for Sampling and Optimization

  • 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.

Speaker Details

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.

    • Portrait of Jeff Running

      Jeff Running

Series: Microsoft Research Talks