Glass transitions and algorithmic barriers in high-dimensional energy landscapes

高维能量景观出现在定量科学的许多学科中。概率、统计学和统计物理学中的经典方法非常适合于本质上是低维的景观系统，在这些系统中，相应的景观只有少量的临界点，或者通过良好的可观测值选择可以简化为有限维的问题。然而，在许多感兴趣的问题中，人们期望临界点的数量与状态空间本身的体积相当，两者都在维度上呈指数增长。该研究的长期目标是了解高维、复杂能量景观的统计特性，以及这些特性如何影响这些景观上的算法和动力系统的行为。为此，PI将从两个看似不同的角度来研究这些问题：(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 dimensional-systems 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.