Oct, 2017

基于多面体的快速 MCMC 采样算法

PDF
TL;DR该研究提出并分析了两种新的 MCMC 抽样算法，即 Vaidya walk 和 John walk，用于从多面体上生成样本。其中提出的 Vaidya walk 算法的混合时间比过去的 Dikin walk 的混合时间少得多，混合时间上界为 O (n^0.5*d^1.5)。在数值例子中，Vaidya 步行的加速超过了 Dikin 步行。
mcmc samplingpolytopevaidya walkjohn walkmixing time
发现论文，激发创造
  • 针对良好条件分布的 Metropolized 采样方法下限

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

    Jun, 2021

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

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

    Jan, 2018

  • 入出之间：用于凸体采样的算法扩散

    提出了一种新的随机行走方法，用于均匀采样高维凸体；它在输出方面具有比之前已知的方法更强的保证，特别是在 Rényi 散度方面。证明与现有的问题的多项式时间算法方法不同，我们利用了随机扩散的视角，通过收敛性的速率与平稳密度的功能等周常数来显示到目标分布的收缩。

    May, 2024

  • 用度量的 Dikin Walk 高效采样 PSD 空间锥

    半定规划和优化中的采样过程，使用 Dikin 行走和内点方法结合，通过适当的指标选择，可以在多项式对数的复杂度下减少混合时间和步骤复杂度。

    Jul, 2023

  • 常数条件下对数凹密度的常微分方程算法理论与采样

    本文提出了一种近似线性的多元常微分方程算法，用于解决样本采集问题，特别是针对 Hamiltonian Monte Carlo 的多维 logconcave 密度函数，拥有多项式对数深度。

    Dec, 2018

  • 非对数凹分布的 MCMC 算法快速条件混合

    本文研究 MCMC 算法的 mixing rate 问题，并根据 Poincaré inequality 定理，展示 MCMC 算法在 state space 的 subset 上的条件概率分布上快速逼近真实条件分布的能力，进而探讨该理论在高斯混合模型采样和 Gibbs 采样中的应用。

    Jun, 2023

  • 通过在 Wasserstein 空间中的多面体优化实现均场变分推断的算法

    有限维多面体子集、Wasserstein 空间、均场变分推断、最小化算法和 KL 散度。

    Dec, 2023

  • 基于随机中点的更快扩散采样：连续和并行

    近年来，在扩散模型的离散化界限方面出现了浓厚的兴趣，本文提出了一种新的受 Shen 和 Lee 随机中点方法启发的扩散模型离散化方案，证明了该方法在从任意平滑分布中进行采样的维度依赖方面达到了已知最佳结果，同时还展示了可以将算法并行化以实现更快速的采样。

    Jun, 2024

  • 关于光滑性和等周性下 Metropolis-Adjusted Langevin 算法混合的简单证明

    本研究研究了在 $\mathbb {R}^d$ 上采样目标密度的 Metropolis-Adjusted Langevin 算法的混合时间，发现它在一定条件下的混合时间为 $O ((L\Upsilon)^{\frac12}/\psi_\mu^2\log (1/\epsilon))$。

    Apr, 2023

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

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

    Sep, 2019