权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

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.

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