A cubic algorithm for computing Gaussian volume

DOI10.1137/1.9781611973402.90MaRDI QIDQ5384052zbMATH OpenOpenAlexFDO

Authors Ben Cousins, Santosh S. Vempala

Publication date 20 June 2019

Published in Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1306.5829

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20)

Abstract: 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^{\ast }(n^3)$ while the complexity of sampling is $O^{\ast }(n^3)$ for the first sample and $O^{\ast }(n^2)$ 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.

Recommendations

• Gaussian Cooling and $O^*(n^3)$ Algorithms for Volume and Gaussian Volume
• Random walks in a convex body and an improved volume algorithm
• Random walks and anO*(n5) volume algorithm for convex bodies
• scientific article; zbMATH DE number 1149839
• Bypassing KLS: Gaussian cooling and an O^(n^3) volume algorithm

Cited in

(15)

• The volume algorithm revisited: relation with bundle methods
• An almost constant lower bound of the isoperimetric coefficient in the KLS conjecture
• Practical volume approximation of high-dimensional convex bodies, applied to modeling portfolio dependencies and financial crises
• Bypassing KLS: Gaussian cooling and an O^(n^3) volume algorithm
• A practical volume algorithm
• Fast MCMC sampling algorithms on polytopes
• Gaussian Cooling and $O^*(n^3)$ Algorithms for Volume and Gaussian Volume
• Geodesic Walks in Polytopes
• Semidefinite Relaxations for Lebesgue and Gaussian Measures of Unions of Basic Semialgebraic Sets
• scientific article; zbMATH DE number 7236423 (Why is no real title available?)
• A generalized central limit conjecture for convex bodies
• Log-concave sampling: Metropolis-Hastings algorithms are fast
• Error regions in quantum state tomography: computational complexity caused by geometry of quantum states
• Truncated log-concave sampling for convex bodies with reflective Hamiltonian Monte Carlo
• Fast mixing of data augmentation algorithms: Bayesian probit, logit and Lasso regression

This page was built for publication: A cubic algorithm for computing Gaussian volume

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5384052)