acceptodds
Under review as a conference paper at ICLR 2027

Improved Rates of Learning Gaussian Graphical Models from Glauber Dynamics

Abstract

We give a polynomial-time algorithm for learning Gaussian graphical models from a single Glauber trajectory, reducing the observation time from (Shen et al., 2026) to . Here is the maximum degree, 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 and . 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.

Primary area:
learning theory
Keywords:
Glauber Dynamics, Gaussian Graphical Models, Theory, Algorithms, Learning from dynamics

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_TCmuOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
1
Soundness
3
Read review
Paper summary

This paper discusses improvements in learning the underlying structure of a Gaussian Graphical Model using only the observations of the graph variables being updated. Variables are updated one at a time, with updates randomly distributed as a poisson distribution, and the joint Gaussian model is held static.

The key contributions are a description of 3 algorithm variants (local, least-squares and least-squares subset) with associated proofs for each, that significantly improve the required observation time compared to the problem's previous state of the art (Shen 2026, Tirukkonda & Dasarathy 2026), approaching the theoretical minimum. There is no empirical validation, as the paper's results are primarily theoretical.

Critical strengths

This work has strong technical merit, significantly reducing the observation time compared to previous works.

The local algorithm proposed requires shorter update patterns (i,i,j and i,j,i vs i,i,j,i), thereby increasing their likelihood and reducing the required observation time. Moreover, by taking a weighted average of observation windows with weights carefully designed to remove the bias from other variables' updates, they allow for a longer observation window than Shen (which kept the observation window intentionally small to reduce the chance of additional neighbouring variables updating).

These combine for a result that drives down the observation time from O~(k3a−5)\tilde{O}(k^3a^{-5}) to O~(k2a−2)\tilde{O}(k^2a^{-2}), while keeping computation in polynomial time and requires no guarantees on mixing time or initial state.

Critical weaknesses

This work has several key issues, which I would like to see resolved - primarily in its motivation and the clarity of presentation.

1. Motivation

I don't yet understand the motivation for this problem. While there are clear and significant theoretical improvements in the observation time from previous work, I need some more convincing of why this is useful and what it's potential applications are. My concern is that the assumptions are very restrictive:

  • the variables update on a poisson clock
  • the graph we're learning has static edges
  • the updates are precision-weighted sums of their neighbours (rather than some unknown dynamics) and that on top of this, we are only learning the existence of edges rather than the edges' correlation/covariance.

As a result, in the paper's current form the motivation is too brief and needs to be clearer. Without an improved understanding of where the proposed solutions would be employed, it's difficult to appreciate the technical significance of the work.

2. Clarity

There is too much assumed knowledge in the main text. It would be helpful to:

  • explain that patterns like (i,i,j) or (i,i,j,i) are update patterns for two co-ordinates x_i and x_j when first referring to them
  • defining variables more clearly, such as the failure probability delta (e.g. is it the proportion of edges correctly identified, or the probability of successfully identifying the overall graph structure?) or what acceptance Aij\mathcal{A}_{ij} means.
  • defining acronyms on first use, even when they're ubiquitous across the field (e.g. OLS)
  • include some figures to illustrate some of the theoretical results more clearly.
  • a conclusion or summary section at the end, describing the key findings, their significance, and interesting areas for future work would be beneficial.

While I appreciate these will be clear to the authors, they made the paper difficult to interpret - individually none affect my assessment, but these and several more small examples each contribute to a wider pattern in the paper of assuming far too much familiarity with relevant theory from the reader.

Questions for authors

I congratulate the authors on their work, and have worked to give as honest and rigorous an assessment as I am capable. My key remaining suggestions for the authors are below:

1. Clearer setting out of assumptions

There are several assumptions restricting the set of Gaussian graphical models this algorithm applies to, however they're currently scattered throughout the paper. For practitioners, it would be very helpful to have these collected in one place clearly laid out with the below:

  • the variables update on a poisson clock
  • the graph being learned has static edges
  • the updates are precision-weighted sums of their neighbours (rather than unknown dynamics)

2. Empirical validation

While I appreciate this is primarily a theoretical paper, having no empirical validation at all has made it difficult to interpret the improvement over Tirukkonda & Dasarathy's result, and how robustly the asymptotic, theoretical results translate to empirical settings. I would suggest including some results from small, simple, synthetic graphs to compare the yours against Tirukkonda & Dasarathy's - I think it would also help with clarity.

5 comments
AuthorsOpenReview ↗

Official Comment by Authors

Thank you for the very detailed review and for the specific suggestions on the motivation, the notation, and the experiments.

On the motivation.

In most of statistics, each observation is assumed to be a fresh i.i.d. sample, which is often unrealistic; a more realistic model is that the world evolves over time according to some dynamics and we observe it as it evolves. We consider Gaussian Glauber dynamics because Glauber dynamics is one of the simplest and most common dynamics, and Gaussians are the most well-studied continuous random variables, complementing the discrete Ising and higher-order Markov random field setting of Gaitonde, Moitra, and Mossel (2025). These two choices together determine the model of this paper and of prior work (Tirukkonda et al., 2024; Shen et al., 2026; Tirukkonda and Dasarathy, 2026).

Even for degree-one graphs, the observation time must scale as 1/α21/\alpha^2 (Shen et al., 2026, Theorem 7.3). To our knowledge, Theorem 1.1 is the first polynomial-time algorithm for learning from Glauber dynamics with a proven 1/α21/\alpha^2 dependence in any model, including discrete ones such as Ising models; prior guarantees either do not establish 1/α21/\alpha^2 (Tirukkonda et al., 2024; Gaitonde and Mossel, 2024; Gaitonde et al., 2025; Shen et al., 2026) or search over all candidate neighborhoods (Tirukkonda and Dasarathy, 2026). This answers the question posed by Tirukkonda and Dasarathy (2026, Section 7).

On the update rule and edges-only learning.

The precision-weighted update is not an added assumption: redrawing xix_i from its conditional law under N(0,Θ−1)N(0,\Theta^{-1}) is exactly the Glauber dynamics, the model of the prior work above. Each update of ii is an observation y=∑j≠iβijxj+εy=\sum_{j\neq i}\beta_{ij}x_j+\varepsilon with βij=−Θij/Θii\beta_{ij}=-\Theta_{ij}/\Theta_{ii} and Gaussian ε\varepsilon independent of the current state, so each coordinate defines a sparse linear regression, a central problem in statistics, whose covariates are generated by the other d−1d-1 regressions. Finding the support is where the computational difficulty lies: given N(i)N(i), the βij\beta_{ij} are fit by least squares in at most kk variables, while without it N(i)N(i) must be selected from ∑s≤k(d−1s)\sum_{s\le k}\binom{d-1}{s} candidates, which results in the neighborhood search of Tirukkonda and Dasarathy (2026).

On notation (update patterns and δ\delta).

We will add a guide:

  • There are dd variables, the maximum degree is at most kk, and every edge has normalized strength at least α\alpha.
  • Every update is observed and each coordinate has an independent rate-one clock, giving dTdT updates by time TT in expectation.
  • We want the entire graph to be correct with probability at least 1−δ1-\delta.
  • Algorithm 1 accepts a window if reading only ii and jj gives exactly iijiij or ijiiji; for example, i,ℓ,j,ii,\ell,j,i gives ijiiji for a third variable ℓ\ell.

On a conclusion.

We will add future works and conclusion. We will give two takeaways and an open question:

  • One can learn the graph in polynomial time with the optimal 1/α21/\alpha^2 dependence, up to logarithmic factors, without mixing.
  • One need not commit to a single update pattern that works from every starting state, as with iijiiiji in Shen et al. (2026) and iijiiiijii in Gaitonde et al. (2025). We combine iijiij, informative when the expected change in jj is small, with ijiiji, informative when it is large; their signals share a sign, so we use both without knowing the regime, and with bias cancellation across window lengths this improves 1/α51/\alpha^5 to 1/α21/\alpha^2.
  • Future work: the local test pays k2k^2 while Algorithm 3 pays kk via neighborhood search; can linear dependence on kk be achieved in polynomial time?

On synthetic experiments.

For this rebuttal, we ran nodewise ordinary least squares (OLS, Algorithm 2) against LS-DuNeS (Tirukkonda and Dasarathy, 2026) on an eight-node cycle with normalized edge strength 1/41/4, starting from zero, on the same trajectories, with thresholds chosen on 100 separate simulations at each TT. Exact graph recoveries on 100 fresh trajectories:

Observation time TTOLS (Algorithm 2)LS-DuNeS
640/1000/100
25633/10015/100
1024100/10098/100

On asymptotics vs. practice.

The local algorithm (Algorithm 1) runs in polynomial time, but its advantage is asymptotic, which is why our experiment compares OLS instead. Theorem 1.1 concerns sparse graphs in high dimension, where the local algorithm needs O~(k2/α2)\widetilde O(k^2/\alpha^2) and OLS O~(d/α2)\widetilde O(d/\alpha^2). On eight variables, OLS fits just seven predictors, which is easy, while the local algorithm must see iijiij or ijiiji in a short window to get even one observation for a pair, so its advantage does not show at simulable lengths. We believe the paper should be judged on the theoretical merits of Theorem 1.1, which resolves the open question of Tirukkonda and Dasarathy (2026).

I thank the authors for their comments - their hard work and desire for the paper's success is clear and commendable. The theoretical results, particularly Theorem 1.1, are a significant improvement in an active field. Moreover, I appreciate the addition of a conclusion & future work, as well as the experiment and the motivation they've provided.

Unfortunately, their comments don't entirely resolve my two primary concerns - motivation and clarity. While motivation has been mostly addressed (though I would like to better understand real-world applications of Glauber dynamics), the paper's clarity hasn't. I think the issues require more than a notation guide, as the paper's main body would remain impenetrably dense. Concepts, variables and ideas should be introduced throughout the paper, with as little technical jargon as possible, and that involves significant text revision.

As a result, I will keep my score. The results presented are worthy of publication, however the paper in its current state is too unclear. While the changes suggested by the authors would help, I believe the work required for the paper's legibility is substantial enough that I can't approve its submission. As a result, I believe this paper would do well to be revised and resubmitted to another conference.

AuthorsOpenReview ↗

Official Comment by Authors

Thank you for following up. Your comment helped us see where the motivation and definitions needed to appear in the argument itself. We’ve revised the main body of the paper to improve clarity in the following ways.

  • Motivation. We start with the tradeoff between sample size and computation for independent observations. We then explain what prior work achieved with discrete Glauber dynamics, and why the Gaussian case is a natural next question.
  • Model and recovery task. At the start of the results, we give the observation model and the recovery problem in separate boxes. We explain why the regressions are quick to fit once the neighborhoods are known, and clarify that δ\delta bounds the probability of any error in the recovered edge set.
  • Local test. Before defining the test statistic, we spell out which windows count for a pair of coordinates. For example, if ℓ\ell is neither ii nor jj, a window with updates (i,ℓ,j,i)(i,\ell,j,i) counts as (i,j,i)(i,j,i) for the pair (i,j)(i,j).
  • Rates and computation. We explain why the inverse-square dependence on edge strength is a necessary lower bound and why its dependence matters to our paper, and spell out the tradeoff between polynomial-time algorithms and exhaustive neighborhood search. The local algorithm achieves the optimal dependence on edge strength up to logarithmic factors uniformly over arbitrary starts.

The technical overview is meant to help readers follow the main steps of the proofs of Theorems 1.1–1.3. For Theorem 1.1, Section 2.1 explains where the local test gets its evidence for an edge and how combining windows of different lengths controls the bias from other coordinates updating. Establishing that control uniformly over starting states is a technically involved part of the proof.

Section 2.2 explains how the guarantees for Ordinary least squares (OLS) and exhaustive subset selection in Theorems 1.2 and 1.3 follow from two shared technical bounds. The main difficulty is proving that a single trajectory supplies enough variation in the predictors and controlling how the update noise affects our estimator (Lemmas D.1 and D.2). Once those bounds are in place, standard least-squares arguments give the coefficient error bounds needed to recover the graph.

We’ll upload the revised manuscript later today. We’d be grateful if you could take another look once it’s up. If there’s a step where the role of the technical argument is still hard to see, we’d appreciate knowing where.

Reviewer_kNHvOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies the problem of recovering the underlying Gaussian graphical model from a single trajectory generated by Glauber dynamics.

Suppose we are given a sequence of samples generated as follows. We start with an initial state x(0)x^{(0)}, which can be arbitrary. Each coordinate ii has an independent rate-one Poisson clock. Specifically, the time between consecutive updates of coordinate ii follows an exponential distribution with mean 11. Whenever a clock rings, the corresponding coordinate is resampled from its conditional Gaussian distribution given the current values of all other coordinates, which remain unchanged. This produces a sequence of dependent samples. Our goal is to recover the underlying graph from this trajectory.

The proposed approach works as follows. First, the algorithm partitions the observed trajectory into consecutive intervals of randomly selected lengths. Within each interval, it examines every pair of nodes (i,j)(i,j) and checks whether their update sequence matches either (i,i,j)(i,i,j) or (i,j,i)(i,j,i). If so, it computes a statistic based on the signs of their value changes and updates the pair's accumulated score SijS_{ij} using a weighted contribution. The weights are designed to cancel biases introduced by updates to other coordinates. After processing all intervals, the algorithm declares an edge between ii and jj if the absolute average score exceeds a predefined threshold.

The main theoretical result shows that the algorithm can recover the exact underlying graph with probability at least 1−δ1-\delta using an observation time of O~(k2/α2)\widetilde O(k^2/\alpha^2), where kk is the maximum graph degree and α\alpha is the minimum normalized edge strength. The algorithm runs in polynomial time, and its guarantee does not depend on the mixing time or condition number.

Critical strengths
  • The paper significantly improves the observation-time complexity of graph recovery while maintaining polynomial-time computation.
Critical weaknesses
  • The presentation may be challenging for readers unfamiliar with the domain. More intuitive explanations would help improve accessibility and clarity.
Questions for authors

see weaknesses

2 comments
AuthorsOpenReview ↗

Official Comment by Authors

Thank you for pointing out where an example would help explain the local algorithm.

The presentation may be challenging for readers unfamiliar with the domain.

We agree that the exposition is demanding for readers outside this area. We wrote the technical overview to isolate the core of the argument.

The main new idea is to use two update patterns: iijiij for testing whether a change in coordinate xix_i carries over to xjx_j; ijiiji testing whether a change in xjx_j carries back to xix_i, and to show that together they suffice from every starting state. In the revision we will make this clearer.

More intuitive explanations would help improve accessibility and clarity.

We will add more intuitive explanations in the revision. For reference, consider two coordinates xix_i and xjx_j with Θii=Θjj=1\Theta_{ii}=\Theta_{jj}=1 and Θij=1/2\Theta_{ij}=1/2. Each update redraws one coordinate as −1/2-1/2 times the other plus independent N(0,1)N(0,1) noise, so along this edge the two tend to move in opposite directions. In a window, let Δi\Delta_i be the change in xix_i at its last update and Δj\Delta_j the change in xjx_j at its update. Without an edge, Pr⁡[ΔiΔj<0]=12\Pr[\Delta_i\Delta_j<0]=\tfrac12; with an edge, the excess Pr⁡[ΔiΔj<0]−12\Pr[\Delta_i\Delta_j<0]-\tfrac12 is nonnegative for both patterns and Ω(α)\Omega(\alpha) for at least one.

We write ξ1,ξ2,ξ3\xi_1,\xi_2,\xi_3 for the independent N(0,1)N(0,1) noises of the three updates and m=E[Δj]=−34xjm=\mathbb E[\Delta_j]=-\tfrac34 x_j, where xjx_j is its starting value. Then

  • iijiij: Δi=ξ2−ξ1\Delta_i=\xi_2-\xi_1 and Δj=m−12ξ2+ξ3\Delta_j=m-\tfrac12\xi_2+\xi_3;
  • ijiiji: Δj=m−12ξ1+ξ2\Delta_j=m-\tfrac12\xi_1+\xi_2 and Δi=−12Δj+ξ3−ξ1\Delta_i=-\tfrac12\Delta_j+\xi_3-\xi_1.

When mm is small, the sign of Δj\Delta_j is set by the noise. In iijiij, Δj\Delta_j contains −12ξ2-\tfrac12\xi_2, the fresh fluctuation of xix_i carried over to xjx_j, so Δi\Delta_i and Δj\Delta_j have opposite signs noticeably more often than not. In ijiiji, the response −12Δj-\tfrac12\Delta_j of xix_i is largely offset by −ξ1-\xi_1, which also enters Δj\Delta_j, so the excess is small.

When mm is large, Δj>0\Delta_j>0 with high probability. In iijiij, the sign of Δi=ξ2−ξ1\Delta_i=\xi_2-\xi_1 is then close to a fair coin, so the excess nearly vanishes. In ijiiji, Δi\Delta_i has mean −m/2-m/2, so with high probability xix_i moves down while xjx_j moves up, and the excess is large.

Since both excesses are nonnegative, we can average the two patterns without knowing which case we are in.

Thank you for the response and the clarification. I will keep the original positive score.

Reviewer_XW4NOpenReview ↗
Rating
2
Confidence
2
Informativeness
1
Presentation
1
Soundness
3
Read review
Paper summary

This paper studies learning Gaussian graphical model from GLAUBER dynamics. The paper propose a new update pattern which results in an improved rate of learning from O(k^3/alpha^5) to O(k^2/alpha^2), where k is the maximum degree of the underlying graph and alpha is the minimum normalised edge strength.

Critical strengths

The problem is interesting and the theoretical contribution, i.e., rate improvement is solid.

Critical weaknesses

However, the paper is not well written and hard to follow: starting from abstract: what is the meaning of uptake pattern i-j-i versus i-i-j or any other patterns?

Many notations are not properly defined and thus hard to both understand and verify the correctness of the statements. The paper reads like a technical report for a knowledgeable person who I directly working on similar problem.

I do understand that the paper is mainly theoretical and it shows the rate improvements but it is useful to see how it outperforms the state of the art in at least some synthetic experiments.

Tirukkonda & Dasarathy (2026) already obtain the similar rate. The dense-graph comparisons in Appendix E rest on the authors’ own adaptations of baselines, and the table mixes bounds with different assumptions (for example, H depends on the initial state). The claimed improvements need fairer framing.

Questions for authors

The algorithms need known k, alpha, delta, a fully observed continuous-time trajectory, and rate-one clocks. how robust is the method when they are misspecified?

Please define the terms and notations

1 comment
AuthorsOpenReview ↗

Official Comment by Authors

Thank you for raising the comparison with Tirukkonda and Dasarathy and for pointing out where the notation was hard to follow.

Tirukkonda & Dasarathy (2026) already obtain the similar rate.

This comparison leaves out the cost of that rate. Tirukkonda and Dasarathy (2026) do get 1/α21/\alpha^2, but both of their algorithms search exhaustively over candidate neighborhoods, so their running time scales as d2k+1d^{2k+1}, which is not polynomial. In Section 7 they list recovery without mixing, optimal dependence on edge strength, and polynomial running time, and ask whether “all three can be achieved simultaneously.” Theorem 1.1 answers this affirmatively up to logarithmic factors: observation time O~(k2/α2)\widetilde O(k^2/\alpha^2) from every starting state, with polynomial running time whose exponent is independent of kk. The earlier polynomial-time algorithm of Shen et al. (2026, Theorem 1.3) needs O~(k3/α5)\widetilde O(k^3/\alpha^5), and their lower bound (Theorem 7.3) shows that 1/α21/\alpha^2 is necessary even for degree-one graphs.

The dense-graph comparisons in Appendix E rest on the authors’ own adaptations of baselines, and the table mixes bounds with different assumptions (for example, H depends on the initial state). The claimed improvements need fairer framing.

The purpose of Appendix E is to establish a polynomial-time baseline for our dense ordinary least squares (OLS) result, and we did not alter their methods. The theorems of Tirukkonda and Dasarathy (2026) assume d≥2k+1d\ge 2k+1 in our notation (their Section 3.3), so they give no bound for dense graphs, and setting k=d−1k=d-1 is not allowed. Appendix E therefore applies their own estimators and analysis with the predictor set fixed to all other vertices, which only removes the neighborhood search, and obtains d2/α2d^2/\alpha^2 times a logarithm that depends on the covariance and the start for LS, and O~(d3/α2)\widetilde O(d^3/\alpha^2) for AU, against O~(d/α2)\widetilde O(d/\alpha^2) for OLS uniformly over models and starts (our Theorem 1.2). A sharper analysis or a different algorithm may well do better. Neither dense bound is in the main table, and our comparison for Theorem 1.1 uses only their sparse results as stated (their Theorems 1 and 2).

HH is the logarithmic factor in the LS-DuNeS bound (their Theorem 1), which depends on the covariance and on the start zz. We list it separately because, as our Theorems 1.1 and 1.2 show, this dependence on the covariance and the start is unnecessary. We will give HH its own column and label the dense bounds as our deductions wherever we quote them.

what is the meaning of uptake pattern i-j-i versus i-i-j or any other patterns?

Please define the terms and notations

In prior work on learning from dynamics, it is standard to use patterns of updates, for example iijiiiji in Shen et al. (2026, Section 2) and iijiiiijii in Gaitonde, Moitra, and Mossel (2025, Section 2), and we use the same approach and notation. Reading only the updates to ii and jj in a window (other coordinates may update in between), ijiiji means ii, then jj, then ii again, and iijiij means ii twice, then jj. What is new is that these two orders give complementary edge signals that we can combine from every starting state. We will define the notation at first use in the abstract and collect the definitions before the results.

The algorithms need known k, alpha, delta, a fully observed continuous-time trajectory, and rate-one clocks. how robust is the method when they are misspecified?

We chose the simplest setting in which the core difficulty already arises: telling a direct interaction from the effect of updates to neighboring coordinates, using one trajectory that may be far from equilibrium. Whether this could be done in polynomial time with the optimal dependence on edge strength was open even there. Several of these assumptions can be relaxed without changing that difficulty:

  • Clock rates: a common rate only rescales observation time, and rates within a constant factor of each other change the guarantees by constant factors.
  • Known parameters: Algorithm 1 needs only an upper bound KK on the degree and a lower bound a>0a>0 on the edge strength, and Theorem 1.1 then gives O~(K2/a2)\widetilde O(K^2/a^2) at the failure probability δ\delta we choose.
  • Partial observation: if each window is observed independently with probability pp (its starting state and all its updates), we run the same test on the observed windows, and since the proof works from every starting state, this costs a factor O(1/p)O(1/p) in elapsed time.

it is useful to see how it outperforms the state of the art in at least some synthetic experiments.

In an experiment run for this rebuttal on an eight-node cycle, nodewise OLS (Algorithm 2) recovered the entire graph on 33 of 100 trajectories at T=256T=256, against 15 for LS-DuNeS, and on 100 against 98 at T=1024T=1024. Our response to Reviewer TCmu gives the setup and discusses the local algorithm.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.