Bypassing KLS: Gaussian Cooling and an O^*(n3) Volume Algorithm
By Benjamin R. Cousins, Santosh Srinivas Vempala. 2014
60 citations recorded by the source corpus.
We present an O*(n3) 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*(n4). 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 such complexity relied on a positive resolution of the KLS hyperplane conjecture, a central open problem in convex geometry.
Subfields: Applied Mathematics, Computer Graphics and Computer-Aided Design, Statistics and Probability
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Applied Mathematics
In Statistics and Probability
Citations in the corpus
- Certified Adversarial Robustness via Randomized Smoothing (2019, background): “…the problem amounts to computing a lower bound on the Gaussian measure of the decision region of class cA. Specialized algorithms have been developed for estimating the Gaussian measure of convex sets (Cousins & Vempala, 2015), but the decision regions of a neural network are not in general convex.”