Mixing-Free and Signal-Optimal Learning of Gaussian Graphical Models from Glauber Dynamics

Structure learning in Gaussian Graphical Models (GGMs) is typically performed using independent and identically distributed (i.i.d.) samples. However, in many real-world applications—such as tracking information spread or agent coordination—data are generated as a single, dependent trajectory of a stochastic process. The authors investigate whether it is possible to recover the graph structure from a single trajectory of random-scan Gaussian Glauber dynamics without relying on strong assumptions like fast mixing or specific spectral conditions, while maintaining optimal sample complexity.

The authors propose a meta-algorithm called DuNeS (Dueling-Neighborhood Search). This framework treats structure learning as a support-testing problem: for each node, it compares candidate neighborhoods against 'dueling' sets to verify the true edges. The authors instantiate this meta-algorithm with two distinct local statistics:

1. LS-DuNeS: Uses a local least-squares regression at each node. By leveraging the fact that each update provides a fresh Gaussian innovation, the authors construct a statistic that is robust to the non-stationary, dependent nature of the trajectory.
2. AU-DuNeS: Uses a pattern-based statistic that counts specific alternating update sequences (i, j, i). This approach avoids the need for complex corrections for neighbor-update contamination by explicitly testing candidate sets.

Both methods are designed to be 'mixing-free,' meaning they do not require the Markov chain to reach stationarity or satisfy a spectral gap condition, allowing them to work even when the dynamics are slow.

The study demonstrates that both LS-DuNeS and AU-DuNeS achieve the information-theoretically optimal dependence on the minimum edge strength (κ⁻²). LS-DuNeS requires approximately O(pd²/κ²) updates, while AU-DuNeS requires O(pd⁴/κ²) updates. Crucially, these guarantees hold from arbitrary initializations and do not require the chain to mix. The analysis relies on extracting 'fresh' Gaussian innovations from the update sequence, which allows for rigorous control of the statistics despite the high dependence between observations.