AF:Small: Fundamental High-Dimensional Algorithms

AF:Small：基本的高维算法

基本信息

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

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

项目摘要

The availability of high-dimensional data in important application areas has made efficient tools to handle such data the need of the century. This proposal addresses some of the most basic questions arising from this need. The topics targeted in this project are on the frontier of research in algorithms, targeting well-known open problems with promising new ideas. Progress on these problems is sure to unravel mathematical structure and is likely to yield new tools. As the field of algorithms continues to expand (and extend its reach beyond computer science), such tools have become indispensable.The PI was the founding director of the Algorithms and Randomness Center (ARC) and continues in-depth collaborations with scientists from other fields to identify problems and ideas that could play a fundamental role in understanding the complexity of computation. The topics and findings of this project will be used to design graduate courses and contribute to undergraduate ones. The graduate courses will be the basis for textbooks to benefit the research community. In addition, up-to-date surveys on these topics will be prepared by the PI and collaborators.Sampling, Learning and Optimization in high dimension are intricately linked at many levels: reductions between problems from one topic to another, insights from one that apply to another, common analysis techniques and similar contexts (e.g., large, high-dimensional data). This project is motivated by quest for a theory of efficient algorithms, a theory that would include algorithmic tools, lower bounds and analysis techniques, in addition to questions that arise from the quest but are of independent mathematical interest and provide new ideas for classical fields.Specifically, the project seeks to find efficient algorithms for sampling in the oracle model as well as for explicit polytopes, faster sampling and optimization using Riemannian geometry; algorithms for learning polyhedra, the analysis of neural networks with a single hidden layer, robust estimation and unsupervised learning in the presence of noise, and algorithmic considerations in the representation and analysis of very large (but not dense) graphs.

高维数据在重要应用领域的可用性使得处理此类数据的有效工具成为本世纪的需要。该提案解决了因这一需求而产生的一些最基本的问题。该项目的主题是算法研究的前沿，针对众所周知的开放问题和有前景的新想法。这些问题的进展肯定会解开数学结构，并可能产生新的工具。随着算法领域不断扩展（并将其范围扩展到计算机科学之外），此类工具已变得不可或缺。PI 是算法和随机性中心（ARC）的创始主任，并继续与其他领域的科学家进行深入合作识别在理解计算复杂性方面可以发挥基础作用的问题和想法。该项目的主题和研究结果将用于设计研究生课程并为本科生课程做出贡献。研究生课程将成为教科书的基础，使研究界受益。此外，PI 和合作者将准备有关这些主题的最新调查。高维度的采样、学习和优化在许多层面上错综复杂地联系在一起：从一个主题到另一个主题的问题之间的简化，从适用的主题中获得的见解另一方面，常见的分析技术和类似的环境（例如，大型、高维数据）。该项目的动机是寻求高效算法的理论，该理论将包括算法工具、下界和分析技术，以及在探索中产生但具有独立数学兴趣并为经典领域提供新思想的问题。具体来说，该项目旨在寻找有效的算法，用于预言模型中的采样以及显式多面体、使用黎曼几何的更快采样和优化；学习多面体的算法，具有单个隐藏层的神经网络的分析，存在噪声的鲁棒估计和无监督学习，以及非常大（但不密集）图的表示和分析中的算法考虑。