{"id":"b6d61d85-023e-4f1d-b97b-e684d01ffc78","arxiv_id":"2411.11174","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A simple subgaussian argument lets the Sparsitron algorithm recover SK model parameters in polynomial time for all beta <= sqrt(log n), breaking the beta=1 barrier.","lead":"This paper shows that the parameters of the Sherrington-Kirkpatrick spin glass can be learned in polynomial time even at low temperature, beyond the beta=1 phase transition where previous methods failed. The proof uses a simple subgaussian concentration bound on local fields instead of heavy covariance machinery.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 3.4 bounds the tail of |Ai·X+hiXi|, but Theorem 3.2 requires the same tail for |Ai·X+hi|; the paper never bridges these, leaving the external-field recovery step unjustified even for β>1, though a triangle-inequality repair appears available.","rationale":"The reader's verdict of CONDITIONAL is appropriate: the core Sparsitron-based argument and the low-temperature regime β>1 appear sound, and the identified gaps are repairable rather than fatal. I agree with the reader that Lemma 3.3's subgaussian normalization has a small-β error. My stress-test adds that the proof has a second, more directly load-bearing gap: Lemma 3.4's tail is for |A_i·X+h_iX_i|, while the invoked Theorem 3.2 needs |A_i·X+h_i|; without a bridge, the external-field recovery claim does not follow from the stated lemmas even for β>1. The bridge is easy (triangle inequality plus Gaussian tail on h_i), so I do not move to REJECT; the paper should either state Lemma 3.4 with h_i or add the bridge explicitly. No machine-checked proof exists, but the elementary, parameter-free structure and the fact that the flaw is localized to a restatement and a factor support conditional acceptance. The concrete test above settles whether the fix is as simple as expected.","tokens_in":27499,"tokens_out":25809,"duration_ms":237120,"concrete_test":"Re-derive the step from Lemma 3.4 to Theorem 3.2 with the corrected quantity |A_i·X+h_i| throughout: (i) re-prove the exponential moment bound E_X exp(|A_i·X+h_i|²/(Bβ²)) for β≥1 using the same Cauchy-Schwarz argument with h_i not multiplied by X_i; (ii) check whether the Markov tail yields Pr(|A_i·X+h_i|>C)≤1/n with C=O(β²+β√log n). If both go through, restate Lemma 3.4 with h_i and the proof is repaired; if (ii) requires adding O(√log n) to C, the theorem's sample complexity for β<1 must be weakened, while for β≥1 it remains unchanged.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Section 3.3's main reduction is incomplete as written. Theorem 3.5 applies [GM24, Thm 3.2], whose condition (2) is Pr_{X∼D_{A,h}}[|A_i·X+h_i|≤C]≥3/4. What Lemma 3.4 actually proves is Pr[|A_i·X+h_iX_i|≤C]≥1−1/n with C=O(β²+β√log n). Because X_i modulates h_i, the event in Lemma 3.4 is not the event required: for a fixed non-zero h_i, configurations with |A_i·X+h_i|>C can satisfy |A_i·X+h_iX_i|≤C (e.g., when X_i has the sign that cancels h_i). The proof of Theorem 3.5 does not supply the missing step. One can repair it by observing |A_i·X+h_i|≤|A_i·X+h_iX_i|+2|h_i| and using the Gaussian tail |h_i|≤O(√log n), which gives C'=C+O(√log n)=O(C) for all β≥1; for β<1 the needed C' becomes O(√log n), changing the stated exponent. This is a genuine gap in the logical chain, not a numerical constant issue; it affects the advertised external-field recovery in Theorem 3.7. A separate boundary error in Lemma 3.3 is the claim that A_i·x+h_i is O(β)-subgaussian: h_i∼N(0,1) makes the constant O(max(β,1)), so the denominator Bβ² is invalid for small β. In the low-temperature regime β≥1 this secondary issue is harmless.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies parameter recovery for Ising models and higher-order Markov random fields with random coefficients. It proves that Sparsitron, run with N = exp(O(β² + β√log n)) · poly(n, 1/ε) samples, recovers the interaction matrix and external field of the Sherrington-Kirkpatrick model to accuracy ε in infinity norm (with a factor n for the external field) with probability 1 − O(1/n) over the random parameter draw. This covers β ≤ √log n, including the low-temperature regime β ≥ 1 where covariance-based arguments provably fail. The proof bounds tails of local fields via a partition-function decoupling argument and subgaussian concentration, then applies the Gaitonde-Mossel reduction. The paper also extends the approach to random MRFs on arbitrary bounded-degree graphs and to pure p-spin models, with exact recovery in the Rademacher case.","tokens_in":27874,"tokens_out":10069,"duration_ms":96655,"significance":"If the central argument is repaired, this is a substantial advance: it gives the first polynomial-time parameter recovery for the SK model past β = 1, with a proof that avoids the covariance-operator bounds and functional inequalities used in prior work. The extension to p-spin models and random MRFs on arbitrary graphs is also novel, as is the sub-polynomial exact recovery for Rademacher weights. The proof strategy is simple and appears to be correct in its main mechanism. I found no circularity, and the use of the KM17 and GM24 results as black boxes is appropriate. The technical gaps identified below are local and repairable, and for the headline low-temperature regime β ≥ 1 the indicated repair does not change the stated exponents.","major_comments":[{"comment":"Lemma 3.4 proves a tail bound on |A_i·X + h_i X_i|, but Theorem 3.2, which is the reduction invoked in the proof of Theorem 3.5, requires condition (2) to hold for |A_i·X + h_i|. These are not the same event: for a fixed nonzero h_i, a configuration with |A_i·X + h_i| > C can satisfy |A_i·X + h_i X_i| ≤ C when X_i has the sign that cancels h_i. The proof of Theorem 3.5 does not supply the missing step. A repair is available via |A_i·X + h_i| ≤ |A_i·X + h_i X_i| + 2|h_i| and the Gaussian tail |h_i| ≤ O(√log n), which yields C' = O(β² + β√log n) for β ≥ 1 but C' = O(√log n) for small β. The external-field recovery in Theorem 3.7 and the uniform-in-β sample complexity in Theorems 3.5 and 1.1 are therefore not established as written.","section":"Section 3.3, Lemmas 3.3–3.4 and Theorem 3.5"},{"comment":"The proof claims that A_i·x + h_i is O(β)-subgaussian because h_i is O(1)-subgaussian. Since h_i ∼ N(0,1), the sum has variance β² + 1 and subgaussian constant Θ(max(β,1)), not Θ(β). Consequently the normalization Bβ² in Eq. (4) is invalid for β below a constant: already the h_i term alone gives E exp(h_i²/(Bβ²)) = ∞ for sufficiently small β, contradicting the claimed finite expectation. Replacing the denominator by B(β² + 1) repairs Lemma 3.3 but propagates to Lemma 3.4, changing the tail constant from O(β² + β√log n) to O(β² + 1 + √log n) for small β.","section":"Section 3.3, Lemma 3.3"}],"minor_comments":[{"comment":"The informal Theorem 1.1 states ‖h − ĥ‖∞ ≤ ε, whereas the formal Theorem 3.7 proves only ‖h − ĥ‖∞ ≤ nε. Please align the informal and formal statements, or track the extra n factor explicitly.","section":"Theorem 1.1 vs. Theorem 3.7"},{"comment":"The sentence introducing total variation distance says 'The KL-divergence between P and Q is defined as' but the displayed formula is the total variation distance; this should be corrected.","section":"Definition B.2"},{"comment":"The displayed sample complexity is O(β² n log n log(n/δε)/ε⁴), but substituting λ = O(β√n log n) into Theorem 3.1 gives an additional log n factor; please reconcile the exponents.","section":"Theorem 3.7"},{"comment":"The parameter γ = √(βt + σ²) appears to contain a typo; the variance of the local field suggests γ should be of order √(β² + σ²) or the intended rescaling should be stated explicitly.","section":"Remark 3.10"}],"recommendation":"major_revision","confidential_remarks":"The two main gaps are in the proof of the external-field condition for Theorem 3.2 and in the subgaussian normalization for small β. Both appear repairable without changing the low-temperature result, so I do not see grounds for rejection. The informal Theorem 1.1 overstates the field-recovery accuracy relative to Theorem 3.7 and should be corrected. The authors should also double-check the exact statement of GM24's Theorem 3.2 to ensure that the version quoted in the text is the one being applied."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Here's my read on 2411.11174.\n\nThe headline is right: this breaks the β=1 barrier for learning the SK model. The key idea is that you don't need the covariance operator of the Gibbs measure to be bounded; you only need concentration of X along the row directions A_i. Since the rows are subgaussian, a first-moment calculation over A,h gives E_X exp(|A_i·X + h_iX_i|^2/Bβ²) ≤ n² exp(O(β²)) w.h.p., which yields a tail bound with C = O(β²+β√log n). That is a genuinely new and simple route, and it avoids the heavy machinery in GM24. The extensions to random MRFs on arbitrary graphs and to pure p-spin models are real, and they address an open problem from GM24.\n\nThe soft spots are concentrated in Section 3.3. The tail bound that Lemma 3.4 actually proves is for |A_i·X + h_iX_i|, but GM24's Theorem 3.2 (restated here) needs the same tail for |A_i·X + h_i|. Those are not the same event; X_i can cancel h_i in one but not the other. Theorem 3.5 just applies GM24 with C from Lemma 3.4, so the external-field recovery step is missing an argument. This is a genuine gap, but it is repairable: |A_i·X + h_i| ≤ |A_i·X + h_iX_i| + 2|h_i|, and |h_i| ≤ O(√log n) w.h.p., so for β ≥ 1 the new C is still O(β²+β√log n). The main theorem survives with a one-page fix. The paper does not supply that fix, so a referee should demand it.\n\nSecond, the proof assumes A_i·x + h_i is O(β)-subgaussian. With h_i ~ N(0,1), the constant is O(max(β,1)). So the Bβ² normalization is invalid for small β. This is a boundary error; it doesn't touch the advertised β≥1 regime, and for very small β the prior high-temperature bounds are strictly better anyway.\n\nThe paper is otherwise careful, and the citation pattern is fine: GM24, KM17, and the spin-glass literature are handled honestly. Self-citation is not an issue because KM17 is used as a black box.\n\nI'd send this to review. It's a significant claim with a proof that is close to correct; the fixes are mechanical. A serious referee will likely return conditional acceptance. The result is true.","headline":"Breaking the β=1 barrier for learning the SK model is a real advance, but the paper as written has a repairable gap: the tail bound is proven for |A_i·X+h_iX_i| while the reduction needs |A_i·X+h_i|, and the external-field step is missing a bridge that a triangle inequality can fix.","tokens_in":28429,"tokens_out":12491,"would_cite":true,"duration_ms":163752,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q32","82B44"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper claims SK spin-glass parameters are recoverable in polynomial time for every beta up to sqrt(log n), crossing the beta=1 phase transition.","keywords":["Sherrington-Kirkpatrick model","Ising model learning","parameter recovery","Sparsitron","multiplicative weights","subgaussian concentration","low-temperature phase","random Markov random fields"],"falsifier":"Run the claimed tail bound on finite SK instances: draw $D_{A,h}\\sim SK(\\beta)$ with $\\beta=0.1$ and $n=1000$, sample $X$ from the model, and estimate $\\Pr[|A_i\\cdot X+h_iX_i| > C(\\beta^2+\\beta\\sqrt{\\log n})]$ for the constant $C$ in the $O(\\cdot)$. If this probability is not below $1/n$ for every row, Lemma 3.4 fails as stated and the small-$\\beta$ case would need a corrected proof. A complementary experiment at $\\beta=1.5$ with the claimed $\\exp(O(\\beta^2))\\,\\mathrm{poly}(n)$ samples would test the main theorem directly.","tokens_in":27276,"feed_emoji":"🎲","tokens_out":16552,"duration_ms":271729,"temperature":0.7,"pith_summary":"The paper sets out to show that the Sherrington-Kirkpatrick (SK) model—an Ising model with iid Gaussian couplings scaled by $\\beta/\\sqrt{n}$—can be learned from samples even in the low-temperature phase $\\beta\\ge 1$, where earlier algorithms and the statistical-physics tools behind them stop working. It claims that running the Sparsitron multiplicative-weights algorithm coordinate by coordinate recovers the interaction matrix to entrywise accuracy $\\epsilon$ and the external field to accuracy $n\\epsilon$ using $N=\\exp(O(\\beta^2+\\beta\\sqrt{\\log n}))\\,\\mathrm{poly}(n,1/\\epsilon)$ samples and $O(n^2N)$ time; for $\\beta\\le\\sqrt{\\log n}$ this is polynomial time. If the claim is correct, the phase transition at $\\beta=1$ is not a computational barrier for parameter recovery: the same simple algorithm works on both sides. The argument extends to random Ising models on arbitrary graphs and to higher-order random Markov random fields, where even high-temperature guarantees were previously open.","feed_headline":"Polynomial-time learner crosses the beta=1 spin-glass barrier","feed_subtitle":"A multiplicative-weights algorithm recovers SK couplings in exp(beta^2) samples, even in the low-temperature phase.","key_machinery":"Two ingredients carry the argument. The first is Sparsitron, a multiplicative-weights algorithm that learns a sigmoid function from labeled samples; the earlier reduction of parameter recovery to a squared-loss guarantee for this sigmoid is reused without change. The second is a new concentration lemma: the local field $A_i\\cdot X+h_iX_i$, with $X$ drawn from the Gibbs measure, is subgaussian at scale $O(\\beta)$ uniformly in $i$, with high probability over the random SK instance. The proof decouples the partition function by pairing each configuration $x$ with its spin-flip $x^{\\{i\\}}$ and uses the subgaussianity of the random couplings, so the exponential moment is controlled without any covariance operator norm. The resulting tail bound provides the constant-probability 'good region' in which the sigmoid is anti-Lipschitz with only a $\\exp(O(\\beta^2+\\beta\\sqrt{\\log n}))$ penalty. For higher-order MRFs the same lemma is generalized to subgaussian differences $\\psi(x)-\\psi(y)$ of the factorization polynomial, which yields the $C$-smoothness condition used by the $t$-wise recovery theorems.","core_discovery":"The central discovery is that the low-temperature barrier for learning the SK model comes from the specific techniques used by prior work, not from the model itself. Previous approaches reduced learnability to a bound on the operator norm of the covariance $\\mathbb{E}_{X\\sim D_{A,h}}[XX^T]$, a quantity that provably diverges for $\\beta\\ge 1$. The paper instead proves a direct subgaussian bound on the local fields the algorithm actually needs: with high probability over the random choice of $A,h$, for every row $i$, $\\mathbb{E}_{X\\sim D_{A,h}}[\\exp(|A_i\\cdot X+h_iX_i|^2/(B\\beta^2))]\\le n^2 e^{O(\\beta^2)}$. This yields a tail bound of the form $|A_i\\cdot X+h_iX_i|\\le O(\\beta^2+\\beta\\sqrt{\\log n})$ except with probability $1/n$, and this tail bound is exactly what the parameter-recovery reduction requires. Plugging it into the Sparsitron analysis produces the sample bound $N=\\exp(O(\\beta^2+\\beta\\sqrt{\\log n}))\\,\\mathrm{poly}(n,1/\\epsilon)$ and thus polynomial time for $\\beta\\le\\sqrt{\\log n}$.","pith_inferences":["Editorial inference: the real condition suggested by the proof is subgaussian concentration of the Gibbs local fields, not boundedness of the covariance operator; other disordered models with such concentration, such as diluted spin glasses or mixtures of $p$-spin terms, should be learnable by the same argument even where spectral conditions fail.","Editorial inference: the bound $\\beta\\le\\sqrt{\\log n}$ is a sufficient condition, not a proven frontier; the exponential-moment calculation is loose enough that the true polynomial-time threshold may extend to larger $\\beta$, and a finite-$n$ experiment at fixed $\\beta=2$ is a natural probe.","Editorial inference: a fully uniform statement over all $\\beta>0$ still needs one additional calculation, because the local-field moment lemma is normalized by $\\beta$ while a standard Gaussian external field has scale $1$; for very small $\\beta$ the lemma as written needs a separate argument."],"forward_implications":["For any fixed inverse temperature $\\beta>1$, the sample count becomes $\\exp(O(\\beta^2))\\,\\mathrm{poly}(n,1/\\epsilon)$, so every fixed low temperature is learned in polynomial time, not just a thin band above $\\beta=1$.","Success over the random model holds with probability $1-O(1/n)$, improving on the $1-O(1/\\log n)$ guarantee of the prior high-temperature algorithm, and a Gaussian external field requires no extra treatment.","On arbitrary bounded-degree graphs with random Gaussian weights, the same algorithm recovers the graph and parameters with $\\exp(O(\\beta^2+\\beta\\sqrt{\\log n}))\\,\\mathrm{poly}(d,\\log n,1/\\epsilon)$ samples; with Rademacher weights it recovers the model exactly with a sub-polynomial sample count.","For random $t$-wise MRFs and pure $t$-spin models, parameter recovery and TV-distance closeness hold with $\\exp(O(\\beta^2 t+\\beta t\\sqrt{\\log n}))\\,\\mathrm{poly}(n^t,1/\\epsilon)$ samples, a regime where even high-temperature results were previously open.","Because parameter recovery implies KL and TV closeness, the algorithm can output an Ising model $\\epsilon$-close in total variation to the true one."],"supporting_citations":[{"why":"Supplies the Sparsitron multiplicative-weights algorithm and the reduction from parameter recovery to small squared loss that the paper reuses.","marker":"[KM17]"},{"why":"Gives the prior high-temperature covariance-based algorithm whose barrier at beta=1 the paper aims to remove.","marker":"[GM24]"},{"why":"Provides the operator-norm bound on the SK covariance that the paper identifies as provably failing for beta>=1.","marker":"[EAG24]"},{"why":"Supplies the subgaussian exponential-moment and tail facts used in the local-field concentration lemma.","marker":"[Ver18]"}],"fun_headline_variants":["Subgaussian trick learns SK model even at low temperature","Crossing the beta=1 spin-glass barrier with multiplicative weights","Polynomial-time learner for low-temperature Sherrington-Kirkpatrick","Spin glasses: simple proof shows learnable beyond beta=1"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that each local field is subgaussian at scale proportional to $\\beta$, whereas a standard Gaussian external field has scale $1$; for small $\\beta$ the proof's normalization in the exponential-moment lemma is therefore not justified as written, and the displayed calculation even switches between $A_i\\cdot X+h_i$ and $A_i\\cdot X+h_iX_i$.","fun_headline_variants_meta":{"raw":{"variants":["Subgaussian trick learns SK model even at low temperature","Crossing the beta=1 spin-glass barrier with multiplicative weights","Polynomial-time learner for low-temperature Sherrington-Kirkpatrick","Spin glasses: simple proof shows learnable beyond beta=1"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000269,"raw_usage":{"total_tokens":1628,"prompt_tokens":957,"completion_tokens":671,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":573,"completion_tokens_details":{"reasoning_tokens":601}},"tokens_in":573,"tokens_out":671,"duration_ms":7697,"temperature":1.0,"reasoning_tokens":601,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T18:51:26.863202+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the claimed tail bound on finite SK instances: draw $D_{A,h}\\sim SK(\\beta)$ with $\\beta=0.1$ and $n=1000$, sample $X$ from the model, and estimate $\\Pr[|A_i\\cdot X+h_iX_i| > C(\\beta^2+\\beta\\sqrt{\\log n})]$ for the constant $C$ in the $O(\\cdot)$. If this probability is not below $1/n$ for every row, Lemma 3.4 fails as stated and the small-$\\beta$ case would need a corrected proof. A complementary experiment at $\\beta=1.5$ with the claimed $\\exp(O(\\beta^2))\\,\\mathrm{poly}(n)$ samples would test the main theorem directly.","supporting_citations":[],"review_version":1}