Efficiently learning and sampling multimodal distributions with data-based initialization

Frederic Koehler, Holden Lee, Thuy-Duong Vuong

Abstract

Sampling from multimodal distributions using Markov Chain Monte Carlo (MCMC) methods is traditionally hindered by slow mixing times, as chains often become trapped in local modes. This paper demonstrates that if a Markov chain possesses a $k$-th order spectral gap, initializing the chain from a small set of $\tilde{O}(k/\varepsilon^2)$ samples from the stationary distribution allows for the efficient generation of new samples. We show that the conditional law of these samples is $\varepsilon$-close in Total Variation (TV) distance to the target measure. This framework is robust to perturbations, making it applicable to Langevin diffusion with score estimation error and Glauber dynamics with pseudolikelihood estimation. Notably, this work improves previous exponential dependencies on $k$ to linear ones and provides the first efficient algorithm for learning a natural class of low-complexity Ising measures.

Introduction: The Challenge of Multimodality

In the study of Markov chains, the "mixing time" serves as the primary metric for how quickly a process converges to its stationary distribution. For multimodal distributions—those characterized by multiple peaks or clusters separated by regions of low probability—mixing is typically "torpid." The chain becomes trapped in a single mode, unable to cross the bottlenecks required to explore the full state space. Consequently, standard MCMC methods often fail to represent the true distribution within a reasonable timeframe.

While practitioners have long utilized "warm starts" or data-based initialization to circumvent these bottlenecks, a rigorous theoretical foundation for this success has been limited. Previous research indicated that such initialization could work, but the required sample complexity scaled exponentially with the number of modes ($k$). This paper addresses this gap, providing a general framework that ensures efficient sampling with only a linear dependence on $k$.

Theoretical Framework: Higher-Order Spectral Gaps

The authors shift the focus from the standard spectral gap (which governs convergence from any arbitrary starting point) to the higher-order spectral gap.

1. Higher-Order Spectral Theory

If a distribution can be decomposed into $k$ well-connected components (such as a mixture of $k$ Gaussians), the transition matrix of the associated Markov chain will exhibit a significant gap after the $k$-th eigenvalue ($\lambda_{k+1}$). While the first $k$ eigenvalues may be very close to 1 (indicating slow mixing between modes), the gap after $\lambda_{k+1}$ indicates fast mixing within those modes.

2. Eigenfunction Balance

The core technical innovation of this work is the proof that an empirical distribution formed by $n$ samples is "eigenfunction balanced." This ensures that the starting distribution does not disproportionately favor the slow-mixing directions associated with the first $k$ eigenvalues. By starting from a distribution that is already "aware" of the various modes, the chain only needs to mix locally, which occurs much faster.

3. Perturbation Stability

A critical aspect of this theory is its stability. The authors prove that the bounds hold even when the Markov chain is slightly perturbed. This is vital for modern machine learning applications like Score Matching (used in diffusion models) and Pseudolikelihood Estimation, where the true score function or transition probabilities are only known approximately.

Key Insights and Results

Linear vs. Exponential Complexity

The most significant advancement is the improvement of sample complexity from $e^k$ to $O(k/\epsilon^2)$. This reduction makes the theory applicable to complex, high-dimensional distributions with a large number of components, where previous bounds were practically unusable.

Justifying Generative Models

This research provides a mathematical justification for the empirical success of data-based initialization in generative modeling. It suggests that if a model has enough data to represent the underlying modes of a distribution, the subsequent Langevin dynamics or diffusion processes only need to perform local refinement, bypassing the global mixing bottleneck.

Learning Ising Models

The paper applies these insights to Ising models, specifically a class of "low-complexity" or "low-rank" Gibbs measures. The authors present the first efficient algorithm to learn these models from samples, even in low-temperature regimes where standard methods typically fail due to metastability.

Conclusion and Future Directions

This work bridges the gap between MCMC theory and practical generative modeling by showing that a small amount of data can fundamentally change the tractability of sampling. By leveraging the $k$-th order spectral gap, we can efficiently sample from distributions that would otherwise take exponential time to explore.

However, the method still requires an initial set of samples from the target distribution, meaning it is better suited for density estimation and generative tasks than for "pure" sampling problems where the distribution is known only by a formula. Future research may explore whether these techniques can be extended to even more complex systems, such as spin glasses, or if pseudolikelihood estimation can achieve similar results without the need for an explicit MCMC step.

Summary updated

Abstract

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\'e 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.
BibTeX
@inproceedings{koehler2025efficiently,
  author = {Frederic Koehler and Holden Lee and Thuy-Duong Vuong},
  title = {{Efficiently learning and sampling multimodal distributions with data-based initialization}},
  booktitle = {Conference on Learning Theory},
  year = {2025},
  url = {https://openreview.net/forum?id=UjTMn78gwx},
}
Figure