论文标题
关于贝叶斯后取样的大都市调整后的兰格文算法的计算复杂性
On the Computational Complexity of Metropolis-Adjusted Langevin Algorithms for Bayesian Posterior Sampling
论文作者
论文摘要
在本文中，我们使用大都会调整后的Langevin算法（MALA）研究了贝叶斯后部（或伪后者）采样的计算复杂性。 Mala首先使用离散时间Langevin SDE提出了一个新的状态，然后使用大都会危机拒绝来调整拟议的状态。 MALA的大多数现有理论分析都取决于目标分布的平稳性和强大的对数洞穴的特性，而目标分布通常缺乏实用的贝叶斯问题。我们的分析取决于统计大型样本理论，该理论限制了贝叶斯后部以非常特定的方式平滑和对数洞穴的偏差。特别是，我们引入了一种新技术，该技术通过$ s $ - 传导配置文件将马尔可夫链与连续状态空间的混合时间界定，从而在多个方面提供了比现有技术的改进。通过采用这项新技术，我们建立了$ d^{1/3} $的最佳参数依赖性，并且在燃烧期间燃烧后的MALA中的$κ$的条件数依赖性，在标准的贝叶斯式贝叶斯设置后，目标后部分布接近$ d $ d $ d $ d $ d $ d $ d $ d $ d $ d $ d $ d $ d $ d $ d $ d $ d $ d $ d $ d $ d $ d $ d $ d $ d $ dimentiment covrix $ a covarix $ a a covarixy $ a a corix $ a。我们还证明了一个匹配的混合时间下限，用于从多元高斯通过MALA采样以补充上限。
In this paper, we examine the computational complexity of sampling from a Bayesian posterior (or pseudo-posterior) using the Metropolis-adjusted Langevin algorithm (MALA). MALA first employs a discrete-time Langevin SDE to propose a new state, and then adjusts the proposed state using Metropolis-Hastings rejection. Most existing theoretical analyses of MALA rely on the smoothness and strong log-concavity properties of the target distribution, which are often lacking in practical Bayesian problems. Our analysis hinges on statistical large sample theory, which constrains the deviation of the Bayesian posterior from being smooth and log-concave in a very specific way. In particular, we introduce a new technique for bounding the mixing time of a Markov chain with a continuous state space via the $s$-conductance profile, offering improvements over existing techniques in several aspects. By employing this new technique, we establish the optimal parameter dimension dependence of $d^{1/3}$ and condition number dependence of $κ$ in the non-asymptotic mixing time upper bound for MALA after the burn-in period, under a standard Bayesian setting where the target posterior distribution is close to a $d$-dimensional Gaussian distribution with a covariance matrix having a condition number $κ$. We also prove a matching mixing time lower bound for sampling from a multivariate Gaussian via MALA to complement the upper bound.
