Friday, April 28, 2017 - 10:30am
Klaus 2100
Title: | Efficient High-dimensional Sampling and Integration |
Advisor: | Prof. Santosh Vempala, School of Computer Science |
Committee: | Prof. Ton Dieker, Department of Industrial Engineering and Operations Research (Columbia University) |
Prof. Dana Randall, School of Computer Science | |
Prof. Prasad Tetali, School of Mathematics | |
Prof. Eric Vigoda, School of Computer Science | |
Reader: | Prof. Ton Dieker, Department of Industrial Engineering and Operations Research (Columbia University) |
SUMMARY: High-dimensional sampling and integration is a shining example of the power of randomness in computation, where randomness provably helps. Additionally, the theoretical advances for these problems seem to lead to efficient algorithms in practice. The algorithms and techniques extend to a variety of fields, such as operations research and systems biology. The main contribution is an O*(n3) randomized algorithm for estimating the volume of a well-rounded convex body, improving on the previous best complexity of O*(n4). 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. Building to this result, algorithmic improvements for Gaussian sampling and integration are developed. A crucial algorithmic ingredient is analyzing an accelerated cooling schedule with Gaussians that achieves a perfect trade-off with the complexity of Gaussian sampling. The theoretical insights transfer over to efficient algorithms in practice, as is demonstrated by a MATLAB adaptation of the volume algorithm. The performance vastly exceeds the current best deterministic algorithms. Additionally, an implementation of the sampling algorithm, when applied to systems biology for the analysis of metabolic networks, significantly advances the frontier of computational feasibility.