AF: Small: Fundamental High-Dimensional Algorithms

AF：小：基本的高维算法

基本信息

批准号：
2007443
负责人：
Santosh Vempala
金额：
$ 40万
依托单位：
Georgia Tech Research Corporation
依托单位国家：
美国
项目类别：
Standard Grant
财政年份：
2020
资助国家：
美国
起止时间：
2020-08-01 至 2024-07-31
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=2007443&HistoricalAwards=false
关键词：
AF Small Fundamental Dimensional Algorithms

项目摘要

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.

在无数应用中，高维数据的可用性使高效且通用的算法工具成为了迫切需要。该项目探讨了在高维度中满足这一需求的基本问题：如何计算卷？如何使用约束优化？如何从所需的分布中采样？如何从样品中学习？这些问题的进展将建立新兴数据科学的基础。研究人员通常与其他学科的科学家合作，以确定具体的挑战。他将继续组织协作研讨会，写出该项目发现的最新研究调查，以及有关连续算法的教科书，并维护开源软件，以进行最新的抽样，这是该项目的主要目标。从优化到采样问题。具体而言，它将探索非convex优化和采样算法，以实现强大的聚类和学习（在存在对抗性噪声的情况下），通过利用Riemannian几何形状来更快采样，并通过利用坎南 - 洛瓦斯·塞米诺维特人的最新进展来计算，以进行数量计算。它还将探索对流形的这种猜想，以及对多元卷的确定性算法的可能性。该奖项反映了NSF的法定任务，并被认为是值得通过基金会的知识分子和更广泛影响的审查标准来通过评估来获得支持的。