Theoretical Guarantees for MCMC Algorithms

Drawing samples from a known distribution is a core computational challenge common to many disciplines, with applications in statistics, probability, perations research, and other areas involving stochastic models. Recent decades have witnessed great success of Markov Chain Monte Carlo (MCMC) algorithms suited for generating random samples. However, the theoretical understanding of MCMC algorithms used in practice is far from complete. In this talk, we present several results that attempt to develop a better understanding of sampling algorithms and make a beautiful connection between the task of optimization and random sampling.

In the first part of the talk, we discuss two new MCMC sampling algorithms, the Vaidya walk and the John walk, for generating samples from the uniform distribution over a polytope. Both random walks are sampling algorithms derived from interior point methods. In the second part of the talk, we discuss the power of accept-reject step in MCMC algorithms for the task of sampling from log-concave distributions. We show that for Langevin algorithms, using the accept-reject step provides an exponential gain in the convergence rate. Our results are explicit and non asymptotic in nature which improve upon the prior work in the literature. We validate our theoretical findings in practice via several experiments (this talk is based on joint work with Yuansi Chen, Martin Wainwright and Bin Yu)..

Bio: Raaz Dwivedi is a third year PhD student in the department of Electrical Engineering and Computer Science at University of California, Berkeley, under the joint supervision of Prof Martin Wainwright and Prof Bin Yu. He received a B. Tech. in Electrical Engineering from IIT Bombay in 2014. He received the President of India Gold Medal, Institute Silver Medal and the Best B. Tech. Project award in 2014 at IIT Bombay. He is also a recipient of the Berkeley Fellowship in 2015 and was one of the US Junior Oberwolfach Fellows in 2017.