arXiv:2507.11236cs.DScs.LG2025-07

通过强化平滑性假设,实现非对数凹分布采样的多项式复杂度算法。

Improved sampling algorithms and functional inequalities for non-log-concave distributions

  • 在更强的光滑性假设下,设计了新采样算法
  • 当L为常数时,查询复杂度为d和1/ε的多项式
  • 适用于需要高效采样的高维非对数凹分布

研究在仅能访问势函数V及其梯度∇V的条件下,从密度∝e⁻ᵛ的分布μ中采样的问题。在标准假设(1)V是L-光滑的,(2)二阶矩≤M下,已有工作表明复杂度至少为( LM/(dε) )^{Ω(d)}。本文引入更强假设(1*):从μ出发的奥恩斯坦-乌伦贝克过程中的任意分布的势函数均为L-光滑。在此假设与(2)下,采样复杂度可降至poly(L,d)·((Ld+M)/ε²)^{O(L+1)},当L=O(1)且M=poly(d)时为d和1/ε的多项式。该结果相比前人方法实现指数级加速。进一步,在额外假设‖X‖对X∼μ为λ-次高斯时,μ的庞加莱常数至多为O(λ)^{2(L+1)},并建立了修正对数Sobolev不等式。作为应用,给出了特定强对数凹混合分布的修正对数Sobolev常数的新估计。

原文摘要 · Abstract (English)

We study the problem of sampling from a distribution $μ$ with density $\propto e^{-V}$ for some potential function $V:\mathbb R^d\to \mathbb R$ with query access to $V$ and $\nabla V$. We start with the following standard assumptions: (1) $V$ is $L$-smooth. (2) The second moment $\mathbf{E}_{X\sim μ}[\|X\|^2]\leq M$. Recently, He and Zhang (COLT'25) showed that the query complexity of this problem is at least $\left(\frac{LM}{dε}\right)^{Ω(d)}$ where $ε$ is the desired accuracy in total variation distance, and the Poincaré constant can be unbounded. Meanwhile, another common assumption in the study of diffusion based samplers (see e.g., the work of Chen, Chewi, Li, Li, Salim and Zhang (ICLR'23)) strengthens (1) to the following: (1*) The potential function of *every* distribution along the Ornstein-Uhlenbeck process starting from $μ$ is $L$-smooth. We show that under the assumptions (1*) and (2), the query complexity of sampling from $μ$ can be $\mathrm{poly}(L,d)\cdot \left(\frac{Ld+M}{ε^2}\right)^{\mathcal{O}(L+1)}$, which is polynomial in $d$ and $\frac{1}ε$ when $L=\mathcal{O}(1)$ and $M=\mathrm{poly}(d)$. This improves the algorithm with quasi-polynomial query complexity developed by Huang et al. (COLT'24). Our results imply that the seemingly moderate strengthening from (1) to (1*) yields an exponential gap in the query complexity. Furthermore, we show that together with the assumption (1*) and the stronger moment assumption that $\|X\|$ is $λ$-sub-Gaussian for $X\simμ$, the Poincaré constant of $μ$ is at most $\mathcal{O}(λ)^{2(L+1)}$. We also establish a modified log-Sobolev inequality for $μ$ under these conditions. As an application of our technique, we obtain a new estimate of the modified log-Sobolev constant for a specific class of mixtures of strongly log-concave distributions.

采样算法概率不等式高维分布

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。