CAREER: Analysis of Slowly Mixing Markov Chains

Northwestern University, Evanston IL

Investigators

Abstract

Markov chains are an important family of stochastic processes used in many scientific fields, including sampling and optimization algorithms and physical modeling of thermodynamics. In recent decades, their mathematical study has been oriented around the time to converge to an equilibrium state from a worst-case initialization, known as the mixing time. Often, however, the worst-case mixing time is much larger than the convergence time from typical initializations. This project will develop the theory of convergence times from commonly encountered initializations when worst-case mixing times are slow. The research program will be complemented by educational activities, including a summer school for graduate students focused on the interplay between high-dimensional probability, data science, and machine learning. The project will also support the PI’s engagement with the broader scientific community around developing solid theoretical foundations to parallel the rapid acceleration of artificial intelligence capabilities. The project also provides research opportunities for graduate students. The research aims of the project are focused on developing mathematical tools for studying equilibration of Markov chains in high-dimensional spaces from nice initializations (e.g., random or high-temperature) when worst-case mixing times are exponentially slow in the dimension. Markov chains to be studied include families appearing in (1) Markov chain Monte Carlo sampling in computer science, (2) low-temperature Glauber dynamics in statistical physics, and (3) optimization algorithms on non-convex loss landscapes in machine learning. A core goal is to put the scientific understanding of simulated annealing, metastability, and the role of initialization in high dimensions on a more rigorous mathematical footing. 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.