RI: Small: Gradient-Based Discrete Markov Chain Monte Carlo: Algorithms, Theoretical Foundations, and Applications

This project addresses a central challenge in artificial intelligence (AI) and data science: how to make accurate and reliable decisions when dealing with complex, discrete data; that is, data made up of distinct elements like words, networks, or molecular structures. Many important tasks in science, engineering, and everyday technology rely on the ability to reason under uncertainty in these settings. However, current algorithms often struggle to efficiently explore the vast space of possibilities such data can represent. This research will develop a new class of sampling algorithms designed to be faster, more scalable, and more statistically reliable, making it easier for machine learning systems to handle discrete data effectively. These advances will support the development of trustworthy AI systems, improve scientific simulations, and enable more controllable generative models in areas like drug design, recommendation systems, and natural language processing. By releasing open-source tools and training a diverse group of students and researchers, the project also contributes to the broader scientific community and helps build a skilled workforce. In doing so, it supports the national interest by advancing the progress of science, promoting innovation, and enhancing economic and societal well-being. This project develops a new framework for discrete Markov chain Monte Carlo (MCMC) algorithms that leverages gradients. The proposed gradient-based discrete MCMC (GD-MCMC) approach provides more informed exploration and significantly improves convergence compared to traditional methods. The research plan is structured into three thrusts. The first thrust focuses on developing algorithmic innovations for MCMC in non-log-concave and non-smooth discrete distributions. The second thrust establishes theoretical foundations by providing convergence guarantees for both log-concave and non-log-concave settings. The third thrust demonstrates practical impact in both machine learning and scientific domains, with applications in discrete generative models and molecular optimization. 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.