Dec, 2023

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

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

    我们提出了一种新的镜像随机 Langevin 扩散离散化方法，并给出了其收敛性的确定证明。

    Oct, 2020

  • 镜子 Langevin 算法在消失偏差时收敛

    该研究探讨了优化中将问题的几何形状从欧几里得度量变为黑塞度量的技术，并研究了基于镜面流的镜面 Langevin 算法的偏差收敛性和混合时间界限。研究表明，这种算法可以通过自协调条件来实现收敛。

    Sep, 2021

  • Metropolis-adjusted Langevin 算法的非凸采样

    本文提出的正则性条件使我们能够在许多统计和机器学习应用中获取更快的边界。其中包括使用弱凸先验分布的贝叶斯逻辑回归和学习 0-1 损失函数的线性分类器的非凸优化问题。本文的主要技术贡献是我们通过能量守恒误差对 MALA 的 Metropolis 接受概率进行分析，并通过三阶和四阶正则性条件限制该误差。

    Feb, 2019

  • 对数凹采样：Metropolis-Hastings 算法速度快

    研究了如何从强对数凹密度分布中进行采样，并证明了使用 Metropolis-adjusted Langevin 算法（MALA）混合时间的非渐近上界。结果表明 MALA 与未调整的 Langevin 算法（ULA）相比，使用接受 - 拒绝步骤可以在误差容限上实现指数级改进。此外，我们提供了一些数字例子来支持我们的理论发现，并证明了适应 Metropolis-Hastings 调整的 Langevin 类型采样算法的好处。

    Jan, 2018

  • 镜像 Langevin 动力学

    研究了从受限分布中采样的问题，提出了一种统一的框架来导出新的一阶采样方案，并应用于 Dirichlet posteriors 中，证明了第一阶算法实现了收敛性，最后在真实数据集上报告了有希望的实验结果。

    Feb, 2018

  • 近端马尔可夫链蒙特卡罗算法

    该论文提出了新的 Metropolis-adjusted Langevin 算法 (MALA)，利用凸分析高效地模拟从高维度密度中提取属于对数凹集的样本，可应用于高维、不连续可微分的密度分布，在图像处理和机器学习领域有重要应用价值。

    Jun, 2013

  • 镜像 Langevin Monte Carlo 的 Wasserstein 控制

    本研究主要探讨了在 Hessian 型流形上的 Langevin 扩散过程与镜像下降的关系，运用该理论推导出了 Hessian Riemannian Langevin Monte Carlo 算法的非渐进抽样误差上限并证明了其适用性。

    Feb, 2020

  • 镜像朗之万扩散的指数遍历性

    研究了一种从不合适条件的对数凹分布中进行采样的方法，证明了其具有无关维数和目标分布的快速收敛速率，进一步应用于优化中，提供了一种基于内点法的策略来从凸体上分布中进行均匀分布采样，这一方法新颖性的体现在于指出了 chi-squared divergence 的作用，为朴素 Langevin 漂移在 Wasserstein 距离内的收敛提供了新的结果。

    May, 2020

  • 加速 Langevin 动力学的近端算法

    基于随机化的 Nesterov 方案，我们开发了一类新颖的 MCMC 算法。我们通过适当地添加噪声，得到了一种时间非齐次的欠阻尼 Langevin 方程，并证明它的不变测度是一个指定的目标分布。同时，我们还建立了它在 Wasserstein-2 距离下的收敛速率。我们还提供了调整的 Metropolis 和随机梯度版本的所提出的 Langevin 动力学。实验演示显示出所提出的方法在统计学和图像处理中不同模型上优于典型的 Langevin 抽样器，包括更好的 Markov 链混合性能。

    Nov, 2023

  • 针对良好条件分布的 Metropolized 采样方法下限

    给出了使用两种蒙特卡罗采样方法（MALA 和 HMC）在良好条件的分布下性能的下界，并确定了每种方法的最短混合时间和松弛时间。该文还发现了跃点积分和 Chebyshev 多项式之间的新连接。

    Jun, 2021