标题： 一种求解非光滑复合势能的有效采样算法 显示英文标题

标题： An Efficient Sampling Algorithm for Non-smooth Composite Potentials

摘要： 我们研究了从形式为$p(x) \propto \exp(-f(x)- g(x))$的密度中采样的问题，其中$f: \mathbb{R}^d \rightarrow \mathbb{R}$是一个光滑且强凸的函数，而$g: \mathbb{R}^d \rightarrow \mathbb{R}$是一个凸且满足Lipschitz条件的函数。 我们基于 Metropolis-Hastings 框架提出了一种新算法，并证明它在最多$O(d \log (d/\varepsilon))$次迭代内能够以总变差距离$\varepsilon$内达到目标密度。 这一保证扩展了之前关于从具有光滑对数密度的分布中采样的结果（$g = 0$），将其推广到更一般的复合非光滑情形，且混合时间与条件数的倍数无关。 我们的方法基于一种新颖的近似投影提议分布，该分布对于一大类非光滑函数$g$可以高效计算。 显示英文摘要

摘要： 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 algorithm based on the Metropolis-Hastings framework, and prove that it mixes to within TV distance $\varepsilon$ of the target density in at most $O(d \log (d/\varepsilon))$ iterations. This guarantee extends previous results on sampling from distributions with smooth log densities ($g = 0$) to the more general composite non-smooth case, with the same mixing time up to a multiple of the condition number. Our method is based on a novel proximal-based proposal distribution that can be efficiently computed for a large class of non-smooth functions $g$.