Discrete distributions are learnable from metastable samples

Abhijith Jayakumar, Andrey Y. Lokhov, Sidhant Misra, Marc Vuffray

Abstract

Physically motivated stochastic dynamics are often used to sample from high-dimensional distributions. However such dynamics often get stuck in specific regions of their state space and mix very slowly to the desired stationary state. This causes such systems to approximately sample from a metastable distribution which is usually quite different from the desired, stationary distribution of the dynamic. We rigorously show that, in the case of multi-variable discrete distributions, the true model describing the stationary distribution can be recovered from samples produced from a metastable distribution under minimal assumptions about the system. This follows from a fundamental observation that the single-variable conditionals of metastable distributions that satisfy a strong metastability condition are on average close to those of the stationary distribution. This holds even when the metastable distribution differs considerably from the true model in terms of global metrics like Kullback-Leibler divergence or total variation distance. This property allows us to learn the true model using a conditional likelihood based estimator, even when the samples come from a metastable distribution concentrated in a small region of the state space. Explicit examples of such metastable states can be constructed from regions that effectively bottleneck the probability flow and cause poor mixing of the Markov chain. For specific cases of binary pairwise undirected graphical models (i.e. Ising models), we extend our results to further rigorously show that data coming from metastable states can be used to learn the parameters of the energy function and recover the structure of the model.

Introduction

In high-dimensional statistics and physics, Markov Chain Monte Carlo (MCMC) is the workhorse for sampling from complex distributions. However, these chains frequently encounter the phenomenon of metastability, where they remain "stuck" in local regions of the state space for extended periods. Conventional wisdom suggests that if samples are drawn from such a metastable state rather than the true stationary distribution, the learning process is fundamentally compromised.

A recent study by Jayakumar et al. challenges this intuition. They demonstrate that for discrete distributions, the true underlying model can be recovered even when the data is drawn from a "bad" metastable sample.

The Challenge of Metastability

Many physical and biological systems are modeled using undirected graphical models, such as Ising models. Learning these models typically assumes access to independent, identically distributed (i.i.d.) samples from the "ground truth." In practice, data often comes from natural dynamical systems or MCMC samplers that exhibit slow mixing.

When a system is metastable, it may spend an immense amount of time in a restricted corner of the state space. Applying Maximum Likelihood Estimation (MLE) to this data results in an algorithm attempting to match the global statistics of the biased sample to the model, leading to wildly incorrect estimates. The authors investigate whether it is possible to bypass this global bias to identify the true parameters of the energy function.

Theoretical Framework and the Core Insight

The researchers bridge statistical physics and learning theory through two primary concepts:

  1. Strong Metastability: They define metastability based on the degree to which a distribution violates the detailed balance condition. If a distribution remains relatively stable after a single step of the Markov chain, it is considered strongly metastable.
  2. Pseudo-Likelihood (PL) Estimation: Unlike MLE, which considers the probability of entire configurations, PL focuses on single-variable conditionals—the probability of one variable given the state of all others.

The central mathematical contribution is Theorem 1, which proves that in a strongly metastable state, these local conditionals are, on average, very close to the conditionals of the true stationary distribution.

Free energy landscape illustrating the relationship between a metastable distribution $\nu(\sigma)$ and the stationary distribution $\mu(\sigma)$.

The "Aha!" moment lies in the distinction between global and local properties. While the global probability mass of a metastable state is "wrong" (exhibiting high KL divergence from the truth), the local rules governing variable interactions remain "right." Metastability is typically caused by a "bottleneck" in the state space that prevents escape; however, within that bottlenecked region, the variables still adhere to the local physics of the true energy function. Because Pseudo-Likelihood only considers local conditionals, it is inherently robust to the global sampling bias caused by slow mixing.

Key Results and Validation

The paper provides theoretical validation and numerical experiments using the Curie-Weiss model, a classic all-to-all connected Ising model. This model is ideal because it features a bimodal distribution where samplers easily get stuck in one "phase" (e.g., positive magnetization) even if the other phase is more probable.

Key findings include:

  • Bias-Variance Tradeoff: The error in learning from metastable samples consists of a statistical error (vanishing with more data) and a "metastability bias" (often exponentially small in system size).
  • Ising Model Recovery: The authors prove that Ising model parameters can be recovered with $O(\log n)$ samples, even if trapped in a metastable state.
  • Numerical Validation: In simulations with 5,000 spins, the PL estimator successfully recovered true coupling ($J$) and magnetic field ($h$) parameters from samples stuck in a local minimum. Conversely, the MLE estimator failed completely, even predicting the incorrect sign for the magnetic field.

Limitations and Future Work

While promising, the results rely on the "Strong Metastability" condition, which may not hold for all types of biased data. Future work includes extending these proofs to continuous variables and exploring model misspecification. The authors also note a "metastability gap" between different definitions of metastability, suggesting that further exploration could lead to even tighter learning guarantees.

Summary updated

Abstract

Physically motivated stochastic dynamics are often used to sample from high-dimensional distributions. However such dynamics often get stuck in specific regions of their state space and mix very slowly to the desired stationary state. This causes such systems to approximately sample from a metastable distribution which is usually quite different from the desired, stationary distribution of the dynamic. We rigorously show that, in the case of multi-variable discrete distributions, the true model describing the stationary distribution can be recovered from samples produced from a metastable distribution under minimal assumptions about the system. This follows from a fundamental observation that the single-variable conditionals of metastable distributions that satisfy a strong metastability condition are on average close to those of the stationary distribution. This holds even when the metastable distribution differs considerably from the true model in terms of global metrics like Kullback-Leibler divergence or total variation distance. This property allows us to learn the true model using a conditional likelihood based estimator, even when the samples come from a metastable distribution concentrated in a small region of the state space. Explicit examples of such metastable states can be constructed from regions that effectively bottleneck the probability flow and cause poor mixing of the Markov chain. For specific cases of binary pairwise undirected graphical models (i.e. Ising models), we extend our results to further rigorously show that data coming from metastable states can be used to learn the parameters of the energy function and recover the structure of the model.
BibTeX
@misc{jayakumar2024discrete,
  author = {Abhijith Jayakumar and Andrey Y. Lokhov and Sidhant Misra and Marc Vuffray},
  title = {{Discrete distributions are learnable from metastable samples}},
  year = {2024},
  eprint = {2410.13800},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2410.13800},
}
Figure