Randomized Interior Point methods for Sampling and Optimization

Hariharan Narayanan

We present a Markov chain (Dikin walk) for sampling from a convex body equipped with a self-concordant barrier, whose mixing time from a "central point" is strongly polynomial in t…