{"id":"1419a7d9-ee6d-42c7-a2ec-de78754fd636","arxiv_id":"2509.05016","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"The authors establish a tight FPRAS/hardness phase transition for chi-alpha divergence between Ising models and extend the approach to KL, Rényi, Jensen-Shannon, alpha-divergence, and squared Hellinger.","lead":"This paper gives approximation algorithms and matching hardness results for computing a broad class of statistical divergences between two Ising models, extending earlier total-variation-distance work. The key finding is a sharp phase transition for chi-alpha divergence: tractable exactly when an associated family of spin systems is itself tractable.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The claimed Rényi-divergence extension uses the wrong f; f(x)=−ln x+x−1 is reverse KL, so Theorem 1.7 does not approximate Rényi divergence.","rationale":"The reader's verdict was CONDITIONAL, and I agree that a conditional assessment is appropriate, but my main reason differs from the reader's weakest_assumption. The reader focused on the b-marginal lower bound as the load-bearing premise; that is an explicit assumption of the theorems, not a hidden flaw, and it is satisfied in the zero-field constant-parameter family where the phase transition is claimed. The reader also noted the Rényi naming problem in their rationale, and that is the concrete, verifiable error I find most load-bearing. The paper's abstract and Theorem 1.7 explicitly advertise an algorithm for Rényi divergence, but the function f(x)=−ln x+x−1 defines the reverse KL divergence, not a Rényi divergence. This is not a cosmetic naming issue: the algorithm's estimator targets E_μ[f(ν/μ)], which equals KL(μ∥ν), and there is no transformation given that would yield a Rényi divergence. The χ^α results are unaffected: the algorithms and hardness proofs for χ^α are internally consistent, the reduction to sampling/counting oracles is well-posed, and the phase transition in the zero-field unified family matches the known partition-function tractability boundary. The Lemma 2.3 minimizer typo (the claimed optimal t is off by a factor of 2 in the power) is harmless because the proof only needs a valid t in (0,1), and the resulting bound still has the correct Θ(θ^α) scaling. Therefore the verdict should remain CONDITIONAL: the central χ^α contribution is sound, but the Rényi extension claim is false and must be corrected before the paper's full claims are accepted.","tokens_in":164,"tokens_out":33547,"duration_ms":271940,"concrete_test":"Compute the f-divergence for f(x)=−ln x+x−1 between two Bernoulli distributions with p=0.9, q=0.5 and compare with the order-2 Rényi divergence. The former equals q ln(q/p)+(1−q)ln((1−q)/(1−p)) = 0.5 ln(0.5/0.9)+0.5 ln(0.5/0.1) ≈ 0.5108, which is KL(μ∥ν). The latter equals ln E_μ[(ν/μ)^2] = ln(0.5(1.8)^2+0.5(0.2)^2) = ln(1.64) ≈ 0.4947. The numerical difference confirms the paper's 'Rényi divergence' is actually reverse KL; this settles the misidentification without ambiguity.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Section 1.2 and Theorem 1.7 claim that the f-divergence with f(x)=−ln x+x−1 is the Rényi divergence. This is incorrect: substituting this f into the definition gives D_f(ν∥μ)=E_μ[−ln(ν/μ)+ν/μ−1]=KL(μ∥ν), the reverse KL divergence, not a Rényi divergence. The Rényi divergence of order α is defined as (1/(α−1))ln E_μ[(ν/μ)^α] (with α→1 giving KL) and is not an f-divergence with generator −ln x+x−1. Consequently, the algorithm in Section 6.2 estimates the reverse KL divergence, and the abstract's claim that the algorithm extends to Rényi divergence is unsubstantiated. This is a real false assertion in the advertised extensions, though it does not affect the χ^α phase transition (Theorems 1.4 and 1.6), which appears technically sound. The b-marginal assumption is explicit and is satisfied in the constant-parameter instances where the phase transition is stated, so it is not a hidden flaw.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the problem of approximating the f-divergence between two Ising models given by their interaction matrices and external fields, up to relative error. For the χ^α-divergence with constant integer α, it gives an FPRAS (Theorem 1.4) under a b-marginal lower bound on both input distributions, assuming sampling and approximate counting oracles for every model in the interpolating family F(ν,μ,α). For zero-field, unified-value Ising models with β_μ>β_ν≥(Δ-2)/Δ, it proves a matching hardness result (Theorem 1.6) when (β_ν/β_μ)^α β_μ < (Δ-2)/Δ, yielding a phase transition. The paper also claims algorithms for KL, Rényi, Jensen-Shannon, α-divergence, and squared Hellinger distance.","tokens_in":28731,"tokens_out":22200,"duration_ms":163683,"significance":"The χ^α phase transition is a substantial, clean result: it provides a complete threshold in a natural constant-parameter regime, extends the earlier TV-distance work of [FLY25] to a general family of divergences, and the hardness direction rests on established anti-ferromagnetic partition-function inapproximability. The proofs are detailed, with explicit running times and oracle assumptions. The b-marginal lower bound is stated clearly and is satisfied in the constant-parameter instances where the phase transition is formulated. The main weakness is the incorrect identification of Rényi divergence in the extension sections, which overstates the paper's contributions even though it does not affect the χ^α results.","major_comments":[{"comment":"The paper's claimed extension to Rényi divergence is mathematically incorrect. The function f(x)=-ln x+x-1, which the paper labels as generating the Rényi divergence, gives D_f(ν||μ)=E_μ[-ln(ν/μ)+ν/μ-1]=KL(μ||ν), the reverse KL divergence. The actual Rényi divergence of order α is (1/(α-1))ln E_μ[(dν/dμ)^α], which is not an f-divergence of the form studied. Consequently Theorem 1.7 and the abstract's assertion that the algorithm extends to Rényi divergence are unsupported; the algorithm in Section 6 estimates reverse KL. The same paragraph in Section 1.2 also misstates the limits of the α-divergence: for f(x)=(x^α-αx-(1-α))/(α(α-1)), the limit α→1 is x ln x-x+1 (KL), and α→0 is -ln x+x-1 (reverse KL), not the reverse of what is written. These statements must be corrected or the Rényi claims removed.","section":"Section 1.2, Theorem 1.7, Section 6"}],"minor_comments":[{"comment":"The proof claims that g(t) attains its minimum at t=(b^{2α}θ^α/2)^{1/(α+1)}, but the derivative g'(t) vanishes at t=(2b^{2α}θ^α)^{1/(α+1)}. The bound remains valid with the stated t, since the inequality holds for every t, but the 'minimum' claim and the subsequent display should be corrected or the optimal t used.","section":"Lemma 2.3"},{"comment":"The running-time summary states T=Θ_{α,b}(1/(ε^2 θ^α)), but the algorithm in Section 5.1 defines T as ⌈8·10^4(α+1)/(ε^2 B_{α,b}(θ)^2)⌉, and since B_{α,b}(θ)=Θ(θ^α), this is T=Θ_{α,b}(1/(ε^2 θ^{2α})), matching Theorem 1.4. The exponent in Lemma 5.1 should be corrected.","section":"Lemma 5.1"},{"comment":"In the sentence describing contributions to D_{χ^α}, the formula for ν(σ)>μ(σ) is written as μ(σ)(μ(σ)/ν(σ)-1)^α; it should be μ(σ)(ν(σ)/μ(σ)-1)^α. The following line uses the correct expression.","section":"Lemma 5.2 proof"},{"comment":"The row labeled 'Rényi' lists f(x)=-ln x+x-1; this is reverse KL, and the table's computed f'' and F(ζ) are correct for that function. The label should be changed to avoid propagating the error described in the major comment.","section":"Section 6.1 table"},{"comment":"The abstract and Problem 1.1 state the problem for general Ising models without mentioning the b-marginal lower bound, while Theorem 1.4 requires it. The scope should be qualified, since the b-marginal condition can fail for low-temperature Ising models even when sampling and counting are tractable.","section":"Abstract and Introduction"}],"recommendation":"major_revision","confidential_remarks":"The core χ^α results (Theorems 1.4 and 1.6) appear technically sound and are a meaningful advance over the TV-distance results of [FLY25]. The principal obstacle to acceptance is the false identification of the Rényi divergence in the abstract, Section 1.2, Theorem 1.7, and Section 6; this is fixable by removing the Rényi claims or providing a correct algorithm, but the current version's advertised scope is inaccurate. The paper also relies substantially on the authors' own [FLY25] for the parameter-distance lemma and the small-distance framework; this is appropriately cited and does not constitute circularity."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things you should know. The core result — a tight computational phase transition for approximating the χ^α-divergence between Ising models — is real, and the proof ideas are genuinely nice: they expand the divergence into partition functions of intermediate Ising models and then show hardness by reducing from antiferromagnetic partition functions when those intermediate models cross the uniqueness threshold. Second, the paper's advertised extension to Rényi divergence is wrong. The generator f(x)=-ln x + x - 1 gives reverse KL, not Rényi, and the claim in Theorem 1.7 and the abstract does not hold.\n\nThe starting point is [FLY25]'s TV-distance work; the paper generalizes it to f-divergences, with the main new ingredient being the binomial expansion trick that turns χ^α into a sum of ratios of partition functions of models J^(k) = k Jν - (k-1) Jμ. The hardness side is clean: when the input models are both easy (unique or ferromagnetic) but the α-th intermediate model is antiferromagnetic beyond uniqueness, an FPRAS for the divergence would give an FPRAS for a hard partition function. The phase transition at (βν/βμ)^α βμ = (Δ-2)/Δ is exactly the kind of crisp statement that makes this paper worth reading. The proofs are detailed and mostly check out.\n\nThe Rényi issue is not cosmetic. The abstract claims extension to Rényi divergence; that extension is unsubstantiated. The authors should either withdraw the claim or actually solve the Rényi problem. The α-divergence section also has a naming slip: the limits α→0 and α→1 give reverse KL and forward KL, respectively, not KL and Rényi. These are localized but they appear in the abstract, so they need fixing before publication.\n\nLemma 2.3's stated minimizer is wrong: the derivative of g(t) vanishes at t = (2b^{2α}θ^α)^{1/(α+1)}, not at (b^{2α}θ^α/2)^{1/(α+1)}. The bound still holds because any t in (0,1) works, and the chosen B is a valid (slightly suboptimal) constant, but the proof as written is incorrect and the claim that the function \"obtains its minimum\" at that t is false.\n\nThe b-marginal lower bound assumption is explicit and necessary, but it rules out low-temperature Ising models. That limits the applicability, not the correctness of the stated results.\n\nBottom line: this paper deserves a serious referee. The χ^α results are a solid contribution to divergence approximation for graphical models, and the hardness matching is valuable. It should not be desk-rejected. The referee should require the Rényi claim to be corrected or removed, and the Lemma 2.3 proof to be fixed. After that, I'd be happy to see it in print.","headline":"The χ^α-divergence phase-transition result is real and worth refereeing, but the paper's advertised Rényi-divergence extension is mislabeled and the Lemma 2.3 minimizer claim is wrong.","tokens_in":29127,"tokens_out":9933,"would_cite":true,"duration_ms":71671,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q25","68W20","82B20"],"pacs":[],"model":"deepseek-v4-flash","headline":"For zero-field uniform-interaction Ising models, approximating the \\(\\chi^\\alpha\\)-divergence has a sharp tractability boundary: an FPRAS exists exactly when \\((\\beta_\\nu/\\beta_\\mu)^\\alpha\\beta_\\mu \\ge (\\Delta-2)/\\Delta\\), and below it…","keywords":["f-divergence","Ising model","chi-alpha divergence","FPRAS","computational phase transition","approximate counting","parameter distance","anti-ferromagnetic Ising model"],"falsifier":"Enumerate all zero-field 3-regular graphs on up to, say, 12 vertices, take \\(\\$\\alpha$=2\\), \\(\\beta_\\nu=1/3\\), \\(\\beta_\\mu=2/3\\), and compute the exact \\(\\$chi^{2}$\\)-divergence and partition functions; Lemma 7.2 predicts the ratio \\(D_{\\$chi^{2}$}(\\nu\\|\\mu)Z(G,\\beta_\\nu)^2/Z(G,\\beta_\\mu)\\) stays within constant factors of \\(Z(G,1/6)\\), so a graph violating those bounds would refute the hardness reduction's core comparison.","tokens_in":28176,"feed_emoji":"🧲","tokens_out":14558,"duration_ms":118121,"temperature":0.7,"pith_summary":"Approximating the \\(f\\)-divergence between two Ising models—the family of measures that includes total-variation distance—has a precise algorithmic boundary when the divergence is the \\(\\chi^\\$\\alpha$\\)-divergence. The paper shows that, under a condition that every conditional single-spin marginal of both models stays above a fixed constant \\(b>0\\), the \\(\\chi^\\$\\alpha$\\)-divergence admits a fully polynomial randomized approximation scheme (FPRAS) whenever an interpolating family of Ising models admits sampling and approximate-counting oracles. It then proves a matching hardness result: for zero-field models with uniform interactions on \\(\\$\\Delta$\\)-regular graphs, an FPRAS exists if and only if \\((\\beta_\\nu/\\beta_\\mu)^\\$\\alpha$\\beta_\\mu \\ge (\\$\\Delta$-2)/\\$\\Delta$\\), and below that threshold no FPRAS exists unless NP=RP. The same oracle-based machinery is claimed to extend to KL, Rényi, Jensen-Shannon, \\(\\$\\alpha$\\)-divergence, and squared Hellinger distance. A careful reader should care because the result turns a quantity used throughout statistics and machine learning into a computational problem with a sharp transition, not a smooth tradeoff.","feed_headline":"One formula decides when Ising divergences are computable","feed_subtitle":"For chi-alpha divergence, one inverse-temperature product marks the easy/hard boundary; below it, approximation is NP-hard.","key_machinery":"The machinery that carries the argument is the interpolated family of Ising models \\(\\mathcal F(\\nu,\\mu,\\$\\alpha$)\\), whose \\(k\\)-th member has interaction \\($J^{{(k)}}$=kJ^\\nu-(k-1)J^\\mu\\) and external field \\($h^{{(k)}}$=kh^\\nu-(k-1)h^\\mu\\). Because the weight of a configuration in that model is proportional to \\(\\nu^k(\\$\\sigma$)/\\$mu^{{k-1}}$(\\$\\sigma$)\\), a binomial expansion of the likelihood ratio rewrites the \\(\\chi^\\$\\alpha$\\)-divergence as an alternating sum of partition-function ratios \\(Z_\\$mu^{{k-1}}$Z_k/Z_\\nu^k\\), where \\(Z_k\\) is the partition function of the \\(k\\)-th interpolated model. The algorithm estimates each ratio with counting oracles and samples the interpolated models to decide which side of the likelihood ratio each configuration lies on; an error-control lemma lower-bounds the divergence by \\(\\sum_\\$\\sigma$ \\mu(\\$\\sigma$)(\\nu(\\$\\sigma$)/\\mu(\\$\\sigma$)+1)^\\$\\alpha$\\) in the large-parameter-distance case. For small parameter distance, the ratio \\(W=w_\\nu(X)/w_\\mu(X)\\) under \\(X\\sim\\mu\\) is concentrated and a sample-average estimator works. The hardness direction maps the divergence to the partition function of an anti-ferromagnetic Ising model at inverse temperature \\(\\$\\beta$=(\\beta_\\nu/\\beta_\\mu)^\\$\\alpha$\\beta_\\mu\\), where known inapproximability results for counting apply.","core_discovery":"The central claim is a matching algorithm-hardness pair. On the algorithmic side (Theorem 1.4), for any constant integer \\(\\$\\alpha$\\ge 1\\), if both input Ising models are \\(b\\)-marginally bounded and every model in the family \\(\\mathcal F(\\nu,\\mu,\\$\\alpha$)=\\{(G,$J^{{(k)}}$,$h^{{(k)}}$): $J^{{(k)}}$=kJ^\\nu-(k-1)J^\\mu,\\ $h^{{(k)}}$=kh^\\nu-(k-1)h^\\mu,\\ 0\\le k\\le \\$\\alpha$\\}\\) admits sampling and approximate-counting oracles, then the \\(\\chi^\\$\\alpha$\\)-divergence can be approximated in polynomial time with relative error \\($e^{{\\pm\\varepsilon}}$\\). On the hardness side (Theorem 1.6), fix \\(\\$\\alpha$\\ge 2\\), \\(\\$\\Delta$\\ge 3\\), and zero-field uniform-interaction models \\((G,\\beta_\\nu)\\), \\((G,\\beta_\\mu)\\) with \\(\\beta_\\mu>\\beta_\\nu\\ge(\\$\\Delta$-2)/\\$\\Delta$\\) and \\((\\beta_\\nu/\\beta_\\mu)^\\$\\alpha$\\beta_\\mu<(\\$\\Delta$-2)/\\$\\Delta$\\); then, unless NP=RP, no FPRAS exists, even though both input models are individually tractable. For this family the two theorems yield an exact phase transition at \\((\\beta_\\nu/\\beta_\\mu)^\\$\\alpha$\\beta_\\mu=(\\$\\Delta$-2)/\\$\\Delta$\\). The paper further claims the same oracle-based framework approximates several other standard divergences, including KL and Rényi divergences, requiring oracles only for the input models in those cases.","pith_inferences":["The threshold expression \\((\\beta_\\nu/\\beta_\\mu)^\\alpha\\beta_\\mu\\) predicts that hardness appears precisely when the interpolated model at \\(k=\\alpha\\) crosses the anti-ferromagnetic uniqueness boundary; if approximate counting for anti-ferromagnetic models were ever extended below that boundary, the divergence phase transition would shift accordingly.","A natural testable extension is to ask whether the \\(b\\)-marginal lower bound can be replaced by high-temperature or correlation-decay assumptions; the paper's Lemmas 2.2 and 2.3 suggest the same structure would survive as long as single-site marginals stay bounded away from zero on relevant subsets.","For real, non-integer \\(\\alpha\\), the binomial expansion breaks, but the phase-transition formula suggests an interpolation-based estimator might still work; checking numerically whether the same threshold governs tractability for, say, \\(\\alpha=1.5\\) would be a concrete next step.","In practical terms, the small-parameter-distance estimator \\(\\hat D = \\frac1T\\sum_i f(W_i/\\bar W)\\) with \\(T=\\mathrm{poly}(n/\\varepsilon)\\) gives an off-the-shelf plug-in recipe whenever likelihood ratios are concentrated; one could benchmark it on lattice Ising models to see whether the worst-case sample count is pessimistic."],"forward_implications":["When the oracle assumptions hold and the \\(b\\)-marginal bound is constant, Theorem 1.4 gives a fully polynomial randomized scheme for the \\(\\chi^\\alpha\\)-divergence, generalizing the TV-distance FPRAS that corresponds to \\(\\alpha=1\\).","In the zero-field uniform-interaction setting, the paper's two theorems imply an exact phase transition: FPRAS exists if and only if \\((\\beta_\\nu/\\beta_\\mu)^\\alpha\\beta_\\mu\\ge(\\Delta-2)/\\Delta\\), with NP=RP-hardness otherwise.","Because the hardness instances have both input models individually tractable, the intermediate interpolated model at \\(k=\\alpha\\) is what makes the divergence hard; the oracle assumptions in the algorithmic theorem are therefore necessary, not an artifact.","For KL, Rényi, and Jensen-Shannon divergences, only the two input models need sampling and counting oracles, so the tractability region is larger than for \\(\\chi^\\alpha\\)-divergence.","When the parameter distance between the two models is small (\\(<1/(10(n+3m))\\)), any \\(f\\)-divergence satisfying a mild derivative condition is approximable with just a sampling oracle, no counting oracle."],"supporting_citations":[{"why":"Supplies the parameter-distance definition, the TV lower bound used in Lemma 3.1, and the small-distance sampling algorithm that Theorem 4.2 generalizes.","marker":"[FLY25]"},{"why":"Provides rapid mixing and polynomial sampling/approximate counting at the uniqueness threshold, making the input models in the tractable regime and Corollary 1.5 effective.","marker":"[CCYZ25]"},{"why":"Provides polynomial-time approximation of ferromagnetic Ising partition functions, used to certify tractability of input models with \\(\\beta\\ge1\\) and to compute partition functions in the hardness proof.","marker":"[JS93]"},{"why":"Establishes inapproximability of the anti-ferromagnetic Ising partition function beyond uniqueness on \\(\\Delta\\)-regular graphs, the hardness seed for Theorem 1.6.","marker":"[SS14]"},{"why":"Extends the anti-ferromagnetic inapproximability to all required parameter ranges, supplying the inapproximability factor used in Lemma 7.1.","marker":"[GŠV16]"}],"fun_headline_variants":["Ising divergence approximation hits exact phase boundary","One inverse-temperature product sets Ising divergence tractability","Matching algorithm and hardness for Ising chi-alpha divergence","Sharp threshold for approximating Ising f-divergence","Easy-hard boundary for Ising chi-alpha divergence approximation"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that every conditional single-spin marginal of both input distributions is bounded below by a fixed positive constant \\(b\\); if a marginal can be exponentially small, the divergence lower bounds and the algorithm's error control stop working.","fun_headline_variants_meta":{"raw":{"variants":["Ising divergence approximation hits exact phase boundary","One inverse-temperature product sets Ising divergence tractability","Matching algorithm and hardness for Ising chi-alpha divergence","Sharp threshold for approximating Ising f-divergence","Easy-hard boundary for Ising chi-alpha divergence approximation"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000198,"raw_usage":{"total_tokens":1420,"prompt_tokens":1051,"completion_tokens":369,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":667,"completion_tokens_details":{"reasoning_tokens":293}},"tokens_in":667,"tokens_out":369,"duration_ms":3736,"temperature":1.0,"reasoning_tokens":293,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T16:26:06.582397+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Enumerate all zero-field 3-regular graphs on up to, say, 12 vertices, take \\(\\$\\alpha$=2\\), \\(\\beta_\\nu=1/3\\), \\(\\beta_\\mu=2/3\\), and compute the exact \\(\\$chi^{2}$\\)-divergence and partition functions; Lemma 7.2 predicts the ratio \\(D_{\\$chi^{2}$}(\\nu\\|\\mu)Z(G,\\beta_\\nu)^2/Z(G,\\beta_\\mu)\\) stays within constant factors of \\(Z(G,1/6)\\), so a graph violating those bounds would refute the hardness reduction's core comparison.","supporting_citations":[],"review_version":2}