技术摘要：对数凹采样的一种统一复杂度界限

问题陈述

本文研究了在 $\mathbb{R}^d$ 上对任意全维对数凹概率测度 $\pi_X \propto e^{-V}$ 进行采样的算法问题，其中 $V: \mathbb{R}^d \to \mathbb{R} \cup \{\infty\}$ 是一个仅能通过评估算子（evaluation oracle）访问的凸函数。目标是确定生成一个样本 $X^*$ 所需的查询复杂度（即 $V$ 的评估次数），使得其分布在 Rényi 散度意义下接近 $\pi_X$，给定一个“热启动”（warm start）初始分布 $\pi_0$。

假设采用一种特定的归一化方式：即“基集” $L_g = \{x : V(x) - \inf V \le 10d\}$ 包含单位球 $B(0,1)$。这确保了有效支撑集的规模不会过小。

先前关于 In-and-Out 算法（一种通过指数提升得到的近端采样器/proximal sampler）的研究，其收敛速率包含了一个项 $\Lambda \vee 1$（其中 $\Lambda = \|\text{cov } \pi_X\|_{op}$）。在良态设置下（例如强对数凹且平滑的密度），这导致复杂度约为 $\kappa d + d^2$，其中 $\kappa$ 是条件数。其中的 $d^2$ 项是一个分析上的人工产物，具体源于对提升后分布的庞加莱常数（Poincaré constant）进行了松散的估计。本文探讨了这个加性的 $d^2$ 项是不可避免的，还是仅仅是证明技术的产物。

方法论

作者利用了 In-and-Out 算法（也称为近端采样器），该算法在向前高斯步和涉及目标势函数 $V$ 的向后步之间交替进行。为了仅使用零阶算子实现向后步，算法采用了指数提升（exponential lifting）。

1. 指数提升： 将分布 $\pi_X$ 提升到更高维空间 $\mathbb{R}^d \times \mathbb{R}$，其测度为 $\pi_Z$，密度为：
   $$\pi_Z(dx, dt) \propto e^{-dt} \mathbf{1}[V(x) \le dt] \, dx \, dt$$
   $\pi_Z$ 在 $x$ 坐标上的边缘分布正是 $\pi_X$。$\pi_Z$ 的支撑集是凸的，且其对数密度在提升后的坐标 $t$ 上是线性的，这简化了向后步的实现。

2. 收敛性分析： 采样器在 $\chi^2$ 散度（以及随后的 Rényi 散度）中的收敛速率受提升分布的庞加莱常数 $C_{PI}(\pi_Z)$ 控制。先前的分析依赖于界限 $\|\text{cov } \pi_Z\| \lesssim \|\text{cov } \pi_X\| \vee 1$，这引入了有问题的 $\vee 1$ 项。

3. 关键技术创新： 本文改进了提升分布协方差的界限。

   • 作者观察到，如果 $X \sim \pi_X$ 且 $E \sim \text{Exp}(1)$ 相互独立，则提升变量 $T$ 满足 $T \stackrel{d}{=} (V(X) + E)/d$。
   • 这意味着 $\text{Var}_{\pi_Z}(T) = \text{Var}_{\pi_X}(V(X))/d^2 + 1/d^2$。
   • 利用**方差熵（varentropy）**界限（即信息量 $-\log \pi_X(X)$ 的方差），该界限指出对于对数凹密度，$\text{Var}_{\pi_X}(V(X)) \le d$，作者得出：
     $$\text{Var}_{\pi_Z}(T) \le \frac{d}{d^2} + \frac{1}{d^2} = \frac{2}{d}$$
   • 通过对全协方差矩阵应用 Cauchy-Schwarz 不等式，作者证明了：
     $$\|\text{cov } \pi_Z\| \le \|\text{cov } \pi_X\| + \frac{2}{d}$$
   • 在基集归一化条件下，可以证明 $1/d \lesssim \|\text{cov } \pi_X\|$，这意味着加性项被协方差的内在尺度所吸收。

核心贡献与结果

1. 改进的庞加莱常数界限

核心理论贡献是 引理 1.3，它确立了提升分布协方差的算子范数满足 $\|\text{cov } \pi_Z\| \le \|\text{cov } \pi_X\| + 2/d$。因此，提升分布的庞加莱常数满足 $C_{PI}(\pi_Z) \lesssim \|\text{cov } \pi_X\| \log d$，从而消除了此前导致 $\vee 1$ 项出现的加性常数。

2. 统一复杂度界限（定理 1.1）

改进后的协方差界限导出了从热启动进行零阶对数凹采样的统一复杂度结果：

• Rényi 散度 ($R_q$)： 对于 $q \ge 2$，算法在期望意义下使用 $\tilde{O}(q d^2 \Lambda \log^3(1/\epsilon))$ 次查询，返回一个满足 $R_q(\text{law } X^* \| \pi) \le \epsilon$ 的样本。
• Rényi 无穷散度 ($R_\infty$)： 如果初始分布是 $M_\infty$-热的，算法使用 $\tilde{O}(d^2 R \Lambda^{1/2} \text{polylog}(1/\epsilon))$ 次查询，返回一个满足 $R_\infty(\text{law } X^* \| \pi) \le \epsilon$ 的样本，其中 $R = \mathbb{E}_\pi[\|X\|^2]$。

3. 恢复良态界限（推论 1.2）

对于良态分布（其中 $V$ 是 $\alpha$-强对数凹且 $\beta$-对数平滑，条件数为 $\kappa = \beta/\alpha$），新界限恢复了最优复杂度 $\tilde{O}(q \kappa d \log^3(1/\epsilon))$。

• 重要性： 这消除了之前的 $d^2$ 项（此前在 [KV25b, KV25a, KV25c] 等工作中表现为 $\kappa d + d^2$）。该结果表明，相同的算法和分析框架可以无缝应用于通用对数凹设置和良态设置，而无需单独的分析或承受人工惩罚。

意义与主张

本文声称提供了一个简单、统一且接近紧致的界限，用于对任意对数凹分布进行采样。

• 统一性： 主要意义在于复杂度的统一。通过移除“ $\vee 1$ ”这一人工产物，作者表明，通用对数凹采样的查询复杂度自然地由目标分布的协方差决定，正如在凸体上进行均匀采样一样。
• 紧致性： 该界限被描述为对于约束设置（例如限制在凸体内的高斯分布）和良态设置都是“接近紧致”的。
• 方法论的简洁性： 改进并非通过改变算法（In-and-Out 保持不变）实现的，而是通过利用方差熵界限对提升分布的几何结构进行更精细的分析。这简化了先前文献中建立的理论保证。

作者并未提出新的实验应用或未来的算法方向，而是将这项工作定位为迈向单一、连贯的对数凹采样复杂度理论的基础性步骤。