Faster accurate sampling from complex data with warm start methods
Accelerated High-Accuracy Sampling from a Warm Start via the Proximal Bouncy Particle Sampler
Data Structures and AlgorithmsMachine Learning
Summary
When computers need to understand messy, high-dimensional data better, they often use a process called sampling from a probability distribution. This paper introduces a new way to do this faster and more accurately, especially when starting close to the solution. The authors combined two previous methods to create the Proximal Bouncy Particle Sampler, which requires fewer calculations to get a good sample. This can speed up many computational tasks that rely on sampling.
What this means in practice
- •For machine learning engineers: Generate high-quality samples from complex models more efficiently by using the faster Proximal Bouncy Particle Sampler with warm starts.
- •For statistical data analysts: Perform faster Bayesian inference by sampling with improved convergence guarantees in strongly convex and smooth settings.
Authors
Fan Chen, Sinho Chewi, Jianfeng Lu, Matthew S Zhang
Abstract
We study the problem of sampling from $μ(\mathrm{d}x)\propto e^{-V(x)}\,\mathrm{d}x$ on $\mathbb{R}^d$, where $V$ is $α$-strongly convex and $β$-smooth, and write $κ:=β/α$. We design and analyze the Proximal Bouncy Particle Sampler (Proximal BPS), a new sampler that combines ideas from the proximal sampler and the bouncy particle sampler. From a warm start initialization with $ O(1) $ Rényi divergence w.r.t. $μ$, Proximal BPS returns a sample whose law is $\varepsilon$-close to $μ$ in total variation distance using $\widetilde O(\sqrtκ\,d^{1/4} \,\mathrm{polylog}(1/\varepsilon))$ gradient queries in expectation.