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.