Search papers, labs, and topics across Lattice.
This paper presents a polynomial-time algorithm for learning the structure of a $d$-sparse Gaussian graphical model from a single trajectory of Glauber dynamics, addressing the challenge of temporally correlated observations. The proposed method achieves a trajectory-length guarantee independent of the mixing time, which is a significant advancement over existing approaches that rely on i.i.d. samples. Key components of the algorithm include conditional variance estimation, a local edge testing mechanism, and a robust median-based estimator to ensure accuracy despite temporal dependencies.
Learning Gaussian graphical models from a single trajectory could revolutionize how we handle temporally correlated data in machine learning applications.
We study the task of learning the structure of a $d$-sparse Gaussian graphical model on $n$ variables from a single trajectory of Glauber dynamics. Beyond algorithmic considerations, many applications present temporally correlated observations rather than i.i.d.\ samples. In the classical i.i.d.\ setting, under comparably general sparsity and minimum edge-strength assumptions, sublinear-in-$n$ sample guarantees are known, but achieving them in polynomial-time remains open. Motivated in part by this gap, we give a polynomial-time algorithm that recovers the conditional-independence graph from a single Glauber trajectory, with a trajectory-length guarantee that does not depend on the mixing time. Technically, our algorithm has three components. First, we estimate the conditional variances and rescale the trajectory to reduce to the unit-diagonal case, without changing the underlying graph. Second, we design a local edge test that extracts adjacency information from short update windows by isolating pairwise influence. Third, we aggregate these local statistics using a robust median-based estimator, and prove accuracy despite temporal dependence arising from a single trajectory.
