AF: EAGER: Fundamental High-Dimensional Algorithms

高维集合和高维分布在科学和工程中是普遍存在的。随着现代传感和数据收集方法的发展，现在的瓶颈是对这些复杂集合的分析。在低维环境下工作良好的算法通常不能随着维度的增加而很好地扩展。因此，了解优化(集合中的最优点)、积分(集合的总质量)或学习(从而能够确定哪些点在集合中，哪些不在集合中)等基本问题的复杂性是至关重要的，也是本项目的动机。处理高维数据的一个重要方法是随机游动采样。PI将研究测试几何随机游动“即时”收敛的方法。这种方法通过提供近乎最优的收敛经验测试，将显著提高基于马尔可夫链的算法的性能。它们将允许算法具有针对特定输入而不是最坏情况的输入进行调整的复杂性。作为应用，PI将研究高维凸体和对数凹分布的更快的舍入算法。本文提出的方法和技术将引起概率和几何研究者以及算法和复杂性研究者的兴趣。PI提出了两个特定的函数来测试凸体中球行走的收敛和一个特定的舍入算法。这两种方法在实验中似乎都表现良好。严格地分析它们是一项重大挑战，因为已知的概率论技术通常只能在马尔科夫链接近其平稳分布时才能说出一些东西。这里的基本问题是：在马尔科夫链收敛之前，它的分布有什么结构？

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?