提出高效采样非对数凹分布的新算法，提升采样复杂度上限。
Complexity of Non-Log-Concave Sampling in Fisher Information
- 基于近端采样器与受限高斯预言机实现
- 采样复杂度在维度依赖上达到对数凹分布水平
- 适用于需要高精度采样的机器学习研究者
我们研究从对数光滑的非对数凹分布中采样时，获得相对Fisher信息保证的查询复杂度；这相当于优化中的近似驻点寻找。算法基于近端采样器，即Langevin扩散的隐式离散化，需实现称为受限高斯预言机（RGO）的反向步骤。通过利用近期在高精度瑞尼散度下对数凹分布采样的成果，我们得到一个近似RGO的实现方式。当与近端采样器结合使用时，该方法在相对Fisher信息上的复杂度保证继承了对数凹采样的维度依赖特性，并优于以往非对数凹采样的结果。此外，我们还证明了一个逆向归约：若非对数凹采样在相对Fisher信息上的维度依赖得以改进，则高精度对数凹采样亦将受益于更优的维度依赖。
原文摘要 · Abstract (English)
We study the query complexity of obtaining a relative Fisher information guarantee for sampling from a log-smooth non-log-concave distribution; this is a sampling analog of finding an approximate stationary point in optimization. Our algorithm is based on the proximal sampler, which is an implicit discretization of the Langevin diffusion, and requires an implementation of the backward step known as the restricted Gaussian oracle (RGO). We show that by leveraging the recent results for log-concave sampling with high-accuracy guarantees in Rényi divergence, we can obtain an approximate RGO implementation that -- when used with the proximal sampler -- yields a complexity guarantee in relative Fisher information that inherits the same dimension dependence as log-concave sampling, and improves upon prior work for non-log-concave sampling. We also show a converse reduction that any improvement in the dimension dependence in relative Fisher information for non-log-concave sampling will yield an improved dimension dependence for high-accuracy log-concave sampling.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。