High-dimensional sets and distributions are ubiquitous in science and engineering. With modern sensing and data collection methods, the bottleneck is now the analysis of such complex sets. Algorithms that work well in low-dimension often do not scale well as the dimension increases. Thus, understanding the complexity of basic problems such as optimization (the best point in a set) or integration (the total mass of a set) or learning (so as to be able to decide which points are in the set and which aren't) is critical, and is the motivation for this project.
An important method to handle data in high dimension is sampling by random walks. The PI will investigate methods to test the convergence of Geometric Random Walks "on-the-fly." Such methods would significantly improve the performance of Markov chain based algorithms by providing nearly optimal empirical tests of convergence. They would allow algorithms to have complexity that is tuned to the specific input rather than the worst-case input. As an application, the PI will investigate faster rounding algorithms for high-dimensional convex bodies and log-concave distributions. The methods and techniques developed here will be of interest to researchers in probability and geometry as well as those in algorithms and complexity.
The PI proposes two specific functions to test the convergence of the ball walk in a convex body and a specific rounding algorithm. Both seem to perform well in experiments. Analyzing them rigorously presents major challenges because known techniques from probability theory are typically only able to say something about a Markov chain when it is close to its stationary distribution. The fundamental question here is: what structure does the distribution of a Markov chain have, *before* it converges?
