arXiv:2411.09117cs.LGcs.DS2024-11被引 15

用少量数据初始化,快速采样多模态分布。

Efficiently learning and sampling multimodal distributions with data-based initialization

  • 基于数据初始化马尔可夫链,提升采样效率。
  • 仅需约 $\tilde O(k/\varepsilon^2)$ 个样本,即可在 $\varepsilon$ 范围内逼近目标分布。
  • 适用于得分匹配、伊辛模型等,适合低复杂度分布学习场景。

本文研究在仅获得少量样本的情况下,如何通过马尔可夫链高效采样多模态分布。即使混合速度任意慢,只要马尔可夫链具有 $k$ 阶谱间隙,从 $\tilde O(k/\varepsilon^2)$ 个来自平稳分布的样本中初始化,以高概率生成的样本其条件分布与平稳分布的总变差距离不超过 $\varepsilon$。该结果适用于满足庞加莱不等式的 $k$ 个分布的混合,若满足对数索博列夫不等式则收敛更快。理论对链的扰动稳定,适用于带得分估计误差的朗之万扩散及伪似然估计误差下的格鲁贝尔动力学。该分析首次证明了自然类低复杂度伊辛模型可从样本中高效学习,且改进并推广了Koehler和Vuong(2023)的结果,将 $k$ 的依赖从指数级变为线性,并适用于任意半群。

原文摘要 · Abstract (English)

We consider the problem of sampling a multimodal distribution with a Markov chain given a small number of samples from the stationary measure. Although mixing can be arbitrarily slow, we show that if the Markov chain has a $k$th order spectral gap, initialization from a set of $\tilde O(k/\varepsilon^2)$ samples from the stationary distribution will, with high probability over the samples, efficiently generate a sample whose conditional law is $\varepsilon$-close in TV distance to the stationary measure. In particular, this applies to mixtures of $k$ distributions satisfying a Poincaré inequality, with faster convergence when they satisfy a log-Sobolev inequality. Our bounds are stable to perturbations to the Markov chain, and in particular work for Langevin diffusion over $\mathbb R^d$ with score estimation error, as well as Glauber dynamics combined with approximation error from pseudolikelihood estimation. This justifies the success of data-based initialization for score matching methods despite slow mixing for the data distribution, and improves and generalizes the results of Koehler and Vuong (2023) to have linear, rather than exponential, dependence on $k$ and apply to arbitrary semigroups. As a consequence of our results, we show for the first time that a natural class of low-complexity Ising measures can be efficiently learned from samples.

采样多模态马尔可夫链伊辛模型

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