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 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.