UC Berkeley

Sampling algorithms based on Markov chain Monte Carlo (MCMC) are ubiquitous across theory and practice. The success of MCMC algorithms is typically established by upper bounding their mixing time, and over the past several decades a rich theory for doing so has emerged.However, classical mixing time based arguments fail to explain why MCMC has been so successful for statistical inference and the scientific simulation. The classical notion of rapid worst-case mixing is often too stringent of a notion to apply to these settings. Instead, one needs to analyze warm start mixing, or analyze the inference and optimization performance of MCMC before it has mixed. In this thesis, we build new theory in these directions to explain MCMC’s success in these difficult-to-understand settings.We then pivot to an entirely different subject matter altogether: that of synthetic data in modern machine learning. We study the counterintuitive success of synthetic data in regimes where the data is generated from models that are weaker than their students. We also probe the limitations of synthetic data to elicit certain reasoning behaviors from language models.