AF: EAGER: Fundamental High-Dimensional Algorithms

AF：EAGER：基本高维算法

• 批准号: 1555447
• 负责人: Santosh Vempala
• 金额: $ 10万
• 依托单位: Georgia Tech Research Corporation
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2015
• 资助国家: 美国
• 起止时间: 2015-09-01 至 2016-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1555447&HistoricalAwards=false
• 关键词: AF; EAGER; Fundamental; Dimensional; Algorithms

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?

高维集和分布在科学和工程中无处不在。借助现代感测和数据收集方法，瓶颈现在是对这种复杂集的分析。在低维度上运作良好的算法通常不会随着尺寸的增加而缩小不佳。因此，了解基本问题的复杂性，例如优化（集合中的最佳点）或集成（集合的总质量）或学习（以便能够确定该点在集合中，哪些不是）至关重要，这是该项目的动机。处理高维数据的重要方法是由随机步行采样。 PI将调查“即时”测试几何随机步行的收敛方法。通过提供几乎最佳的收敛经验测试，这种方法将显着改善基于马尔可夫链的算法的性能。它们将允许算法具有调谐到特定输入而不是最坏情况输入的复杂性。作为应用程序，PI将研究更快的圆形算法，以实现高维凸形和对数凸出分布。研究人员在概率和几何形状以及算法和复杂性中所开发的方法和技术都将引起人们的关注。PI提出了两个特定功能，以测试在凸体中和特定圆形算法中球行走的收敛性。两者似乎在实验中表现良好。严格地分析它们，提出了主要挑战，因为概率理论的已知技术通常只能说马尔可夫链接近其固定分布时。这里的基本问题是：马尔可夫链的分布有什么结构， *在 *融合之前 *？