论文标题
受到限制的采样
Penalized Overdamped and Underdamped Langevin Monte Carlo Algorithms for Constrained Sampling
论文作者
论文摘要
我们考虑了受约束的采样问题，即目标是从目标分布中取样$π（x）\ propto e^{ - f（x）} $当$ x $约束以躺在凸面$ \ mathcal {c} $上时。由连续优化的惩罚方法激发，我们提出了受到惩罚的Langevin Dynamics（PLD），并受到惩罚不足的Langevin Monte Carlo（PULMC）方法，该方法将约束采样问题转换为不受限制的采样问题，通过引入惩罚功能，以造成约束违法的惩罚功能。当$ f $平稳且可用时，我们会得到$ \ tilde {\ nathcal {o}}（d/\ varepsilon^{10}）$ itseration $ itseration complactity pld以$ \ varepsilon $ -Error对目标进行采样，以便在电视距离和$ \ tilde cdiLde cdiLde cdc {对数因素。对于PULMC，我们将结果提高到$ \ tilde {\ Mathcal {o}}（\ sqrt {d}/\ varepsilon^{7}）$当$ f $的Hessian是Lipschitz的Hessian and lipschitz和$ \ nathcal {c} $的边界时，就足够了。据我们所知，这些是在处理非convex $ f $的受约束抽样中引导不足的Langevin Monte Carlo方法的第一个收敛结果，并提供了具有确定性梯度的现有方法之间的最佳维度依赖性。如果可以使用$ f $的梯度的无偏随机估计，我们建议使用可以处理随机梯度的PSGLD和PSGULMC方法，并且不需要大都市施加校正步骤，并且可以对大型数据集进行扩展。对于PSGLD和PSGULMC，当$ f $强烈凸出且平稳时，我们获得了$ \ tilde {\ Mathcal {o}}}}（d/\ varepsilon^{18}）$和$ \ tilde {\ tilde {\ natercal {\ mathcal {o}}（o}}（d \ sqrt} $} $} W2距离的复杂性。当$ f $平稳并且可能是非凸件时，我们会提供有限的时间性能和迭代复杂性结果。最后，我们说明了贝叶斯套索回归的表现，贝叶斯限制了深度学习问题。
We consider the constrained sampling problem where the goal is to sample from a target distribution $π(x)\propto e^{-f(x)}$ when $x$ is constrained to lie on a convex body $\mathcal{C}$. Motivated by penalty methods from continuous optimization, we propose penalized Langevin Dynamics (PLD) and penalized underdamped Langevin Monte Carlo (PULMC) methods that convert the constrained sampling problem into an unconstrained sampling problem by introducing a penalty function for constraint violations. When $f$ is smooth and gradients are available, we get $\tilde{\mathcal{O}}(d/\varepsilon^{10})$ iteration complexity for PLD to sample the target up to an $\varepsilon$-error where the error is measured in the TV distance and $\tilde{\mathcal{O}}(\cdot)$ hides logarithmic factors. For PULMC, we improve the result to $\tilde{\mathcal{O}}(\sqrt{d}/\varepsilon^{7})$ when the Hessian of $f$ is Lipschitz and the boundary of $\mathcal{C}$ is sufficiently smooth. To our knowledge, these are the first convergence results for underdamped Langevin Monte Carlo methods in the constrained sampling that handle non-convex $f$ and provide guarantees with the best dimension dependency among existing methods with deterministic gradient. If unbiased stochastic estimates of the gradient of $f$ are available, we propose PSGLD and PSGULMC methods that can handle stochastic gradients and are scaleable to large datasets without requiring Metropolis-Hasting correction steps. For PSGLD and PSGULMC, when $f$ is strongly convex and smooth, we obtain $\tilde{\mathcal{O}}(d/\varepsilon^{18})$ and $\tilde{\mathcal{O}}(d\sqrt{d}/\varepsilon^{39})$ iteration complexity in W2 distance. When $f$ is smooth and can be non-convex, we provide finite-time performance bounds and iteration complexity results. Finally, we illustrate the performance on Bayesian LASSO regression and Bayesian constrained deep learning problems.
