Glass transitions and algorithmic barriers in high-dimensional energy landscapes

点击翻译按钮获取中文摘要

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.