AF: Small: High-dimensional geometry and probability for efficient inference

这个时代的一个基本挑战是推理，即从数据中提取信息。从算法的角度来看，一个特别的挑战是维数灾难。这涉及到随着数据特征数量的增长，计算成本呈指数级爆炸。该项目将促进对具有许多特征的数据的理解，并为数据摘要提供新的工具。它具有很高的潜力，导致新的实用算法的发展，从数据中提取信息。该项目的主要教育成果将是培训理论计算机科学博士生，并为本科生提供研究经验和指导。该项目将通过资助博士生参加关于数据科学基础和理论计算机科学其他方面的著名研讨会来丰富博士生的经验。该项目将设计用于有效推理的新工具，并巩固对现有工具的理解。重点将放在张量方法，反卷积和凸优化。基本的主题是使用的想法，从高维概率，离散和凸几何。这些选择的理由有两个。首先，研究团队在这些领域具有很高的素质。其次，这些基础字段提供了一些最强大的工具来理解高维数据。在该项目更广泛的主题中，该项目将重点关注（1）优化中的Frank-Wolfe方法，（2）盲和非盲反卷积以及与张量方法和高斯混合模型参数估计的相互作用，以及（3）描述和总结数据形状的几何工具。该项目将深入了解公认的挑战。虽然这些问题具有挑战性，但近年来在这些问题上取得了稳步进展，例如对张量方法的新见解。一个具体的智力机会是正确的工具，在高维概率和离散和凸几何的识别，提供深入了解新算法的设计推理和数据分析。在数据科学和优化的基础上提出的工作与随机多面体，随机矩阵，高维概率以及离散和凸几何有关。该奖项旨在提供更多的“异花授粉”实例，即理论工具可以帮助设计新的算法，而算法方法为理论领域提供了新的问题和动力。该奖项反映了NSF的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

A fundamental challenge of this time is inference, that is the extraction of information from data. A particular challenge from the algorithmic perspective is the curse of dimensionality. This involves the exponential explosion of computational cost as the number of features of the data grows. The project will advance the understanding of data with many features and provide new tools for data summarization. It has a high potential of leading to the development of new practical algorithms to extract information from data. The main educational outcome of the project will be to train PhD students in theoretical computer science and to provide research experience and mentoring to undergraduate students. The project will enrich the experience of PhD students by funding their attendance to prestigious workshops on the foundations of data science and other aspects of theoretical computer science.The project will design new tools for efficient inference and solidify understanding of existing tools. The focus will be on tensor methods, deconvolution and convex optimization. The underlying theme is the use of ideas from high-dimensional probability, and discrete and convex geometry. The rationale for these choices is twofold. Firstly, the research team is highly qualified in those fields. Secondly, those foundational fields provide some of the most powerful tools available to understand high-dimensional data. Within the broader topics of the project, this project will focus on (1) Frank-Wolfe methods in optimization, (2) blind and non-blind deconvolution and the interplay with tensor methods and parameter estimation for Gaussian mixture models, and (3) geometric tools to describe and summarize the shape of data. The project will provide insight into well-recognized challenges. While the questions are challenging, in recent years there has been steady progress on them, such as new insights into tensor methods. A specific intellectual opportunity is the identification of the right tools in high-dimensional probability and discrete and convex geometry that provide insight into the design of new algorithms for inference and data analysis. The proposed work on the foundations of data science and optimization has connections with random polytopes, random matrices, high-dimensional probability and discrete and convex geometry. The proposed work is expected to provide more instances of "cross-pollination," where theoretical tools can aid the design of new algorithms and the algorithmic approach provides new questions and motivations to theoretical fields.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.