权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

Inference in High-Dimensional Statistical Models: Algorithmic Tractability and Computational Barriers

高维统计模型中的推理：算法易处理性和计算障碍

基本信息

批准号：
2015517
负责人：
David Gamarnik
金额：
$ 20万
依托单位：
Massachusetts Institute of Technology
依托单位国家：
美国
项目类别：
Standard Grant
财政年份：
2020
资助国家：
美国
起止时间：
2020-09-01 至 2023-08-31
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=2015517&HistoricalAwards=false
关键词：
Inference Dimensional Statistical Models Algorithmic

项目摘要

Extracting knowledge from data using statistical and machine learning methods often involves computations, which don't scale well with dataset sizes. This is dictated by the necessity of analyzing large scale statistical models, where the scale of the data ever increases due to our unprecedented ability to accumulative massive amounts of it. Often this leads to models where the number of parameters far exceeds the amount of collected data, rendering many classical inference models ill-posed and classical computational methods prohibitively time consuming. Thus the value brought about by the abundance of data comes at the expense of the necessity to develop completely novel computational tools that are capable of dealing with the curse of dimensionality. While there is an abundance of literature devoted to designing efficient computational methods of inference in high-dimensional statistical models, it was discovered that many algorithms hit a certain computational barrier, beyond which seemingly only brute-force and thus computationally prohibitive algorithms can succeed. Not much is known regarding the fundamental computational limitations arising above this barrier, which is popularly dubbed the nformation Theoretic vs Computation gap. What is the origin of this barrier? Does it indeed correspond to the onset of algorithmically intractable problems, or is it just a matter of being more clever about designing faster algorithms? The project also provides research training opportunities for graduate students. In the present project the PI develops a completely novel approach for understanding fundamental computational barriers arising in high dimensional statistical models. The approach is based on powerful and illuminating insights derived from the field of statistical physics, specifically the theory of spin glasses. In particular, the PI intends to establish that the onset of the algorithmic barriers is caused by phase transition in the landscape of the solution space, marking a drastic change in the solution space geometry of underlying inference problems. This change in geometry of the solution space landscape taking the form of the so-called Overlap Gap Property (OGP), can further be used to rule out broad classes of algorithms as potential contenders to bridge the information theoretic and algorithmic gap. These classes of algorithms include algorithms based on local improvements, such as Gradient Descent and Stochastic Gradient Descend algorithms, algorithms based on Markov Chain Monte Carlo Method, algorithms broadly defined as Approximate Message Passing iterations, and algorithms based on constructing low-degree polynomials. The PI in particular intends to investigate the validity of a bold conjecture stating that for most, if not all of the known models exhibiting apparent algorithmic barriers, the onset of this barrier coincides with the onset of the OGP. The PI intends to investigate this conjecture in the context of several widely studied modern models of high dimensional statistics and machine learning fields, including the Stochastic Block Model, the Spiked Tensor Model, and Wide Neural Networks model. All of these models are known to exhibit an apparent algorithmic hardness in some parameter regimes and thus these models offer a valuable framework for investigating the validity of the aforementioned conjecture, as well as algorithmic intractability implications.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.

使用统计和机器学习方法从数据中提取知识通常涉及计算，这些计算不能很好地扩展数据集的大小。这是由分析大规模统计模型的必要性所决定的，由于我们前所未有的积累大量数据的能力，数据的规模不断增加。这通常会导致模型的参数数量远远超过所收集的数据量，使许多经典推理模型不适定，并且经典计算方法非常耗时。因此，丰富的数据带来的价值是以开发全新的计算工具的必要性为代价的，这些工具能够处理维度的诅咒。虽然有大量的文献致力于在高维统计模型中设计高效的推理计算方法，但人们发现许多算法都遇到了一定的计算障碍，超过这个障碍似乎只有蛮力算法才能成功，因此计算上是禁止的。关于在这个屏障之上产生的基本计算限制，人们知之甚少，这通常被称为信息理论与计算差距。这个势垒的起源是什么？它是否确实与算法棘手问题的开始相对应，还是仅仅是设计更快算法的更聪明的问题？该项目还为研究生提供研究培训机会。在目前的项目中，PI开发了一种全新的方法来理解高维统计模型中产生的基本计算障碍。该方法基于统计物理学领域，特别是自旋玻璃理论的强大而有启发性的见解。特别是，PI打算确定算法障碍的开始是由解空间景观中的相变引起的，这标志着潜在推理问题的解空间几何结构的巨大变化。这种以所谓的重叠间隙属性（OGP）形式出现的解空间景观的几何变化，可以进一步用于排除作为弥合信息理论和算法差距的潜在竞争者的广泛算法类别。这类算法包括基于局部改进的算法，如梯度下降和随机梯度下降算法，基于马尔可夫链蒙特卡罗方法的算法，广义上定义为近似消息传递迭代的算法，以及基于构造低次多项式的算法。PI特别打算调查一个大胆猜想的有效性，该猜想指出，对于大多数（如果不是全部的话）表现出明显的算法障碍的已知模型，这种障碍的开始与OGP的开始是一致的。PI打算在几个被广泛研究的高维统计和机器学习领域的现代模型的背景下研究这一猜想，包括随机块模型、尖刺张量模型和宽神经网络模型。已知所有这些模型在某些参数制度中表现出明显的算法硬度，因此这些模型为调查上述猜想的有效性以及算法的难治性含义提供了有价值的框架。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。