揭示非对数凹分布采样所需查询次数的紧致下界，明确其与优化的差距。
On the query complexity of sampling from non-log-concave distributions
- 构建在光滑性与矩约束下的反例，证明采样复杂度下界为(\frac{LM}{dε})^{Ω(d)}
- 提出匹配上界算法，复杂度为(\frac{LM}{dε})^{\mathcal{O}(d)}，实现复杂度紧致刻画
- 发现现有高效采样算法依赖更强条件，且采样比优化快超指数级
我们研究在不满足良好等周条件的d维分布 $p(x)\propto e^{-f(x)}$ 下的采样问题。对于任意满足 $LM\ge d\ge 5$、$ε\in (0,\frac{1}{32})$ 的参数，任何具有 $f(x)$ 和 $\nabla f(x)$ 查询访问的算法，均存在一个 $L$-对数光滑、二阶矩不超过 $M$ 的分布，使得算法需 $\left(\frac{LM}{dε}\right)^{Ω(d)}$ 次查询才能生成与目标分布总变差距离在 $ε$ 内的样本。我们通过一个 $\left(\frac{LM}{dε}\right)^{\mathcal{O}(d)}$ 查询的算法补全了该下界，从而完全刻画了非对数凹分布采样的紧致（仅指数常数差异）查询复杂度。我们的结果与 Huang 等人（COLT'24）形成鲜明对比：他们提出的算法在 $M=\mathtt{poly}(d)$ 时具拟多项式复杂度，但依赖更强条件——从目标分布出发的欧拉-伦德施泰特过程路径上所有分布均为 $\mathcal{O}(1)$-对数光滑。我们证明该条件严格强于仅要求目标分布 $\mathcal{O}(1)$-对数光滑。此外，我们在高斯混合模型背景下研究此条件，并将结果置于「采样与优化」的更广泛框架中（Ma 等人，PNAS'19），表明在多数参数范围内，采样比优化快超指数级（以维度 $d$ 为基准）。
原文摘要 · Abstract (English)
We study the problem of sampling from a $d$-dimensional distribution with density $p(x)\propto e^{-f(x)}$, which does not necessarily satisfy good isoperimetric conditions. Specifically, we show that for any $L,M$ satisfying $LM\ge d\ge 5$, $ε\in \left(0,\frac{1}{32}\right)$, and any algorithm with query accesses to the value of $f(x)$ and $\nabla f(x)$, there exists an $L$-log-smooth distribution with second moment at most $M$ such that the algorithm requires $\left(\frac{LM}{dε}\right)^{Ω(d)}$ queries to compute a sample whose distribution is within $ε$ in total variation distance to the target distribution. We complement the lower bound with an algorithm requiring $\left(\frac{LM}{dε}\right)^{\mathcal{O}(d)}$ queries, thereby characterizing the tight (up to the constant in the exponent) query complexity for sampling from the family of non-log-concave distributions. Our results are in sharp contrast with the recent work of Huang et al. (COLT'24), where an algorithm with quasi-polynomial query complexity was proposed for sampling from a non-log-concave distribution when $M=\mathtt{poly}(d)$. Their algorithm works under the stronger condition that all distributions along the trajectory of the Ornstein-Uhlenbeck process, starting from the target distribution, are $\mathcal{O}(1)$-log-smooth. We investigate this condition and prove that it is strictly stronger than requiring the target distribution to be $\mathcal O(1)$-log-smooth. Additionally, we study this condition in the context of mixtures of Gaussians. Finally, we place our results within the broader theme of ``sampling versus optimization'', as studied in Ma et al. (PNAS'19). We show that for a wide range of parameters, sampling is strictly easier than optimization by a super-exponential factor in the dimension $d$.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。