Learning Gaussian Graphical Models from a Glauber Trajectory Without Mixing

Learning the structure of a Gaussian graphical model (GGM) is a fundamental task in high-dimensional statistics. While efficient algorithms exist for i.i.d. samples, many real-world systems provide temporally correlated observations, such as those generated by Glauber dynamics. A critical question is whether one can learn the conditional-independence graph from a single trajectory of such dynamics without waiting for the chain to reach stationarity (mixing), which can be prohibitively slow.

The authors introduce a polynomial-time algorithm that recovers the sparsity pattern of a d-sparse GGM from a single Glauber trajectory. The approach consists of three main steps:

1. Normalization: The algorithm estimates conditional variances from short trajectory windows to rescale the model, effectively reducing it to a unit-diagonal precision matrix.
2. Local Edge Testing: For each candidate edge, the algorithm identifies specific update patterns (the "iiji" pattern) that isolate the influence of one variable on another. This pattern is designed to break the temporal dependence inherent in the trajectory.
3. Robust Aggregation: Because the algorithm cannot perfectly verify if a window is "clean" (i.e., free from confounding updates by neighbors), it treats windows with potential hidden updates as contaminated and uses a robust median-based estimator to aggregate statistics across many windows.

The authors prove that their algorithm recovers the sparsity pattern with high probability given a trajectory length that depends polynomially on the sparsity d and the minimum edge strength, but crucially, with no dependence on the mixing time. They also provide an information-theoretic lower bound, showing that a logarithmic trajectory length is necessary for structure learning, and demonstrate that their algorithm matches this logarithmic dependence.