Efficiently learning and sampling multimodal distributions with data-based initialization
This addresses the challenge of slow mixing in Markov chains for sampling complex distributions, with implications for machine learning methods like score matching, though it is incremental in generalizing existing theoretical bounds.
The paper tackles the problem of efficiently sampling from multimodal distributions by using data-based initialization of Markov chains, showing that with a spectral gap condition, initialization from a small number of samples can generate samples close to the stationary measure in TV distance. It applies to mixtures and improves prior results by reducing dependence on the number of modes from exponential to linear, enabling efficient learning of low-complexity Ising measures.
We consider the problem of sampling a multimodal distribution with a Markov chain given a small number of samples from the stationary measure. Although mixing can be arbitrarily slow, we show that if the Markov chain has a $k$th order spectral gap, initialization from a set of $\tilde O(k/\varepsilon^2)$ samples from the stationary distribution will, with high probability over the samples, efficiently generate a sample whose conditional law is $\varepsilon$-close in TV distance to the stationary measure. In particular, this applies to mixtures of $k$ distributions satisfying a Poincaré inequality, with faster convergence when they satisfy a log-Sobolev inequality. Our bounds are stable to perturbations to the Markov chain, and in particular work for Langevin diffusion over $\mathbb R^d$ with score estimation error, as well as Glauber dynamics combined with approximation error from pseudolikelihood estimation. This justifies the success of data-based initialization for score matching methods despite slow mixing for the data distribution, and improves and generalizes the results of Koehler and Vuong (2023) to have linear, rather than exponential, dependence on $k$ and apply to arbitrary semigroups. As a consequence of our results, we show for the first time that a natural class of low-complexity Ising measures can be efficiently learned from samples.