Glass transitions and algorithmic barriers in high-dimensional energy landscapes

高维能量景观出现在定量科学的许多学科中。概率、统计学和统计物理中的经典方法非常适合于本质上是低维系统的景观，其中相应的景观只有少量的临界点，或者可以通过选择好的观察量来简化为有限维的问题。然而，在许多感兴趣的问题中，人们预计临界点的数量与状态空间本身的体积相当，两者在维度上呈指数增长。 这项拟议研究的长期目标是了解高维、复杂能量景观的统计特性，以及这些特性如何影响算法和动力系统在这些景观上的行为。为此，公安部将从两个看似截然不同的角度调查这些问题： (1)开发从统计物理研究玻璃化转变的框架 (2)高维统计问题中信息理论和算法阈值的分析。 第一个观点将进一步为自旋玻璃的动力学和结构理论奠定严密的基础。这个问题是自旋眼镜研究的核心。我们将把重点放在玻璃阶段，这是使用启发式“复制对称破缺”和“腔方法”技术开发的理解的中心。第二部分将加深我们对统计学中出现的高维优化问题的理解。尽管这些研究路线看起来截然不同，但它们实际上是一枚硬币的两面。这项工作的很大一部分将调查这类问题之间的许多深层次联系。 这项研究将集中在统计物理和数据科学交界处的数学问题上。它将涉及随机分析、概率、变分和偏微分方程组的技术组合。 预期的影响。围绕着对这些问题的研究，物理学、计算机科学和信息论中有许多充满活力的团体。他们为我们对领域的理解做出了许多贡献。然而，这些工作中的大部分都缺乏严谨的理论基础。这项研究的目标就是帮助建立这样的基础。 这项工作将立即为这些不同领域的研究人员提供分析硬度转变的严格方法。随着维度的增加，这些方法变得更加健壮。这方面的最新进展已经改变了这些社区理解和继续其研究议程的方式，但仍有许多工作要做。最后，这项提案的许多组成部分构成了适合广泛HQP的研究项目。

High-dimensional energy landscapes appear in many disciplines in the quantitative sciences. Classical methods in probability, statistics, and statistical physics are well-suited to landscapes that are intrinsically low dimensionalsystems where the corresponding landscape has only a small number of critical points or can be reduced to a finite dimensional problem by a good choice of observables. In many problems of interest, however, one expects that the number of critical points is comparable to the volume of the state space itself, with both growing exponentially in the dimension. The long-term goal of the proposed research is to understand the statistical properties of high-dimensional, complex energy landscapes and how these properties affect the behaviour of algorithms and dynamical systems on these landscapes. To this end, the PI will investigate these questions from two seemingly distinct perspectives: (1) Developing a framework to study the glass transition from statistical physics (2) The analysis of information theoretical and algorithmic thresholds in problems in high-dimensional statistics. The first perspective will further the development of a rigorous foundation for the dynamical and structural theory of spin glasses. This question is at the heart of the study of spin glasses. We will focus on the glassy phase which is central to the understanding developed using the heuristic “replica symmetry breaking” and “cavity method” techniques. The second will further our understanding of high-dimensional optimization problems arising in statistics. Although these lines of research appear distinct, they are in fact two sides of the same coin. A large portion of this work will be investigating the many deep connections between these classes of problems. This research will focus on mathematical questions at the interface of statistical physics and data science. It will involve a combination of techniques from stochastic analysis, probability, variational calculus, and partial differential equations. Expected Impact. There are vibrant communities in physics, computer science, and information theory developing around the study of these questions. They have made many contributions to our understanding of fields. Much of this work, however, is lacking a rigorous theoretical foundation. The goal of this research is to help build such a foundation. This work will immediately provide researchers in these diverse fields with rigorous methods to analyze hardness transitions. These methods become more robust as the dimension increases. Recent progress in this direction has already made changes to how these communities understand and continue their research agendas, however there is still much to be done. Finally, there are many components of this proposal that constitute research projects appropriate for a wide range of HQP.