2024/08/18 by Anari, Nima, Gao, Ruiquan, Rubinstein, Aviad · 4 citations
#Artificial Intelligence (cs.AI) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Probability (math.PR)
paper · doi:10.48550/arxiv.2408.09442
We show how to use parallelization to speed up sampling from an arbitrary distribution μ on a product space [q]n, given oracle access to counting queries: ℙX∼ μ[XS=σS] for any S⊆ [n] and σS ∈ [q]S. Our algorithm takes O(n2/3⋅ polylog(n,q)) parallel time, to the best of our knowledge, the first sublinear in n runtime for arbitrary distributions. Our results have implications for sampling in autoregressive models. Our algorithm directly works with an equivalent oracle that answers conditional marginal queries ℙX∼ μ[Xi=σi \vert XS=σS], whose role is played by a trained neural network in autoregressive models. This suggests a roughly n1/3-factor speedup is possible for sampling in any-order autoregressive models. We complement our positive result by showing a lower bound of \widetildeΩ(n1/3) for the runtime of any parallel sampling algorithm making at most poly(n) queries to the counting oracle, even for q=2.