一种用于非光滑复合势函数的高效取样算法

Oct, 2019

一种用于非光滑复合势函数的高效取样算法

An Efficient Sampling Algorithm for Non-smooth Composite Potentials

Wenlong Mou, Nicolas Flammarion, Martin J. Wainwright, Peter L. Bartlett

TL;DR本文提出了一种基于Metropolis-Hastings框架的新算法，用于采样具有复合非平滑密度的分布，并针对这种新算法证明了在至多$O(d log(d/ε))$次迭代内将混合到距目标密度不超过Eps的总变差距离，而该方法的一个关键点在于使用了可用于大类非平滑函数G的一种新的近端基于提议分布的方法。

Abstract

We consider the problem of sampling from a density of the form $p(x) \propto \exp(-f(x)- g(x))$, where $f: \mathbb{R}^d \rightarrow \mathbb{R}$ is a smooth and strongly convex function and $g: \mathbb{R}^d \rightarrow \mathbb{R}$ is a convex and Lipschitz function. We propose a new alg

发现论文，激发创造

使用投影 Langevin 蒙特卡洛采样对数凹分布

通过投影步骤（与投影随机梯度下降类似），我们将Langevin Monte Carlo（LMC）算法扩展到紧支持测度。我们的主要结果特别表明，当目标分布是均匀分布时，LMC在$\tilde{O}(n^7)$步内混合。我们还提供初步的实验证据表明，LMC的表现至少与hit-and-run相当，而Lov{\'a}sz和Vempala证明了更好的混合时间为$\tilde{O}(n^4)$。

Jul, 2015

使用运动朗之万扩散从对数凹密度中采样

使用Langevin扩散过程进行离散化的蒙特卡洛算法可用于对光滑且强对数凹密度进行采样, 本文主要研究了这个框架, 并证明了基于kinetic Langevin扩散的Monte Carlo算法的混合性质和采样质量, 进一步证明了Hessian矩阵Lipschitz连续的情况下, 使用新的离散化方法可以显著提高采样误差的上界。

Jul, 2018

随机中点法用于对数凹采样

本研究提出了一种基于欠阻尼 Langevin 扩散的MCMC算法来解决从对数凹分布中采样问题，并设计了一种新的模拟随机微分方程的框架，该框架不仅可以解决对数凹采样问题，还可以应用于任何涉及模拟（随机）微分方程的问题。

Sep, 2019

带受限高斯序列预言的复合对数凹采样

本文提出了一种算法来从具有复合密度的分布中采样，这些密度由具有良好条件数的 $f$ 和凸（但可能不光滑）函数 $g$ 构成，这组密度通过受限高斯 oracle 的抽象来推广限制为凸集的约束。该算法是概念上简单的，实验表明其可显著优于 hit-and-run 算法用于采样（非对角线）高斯分布的正定方向区域限制。

Jun, 2020

对数拉普拉斯变换的算法特征及非欧几里得近端采样器

本文介绍了一种针对非欧几里得几何体的高效采样算法，该算法通过log-Laplace变换提供正则化性质，这种采样器匹配现有的欧几里得采样器，并在凸优化等领域表现出色。

Feb, 2023

通过正则化的Wasserstein近似实现无噪声采样算法

基于潜在函数模型抽样的显式基于评分的MCMC方法，以确定性的方式演化粒子，使用核卷积逼近的方法得到评分项，表现出快速收敛性和改进的维度依赖性相对于未调整的Langevin算法（ULA）和Metropolis调整的Langevin算法（MALA）的混合时间界限，在二次势函数下导出了每次迭代的分布的闭式表达，表征了方差降低，实证结果表明粒子以有序的方式行动，位于潜在函数的等值线上，此外，基于提出方法的后验均值估计器相对于ULA和MALA更接近最大后验估计器，在贝叶斯逻辑回归中表现出来。

Aug, 2023

Metropolis调整的镜像 Langevin 算法在有约束空间快速采样

我们提出了一种名为Metropolis-adjusted Mirror Langevin算法的新方法，用于从支持为紧凸集的分布中进行近似抽样。该算法在镜像Langevin算法（Zhang等人，2020）的单步离散化所产生的马尔可夫链中添加了接受-拒绝过滤器，而已知的镜像Langevin算法的离散化具有渐近偏差。当势函数相对平滑、凸且在自共轭镜像函数上满足Lipschitz条件时，我们给出了所提算法的混合时间的上界。作为算法产生的马尔可夫链可逆性的结果，我们对近似抽样的误差容限得到了指数级的改善依赖。我们还进行了数值实验以验证我们的理论发现。

Dec, 2023

非对数凹分布的零阶采样方法：通过去噪扩散缓解亚稳定性

非对数凹分布下的采样问题中，提出了一种基于非归一化密度查询的采样方法，通过模拟去噪扩散过程以及用通用蒙特卡罗估计器逼近其评分函数，构建了Diffusion Monte Carlo (DMC)框架。进一步，通过拒绝采样实现DMC的oracle，形成真正的算法Zeroth-Order Diffusion Monte Carlo (ZOD-MC)。在不假设目标分布为对数凹或满足任何等面积不等式的情况下，提供了DMC的收敛性分析。证明了ZOD-MC具有与所需采样精度的反多项式依赖关系，但仍然受到维度诅咒的影响。因此，在低维度分布中，ZOD-MC是一种高效的采样器，其性能超越了最新的采样器，包括基于去噪扩散的RDMC和RS-DMC。最后，实验证明ZOD-MC对于模态之间的高屏障或非凸势能的不连续性具有不敏感性。

Feb, 2024

基于先验扩散的Langevin算法在非对数凹采样问题中的改进分析

在这篇论文中，我们研究了应用于满足对数Sobolev不等式（LSI）的目标分布的先验扩散技术，证明了改进的 Langevin 算法在不同步长计划下能够获得与维度无关的 KL 散度收敛，并通过构建插值的 SDE 和准确描述过阻尼 Langevin 动力学离散更新的方法提供了理论分析的证明。我们的研究结果展示了先验扩散对更广泛类别的目标分布的优势，并为开发更快的采样算法提供了新的见解。

Mar, 2024

优化和采样的近端预言机

本文考虑了具有非光滑目标函数和具有非光滑潜势（负对数密度）的凸优化和对数凹取样问题，并研究了两个特定的设置，其中凸目标/潜势函数可以是半光滑的，也可以是复合形式，作为半光滑分量的有限和。为了克服非光滑性带来的挑战，我们的算法在优化和取样上使用了两种强大的近端框架：优化的近端点框架和使用增广分布上的Gibbs取样的交替取样框架（ASF）。优化和取样算法的关键组成部分是通过正则化割平面法对近端映射的高效实现。我们在半光滑和复合的两种情况下建立了近端映射的迭代复杂性。此外，我们还提出了一种适应性近端捆绑法用于非光滑优化。该方法是通用的，因为它不需要任何问题参数作为输入。此外，我们开发了一个类似于优化中近端映射的近端取样预测器，并使用一种新颖的技术（改进的高斯积分）建立了其复杂性。最后，我们将这个近端取样预测器和ASF结合起来，得到了一个在半光滑和复合设置中具有非渐近复杂性界限的马尔可夫链蒙特卡洛方法用于取样。

Apr, 2024