New algorithms recover graphs from Glauber dynamics without mixing time
Two mixing-free methods achieve optimal κ⁻² sample complexity from dependent data
Gaussian graphical model selection typically assumes independent samples, but real data often come as dependent stochastic processes. Vignesh Tirukkonda and Gautam Dasarathy tackle exact recovery from a single trajectory of random-scan Gaussian Glauber dynamics. Existing methods either require the chain to mix (which can take super-polynomial time in dimension p) or are suboptimal in the minimum edge strength κ. The authors present two mixing-free algorithms that achieve the optimal κ⁻² dependence from information theory.
Both algorithms instantiate a dueling-neighborhood search meta-algorithm using local statistics built directly from the update sequence. The first fits least-squares regression at each node's updates, requiring O(p d²/κ²) updates (where d is max degree) and depends only logarithmically on a local conditioning quantity. The second counts occurrences of a specific update pattern and needs O(p d⁴/κ²) updates with no condition number dependence. A key technical contribution is extracting fresh Gaussian innovations from the dependent, non-stationary observations—enabling mixing-free control without invoking stationarity, spectral gaps, or mixing conditions.
- First algorithm: least-squares regression on update sequences, O(p d²/κ²) sample complexity
- Second algorithm: pattern-counting based, O(p d⁴/κ²) with no condition number dependence
- Both achieve exact recovery from arbitrary initialization without mixing time constraints
Why It Matters
Enables reliable graph structure learning from dependent time-series data without waiting for chain convergence.