# Optimal Sublinear Sampling of Spanning Trees and Determinantal Point Processes via Average-Case Entropic Independence arXiv: https://arxiv.org/abs/2204.02570 · HTML: https://mlsanity.com/paper/2204.02570/ ## Key facts - Cited by 8 papers in the map (data through 14 Oct 2026). - Builds on 24 of its 51 references that are in the map. - First posted on arXiv 6 Apr 2022. ## Builds on (most cited first, 24 of 24) - [Determinantal Point Processes in Randomized Numerical Linear Algebra](https://mlsanity.com/paper/2005.03185/) (2020) - [Monte Carlo Markov Chain Algorithms for Sampling Strongly Rayleigh Distributions and Determinantal Point Processes](https://mlsanity.com/paper/1602.05242/) (2016) - [Exact sampling of determinantal point processes with sublinear time preprocessing](https://mlsanity.com/paper/1905.13476/) (2019) - [Sampling from a k-DPP without looking at all items](https://mlsanity.com/paper/2006.16947/) (2020) - [Localization Schemes: A Framework for Proving Mixing Bounds for Markov Chains](https://mlsanity.com/paper/2203.04163/) (2022) - [Leveraged volume sampling for linear regression](https://mlsanity.com/paper/1802.06749/) (2018) - [Fast determinantal point processes via distortion-free intermediate sampling](https://mlsanity.com/paper/1811.03717/) (2018) - [A (Slightly) Improved Approximation Algorithm for Metric TSP](https://mlsanity.com/paper/2007.01409/) (2020) - [Graph Clustering using Effective Resistance](https://mlsanity.com/paper/1711.06530/) (2017) - [Sampling Random Spanning Trees Faster than Matrix Multiplication](https://mlsanity.com/paper/1611.07451/) (2016) - [Fractionally Log-Concave and Sector-Stable Polynomials: Counting Planar Matchings and More](https://mlsanity.com/paper/2102.02708/) (2021) - [An almost-linear time algorithm for uniform random spanning tree generation](https://mlsanity.com/paper/1711.06455/) (2017) - [A Matrix Chernoff Bound for Strongly Rayleigh Distributions and Spectral Sparsifiers from a few Random Spanning Trees](https://mlsanity.com/paper/1810.08345/) (2018) - [Isotropy and Log-Concave Polynomials: Accelerated Sampling and High-Precision Counting of Matroid Bases](https://mlsanity.com/paper/2004.09079/) (2020) - [Fast Generation of Random Spanning Trees and the Effective Resistance Metric](https://mlsanity.com/paper/1501.00267/) (2015) - [The Kannan-Lov'asz-Simonovits Conjecture](https://mlsanity.com/paper/1807.03465/) (2018) - [Modified log-Sobolev inequalities for strongly log-concave distributions](https://mlsanity.com/paper/1903.06081/) (2019) - [An Experimental Evaluation of the Best-of-Many Christofides' Algorithm for the Traveling Salesman Problem](https://mlsanity.com/paper/1506.07776/) (2015) - [Determinant-Preserving Sparsification of SDDM Matrices with Applications to Counting and Sampling Spanning Trees](https://mlsanity.com/paper/1705.00985/) (2017) - [Correcting the bias in least squares regression with volume-rescaled sampling](https://mlsanity.com/paper/1810.02453/) (2018) - [Improved Analysis of Higher Order Random Walks and Applications](https://mlsanity.com/paper/2001.02827/) (2020) - [Domain Sparsification of Discrete Distributions using Entropic Independence](https://mlsanity.com/paper/2109.06442/) (2021) - [A Polynomial Time MCMC Method for Sampling from Continuous DPPs](https://mlsanity.com/paper/1810.08867/) (2018) - [An Improved Approximation Algorithm for the Minimum k-Edge Connected Multi-Subgraph Problem](https://mlsanity.com/paper/2101.05921/) (2021) ## Built on by (most cited first, 8 of 8) - [Solving Dense Linear Systems Faster Than via Preconditioning](https://mlsanity.com/paper/2312.08893/) (2023) - [Kernel quadrature with randomly pivoted Cholesky](https://mlsanity.com/paper/2306.03955/) (2023) - [Recent and Upcoming Developments in Randomized Numerical Linear Algebra for Machine Learning](https://mlsanity.com/paper/2406.11151/) (2024) - [A Faster Sampler for Discrete Determinantal Point Processes](https://mlsanity.com/paper/2210.17358/) (2022) - [Distributed Least Squares in Small Space via Sketching and Bias Reduction](https://mlsanity.com/paper/2405.05343/) (2024) - [Turbocharging Gaussian Process Inference with Approximate Sketch-and-Project](https://mlsanity.com/paper/2505.13723/) (2025) - [Mining the Minoria: Unknown, Under-represented, and Under-performing Minority Groups](https://mlsanity.com/paper/2411.04761/) (2024) - [Bypassing orthogonalization in the quantum DPP sampler](https://mlsanity.com/paper/2503.05906/) (2025) ## Abstract (arXiv) 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 widetildeO(lvert Vrvert) time per sample after an initial widetildeO(lvert Ervert) 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 widetildeO(kω) time after an initial widetildeO(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 widetildeO(minnk2, nω) to widetildeO(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 tll n. We show that for strongly Rayleigh distributions, we can can achieve the optimal t=widetildeO(k). Our reduction involves sampling from widetildeO(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'asz-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.