CAREER: Unbiased Estimation with Faithful Markov Chains for Scalable Statistical Inference

Harvard University, Cambridge MA

Investigators

Abstract

Numerical integration is a common goal in all scientific fields where complex probabilistic models need to be simulated and calibrated. In statistics, numerical integration is used in virtually all tasks, from parameter inference to model averaging and hypothesis testing. Among state-of-the-art numerical integration techniques, most methods are randomized algorithms that operate iteratively, generating a sequence of random states, one after the other. Unfortunately, their iterative nature stands at odds with current directions in computing hardware: increasingly parallel architectures and stagnating clock rates. This research develops new algorithms that provide accurate estimates of integrals as a number of random quantities, that can be generated independently and in parallel, goes to infinity. The proposed techniques are employed to address long-standing challenges in statistical inference for large models and complex data. The proposed innovations combine applied probability, computer science and statistical computing, and apply to many fields including machine learning, statistical mechanics, computational neuroscience and epidemiology, where high-dimensional integrals abound. The project involves the development of software and features an educational program with courses and research opportunities for students, and a broader dissemination program. To numerically approximate high-dimensional integrals, Markov Chain Monte Carlo methods iteratively generate sequences that explore the landscape described by the integrand. These methods yield estimators that converge to the integrals of interest in the limit of the number of iterations. However, algorithms that rely on iterative asymptotic regimes risk becoming obsolete in the era of parallel computing hardware. The proposed research develops new Monte Carlo estimators that are unbiased for the expectations of interest, while having a finite computing cost and a finite variance. They can thus be generated independently in parallel and averaged over, paving the way for scalable numerical integration on large-scale parallel computers. The proposed estimators rely on faithful couplings of Markov chains, whereby pairs of chains coalesce after a random number of iterations. This project includes theoretical investigations on the efficiency of the proposed estimators, and the design of practical coupling strategies for various applications. The research connects with topics in numerical methods, stochastic processes and optimal transport. Beyond parallel computing, the proposed estimators are used to tackle statistical challenges such as normalizing constant estimation and modular inference for large models made of multiple components. 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.