Glass transitions and algorithmic barriers in high-dimensional energy landscapes

高维能源景观中的玻璃化转变和算法障碍

• 批准号: RGPIN-2020-04597
• 负责人: Jagannath, Aukosh
• 金额: $ 2.4万
• 依托单位: University of Waterloo
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2020
• 资助国家: 加拿大
• 起止时间: 2020-01-01 至 2021-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=717229
• 关键词: Glass; transitions; algorithmic; barriers; dimensional

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.

高维能量景观出现在定量科学的许多学科中。概率、统计学和统计物理学中的经典方法非常适合于那些本质上是低维系统的景观，在这些系统中，相应的景观只有少量的临界点，或者通过良好的可观测值选择可以简化为有限维问题。然而，在许多感兴趣的问题中，人们期望临界点的数量与状态空间本身的体积相当，两者都在维度上呈指数增长。