CAREER: Sampling, learning and testing spin systems

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

Spin systems are ubiquitous in science and engineering. They provide a robust mathematical model for studying complex systems of small interacting particles and are thus used to tackle central scientific challenges. They originated in statistical physics, and, in the last few decades, they have gained prominence in computational biology, machine learning, and theoretical computer science. This project focuses on the fundamental computational problems that emerge from the study of spin systems. Specifically, it aims to advance the theoretical understanding of such problems; this is well-known to improve the performance and reliability of applications that utilize spin systems.The project focuses on the problems of sampling, learning, and testing, which are among the most frequently encountered computational tasks in the context of spin systems. The first research direction of the project concerns the study of Markov chain Monte Carlo (MCMC) sampling algorithms for spin systems. These algorithms often rely on heuristics and empirical approaches to certify convergence, resulting in biased samplers and unreliable experimental outcomes. As such, the project focuses on the rigorous analysis of the convergence rates of MCMC algorithms. For this, several techniques for analyzing Markov chains will be developed or enhanced, addressing the well-known limitations of the available tools for Markov-chain analysis. The second direction of the project concerns the two closely related inference problems of identity testing and structure learning. This project's unified study of sampling, learning, and testing is novel. It will create essential connections and blend ideas from machine learning, statistical physics, and theoretical computer science.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.