Talks
Fall 2021

Algorithms for Sampling Convex Bodies

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

Add to Calendar

Speaker: 

Aditi Laddha (Georgia Institute of Technology)

Location: 

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.