AF: Small: Fundamental High-Dimensional Algorithms

大量应用程序中高维数据的可用性使得高效和通用的算法工具成为迫切需要。本项目探讨了解决高维需求的基本问题：如何计算体积？如何在约束条件下进行优化？如何从所需的分布中进行抽样？如何从样本中学习？在这些问题上的进展将为新兴的数据科学奠定基础。研究人员经常与其他学科的科学家合作，以确定具体的挑战。他将继续组织协作研讨会，撰写了解该项目发现的最新研究调查，以及一本关于连续算法的教科书，并维护用于最先进采样的开源软件。该项目的主要目标是从三个方面扩展算法技术：从欧几里得几何到非欧几里得几何，从凸到非凸环境，从优化到采样问题。具体地说，它将探索非凸优化和采样的算法，稳健的聚类和学习(在存在对抗性噪声的情况下)，利用黎曼几何进行更快的采样，以及通过利用Kannan-Lovasz-Simonovits超平面猜想的最新进展来进行体积计算的算法。它还将探索这样一个流形的猜想，以及多面体体积的确定性算法的可能性。这个奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

The availability of high-dimensional data in a myriad of applications makes efficient and general-purpose algorithmic tools a critical need. This project explores basic questions to address this need in high dimension: How to compute the volume? How to optimize with constraints? How to sample from a desired distribution? How to learn from samples? Progress on these questions will build the foundations of the emerging science of data. The investigator routinely collaborates with scientists from other disciplines to identify specific challenges. He will continue to organize collaborative workshops, write up-to-date research surveys informed by the discoveries of this project, as well as a textbook on Continuous Algorithms, and maintain open-source software for state-of-the-art sampling.The major goal of this project is to extend algorithmic techniques in three ways: from Euclidean to non-Euclidean geometries, from convex to non-convex settings and from optimization to sampling problems. Concretely, it will explore algorithms for non-convex optimization and sampling, for robust clustering and learning (in the presence of adversarial noise), for faster sampling by utilizing Riemannian geometries, and for volume computation by leveraging recent progress on the Kannan-Lovasz-Simonovits hyperplane conjecture. It will also explore such a conjecture for manifolds, and the possibility of a deterministic algorithm for polytope volume.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.