论文标题
跨越树木和确定点过程的最佳sublinear采样。
Optimal Sublinear Sampling of Spanning Trees and Determinantal Point Processes via Average-Case Entropic Independence
论文作者
论文摘要
我们设计了快速算法，以反复从强烈的瑞利分布中采样，其中包括随机跨越树分布和确定点过程。对于图$ g =（v，e）$，我们展示了如何大致统一地随机跨越$ g $ in $ \ widetilde {o}（\ lvert v \ rvert）$ time在初始$ \ wideTilde {o}（\ lvert e \ rvert e \ rvert）$ time time PrepoRocessing之后，每个样品$ g $ a。对于$ n $元素的尺寸$ k $的子集的确定点过程，我们展示了如何以$ \ widetilde {o} {o}（k^ω）$在初始$ \ wideTilde {o} {o} {o}（o}（nk^{ω-1}）$ time time percrocessing，$ω<2.372864 $ω<2.372864之后，在$ \ wideTilde {o}（k^ω）$中我们甚至改进了从确定点过程中获取单个样本的最新技术，从$ \ widetilde {o}（\ min \ {nk^2，n^ω\}）$到$ \ widetilde {O}（nk^{ω-1}）$。 在我们的主要技术结果中，我们达到了强烈的雷利分布的最佳范围稀疏限制。在域稀疏中，从$ \ binom {[n]} {k} $上的分配$μ$采样缩短为$ \ binom {[t]} {k} $ for $ t \ ll n $的相关分布的采样。我们表明，对于强烈的瑞利分布，我们可以实现最佳$ t = \ widetilde {o}（k）$。我们的还原涉及从$ \ widetilde {o}（1）$ domain-sparsparsified分布进行采样，所有这些分布都可以有效地产生，以便假设方便地访问$μ$的边缘的近似高估。访问边际类似于访问连续分布的平均值和协方差，或者知道分布的“各向同性”，这是Kannan-Lovász-Simonovits（KLS）猜想的关键假设，基于它的最佳采样器。我们认为我们的结果是KLS猜想的道德类似物及其对抽样的后果，以实现强烈的瑞利度量。
We design fast algorithms for repeatedly sampling from strongly Rayleigh distributions, which include random spanning tree distributions and determinantal point processes. For a graph $G=(V, E)$, we show how to approximately sample uniformly random spanning trees from $G$ in $\widetilde{O}(\lvert V\rvert)$ time per sample after an initial $\widetilde{O}(\lvert E\rvert)$ time preprocessing. For a determinantal point process on subsets of size $k$ of a ground set of $n$ elements, we show how to approximately sample in $\widetilde{O}(k^ω)$ time after an initial $\widetilde{O}(nk^{ω-1})$ time preprocessing, where $ω<2.372864$ is the matrix multiplication exponent. We even improve the state of the art for obtaining a single sample from determinantal point processes, from the prior runtime of $\widetilde{O}(\min\{nk^2, n^ω\})$ to $\widetilde{O}(nk^{ω-1})$. In our main technical result, we achieve the optimal limit on domain sparsification for strongly Rayleigh distributions. In domain sparsification, sampling from a distribution $μ$ on $\binom{[n]}{k}$ is reduced to sampling from related distributions on $\binom{[t]}{k}$ for $t\ll n$. We show that for strongly Rayleigh distributions, we can can achieve the optimal $t=\widetilde{O}(k)$. Our reduction involves sampling from $\widetilde{O}(1)$ domain-sparsified distributions, all of which can be produced efficiently assuming convenient access to approximate overestimates for marginals of $μ$. Having access to marginals is analogous to having access to the mean and covariance of a continuous distribution, or knowing "isotropy" for the distribution, the key assumption behind the Kannan-Lovász-Simonovits (KLS) conjecture and optimal samplers based on it. We view our result as a moral analog of the KLS conjecture and its consequences for sampling, for discrete strongly Rayleigh measures.
