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