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

职业：高维统计问题的可归约性：信息保存映射、算法和复杂性。

• 批准号: 1940205
• 负责人: Guy Bresler
• 金额: $ 65万
• 依托单位: Massachusetts Institute of Technology
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2020
• 资助国家: 美国
• 起止时间: 2020-02-01 至 2025-01-31
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1940205&HistoricalAwards=false
• 关键词: CAREER; Reducibility; among; dimensional; statistics

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.

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

项目成果

Phase transitions for detecting latent geometry in random graphs

用于检测随机图中潜在几何形状的相变

• DOI: 10.1007/s00440-020-00998-3
• 发表时间: 2020
• 期刊: Probability Theory and Related Fields
• 影响因子: 2
• 作者: Brennan, Matthew;Bresler, Guy;Nagaraj, Dheeraj
• 通讯作者: Nagaraj, Dheeraj

Minimax Prediction in Tree Ising Models

Tree Ising 模型中的极小极大预测

• DOI: 10.1109/isit44484.2020.9174341
• 发表时间: 2020
• 期刊: IEEE International Symposium on Information Theory
• 作者: Bresler, Guy;Karzand, Mina
• 通讯作者: Karzand, Mina

Learning a Tree-Structured Ising Model in Order to Make Predictions

• DOI: 10.1214/19-aos1808
• 发表时间: 2016-04
• 期刊: ArXiv
• 作者: Guy Bresler;Mina Karzand

Learning Restricted Boltzmann Machines with Sparse Latent Variables

学习具有稀疏潜变量的受限玻尔兹曼机

• 发表时间: 2020
• 期刊: Advances in neural information processing systems
• 作者: Bresler, Guy;Buhai, Rares-Darius.
• 通讯作者: Buhai, Rares-Darius.

Metastable mixing of Markov chains: Efficiently sampling low temperature exponential random graphs

• DOI: 10.1214/23-aap1971
• 发表时间: 2022-08
• 期刊: The Annals of Applied Probability
• 作者: Guy Bresler;Dheeraj M. Nagaraj;Eshaan Nichani