{"id":"042bed36-6593-4976-afd1-9b2fa50bffe4","arxiv_id":"2502.00557","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"They show that for Bernoulli noise on the hypercube, the score of the noisy distribution gives the optimal Hamming denoiser, and they prove Wasserstein convergence for two discrete Langevin samplers at high noise.","lead":"This paper extends score-based generative modeling to binary data on the Boolean hypercube, replacing Gaussian noise with Bernoulli sign flips. It derives a binary version of the Tweedie-Miyasawa formula that connects optimal denoising to the score function, and analyzes the convergence of discrete Langevin samplers for the smoothed distribution.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"All convergence results assume the exact score; the trained denoiser is never shown to satisfy the regularity conditions, so the end-to-end claim is unproven for the actual method.","rationale":"The paper's theoretical core is internally coherent: the Tweedie–Miyasawa analogue for Bernoulli noise (Lemma 2.2), the denoising bound (Lemma 2.3), the multi-measurement identity (Lemma 2.4), and the Wasserstein contraction and bias results for the discrete Langevin samplers are derived carefully and appear to hold under their stated assumptions. The treatment of the two-stage sampler with convex-smoothness condition (Eq. 8) is a genuine contribution. However, the central claim of an end-to-end sampling method depends on a learned score being available and accurate enough to inherit the regularity properties used in the proofs. The reader's weakest assumption identifies exactly this gap: the paper never analyzes how score estimation error propagates into the Wasserstein bounds, and it never checks whether a U-Net denoiser trained only on hypercube vertices gives trustworthy scores in the interior used by sequential multi-measurement sampling. This is the most load-bearing concern because it sits between the theorems and the actual algorithm; without it, the propositions are oracle results. The experiments in §5.2 do not close the gap: they are qualitative, operate at α=0.5 with d=784 (α√d≈14, far outside 8dα²e^{4α}≤1), and use η=1/α, which violates the two-stage theorem's condition e^{−2/η+2α}≤1/d. The proposed concrete test on the synthetic mixture would settle the concern by measuring score error and its downstream effect in a regime where the exact score is known. I therefore agree with the conditional verdict: the math is sound as an idealized framework, but the practical end-to-end guarantee is not yet established.","tokens_in":21063,"tokens_out":19346,"duration_ms":189306,"concrete_test":"In the synthetic mixture model of §5.1 with d=16, where ∇log q_α is computable in closed form, choose α=0.1/√d (inside the theorem's regime). Train the logistic-regression denoiser on a finite sample (e.g., n=10^4) at that α, and evaluate (i) sup over hypercube vertices and over interior grid points of ∥s_learned(y)−∇log q_α(y)∥∞, and (ii) the empirical Lipschitz constants β1_learned, β2_learned from Eq. (4) on that grid. Then run the two-stage sampler with s_learned and with the exact score from the same starting distribution, estimating W(q′_learned, q_α) and W(q′_exact, q_α) by long chains with the closed-form transition matrices.","verdict_should_be":"UNCHANGED","load_bearing_attack":"All four convergence propositions (3.1–3.4) are stated for a Markov chain driven by the exact score s(y)=∇log q_α(y) satisfying Eq. (4) and Eq. (8) with β1=α, β2=α². The method, however, replaces s by a finite-sample neural-network denoiser trained with logistic regression at hypercube vertices. Nothing in the paper bounds ∥s_learned−s∥ or shows that s_learned inherits the ℓ∞ bound α and the α²-Lipschitz condition; a U-Net trained with AdamW has uncontrolled Lipschitz constants, and if β1,β2 are exceeded the contraction proofs in Propositions 3.1 and 3.3 do not apply, so the chain may fail to mix or may converge to a distribution far from q_α. The problem is worse for multi-measurement sampling: Lemma 2.4 and the sequential sampler require evaluating the score at averaged points in the interior [−1,1]^d, but the experiments train only on vertices (or, if averages are used, no such experiment or analysis is reported). This is not a cosmetic issue: the title promises sampling by denoising through score functions, and absent a score-error propagation theorem, the end-to-end claim is an idealized statement about an oracle. I also note the experimental regime is outside the theory: for binarized MNIST d=784, α=0.5 gives α√d≈14, violating 8dα²e^{4α}≤1, and η=1/α gives e^{−2/η+2α}=1, violating the Proposition 3.4 condition e^{−2/η+2α}≤1/d.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies Bernoulli sign-flip smoothing y = x ∘ ε on {−1,1}^d, defines an extension q_α(y) of the noisy pmf to R^d via q_α(y) ∝ Σ_x p(x) e^{α x^⊤ y}, proves a Tweedie–Miyasawa identity E[x|y] = (1/α)∇ log q_α(y) (Lemma 2.2), proposes logistic-regression denoising to learn the score, and introduces one- and two-stage discrete Langevin samplers. It proves Wasserstein contraction and stationary-bias bounds for the exact-score chains (Propositions 3.1–3.4), extends the identity to multiple measurements with effective noise mα (Lemma 2.4), and reports synthetic and binarized-MNIST experiments.","tokens_in":21420,"tokens_out":9550,"duration_ms":85322,"significance":"If the theoretical claims held for the implemented algorithm, this would be a valuable alternative to discrete diffusion: it avoids SDE discretization, gives an exact denoising–score identity on the hypercube, and provides explicit Wasserstein contraction results for discrete Langevin-like kernels in this setting. The appendices are careful and the lemmas and propositions are proved from stated assumptions with explicit constants. The main caveat is that the theory is oracle-level: it uses the exact score, whereas the experiments use a learned U-Net, and the demonstrated operating points lie outside the theorem regimes. The contribution is nonetheless a solid conceptual and algorithmic framework.","major_comments":[{"comment":"All four convergence results are proved for the exact score s = ∇ log q_α satisfying Eq. (4) and Eq. (8). The implemented method replaces s by a U-Net trained by logistic regression on hypercube vertices. No bound on ∥ŝ − s∥ is given, and it is not shown that ŝ inherits ∥ŝ∥∞ ≤ α or an α²-Lipschitz property. Since the stationary distribution in Propositions 3.2 and 3.4 is defined through a transition kernel built from the exact score, the end-to-end claim of \"sampling binary data by denoising through score functions\" is proved only for an oracle, not for the algorithm in Section 5.","section":"Section 3, Propositions 3.1–3.4"},{"comment":"Multi-measurement and sequential sampling require the score at interior points ȳ ∈ [−1,1]^d and at parameter mα. Section 2.3's training procedure uses single noisy vertices only. The remark in Section 2.4 that one can train on averaged measurements is not supported by experiments or analysis, and Section 3 correctly notes that the extension of q_α to R^d is non-unique up to additive linear score terms. Thus the learned denoiser's behavior on the interior, on which Lemma 2.4 and the sequential sampler rely, is unconstrained and unverified.","section":"Sections 2.4 and 3.2"},{"comment":"The MNIST experiments are outside the stated theorem conditions. For d = 784 and α = 0.5, the condition 8dβ₂e^{4β₁} ≤ 1 of Propositions 3.3 and 3.4 gives 8 · 784 · 0.25 · e² ≈ 1.16 × 10⁴, and η = 1/α gives e^{−2/η + 2β₁} = 1, violating the assumption e^{−2/η + 2β₁} ≤ 1/d of Proposition 3.4. The claim that the experiments validate the theoretical findings is therefore unsupported; at best they are heuristics in a regime the theory does not cover.","section":"Section 5.2 and Propositions 3.3–3.4"},{"comment":"There is a mismatch between the regime where the sampler is proven to converge and the regime where denoising is useful. Lemma 2.3 gives denoising error O(d e^{−2α}), which is small only for large α, while the contraction conditions hold only for α ≪ 1/d (one-stage) or α ≪ 1/√d (two-stage). No composite end-to-end bound quantifies the trade-off for the procedure \"sample from q_α, then denoise\"; the multi-measurement idea in Lemma 2.4 is the right remedy, but its combination with the sequential sampler's bias is not analyzed.","section":"Lemma 2.3 versus Propositions 3.1–3.4"}],"minor_comments":[{"comment":"The index set in \"for i ∈ {-1, . . . ,1}^d\" should be i ∈ {1, . . . , d}.","section":"Section 2.1, Eq. (1)"},{"comment":"The proof of Lemma 2.4 says \"Following the same reasoning that in the proof of Lemma 2.4\"; the intended reference is Lemma 2.3.","section":"Appendix A"},{"comment":"In the Lipschitz condition, \"∥y − y∥₁\" should read \"∥y − y′∥₁\".","section":"Section 3, Eq. (4)"},{"comment":"The text uses \"learning rate equal to 1/α\" in Section 5.1 and \"step-size η\" elsewhere; the terminology should be unified.","section":"Section 5.1 and Section 5.2"},{"comment":"The mixing time is reported as 1/(1 − λ₂), but λ₂ is not defined in the main text; it should be defined explicitly.","section":"Figure 3 and surrounding text"},{"comment":"The use of Wikipedia links for the total variation distance, Chernoff bound, and Pinsker's inequality is informal; standard textbook references (e.g., Levin and Peres, 2017) would be more appropriate.","section":"Appendices B–E"},{"comment":"The qualitative MNIST panels would benefit from quantitative metrics, especially because the theoretical bounds do not apply in that regime.","section":"Section 5.2"}],"recommendation":"major_revision","confidential_remarks":"To the editor: the paper is likely to draw attention because of the authors and the simplicity of the framework. The main issue is the gap between oracle-level theory and the practical algorithm; this is common in generative modeling papers, but the manuscript states the theory and experiments validate each other more strongly than they do. A revision that either adds finite-sample score-error propagation or Lipschitz verification of the learned score, and recalibrates the experimental claims to the proven regime or explicitly presents the experiments as heuristic, would put the paper in acceptable shape. I do not see a fatal flaw in the mathematical derivations themselves."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The genuinely new material is the Wasserstein contraction analysis for discrete Langevin samplers (Props 3.1 and 3.3) and the clean binary Tweedie-Miyasawa identity (Lemma 2.2). The multi-measurement extension is a direct analog of the Gaussian work you know, but the contraction bounds are a real addition to the discrete sampling literature. The appendices are self-contained and careful; the regularity assumptions are stated and verified for the exact q_α. So the idealized framework is sound.\n\nThe soft spot is exactly where the stress-test note lands: every convergence result is about a chain driven by the exact score s = ∇ log q_α. The method replaces s with a U-Net trained on hypercube vertices, and the paper never bounds ∥s_learned − s∥ or shows that the learned score inherits the ℓ∞ bound α and the α²-Lipschitz condition. If those constants are exceeded, the contraction proofs in Props 3.1 and 3.3 do not apply. For a U-Net there is no reason to expect them to hold. That is a real gap between the title's promise and what is proven. I'd call it a gap, not a fatal flaw: the idealized analysis is honest and a perturbation theorem would be a natural follow-up.\n\nThe second soft spot is the regime mismatch. The theory needs α ≲ 1/√d or 1/d for contraction and stationarity, which is very high noise; denoising at that noise is poor, with Lemma 2.3 giving only de^{-2α}. The MNIST experiments at α = 0.5 (d = 784) sit outside the stated conditions, and η = 1/α violates the Prop 3.4 condition e^{-2/η+2β1} ≤ 1/d. Those experiments are qualitative with no baselines, so they carry little evidential weight. The synthetic experiments are more informative but mostly at small d.\n\nThis is an honest theory contribution, not a demonstration of a working generative model. It deserves a serious referee: the contraction bounds are new and the proof strategy is reusable. The referee should ask for a score-error propagation section, or at least an explicit statement that the end-to-end claim is not yet theorem-backed. The citation practice is fine; the self-citations are to the Gaussian counterpart the work directly extends. If I were the editor, I'd send it to review, expecting heavy revision on the experimental claims.","headline":"A careful theory paper on binary walk-jump sampling whose contraction bounds are new and sound, but whose end-to-end claim is unproven because the learned score never appears in the analysis.","tokens_in":22007,"tokens_out":2077,"would_cite":true,"duration_ms":20901,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["60J22","60J05"],"pacs":[],"model":"deepseek-v4-flash","headline":"On the hypercube, the optimal denoiser is the sign of the score, and discrete Langevin sampling converges exponentially at high noise.","keywords":["binary data","Bernoulli noise","Tweedie-Miyasawa formula","denoising","discrete Langevin sampling","Boolean hypercube","multi-measurement sampling","Wasserstein convergence"],"falsifier":"For the $d=8$ mixture model used in the paper, compute the exact transition matrix of the two-stage sampler, run it from uniform initialization, and compare the empirical Wasserstein distance to $q_\\alpha$ with the bound $W(q',q)\\le 12d\\sqrt{\\beta_2 d}$ and the contraction rate $1-\\tfrac12 e^{-2/\\eta-2\\beta_1}$ under the stated conditions; a violation at allowed parameters would falsify the quantitative claim. A complementary check is to evaluate a trained denoiser at random averaged inputs $\\bar y_{1:m}\\in[-1,1]^d$ and compare with exact $\\mathbb{E}[x|y_{1:m}]$ for a synthetic prior, testing whether the learned score is accurate where multi-measurement sampling uses it.","tokens_in":20838,"feed_emoji":"🎲","tokens_out":12157,"duration_ms":108584,"temperature":0.7,"pith_summary":"This paper aims to establish that binary data on the hypercube $\\{-1,1\\}^d$ can be learned and sampled without leaving the discrete world. The key move is to smooth the target distribution $p$ by independent Bernoulli sign flips, producing a noisy law $q_\\alpha$, and to prove the identity $\\mathbb{E}[x|y] = (1/\\alpha)\\nabla\\log q_\\alpha(y)$ for $y = x \\circ \\varepsilon$. That identity makes the optimal Hamming-loss denoiser equal to the sign of the score, exactly as the Tweedie-Miyasawa formula does for Gaussian noise, and it turns denoising into score estimation. The paper then analyzes discrete Langevin samplers on $q_\\alpha$, showing exponential Wasserstein contraction at high noise, and a multi-measurement extension that lowers effective noise by averaging several noisy observations at a fixed level. If the claims hold, binary generative models could be trained by logistic-regression denoising and sampled by a fixed-noise Markov chain, with no diffusion time discretization.","feed_headline":"One identity turns binary denoising into score sampling","feed_subtitle":"The optimal denoiser equals the score, so binary generative models can learn and sample without continuous diffusion","key_machinery":"The carrying object is the binary Tweedie-Miyasawa identity $\\mathbb{E}[x|y]=(1/\\alpha)\\nabla\\log q_\\alpha(y)$ for the Bernoulli sign-flip noise model. The score $\\nabla\\log q_\\alpha$ is a continuous function on $\\mathbb{R}^d$ obtained from an exponential tilt of $p$, and its regularity is controlled by $\\|\\nabla\\log q_\\alpha\\|_\\infty\\le \\alpha$ and the $\\ell^1$-Lipschitz bound $\\|\\nabla\\log q_\\alpha(y)-\\nabla\\log q_\\alpha(y')\\|_\\infty \\le \\alpha^2\\|y-y'\\|_1$, which come from $\\nabla^2\\log q_\\alpha=\\alpha^2\\operatorname{cov}(x|y)$. These constants turn the sampling problem into a contraction problem for discrete Langevin kernels, and the multi-measurement variant uses the averaged argument $\\bar y_{1:m}$ to reduce effective noise.","core_discovery":"For the random sign-flip model $y = x \\circ \\varepsilon$ with $\\Pr(\\varepsilon_i=1)=\\sigma(2\\alpha)$, the paper's central identity is $\\mathbb{E}[x|y] = (1/\\alpha)\\nabla\\log q_\\alpha(y)$, where $q_\\alpha(y) \\propto \\sum_{x} p(x) e^{\\alpha x^\\top y}$ is the law of the noisy data, defined for all $y\\in\\mathbb{R}^d$ even though the data live on the hypercube. Hence the optimal denoiser under Hamming loss is $f(y)=\\operatorname{sign}(\\mathbb{E}[x|y])=\\operatorname{sign}(\\nabla\\log q_\\alpha(y))$, and the score can be learned by logistic regression on pairs $(x, x\\circ\\varepsilon)$. For sampling, the paper introduces one-stage and two-stage discrete Langevin kernels and proves exponential contraction in the Wasserstein metric when $4\\beta_2 d e^{2\\beta_1}\\le 1$ (respectively $8\\beta_2 d e^{4\\beta_1}\\le 1$), with $\\beta_1=\\alpha$, $\\beta_2=\\alpha^2$ for the true score; the two-stage sampler has stationary bias at most $12d\\sqrt{\\beta_2 d}$ when $e^{-2/\\eta+2\\beta_1}\\le 1/d$. For $m$ independent noisy measurements, $\\mathbb{E}[x|y_{1:m}]=(1/m\\alpha)\\nabla\\log q_{m\\alpha}(\\bar y_{1:m})$, so the effective noise is $m\\alpha$ while each sampling step stays at level $\\alpha$.","pith_inferences":["Extension: the same exponential-tilt structure should extend to other exponential-family noise channels, where the effective noise parameter would play the role of $\\alpha$; the contraction constants would need to be re-derived for each channel.","Extension: a practical test of the theory is to estimate the Lipschitz constant of trained denoisers at interior points $\\bar y_{1:m}\\in[-1,1]^d$; if it substantially exceeds $\\alpha^2$, the guaranteed contraction regime may shrink and the two-stage advantage could vanish.","Extension: because multi-measurement sampling evaluates the score at averaged points inside the hypercube, training data drawn only from vertices may under-cover that region; generating corrupted-and-averaged inputs during training is a direct way to close the gap."],"forward_implications":["Training a binary generative model reduces to logistic regression on noisy hypercube pairs, with no continuous-time diffusion or noise schedule, provided the learned denoiser approximates $\\nabla\\log q_\\alpha$.","At noise level $\\alpha\\le 1/(4\\sqrt d)$, the one-stage discrete Langevin chain contracts exponentially in Wasserstein distance, so its mixing time is controlled by the rate $1-\\tfrac12 e^{-2/\\eta-\\alpha}$.","With $m$ independent noisy measurements, the denoising error bound improves from $d e^{-2\\alpha}$ to $d e^{-m\\alpha}$, while the sampler can still run at the easier fixed noise level $\\alpha$.","The two-stage sampler has stationary bias at most $12d\\sqrt{\\beta_2 d}=12\\alpha d^{3/2}$ when $e^{-2/\\eta+2\\alpha}\\le 1/d$, which is small compared with the hypercube diameter once $\\alpha\\ll 1/\\sqrt d$; this is the paper's formal analogue of log-concave sampling in Euclidean space.","On binarized MNIST, step size $\\eta=1/\\alpha$ gives fast mixing at $\\alpha=0.5$ and breakdown at $\\alpha=2$, consistent with the high-noise regime the theory covers."],"supporting_citations":[{"why":"Supplies the empirical-Bayes denoising tradition whose Gaussian identity the paper generalizes to Bernoulli noise.","marker":"Robbins (1956)"},{"why":"States the Tweedie-Miyasawa formula that is the Euclidean analogue of Lemma 2.2.","marker":"Miyasawa (1961)"},{"why":"Provides the discrete Langevin transition kernel that the paper's one-stage and two-stage samplers build on.","marker":"Zhang et al. (2022)"},{"why":"Introduces sequential multi-measurement sampling and the log-concavity argument that the binary multi-measurement scheme extends.","marker":"Saremi et al. (2024)"},{"why":"Establishes neural empirical Bayes and the step-size rule, set to sigma squared there and 1/alpha here, that the experiments adopt.","marker":"Saremi and Hyvärinen (2019)"},{"why":"Supplies the Wasserstein and total-variation Markov chain convergence framework used in the proofs.","marker":"Levin and Peres (2017)"},{"why":"Provides the smooth-convex inequality used as the regularity assumption in Proposition 3.4.","marker":"Bach (2024)"},{"why":"Motivates the two-stage Gibbs sampler by showing how to sample from structured high-dimensional distributions with an auxiliary variable.","marker":"Lee et al. (2021)"}],"fun_headline_variants":["Binary denoising equals score sampling","Sign-flip identity bridges denoising and sampling","Bernoulli smoothing yields binary score sampler","Hypercube sampling via Tweedie-style identity","Score function from optimal binary denoiser"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that the denoiser used in practice is close enough to the true mathematical score, with the same boundedness and smoothness, even at points inside the hypercube where it is only trained indirectly; the proofs assume that exact score, while the experiments run with a learned approximation.","fun_headline_variants_meta":{"raw":{"variants":["Binary denoising equals score sampling","Sign-flip identity bridges denoising and sampling","Bernoulli smoothing yields binary score sampler","Hypercube sampling via Tweedie-style identity","Score function from optimal binary denoiser"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000175,"raw_usage":{"total_tokens":1378,"prompt_tokens":1131,"completion_tokens":247,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":747,"completion_tokens_details":{"reasoning_tokens":180}},"tokens_in":747,"tokens_out":247,"duration_ms":3315,"temperature":1.0,"reasoning_tokens":180,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-09T18:34:12.838584+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"For the $d=8$ mixture model used in the paper, compute the exact transition matrix of the two-stage sampler, run it from uniform initialization, and compare the empirical Wasserstein distance to $q_\\alpha$ with the bound $W(q',q)\\le 12d\\sqrt{\\beta_2 d}$ and the contraction rate $1-\\tfrac12 e^{-2/\\eta-2\\beta_1}$ under the stated conditions; a violation at allowed parameters would falsify the quantitative claim. A complementary check is to evaluate a trained denoiser at random averaged inputs $\\bar y_{1:m}\\in[-1,1]^d$ and compare with exact $\\mathbb{E}[x|y_{1:m}]$ for a synthetic prior, testing whether the learned score is accurate where multi-measurement sampling uses it.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the empirical-Bayes denoising tradition whose Gaussian identity the paper generalizes to Bernoulli noise."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"States the Tweedie-Miyasawa formula that is the Euclidean analogue of Lemma 2.2."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the discrete Langevin transition kernel that the paper's one-stage and two-stage samplers build on."},{"cited_title":"W., and Bach, F","cited_arxiv_id":null,"evidence_quote":"Introduces sequential multi-measurement sampling and the log-concavity argument that the binary multi-measurement scheme extends."},{"cited_title":"and Hyv \\\"a rinen, A","cited_arxiv_id":null,"evidence_quote":"Establishes neural empirical Bayes and the step-size rule, set to sigma squared there and 1/alpha here, that the experiments adopt."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the Wasserstein and total-variation Markov chain convergence framework used in the proofs."},{"cited_title":"T., Shen, R., and Tian, K","cited_arxiv_id":null,"evidence_quote":"Motivates the two-stage Gibbs sampler by showing how to sample from structured high-dimensional distributions with an auxiliary variable."}],"review_version":1}