EVENT DETAILS AND ABSTRACT

Title: Parallel sampling
Speaker: Nima Anari
Speaker Info: Stanford University
Brief Description: Parallel sampling
Special Note:
Abstract:

I will talk about the parallelization of sampling algorithms. The main focus will be a new result that shows how to speed up sampling from an arbitrary distribution on a product space [q]^n, given oracle access to conditional marginals, as in any-order autoregressive models. The algorithm takes n^{2/3} polylog(n, q) parallel time, the first sublinear-in-n bound for arbitrary distributions. We also show a lower bound of n^{1/3} on the parallel runtime of any algorithm, putting the complexity firmly in the sublinear but polynomially large territory. I will also discuss results and conjectures about the parallelization of other sampling algorithms, including some based on stochastic localization, a.k.a. the denoising diffusion process. Based on joint work with Aviad Rubinstein and Ruiquan Gao.