AF:Small: Fundamental High-Dimensional Algorithms

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

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.