TL;DR
Standard Markov Chain Monte Carlo (MCMC) algorithms take exponentially long to sample from multimodal distributions because they get trapped in local modes. This paper proves that if a distribution exhibits a higher-order spectral gap (meaning it has at most $k$ well-separated modes), initializing the chain from $\tilde{O}(k/\varepsilon_{\mathrm{TV}}^2)$ data samples guarantees polynomial-time sampling within $\varepsilon_{\mathrm{TV}}$ total variation distance. The theory is robust to errors in learned dynamics (e.g., score matching or pseudolikelihood) and delivers the first computationally efficient algorithm for learning low-complexity Ising models from samples.
What Problem Does This Paper Address?
In high-dimensional statistics and machine learning, sampling from multimodal distributions is notoriously difficult. Natural local dynamics—such as Langevin diffusion in continuous space or Glauber dynamics on discrete lattices—suffer from metastability: they rapidly mix within an individual mode but take exponentially long to cross low-density bottlenecks between modes.
However, in generative modeling and density estimation, practitioners routinely initialize MCMC chains from the empirical training data (known as data-based initialization or contrastive divergence warm starts) and find that it works remarkably well. Prior theory could only justify this heuristic under strong conditions that suffered from an exponential dependence on the number of components $k$. This paper addresses two foundational questions:
- Why and when does data-based initialization rigorously overcome multimodal bottlenecks?
- Can we provide sample- and time-efficient guarantees that depend only linearly on the number of modes, even when the Markov chain is estimated from noisy data?
Methods
The authors re-examine data-based initialization through an operator-theoretic, spectral lens:
- Higher-Order Spectral Gap: Instead of requiring a standard spectral gap $\lambda_2(-\mathcal{L}) > 0$ (which is exponentially small in multimodal settings), the authors require a gap after the $k$-th eigenvalue, $\lambda_{k+1}(-\mathcal{L}) \ge \alpha > 0$. The first $k$ eigenfunctions govern the slow inter-modal transitions, while the remaining spectrum governs fast intra-modal mixing.
- Eigenfunction Balance via Matrix Bernstein: To bypass slow mixing along the top $k$ eigenfunctions, an initial distribution must be nearly orthogonal to the subspace spanned by those eigenfunctions. The authors prove that the empirical measure over $n = \tilde{\Omega}(k/\varepsilon_{\mathrm{TV}}^2)$ independent samples naturally satisfies this eigenfunction balance condition with high probability.
- Stationary Perturbation Analysis: When transition dynamics are learned (e.g., estimating score functions $\nabla \ln \pi$ or conditional marginals via pseudolikelihood), the authors bound trajectory errors by evaluating the Kullback–Leibler (KL) divergence of paths initialized at stationarity $\pi$, then transferring this control to empirical data samples via Pinsker's and Bernstein's inequalities.
- Multiplicative Mixture Decompositions: For discrete spin systems, the authors use the Hubbard–Stratonovich transform and net coverings to show that approximately low-rank Ising models can be decomposed into a mixture of rapidly mixing measures.
Datasets
Not discussed in the paper. The work is purely theoretical and does not evaluate on empirical datasets or benchmark suites.
Key Insights and Ideas
- Data cancels out the bottlenecks: The expected projection of the empirical measure onto any non-trivial eigenfunction of the reversible generator is exactly zero. A modest sample size ($n \propto k$) suffices to ensure the projection onto the entire subspace of the $k$ slowest modes is tiny.
- Linear vs. Exponential dependence on $k$: Previous analyses relied on spatial cluster separation, which broke down when clusters overlapped and produced sample complexity exponential in $k$. The spectral approach completely circumvents overlap issues, improving sample dependence from $\exp(k)$ to near-optimal $\tilde{O}(k)$.
- Escaping the parameter identifiability trap: Prior algorithms for learning Ising models required identifying the interaction matrix $J$, incurring an exponential sample complexity $\exp(O(R))$ in the row-norm $R$. By combining pseudolikelihood with warm-started Glauber dynamics, this paper shows that sampling within $\varepsilon_{\mathrm{TV}}$ is possible in $\mathrm{poly}(n, R)$ samples without needing to identify the underlying graph structure.
Key Results
- General Markov Semigroups: Given a $k$-th order spectral gap $\lambda_{k+1} \ge \alpha$ and a mild warm-start parameter $R$, taking $n = \tilde{\Omega}(k/\varepsilon_{\mathrm{TV}}^2)$ samples and running dynamics for time $t \ge t_0 + \frac{1}{\alpha}\ln(4R/\varepsilon_{\mathrm{TV}}^2)$ yields an $\varepsilon_{\mathrm{TV}}$-accurate sample with probability at least $1 - \delta$.
- Langevin Diffusion & Monte Carlo: For mixtures of $k$ smooth distributions satisfying a Poincaré or log-Sobolev inequality, continuous Langevin diffusion and discrete Langevin Monte Carlo converge in $\mathrm{poly}(d, k, 1/\varepsilon_{\mathrm{TV}})$ steps and tolerate an $L_2$ score estimation error of $\varepsilon_{\mathrm{score}} = O(\varepsilon_{\mathrm{TV}}/\sqrt{T})$.
- Learning Low-Rank Ising Models: For $n$-spin Ising models whose interaction matrix $J$ has $r$ eigenvalues exceeding $1 - 1/c$ and bounded negative spectrum, pseudolikelihood estimation coupled with data-initialized Glauber dynamics achieves TV error $\varepsilon_{\mathrm{TV}}$ using $(nr\lambda_1)^{O(r)}/\varepsilon_{\mathrm{TV}}^4$ samples, providing the first polynomial-time learning guarantee in the low-temperature regime for low-rank interactions.
Limitations and Future Work
- Rank dependence: The sample complexity for Ising models depends exponentially on the rank $r$ (i.e., $(n\lambda_1)^{O(r)}$). The authors show this exponential dependence is information-theoretically necessary in general (e.g., $r$ disjoint Curie-Weiss models create $2^r$ modes).
- Reliance on i.i.d. samples: The algorithm requires an initial pool of unbiased samples from the target measure $\pi$ (or a distribution close to it in TV). It cannot generate samples from scratch without prior data.
- Pure pseudolikelihood vs. dynamics: It remains an open theoretical question whether pseudolikelihood estimation alone (without subsequent data-initialized sampling) can match these TV guarantees for multimodal Ising models.
Summary updated