High-Accuracy Sampling with First-Order Information

Thomas M. Menino Convention & Exhibition Center 

Optimization and sampling are often treated as closely related computational problems, but their high-accuracy behavior can be strikingly different. With noisy gradients, optimization generally requires polynomially many queries in the inverse accuracy. I will show that sampling can instead achieve polylogarithmic dependence, even using only stochastic first-order information. The key tool is a
first-order rejection sampler (FORS), which replaces function-value evaluations by randomized path-integral estimators of potential differences. Combined with the proximal sampler, this yields
high-accuracy algorithms for log-concave distributions and diffusion models.