Discrete distributions are learnable from metastable samples

arXiv:2410.13800 · stat.ML, cond-mat.stat-mech, cs.LG · Submitted 2026-07-02 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: AI Radio. Generated commentary on the latest Artificial Intelligence papers.

Tom: Next we'll be talking about the paper "Discrete distributions are learnable from metastable samples".

Jane: The paper was written by Abhijith Jayakumar, Andrey Y. Lokhov, Sidhant Misra and Marc Vuffray from Los Alamos National Laboratory.

Tom: Stay tuned as we take you through the paper and discuss its implications.

Title: Tom: Welcome back, everyone! We've got a fascinating paper to dig into today, and it's called "Discrete distributions are learnable from metastable samples." Jane, I have to say, that title alone got me excited.

Jane: It's a great title, Tom, because it packs a huge promise into just a few words. For anyone just tuning in, a discrete distribution is just a way of describing probabilities when things can only be in a finite number of states, like a coin flip or a spin being up or down.

Tom: Right, and "metastable" is the key word here. It sounds like a fancy physics term, and it is, but the basic idea is a system that gets stuck in a state that isn't its true, final resting state. Think of a ball rolling into a small dip on a hillside instead of all the way down to the valley floor.

Jane: Exactly. And the paper is saying that even if you only get samples from that stuck state, you can still learn the rules of the true, final state. That's the "learnable" part of the title. It's a pretty bold claim.

Tom: It is bold, and it goes against a lot of conventional wisdom. Usually, you'd think, "Garbage in, garbage out." If your data is from the wrong place, how can you possibly learn the right model?

Jane: And that's exactly the question the authors from Los Alamos National Lab—Abhijith Jayakumar, Andrey Lokhov, Sidhant Misra, and Marc Vuffray—set out to answer. They're basically saying that the "garbage" isn't as useless as we thought.

Tom: So, for our listeners, this isn't just an academic curiosity. This is about real-world situations where we have to learn from data that isn't perfect. Imagine trying to model the weather, but your sensors are stuck in a local pattern, or modeling a protein, but the simulation is trapped in a specific shape.

Jane: Right. The potential to extract the true underlying model from imperfect, stuck data could be huge for those fields. It suggests that we might not need perfect sampling to get at the fundamental truth.

Tom: And that's the promise we're going to unpack today. We'll get into the math, the definitions, and the experiments. But for now, let's just sit with that core idea: you can learn the truth from a stuck state.

Jane: It really is a counterintuitive and powerful concept. I'm curious to see how they prove it.

Tom: Me too. Let's get into the summary of the paper next and see how they actually pull this off.

Summary: Jane: So, Tom, we've established the headline. The paper "Discrete distributions are learnable from metastable samples" claims you can learn the true model from stuck data. But the summary is where they really lay out the mechanism.

Tom: And the mechanism is surprisingly elegant. They define something called "strong metastability." It's a more specific condition than just being stuck. It's about how much the system violates a fundamental rule of equilibrium called detailed balance.

Jane: Let's unpack that. Detailed balance is a property of a well-behaved system where the flow of probability between any two states is equal in both directions. It's like a balanced see-saw. A strongly metastable state is one where that see-saw is only slightly off-balance.

Tom: And their key theorem, which is the heart of the paper, shows that if a distribution is only slightly off-balance in this specific way, then its single-variable conditionals are almost the same as the true distribution's.

Jane: Okay, so "single-variable conditionals" is a mouthful. Let's simplify. It means if you know the state of every other variable, the probability of one specific variable being in a certain state is almost identical in the stuck distribution and the true distribution.

Tom: Exactly. And this is a huge deal because many powerful learning algorithms, like the pseudo-likelihood method they focus on, work by learning exactly these conditionals. They don't try to match the whole distribution at once.

Jane: Right. It's like learning the rules of a game by watching how one player reacts to all the others, rather than trying to understand the entire game board at once. If those reactions are correct, you can learn the game.

Tom: And the paper shows that even when the stuck distribution is wildly different from the true one in a global sense—like, they're in completely different parts of the state space—the conditionals can still be spot on.

Jane: That's the "far apart globally, close locally" idea. It's a beautiful result. It means the information needed to learn the true model is actually present in the stuck data, just hidden in a way we weren't looking at before.

Tom: So the summary is basically a recipe. Define the right kind of stuckness, prove that it preserves the local information, and then show that a standard learning algorithm can use that information.

Jane: It's a really clean theoretical argument. But a theory is only as good as its application. I'm excited to see how they actually construct these metastable states and what it means for learning.

Tom: Absolutely. Let's move on to the improvements and the specific constructions they came up with.

Improvements: Tom: So Jane, we've got the theory. But a paper like "Discrete distributions are learnable from metastable samples" needs to show that these metastable states actually exist in interesting systems. That's where the improvements and constructions come in.

Jane: Right. They don't just say "trust us." They build explicit examples. One of the most important constructions is tied to a concept called "conductance" in Markov chains.

Tom: For our listeners, conductance is a measure of how hard it is for a random process to escape a region of states. A low conductance means there's a bottleneck, a narrow passage that's hard to cross.

Jane: And the paper shows that any such bottleneck region naturally supports a strongly metastable state. If you just take the true distribution and restrict it to that region, it automatically satisfies their condition.

Tom: That's a beautiful connection. It means the kind of stuckness they're talking about isn't some rare, pathological thing. It's exactly what happens when a system is slow to mix, which is common in complex systems like spin glasses.

Jane: And they make it even more concrete with the Curie-Weiss model, a classic model of a ferromagnet. They show that the states you get stuck in are centered around the minima of the free energy, which is a very physical and intuitive picture of metastability.

Tom: It's like a ball sitting in a local dip in the energy landscape. The ball is stuck, but the local shape of the dip still tells you about the overall landscape.

Jane: But the real improvement, the thing that makes this practical, is the learning guarantees. They don't just show the conditionals are close; they prove that you can actually recover the model parameters.

Tom: For the Ising model, which is the workhorse of statistical physics, they prove that with enough samples from a metastable state, you can learn the couplings and magnetic fields with an error that only has a small, controllable bias.

Jane: And that bias is tied to how metastable the state is. For systems that are really stuck, this bias becomes incredibly small, even exponentially small in the number of variables.

Tom: So, the "improvement" here is a full theoretical framework. They've taken a vague idea—"can we learn from bad data?"—and turned it into a rigorous mathematical statement with explicit algorithms and sample complexity bounds.

Jane: It's a complete package. They even show how to do structure learning, which means figuring out which variables are connected to which, just from this stuck data.

Tom: That's a big deal for reconstructing the underlying graph of a complex network. Let's get into the first page of the paper to see how they set all this up.

First Page: Jane: We're back, and we're looking at the very first page of "Discrete distributions are learnable from metastable samples." It's a great introduction because it sets the stage for the whole problem.

Tom: It starts with the classic issue: Markov chains are the go-to tool for sampling complex distributions, but they often mix very slowly. They get trapped in these metastable states.

Jane: And the paper makes a really sharp observation here. It points out that most learning algorithms, like Maximum Likelihood Estimation, try to minimize a global metric like Kullback-Leibler divergence. And if your data is from a metastable state, that global metric is huge.

Tom: Right. The stuck distribution is just too far from the true one for a global method to ever bridge the gap. The paper says, "Prima facie, this task looks hopeless." And it really does, from that global perspective.

Jane: But then they pivot. They say, "However for the purposes of learning, it is not always necessary or useful to minimize such global metrics." And that's the key insight that sets the whole paper in motion.

Tom: They point to algorithms like pseudo-likelihood that work by learning the single-variable conditionals. These local methods don't care about the global distance; they just care about the local relationships.

Jane: And that's the seed of the whole paper. The first page is essentially a promise: "We will show that even though the global picture is wrong, the local picture is right, and that's enough."

Tom: It's a masterclass in framing a problem. They acknowledge the obvious objection—"this looks hopeless"—and then immediately offer a different way of thinking that makes the problem tractable.

Jane: It also connects to the broader motivation. They mention that many natural systems, from molecular biology to quantum field theory, exhibit slow mixing. So this isn't just a theoretical problem for computer scientists.

Tom: Right. It's a problem for anyone trying to learn from data generated by a physical process that's out of equilibrium. And this paper is saying, "Don't worry, we've got a way to handle it."

Jane: It's a very compelling opening. It makes you want to read on to see if they can deliver on that promise. And from what we've discussed, it seems like they do.

Tom: They absolutely do. Let's wrap up our thoughts on this one.

Conclusion: Tom: Well, we've had a great time with "Discrete distributions are learnable from metastable samples." Let's try to pull it all together for our listeners.

Jane: The central message is that you can learn the true model of a system even when your data comes from a stuck, metastable state. The key was to focus on local information, the single-variable conditionals, rather than global differences.

Tom: And they proved this with a rigorous definition of strong metastability, showed that these states exist in common physical systems, and provided concrete learning guarantees for models like the Ising model.

Jane: The implications are pretty significant. It suggests that we can be more confident in learning from data that might not be perfectly sampled, which is often the case in real-world applications.

Tom: For me, the most exciting part is the potential to apply this to systems we thought were too hard to learn from. If a simulation is stuck, maybe we don't have to throw it out. We can still extract the fundamental physics.

Jane: And the numerical experiments with the Curie-Weiss model and the spin glass really drive the point home. They show the method working in practice, recovering the true parameters from data that was clearly not from the equilibrium distribution.

Tom: It's a really satisfying result. It takes a common problem, gives it a rigorous framework, and provides a practical solution. It's a great example of how theoretical physics and computer science can come together.

Jane: I think this paper will have a lasting impact on how we think about learning from dynamical systems. It's a fresh perspective that opens up a lot of new questions.

Tom: Absolutely. So, we'll say goodbye to this paper, but we're definitely going to be thinking about its ideas for a long time.

Jane: Thanks for joining us, everyone. We'll be back soon with another exciting paper to discuss.

Tom: Until next time, keep questioning, keep learning, and don't be afraid of a little metastability.

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

Los Alamos National Laboratory

stat.ML, cond-mat.stat-mech, cs.LG

Submitted: 2026-07-02

Updated: 2026-08-11

Comments: Updated version. Spin glass experiments added

Journal ref: Nat Communications (2026)

DOI: 10.1038/s41467-026-75439-1

Code: https://github.com/abhijithjlanl/metastable-learning

License: http://creativecommons.org/licenses/by/4.0/

Importance score: 80/100

The gist: This paper investigates whether the stationary distribution of a Markov chain can be learned from samples drawn from a metastable state of the chain, rather than from independent and identically

Key concepts

Metastable State
A state where a system gets stuck in a position that is not its true final resting point. This is like a ball rolling into a small dip on the hillside instead of all the way down to the valley floor.
Strong Metastability
A specific condition of being stuck, defined by how much the system violates 'detailed balance.' It means a system is only slightly off-balance, allowing for specific mathematical proofs about its local data.
Single-Variable Conditionals
'Conditionals' mean that if you know the state of every other variable, the probability of one specific variable being in a certain state is almost identical in both the stuck and true distribution.

Terminology

Summary

This paper investigates whether the stationary distribution of a Markov chain can be learned from samples drawn from a metastable state of the chain, rather than from independent and identically distributed (i.i.d.) samples from the true distribution. The authors rigorously show that for multivariable discrete distributions, the true stationary model can be recovered from metastable samples, despite the fact that metastable distributions can be far from the stationary distribution under global metrics like Kullback-Leibler (KL) divergence or total variation (TV) distance.

The paper begins by motivating the problem: "Markov chains are by far the most popular tool used to study systems described by many-variable probability distributions. It is well known that Markov chains can mix very slowly to the stationary distribution and this is often associated with the existence of so-called metastable states, where the chain can get stuck for long periods of time. The authors note that while many learning guarantees assume i.i.d. samples from the ground truth distribution, this assumption is less likely to hold in cases where the source of the data is a natural dynamical system or Markov chain sampling algorithm, due to slow mixing often exhibited by such systems."

The paper defines two notions of metastability. The first, called metastability, is defined as: A distribution ν is η-metastable with respect to a Markov chain P if and only if ν − νPTV ≤ η. The second, called strong metastability, is defined as: Let P be a Markov chain with a state space S. Then a distribution ν is η-strongly metastable with respect to P iff (1/2) Σ i,j∈S P(ij)ν(j) − P(ji)ν(i) ≤ η. The authors note that If we set η to zero in the definition of strong metastability, then we get the detailed balance condition, and that strong metastability implies metastability with the same η.

The paper establishes the existence of strongly metastable distributions for reversible Markov chains using the concept of conductance. For a set A ⊆ S, the conductance is defined as Γ(A):= Σ j∈A, i∈A c P(ij)µ(j) / Σ j∈A µ(j). The authors show that for any subset A, the distribution µ A(σ) = µ(σ)/µ(A) for σ ∈ A and 0 otherwise is Γ(A)-strongly metastable. They connect this to slow mixing via the Cheeger bound, showing that for a slow-mixing reversible Markov chain P with stationary distribution µ, we conclude that there exists an η-strongly metastable distribution with η exponentially small in the number of spins.

The paper also establishes robustness properties of strong metastability. Proposition 2 shows that convex combinations of strongly metastable distributions are also strongly metastable, and Proposition 3 shows that if ν is η-strongly metastable for a reversible Markov chain P, then νP t is (1+2t)η-strongly metastable for every integer t ≥ 1.

The central theoretical result is Theorem 1, which states: "Consider a system of n discrete random variables where each of them can take values from the set Q. Let ν be an η−strongly metastable distribution of a reversible Markov chain P with a stationary state µ. If this chain satisfies Condition 1, then the single-variable conditionals of ν are close to those of µ in the following sense: Σ u=1 n Σ σ∈Q n ν(σ) ν(.σ) − µ(.σ) TV ≤ η/ω P." Here, Condition 1 requires that the ratio of the transition probability to the single-variable conditional is lower bounded by ω P > 0, which is satisfied by both Glauber dynamics (ω P = 1/n) and Metropolis-Hastings samplers.

The authors emphasize the significance of this result: This is a central observation in this paper which says that a strong metastable distribution has on average single-variable conditionals that are very close to that of the equilibrium distribution. They contrast this with the fact that the TV distance between the metastable distribution from the equilibrium distribution is µ A − µ TV = 1 − µ(A), which is generally not an exponentially small quantity even if the Markov chain mixes slowly.

Building on Theorem 1, the paper proves learning guarantees for the pseudo-likelihood (PL) method. Theorem 2 provides a test error bound: "Given M′ independent samples from an η-strongly metastable distribution ν of a reversible Markov chain, the true graphical model parameters are nearly optimal for PL in the following sense: (1/M′) Σ t,u L u(θ*, σ(t)) − L u(θ̂, σ(t)) ≤ 2(1+(Q−1)e 2γ)η/ω P + sqrt(log(e 2γ(Q−1)) log(1/δ) / (2M′)). The authors note that the O(1/√M′) term here is the statistical error in the estimation of the loss function. Hence, if M′ is small enough this statistical error will swamp the O(η/ω P) bias introduced by having bad data."

For the specific case of Ising models (binary variables with pairwise interactions), the paper proves parameter and structure learning guarantees. Theorem 3 states that with M = O(e 4γ log(n)/ε 4) samples from an η-strongly metastable distribution, with probability greater than 1−δ, the following guarantee holds for all u ∈ [n]: max v≠u θ* uv − θ̂ uv ≤ ε + 4e 2γ sqrt((1+γ)η/ω P). Theorem 4 provides structure learning guarantees using thresholding, and Theorem 5 shows that magnetic fields can be recovered with a second round of optimization, with error bounded by ε h + 4 sqrt(d ε h max e h max) + 4 sqrt(η h max e h max/ω P).

The paper also includes numerical experiments. For the Curie-Weiss model, the authors construct strongly metastable states by expanding the free energy around its minima. They show numerically that these states have η values that decay with system size, and they demonstrate that the model parameters J and h can be learned from Glauber dynamics samples that are stuck at a metastable state. They compare the PL loss landscape with the maximum likelihood loss landscape, showing that the PL loss function has its minimum close to the true model, while MLE predicts the wrong sign for the magnetic field in the model.

For a spin glass model with q=3 states and higher-order (third-order) interactions, the authors demonstrate learning from metastable samples. They observe metastability by comparing average energies of samples from different samplers, and show that both parameter and structure learning succeed given metastable samples, with the histogram of learned couplings clearly separating true hyperedges from non-edges.

The paper concludes with a discussion of open questions, including whether there are large separations between the two measures of metastability (conjecturing that the O(n) separation shown is not optimal), whether strong metastability is the right model for samples from unmixed Markov chains, and potential extensions to continuous variable graphical models and more general energy-based models.

Improvements for AI systems

Based on the paper, here are specific improvements for AI systems, particularly those involving Markov Chain Monte Carlo (MCMC) sampling, generative models, and probabilistic graphical model learning.

1. Robust Learning from Stuck Samplers (MCMC-based Generative Models)

  • Improvement: AI systems that use MCMC (e.g., Gibbs sampling, Metropolis-Hastings) for training or inference often fail when the chain gets trapped in a metastable state. Current practice discards this data or restarts the chain. This paper provides a theoretical guarantee that the true model parameters can still be learned from this bad data.

  • Specific Implementation: Modify the training loss function of an energy-based model or a Boltzmann machine. Instead of using Maximum Likelihood (which minimizes global KL divergence and will fail), switch to a Pseudo-Likelihood (PL) loss (or a conditional-likelihood-based loss like Interaction Screening). The paper proves that minimizing this PL loss on samples from a metastable state yields parameters that are provably close to the true stationary distribution's parameters, with an error bounded by the metastability parameter η.

  • What the improved AI system can do: It can continue training and converge to the correct model even when its internal sampler is demonstrably not mixing (e.g., stuck in a local mode). This makes training more robust and reduces the need for expensive burn-in periods or complex tempering schemes in scenarios where the sampler is slow. It effectively turns a failure mode (slow mixing) into a usable data source.

2. Enhanced Structure Learning for Sparse Graphical Models

  • Improvement: The paper provides rigorous guarantees (Theorem 3, 4, 5) for learning the structure (edges) and parameters of Ising models from metastable samples. This is a direct upgrade for any AI system that performs causal inference or learns sparse undirected graphical models from data.

  • Specific Implementation: When using l1-regularized logistic regression (a standard method for learning Ising models), the paper shows that the sample complexity and error bounds hold even if the data is not i.i.d. from the true distribution but from a strongly metastable one. The key is to use the conditional likelihood (PL) rather than the joint likelihood.

  • What the improved AI system can do: It can accurately reconstruct the underlying graph (which variables interact) and estimate the interaction strengths from data that would previously be considered too contaminated or unrepresentative. This is particularly useful in fields like systems biology or neuroscience, where data is often collected from dynamical systems that may not be in equilibrium.

3. New Criterion for Data Quality and Model Validation

  • Improvement: The paper defines a new, computable metric for data quality: strong metastability (violation of detailed balance). This is a more useful diagnostic than just looking at the total variation distance between the empirical data distribution and the model distribution.

  • Specific Implementation: Before training a generative model, an AI system can compute the strong metastability of its training data with respect to the model's transition kernel. If this value is small (η), the system can confidently use PL-based learning. If it is large, the system knows the data is not from a simple metastable state and may need to adjust its sampling strategy.

  • What the improved AI system can do: It can automatically assess whether its training data is good enough for a specific learning algorithm. It provides a principled way to decide between using a global metric (MLE) or a local metric (PL) for training, preventing the system from wasting resources on a method that is theoretically guaranteed to fail.

4. Improved Robustness for Conditional Models

  • Improvement: The core theoretical result (Theorem 1) shows that the single-variable conditionals of a metastable distribution are, on average, very close to those of the true distribution. This is a fundamental property that can be exploited by any AI system that uses conditional probabilities.

  • Specific Implementation: For AI systems that rely on autoregressive models (which factorize a joint distribution as a product of conditionals), this result implies that the model can be trained on data from a metastable state and still learn accurate conditionals. This is because the training objective for autoregressive models is precisely to match the conditionals.

  • What the improved AI system can do: It can be trained on data that is generated by a slow-mixing process (e.g., a video sequence from a physical simulation that is trapped in a local configuration) and still learn the correct transition probabilities between states, making its predictions more accurate and robust to non-equilibrium data.

5. New Algorithm for Detecting and Characterizing Metastable States

  • Improvement: The paper provides a constructive method (Section IV, Appendix C) for identifying strongly metastable distributions by analyzing the free energy landscape. This is a powerful tool for AI systems that need to understand the structure of complex systems.

  • Specific Implementation: An AI system analyzing a physical or biological system can use the paper's method to find local minima of the free energy. It can then construct candidate metastable distributions and verify their strong metastability by computing the detailed balance violation. This allows the system to identify and characterize the modes of a distribution that a sampler might get stuck in.

  • What the improved AI system can do: It can proactively identify the failure modes of its own samplers. For example, in a drug discovery pipeline, it could identify metastable protein conformations that a molecular dynamics simulation is likely to get trapped in, allowing for more efficient sampling strategies or a better understanding of the system's behavior.

Abstract

Physically motivated stochastic dynamics are widely used to sample from high-dimensional distributions. However, such samplers often get trapped in metastable states, approximately sampling from a distribution that differs significantly from the desired stationary state. We rigorously show that for multivariable discrete distributions, the true stationary model can nevertheless be recovered from these metastable samples. This relies on a fundamental observation: for distributions satisfying a strong metastability condition, their single-variable conditional probabilities are on average extremely close to those of the true stationary distribution. This remains true even when the two distributions are far apart under global metrics such as Kullback-Leibler divergence. Consequently, we can effectively learn the true model using a conditional-likelihood estimator even when the samples are drawn from a restricted state space. Extending these general results to Ising models, we prove rigorous parameter and structure learning guarantees. Finally, we demonstrate this phenomenon numerically on higher-alphabet spin glass models.

Sources

Related papers