Sampling and finding solutions in spin systems and neural networks

The objective of this project is to analyze the structural and algorithmic characteristics of high-dimensional probability models encountered in statistical inference and physics. Fundamental questions regarding the feasibility of extracting information from noisy data and executing efficient computations on it can be formulated within the framework of spin systems—models comprising a large number of locally interacting variables defined on a graph. The emergent global behavior of such systems provides insights into the statistical and computational limits of inference. Notably, varying the interaction strength can induce phase transitions, leading to significant reconfigurations of the probability mass. These transitions often delineate the boundary between algorithmically tractable and intractable regimes. The project aims to characterize the computational relevance of these transitions, devise efficient algorithms for the tractable phase, and establish lower bounds on algorithmic performance in the intractable phase. This project will focus on a class of canonical probabilistic models such as variants of the Ising model, mean-field spin glasses and perceptron models of neural networks. A primary objective is to design and analyze efficient algorithms for sampling from the associated Gibbs distributions and for finding lowest energy (or ground state) configurations. A second objective is to examine the concentration properties and possibly chaotic behavior under perturbation of the Gibbs measure. These aspects will be studied in relation to their algorithmic and statistical implications, with the aim of understanding how the geometry of the underlying energy landscape influences computational feasibility and inference performance. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.