分析归一化常数估计的复杂度，为重要性采样提供理论保障。
Complexity Analysis of Normalizing Constant Estimation: from Jarzynski Equality to Annealed Importance Sampling and beyond
- 基于最优传输与吉尔萨诺夫定理，建立非渐近复杂度分析框架。
- 首次给出退火重要性采样的复杂度上界：$\widetilde{O}\left(\frac{dβ^2\mathcal{A}^2}{\varepsilon^4}\right)$。
- 提出反向扩散采样新算法，有效应对多模态场景下的高动作量问题。
给定一个未归一化的概率密度 $π\propto\mathrm{e}^{-V}$，估计其归一化常数 $Z=\int_{\mathbb{R}^d}\mathrm{e}^{-V(x)}\mathrm{d}x$ 或自由能 $F=-\log Z$ 是贝叶斯统计、统计力学和机器学习中的关键问题。该问题在高维或分布多模时尤为困难。为降低传统重要性采样估计器的方差，退火类方法如 Jarzynski 等式和退火重要性采样被广泛采用，但其定量复杂度保证仍不明确。本文首次对退火重要性采样进行非渐近分析，导出在高概率下以相对误差 $\varepsilon$ 估计 $Z$ 的预言复杂度为 $\widetilde{O}\left(\frac{dβ^2\mathcal{A}^2}{\varepsilon^4}\right)$，其中 $β$ 表示 $V$ 的光滑性，$\mathcal{A}$ 为连接目标分布 $π$ 与可处理参考分布的概率测度曲线的动作。分析借助吉尔萨诺夫定理与最优传输，无需目标分布的等周假设。针对常用几何插值带来的大动作量问题，本文提出基于反向扩散采样的新算法，建立其复杂度分析框架，并在实验中验证其在多模态场景下的高效性。
原文摘要 · Abstract (English)
Given an unnormalized probability density $π\propto\mathrm{e}^{-V}$, estimating its normalizing constant $Z=\int_{\mathbb{R}^d}\mathrm{e}^{-V(x)}\mathrm{d}x$ or free energy $F=-\log Z$ is a crucial problem in Bayesian statistics, statistical mechanics, and machine learning. It is challenging especially in high dimensions or when $π$ is multimodal. To mitigate the high variance of conventional importance sampling estimators, annealing-based methods such as Jarzynski equality and annealed importance sampling are commonly adopted, yet their quantitative complexity guarantees remain largely unexplored. We take a first step toward a non-asymptotic analysis of annealed importance sampling. In particular, we derive an oracle complexity of $\widetilde{O}\left(\frac{dβ^2{\mathcal{A}}^2}{\varepsilon^4}\right)$ for estimating $Z$ within $\varepsilon$ relative error with high probability, where $β$ is the smoothness of $V$ and $\mathcal{A}$ denotes the action of a curve of probability measures interpolating $π$ and a tractable reference distribution. Our analysis, leveraging Girsanov's theorem and optimal transport, does not explicitly require isoperimetric assumptions on the target distribution. Finally, to tackle the large action of the widely used geometric interpolation, we propose a new algorithm based on reverse diffusion samplers, establish a framework for analyzing its complexity, and empirically demonstrate its efficiency in tackling multimodality.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。