Pith. sign in

REVIEW 1 major objections 2 minor 53 references

A single dependent Glauber trajectory suffices to recover a Gaussian graphical model's graph at the optimal κ⁻² signal rate — no mixing or stationarity required.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review · deepseek-v4-flash

2026-08-01 15:06 UTC pith:WTCSIEGU

load-bearing objection The paper is the real thing — mixing-free, κ⁻²-rate GGM recovery from a single Glauber trajectory — but the printed LS-DuNeS threshold τ = κ/(2√λ⁻_m) is a misplaced radical that breaks the separation proof; the intended τ = (κ/2)√λ⁻_m closes it. the 1 major comments →

arxiv 2607.18559 v1 pith:WTCSIEGU submitted 2026-07-20 stat.ML cs.LGmath.STstat.TH

Mixing-Free and Signal-Optimal Learning of Gaussian Graphical Models from Glauber Dynamics

Vignesh Tirukkonda , Gautam Dasarathy This is my paper
classification stat.ML cs.LGmath.STstat.TH MSC 62M0560J10
keywords Gaussian graphical modelsstructure learningGlauber dynamicssingle-trajectory estimationmixing-free guaranteessample complexitydueling neighborhood searchexact recovery
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper takes on a harder version of a classic statistics problem: instead of independent samples from a Gaussian graphical model, the data are a single trajectory of a random-scan Gaussian Glauber (Gibbs) sampler, whose successive states are highly dependent and non-stationary. It argues that the conditional-independence graph can still be recovered exactly, at the information-theoretically optimal dependence on the weakest edge's signal strength κ, without waiting for the chain to mix: no stationarity, spectral-gap, or Dobrushin-type contraction conditions anywhere. The route is a shared dueling-sets search (DuNeS) instantiated by two local statistics: a least-squares regression read off each node's own update times (LS-DuNeS, about p d²/κ² updates for p variables of degree at most d), and a pattern-counting statistic built from alternating i,i,j,i update blocks (AU-DuNeS, about p d⁴/κ² updates, with no condition-number dependence). A sympathetic reader would summarize the core insight as: the trajectory, though dependent, is laced with fresh Gaussian innovations wherever a coordinate has just been refreshed, and those innovations supply the randomness the estimators need. If the paper is right, it closes the gap between the κ⁻² lower bound and achievable single-trajectory recovery.

Core claim

Central claim: a Gaussian graphical model's graph can be recovered exactly from one Glauber trajectory at the optimal κ⁻² signal-strength rate, with no mixing or stationarity assumptions. Earlier local estimators paid κ⁻⁵; earlier κ⁻² estimators waited for mixing. The two algorithms share a dueling-sets search: LS-DuNeS regresses each node's refreshed values on tested coordinates, recovering the graph from about p d²/κ² updates with the conditioning quantity ρ_{2d}(Θ) entering only logarithmically; AU-DuNeS counts alternating i,i,j,i update blocks, needing about p d⁴/κ² updates with no condition-number dependence. Both hold from any initialization — the dependent trajectory is laced with fre

What carries the argument

At the core: whenever a coordinate is refreshed, its new value is a predictable past-measurable part plus a fresh, independent Gaussian innovation. Such fresh-innovation rows or blocks are called 'regenerated,' and they appear often enough to supply the anti-concentration the estimators need. LS-DuNeS uses regenerated rows of the i-trace (the trajectory read when node i updates) to lower-bound the smallest eigenvalue of an empirical regression design; a Lyapunov-style drift bound on the potential xᵀΘx upper-bounds it. AU-DuNeS uses four-tick blocks labeled i,i,j,i, on which the data obey y_b = β_{ij}x_b + ξ_b with independent Gaussian contrast noise; its statistic is the scale-free drop in r

Load-bearing premise

The load-bearing premise is the update structure of Section 3.2, equation (4): every refresh of a node must add an exactly Gaussian innovation, independent of the past and of the update labels — every spectral, drift, and self-normalized bound in the proofs leans on that fresh-noise decomposition, and merely sub-Gaussian or state-dependent noise would break the κ⁻² rate; secondarily, the algorithms take κ and d as exact inputs, a limitation the paper discloses in Section 7.

What would settle it

Simulate random-scan Gaussian Glauber dynamics on a small chain or grid containing a weakest edge of known strength κ, run LS-DuNeS or AU-DuNeS, and measure the trajectory length needed for exact recovery as κ varies: a growth faster than κ⁻² (up to log factors) would falsify the claimed rate. A second targeted check: hold κ fixed while making a 2d-by-2d principal submatrix of the precision matrix nearly singular, so the degree-constrained spectral radius ρ_{2d}(Θ) grows dramatically; LS-DuNeS's required length should grow only logarithmically in it, and AU-DuNeS's should not change — polynomi

Watch this falsifier — get emailed when new claim-graph text bears on it.

If this is right

  • Exact recovery from a single Glauber trajectory is achievable at the κ⁻² rate of the information-theoretic lower bounds, with no mixing-time, stationarity, spectral-gap, or contraction assumptions, from an arbitrary initialization.
  • LS-DuNeS's budget stays essentially linear in the dimension even when the degree-constrained spectral radius ρ_{2d}(Θ) is super-polynomial — Proposition 2 shows that regime is exactly where mixing-based reductions become super-polynomial, while LS-DuNeS pays only a log factor.
  • AU-DuNeS's guarantee carries no condition number at all, so a single trajectory suffices for every positive-definite precision matrix in the model class.
  • The dueling-sets abstraction isolates separation as the one property a local statistic must satisfy, so any future statistic that separates at scale κ inherits the recovery guarantee and the κ⁻² rate for free.
  • The only slack versus the lower bound is an additive log(1/κ) and d² or d⁴ factors coming largely from the search over candidate sets — both identified in the paper as concrete targets for tightening.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Editorial extension: the fresh-innovation principle reads as a transferable design rule — any timestamped, single-coordinate update process with independent refresh noise (asynchronous gossip or opinion-dynamics processes, whose update equations the paper notes are identical) could plausibly inherit the same mixing-free, κ⁻² analysis.
  • The paper leaves parameter-free operation open: its thresholds and the enumeration of size-d sets require exact knowledge of d and κ. A natural extension is an adaptive version that estimates κ from the realized separation gaps; the explicit threshold τ = κ²/128 suggests such gaps are learnable at the κ scale.
  • The d² and d⁴ factors above the per-node lower bound Ω(κ⁻² log p) stem partly from exhaustive candidate enumeration; replacing it with a randomized or greedy duel protocol that still certifies separation could plausibly cut those factors while preserving mixing-freeness and the κ⁻² rate.
  • The search cost O(p^{2d+1}) is polynomial only for constant degree, and the paper explicitly leaves open whether mixing-freeness, κ-optimality, and polynomial time can coexist; the separation abstraction suggests a marginal or convex test as the most direct candidate to check.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

1 major / 2 minor

Summary. This paper studies exact recovery of the conditional-independence graph of a Gaussian graphical model from a single trajectory of random-scan Gaussian Glauber dynamics, started from an arbitrary deterministic state. The authors propose two instantiations of a dueling-neighborhood-search meta-algorithm, LS-DuNeS and AU-DuNeS, and prove finite-sample recovery guarantees of Õ(pd²/κ²) and Õ(pd⁴/κ²) updates, respectively, where κ is the minimum normalized edge strength. The stated contributions are: (i) a deterministic reduction from a uniform separation property of a local statistic to exact recovery (Proposition 1); (ii) a regression-based statistic along node update times, with spectral control of the design via fresh Gaussian innovations and a Lyapunov drift argument (Section 5); and (iii) an alternating-update pattern statistic with self-normalized concentration under a specially constructed filtration (Section 6). The key novelty claimed is optimal κ^{-2} dependence without stationarity, mixing, spectral-gap, or condition-number assumptions.

Significance. If correct, this is a substantive advance: it removes the mixing-time dependence that has been the main bottleneck in prior trajectory-based GGM learning, and it matches the κ^{-2} rate of information-theoretic lower bounds with explicit algorithms. The paper is a pure proof paper: thresholds are derived rather than tuned, constants are explicit, and the dependence on the local conditioning quantity ρ_{2d}(Θ) is only logarithmic in the LS-DuNeS bound. The two-algorithm contrast (logarithmic conditioning vs. no conditioning at the price of d²) gives a clean tradeoff. The machine-checkable-style proof structure with named lemmas and appendix proofs is a strength, as are the explicit budgets and the disclosed limitations in Section 7.

major comments (1)
  1. [Eq. (41)-(42); Appendix B.4] There is a load-bearing mismatch between the printed threshold and the proof. Proposition 12 states τ := κ/(2√λ−m). In the proof, for a true edge the established lower bound is (7/(8√2))κ√λ−m, and the proof asserts this is > τ. This inequality is equivalent to λ−m > 4√2/7 ≈ 0.808. But λ−m = c0 gm/(4m) with c0 = (log 3)/4 and gm ≤ (m−1)/(2q), so λ−m ≤ (log 3)/(32q) ≤ 0.011 for every q ≥ 3. Thus the displayed separation claim (42) does not follow from the proof as written. The proof closes if the intended threshold is τ = (κ/2)√λ−m (radical outside the denominator) and the corresponding non-neighbor bound is stated accordingly. Since this is exactly the step converting separation into recovery, Theorem 1 as stated is not proven without correcting the threshold and re-checking the separation inequalities.
minor comments (2)
  1. [Appendix B.4] The threshold appears both in the proposition statement and in the final display of the proof; please correct the typo consistently and re-express the numerical comparison as 7/(8√2) > 1/2 for the intended threshold τ = (κ/2)√λ−m.
  2. [Algorithm 1] The search over all size-d candidate sets and dueling sets has complexity O(p^{2d+1}), as acknowledged in Section 7. For clarity, the abstract could state that the sample-complexity claims are statistical and do not include the search-order factor; currently the phrase 'updates' might be read as total computation.

Circularity Check

0 steps flagged

No significant circularity: the recovery theorems follow from the Glauber update equations and rate-match independent lower bounds.

full rationale

I walked the derivation chain for both instantiations. The load-bearing statistical facts — Lemma 3 (regression form on the i-trace), Lemma 8 (drift inequality), Lemma 9 (regenerated rows), Lemma 13 (block regression identity), and the filtration in Lemma 23 — are all proved directly from the stated update rule (4): each refreshed coordinate is replaced by the exact conditional Gaussian expectation plus an independent Gaussian innovation. No parameter is fitted from the trajectory to set thresholds or constants; the thresholds τ = (κ/2)√λ−m and τ = κ²/128 are explicit analytic functions of the model parameters appearing in the separation proofs. The claim of κ^{−2} optimality is a rate-matching statement against cited lower bounds; while [43] is a same-group self-citation, [40] is an independent lower bound with the same κ^{−2} scaling, so the benchmark does not reduce to the present work. The DuNeS template intentionally abstracts DICE [32], but that is antecedent algorithm design, not a prediction derived from the target result. The self-citations [42,43] are used in related work and as a comparison baseline, not to justify the main theorems. The disclosed limitations (d and κ as inputs; log(1/κ) gap; computational cost of exhaustive search) are correctness/scope caveats, not signs of circularity. I found no equation whose claimed output is equivalent to its input by construction.

Axiom & Free-Parameter Ledger

6 free parameters · 8 axioms · 0 invented entities

The central claims rest on: (i) the Glauber dynamics model with exact conditional Gaussianity and label-independent innovations (the entire proof architecture); (ii) the model class M(p,d,κ) with the estimator allowed to know (p,d,κ); (iii) standard concentration inequalities and the cited κ^{-2} lower bounds. No parameter is fitted to data; the thresholds, budgets, and constants (τ, c₀, n⋆, m, peeling grid) are derived in the analysis. The one non-standard input is knowledge of κ and d, explicitly disclosed. No invented entities: the 'fresh Gaussian innovation' is a structural fact of the model, not a postulated mediator.

free parameters (6)
  • LS-DuNeS separation threshold τ = (κ/2)·√(λ⁻_m)
    Analysis-derived threshold (Theorem 1, Definition 6); deterministically computable from m, d, κ, but requires exact knowledge of κ, which the model supplies to the estimator (Sec. 3.3). Not fitted to data.
  • AU-DuNeS separation threshold τ = κ²/128
    Placed between the null bound (Φ ≤ 40 log(2en₀/δ)/n₀ ≤ κ²/128) and the signal bound (Φ ≥ κ²/64) in Proposition 14; hand-chosen constant, not fitted to data.
  • Lower-spectral-bound constant c₀ = 1/(4 log 3) = 1/(4 log 3) ≈ 0.183
    Arises from the chord inequality log(1+2v) ≥ v·log 3 in Lemma 11; sets λ⁻_m = c₀g_m/(4m), which fixes the separation margin and the threshold scale.
  • Block budget n⋆ = ⌈(10240/κ²)·log(61440e|T|/(κ²δ))⌉
    Theorem 2 (66): algorithmic budget chosen so every tested triple accumulates enough i-i-j-i blocks; derived from the fixed-triple separation condition and the union bound, not from data.
  • Row budget m = ⌊N/(2p)⌋ and horizon constants in t_m(δ)
    Theorem 1 / eq. (28): the factor 1/2 guarantees every node accumulates m rows within horizon N with high probability (Lemma 6); analysis constants, not data-fitted.
  • Peeling/grid constants (40, 5120, 1/32, dyadic bin structure)
    Lemma 15 and Propositions 12/14: constants inside the dyadic-peeling self-normalized bound and the resulting budgets; all absorbed into universal constants C in the main theorems.
axioms (8)
  • domain assumption Precision Θ ≻ 0 with Θ_ij = 0 iff {i,j} is not an edge, max degree d, min normalized edge strength κ (model class M(p,d,κ))
    Section 3.1, eq. (1)-(3); defines the statistical model and the signal parameter κ used in every threshold.
  • domain assumption Update innovations ε_i^(t) are mutually independent Gaussians with variance σ²_i = Θ^{-1}_ii, independent of the iid uniform update labels
    Section 3.2, eq. (4)-(5); the 'fresh Gaussian innovation' engine behind Lemmas 3, 8, 9, 13, 17, 23. If noise were not exactly Gaussian and fresh, the regenerated-row and self-normalized arguments would fail.
  • domain assumption Update labels I(t) ~ Unif(V) i.i.d.
    Section 3.2; drives all binomial counting (Lemmas 6, 10, 19) and the block-pattern probability q^{-4}.
  • standard math Standard concentration machinery: Laurent-Massart chi-square tails, Chernoff bounds, Abbasi-Yadkori et al. self-normalized martingale bound, Gaussian concentration, epsilon-net covering of the sphere
    Used throughout Appendices B, C, D; all cited (refs [1, 8, 26, 33, 46]) and standard.
  • domain assumption Estimator receives (p, d, κ, δ) as inputs
    Section 3.3 remark and Section 7; thresholds and candidate enumeration need exact κ and d; adaptation explicitly left open.
  • domain assumption Non-degeneracy p ≥ 2d+1 so that size-d dueling sets exist
    Section 4; required by the dueling-set construction.
  • domain assumption Deterministic initialization; LS-DuNeS horizon depends on E₀ = X(0)^TΘX(0) only logarithmically; AU-DuNeS is E₀-free
    Section 3.3 and Theorems 1-2; consistency of the 'arbitrary initialization' claim.
  • standard math κ^{-2} sample complexity is information-theoretically necessary in this setting (lower bounds of [40, 43])
    Section 3.1 footnote 2; the optimality claim is only as strong as these cited lower bounds. [43] is a same-group self-citation, but it is a parameter-free derivation with stated assumptions, treated as independent support per review rules.

pith-pipeline@v1.3.0-alltime-deepseek · 45653 in / 40648 out tokens · 423216 ms · 2026-08-01T15:06:01.666439+00:00 · methodology

0 comments
read the original abstract

Gaussian graphical model selection is usually studied under independent sampling, but in many applications the data arise as a single trajectory of a dependent stochastic process. We study exact recovery of the graph from one trajectory of random-scan Gaussian Glauber dynamics. Existing techniques for this problem either inherit the mixing time of the chain, which can be super-polynomial in the dimension $p$ without strong assumptions, or are suboptimal in the minimum normalized edge strength $\kappa$. We propose two algorithms that are mixing-free and attain the $\kappa^{-2}$ dependence of the information-theoretic lower bounds. Both instantiate a shared dueling-neighborhood search meta-algorithm with a local statistic built directly from the update sequence. The first fits a least-squares regression at the updates of each node and recovers the graph from $\widetilde O(pd^{2}/\kappa^{2})$ updates, where $d$ is the maximum degree. This algorithm's data requirement depends on a local conditioning quantity, but only logarithmically and is provably optimal even when the underlying chain mixes slowly. The second algorithm is based on counting occurences of a specific update pattern and requires $\widetilde O(pd^{4}/\kappa^{2})$ updates, with no dependence on any condition number. The central technical challenge is that both statistics are built from dependent, non-stationary observations. Our analysis tackles this by demonstrating how to extract fresh Gaussian innovations from the update sequence, which yields mixing-free control of appropriate quantities. Neither the algorithms nor their analyses invoke stationarity, a spectral gap, or mixing conditions, and all guarantees hold from an arbitrary initialization.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

53 extracted references · 3 canonical work pages

  1. [1]

    Abbasi-Yadkori, D

    Y. Abbasi-Yadkori, D. Pál, and C. Szepesvári. Improved algorithms for linear stochastic bandits. In Advances in Neural Information Processing Systems, volume 24, 2011

    2011

  2. [2]

    Y. Amit. On rates of convergence of stochastic relaxation for gaussian and non-gaussian distributions. Journal of Multivariate Analysis, 38(1):82–99, 1991

    1991

  3. [3]

    Y. Amit. Convergence properties of the gibbs sampler for perturbations of gaussians.The Annals of Statistics, 24(1):122–140, 1996

    1996

  4. [4]

    Lavenant, andG

    F.Ascolani, H. Lavenant, andG. Zanella. Entropy contraction of theGibbs samplerunder log-concavity. arXiv preprint arXiv:2410.00858, 2024

    arXiv 2024

  5. [5]

    Auletta, D

    V. Auletta, D. Ferraioli, F. Pasquale, and G. Persiano. Metastability of logit dynamics for coordination games.Algorithmica, 80(11):3078–3131, Sept. 2017. ISSN 1432-0541. doi: 10.1007/s00453-017-0371-8. URLhttp://dx.doi.org/10.1007/s00453-017-0371-8

    work page doi:10.1007/s00453-017-0371-8 2017

  6. [6]

    Banerjee, L

    O. Banerjee, L. E. Ghaoui, and A. d’Aspremont. Model selection through sparse maximum likelihood estimation, 2007

    2007

  7. [7]

    Berenbrink, M

    P. Berenbrink, M. Hoefer, D. Kaaser, P. Lenzner, M. Rau, and D. Schmand. Asynchronous opinion dynamics in social networks.Distributed Computing, 2024. doi: 10.1007/s00446-024-00467-3. URL https://doi.org/10.1007/s00446-024-00467-3

    work page doi:10.1007/s00446-024-00467-3 2024

  8. [8]

    Boucheron, G

    S. Boucheron, G. Lugosi, and P. Massart.Concentration Inequalities: A Nonasymptotic Theory of Independence. Oxford University Press, 2013. 23

    2013

  9. [9]

    S. Boyd, A. Ghosh, B. Prabhakar, and D. Shah. Randomized gossip algorithms.IEEE Transactions on Information Theory, 52(6):2508–2530, 2006

    2006

  10. [10]

    Bresler, D

    G. Bresler, D. Gamarnik, and D. Shah. Learning graphical models from the glauber dynamics, 2014

    2014

  11. [11]

    V. H. de la Pena, M. J. Klass, and T. Leung Lai. Self-normalized processes: exponential inequalities, moment bounds and iterated logarithm laws. 2004

    2004

  12. [12]

    M. H. DeGroot. Reaching a consensus.Journal of the American Statistical Association, 69(345): 118–121, 1974. ISSN 01621459, 1537274X. URLhttp://www.jstor.org/stable/2285509

    arXiv 1974

  13. [13]

    L. A. Dennis, Y. Fu, and M. Slavkovik. Markov chain model representation of information diffusion in social networks.Journal of Logic and Computation, 32(6):1195–1211, 03 2022

    2022

  14. [14]

    Drton and M

    M. Drton and M. H. Maathuis. Structure learning in graphical modeling, 2016

    2016

  15. [15]

    A. Dutt, A. Y. Lokhov, M. Vuffray, and S. Misra. Exponential reduction in sample complexity with learning of ising model dynamics, 2021. URLhttps://arxiv.org/abs/2104.00995

    Pith/arXiv arXiv 2021

  16. [16]

    Edwards, G

    D. Edwards, G. C. de Abreu, and R. Labouriau. Selecting high-dimensional mixed graphical models using minimal aic or bic forests.BMC Bioinformatics, 11(1):18, 2010. doi: 10.1186/1471-2105-11-18. URLhttps://doi.org/10.1186/1471-2105-11-18

    work page doi:10.1186/1471-2105-11-18 2010

  17. [17]

    Elboim, Y

    D. Elboim, Y. Peres, and R. Peretz. The asynchronous degroot dynamics, 2024

    2024

  18. [18]

    Thegaussiangraphicalmodelincross-sectional and time-series data, 2016

    S.Epskamp,L.J.Waldorp,R.Mõttus,andD.Borsboom. Thegaussiangraphicalmodelincross-sectional and time-series data, 2016

    2016

  19. [19]

    Friedman, T

    J. Friedman, T. Hastie, and R. Tibshirani. Sparse inverse covariance estimation with the graphical lasso. Biostatistics, 9(3):432–441, 2008

    2008

  20. [20]

    Gaitonde and E

    J. Gaitonde and E. Mossel. A unified approach to learning ising models: Beyond independence and bounded width, 2023. URLhttps://arxiv.org/abs/2311.09197

    Pith/arXiv arXiv 2023

  21. [21]

    Gaitonde, A

    J. Gaitonde, A. Moitra, and E. Mossel. Better models and algorithms for learning ising models from dynamics.arXiv preprint arXiv:2507.15173, 2025

    Pith/arXiv arXiv 2025

  22. [22]

    Gaitonde, A

    J. Gaitonde, A. Moitra, and E. Mossel. Bypassing the noisy parity barrier: Learning higher-order markov random fields from dynamics. InProceedings of the 57th Annual ACM Symposium on Theory of Computing, pages 348–359, 2025

    2025

  23. [23]

    R. A. Horn and C. R. Johnson.Matrix Analysis. Cambridge University Press, 2 edition, 2012

    2012

  24. [24]

    S. R. Howard, A. Ramdas, J. McAuliffe, and J. Sekhon. Time-uniform, nonparametric, nonasymptotic confidence sequences.The Annals of Statistics, 49(2):1055–1080, 2021

    2021

  25. [25]

    C. Lara, E. Massad, L. Fernandez Lopez, and M. Amaku. Analogy between the formulation of ising-glauber model and si epidemiological model.Journal of Applied Mathematics and Physics, 07: 1052–1066, 01 2019. doi: 10.4236/jamp.2019.75071

    arXiv 2019

  26. [26]

    Laurent and P

    B. Laurent and P. Massart. Adaptive estimation of a quadratic functional by model selection.Annals of statistics, pages 1302–1338, 2000

    2000

  27. [27]

    S. L. Lauritzen.Graphical Models. Oxford University Press, 1996. ISBN 0-19-852219-3. 24

    1996

  28. [28]

    W. A. Link and M. J. Eaton. On thinning of chains in mcmc.Methods in ecology and evolution, 3(1): 112–115, 2012

    2012

  29. [29]

    S. N. MacEachern and L. M. Berliner. Subsampling the gibbs sampler.The American Statistician, 48 (3):188–190, 1994

    1994

  30. [30]

    Meinshausen and P

    N. Meinshausen and P. Bühlmann. High-dimensional graphs and variable selection with the lasso. 2006

    2006

  31. [31]

    S. P. Meyn and R. L. Tweedie. Computable bounds for geometric convergence rates of Markov chains. Annals of Applied Probability, 4(4):981–1011, 1994

    1994

  32. [32]

    Misra, M

    S. Misra, M. Vuffray, and A. Y. Lokhov. Information theoretic optimal learning of gaussian graphical models. InConference on Learning Theory, pages 2888–2909. PMLR, 2020

    2020

  33. [33]

    Cambridge university press, 2017

    M.MitzenmacherandE.Upfal.Probabilityandcomputing: Randomizationandprobabilistictechniques in algorithms and data analysis. Cambridge university press, 2017

    2017

  34. [34]

    Montanari and A

    A. Montanari and A. Saberi. The spread of innovations in social networks.Proceedings of the National Academy of Sciences, 107(47):20196–20201, 2010. doi: 10.1073/pnas.1004098107. URL https://www.pnas.org/doi/abs/10.1073/pnas.1004098107

    doi:10.1073/pnas.1004098107 2010

  35. [35]

    A. B. Owen. Statistically efficient thinning of a markov chain sampler.Journal of Computational and Graphical Statistics, 26(3):738–744, 2017

    2017

  36. [36]

    Ravikumar, M

    P. Ravikumar, M. J. Wainwright, G. Raskutti, and B. Yu. High-dimensional covariance estimation by minimizingℓ 1-penalized log-determinant divergence.Electronic Journal of Statistics, 2011

    2011

  37. [37]

    Riabiz, W

    M. Riabiz, W. Y. Chen, J. Cockayne, P. Swietach, S. A. Niederer, L. Mackey, and C. J. Oates. Optimal thinning of mcmc output.Journal of the Royal Statistical Society Series B: Statistical Methodology, 84 (4):1059–1081, 2022

    2022

  38. [38]

    J. S. Rosenthal. Minorization conditions and convergence rates for markov chain monte carlo.Journal of the American Statistical Association, 90(430):558–566, 1995

    1995

  39. [39]

    G. A. F. Seber and A. J. Lee.Linear Regression Analysis. Wiley, Hoboken, NJ, 2 edition, 2003

    2003

  40. [40]

    E. Shen, T. Wu, M. Majid, and A. Moitra. Learning gaussian graphical models from a glauber trajectory without mixing, 2026. URLhttps://arxiv.org/abs/2606.31230

    Pith/arXiv arXiv 2026

  41. [41]

    Simchowitz, H

    M. Simchowitz, H. Mania, S. Tu, M. I. Jordan, and B. Recht. Learning without mixing: Towards a sharp analysis of linear system identification. InProceedings of the 31st Conference on Learning Theory, pages 439–473, 2018

    2018

  42. [42]

    Tirukkonda, A

    V. Tirukkonda, A. Rayas, and G. Dasarathy. Structure learning in gaussian graphical models from glauber dynamics. In2025 IEEE International Symposium on Information Theory (ISIT), pages 1–6. IEEE, 2025

    2025

  43. [43]

    Tirukkonda, A

    V. Tirukkonda, A. Rayas, and G. Dasarathy. Local and mixing-based algorithms for gaussian graphical model selection from glauber dynamics, 2026. URLhttps://arxiv.org/abs/2412.18594

    Pith/arXiv arXiv 2026

  44. [44]

    Statisticallearningtheoryforcontrol: Afinite-sample perspective.IEEE Control Systems Magazine, 43(6):67–97, 2023

    A.Tsiamis,I.Ziemann,N.Matni,andG.J.Pappas. Statisticallearningtheoryforcontrol: Afinite-sample perspective.IEEE Control Systems Magazine, 43(6):67–97, 2023. 25

    2023

  45. [45]

    S. A. van de Geer.Empirical Processes in M-Estimation. Cambridge University Press, Cambridge, 2000

    2000

  46. [46]

    Vershynin.High-Dimensional Probability: An Introduction with Applications in Data Science

    R. Vershynin.High-Dimensional Probability: An Introduction with Applications in Data Science. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2018

    2018

  47. [47]

    N. S. Wadia. A mixing time bound for Gibbs sampling from log-smooth log-concave distributions. arXiv preprint arXiv:2412.17899, 2024

    Pith/arXiv arXiv 2024

  48. [48]

    N.-Y. Wang. Convergence rates of the random scan gibbs sampler under the dobrushin’s uniqueness condition. 2017

    2017

  49. [49]

    Wang and L

    N.-Y. Wang and L. Wu. Convergence rate and concentration inequalities for gibbs sampling in high dimension. 2014

    2014

  50. [50]

    W. Wang, M. J. Wainwright, and K. Ramchandran. Information-theoretic bounds on model selection for gaussian markov random fields. In2010 IEEE International Symposium on Information Theory, pages 1373–1377. IEEE, 2010

    2010

  51. [51]

    Yuan and Y

    M. Yuan and Y. Lin. Model selection and estimation in the Gaussian graphical model.Biometrika, 94 (1):19–35, 03 2007. ISSN 0006-3444. doi: 10.1093/biomet/asm018. URLhttps://doi.org/10. 1093/biomet/asm018

    doi:10.1093/biomet/asm018 2007

  52. [52]

    enough randomness

    N.Zhan,Y.Sun,A.Jakhar,andH.Liu. Graphicalmodelsforfinancialtimeseriesandportfolioselection, 2021. 26 Appendices A Proof of Proposition 1 WeprovethedeterministicrecoveryguaranteeforDuNeSstatedinProposition1. Foreachnode i,availability and separation give an accepted candidate containingSi, rule out candidates that omit a neighbor, and ensure that cleanup f...

    2021

  53. [53]

    In particular, |λ∗|= S2 2σ2 iV ≤ R 2σ2 i √ V .(103) Thefixed-λidentitycanonlybeappliedtovalueschosenbeforeobserving ξ,sowereplacetherandomchoice λ∗ by a finite deterministic net

    Now, on the eventE, the random maximizerλ∗ lies in a bounded interval, but its location still depends on the data. In particular, |λ∗|= S2 2σ2 iV ≤ R 2σ2 i √ V .(103) Thefixed-λidentitycanonlybeappliedtovalueschosenbeforeobserving ξ,sowereplacetherandomchoice λ∗ by a finite deterministic net. The net is constructed separately on dyadic ranges ofV such tha...

    2000