CRII: AF: Markov Chain Monte Carlo Algorithms for Spin Systems

Generating samples from probability distributions is a fundamental computational task in science, engineering, and technology. Efficient and unbiased sampling algorithms have a significant impact in a variety of fields, notably including statistics, biology, physics, and computer science. The Markov chain Monte Carlo (MCMC) method provides a powerful class of sampling algorithms used by an active community of researchers in diverse applications, typically relying on heuristics for their design and analysis. This project focuses on the theoretical study of MCMC algorithms, aiming to increase their reliability and to reduce computational costs in practice. Two application areas will be most relevant: statistical physics and machine learning. Most of the work will be carried out in close collaboration with graduate students; the training provided will be conducive to their development as researchers. The PI will consider the problem of sampling from Gibbs (or Boltzmann) distributions in the context of spin systems, a general framework for modeling interacting systems of simple elements. In this context, the PI intends to rigorously analyze the efficiency of popular MCMC algorithms. Two specific foci will be the Alternating Scan dynamics for bipartite systems and the Swendsen-Wang algorithm for the classical Ising/Potts model from statistical physics. The former is actively used to train Restricted Boltzmann Machines and build sophisticated deep learning architectures, while the latter is a standard method for sampling from the Ising/Potts distribution. The PI will also study the interplay between the efficiency of MCMC algorithms and the phase transitions of the underlying probabilistic model. Additional computational implications of these phase transitions will be explored in the context of structure learning, a closely related supervised learning problem. As such, the connections between theoretical computer science, statistical physics, and machine learning will play a central role in this project. 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.