CAREER:Reducibility among high-dimensional statistics problems: information preserving mappings, algorithms, and complexity.

大规模的数据收集和分析正在改变科学、工程和工业。其核心是，应用程序依赖于统计推断，即从噪声数据中提取意义。这是一项挑战，不仅因为规模庞大，而且还因为必须经常利用复杂的底层结构。执行推理任务的两个基本资源是(1)数据，数据在质量和数量上可以变化；(2)计算。这似乎是一种权衡：计算上不可行的算法所需的最小数据量通常远远少于所有已知的计算效率高的算法所需的数据量。由于对这种权衡的理解很差，该项目的目标是为结构化推理问题的算法的最佳计算和统计效率的推理创建数学基础。通过与商业、经济、医疗技术、社会网络分析、遗传学、神经科学和许多其他领域的基本程序和方法相关的新的基本见解，可能会产生重大的社会影响。此外，作为协同研究和教育计划的一部分，该项目将采取多方面的STEM教育方法，包括：(1)指导本科生和研究生进行研究；(2)拓展高中和本科群体；(3)为本科生创造与项目相关主题的合作研究体验；(4)开发麻省理工学院的新课程，包括高级本科和博士课程。该项目旨在发展统计推理的综合平均情况复杂性理论，类似于组合问题的经典P对NP理论，表征推理何时有效可解或不有效可解，并显示问题之间的强等效性。大部分技术方法是基于开发平均情况约简的新技术，从而产生不同问题之间的精确关系。平均情况约简将一个问题转换为另一个问题，这意味着对每个问题所需的数据和计算资源进行比较。除了描述基本限制之外，本项目所追求的方法将产生算法和见解。通过创建问题之间的约简网络，将有可能将一个问题的算法转换为其他问题的算法。此外，通过这种双向约简得到的强等价将表明，同样的现象出现在看似不同的问题中，因为它们的核心是同一个问题。该项目有可能改变研究统计推断问题的基本方法。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

Large-scale data collection and analysis is transforming science, engineering, and industry. At their core, applications rely on statistical inference whereby meaning is extracted from noisy data. This is challenging due not only to the sheer scale, but also the complex underlying structure that must often be exploited. The two basic resources for carrying out an inference task are (1) data, which can vary in quality and quantity; and (2) computation. There appears to be a trade-off: The minimum amount of data needed by computationally infeasible algorithms is often far less than what is required by all known computationally efficient algorithms. As this trade-off is poorly understood, the objective of the project is to create the mathematical foundations for reasoning about the optimal computational and statistical efficiency of algorithms for structured inference problems. Significant societal impact may be possible via new fundamental insights relevant to basic procedures and methods used across business, economics, medical technology, social network analysis, genetics, neuroscience, and many other domains. Furthermore, as part of a synergistic research and education plan, the project will take a multi-faceted approach to STEM education, including: (1) mentorship of both undergraduate and graduate students in research; (2) outreach to both high school and undergraduate groups; (3) creation of a collaborative research experience for undergraduate students on topics related to the project; and (4) development of new courses at MIT, both at the advanced undergraduate and PhD levels. The project aims to develop a comprehensive average-case complexity theory of statistical inference, analogous to the classical P versus NP theory for combinatorial problems, characterizing when inference is or is not efficiently solvable and showing strong equivalences between problems. The bulk of the technical approach is based on developing new techniques for average-case reductions that yield precise relationships between different problems. Average-case reductions transform one problem into another, implying a comparison between the data and computation resources required by each. In addition to characterizing fundamental limits, the approach pursued in this project will result in algorithms and insights. By creating a web of reductions between problems, it will be possible to translate algorithms for one problem into algorithms for other problems. Furthermore, strong equivalences obtained via such two-way reductions will show that the same phenomenon appears in seemingly different problems because they are at their core the same problem. The project has the potential to change the basic methodology for studying statistical inference problems.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.