2013/06/25 by Ben Cousins, Santosh Vempala, Cousins, Ben +1 · 3 citations
Computer Science · Mathematics · #Bayesian Methods and Mixture Models #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Functional Analysis (math.FA) #Markov Chains and Monte Carlo Methods #Probability (math.PR) #Statistical Methods and Inference #cs.DS #math.FA #math.PR
paper · pdf · doi:10.48550/arxiv.1306.5829
23 pages
openalex publication_date 2013/06/25 · arxiv created 2013/07/11 · arxiv updated 2013/07/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We present randomized algorithms for sampling the standard Gaussian distribution restricted to a convex set and for estimating the Gaussian measure of a convex set, in the general membership oracle model. The complexity of integration is O^*(n3) while the complexity of sampling is O^*(n3) for the first sample and O^*(n2) for every subsequent sample. These bounds improve on the corresponding state-of-the-art by a factor of n. Our improvement comes from several aspects: better isoperimetry, smoother annealing, avoiding transformation to isotropic position and the use of the "speedy walk" in the analysis.