Penalized nonreversible methods speed up constrained sampling tasks
Penalized Nonreversible Langevin for Constrained Sampling
Machine Learning
Summary
Sampling complex data shapes with strict boundaries is often difficult and slow. This paper offers a way to use a special kind of guided random walk, called penalized nonreversible Langevin dynamics, to explore such spaces more efficiently. The authors show mathematically that their method quickly approaches the desired sampling distribution, even when approximations are involved. They also find settings where their method works noticeably faster than traditional approaches. Finally, they test their ideas on various problems including Bayesian statistics and neural networks.
What this means in practice
- •For machine learning engineers: Improve efficiency of sampling methods for constrained Bayesian regression and classification problems using this penalized nonreversible Langevin algorithm.
- •For statistical data scientists: Accelerate sampling from constrained distributions to better evaluate uncertainty in models with domain restrictions.
Authors
Pervez Ali, Weihao Dong, Xiaoyu Wang
Abstract
We propose penalized nonreversible Langevin algorithms for sampling from $π(x)\propto e^{-f(x)}\mathbf 1_{\mathcal C}(x)$, where $\mathcal C\subset\mathbb R^d$ is a compact convex set. The algorithms combine a squared distance penalty with constant or compatible state dependent skew symmetric perturbations that preserve the penalized Gibbs distribution. For smooth, possibly nonconvex $f$, we derive nonasymptotic total variation bounds for the full gradient algorithm under a log Sobolev inequality. When unbiased stochastic gradients are available, we establish $2$-Wasserstein bounds under global contraction and Lipschitz conditions on the full drift in an adapted quadratic metric. For a fixed penalty parameter, the error relative to the penalized Gibbs distribution decays exponentially to an $\mathcal{O}(\sqrtη)$ neighborhood, where $η$ is the stepsize. We also bound the discrepancy between the penalized Gibbs distribution and the constrained target. In a two dimensional quadratic model, we establish nonreversible acceleration by tuning the skew perturbation to the curvature imbalance induced by penalization. With the target accuracy and smaller curvature fixed and initial Wasserstein distances uniformly bounded, tuning the skew perturbation improves the sufficient Euler iteration bound from linear to logarithmic in the curvature ratio. Numerical experiments evaluate the algorithms on constrained Bayesian regression, classification, neural networks, and truncated sampling, and examine the acceleration mechanism in a stochastic quadratic model.