Learning Gaussian Graphical Models from a Glauber Trajectory Without Mixing

• URL: http://arxiv.org/abs/2606.31230v1
• Date: Tue, 30 Jun 2026 07:07:57 GMT
• Title: Learning Gaussian Graphical Models from a Glauber Trajectory Without Mixing
• Abstract summary: 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.<n>Motivated in part by this gap, we give a conditional-time algorithm that recovers the trajectory-length guarantee from a single Glauber trajectory.
• Score: 13.453178572042125
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• Mixing-Free and Signal-Optimal Learning of Gaussian Graphical Models from Glauber Dynamics [5.844015313757267]
  We study exact recovery of the graph from one trajectory of random-scan Gaussian Glauber dynamics.<n>We propose two algorithms that are mixing-free and attain the $-2$ dependence of the information-theoretic lower bounds.
  arXiv  Detail & Related papers  (2026-07-20T22:44:45Z)
• Why SGD is not Brownian Motion: A New Perspective on Stochastic Dynamics [92.39053980710702]
  Gradient Descent (SGD) is commonly modeled as a Langevin process, assuming that minibatch noise acts as Brownian motion.<n>This approximation relies on a continuous-time limit and a sqrt(eta) noise scaling that does not match the discrete SGD update at finite learning rate.<n>We propose an alternative formulation of SGD as deterministic dynamics in a fluctuating loss landscape induced by minibatch sampling.
  arXiv  Detail & Related papers  (2026-05-21T15:50:40Z)
• On the Wasserstein Convergence and Straightness of Rectified Flow [54.580605276017096]
  Rectified Flow (RF) is a generative model that aims to learn straight flow trajectories from noise to data.<n>We provide a theoretical analysis of the Wasserstein distance between the sampling distribution of RF and the target distribution.<n>We present general conditions guaranteeing uniqueness and straightness of 1-RF, which is in line with previous empirical findings.
  arXiv  Detail & Related papers  (2024-10-19T02:36:11Z)
• Bypassing the Noisy Parity Barrier: Learning Higher-Order Markov Random Fields from Dynamics [21.976109703401114]
  We consider the problem of learning graphical models, also known as Markov random fields (MRFs) from temporally correlated samples. In particular, we show that given a trajectory with $widetildeO_k(n)$ site updates of an order $k$ MRF from the Glauber dynamics, there is an algorithm that recovers the graph and the parameters in $widetildeO_k(n2)$ time. Our results thus surprisingly show that this more realistic, but intuitively less tractable, model for MRFs actually leads to efficiency far beyond what
  arXiv  Detail & Related papers  (2024-09-09T02:32:45Z)
• Bayesian Circular Regression with von Mises Quasi-Processes [57.88921637944379]
  In this work we explore a family of expressive and interpretable distributions over circle-valued random functions.<n>For posterior inference, we introduce a new Stratonovich-like augmentation that lends itself to fast Gibbs sampling.<n>We present experiments applying this model to the prediction of wind directions and the percentage of the running gait cycle as a function of joint angles.
  arXiv  Detail & Related papers  (2024-06-19T01:57:21Z)
• Graph Spatiotemporal Process for Multivariate Time Series Anomaly Detection with Missing Values [67.76168547245237]
  We introduce a novel framework called GST-Pro, which utilizes a graphtemporal process and anomaly scorer to detect anomalies. Our experimental results show that the GST-Pro method can effectively detect anomalies in time series data and outperforms state-of-the-art methods.
  arXiv  Detail & Related papers  (2024-01-11T10:10:16Z)
• Towards Faster Non-Asymptotic Convergence for Diffusion-Based Generative Models [49.81937966106691]
  We develop a suite of non-asymptotic theory towards understanding the data generation process of diffusion models. In contrast to prior works, our theory is developed based on an elementary yet versatile non-asymptotic approach.
  arXiv  Detail & Related papers  (2023-06-15T16:30:08Z)
• Bridging Discrete and Backpropagation: Straight-Through and Beyond [62.46558842476455]
  We propose a novel approach to approximate the gradient of parameters involved in generating discrete latent variables. We propose ReinMax, which achieves second-order accuracy by integrating Heun's method, a second-order numerical method for solving ODEs.
  arXiv  Detail & Related papers  (2023-04-17T20:59:49Z)
• Machine learning algorithms for three-dimensional mean-curvature computation in the level-set method [0.0]
  We propose a data-driven mean-curvature solver for the level-set method. Our proposed system can yield more accurate mean-curvature estimations than modern particle-based interface reconstruction.
  arXiv  Detail & Related papers  (2022-08-18T20:19:22Z)
• Nonparametric Factor Trajectory Learning for Dynamic Tensor Decomposition [20.55025648415664]
  We propose NON FActor Trajectory learning for dynamic tensor decomposition (NONFAT) We use a second-level GP to sample the entry values and to capture the temporal relationship between the entities. We have shown the advantage of our method in several real-world applications.
  arXiv  Detail & Related papers  (2022-07-06T05:33:00Z)
• Learning with little mixing [9.574025613149871]
  We study square loss in a realizable time-series framework with martingale difference noise. Our main result is a fast rate excess risk bound which shows that whenever a trajectory hypercontractivity condition holds, the risk of the least-squares estimator on dependent data matches the iid rate order-wise after a burn-in time.
  arXiv  Detail & Related papers  (2022-06-16T16:06:47Z)
• Learning non-Gaussian graphical models via Hessian scores and triangular transport [6.308539010172309]
  We propose an algorithm for learning the Markov structure of continuous and non-Gaussian distributions. Our algorithm SING estimates the density using a deterministic coupling, induced by a triangular transport map, and iteratively exploits sparse structure in the map to reveal sparsity in the graph.
  arXiv  Detail & Related papers  (2021-01-08T16:42:42Z)
• Least Squares Regression with Markovian Data: Fundamental Limits and Algorithms [69.45237691598774]
  We study the problem of least squares linear regression where the data-points are dependent and are sampled from a Markov chain. We establish sharp information theoretic minimax lower bounds for this problem in terms of $tau_mathsfmix$. We propose an algorithm based on experience replay--a popular reinforcement learning technique--that achieves a significantly better error rate.
  arXiv  Detail & Related papers  (2020-06-16T04:26:50Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.