Smoothed Picard method improves sampling from complex shapes
Smoothed Picard Hamiltonian Monte Carlo
Data Structures and AlgorithmsMachine Learning
Summary
Sampling from complicated high-dimensional shapes is important in fields like statistics but can be slow and inaccurate. The authors developed a new method that uses smoothing and improved iteration steps to produce samples more efficiently for a certain class of shapes. They provide mathematical guarantees on how accurate the samples are and how many steps the method needs. The technique also helps generate better starting points for another sampling method, improving overall accuracy.
What this means in practice
- •For machine learning engineers: Generate initial data samples efficiently for training probabilistic models with strongly log-concave objectives.
- •For financial modelers: Improve sampling techniques for risk models relying on high-dimensional log-concave distributions to produce faster simulations.
Authors
Fan Chen, Sinho Chewi, Jianfeng Lu, Matthew S Zhang
Abstract
We develop a new low-accuracy sampler, called \emph{smoothed Picard Hamiltonian Monte Carlo}, which combines Gaussian smoothing, Picard iteration, and higher-order discretization. For a log-concave target $π\propto \exp(-V)$ in dimension $d$ satisfying $0 \prec αI \preceq \nabla^2 V \preceq βI$, with condition number $κ:= β/α$, smoothed Picard HMC returns a sample with $\sqrt α\,W_2(\cdot,π) \le \varepsilon$ using $\widetilde O(κ^2 + κ^{7/6} d^{1/6}/\varepsilon^{1/3})$ gradient queries. We also prove stronger $W_q$ bounds, and then develop an algorithmic framework, the recursive warm start generator, to upgrade these $W_q$ bounds to stronger divergence guarantees. This produces a warm start for the proximal bouncy particle sampler, introduced in a companion work, leading to a high-accuracy log-concave sampler with complexity $\widetilde O((κ^{7/6} d^{1/6} + κ^{1/2} d^{1/4})\mathrm{polylog}(1/\varepsilon))$.