level: research
gaussian graphical model selection typically assumes independent samples, but many real-world datasets come as a single trajectory from a dependent process. this work focuses on exact graph recovery from one trajectory of random-scan gaussian glauber dynamics. existing methods either rely on the chain's mixing time, which can be super-polynomial in dimension without strong assumptions, or are suboptimal in the minimum normalized edge strength.
the authors propose two algorithms that avoid mixing time entirely and achieve the optimal dependence on edge strength, matching information-theoretic lower bounds. both use a dueling-neighborhood search meta-algorithm with a local statistic computed directly from the update sequence. the first algorithm fits a least-squares regression at each node's updates and recovers the graph from roughly order of p times d squared divided by kappa squared updates, where p is dimension, d is maximum degree, and kappa is minimum edge strength.
the second algorithm uses a simpler threshold-based test and requires slightly more updates but is computationally lighter. both methods work without requiring the chain to mix, making them applicable to high-dimensional settings where mixing is slow. the analysis relies on new concentration inequalities for dependent data from the glauber dynamics, showing that local update statistics concentrate around their expectations even far from stationarity.
why it matters: this enables learning graphical models from dependent time-series data without waiting for mixing, useful in neuroscience, finance, and other fields where only a single long observation is available.