Summary
Sampling from complex, curved shapes like those in some probability problems can be slow and tricky. This paper shows that following a special process called Gaussian cooling keeps the shape's spread stable along the way. Because of this stability, the authors improve how fast computers can start sampling from scratch. Their method reduces the time needed to almost n to the 2.5 power steps, better than previous known results.
What this means in practice
- •For machine learning engineers: Speed up initialization of algorithms that sample from complex probability models starting without prior knowledge.
- •For data scientists: Improve generation of synthetic data or uncertainty estimation by faster sampling of multidimensional logconcave distributions.
A theory result. No direct application yet.
Authors
Yunbum Kook, Santosh S. Vempala
Abstract
We show that logconcave probability measures along the Gaussian cooling path have thin-shell stability, generalizing the thin-shell theorem. This result leads to improved complexity for the fundamental problem of sampling an arbitrary logconcave distribution from a cold start. For (near-)isotropic logconcave distributions, the complexity is nearly $n^{2.5}$, improving the previous bound of $n^{2.75}$, and matching the complexity of the abstract Speedy walk.