arXiv:2507.18021math.STcs.DS2025-07被引 4

提出零阶采样新算法,实现更优复杂度与简洁分析。

Zeroth-order Logconcave Sampling

  • 基于 $q$-Rényi 散度的冷启动,通过热力平滑直接生成高质量样本
  • 对 $q= ildeigOmega(1)$ 实现当前最优采样复杂度
  • 首次在无一阶信息下完成该类分析,适合高维概率采样研究者

我们研究从一般对数凹分布中进行零阶查询采样的复杂度:给定凸函数 $V:\mathbb{R}^d\rightarrow\mathbb{R}\cup\{\infty\}$ 的评估黑盒,输出一个与密度 $e^{-V}$ 在 $\varepsilon$-距离内的点。已有大量工作在 $\infty$-Rényi 散度的点态热启动假设下,通过退火构造热启动,实现总变差距离下的高效算法。本文解决更通用的问题:使用 $q$-Rényi 散度热启动,生成在 $q$-Rényi 散度下 $\varepsilon$-接近的目标分布样本。第一项主要成果是针对 $q=\tilde\bigOmega(1)$ 构造了具有当前最优复杂度的端到端算法;第二项结果展示了如何通过全程维持 $q$-Rényi 散度,直接由退火生成 $q$-Rényi 热启动,从而获得更简洁的分析和更优复杂度。此前此类结果仅在光滑性和一阶信息可访问的更强假设下成立。此外,我们通过反例推翻了一个关于各向同性对数凹分布二次倾斜的几何猜想,建立了高斯退火的下界。核心在于证明热伴随算子的超收缩性,并将其转化为近端采样器的改进混合时间保证。整个采样与退火分析路径简化自然,直接将收敛速率关联于目标分布的等周常数。

原文摘要 · Abstract (English)

We study the zeroth-order query complexity of sampling from a general logconcave distribution: given access to an evaluation oracle for a convex function $V:\mathbb{R}^{d}\rightarrow\mathbb{R}\cup\{\infty\}$, output a point from a distribution within $\varepsilon$-distance to the density proportional to $e^{-V}$. A long line of work provides efficient algorithms for this problem in TV distance, assuming a pointwise warm start (i.e., in $\infty$-Rényi divergence), and using annealing to generate such a warm start. Here, we address the natural and more general problem of using a $q$-Rényi divergence warm start to generate a sample that is $\varepsilon$-close in $q$-Rényi divergence. Our first main result is an algorithm with this end-to-end guarantee with state-of-the-art complexity for $q=\widetildeΩ(1)$. Our second result shows how to generate a $q$-Rényi divergence warm start directly via annealing, by maintaining $q$-Rényi divergence throughout, thereby obtaining a streamlined analysis and improved complexity. Such results were previously known only under the stronger assumptions of smoothness and access to first-order oracles. We also show a lower bound for Gaussian annealing by disproving a geometric conjecture about quadratic tilts of isotropic logconcave distributions. Central to our approach, we establish hypercontractivity of the heat adjoint and translate this into improved mixing time guarantees for the Proximal Sampler. The resulting analysis of both sampling and annealing follows a simplified and natural path, directly tying convergence rates to isoperimetric constants of the target distribution.

采样算法对数凹分布零阶优化退火方法

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