复合对数凹采样新算法：近端梯度匹配最优复杂度
A proximal gradient algorithm for composite log-concave sampling
做高维采样或贝叶斯推断的团队终于有了一个理论干净、复杂度最优的通用工具——复合目标下的采样效率首次追上光滑情形，做 MCMC 算法设计的建议细读。
研究者提出一种针对复合对数凹分布（形如 e^{-f-g}）的采样算法，仅需对 f 计算梯度，对 g 使用受限高斯预言机（RGO）。该算法在 f+g 强凸且 f 光滑时，达到总变差距离 ε 误差的迭代次数为 Õ(κ√d log⁴(1/ε))，与经典 g=0 情形的最优结果一致。此外，算法还扩展到非对数凹（满足 Poincaré 或 log-Sobolev 不等式）以及 f 非光滑但 Lipschitz 的情形。这是首次将近端梯度思想系统引入采样领域，理论保证与优化中的近端梯度法相呼应。
A proximal gradient algorithm for composite log-concave sampling
We propose an algorithm to sample from composite log-concave distributions over $\mathbb{R}^d$, i.e., densities of the form $π\propto e^{-f-g}$, assuming access to gradient evaluations of $f$ and a restricted Gaussian oracle (RGO) for $g$. The latter requirement means that we can easily sample from the density $\text{RGO}_{g,h,y}(x) \propto \exp(-g(x) -\frac{1}{2h}||y-x||^2)$, which is the sampling analogue of the proximal operator for $g$. If $f + g$ is $α$-strongly convex and $f$ is $β$-smooth, our sampler achieves $\varepsilon$ error in total variation distance in $\widetilde{\mathcal O}(κ\sqrt d \log^4(1/\varepsilon))$ iterations where $κ:= β/α$, which matches prior state-of-the-art results for the case $g=0$. We further extend our results to cases where (1) $π$ is non-log-concave but satisfies a Poincaré or log-Sobolev inequality, and (2) $f$ is non-smooth but Lipschitz.
