Gaussian Cooling and O*(n^3) Algorithms for Volume and Gaussian Volume
| Autor: | Cousins, Ben, Vempala, Santosh |
|---|---|
| Rok vydání: | 2014 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | We present an $O^*(n^3)$ randomized algorithm for estimating the volume of a well-rounded convex body given by a membership oracle, improving on the previous best complexity of $O^*(n^4)$. The new algorithmic ingredient is an accelerated cooling schedule where the rate of cooling increases with the temperature. Previously, the known approach for potentially achieving this asymptotic complexity relied on a positive resolution of the KLS hyperplane conjecture, a central open problem in convex geometry. We also obtain an $O^*(n^3)$ randomized algorithm for integrating a standard Gaussian distribution over an arbitrary convex set containing the unit ball. Both the volume and Gaussian volume algorithms use an improved algorithm for sampling a Gaussian distribution restricted to a convex body. In this latter setting, as we show, the KLS conjecture holds and for a spherical Gaussian distribution with variance $\sigma^2$, the sampling complexity is $O^*(\max\{n^3, \sigma^2n^2\})$ for the first sample and $O^*(\max\{n^2, \sigma^2n^2\})$ for every subsequent sample. Comment: This paper is a combination of two previously published conference papers: "A Cubic Algorithm for Computing Gaussian Volume" (SODA 2014, arXiv:1306.5829) and "Bypassing KLS: Gaussian Cooling and an $O^*(n^3)$ Volume Algorithm" (STOC 2015). Additionally, this version has a major simplification to the main proof in the latter conference paper. (Lemma 3.2 in this version) 36 pages |
| Databáze: | arXiv |
| Externí odkaz: |
|