Learning Gaussian Graphical Models from a Glauber Trajectory Without Mixing

We study the task of learning the structure of a $d$-sparse Gaussian graphical model on $n$ variables from a single trajectory of Glauber dynamics. Beyond algorithmic considerations, many applications present temporally correlated observations rather than i.i.d. samples. Moreover, in the classical i.i.d. setting, polynomial-time structure learning from a sublinear in $n$ number of samples is suspected to be computationally hard without additional assumptions on the precision matrix. Motivated in part by this, we design the first polynomial-time algorithm that recovers the conditional-independence graph from a single Glauber trajectory, with a trajectory-length guarantee that does not depend on the mixing time. Technically, our algorithm has three components. First, we estimate the conditional variances and rescale the trajectory to reduce to the unit-diagonal case, without changing the underlying graph. Second, we design a local edge test that extracts adjacency information from short update windows by isolating pairwise influence. Third, we aggregate these local statistics using a robust median-based estimator, and prove accuracy despite contamination and temporal dependence arising from a single trajectory.

Many scientific datasets record a system as it changes over time, rather than as separate independent measurements. This paper studies how to learn which quantities directly affect each other from one long record of such a system. A standard approach is to wait long enough that the data look nearly independent, but this waiting period can be extremely long or hard to estimate. We give an efficient method that avoids this step. The method searches for short, informative patterns in the system’s updates, uses them to test whether two quantities are directly linked, and combines many such tests in a way that is robust to misleading observations. Our results show that a single time series can contain enough local information to learn the underlying interaction network, even when the system evolves slowly.