![statistics image](/sites/default/files/styles/max_325x325/public/2022-03/ev-stats_0.png?itok=w6pZu2aD)
Parallel sampling via counting
Sequoia Hall Room 200
I will talk about parallelization of sampling algorithms. The main focus of the talk will be a new result, where we show how to speed up sampling from an arbitrary distribution on a product space [q]^n, given oracle access to conditional marginals. Our algorithm takes roughly n^{2/3} polylog(n, q) parallel time, the first sublinear-in-n bound for arbitrary distributions. This suggests a roughly n^{1/3}-factor speedup is possible for sampling in any-order autoregressive models. We 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. Time permitting, I will also discuss results and conjectures about parallelization of other sampling algorithms, including some based on stochastic localization.
This is based on joint work with Aviad Rubinstein and Ruiquan Gao.