Sampling Binary Data by Denoising through Score Functions
Authors: Francis Bach
Saeed Saremi
Venue: ICML 2025 poster (2025)
Keywords: Langevin MCMC
score function
Boolean hypercube
Bernoulli noise
Primary area: probabilistic_methods->monte_carlo_and_sampling_methods

Abstract: Gaussian smoothing combined with a probabilistic framework for denoising via the empirical Bayes formalism, i.e., the Tweedie-Miyasawa formula (TMF), are the two key ingredients in the success of score-based generative models in Euclidean spaces. Smoothing holds the key for easing the problem of learning and sampling in high dimensions, denoising is needed for recovering the original signal, and TMF ties these together via the score function of noisy data. In this work, we extend this paradigm to the problem of learning and sampling the distribution of binary data on the Boolean hypercube by adopting Bernoulli noise, instead of Gaussian noise, as a smoothing device. We first derive a TMF-like expression for the optimal denoiser for the Hamming loss, where a score function naturally appears. Sampling noisy binary data is then achieved using a Langevin-like sampler which we theoretically analyze for different noise levels. At high Bernoulli noise levels sampling becomes easy, akin to log-concave sampling in Euclidean spaces. In addition, we extend the sequential multi-measurement sampling of Saremi et al. (2024) to the binary setting where we can bring the "effective noise" down by sampling multiple noisy measurements at a fixed noise level, without the need for continuous-time stochastic processes. We validate our formalism and theoretical findings by experiments on synthetic data and binarized images.

Sampling Binary Data by Denoising through Score Functions
Francis Bach
Saeed Saremi? 2
Abstract
chain Monte Carlo (MCMC) a general-purpose class of gradient-based algorithms for sampling from a distribution I in the Euclidean space F whose convergence proper- ties are studied extensively with the assumption that μ is log-concave (Dalalyan, 2017; Durmus & Moulines, 2017; Cheng et al., 2018; Chewi, 2024). Recently, Gaussian smoothing was effectively used for mapping the general problem of sampling in Euclidean space to log-concave sampling (Saremi et al., 2024). Inspired by this line of work, we approach the problem of sampling binary data with "smoothing philosophy," where Bernoulli noise plays prominent role.
Gaussian smoothing combined with probabilis- tic framework for denoising via the empirical Bayes formalism, i... the Tweedie-Miyasan Miyasawa formula (TMF), are the two key ingredients in the success of score-based generative models in Euclidean spaces. Smoothing holds the key for easing the problem of learning and sampling in high dimensions, denoising is needed for recov- ering the original signal, and TMF ties these to- gether via the score function of noisy data. In this work, we extend this paradigm to the prob- lem of learning and sampling the distribution of binary data on the Boolean hypercube by adopt- ing Bernoulli noise, instead of Gaussian noise, smoothing device. We first derive TMF- like expression for the optimal denoiser for the Hamming loss, where a score function naturally appears. Sampling noisy binary data is then achieved using a Langevin-like sampler which we theoretically analyze for different noise lev- els. At high Bernoulli noise levels sampling be- comes easy, akin to log-concave sampling in Eu- clidean spaces. In addition, we extend the se- quential multi- mualiimmeasurementt sampling of Saremi et al. (2024) to the binary setting where we can bring the "effective noise" down by sampling mul- tiple noisy measurements at a fixed noise level, without the need for continuous-tim stochastic processes. We validate formalism and theo- retical findings by experiments on synthetic data and binarized images.
In Euclidean space one can ease the sampling problem by opting for sampling noisy data. In particular, instead of the random variable x, we opt for sampling the random variable y = x + E, where & ~ N(0, o²1) follows a Gaussian distri- bution. This scheme involves single hyperparameter, the standard deviation a. Algebraically, this is akin to sampling from the smoother density Vo of y. which is the convolution of the distribution μ of x with the Gaussian distribution. From a geometric perspective, the noise effectively "fills up" the space with probability mass (the degree of which one controls with o) thus navigating the space becomes easier. One can then "clean up" the mass that is added to the space using denoising. In particular, classical results in statistics (Robbins, 1956; Miyasawa, 1961) state:
E B m] = + o2V log V. (v),
which we refer to as the Tweedie-Miyasee formula (TMF). Note that E[r y] is the least-squares estimator of clean data æ given noisy observation y, and V log Ma is known the score function (Hyvärinen, 2005).
In the generative modeling setting, where the distribution is unknown but we have access to data (z(1) ) one can turn TMF into a supervised least-squares denoising objective for learning the score function of noisy data, where the noisy data y + E, N(0, I) is the input and the clean data the target (Hyvärinen, 2005; Vincent, 201 Saremi & Hyvärinen, 2019). One can then use Langevin MCMC ("walk"") to sample from the learned (v);; the noisy samples can be cleaned with the learned denoiser ("jump"). This sampling scheme was referred to as the walk- jump sampling which we denote by WJS-1 ("1" anticipates the extension we discuss below). There is clear trade-off
1. Introduction
We would like to draw samples from distribution p on the Boolean hypercube {-1, Langevin Markov
Inria, Bcole Normale Supérieure, PSL Research, University, Paris, France Frontieer Research, Prescient Design, Genentech. Correspondence to: Francis Bach franncis bach @ @inria Saced Saremi <saremi. s www.:eencc......
Proceedings of the ndnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Sampling Binary Data by Denoising through Score Functions
here: for higher o, sampling from Vo (y) becomes easier, but the distribution of denoised samples itself goes farther away from u(zz). Despite this trade-off, WJS-1 has proven to be effective in some applications (Pinheiro et al., 2023; Frey et al., 2024; Kirchmeyer et al., 2024).
in Lemma 2.2 we show that
1 V Cx
E E[
log (v))
=
This is essentially the form of TMF for the Bernoulli noise, where crucially the score function appears again. We should emphasize that the score function is well-defined here since 9a (y) has an analytical form (dictated by the exponential tilt) beyond {-1,1) Finally, similar to the Gaussian case discussed earlier we can learn the score function given a dataset {ar() |2-1 by denoising, the subtle difference here is that since x and y are both binary, we can also set up the denoising objective via logistic regression (Section 2.3). Naturally, denoising becomes harder as a decreases, which we can characterize by the Wasserstein distance between the law of x and the law of B[cly] (Lemma 2.3).
The sampling trade-off in WJS-1 is addressed in multi- measurement models (Saremi & Srivastava, 2022; Saremi et al., 2024), in which one is interested in the distribu- tion 1- (V1mm) associated with V1.m == (ya..... 9.m) where yn = =Et A E [wr],, and Ex N(0, o² 1) all independent and independent of x. Saremi et al. (2024) studied a se- quential strategy for sampling from V/ (f):)) and showed that the noise level effectively goes down (as far as the de- noiser is concerned) at the rate a/ /m. Furthermore, if one chooses such that the distribution vo (y1) is log-concave, all the subsequent conditional distributions Vo (1% [91:k k E [m]] remain log-concave. The general sampling problem is therefore mapped to sequence of log-concave sampling while the effective noise goes down via this accumulation of measurements. We refer to this scheme as WJS-m, which involves two hyperparameters: the noise level a, and the number of measurements m. This approach has deep con- nections sampling via diffusion and stochastic localiza- tion (Montanari, 2023). The main conceptual difference is that the multi measurement sampling does not involve dis- cretizing an SDE (Song et al., 2021: Campbell et al., 2022) for bringing the noise down. Fundamentally, this is due to the discrete nature of measurement accumulation.
Our second main contribution in this work is to analytically study sampling from qa (g) using gradient- methods with a formal understanding of the role the Bernoulli noise level plays in easing the problem of sampling binary data. There has been a recent interest on devising gradient- based sampling strategies for discrete distributions from the perspective of Gibbs sampling (Grathwohl et al., 2021), and Langevin MCMC (Zhang et al., 2022). Our approach here is close to the later, where in addition we introduce a new two- stage discrete Langevin MCMC algorithm (Section 3.2), with improved behavior high noise.
Langevin-like updates are especially motivated here on two fronts: (i) the probability mass of noisy data is more spread out on the Boolean hypercube and it demands coming up with Markov moves where many coordinates are updated in parallel (in contrast to "cautious" Linll--corddnnal Gibbs updates), (ii) the score function V log qo (y) is readily acces- sible to be used via denoising and our binary TMF. Regard- ing the first point, we theoretically analyze the contraction properties of the vanilla (one-stage) and two-stage discrete Langevin MCMC, where the noise level a plays a promi- nent role in the exponential convergence of the algorithms. To our knowledge, there is no prior work on the exponen- tial convergence of discrete Langevin-like algorithms in the Wasserstein metric (Propositions 3.1 and 3.3). Furthermore, we extend our contraction results by proving bounds on the distance between the stationary distributions of the discrete Langevin algorithms and the target distribution Ja in the Wasserstein metric (Propositions 3.2 and 3.4). These results again highlight the important role the noise level a plays.
1.1. Contributions
Given this background, we approached the problem of sam- pling from a distribution p(x) on و by devising a smoothing method, with the key restriction to stay on the Boolean hypercube (in this purely binary world Gaus- sian noise does not exist). The natural choice to "smooth" the binary data is to use (isotropic) random sign flips dic- tated by the Bernoulli noise: = x o E, where o denotes the Hadamard (i.e., pointwise) product. The noise e is drawn from the Bernoulli distribution, IP( = 1) = (2xx). where the sigmoid function, and a > 0 is the noise parameter. The probability mass function of the noisy data (y) happens to be transformation of p(x) via an expo- nential tilt governed by exp(ox y). As a decreases, the probability mass gets more spread out on the hypercube, thus easing the sampling problem, where in the extreme case, a = 0, we arrive at the uniform distribution.
For denoising there are subtle differences between the Boolean/Bernouli and Fuclidean/Gaussian setups, where the optimal denoiser f takes values on the Boolean hyper- cube and the Hamming loss is the natural loss. We show in Lemma 2.1 that f takes the form f() = sign(E[<[u]), and
Informally, there are parallels between contractivity results for high Bernoulli noise (small a) and the exponential con- vergence of Langevin MCMC for log-concave distributions achieved for large o in the Euclidean/Gausian case (Saremi et al., 2024, Theorem 1). We make this connection for- mal from the angle of sampling multiple noisy data, where multiple Bernoulli noise is added independently to clean
2

---

Sampling Binary Data by Denoising through Score Functions
data, where the noise level is held fixed. The TMF for the multiple Bernoulli measurements takes the form
where a(u) = I+e- e4/94e-w77 the sigmoid func- tion, and a 3 0 is the noise parameter (the noise decreases with a:). When a is large, ((2x) is close to one, and thus e is the vector of all ones with high probability, and y is close to x: (small noise). When a is equal to zero, then o (2n) = 1/2, and e is uniform, and so is (high noise). Moreover, The ex- pected number of flips is equal to da(-2ex, and goes from d/2 when a = 0 to exponentially fast when a = +o0. We refer to this noise model as Bernoulli noise (in (11,
B c (1:m]
V log Jma (T1sm),
ma
where V1.m Li=t U/. which corresponds to reduced noise dictated by ma (Lemma 2.4).
We conduct a set of experiments on synthetic data, where we study a mixture model on {-1, akin to mixture of Gaussians in Rd. The experiments were designed to quantify denoising for strong and weak priors and probe the sampling properties of our scheme. We also conduct experiments binarized MNIST by qualitatively studying the role of and demonstrate the fast mixing our algorithm can achieve with essentially no tuning (the step-size is simply set to 1/a).
We can write the probability mass function of
r(E) II o (20E,) = II +e (2 aj el i=1
and the probability mass function ga of y defined in Eq. (1) as:
1.2. Related work
(y( = Σ
((x)r(yox)
There is growing body of work on sampling from dis- crete distributions with score-based models that build on denoising diffusion models (Sohl-Dickstein et al., 2015; Hoogeboom et al., 2021; Austin al., 2021; Camphell et al., 2022; Lou et al., 2024; Shi et al., 2024; Kim et al., 2025). There are variations between these models, but they are all fundamentally formulated based on forward/backward continuous time diffusion process for corrupting the data and learning score functions, via denoising, to reverse the process. In particular, Montanari (2023, Section 4.4) con- siders a noise process similar to ours and Pham et al. (2025) show how it can be inverted using Markov jump processes, with denoisers which are similar to the ones defined in Sec- tion2 2. Algorithmically, these continuous-time processes are then discretized using various schemes. Our approach here is fundamentally different with single noise scale sampling strategy: at each stage of measurement accumulation the data is sampled at a fixed noise scale. The process to bring the noise down is therefore discrete by nature, characterized by a single hyperparameter, the number of measurements m, in contrast to devising a noise schedule in diffusion- based prior works.
xE(-1.13
1
Σ
p(z)easTv (2)
(2 (2cohh ad
xE(-1,13"
= x(2a)
Σ
p(z)e 91
arE (=((1111"
since on the hypercube ||0|12 = 1ly11 = d.
When a 0, Ta is the uniform distribution, while for
+00, Qa p. Thus, plays exactly the role of the inverse variance, as can be seen with last expression above that mimics Gaussian noise.
A key observation is that the function qa defined in Eq. (2) is defined for all y E Rdd and not only in (-1, 1jd, so that we can take continuous gradients-not discrete gradients as sometimes done for score matching exten- sions (Hyvärinen, 2007; Meng et al., 2022).
2.2. Denoising
Given the noisy (random) version y E (-1, 13d, how can we recover a good denoised z E {-1,1]<? Like for the Gaussian case, once given a loss function, the opti- mal denoiser has a closed-form expression. We consider the Hamming loss, which has several expressions when x, x E [-1,1]4, as an fn-rr or a squared 8n-nor::
2. Denoising and Binary Score Functions
We consider binary random vector x E 1-,, with probability mass function p(x) (that sums one).
((x, = Σ - = + 1x, x'1 = - - a'Ili
= 1 | 1
2.1. Noise models for binary vectors
It simply counts the number of mistakes, between and d. We then obtain the optimal denoiser from the conditinnal expectation (which extends classical results from binary classification,, see Bach (2024, Section 4.1)).
natural noise model is to use random sign flips, that is,
y= = x 0
(I)
(for the component- wispe product o), where E E {-1, 1]d has independent components, and, for i E {-1...., 17dd
Lemma 2.1 (Optimal denoiser). Given a joint distribution on (x. y). the function f {-1, 1]dd + {-1,1}* that mini- mizes [E( f())) is f(w) = sign(E(r)y)).
P(e; = 1) = =2a),
3

---

Sampling Binary Data by Denoising through Score Functions
Proof. We have:
2.3. Learning the score function
((((,,]()))
Σ p(v)
Σ p(als)(((,,(())) =E{-1,1
In order learn the denoiser, it is natural to consider observations z(1), .(....(")) E {-1,1]" generate inde- pendent noise variables E(")...., {-1.1)* (with P(e)' = 1) = (2x)), and parameterize a denoiser E[zly] = (f(((())
vE(-1,13
and fily) [-1.1) can be optimized independently for each E (-1,1) and i E (1,.... .d), and maximizes D(=ts1 f()1) = -P( = f(())ly). Thus, 1ly) > P(z, = -1yy). which exactly leads to the sign of E[z,|y]- The value of the sign at zero can be taken to be uniformly at random in {-1,1}.
tanh fu(M) R", with thus 2
fi(y) = if 1..
fo (y) of the form 2atanh 1 log qu (v)].
We can learn it through the following denoising criterion (which is exactly logistic regression):
We can now consider the noise model in Eq. (2) from Sec- tion 2.1 and compute the gradient of log qa as
log (1 + exp ( (- x- f0 Sa(z o ()))))
V log (y) Cuel- ExE(-1,1y p(z)eazy
(3)
least-squares objective, 1 Σ Ej= aj ( - go(a()) o ) where the a optimal g(y) is Blalu).
We could also use
which is exactly aBB(rlu)) leading to the following lemma. Lemma 2.2 (Denoising through score functions). For the function qa defined in Eq. (2) for all E Rdd that character- izes the random sign flip model, we have:
2.4. Multiple measurements
Following Saremi et al. (2024), if we assume that we have m
measurements yı,, ym E {-1, 1]d obtained by adding independent noises to the same x, then we have from Eq. (3):
B[rly]
V log (v).
We refer to the function Voo (v) as the score function. It allows to obtain the optimal denoiser by taking the sign. This denoiser has performance that degrades when a goes to zero. We consider the Wasserstein distance derived from the loss E, that is, given two distributions p and 9 111, we consider W (p. g) as the minimum expectation E[E(z, y)] over all distributions on (z, y) with marginals p on x and q on y (Peyré & Cuturi, 2019). The following lemma provides an bound that extends the Gaussian result from Saremi et al. (2024).
E[ ymm
V log Jma (f1mm):
(4)
ma
with 81:m- 1 (y1 + + ym) [-1, Note that this requires to know the function V log Qma beyond {-1, 1)d.
Since the denoiser has to "work" for y & {-1, and for noise levels ma, to learn the score function, we can simply generate multiple measurements and average the corresponding y's (in the Gaussian case, this was possible directly by adding noise with variance divided by m), and use the same denoising objective Section 2.3 (we can also directly sample multinomial random variables to avoid generating m measurements).
Lemma 2.3 (Denoising performance). For the noise model defined in Eq. (2), we have:
W (law of x, law of sign(E(zly))) d2- 2a
Denoising performance. We can extend the denoising performance result when given m measurements by study- ing the sign of 3/1 +... + ym-- This is uniquely defined as soon as m is odd, and when m is even, and yı + + ym is equal to zero, we output -1 or with equal probabilities. We can then extend Lemma 2.3 (see the proof based on Chernoff's s bound in Appendix A).
Proof. We consider the natural coupling with y x where e is independent of x and has independent com- ponents, and simply use the fact that [[ f())) is min- imized exactly by f(y) = sign (H[[ly)) and thus is less than the loss of the naive denoiser that simply outputs da(-2a), which is less than
y, for which ([((x,,)) de 2a
Lemma 2.4 (Denoising performance, multiple measure- ments). For the noise model defined in Eq. (2) and m mea- surements, we have:
Like for the Gaussian case, this bound is true regardless of the strength of the prior on If p(x) is uniform, it cannot really be improved. However, when the prior is strong, better bounds could be derived.
W (law of xz law of sign(E(xlun (.mml,,..,,,,))) & de (a).
with H(a) = 2 log 1ocohhaa 2a > 0 for a > 0, is equivalent to f2 a tends to zero, and to a - log 2 when a tends to infinity.
Note that as opposed to Gaussian noise, the denoising per- formance goes exponentially to zero when a grows.
4

---

Sampling Binary Data by Denoising through Score Functions
Score functions for sequential sampling. Extending the Gaussian case, multiple measurement can be efficiently sampled sequentially. If we want to sample 3/m given y1...., Vm-1 using score functions, we have the joint prob- ability mass function:
Algorithm 1 The single-measurrmment one-stage discrete
Langevin algorithm.
Parameter: noise level
2: Input: steps count n, step size 1, score function 8n.
3: Output: X
4: Initialize Y, E {
ea (mm+++)))))
5: for i = 1 to n do
p(y1, Vm)
Σ =E1-1,134
p(x))
(2 (2cohh a )dm
6: Z <- Yi-1
7: E + fernouli((((21122aaa
{-1,11)
Y, < Zoe
end for
with
Ym
log (ii.:.(......................1.. Bm))
10: return X = sign (sa (Yn)/a)
= E LeE(-1.1) p(z) p( (In (mm++tum))
Exe(-L.1j p(r) e T (vi (1mm))))))))))
by Zhang et al. (2022), which is adapted log-probability- mass functions that defined on Rd:
= 1 V log qma (Fimm)
which depends on the score function with parameter ma, taken at fi.m E [-11, 1] (as mentioned earlier we are able to learn score functions for elements in the interior of the hypereube).
t(y/l)) exp (f (2) y) 2n 1 - v11)) x exp((s + 4)) 'vy)
(6)
which given y, has independent components for y'- Note that without the constraint that y/ E {-1,1]", the first expression above becomes y' = y }o(y) (o((y)+N(p +N(, n/), i.e. exactly (Gaussian) Langevin MCMC.
3. Sampling with Discrete Langevin
We need to sample from the model in Eq. (2), for a prob- ability mass function q which is defined not only on all y E [-1 but on Rd, for which we only know s(y) = V log (vy)- This is the same for conditional sampling from Section 2.4.
As opposed Gaussian Langevin, even with vanishing step-size 1). the stationary distribution of this Markov chain may not approach We can however prove convergence results that are adapted to our situation.
Assumptions. Note that the density q is uniquely defined up to constant for vertices of the hypercube, but that there are multiple versions on the whole hypercube. In particular, one can add the score any linear function (and there are additional invariances).
Convergence results. We now provide two propositions characterizing the convergence of the Markov chain defined in Eq. (6); see Algorithm The first proposition below implies an exponential convergence of the Markov chain (which is not studied by Zhang et al. (2022)). See the proof in Appendix B, based on standard contraction arguments.
We will use the following regularity conditions on that are satisfied by defined in Eq. (2), that is, for all y' E Rdd
Proposition 3.1 (Contractivity). Assume regularity condi- tions in Eq. (5) with 4B2de291 < 1. Given y, E {_1, we have, for the transition kernel defined in Eq. (6):
> < Br, and ||<()) - s0/))ll & B2lly- - v'l (5)
((((-l)) < 2 # > 2).
These assumptions are akin to regularity assumptions made in optimization on the gradient functions, here adapted to the binary case. For the function q defined in Eq. (2) and the associated (this is direct consequence of taking another derivative in Eq. (3), leading to V log (y) a² cz<o))zly)) The same bounds hold for sequential sampling from Section 2.4 (thus benefiting from the same speed as a small a while denoising has the same performance as ma))
We note that when B1 = and 83 a², the constraint becomes 4a 2e < 1 and is satisfied as soon as a < 4 (since then we have 22a < 2), without any assumption about the distribution we want to sample from.
V log 9. we have 31 = and B2 a²
From the previous proposition, we deduce that for each n > 0, the Markov chain always converge exponentially fast to the unique stationary distribution for the Wasserstein distance (Levin & Peres, 2017). Given the exponential rate in 2 ee 22/m-o we can choose a step-size v = 1/a without losing too much in mixing time (this extends the strategy of Saremi & Hyvärinen (2019) in the Gaussian case,
3.1. One-stage discrete Langevin sampler
In order to obtain an approximate sample from q, we consider the following Markov transition kernel proposed
5

---

Sampling Binary Data by Denoising through Score Functions
Algorithm 2 The single-measurremen two-stage discrete
for which the conditional distributions can be computed as
Langevin algorithm.
g(aly) (2 , 1 cto
Parameter: noise level a
2: Input: steps count n. step size 7/, score function Sa
g(vl=) x ((y)e
3: Output: X
4: Initialize Yo E {-1,11d
which we approximate by expanding log q(v) log q(2) s(z) (u =), leading to:
+
5: for i = 1 to n do
6: + Bernoulli(o(2/n)) E {-1,1)
u(:ly) (<>ly) (2cosh 2 eem e t
7: + Y
(8)
8: : =t Bernoulli 22 sa sa(2)) E {-1,1]
u(vlz) a(2)e Vlog a(=) (0-=) 11v=
9: Y + oos
10: end for
o (++a()))
99)
11: return X = sign (Yn)/a)
Thus the Markov chain (with transition kernel v) defined by Gibbs sampling to go from y to y' is defined as follows: take z with a random flip with probability 1 - (2/n)) and then perform independent (non mon--unffrmm flips with probability 1-o (2/n + (2)s obtain 2'; see
where the step-size for the Langevin algorithm is taken to be the noise variance).
see Algorithm 2.
We now show that the stationary distribution of the Markov chain defined by the transition kernel l cannot be too far from the one of y. See the proof based on comparing to Metropolis-Hasting steps in Appendix C. Note that Zhang et al. (2022) only study the situations where the log-density is quadratic (or close to quadratic) without explicit constants, and without results on mixing time.
Note that without the constraint that v/ E {-1, the overal update becomes y = +ss)) + N(0, 2n/). i.e. exactly (Gaussian) Langevin MCMC with a step-size size twice bigger than the single-stage sampler.
Convergence results. When log logy(y) is linear in y, then the proposals defined by u are equal to the ones defined by g (and thus the stationary distribution is exact). Otherwise, we can show the following contractivity result (see the proof based on contraction arguments in Appendix D).
Proposition 3.2 (Distance to stationary distribution). As- sume regularity conditions in Eq. (5) with 482de281 < 1. Let of be the stationary distribution of the transition kernel defined in Eq. (6). Then,
Proposition 3.3 (Contractivity, two-stage sampler). Assume regularity conditions in Eq. (5) with 8d,3c4 & 1. Given y0, E {11,1] 13d, we have, for the transition kernel v defined in Eq. (8) and Eq. (9):
w(d's < 2d(2d + vd3re20.).
W (()(-ly(2)) (0 & (1- 2
In our situation where 31 = and B, = a² this is small compared to the diameter d of the hypercube (its maximal value) only when a is small compared to 1/d. Note that the step-size 77 does not appear directly in the bound in Eq. (7), but it is too small, because of Prop. 3.1 the mixing time will be large (this also applies to Prop. 3.4).
Like in Section 3.1, this leads to exponential convergence to a unique stationary distribution. We can now look the distance between the stationary distribution of the Markov chain and 4. We make the assumption that the score that we use satisfies the usual inequality of convex smooth functions (Bach, 2024, Section 5.2), that is, for all y, E {-1,1]
3.2. Two-stage Langevin sampler
The default Langevin sampler does not have the nice prop- erty that if (v)) x ex y for some E Rd (i.e., independent components), then the stationary distribution is exact.
< log q(v) llog ((=)==(=) (y (y-2) 2) <
B2 11 yy 211.. (10)
2
which is satisfied by syy) = V (vy) in Eq. (2). See the proof of Prop. 3.4 based on comparing to Metropolis- Hasting steps in Appendix E.
Following the continuous-space algorithms from Lee al. (2021); Chewi (2024), we consider instead the idealized two-stage sampler defined below, which is Gibbs sampling for the joint model on (y,2) in 13 131.
Proposition 3.4 (Distance to stationary distribution). As- sume regularity conditions in Eq. (5) and Eq. (10) with 48 & 1. Assume 22/++20. < 3-2 Let o' be the stationary distribution of the two-stage sampler. Then,
(2 cosh bid peeeuuu Tu q(v)etv'=
1
2) 9(v)
W .4) $ 12d B2d.
6

---

Sampling Binary Data by Denoising through Score Functions
Algorithm 3 Multi-meassurmmen binary sampling via single- stage discrete Langevin algorithm (Alg. 1) in the inner loop.
terms of mixing time of Langevin, for the Gaussian case (e.g., when sampling by adding Gaussian noise), the known upperbounds based on log-concavity obtained for Gaussian mixtures by Saremi et al. (2024) is a & a' which is signifi- cantly worse than our two-stage sampler.
Parameter: noise level a
2: Input: number of measurements m, number of steps per measurement n. score functions (Sa )
3: Output: X
4: Initialize Y <-0 0
5. Experiments
5: for t = 1 to m do
6: Initialize Yo E 1-
We now study how new sampling scheme operates, first synthetic data to understand the role of the noise parameter and step-size 7), then on binarized MNIST digits.
7: f 1 to n do
8:
Z ++Y Y (Y1-1 Y)/t
9:
E Bernoulli(a (2/n + Y,-1 seal (Z)/t))
10:
+ Y----108
11: end for
5.1. Synthetic data
12: Y + (Yn - -Y/t
We consider in this section mixtures of two independent binary vectors, that is, we consider, for 3 > 0,
13: end for
14: return X == sign (sma (F)((m))
p(x) = cosh 3y² [2 e1 2 + -0-00
BI
Moreover, as shown in Appendix E, if the step-size 1) is small enough, we get a dependence in d d132.
for which all score functions can be computed (see Ap- pendix F). When 3 is small, p is close to the uniform distri- bution (a "weak" prior), while when 3 large, p is close to sum of two Diraes at opposite points in the hypercube (a "strong" prior).
For our problem where 31 = a and B3 = a², the constraint in 1 leads mixing time proportional d, but to a dis- tance to the true distribution 9 proportional d and or d-o i as opposed to d /od for the ste-stage sampler, thus an advantage for small a (high noise), where we only need < 1/ /d instead of a < 1/d for one-stage sampling.
For d small (d = 8 below), it is possible to perform all com- putations in closed form (e.g.. with infinitely many repli- cations), by computing transition matrices of size 24 x 2d. This allows to analyze precisely the denoising performance.
For completeness, we also provide the multi-measurement binary sampling algorithm in Alg. 3.
Denoising performance with exact samples from y. In Fig. 1, we consider three values of 33 and vary a. As ex- pected, when a decreases, the noise increases, and the de- noising performance degrades. When / is large, the prior has strong effect, so denoising helps. When 8 is small, the prior is not strong, denoising has little effect. Note also that when is large, denoising simply outputs y (the threshold where it happens depend on the strength of the prior).
4. Comparison with Gaussian Noise
An alternative is to add Gaussian noise and define
yG = x =, N(O, L.).
We then have E[z[ya] ya a V log q (yG), from the classical Eweedie-Miyasen formula, with da the density of yo:
Morcover, since the upper bound in Lemma 2.3 obtained from the meaa-square--rrrr, it shows that the denoising performance is significantly better than the bound suggests.
dh (BG) & Σ p(z)eaxTvv Te ve- -1oll 1
mE(-1,13"
& Σ p(z)e we 11lll x qa (yc)e #11e11
== 0.50
y= 1.00
# 2.00
(r(ry))
W 50
=Ef-1.11
(c. Rig))
Wir. Wix.R(p))
WL. Willll
MSSE vil
-.... M.
3
..... MMSP P(pp))
-.....
-.... 31SELr, #ia)]
where qa is the density of the binary case defined in Eq. (2).
2
22
2
Thus,
E|Z|y]] = 1 V log ga (va),
1
2
0
11
that is, the exact same denoiser function (now applied to element of Rd and not (-d,
[ogg/(a)
[o]
[ogg(()
Figure 1. Optimal denoising from strong priors (large (8) weak priors (small 8): comparison between Wasserstein distance and mean-square-emee error of denoising performance.
In terms of denoising performance, for the same a, we see in our experiments that they behave similarly. However, in
7

---

Sampling Binary Data by Denoising through Score Functions
Denoising performance with multiple measurements. In Fig. 2, we assess the benefits of multiple measurements by showing how the Wasserstein distance between our de- sired (noiseless) distribution on I' is estimated more closely by optimal denoising from m measurements when m is increasing, in particular for small a (high noise).
equal to 1/a, and plot the Wasserstein distance to the dis- tribution of for our two samplers. When a is large, the stationary distribution is far from the one of y, with bad per- formance. With a small, then the denoising performance is not great because too much noise is added. When /3 is large (right plot), there is a clear sweet spot. Moreover, the two- stage sampler only provides improvements for small a's.
0
0.50
P 1.00
2,00
0.-
1.5
Fis 3
Wix, sigo
Wien Rtail
Hla!)
Hlpl)
0.50
8 1.00
3 2.00
0.8
W(y Meea)
0.6
1-stage
2-stage
W (g: Blean)
1.5
1 sttae
stage
W (g. tbea))
1 1-stage 2-stage
0.2
0.4
0.5
0.2
0.5
2
0
2
0
(m)
(ogg/())
log,
0
2
4
0
2 loog (a)
Figure 2. Optimal denoising from multiple measurements, for
logg(() (a)
logg(a))
m = 1, 3, 5 (one curve per m), for d = 6, and three values of 33 from strong priors (large 3) to weak priors (small (8).
0.8
1-dtago
((r,, ((y))
0.6
W 11.2999
1.5
2-stagge
W (z, 20012
2-stage
1-stage
0.1
stage sstage
true
Comparisons of mixing times and distance to station- ary distribution. We compare our two sampling schemes (one-stage from Section 3.1, and two-stage from Sec- tion 3.2), and study the associated step sizes in terms of distance between the stationary distribution of the Markov chain and the desired distribution, and mixing time, which is here characterized by 1/(1 X2), where A2 is the sec- ond largest eigenvalues of the transition matrix, classical characterization of mixing time (Levin & Peres, 2017).
0.2
0.5
0
2
2
[ogg((x)
(ogg(a)
(ogg(())
Figure 4. Comparison of I Isstge and 2-stage Langevin sampling. Top: distance to desired distribution W yaaa), bottom: de- noising performance of the stationary distrihutions, measured in Wasserstein distance.
5.2. Binarized MNIST
We see in Fig. 3 that when the step-size 1) is too small, the mixing time explodes for all schemes (as predicted by Props. 3.1 and 3.3), and that for r) = 1/ar we obtain reason- able mixing times.
In this section we present our experiments on MNIST (Le- Cun et al., 1998). The clean binary data were prepared by scaling the pixel values be in [0, 1] which we set as the prob- ability of the Bernoulli distribution. The denoising is set up using logistic regression as outlined in Section 2.3, where we parametrize fo using the U-Net architecture (Ronneberger et al., 2015) with the modifications by Dhariwal Nichol (2021). For optimization, we used Adam (Loshchilov & Hutter, 2019) with the constant learning rate of 10-4 and the weight decay of 10 10-2, We present our experiments for a E {0.25, 0.5. 1, 2} in Figs. 5 and 6.
0.3, B 2.0 a = 1.0, 3 = 2.0 a = 2.0, 3 = 2.0
0.6
I-stagg
1-stago
1 1-stago
(1/ MAtus)
0.4
2-staage
Wy yeta))
2-atage
Wi, yeae))
1.5
0.5
0.2
0
-2
2
-2
-2
0
loga (tpx))
(nns)
logg(raa)
Aa)
60
1-stage 2-stage
1-stage 2-stage
logao A0)
10
1-stage 2-stage
2
Denoising performance. Fig. 5()) shows 20 random bi- narized samples from the test set. Fig. 5 (b-d) shows the denoising performance of a trained model for very high noise, a = 0.25, where we show both B[x w). parametrized as tanh (v())22) (see Section 2.3) and sign (B[a]y)) which is optimal under the Hamming loss. In Fig. 5 (e-g) we re- peat this experiment for trained model at lower noise level a = 0.5. Qualitatively, this is sweet spot as the noise is high, yet the denoising performance is acceptable. Note the "5" flipping to "3", and "3" flipping to "8" by the de- noiser due to the high noise. This already anticipates the fast mixing that could be achieved at this level of noise.
loga (1
1
-2
0
Togg (1)ce)
logg (1)))
1ogg(
Figure 3. Comparison of 1-stage and 2-stage Langevin sampling- Top: distance to desired distribution W W(y, ), bottom: mixing time (in log scale).
Denoising performance with samples obtained by dis-
crete Langevin. We consider in Fig. a learning rate
8

---

Sampling Binary Data by Denoising through Score Functions
7 0 4 1
(a) x from the test set
(b) y = ==zDE,
0.25
(a) two-stage discrete Langevin (Ak
1),
0.5, = (2a)
7 1 72109777 9 9 1 3
(c) B|ayyl 0.25
8
8
3
8
8
8
g
8
8
8
9
9
5
6
5
5
5
5
8
8
3
2
8
3
8
8
3
6
7 9 "
9 3
6
6
6
5
5
5
5
5
8
5
6
6
6
4
6
6
3
3
2
2
2
2
2 Q
(d)
0.25
a
a
2
6
7
8
8
2
2
(b) denoised samples,
0.5
(c)
0.5
0
0
0
0
0
O
6
3
5
3
8
8
8
&
8
2
8
7 0 / Y 9 5 00044//8990900999000
5
9
7
3
3
7
9
2
9
5
5
5
5
5
5
7
5
9
9
7
9
9
9
0
( E[ a a
0
6
6
6
6
6
7
9
5
7 2. / 0 4 / 7
6 0
8 9
9
4
4
4
4
(c) single-stage discrete Langevin (Ak = 1), 0.5,
1/0
(g) sign E[ m]). , a 0.5
Figure 5. The denoising performance binarized MNIST at two high Bernoulli noise levels (a 0.25, and a = 0.5).
(d) single-stage discrete Langevin (Ák 5),
2 2
2
Sampling performance. Fig. 6 (a-f) illustrates the mixing performance of our algorithm for various noise levels. The step-size is set to 1/ in all experiments. All panels show 100 steps of the algorithm, where the sampler is initialized at random bits. In Fig. 6 (a-c) we see the performance of the algorithm in "real time", where all the steps are shown (Ak: = 1). These results show the remarkable mixing our algorithm can achieve. Fig. 6 (d-e) shows the typical perfor- mance of the algorithm for smaller noise a = where the samples sharper but there is less mixing; here the results are shown by skipping steps (Ak=5). 5). Finally, in Fig. 6(f) we see the sampling performance for smaller noise (a = 2), where the sampling algorithm simply breaks down.
(c) single-stage discrete Langevin 5), 1, denoised
(f) single-stage discrete Langevin (Ák 5),
Figure 6. The sampling performance of our algorithm for binarized MNIST three Bernoulli noise levels, visualized on single Markov chains (viewed left right, top to bottom). (a) Two-stage discrete Langevin a = 0.5, (b) the denoised samples are shown, (c) to space only denoised samples are shown for the vanilla (single- stage) algorithm, (d,c) here, a = 1, and we skip every 5 steps, (f) 2, denoised samples not shown as the noise is small.
6. Conclusion
This study was motivated by whether reproduce the success of sampling through denoising while staying within the binary world. This required to reproduce the three key factors: (i) denoising through score functions, (ti) sampling noisy data via "smoothed" score functions, (iii) benefiting from multiple Bernoulli measurements. We achieved three in an algorithmically simple framework, which comes with few hyperparameters (noise level and number of measurements) and arguably simpler formalism than discrete diffusions.
complex ones; (2) sharper denoising results for strong priors could also be examined; finally, (3) faster sampling could achieved through the proper use Metropolis-Hastiing step (Robert & Casella, 2004).
Acknowledgements
We thank Armand Gissler, Alain Durmus, Dario Sharia- tian, and Eliot Beyler for discussions related to this work. This work has received support from the French govern- ment, managed by the National Research Agency, under the France 2030 program with the reference "PR[AIJRIE-PI PSAI" -NN-233-ACCL-00
There are several avenues for future research: (1) our frame- work relies on using a noise process from an exponential family (here, Bernoulli) and can readily be extended to more

---

Sampling Binary Data by Denoising through Score Functions
Impact Statement
Hyvärinen, A.
Estimation of non-normalized statistical models by score matching. Journal of Machine Learning Research, 6(Apr):695-709, 2005.
This paper presents work whose goal is to advance the field of machine learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
Hyvärinen, A. Some extensions of score matching. Com- putational Statistics & Data Analysis, 51(5):2499-22 25122 2007.
References
Kim, J. H.,, Kim, S., Moon, S., Kim, H.,, Woo, J., and Kim, W. Y. Discrete diffusion Schrödinger bridge matching for graph transformation. In International Conference on Learning Representations. 2025.
Austin, J., Johnson, D., Ho, J., Tarlow, D., and van den Berg. R. Structured denoising diffusion models in discrete state- spaces. In Advances in Neural Information Processing Systems, 2021.
Kirchmeyer, M., Pinheiro, P. O., and Saremi, S. Score-based 3D molecule generation with neural fields. In Advances Neural Information Processing Systems, 2024.
Bach, Learning Theory from First Principles. MIT Press, 2024.
Campbell, A., Benton, J., De Bortoli, V. Rainforth, T., Deligiannidis, G., and Doucet, A. continuous time framework for discrete denoising models. In Advances in Neural Information Processing Systems, 2022.
LeCun, Y., Bottou, L.,, Bengio, Y., and Haffner, P. Gradient- based learning applied to document recognition. Proceed- ings of the IEEE, 86(1 11:2278-23244 1998.
Lee, T., Shen, R., and Tian, K. Structured logconcave sampling with restricted gaussian oracle. In Conference on Learning Theory, 2021.
Cheng, X., Chatterji, N. S., Bartlett, P. L.,, and Jordan, M. I. Underdamped Langevin MCMC: A non-asymptotic anal- ysis. In Conference on Learning Theory, 2018.
Levin, D. A. and Peres, Y. Markov Chains and Mixing Times. American Mathematical Society, 2017.
Chewi, S. Log-concave Sampling. Book draft, 2024. URL ht attps:: / chewisinho. github..h.......... io //o/man.... pdf.
Loshchilov, I. and Hutter, F. Decoupled weight decay reg- ularization. In International Conference on Learning Representations, 2019.
Dalalyan, A. S. Theoretical guarantees for approximate sampling from smooth and log-concave densities. Jour- nal of the Royal Statistical Society. Series B (Statistical Methodology), 79(3):651-61) 2017.
Lou, A., Meng, C., and Ermon, S. Discrete diffusion mod- eling by estimating the ratios of the data distribution. In International Conference on Machine Learning, 2024.
Dhariwal, and Nichol, A. Diffusion models beat GANs on image synthesis. In Advances in Neural Information Processing Systems, 2021.
Meng, C., Choi, K., Song, J., and Ermon, S. Concrete score matching: Generalized score matching for discrete data. Advances in Neural Information Processing Systems, 2022.
Durmus, A. and Moulines, É. Nonasymptotic convergence analysis for the unadjusted Langevin algorithm. The Annals of Applied Probability, 27(3):1551 1587, 2017.
Miyasawa, K. An empirical Bayes estimator of the mean of a normal population. Bulletin of the International Statistical Institute, 38(4):181-188 1961.
Frey, N. C., Berenberg, D., Kleinhenz, J., Hotzel, I., Lafrance- J., Kelly, R. L., Wu, Y., Rajpal, A., Ra, S., Bonneau, R., Cho, K., Loukas, A., Gligorijevic, V., and Saremi, S. Protein discovery with discrete walk- jump sampling. In International Conference on Learning Representations, 2024.
Montanari, A. Sampling, diffiusions, and stochastic localiza- tion. arXiv preprint arXiv:2305. 2023.
Peyré, G. and Cuturi, M. Computational optimal transport: With applications to data science. Foundations and Trends in Machine Learning, 115--6)3555607, 2019.
Grathwohl, W., Swersky, K., Hashemi, M., Duvenaud, D., and Maddison, C. Oops I took a gradient: Scalable sam- pling for discrete distributions. In International Confer- ence on Machine Learning, 2021.
Pham, L.-T.-N., Shariatian, D., Ocello, A., Conforti, G., and Durmus, A. Discrete Markov probabilistic models. In International Conference on Machine Learning, 2025.
Hoogeboom, E., Nielsen, D., Jaini, P., Forré, P., and Welling, M. Argmax flows and multinomial diffusion: Learning categorical distributions. In Advances in Neural Informa- tion Processing Systems, 2021.
Pinheiro, P. O., Rackers, J., Kleinhenz, J., Maser, M., Mah- mood, O., Watkins, A. M., Ra, S., Sresht, V., and Saremi, S. 3D molecule generation by denoising voxel grids.
10

---

Sampling Binary Data by Denoising through Score Functions
In Advances in Neural Information Processing Systems, 2023.
Robbins, H. An empirical Bayes approach to statistics. In Proc. Third Berkeley Symp., volume 1, pp. 157-163, 1956.
Robert, C. P. and Casella, G. The Metropolis Hastings algorithm. Monte Carlo Statistical Methods, pp. 267-320, 2004.
Ronneberger, O., Fischer, P., and Brox, T. U-Net: Convolu- tional networks for biomedical image segmentation. In International Conference on Medical Image Computing and Computer-assisted Intervention, 2015.
Saremi, S. and Hyvärinen, A. Neural empirical Bayes. Journal of Machine Learning Research, 20(181):1-23, 2019.
Saremi, S. and Srivastava, R. K. Multimeasurement gener- ative models. In International Conference on Learning Representations. 2022.
Saremi, S., Park, J. W., and Bach, F. Chain of log-concave Markov chains. In International Conference on Learning Representations, 2024.
Shi, J., Han, K., Wang, Z.,, Doucet, A., and Titsias, M. Simplified and generalized masked diffusion for discrete data. In Advances in Neural Information Processing Systems, 2024.
Sohl-Dickstein, J., Weiss, E., Maheswaranathan, N., and Ganguli, S. Deep unsupervised learning using nonequi- librium thermodynamics. In International Conference Machine Learning, 2015.
Song, Y., Sohl-Dickstein,
J., Kingma, D. P., Kumar, A., mon, S., and Poole, B. Score-based generative modeling through stochastic differential equations. In International Conference Learning Representations, 2021.
Vincent, A connection between score matching and noising autoencoders. Neural Computation, 23(7):1661- 1674, 2011.
Zhang, R., Liu, X., and Liu, Q. line sampler for discrete distributions. In International Conference on Machine Learning, 2022.

---

Sampling Binary Data by Denoising through Score Functions
A. Proof of Lemma 2.4
We denote E &m E 1- the m independent noise variables defined in Eq. (I), We assume that m is odd for simplicity. The case m even can be done similarly by splitting the case where Σ E 0.
Following the same reasoning that in the proof of Lemma 2.3, the Wasserstein distance is less than d times the probability that -i=1(Es), < O. Since (s,)1 2u, I where u, is Bernoulli random variable with parameter o(2x) E [1/2, 1]. We need to upper bound, using the Chernoff bound, the following probability as:
m
Uc 2)
exp(-m D(510(2))))
m71
where, for > 0, the Kullback- Leibler divergence between the uniform distribution and the Bernoulli distribution with parameter (2ax) is equal to:
D( 1
1
1
1
(2(())
log
log
20
(2x)
(-
1
1
++e* e2a
+ (2a)
log
log
log
2
2
2
which is always strictly greater than zero for a > 0, equivalent to llog 2 for large and to _ for small a.
B. Proof of Proposition 3.1
Proof. We consider two random variables y' and z' marginally distributed from ((-ly) and ((-|z). We have, by definition of the Wasserstein distance:
d
*(((l)),
inf
Σ
P(l! + 2/) by definition of W,
joint coupling
inf marginal coupling
PP(1/ * z
(11)
1=1
because we can construct canonically a joint coupling from marginal couplings,
PP/// 1 1) because of properties of total variation,
d
= o Yt + s(y))) +
(12)
by definition of the transition kernel in Eq. (6). For proprieties of the total variation distance, see https: wikipedia. variation
org/w Maiikk//otaal htte//otaaaaaaaaiiaaaaaaaaaaa variation..distnnee.ee.o.. distance probabi lity measures. We can then separate i's according to y, 2 or y/ A to get from Eq. (12):
((((1b))((12))
Σ i
(a(-y) yi s(y))) of c222, + s(2);)
a ( ys + s(y))) a 2 + s())))
'See wiki http://:///ee...ppppp/a/////////
12

---

Sampling Binary Data by Denoising through Score Functions We can now divide in two cases, whether y; = 1 or +1, leading to
((1())))
la
( Yi + s(y),)
2
( 11
2 2, + s(x)))
11
la( (1 y1 + s(y),) o 2 2 + s(2)))
Σ
+
Σ
o (1 y1 + s(y),) of 2 + s(z),)
-ル=====
Σ
|a( y1 + s(v).) 0 2 2i + s()),)
+
17
-1--
Σ
0
(- + s()).) - o 2 + s(2):)
1,3 =
|o( + +(y))) - -o( 2 + +c)))
Σ
+
1/
"
Σ
0 2 1
+ +())) - -o( 1
2 + +2)))]
+
Σ
|a(
2 + +(y))) o 2 + +z))))
11
We can now use the facts that a--u) = 1 (u), and that for u, o' > u, d'l) = (()) v) = 22te=400 & 2n0us and
thus, by Taylor's formula, (o(v)- - a(u')) < 2te= |0 - 2l1. to get
((())))
Σ 2 + exp
1
((()); - -(())l
( - 31)
+ Σ 1 , 1a(2
2
2
+ yio(y))) - -o( - - - -)oo())))
2
1)
We can now use the monotonicity of a and the bounds || loc ||s(2]] &B,, and the 32 Li-Lipschizz-comiiiitt of s (all from Eq. (5)) to get
1 282((y,2) z)
((())))
<
+ exp ( 31)
(0l 1)
+ Bi) -o(-2 2 -2__9)) Bi))
11
2 - -B11)] Ely. 2)
22 2) +11 - 20 -
1-1-200
2 + exp
2 - 31))
1)
77
282d
2
+1 1 exp
-(yy,) 2)
2 + exp
(
- -1))
( + 31)
[1 exp ( (-
2 2- -1)) + 2,32d exp ( 1 + +ii] e(y,2). 2).
(-
17
If 4,32de28: < 1, then 2xp (- + Bi) < 3 exp ( ( 2/2 - 31), and we get the desired result:
((((-1))+t(12)) & (1-}
2 exp (- --)) ((g. 2).
13

---

Sampling Binary Data by Denoising through Score Functions
C. Proof of Proposition 3.2
Proof. For the purpose of the proof, we consider adding on top the transition kernel Metropolis-Hasting (MH) step (see, e.g., Robert & Casella, 2004) that keeps the proposal y' given y unchanged with probability
min {1, do (v)
(13)
and go back to y instead. The stationary distribution associated with this transition kernel then exactly q-
We consider an arbitrary probability distribution
We consider two coupled samples y from and from q, that W W(r, q) = Ele(y, 2)]. We also assume that, given y, the binary vectors z' are sampled jointly respectively from E(-ly) and 6(-12), so that the Wasserstein distance given y. between the distributions t(-l9) and t(-1z) is W (t(-lv), = B[e(y', (10()/=2'\lu.> 10) We consider =" obtained from z' by a Metropolis- step; 2" is then marginally distributed from g, while y is marginally distributed according to Σ Eue(-1,y r(u)t(-lu). Thus, by definition of W as the loss for the optimal coupling, we have:
w( Eue(( ((u))))
< Blé(y/ x = = E[ (ccc v')l + 2e ((2", ,/))
Lacceepptss ((='))(((' + roj (2, v')] by definition of the MH step,
accopttp( [(', 1/ B [1 rojoct (((2)) E(2', (2)) by the triangular inequality,
E[[(E', //')l + + [[(1r
exp (- 31) W ((: g) + ((2
2
from the convergence result in Proposition 3.1. We have, by definition of the accept probability in Eq. (13),
E (
Σ
(=) min {1, {())((<112)
(14)
2 -
(15)
with the transition kernel defined in Eq. (6), that is,
(2))) (<'l=)) x (cp(G 17
In order to prove convergence result, have understand under which condition we obtain approximate detailed balance condition (Levin & Peres, 2017). This will be consequence of being small (e.g., here, V log g(z) small).
We define the two additional transition kernels and distributions
i(=1|z) x exp ({=))=) ((z) x 1,
for which we have the detailed balance condition ((2)((='12) - 0(x ((x'){(212)) = 0. We then get, from Eq. (15) and the triangular inequality,
[L ((,,,2) <
[ ((2)1 ((2112) + Σ (<<(,))(()) (f(2112) +(>1lz)),
2,3
14

---

Sampling Binary Data by Denoising through Score Functions
using detailed balance for q and i. For the left term, use the symmetry of i and explicit computation, to get
Σ ((. =))((()) [(=)l f(2122)
Σ (<()) [(2)
Σ ((<1La)e(2''11)
Σ (2)2) -(22) Σ {(2) 1111a) since E(-1La) has independent components.
< 2do(-2/n)TV ④) < 2dexp(-22 (erppp2//)VV(/.... Q),
where TV 1) - E. [a(2) - d(=)] the total variation distance between and q. For the second term, we have Σ f 2)(()) 10(=1=)) <(=1l=)
max Σ ((s'. (<((=)))((=11)) t(='l=)
d. max
(<<'\>) since ((.-)) & d.
4d
< d
2+ 2/1--11
We have used the small lemma for the two probability mass functions on {-1, 1)dd proportional to A(y) & eaTa and
Byy) e To E, (A()) B(y)l & z (2a,) (2b;)) & 2 d
Diml 3mexp(min (4 - b,l-
2
Overall, we get
W (uee--nn
(1 (1-
( desp:)))))d(((((///ve +d.
(- 2 7
2d31
62/1-B1
Thus, a' denotes the stationary distribution of the Markov kernel f, we get, applying the above inequality t d'
w(d'9)) < (1-2 exp ( - _ - - (())
2d3
dv + d. 62/n-31
leading to
W 9) < " Q) 4d 3
We can now use Pinsker's inequality?, to get:
( (()())) 1/2
-(5 Roo log 1 1/2
TV(a.
6 Ee ((2)) B1ll2 zull1 - log 201) 1/2
using the boundedness of s,
( 1e - -
1/2 < Bid,
by choosing 2 such that ((z)) < 1 (there has to be one). We thus get the desired result
Wid. g) < 8d BBid + 4d 3 28, = 2d(2dBie 20h + ed3.
D. Proof of Proposition 3.3
Proof. We can reuse the proof for the one-stage sampler to obtain the contractivity of the second step of the two-stage sampler (updating the fact that we have no 1/2 factor) to get a contracting rate
[--exp exp (- -23,) + 482 1-2+281)
--2-33,
"See httpp:///en wann.wike wiki w a "See attpp://en... http/////.wiiiieeeeeeee...... http:///pp..aoooot//t///////tee.
15

---

Sampling Binary Data by Denoising through Score Functions
We thus need the condition 882de49, to get the contraction
(1-2 exp
1
2 (- 2.3)). (-2-23))
17
We now need to compute the contraction for the first step using simply 31 = B2 = 0 in the same reasoning, leading to
contraction
(1- (1-exp exp ( (- 2 )
Multiplying the two contractions, we get
21-200 exp (
1
2 - - exp (1 < <(1 $1-2
2 -23:)):
exp
2
77
2 17
which leads to the desired result.
E. Proof of Proposition 3.4
Proof. We consider y (2) E {-1, 13dd distributed from an arbitrary distribution r, and y(2) sampled from the distribution q. We sample (1) and (2) from u(- ()) and u(-ly(2), well as g(l) and g(2), from ul ((-12(1) and u(-[=(2) (so that we get full approximate Gibbs sampling step, with transition kernel from yd to g(2) and y(2) to g(2)), all coupled that the Wasserstein distance between
y(1)
and
Σ
(that is, one step of the Markov transition kernel) is less than B( g(2)).
For the purpose of the proof, now add Metropolis Hasting step to the second chain (which leads ((2) so that, since it starts from the stationary distribution q of the full Gibbs sampling step, it remains q. Thus, like in Appendix C,
W Σ (() ).) g(
< ",
( 2( + 22)( ((2)))
(1- exp ( (- マ 281) W (r. (y (1))))))((000 y())
Moreover, like in Appendix C, have, now dropping the superscripts (2):
E[[rejec (v. () a)] = Σ
(( ((
D.
We have, using that g(=lg) = u(2ly). and by definition of v.
(())o(Tl)) Σ E E (((0)\(l==))(=1)> -
Σ Ed()))(ol=)u(011>
16

---

Sampling Binary Data by Denoising through Score Functions
because (()))(=)v)) a(v, (z)])))))) leading
Preject (v. (...))(y. v)]
Σ v.1
P(T. v)
Σ [((e)a(o)))((()))) [((e)a(()))u(ll)))
Σ M.
(T 3)
[((e)(alhh))())))-oooo -Q00)))))0)) (012))((l)))
2
(Øū ( -()=))))(())))))))))>) by the triangular inequality,
2
4.169
mnax
(( - -((]=)(((]=) by bounding the expectation by the max,
2
MrB
2
max
(
-
-aapill)>>-vvaaa -(vl=)((()))
M:B
max
(
<<(l=) + +(vl= -
2
M.B
max
((U.))u(v==))((0)>>> -((1=)) by symmetry,
V.
max
((..))
(0]22) by the triangular incquality,
Σ ((G,))u(vl=)) u(0)=)] Σ ((2 (()x)))))))lll - w((l=)]
max
V:9
9.9
by separating the sum,
E(T, ((,22)a((lz) u(Tl=) + Σ E(z, u)(()
Σ l9(glz) u(512)]
max
by summing out y in the first term,
Σ [((,,) + ddol- 2 +231) z) u(rl=))b
max
max Σ ((0,z) ((0,=))\((0l=)) u((l=)]] 200(-2 +33) max TV u()))))),
(16)
d
using that Ee(z, independent components.
((2 y)((y)=)=
Σ P Pa(an
21 Σ a--2/11 2x(2)) & do(-2/11 2.3)) and that u(-12) has
We can now write, because of our assumption in Eq. (10),
((y|2) = u(ylz) Ztz)
eo(o.z)
with v(v. log ((1) - log g(=) s(2) (y- - 2). which satisfies
32 11y =112.
0 < p(y,)) <
2
17

---

Sampling Binary Data by Denoising through Score Functions
and
log (z)
log Σ u(yl2 u(yl2)eH(uie)
& log Σ u(y]2)e 7 11
d
log Σ ((yl2)edBallo-al)
log
Σ
u(yi zi zi) dall -a1l using that | - =||1 & 2d,
Di
d
log (2(2/1 ((2/n+2s(33))) - 2s 2
by definition of u(-12),
d
Σ log (1+0(-2/1) -
(d05 - 1)) < dlog
-1)
1=1
< dlog [1 2 (2200s 1)) & de 2/0 (E20ps 1) using log(1 + c) cc
(17)
Moreover, we have Z(z) > 1.
We treat the two terms in Eq. (16) separately. For the second term, we have, using Pinsker's inequality,
TV(1(-12), < (eldeel)))))) 1/2
(utuis)) log u(vl2)) 1/2
((112))
( 2 Eutols) log Z(z) p(v.2)
1/2 < ( log Z(2) 1/2
because > 0. Thus the second term in Eq. (16) can be bounded as follows, using Eq. (17):
2do(-2 2 + 2,8)) max (V(((+2))) u({=)) < 2de +28 d (2203= -1) 1/2
(
2
17
= V203/2 - 433 (c200s - -1) 1/2
(18)
For the first term in Eq. (16), we have:
d
Σ y
C(u, 2) |1(0== - u(b|=)|
Σ
Mi u(]l)).
((0.2) - 1 by definition of sp,
7(z)
8
1=1
Σ
1, 1//1)-2s(=)) II (((])lz))
20(2)))
((8.2) 1 by definition of
?(2)
We now the inequality
1 (B.2)
-1
-( 7(2)
1
cx(0.2) - 1) + (1 (1-- ( log 21x))
(())
=
-1] -1) + (log ((z) - ((0,22) =))_ S ((0(022) - 1 + log Z(z),
18

---

Sampling Binary Data by Denoising through Score Functions
which is the result of y 0 and Z è I, get, using ((5 d321ly =||1.
Σ (0.22) | u(z)z))
1 (-22/1 2x(2),) II ((U))zz)) d - -14 log ((z)
i=1
Σ
o( 2/-2/n 231)
II (((T)lzz) ( (22dth dii Esse
Ei 185-1)) - -1 + log 2())
1= 053ンt
3//
d Σ
a(-2/n+ 231)
2d02
II j&
2 +o(-2/11 ) } --1+
+ log 2(2)
1=1
d Σ
= a(-2/1) +281)
2d82
II
+ 0 22) 11} - + log ((x))
1=1
d e 2/1 Σ
2,2082
II
{1 +
26222 - log 2()))
ifi
de- 2/n++ ( (2092 (1+ + (-2n 2 11)
d-1 -1 log (02))(())
From the constraint 8d & 1, we have 32d & 3. which implies that 2dd9 - 1 < 5d32. Moreover, we assume that e 2/n < 1/2 This leads to, using Eq. (17),
Σ (0) ((0,=)))((012)) - u(7)z)]
<
de- 2/1423/ (00 (1
(1+72 d82
15
+ de 22/0+20: (6 - 1))
(6252=11)
2//0+231 _d...)
< de 2/1423/
+ de-
2
de 2// 6d32
+ - d B2e 14/++101
(19)
2
using c
Thus, assembling the terms in Eq. (18) and Eq. (19),
1egreet (v. 0)(( v)]
< de 2/ 6dß2 +
n 32e 1/n+100 -1/0411 + 2 ( 1/2
5
(2)3)) 2
2
Thus, using the same reasoning as in Appendix C, and using that 32d & 1
8
(d'.g))
< 2e 228 E[[reject (,. (T v)1
< 2de 48 6df2 + 5d B 2/1+68
2/22 4 (2 (d,35)) 1/2
5
< 17d Trd2:8. 48, 32 2/55/ + v B2 using 2/1429 < d'
(20)
17d2 48 82 + 2v5 + 4/4 VB2
17 82 + 2v5
1
48, VB2 = de (17d32 / 20d < de [17
1
V dB2 + 220,52
Vd
v8
< 12de 10, dd3..
Overall, we get a bound in d times / B2d² and times Byd if n is small enough, by Eq. (20).
19

---

Sampling Binary Data by Denoising through Score Functions
F. Mixtures of independent variables
In this section, we provide details on score functions for mixtures two independent variables. We start with a few facts about independent variables.
few facts about independent variables. If p(x) x e then
p(x) = Il i== 2 cosh 3
and
Σ p(z)> = tan) =E(-1,1)
(taken componentwise).
If g(y) x E (eee--..pp(z)e"'' =, then y 2, where p(z) e is independent from Since for independent variables, the first moment characterizes the distributions, we have
p(z)e
a(y) x e x
with tanh 7/2 tanh & tanh 3r. We then have two different formulas for q(y):
e
<(v)
I 2 cosh 75
I cosh(3 (3, + az:)
cocsh or) d
i== cosh 3
the second being obtained by computing the sum with respect to x. Note that these two formulas are equal for E {-1, 1)d, for generic y's Moreover, one can check that or B = 0 lead to constant q.
We compute E[x]y]] as
E B[xly] log g(x).
Using the first formula for q leads to B[X v) I which is incorrect. With the second formula, we get:
v log ( tanh(3 - ay).
Mixtures of two independent variables.
We consider
p(r) = c2 B)d
31
+ 2
-1,701
21,
2
With tanh y tanh a tanh 8, then is mixture of
(2cosh yju ? and
71. with
(2 cosh 7)a
d
d II 1=1
((v) = (2 cosh at o Byd
1
c + (gy)
cosh (B (osh)8-ag)) 2
2
1=1
and
II co + azy: ta + az) cosh(8 ag:: tanh(3 - -ay)
V log Qvy)
a
I cosh(3 + awy [
cosh(8 -oy;)
ey tanh(8 + aay e 7 tanh(3 az)
Above, the first formula is valid for all y E RRdd while the second formula is only true for y E (-1,13d.
20


Reviews:
[{"review_id": "XIBC10IhfI", "reviewer": "Reviewer_Fbys", "summary": "The authors introduce a denoising sampling algorithm for distributions supported on the d-dimensional Boolean hypercube. In this discrete context, Gaussian noise does not exist and therefore one has to argue differently. The idea is to noise the target distribution by flipping each coordinate with a given probability, which depends upon a parameter $\\alpha$. The smaller $\\alpha$, the more noise is added to the target distribution. Next, leveraging a clean expression of an optimal denoiser through a conditional expectation, an approximate denoiser is learned from noisy samples using either logistic regression or a least-squares loss. Remarkably, the optimal denoiser admits a representation as the rescaled (continuous) gradient of the logarithm of the noisy distributions. This in parallel with well known results for Gaussian noising. A theoretical bound on the denoising performance is provided at Lemma 2.3. Section 2.4 explores adaptation of this framework to multiple measurements. That is, when the same sample is noised several time by the addition of i.i.d. noise. Section 3 considers the problem of sampling from the noisy distribution. First, a one-stage discrete Langevin sampler is proposed. Contractivity properties under assumptions on $\\alpha$ of the sampler are proven in Proposition 3.1 and a control between the ergodic distribution of the sampler and the noisy distribution is the object of Proposition 3.2. Next, a two-stage Langevin sampler is considered and the same results as for the one-stage sampler are proven. The paper is concluded by a section that contains numerical experiments; first synthetic data are considered in the form of mixtures of two independent binary vectors. Then, the binary mist dataset is considered.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review.\n\nRegarding \"Essential References Not Discussed\", the concurrent work by Le Tuyet et al. (the paper became public after the ICML submission deadline) is different from our paper, as it is based on a \"continuous-time Markov chain,\" but both address the problem of sampling from a distribution on the Boolean hypercube. We'd be happy to cite the concurrent work as well as the paper by Kim et al. that the reviewer mentioned.\n\nRegarding \"Weaknesses\":\n - Improving the bound in Lemma 2.3 is a great research direction, but we're not sure what the reviewer means by \"finite entropy.\" Entropy is always finite in the discrete space.\n - Regarding \"precise discussions,\" please see our general response. In short, we'd be happy to extend our discussions of the diffusion literature.\n \nRegarding \"Other Comments Or Suggestions\":\n\n- Regarding \"pseudo code,\" please see our general response.\n\t\n- The results in section 3 do not follow from known results.\n\n- The parameter $\\eta$ does enter in Proposition 3.4 (see the condition in the proposition; $\\eta$ cannot be too large, depending on $\\beta_1$). The reviewer has a good point regarding $\\eta$ not entering in the distance to the stationary distribution, which we'd be happy to emphasize too in our revision. But please note that, in both cases, based on Propositions 3.1 and 3.3, if $\\eta$ is too small the mixing time will be too large, which is also quite intuitive.\n\t\nRegarding \"Questions For Authors\":\n\n- The main difference between the Bernoulli and the Gaussian case is that the the modulus of the random variables is constant on the Boolean hypercube. This may answer the reviewers question regarding \"the modulus of log-concavity\". We're not sure what the reviewer means by \"computational cost\" in this question. The motivation for swapping $\\alpha$ with $\\alpha/d$ is not clear either. The parameter $\\alpha$ has the semantics of the noise parameter for each coordinate, and it's chosen due to its connection between $q_\\alpha$ and the denoiser (the unnumbered equation in page 2).\n\n- Since $0 < 2\\alpha \\leq 0.5$, we have $e^{2\\alpha} \\leq 2$. It then follows that $4 \\alpha^2 d e^{2\\alpha} < 0.5$. We will clarify this in the paper.\n\n**GENERAL RESPONSE**:\n\nWe would like to thank all the reviewers for their detailed feedback, highlighting the novelty and simplicity of our framework and providing pointers to the literature on discrete diffusion. We address the common concerns here.\n\nThree reviewers brought up references on discrete diffusion that we're happy to add to our literature review. We'd also be happy to extend our discussion of the diffusion approach vs. ours (non-SDE, single noise level) in the related work section.\n\nThe closest reference to our paper is the concurrent paper by Le Tuyet et al., Discrete Markov Probabilistic Models (posted first on arXiv after the ICML deadline). We're happy to discuss this concurrent work as well. In short, their method is very different from ours, as it involves a \"continuous-time Markov chain.\"\n\nSeveral reviewers commented on the need for pseudocode and schematics. Thank you for this constructive feedback. We will add pseudocode and a schematic in our revision.\n\nRegarding novelty, please note that there are no known results on the mixing time of discrete Langevin MCMC, and our convergence results also improve upon the known results [1]. In their paper, they assume the target distribution is quadratic (Eq. 5 in [1]), which we relax substantially with our assumption (4) in our paper.\n\n[1] Zhang et al. (2022) A Langevin-like Sampler for Discrete Distributions", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "Yes they are appropriate", "theoretical_claims": "I checked the correctness of the proofs which are not in the appendix.", "experimental_designs_or_analyses": "I checked the soundness of the experiments in section 5; they seem appropriate to me.", "relation_to_broader_scientific_literature": "The contributions of this article fit into the general literature about generative modeling. There has been already a significant number of papers that proposed score-based methods to sample from discrete data distributions. As the authors correctly report, most of these method use a forward-backward construction based on continuous-time diffusion processes, inspired by diffusion models. The approach undertaken here works in a single denoising step, and does not appeal to discretization of continuous-time processes. Citing this structural difference, the authors do not enter into any detailed comparison with prior work. I believe at least some comments on why doing all in a single step is worthwhile is needed in section 1.2", "essential_references_not_discussed": "I am not aware of prior work that considers the same algorithm proposed in this work. I am aware of the concurrent work by Le Tuyet et al., which studies that same problem but from a different perspective. https://arxiv.org/abs/2502.07939 . There is a large literature on generative modeling based on Markov chains. I believe the paper \"Discrete diffusion Schrodinger bridge matching for graph transformation\" by Kim et al. published at ICLR2025 should enter the literature review.", "other_strengths_and_weaknesses": "Points of strength\n* The paper addresses a fundamental problem, and I believe there is potential for several applications.\n* The proposed algorithm is new, and offers a simpler framework than most previously generative algorithms for generating discrete sequences. The training objective is explicit, and offers an interesting parallelism with Gaussian denoising algorithms.\n\n\nWeaknesses \n* The proposed guarantees of convergence are weak. Lemma 2.3 is interesting as it makes no assumptions on the target $p$. But at the same time, the proposed bound is very rough. One would expect to see that mild regularity assumptions on p such as, say, finte entropy translate into better bounds. The authors should improve on this issue.\n\n* There is essentially no precise discussions about the comparison with generative algorithms based on forward-backward Markov chains. This is true for both theory and experiments.", "other_comments_or_suggestions": "* The authors should provide some schematic view or pseudo code for their algorithm(s)\n* The authors shall provide an intuition about the proof of the result of section 3. Do they follow from known results?\n* The authors should comment on why the parameter $\\eta$ does not enter the bounds at Proposition 3.2 and 3.4 . It is not very clear to me", "questions_for_authors": "1) The log-concavity estimate (8) tells that the modulus of log-concavity of $q$ is independent on the dimension $d$. Of course, this is false when noising in a Gaussian context.Can the authors comment on this? I suspect that this is because noising at level $\\alpha$ in truth means that the computational cost of this operation is of order $\\alpha d$. If so, it would be more correct to rewrite the results substituting $\\alpha$ with $\\alpha/d$.\n\n2) I am confused from the statement right after Propostion 3.1. The authors seem to claim that the condition $\\alpha\\leq 1/(4\\sqrt{d})$ implies the condition $4\\alpha^2de^{2\\alpha}\\leq 1$. This claim seems false to me because of the term $e^{2\\alpha}$ and if so it would have an important impact on the theoretical guarantees of the sampling part. It is likely that I am missing something obvious here, but I would still like the authors to clarify this point", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "P4SNILNBfq", "reviewer": "Reviewer_GyQ3", "summary": "The authors propose a method to sample binary (vector) data by denoising through score functions. They first propose a noise model for binary data where the noise corresponds to a bit flipping with a given probability. Then, they construct the optimal denoiser based on Hamming loss and they show that it corresponds to a sign of a scaled score function (or a conditional expectation of clean data given the noise). Furthermore, they demonstrate better denoising performance provided that more noisy samples (of a fixed clean sample), are available. After that, they construct a sampling algorithm based on a two-stage discrete Langevin sampler (which employs Gibbs sampling), which allows them to produce more \"noisy observations” of a fixed clean sample. The authors complete their study with experiments in the case of binarized MNIST.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review. \n\nPlease note in the original DDPM formulation, there is indeed an SDE behind the scenes. In other words, for understanding the theoretical properties of DDPM one has to return to the SDE formulation. The case of measurement accumulation is discrete by nature. Algorithmically, the methods are differentiated as in the DDPM case, one needs to come up with a forward and backward \"noise schedule\" and the case of measurement accumulation one has to only pick the number of measurements.\n\nRegarding the comment on denoising based on \"one noise level\", we're aware of the extensive research on denoising in the computer vision and signal processing literature, but turning that into a sampling and generative modeling scheme is a not as well studied. For example, the reference Romano et al. (2016) is not a generative model -- there is no connection between the score function and the denoiser in the paper.\n\nWe're not sure what the reviewer means by \"Most of the theoretical claims have already been established in the literature\". The results in Sec. 2 are straightforward generalizations of the results for the Gaussian case. Conceptually, the emergence of a smooth score function that's defined beyond the Boolean hypercube is new. All the results in Sec. 3 are new -- in particular, there is no mixing time result for discrete Langevin MCMC in the literature. We'd be happy to clarify this further in our revisions. \n\nRegarding \"few recent references are missing\", we'd be happy to add the references mentioned by the reviewer in our revisions.\n\nWe disagree that this paper is \"straightforward extension of [1]\". The machinery for discrete sampling and its theoretical properties have little in common with the Gaussian case. But conceptually, we also consider it as an extension of the the previous approach and in our view it's the strength of the method, since we arrive an algorithm with only two hyperparameters ($\\alpha$ and $m$). Our \n\n[1] Saremi et al. (2024) Chain of log-concave Markov chains\n\nRegarding \"Other Comments Or Suggestions\":\n\n- We have an extension of the approach for non-binary data, but it was beyond of the scope of the paper due to space. One simple approach would be to use the 1-hot encoding for any discrete data that turns it into binary data.\n\nRegarding \"Questions For Authors\":\n\n- Regarding \"why would a user pick this method over discrete diffusion\", the choice really comes down to the fact for some applications, single noise models give rise to strong empriical results. Please see the references in the introduction. The models we have proposed in our paper are much simpler in terms of hyperparameters (and arguably in terms of formalism), compared to discrete diffusion. Please also note that we did not do any tuning for our experiments - the step size was simply set to 1/$\\alpha$.\n\n- Our paper is mainly theoretical and the experiments were designed to understand the method. There are extensive comparisons between different regimes in our experiments. The experiments on MNIST are qualitative to show the fast mixing of our algorithm. For this, we encourage the reviewer to compare our results with the concurrent work by Le Tuyet et al., as mentioned by the reviewer Fbys - in our case only one or two steps are required to arrive at a digit. Also, we don't know how to adapt the diffusion approach to give single (fast-mixing) MCMC chains we demonstrated in our experiments.\n\n**GENERAL RESPONSE**:\n\nWe would like to thank all the reviewers for their detailed feedback, highlighting the novelty and simplicity of our framework and providing pointers to the literature on discrete diffusion. We address the common concerns here.\n\nThree reviewers brought up references on discrete diffusion that we're happy to add to our literature review. We'd also be happy to extend our discussion of the diffusion approach vs. ours (non-SDE, single noise level) in the related work section.\n\nThe closest reference to our paper is the concurrent paper by Le Tuyet et al., Discrete Markov Probabilistic Models (posted first on arXiv after the ICML deadline). We're happy to discuss this concurrent work as well. In short, their method is very different from ours, as it involves a \"continuous-time Markov chain.\"\n\nSeveral reviewers commented on the need for pseudocode and schematics. Thank you for this constructive feedback. We will add pseudocode and a schematic in our revision.\n\nRegarding novelty, please note that there are no known results on the mixing time of discrete Langevin MCMC, and our convergence results also improve upon the known results [1]. In their paper, they assume the target distribution is quadratic (Eq. 5 in [1]), which we relax substantially with our assumption (4) in our paper.\n\n[1] Zhang et al. (2022) A Langevin-like Sampler for Discrete Distributions", "claims_and_evidence": "* Claim: A model for noise for binary vectors based on flipping the bits with given probability. Evidence: mathematical derivations\n\n* Claim: Optimal denoiser for this noise model given a Hamming loss which is given by a sign of a conditional expectation of clean data given a noise sample. Evidence: mathematical derivations and proofs\n\n* Claim: Connection of a conditional expectation of clean data given a noise sample, to a score function of a noise model. Evidence: mathematical derivations.\n\n* Claim: Approach to learn this score function via logistic regression. Evidence: Mathematical derivations.\n\n* Claim: Approach to use multiple noisy samples for a one fixed clean sample which allows to better approximate the distribution of clean samples. Evidence: lemma\n\n* Claim: Approach to use discrete Langevin algorithm to sample many noisy samples from a noise model. Evidence: derivations + proofs\n\n* Claim: The proposed approach has better mixing times than Gaussian-based Langevin. Evidence: Derivations and proofs\n\n* Claim: Empirical evidence that the proposed approach leads to a good approximation of a target distribution depending on the noise levels. Evidence: experiments.\n\n* Claim: Empirical evidence that the approach works with Binarized MNIST. Evidence: Experiments.\n\nI would like to challenge the claim that the approach of [1] is the first/only one to consider a generative model approach which does not rely on a SDE, as suggested by the end of the introduction \"The main conceptual difference is that the multi-measurement sampling does not involve discretizing an SDE\". The original formulation of DDPM, see [2,3] for instance, also does not include any SDE discretisation. Similarly, the fact that only one noise level is required is not a specificity of the given model. Such approaches are common in the image processing literature with the Plug-and-Play approaches [4].\n\nSimilarly, I think the claim that all approaches that build on diffusion models require a forward backward formulation (in the discrete setting as emphasized in Section 1.2) is a bit misleading. For example [5] is not based on a SDE perspective (I concede that they use multiple and different noise levels). In particular, there is no discretization approximation in this work.\n\n[1] Saremi et al. (2024) Chain of log-concave Markov chains\n\n[2] Sohl-Dickstein et al. (2015) Deep Unsupervised Learning using Nonequilibrium Thermodynamics\n\n[3] Ho et al. (2020) Denoising Diffusion Probabilistic Models\n\n[4] Romano et al. (2016) The Little Engine that Could: Regularization by Denoising (RED)\n\n[5] Austin et al. (2020) Structured Denoising Diffusion Models in Discrete State-Spaces", "methods_and_evaluation_criteria": "Most of the paper provides mathematical justifications together with error bounds for all the claims. Moreover, it provides empirical evidence highlighting all the theoretical claims made in the paper. The paper is mostly theoretical.\n\nThe experimental setup of the paper is however quite weak and does not emphasize the scalability of the method.", "theoretical_claims": "I skimmed through the appendix and checked most of the proofs. Looks correct. Most of the theoretical claims have already been established in the literature. The main results of the paper in my opinion are Proposition 3.1 and Proposition 3.2.", "experimental_designs_or_analyses": "Experiments are quite simple and straightforward, no concerns for validity.", "relation_to_broader_scientific_literature": "This paper takes a very different approach to discrete modeling compared to Masked diffusion approach and discrete-from-continuous approaches.", "essential_references_not_discussed": "I think a few recent references are missing. \nNotably, there has been some great advances in the direction of discrete diffusion such as [1,2] and the references therein.\nI think it would be worth emphasizing the connections between the current approach and these works. \n\n[1] Shi et al. (2024) Simplified and Generalized Masked Diffusion for Discrete Data\n\n[2] Zhao et al. (2024) Unified Discrete Diffusion for Categorical Data", "other_strengths_and_weaknesses": "I think the paper is well written, all the claims are theoretically justified. \nThe method is a straightforward extension of [1] so the novelty is limited. However, I appreciate the current presentation.\nThe experiments are quite weak.\n\n[1] Saremi et al. (2024) Chain of log-concave Markov chains", "other_comments_or_suggestions": "I suggest to the authors to add a discussion on how they see this work could scale to more complex discrete distributions (i.e., even just higher dimensional colored images?). What if the data is not binary, how would the authors approach it?\nI appreciate that the authors added a discussion that this approach might be applicable to a broader set of exponential families distributions. It would be interesting to have a slightly more concrete discussion for a path forward.", "questions_for_authors": "Motivation: the motivation as to why consider only level of noise (even in the multisample case) is a bit unclear to me. One could say that we avoid the discretisation of the SDE but there is still some discrepancy between the target measure and the approximated one. Overall, I think that the authors should be able to answer the following question: why would a user pick this method over discrete diffusion or autoregressive models?\n\nScalability: How would it scale for non-binary discrete data and to a high dimensional colored images? The current experimental setup does not bring a lot of information regarding the efficiency of the method.\n\nBaseline: no baseline is presented in this work. As it is presented as an alternative to discrete diffusion models it would be interesting to compare the performance in this case", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {"ethical_review_concerns": "No concerns"}}, {"review_id": "hFP8RSfkRX", "reviewer": "Reviewer_XYSZ", "summary": "This paper investigates the problem of sampling from distributions over the binary hypercube using a smoothing-denoising framework. Instead of adding Gaussian noise, the authors introduce a novel approach based on Bernoulli noise. To enhance convergence in the denoising step, they leverage proximal sampling methods. The effectiveness of their method is demonstrated through experiments on synthetic data and binarized images.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review. \n\nRegarding \"Other Comments Or Suggestions\":\n- Thank you, we'll correct the typo.\n\nRegarding \"Questions For Authors\":\n\n- Thank you for the question. Intuitively, kinetic Langevin algorithms or Hamiltonian Monte Carlo also have an auxiliary variable (\"velocity\" in their case). However, making a deeper connection is a great research direction. \n\n- We believe more assumptions need to be made to extend our results to TV.\n\n- The assumptions made in Sec. 3 are akin to regularity assumptions (very common in the optimization literature) in the Euclidean case, which are adopted here for the binary case. In addition, they were required in our proofs in Sec. 3. We'd be happy to clarify this further in the paper.\n\n**GENERAL RESPONSE**:\n\nWe would like to thank all the reviewers for their detailed feedback, highlighting the novelty and simplicity of our framework and providing pointers to the literature on discrete diffusion. We address the common concerns here.\n\nThree reviewers brought up references on discrete diffusion that we're happy to add to our literature review. We'd also be happy to extend our discussion of the diffusion approach vs. ours (non-SDE, single noise level) in the related work section.\n\nThe closest reference to our paper is the concurrent paper by Le Tuyet et al., Discrete Markov Probabilistic Models (posted first on arXiv after the ICML deadline). We're happy to discuss this concurrent work as well. In short, their method is very different from ours, as it involves a \"continuous-time Markov chain.\"\n\nSeveral reviewers commented on the need for pseudocode and schematics. Thank you for this constructive feedback. We will add pseudocode and a schematic in our revision.\n\nRegarding novelty, please note that there are no known results on the mixing time of discrete Langevin MCMC, and our convergence results also improve upon the known results [1]. In their paper, they assume the target distribution is quadratic (Eq. 5 in [1]), which we relax substantially with our assumption (4) in our paper.\n\n[1] Zhang et al. (2022) A Langevin-like Sampler for Discrete Distributions", "claims_and_evidence": "The claims are generally well-supported by proofs and empirical experiments.", "methods_and_evaluation_criteria": "The proposed methods make a significant contribution to sampling from Boolean distributions. While smoothing discrete distributions using Gaussian noise has been extensively studied, the use of Bernoulli noise appears to be a novel and promising approach. A key advantage of Bernoulli noise is its potential to improve mixing time. However, I am uncertain whether a similar convergence rate could be achieved with Gaussian noise when combined with a proximal sampler. Additionally, while I am less familiar with the experimental aspects, I would be interested in understanding the feasibility of applying this method to high-dimensional settings.", "theoretical_claims": "I checked the proofs and didn't find problems.", "experimental_designs_or_analyses": "I am less familiar with the experimental aspects, so I only conducted a high-level review. Based on my assessment, the experimental design appears reasonable and generally supportive of the claims.", "relation_to_broader_scientific_literature": "I don't know.", "essential_references_not_discussed": "I did not find any essential related works that are missing.", "other_strengths_and_weaknesses": "Strengths:\n\n- this paper is well written;\n\n- the use of Bernoulli noise instead of Gaussian noise is new for me;", "other_comments_or_suggestions": "- Line 161 \"is equal is\" -> \"is equal to\"", "questions_for_authors": "- In Section 4, can Gaussian noise with proximal sampling achieve a comparable convergence rate? If that is the case, the advantage of using Bernoulli noise might be limited.\n\n- Is it possible to derive convergence results under other metrics, such as total variation (TV) distance?\n\n- Could you provide a justification for the assumptions made in Section 3?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "fKs31Zbuiq", "reviewer": "Reviewer_REiK", "summary": "This paper proposes a generative model for data on the boolean hypercube. The basic idea is to \"noise\" the data with random sign flips, with expected number of sign flips controlled by a parameter $\\alpha$, and then learn to \"reverse\" this operation which ultimately boils down to learning a denoiser in this paper. The denoiser takes as input a sample from the sign-flipped data distribution which is denoted by  $q_\\alpha$. The overall sampling procedure proceeds as follows: first sample $Y \\sim q_\\alpha$ then query the denoiser at $Y$. \n\nThis sampling procedure introduces a specific compromise: as $\\alpha$ is close to $0$, $q_\\alpha$ becomes closer to the uniform distribution and so is easier to sample but then the law of ${denoiser}_{\\alpha} (Y)$ can be very different from the target distribution. \n\nA workaround is to include multiple measurements i.i.d. $Y_1, ..., Y_m$. In this case the denoiser takes as input these measurements altogether and its denoising performance, as measured by the closeness of the law of $denoiser_\\alpha(Y_1, ..., Y_m)$, improves. Having trained the denoiser, sampling is performed by drawing approximately from the joint marginal distribution of $Y_1, ..., Y_m$. This is done by done first sampling $Y_1 \\sim q_\\alpha$ and then consecutive conditionals $Y_k | Y_{1:k-1}$. Crucially, we can take $\\alpha$ to be small in this case so as to ensure that the distribution is easy to sample while at the same time having improved denoiser performance due to the multi-measurements. Since we are dealing with a discrete space, the authors proceed to develop a gibbs sampler for the initial distribution.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review.\n\nCould the reviewer comment on \"the authors proceed to develop a Gibbs sampler for the initial distribution\"? The algorithm we have studied is not a Gibbs sampler.\n\nRegarding \"In my opinion, the methodology lacks motivation\", our motivation is that in many applications, a single noise level is enough, which in addition can be extended by adding a single hyperparameter (the number of measurements) to improve sample quality.\n\nRegarding \"Essential References Not Discussed\", we'd be happy to add the references mentioned by the reviewer.\n\nRegarding the comment that the paper \"is poorly written at times\", could the reviewer comment on where it is poorly written? We'd be happy to improve the presentation.\n\nRegarding the question on sampling from the conditional distributions, this is explained below Eq. 4. The conditional distributions also satisfy the assumptions (4), which essentially follow from the identities in Section 2. This is also quite intuitive, as sampling from conditional distributions should not be harder than sampling the first noisy measurement. Given this question by the reviewer, we will clarify this further in our revision.\n\nRegarding \"Questions For Authors\":\n\n- Yes for sampling from the measurement-conditioned distributions, we can use the discrete Langevin sampler. \n\n- Changing the step size is a good suggestion for future work. Here, we took a simple approach, choosing a fixed step size, which we also did not tune. The step size is simply set to $1/\\alpha$.\n\n- This is an interesting regime. However, the tradeoff is that for small $\\alpha$ sampling each measurement becomes easier but then one has to wait longer in measurement accumulation to have good denoised samples. For some problems even a single measurement may be enough, but then one shouldn't use a very small $\\alpha$. We do not believe there is a general answer on which strategy is better as this is highly problem dependent.\n\n**GENERAL RESPONSE**:\n\nWe would like to thank all the reviewers for their detailed feedback, highlighting the novelty and simplicity of our framework and providing pointers to the literature on discrete diffusion. We address the common concerns here.\n\nThree reviewers brought up references on discrete diffusion that we're happy to add to our literature review. We'd also be happy to extend our discussion of the diffusion approach vs. ours (non-SDE, single noise level) in the related work section.\n\nThe closest reference to our paper is the concurrent paper by Le Tuyet et al., Discrete Markov Probabilistic Models (posted first on arXiv after the ICML deadline). We're happy to discuss this concurrent work as well. In short, their method is very different from ours, as it involves a \"continuous-time Markov chain.\"\n\nSeveral reviewers commented on the need for pseudocode and schematics. Thank you for this constructive feedback. We will add pseudocode and a schematic in our revision.\n\nRegarding novelty, please note that there are no known results on the mixing time of discrete Langevin MCMC, and our convergence results also improve upon the known results [1]. In their paper, they assume the target distribution is quadratic (Eq. 5 in [1]), which we relax substantially with our assumption (4) in our paper.\n\n[1] Zhang et al. (2022) A Langevin-like Sampler for Discrete Distributions", "claims_and_evidence": "The paper makes a few interesting theoretical claims about the method which helps the reader gain intuition about how the proposed sampler behaves. In terms of evidence, most of them are addressed with theoretical results. One point which I believed is not substantiated with some evidence is the sampling of the conditional distributions. It seems that this is not discussed and is assumed to be rather easy to solve?", "methods_and_evaluation_criteria": "In my opinion the methodology lacks motivation. For example, the popular denoising diffusion models proceed by reversing a forward Markov chain that turns the data into noise. The initial distribution of this reverse process can be sampled almost exactly and then each transition in the backwad process can be sampled quite accurately as long as we have a well-trained denoiser. \n\nThis paper takes an orthogonal approach by instead relying on multiple measurements that are at the same \"noise level\". Due to this design choice, the initial distribution is not trivial to sample from and requires quite a machinery. The authors derive (partial) theoretical guarantees for the sampler they use for this initial distribution but still, the distance of the stationary distribution of their sampler to that of the target is not necessarily small. Furthermore, I believe that no guarantees are given for the conditional distributions that need to be sampled afterwards. \n\nEssentially, I do not think that the paper gives compelling arguments as to why this is needed and what is its advantage compared to more traditional approaches. For example one could think about designing a forward Makov chain of sign flips, and this would converge to the uniform distribution on the hypercube exponentially fast. This Markov chain can then be reversed and having learned the \"denoiser\", I believe that the sampling could be done straightforwardly. This is essentially the analog of the approaches considered in the Masked Diffusion literature [1]. I would really like to understand in which cases this approach is more appealing.\n\n[1] Sahoo, S., Arriola, M., Schiff, Y., Gokaslan, A., Marroquin, E., Chiu, J., Rush, A. and Kuleshov, V., 2024. Simple and effective masked diffusion language models. Advances in Neural Information Processing Systems, 37, pp.130136-130184. \n\n[2] Shi, J., Han, K., Wang, Z., Doucet, A. and Titsias, M., 2024. Simplified and generalized masked diffusion for discrete data. Advances in neural information processing systems, 37, pp.103131-103167.", "theoretical_claims": "The proofs are, as far as I am concerned, correct.", "experimental_designs_or_analyses": "The experiments are sound; there is a toy experiment in which everything can be computed in closed form. It allows the reader to get a good grasp of how the various hyper parameters in the paper influence the final performance. The qualitative analysis of this experiment is interesting. The algorithm is then tested on a simple image experiment. Here again the qualitative analysis of the hyperparameters is sound and interesting. \n\nIt seems to me that this section lacks a comparison with existing methods that showcases its appeal.", "relation_to_broader_scientific_literature": "The paper builds on ideas present in the paper [1]. Still, there are significant differences in terms of scope (here discrete state space) and overall the methodology. The paper is also related to recent works on discrete diffusion which are cited in the paper. I believe that the contribution in this paper is novel wrt these prior works. However, besides emphasizing the difference in methodology with these works, the paper does not discuss the main practical interest of their method vs these prior works. \n\n[1] Saremi, S., Park, J.W. and Bach, F., 2023. Chain of log-concave Markov chains. arXiv preprint arXiv:2305.19473.", "essential_references_not_discussed": "While not essential, the authors should also discuss the recent works [1, 2]. \n\n[1] Sahoo, S., Arriola, M., Schiff, Y., Gokaslan, A., Marroquin, E., Chiu, J., Rush, A. and Kuleshov, V., 2024. Simple and effective masked diffusion language models. Advances in Neural Information Processing Systems, 37, pp.130136-130184. \n\n[2] Shi, J., Han, K., Wang, Z., Doucet, A. and Titsias, M., 2024. Simplified and generalized masked diffusion for discrete data. Advances in neural information processing systems, 37, pp.103131-103167.", "other_strengths_and_weaknesses": "**Strength**: I would like to emphasize that the paper presents interesting ideas and the theoretical results provided are nice to have. \n\n**Weaknesses**: The paper could be challenging to follow for readers less familiar with sampling methods. For instance, providing a clear algorithm would help readers better understand and implement the proposed method. The paper also lacks explanations and discussions, and is poorly written at times.", "other_comments_or_suggestions": "I have no further comments or suggestions besides what is mentioned above.", "questions_for_authors": "- Can you give explicit details about how you sample the conditional distributions? Do you use the discrete Langevin sampler? \n- What happens in practice when you set $\\alpha$ to be very close to $0$ and use a very large number of measurements? \n- Is it useful for the two-stage sampler to start with a large $\\eta$ and then decrease slowly decrease it?\n- Once you decrease $\\alpha$ significantly and then scale $m$ accordingly so that the denoiser performance is decent, the initial distribution of $(Y_1, \\dotsc, Y_m)$ should be very close to a uniform. In this case, the 2-stage sampler would no longer be needed. Can the authors discuss this setting?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper proposes a generative model for binary data on the Boolean hypercube using a denoising approach. The data is corrupted via random bit flips, and a denoiser is trained to reverse this process. To improve performance, the authors introduce a multi-measurement strategy, where the denoiser receives multiple independent noisy versions of the same sample, enabling better reconstruction and which makes sampling easier. A Gibbs sampling procedure is developed to approximate the joint distribution of these noisy inputs. The approach is theoretically grounded through optimal denoising under Hamming loss and is validated with experiments on binarized MNIST.

Most reviewers weakly support the acceptance of the paper, and I align with the general consensus.

Most reviewers agree that the paper makes an interesting contribution to generative modeling for discrete data. However, several of them note that the contributions, theoretical or empirical, are modest, and most importantly, the paper lacks comparisons with existing baselines. In addition, some reviewers point out that the paper does not sufficiently position itself within the literature on discrete diffusion models. I agree with these concerns. In particular, I found that:
- The conditions imposed on $\beta_1,\beta_2$ are very restrictive.  
- Even though the paper is mainly theoretical, the absence of comparisons with existing methods makes it difficult to assess the advantages and limitations of the proposed approach.
- While the paper includes many results, it does not present clear theoretical bounds on the final output of the proposed methods.

Even if the paper is accepted, I strongly encourage the authors to carefully consider these comments, as well as those from the reviewers, and address them in the final version of the manuscript.
Decision: Accept (poster)