🔬 condensed matter

Discrete distributions are learnable from metastable samples

This paper demonstrates that true multivariable discrete distributions, including Ising models, can be rigorously recovered from metastable samples by leveraging the observation that single-variable conditional probabilities remain close to the stationary state even when global distributions diverge, thereby enabling effective model learning via conditional-likelihood estimation.

Original authors: Abhijith Jayakumar, Andrey Y. Lokhov, Sidhant Misra, Marc Vuffray

Published 2026-07-07

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Abhijith Jayakumar, Andrey Y. Lokhov, Sidhant Misra, Marc Vuffray

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Problem: Getting Stuck in a "Local Valley"

Imagine you are trying to map out a massive, foggy mountain range. Your goal is to understand the entire landscape: where the highest peaks are, where the deepest valleys are, and how everything connects.

To do this, you send out a team of hikers (a computer algorithm called a Markov Chain) to walk around and take pictures of the terrain. Usually, if you wait long enough, these hikers will wander everywhere, giving you a perfect, complete map of the whole mountain range.

But here is the catch: Sometimes, the hikers get stuck. They fall into a deep, narrow valley (a metastable state) and can't find the path out to the rest of the mountains. They spend all their time walking around inside this one small valley.

If you look at the photos they took, they only show the inside of that one valley. If you try to build a map of the entire mountain range based only on those photos, you will get it completely wrong. You might think the whole world is just that one valley. In the world of data science, this is a huge problem because many real-world systems (like molecules or social networks) naturally get stuck in these "valleys," making it hard to get good data.

The Old Way vs. The New Discovery

The Old Way (Maximum Likelihood):
Traditionally, scientists tried to fix this by asking: "How can we make our model look exactly like the photos we have?" They used a method that tries to minimize the difference between the model and the data.

The Analogy: Imagine trying to draw a map of the whole world, but you only have photos of a single room. The old method would try to stretch that room to look like the whole world. It fails miserably because the "room" (the metastable data) is fundamentally different from the "world" (the true distribution). The math says the two are too far apart to ever match.

The New Discovery (The Paper's Claim):
The authors of this paper found a clever trick. They realized that even though the hikers are stuck in a small valley, the rules of the terrain inside that valley are actually almost identical to the rules of the terrain outside.

The Analogy: Imagine the valley has a specific rule: "If you step on a red rock, you must turn left." Even if the hikers are stuck in a valley where there are only red rocks, they will still follow that rule perfectly. If you observe them turning left every time they step on a red rock, you can deduce the rule "Red Rock = Turn Left."
The Insight: The paper proves that even if the hikers are stuck in a tiny, restricted part of the state space, the local rules (called single-variable conditionals) they follow are statistically almost the same as the rules they would follow if they were wandering the whole mountain.

How They Learned the True Model

The authors used a method called Pseudo-Likelihood (PL). Instead of trying to guess the whole map at once, this method asks simple, local questions:

"If I am at this spot, what is the most likely place to go next?"
"If I am at this spot, what is the most likely neighbor?"

Because the "local rules" inside the stuck valley are the same as the "local rules" of the whole mountain, the PL method can learn the true structure of the entire system, even though the data only comes from the stuck valley.

The Key Takeaway:
You don't need to see the whole mountain to understand how the mountain works. You just need to understand how the hikers behave locally when they are stuck.

The "Spin Glass" Experiment

To prove this, the authors ran computer simulations on two types of complex systems:

The Curie-Weiss Model: Think of this as a giant magnet where every atom talks to every other atom. They showed that even when the simulation gets stuck in a state where all atoms point "up" (ignoring the fact that the true state should be a mix of up and down), the learning algorithm could still correctly figure out the strength of the magnetic forces between them.
Spin Glass Models: These are like a chaotic maze of interactions. They tested a complex system with three levels of interaction (not just up/down, but three states). Even when the simulation got stuck in a high-energy "trap," the algorithm successfully learned the hidden connections and rules of the system.

Why This Matters (According to the Paper)

The paper concludes that metastability is not a dead end for learning.

Global metrics fail: If you try to measure the difference between the "stuck" data and the "true" data using big, global measurements (like total distance), they look totally different.
Local metrics succeed: If you look at the small, conditional probabilities (the local rules), they are nearly identical.

By using methods that focus on these local rules (like Pseudo-Likelihood), we can recover the true model of a system even when our data is "bad" or incomplete because the system got stuck. It's like being able to reconstruct the entire blueprint of a house just by studying the wiring in one single room, because the wiring rules are consistent throughout the whole building.

Technical Summary: Discrete distributions are learnable from metastable samples

Problem Statement
Markov Chain Monte Carlo (MCMC) methods are the standard tool for sampling from high-dimensional discrete distributions, such as Gibbs distributions or Ising models. However, in systems exhibiting slow mixing—often due to strong interactions or low temperatures—these chains frequently become trapped in metastable states. In such states, the chain samples from a restricted region of the state space for long periods, resulting in a distribution that differs significantly from the true stationary distribution under global metrics like Kullback-Leibler (KL) divergence or Total Variation (TV) distance.

Conventional learning algorithms, such as Maximum Likelihood Estimation (MLE), rely on minimizing global metrics between the data distribution and a hypothesis. Because the KL divergence between a metastable distribution and the true stationary distribution can be large (e.g., proportional to the log of the inverse probability of the metastable region), MLE fails to recover the true model parameters even with infinite data from the metastable state. This raises a critical question: Is it possible to learn the true stationary model of a Markov chain given only samples drawn from its metastable states?

Methodology and Definitions
The authors propose a framework based on the observation that while metastable distributions may be globally distinct from the stationary distribution, their single-variable conditional probabilities remain, on average, extremely close to those of the true stationary distribution.

To formalize this, the paper introduces two definitions of metastability for a distribution $\nu$ with respect to a reversible Markov chain $P$ having stationary distribution $\mu$ :

Metastability ( $\eta$ -metastable): A distribution is $\eta$ -metastable if its TV distance from the distribution after one step of the chain is small ( $|\nu - \nu P|_{TV} \le \eta$ ). This captures the intuitive notion of a distribution that changes slowly over time.
Strong Metastability ( $\eta$ -strongly metastable): A distribution is $\eta$ -strongly metastable if it violates the detailed balance condition of the chain by at most $\eta$ in TV distance ( $\frac{1}{2} \sum_{i,j} |P(i|j)\nu(j) - P(j|i)\nu(i)| \le \eta$ ).

The paper establishes that distributions supported on regions of the state space with low conductance (bottlenecks) are examples of strongly metastable states. Specifically, for slow-mixing chains, there exist strongly metastable states where $\eta$ is exponentially small in the number of variables.

Key Theoretical Results
The central theoretical contribution is Theorem 1, which proves that for a reversible Markov chain satisfying a bounded spin-flip probability condition, the single-variable conditionals of an $\eta$ -strongly metastable distribution $\nu$ differ from those of the true stationary distribution $\mu$ by an average TV distance of $O(\eta/\omega_P)$ , where $\omega_P$ is a lower bound on transition probabilities.

This result implies that while the global distributions may be far apart, the local conditional structures are nearly identical. Since learning methods for discrete graphical models, such as Pseudo-Likelihood (PL) and Interaction Screening, rely on minimizing the average KL divergence between single-variable conditionals rather than global metrics, these methods can effectively recover the true model from metastable data.

Learning Guarantees
The authors derive rigorous learning guarantees for the Pseudo-Likelihood (PL) estimator:

Test Error Bounds (Theorem 2): The PL loss computed from strongly metastable samples is close to the optimal loss, with a bias term scaling as $O(\eta/\omega_P)$ . For slow-mixing systems where $\eta$ decays exponentially with system size, this bias is dominated by statistical errors ( $O(M^{-1/2})$ ) for sufficiently large sample sizes.
Parameter Recovery (Theorem 3): For binary Ising models, the coupling parameters can be learned with an error bound that includes a bias term proportional to $\sqrt{\eta}$ . The sample complexity scales as $\tilde{O}(\beta^d \log n)$ , similar to the i.i.d. case, but with an unavoidable bias dependent on the degree of metastability.
Structure and Field Recovery (Theorems 4 & 5): The paper extends these guarantees to structure learning (recovering the graph edges) and magnetic field recovery. It shows that edges can be recovered with high probability provided the true coupling strengths exceed a threshold determined by the bias term.

Numerical Experiments
The theoretical findings are validated through numerical experiments on two models:

Curie-Weiss Model: The authors construct explicit strongly metastable states centered around the local minima of the free energy landscape. They demonstrate that Glauber dynamics initialized in a positive magnetization state (where the true distribution has negative magnetization) produces samples that are globally far from the truth. However, the PL method successfully recovers the correct coupling ( $J$ ) and magnetic field ( $h$ ) parameters, whereas MLE fails completely, predicting the wrong sign for the magnetic field.
Higher-Order Spin Glass Models: The authors test learning on a model with $q=3$ alphabet and third-order interactions (hypergraph). Despite the chain getting stuck in higher-energy metastable states compared to the ground state, the PL method successfully recovers both the model structure (hyperedges) and the coupling parameters.

Significance and Claims
The paper claims to rigorously demonstrate that the "bad" data produced by slow-mixing Markov chains is not useless for learning. By shifting the focus from global distribution matching to local conditional matching, the authors show that the true stationary model can be recovered from metastable samples.

Key claims include:

Robustness of Conditional Learning: Methods based on single-variable conditionals (like PL) are robust to the global discrepancies caused by metastability, provided the metastability is "strong" (i.e., the detailed balance violation is small).
Existence of Learnable Metastable States: The paper provides explicit constructions showing that metastable states arising from low-conductance sets in state space satisfy the strong metastability condition required for learning.
Generalization: The results suggest that learning discrete distributions is possible even when data is constrained to specific regions of the state space, provided the learning algorithm exploits the conditional structure of the distribution.

The authors note that while the bias in parameter estimates depends on the metastability parameter $\eta$ , for systems exhibiting slow mixing, this bias is often exponentially small, making the learning guarantees nearly optimal in the limit of large system sizes. The work bridges statistical physics concepts (metastability, free energy minima) with statistical learning theory, offering a theoretical justification for the empirical success of learning from non-equilibrium or trapped dynamical data.