- 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 to , 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 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
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.
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 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 is neither nor , a window with updates counts as for the pair .
- 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.
Official Comment by Authors
Thank you for the very detailed review and for the specific suggestions on the motivation, the notation, and the experiments.
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/α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/α2 dependence in any model, including discrete ones such as Ising models; prior guarantees either do not establish 1/α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).
The precision-weighted update is not an added assumption: redrawing xi from its conditional law under N(0,Θ−1) is exactly the Glauber dynamics, the model of the prior work above. Each update of i is an observation y=∑j=iβijxj+ε with βij=−Θij/Θii and Gaussian ε 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−1 regressions. Finding the support is where the computational difficulty lies: given N(i), the βij are fit by least squares in at most k variables, while without it N(i) must be selected from ∑s≤k(sd−1) candidates, which results in the neighborhood search of Tirukkonda and Dasarathy (2026).
We will add a guide:
We will add future works and conclusion. We will give two takeaways and an open question:
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/4, starting from zero, on the same trajectories, with thresholds chosen on 100 separate simulations at each T. Exact graph recoveries on 100 fresh trajectories:
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) and OLS O(d/α2). On eight variables, OLS fits just seven predictors, which is easy, while the local algorithm must see iij or iji 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).