Fall 2021

Algorithms for Sampling Convex Bodies

Tuesday, Sep. 28, 2021 2:50 pm3:30 pm PDT

Add to Calendar


Aditi Laddha (Georgia Institute of Technology)


Calvin Lab Auditorium and Zoom

We discuss two Markov chain Monte Carlo algorithms for uniformly sampling convex bodies. The first is Gibbs sampling, also known as Coordinate Hit-and-Run (CHAR). In each step, the algorithm selects a random coordinate and re-samples that coordinate from the distribution induced by fixing all the other coordinates. This is joint work with Santosh Vempala. The second, weighted Dikin Walk, uses a convex barrier function, via its Hessian, to define an ellipsoid centered at each interior point of a convex body. At each step, it picks a uniformly random point in the ellipsoid centered at the current point. This is joint work with Yin Tat Lee and Santosh Vempala.