Improved dimension dependence of a proximal algorithm for sampling
Improved dimension dependence of a proximal algorithm for sampling
复制标题
DOI：
--
复制
发表时间：
2023-02
期刊：
影响因子：
--
通讯作者：
JiaoJiao Fan;Bo Yuan;Yongxin Chen
中科院分区：
文献类型：
--
作者：
JiaoJiao Fan;Bo Yuan;Yongxin Chen
我们提出了一个采样算法，实现了上级复杂性界在所有的经典设置（强对数凹，对数凹，对数Sobolev不等式（LSI），庞加莱不等式），以及更一般的设置与半光滑或复合电位。我们的算法是基于在~\citet{lee 2021 structured}中引入的邻近采样器。这种近似采样器的性能取决于近似采样器中的关键步骤--限制高斯预言（RGO）的性能。这项工作的主要贡献是RGO的近似拒绝采样的基础上的不精确实现。为了限制RGO的不精确性，我们建立了高斯分布上半光滑函数的一个新的浓度不等式，推广了著名的Lipschitz函数的浓度不等式。将我们的RGO实现应用于近端采样器，我们几乎在所有设置中都实现了最先进的复杂度界限。例如，对于强对数凹分布，我们的方法在没有热启动的情况下具有复杂性界$\tilde\mathcal{O}（\kappa d^{1/2}）$，优于MALA的极大极小界。对于满足LSI的分布，我们的界是$\tilde \mathcal{O}（\hat \kappa d^{1/2}）$，其中$\hat \kappa$是平滑度和LSI常数之间的比率，优于所有现有的界。
We propose a sampling algorithm that achieves superior complexity bounds in all the classical settings (strongly log-concave, log-concave, Logarithmic-Sobolev inequality (LSI), Poincar\'e inequality) as well as more general settings with semi-smooth or composite potentials. Our algorithm is based on the proximal sampler introduced in~\citet{lee2021structured}. The performance of this proximal sampler is determined by that of the restricted Gaussian oracle (RGO), a key step in the proximal sampler. The main contribution of this work is an inexact realization of RGO based on approximate rejection sampling. To bound the inexactness of RGO, we establish a new concentration inequality for semi-smooth functions over Gaussian distributions, extending the well-known concentration inequality for Lipschitz functions. Applying our RGO implementation to the proximal sampler, we achieve state-of-the-art complexity bounds in almost all settings. For instance, for strongly log-concave distributions, our method has complexity bound $\tilde\mathcal{O}(\kappa d^{1/2})$ without warm start, better than the minimax bound for MALA. For distributions satisfying the LSI, our bound is $\tilde \mathcal{O}(\hat \kappa d^{1/2})$ where $\hat \kappa$ is the ratio between smoothness and the LSI constant, better than all existing bounds.