Improved Rates of Learning Gaussian Graphical Models from Glauber Dynamics

We give a polynomial-time algorithm for learning Gaussian graphical models from a single Glauber trajectory, reducing the observation time from $\tilde{O}(d^3/{\alpha }^5)$ (Shen et al., 2026) to $\tilde{O}(d^2/{\alpha }^2)$. Here $d$ is the maximum degree, $\alpha$ is the minimum normalized edge strength, and each coordinate updates at Poisson rate one. The guarantee is uniform over arbitrary initial states and independent of mixing time and condition number. Our method tests for edges using the three-update patterns $i,j,i$ and $i,i,j$. Changes in other variables can distort the test, so we combine results across randomly chosen interval lengths, using weights that reduce this error. This permits longer windows and a higher rate of informative observations. The resulting bound has optimal inverse-square dependence on edge strength, up to logarithmic factors.