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; 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和协作者将对这些主题进行最新的调查。在许多层面上进行采样，学习和优化在许多层面上都复杂地联系在一起：从一个主题到另一个主题之间的减少，从一个应用于另一个主题到另一个主题的洞察力，适用于另一个主题，常见的分析技术和相似的上下文（例如，大型，高维数据）。该项目是由寻求一种有效算法理论的动机，该理论将包括算法工具，下限和分析技术，除了从任务中引起的问题，但具有独立的数学兴趣，并为经典领域提供了新的想法。 Riemannian几何形状；学习Polyhedra的算法，具有单个隐藏层的神经网络的分析，在存在噪声的情况下进行的稳健估计和无监督的学习以及在非常大的（但不是密集）图的表示和分析中的算法考虑因素。