A Cubic Algorithm for Computing Gaussian Volume

ACO Student Seminar
Friday, April 4, 2014 - 12:05pm
1 hour (actually 50 minutes)
Skiles 005
Georgia Tech
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 the integration algorithm is O*(n^3) while the complexity of the sampling algorithm is O*(n^3) for the first sample and O*(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.