{"id":"5ff41d8d-66a1-4166-b867-cf7f5e4013c8","arxiv_id":"2507.15173","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"First algorithms recover Ising structure and parameters from flip-only dynamics trajectories, in time poly(d)n^2 log n for structure and O~(2^d n) for parameters.","lead":"This paper gives the first algorithms that learn an Ising model, its dependency graph and its interaction strengths, from a trajectory where you only see configuration changes, not the hidden update attempts. It resolves an open problem from 2018 and matches the sample complexity of the easier setting where all update attempts are visible.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Assumption 2's stability condition is the load-bearing bridge for the claimed generalization to all reversible single-site chains, and it is verified only for Glauber and Metropolis; the main Glauber structure-learning result itself is not threatened.","rationale":"The reader's weakest-assumption analysis identifies the same load-bearing concern: Assumption 2, especially the stability condition, is the point where the paper's most general claim rests on a regularity property that is verified for only two specific chains. I agree that this is the soft spot. The main Glauber-dynamics structure learning result is supported by a detailed proof and Proposition 3.14 supplies the needed stability parameters, so the central open-problem resolution is not invalidated. The concern is about overclaiming the breadth of the framework, not about an internal contradiction in the Glauber analysis. A concrete test that exhibits a natural site-consistent chain violating stability, or verifies stability for a third standard chain, would settle whether the generality claim is substantive or merely a definitional artifact. No code or machine-checked proofs are provided, so a conditional verdict with moderate confidence remains appropriate.","tokens_in":41750,"tokens_out":35622,"duration_ms":383081,"concrete_test":"Instantiate a reversible single-site chain with a site-consistent monotone proposal f_0(z)=min(1,z^2) (or a smoothed step function) and compute g_0(z)=f_0(z)^2/z over z∈[exp(-2λ), exp(2λ)]. For α=α0, check whether there exists z far from z* with |g_0(z)-g_0(e^α z)|≤δ for the δ0 claimed in Definition 3.10; if so, simulate Algorithm 1's cycle statistic on a 3-vertex path Ising model under this chain and measure the empirical gap between E[Z^{ij}_t|F_{t-1}] and the non-edge upper bound. If the gap closes, the claimed 'any single-site chain' generality fails.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Assumption 2's stability condition (Definition 3.10) is the load-bearing bridge between the cycle statistic and edge/non-edge separation. Corollary 5.5's lower bound requires that for every edge (i,j) with i having another neighbor k, the local function g_i(z)=f_i(z)^2/z has a unique z*(α) and that approximate level sets |g_i(z)-g_i(e^α z)|≤δ imply z is within η(δ) of z*. This is what turns anticoncentration of the linear field into a positive expectation for Z^{ij}_t. The paper verifies this only for Glauber (Prop 3.14) and site-homogeneous Metropolis (Prop 3.16). For the advertised 'broader class of reversible single-site chains', the condition is an abstract postulate. A reversible site-consistent chain whose f_i is, e.g., a steep monotone step or a non-unimodal g_i could have g_i(z)≈g_i(e^α z) at z values far from z*, making the cycle statistic unable to separate edges from non-edges and invalidating Theorem 5.6's generality. The main Glauber result itself is not threatened because Prop 3.14 supplies the needed δ0,η.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the problem of learning an Ising model from a continuous-time Glauber dynamics trajectory in which only actual spin flips are observed, and failed update attempts are not. The main advertised contributions are: (i) a structure-learning algorithm that recovers the dependence graph with O(poly(d) n^2 log n) runtime under Assumption 1, (ii) a parameter-learning algorithm that recovers the interaction matrix A to epsilon accuracy in O~(2^d n) time once the graph is known, (iii) the same guarantees for a broader class of reversible single-site chains, notably Metropolis dynamics, under Assumption 2. The technical machinery includes a degree-8 short-window flip-cycle statistic, anticoncentration estimates for linear forms under the dynamics, a matching-recovery step using spin-spin correlations, and local flip-rate estimation based on reversibility. The paper is self-contained for most of the Glauber structure-learning and interaction-matrix parameter estimation, but two load-bearing parts need attention: the proof of Corollary 5.5 contains an algebraic reduction that appears incorrect, and the recovery of the external fields h is only sketched in a remark.","tokens_in":1655,"tokens_out":1834,"duration_ms":265716,"significance":"If the results are correct, this is a substantial advance over a line of work dating back to Bresler, Gamarnik, and Shah: it removes the strong observability assumption that all site-update attempts are known, which has been considered essential in prior dynamical learning algorithms. The claimed n-dependence matches state-of-the-art guarantees in the i.i.d. setting, and the extension to Metropolis dynamics is a useful robustness property. The paper also contains a careful and largely self-contained development of the short-window flip expansion (Proposition 5.1), the anticoncentration lemma (Corollary 4.5), and the interaction-matrix estimation theorem (Theorem 6.5). The significance is therefore high, but it is conditional on repairing the proof of the dense-edge detection step and on supplying a real proof for the h-recovery claim, since both are advertised as main results.","major_comments":[{"comment":"The reduction to the stability condition is algebraically incorrect, and as written the lower bound (24) does not follow. Let r0 = exp(2*Aik*X^t_k summed over k not equal to i, plus 2*h_i) and r1 = exp(2*Aik*X^t_k summed over k not equal to i,j, minus 2*Aij*X^t_j, plus 2*h_i) be the two ratios in Proposition 5.3. Their product is r0*r1 = exp(4 times the sum over k not equal to i,j of Aik*X^t_k plus 4*h_i), so the j-th term cancels. For Glauber-type g, the near-equality |g(r0) - g(r1)| <= delta is therefore the condition that the sum over k not equal to i,j of Aik*X^t_k is close to -h_i. It is not equivalent to the claimed statement that z := exp(2 times the sum over k not equal to i of Aik*X^t_k plus 2*h_i minus 2*|Aij|) is close to z*(4*|Aij|). Consequently Eq. (27) has the wrong center: it contains plus 2*|Aij|, while the correct center is -h_i. The subsequent anticoncentration event E_a with a = -2*h_i + 2*|Aij| does not rule out the dangerous near-equality; the dangerous event can occur on E_a, so Corollary 5.5 is not established as written. Since Theorem 5.6 and the main structure-learning claim depend on Corollary 5.5, this is a load-bearing gap. The claim appears repairable by taking a = -h_i and applying stability to y = min(r0, r1), but the current proof needs a corrected derivation.","section":"Section 5.2, Corollary 5.5 (Eqs. (26)-(27))"},{"comment":"The abstract and Theorem 1.2 advertise recovery of both A and h to epsilon accuracy, but the formal parameter-learning theorem (Theorem 6.5) only controls the interaction matrix A. The recovery of h is delegated to Remark 1, which contains a one-line sketch and closes with \"We leave the details to the interested reader.\" This is not a proof of the advertised h-recovery claim, and no runtime or high-probability guarantee is given for the fields. Since the external-field recovery is explicitly part of the main results, this gap must be fixed either by supplying a complete proof with the same level of detail as Theorem 6.5 or by explicitly rescoping the main claims to interaction-matrix recovery.","section":"Section 6.2, Theorem 1.2 and Remark 1"}],"minor_comments":[{"comment":"The advertised generality to a broader class of reversible, single-site chains is entirely conditional on the (lambda, alpha0, delta0, eta)-stability condition, which is verified only for Glauber dynamics and site-homogeneous Metropolis dynamics in Propositions 3.14 and 3.16. This is not a flaw in the conditional theorems, but the introduction and abstract should state more precisely that the algorithms are designed for chains satisfying Assumption 2 and that the condition is verified for two specific families; otherwise the reader may infer a broader verified theory.","section":"Section 3.3, Assumption 2 and Definition 3.10"},{"comment":"The definition of the linear form in the proof of Corollary 5.5, written as the sum over ell not equal to i,j of A_{i,ell} x_k, uses ell both as a summation index and as the name of the function while also introducing k as an apparently free index; this should be rewritten with a single clear dummy variable, such as the sum over r not equal to i,j of A_{i,r} x_r.","section":"Section 5.2, Corollary 5.5"},{"comment":"The notation O-tilde and e-O is used without a unified definition; the abstract states O-tilde(2^d n) for parameter learning while Theorem 6.5 states e-O(exp(O(gamma lambda)) 2^d log(1/beta) / delta^4 kappa^8), and the relationship between the two expressions is not explained. The authors should define both notations once and use them consistently.","section":"Throughout"}],"recommendation":"major_revision","confidential_remarks":"The paper is high-quality and the main ideas are promising; the dense-edge detection step is very likely repairable by a corrected anticoncentration argument. I recommend major revision rather than rejection. The two load-bearing issues are the flawed reduction in Corollary 5.5, which supports the main structure-learning theorem, and the missing proof of h recovery. The narrow verification of Assumption 2 is a scope concern, not a correctness issue, and can be addressed in the presentation. If the authors repair the corollary and either prove or rescope the h claim, the paper could be acceptable for a top venue."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Jason, here's the read on arXiv:2507.15173.\n\nThe headline: this is the first real resolution of the flip-only observation problem for learning Ising models from Glauber dynamics, and the main structure-learning theorem is solid. The paper does what it claims for Glauber: recovering the graph in poly(d) n^2 log n sample/runtime from a trajectory where only configuration changes are visible, then parameters in ~O(2^d n poly(1/eps)). The degree-8 cycle statistic is a genuine new construction, and the use of pathwise Freedman concentration to handle unobserved failed updates is clever and appears to work. The matching-recovery step via time-averaged spin-spin correlations is clean. I checked the key separation argument (Corollaries 5.4 and 5.5): the Glauber case is proven, not just asserted, and the anticoncentration input (Corollary 4.5) is derived from a substantial local-stability lemma (Proposition 4.1). No circularity, no fitted parameters. This deserves a serious referee.\n\nWhere I'd push back, gently: the reader's conditional verdict is about the right size. Two soft spots, neither fatal to the main result.\n\nFirst, the abstract and Theorem 1.2 promise recovery of the external fields h, but the proof is Remark 1: \"We leave the details to the interested reader.\" That's a genuine gap between claim and demonstration. It looks fillable—you have multiplicative estimates of Pi ratios, so the displayed equation for h should follow with the Aij estimates at 1/d accuracy—but the paper should actually write it out before publication. Right now the theorem statement overclaims.\n\nSecond, the generality to \"any reversible single-site chain\" is carried by Assumption 2's stability condition (Definition 3.10), verified only for Glauber and site-homogeneous Metropolis. The stress-test note is correct that Corollary 5.5's separation depends on that stability being more than a postulate. That doesn't threaten the Glauber theorem, which is the main advertised result, but the title's \"Better Models\" should be read as a proposal, not a proved universal statement. The authors are reasonably careful in the text; the abstract's \"broader class\" is fair if you read the fine print.\n\nMinor: no code, and the proofs are long enough that I'd want either a full writeup of a nontrivial case or a formalization of the key concentration step. Not a blocker.\n\nNet: the paper is a real advance, the main theorem is well-supported, and the soft spots are presentation and scope, not load-bearing errors. I'd send it to a strong referee, with the caveat that the h-recovery gap and the stability assumption need explicit attention in the revision.\n\nRecommendation: engage with it.","headline":"First real resolution of flip-only observation for learning Ising models from dynamics; main structure-learning theorem is solid, with a fillable gap in the claimed external-field recovery and a broader-generality condition that is verified only for two chains.","tokens_in":42539,"tokens_out":1751,"would_cite":true,"duration_ms":19644,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["62H30","60J20","68W27"],"pacs":[],"model":"deepseek-v4-flash","headline":"Learning Ising models from observed flips alone, with no access to failed update attempts, is possible in near-optimal time.","keywords":["Ising model","learning from dynamics","flip-only observation","Glauber dynamics","Metropolis dynamics","structure learning","parameter estimation"],"falsifier":"Take a reversible single-site chain on a 2-site Ising model that is consistent but not stable, check whether the difference $g_i(z) - g_i(\\exp(\\alpha)z)$ stays below the stated threshold for $z$ near $z^*$ while $|z - z^*|$ is large; if so, the cycle statistic's separation bound fails.","tokens_in":41550,"feed_emoji":"📉","tokens_out":1551,"duration_ms":21523,"temperature":0.7,"pith_summary":"The paper establishes that an Ising model can be learned from the bare trajectory of its Glauber dynamics, observing only the times when a spin actually flips, without any record of update attempts that left the configuration unchanged. Prior algorithms for learning from dynamics all relied on knowing every update attempt, including non-flips; this paper removes that requirement, which is the natural observation model for most real processes. It recovers the dependence graph in time $\\mathrm{poly}(d)\\cdot n^2\\log n$ and the parameters in additional $\\tilde{O}(2^d n)$ time, matching the qualitative complexity of state-of-the-art i.i.d. algorithms. The results extend to any reversible single-site chain satisfying a stability condition, including Metropolis dynamics.","feed_headline":"Learning Ising models from mere flip trajectories","feed_subtitle":"New algorithms need no hidden update clocks, only observed spin changes, and match prior sample complexity.","key_machinery":"The central object is the flip-cycle statistic $Z^{i,j}_t = \\mathbf{1}_{iijjiijj} - 2\\mathbf{1}_{iijjjiij} + \\mathbf{1}_{jiijjiij}$, evaluated on short windows of length $8\\varepsilon$. Its conditional expectation is approximately a squared difference of products of transition rates of the form $g_i(\\pi(X^{t,i\\to+1})/\\pi(X^{t,i\\to-1})) - g_i(\\pi(X^{t,\\oplus j,i\\to+1})/\\pi(X^{t,\\oplus j,i\\to-1}))$, where $g_i$ encodes the reversible transition kernel. A small-window expansion (Proposition 5.1) shows the probability of any bounded flip sequence factorizes into a product of flip rates up to $O(d\\varepsilon)$ error, and a dynamical anticoncentration result guarantees that linear forms in the dynamics deviate noticeably from any fixed value with constant probability. Together these force the statistic to separate edges from non-edges except for isolated matching edges.","core_discovery":"The paper claims that the structure and parameters of an Ising model of maximum degree $d$ can be learned with high probability from the flip-only trajectory $(X_t)_{t=0}^T$, provided the model satisfies standard non-degeneracy bounds (degree $d$, width $\\lambda$, edge magnitude at least $\\alpha$). Structure learning runs in time $\\mathrm{poly}(d)\\,n^2\\log n$ and parameter learning in additional $\\tilde{O}(2^d n)$ time. The key mechanism is a degree-8 flip-cycle statistic $Z^{i,j}_t$ built from short alternating flip sequences; conditional on the past history, its expectation is provably separated between edges that lie in a connected component of average degree greater than 1 and non-edges. The remaining edges form a matching, which is recovered by estimating spin-spin correlations in the resulting product chain. Parameters are then recovered from estimated single-site flip rates along a small subcube, using reversibility to convert ratios of flip rates into edge weights.","pith_inferences":["The flip-cycle statistic likely tests a more general principle: local correlations in a trajectory are detectable from transition events alone even when the underlying update attempts are hidden, provided the observation window is short enough that the dominant path is the intended one.","The abstract stability condition in Assumption 2 may be verified for additional chains such as Barker dynamics or other reversible single-site kernels with monotone transition functions, expanding the algorithmic reach beyond the two examples given.","A natural testable extension is to ask whether the matching-recovery step can be replaced by a flip-only statistic as well, avoiding the need for time-averaged spin-spin correlation estimates.","The parameter learning guarantee should degrade gracefully when edge magnitudes are only lower bounded by $\\alpha$; one could test empirically whether the $\\tilde{O}(2^d)$ factor is actually necessary in practice on sparse graphs."],"forward_implications":["Observing only configuration changes is sufficient for learning, so physical or network processes can be used as data without tracking hidden update attempts.","The runtime and sample complexity match the state-of-the-art i.i.d. learning results, despite the far weaker observation model.","The approach succeeds for a general class of reversible single-site chains, not just Glauber dynamics, whenever the stability condition holds.","Parameter recovery inherits the same $\\tilde{O}(2^d n)$ dependence, suggesting that the exponential-in-degree factor is intrinsic to subcube-based rate estimation rather than to the observation model.","Once the graph is known, the algorithm's parameter estimates achieve $\\varepsilon$-accuracy in $\\tilde{O}(2^d n \\,\\mathrm{poly}(1/\\varepsilon))$ time with high probability."],"supporting_citations":[{"why":"Pioneering work on learning from Glauber dynamics under strong observability; supplies the localization idea and the observation model this paper replaces.","marker":"[BGS18]"},{"why":"Provides the unified i.i.d. and dynamics learning framework whose parameter learning approach is adapted here.","marker":"[GM24]"},{"why":"Introduces the dependent method of moments and the squaring trick that the cycle statistic $Z^{i,j}_t$ generalizes.","marker":"[GMM25]"},{"why":"Establishes the i.i.d. sample complexity baseline that the new algorithm qualitatively matches in the weaker observation model.","marker":"[KM17]"},{"why":"Supplies the Chernoff-type concentration inequality for reversible Markov chains used to estimate spin-spin correlations in the matching step.","marker":"[Lez01]"},{"why":"Provides the pathwise Freedman martingale inequality used to control the parameter estimators simultaneously.","marker":"[BDH+08]"}],"fun_headline_variants":["Learn Ising models without hidden clocks","Ising structure from flip-only traces","Flip-only trajectories reveal Ising graphs","Efficient Ising learning from sparse spin flips","First efficient Ising recovery from flips alone"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"For the general class of chains beyond Glauber and Metropolis, the abstract stability condition in Assumption 2 is a postulate rather than a verified property; if a natural reversible single-site chain violates it, the cycle statistic can no longer separate edges from non-edges.","fun_headline_variants_meta":{"raw":{"variants":["Learn Ising models without hidden clocks","Ising structure from flip-only traces","Flip-only trajectories reveal Ising graphs","Efficient Ising learning from sparse spin flips","First efficient Ising recovery from flips alone"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00023,"raw_usage":{"total_tokens":1558,"prompt_tokens":1100,"completion_tokens":458,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":716,"completion_tokens_details":{"reasoning_tokens":392}},"tokens_in":716,"tokens_out":458,"duration_ms":5295,"temperature":1.0,"reasoning_tokens":392,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T15:38:50.665065+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a reversible single-site chain on a 2-site Ising model that is consistent but not stable, check whether the difference $g_i(z) - g_i(\\exp(\\alpha)z)$ stays below the stated threshold for $z$ near $z^*$ while $|z - z^*|$ is large; if so, the cycle statistic's separation bound fails.","supporting_citations":[],"review_version":1}