Sampling from Binary Quadratic Distributions via Stochastic Localization
Authors: Chenguang Wang
Kaiyuan Cui
Weichen Zhao
Tianshu Yu
Venue: ICML 2025 poster (2025)
Keywords: Stochastic Localization
Discrete MCMC samplers
Binary Quadratic Distribution
Primary area: probabilistic_methods->monte_carlo_and_sampling_methods
TL;DR: We prove that posterior distributions in stochastic localization iterations satisfy Poincaré inequalities when sampled using discrete MCMC samplers, enabling efficient sampling from binary quadratic distributions.

Abstract: Sampling from binary quadratic distributions (BQDs) is a fundamental but challenging problem in discrete optimization and probabilistic inference. Previous work established theoretical guarantees for stochastic localization (SL) in continuous domains, where MCMC methods efficiently estimate the required posterior expectations during SL iterations. However, achieving similar convergence guarantees for discrete MCMC samplers in posterior estimation presents unique theoretical challenges. 
In this work, we present the first application of SL to general BQDs, proving that after a certain number of iterations, the external field of posterior distributions constructed by SL tends to infinity almost everywhere, hence satisfy Poincaré inequalities with probability near to 1, leading to polynomial-time mixing. This theoretical breakthrough enables efficient sampling from general BQDs, even those that may not originally possess fast mixing properties. Furthermore, our analysis, covering enormous discrete MCMC samplers based on Glauber dynamics and Metropolis-Hastings algorithms, demonstrates the broad applicability of our theoretical framework.
Experiments on instances with quadratic unconstrained binary objectives, including maximum independent set, maximum cut, and maximum clique problems, demonstrate consistent improvements in sampling efficiency across different discrete MCMC samplers.

Sampling from Binary Quadratic Distributions via Stochastic Localization
Chenguang Wang 12
Kaiyuan Cui 33 Weichen Zhao
Tianshu Yu'
Abstract
1. Introduction
In this work, we consider sampling from the Gibbs measure with the form of binary quadratic distributions (BQDs):
Sampling from binary quadratic distributions (BQDs) a fundamental but challenging problem in discrete optimization and probabilistic infer- ence. Previous work established theoretical guar- antees for stochastic localization (SL) in continu- ous domains, where MCMC methods efficiently estimate the required posterior expectations dur- ing SL iterations. However, achieving similar con- vergence guarantees for discrete MCMC samplers in posterior estimation presents unique theoreti- cal challenges. In this work, we present the first application of SL to general BQDs, proving that after certain number of iterations, the external field of posterior distributions constructed by SL. tends to infinity almost everywhere, hence satisfy Poincaré inequalities with probability near to I, leading to polynomial-ting time mixing. This theo- retical breakthrough enables efficient sampling from general BQDs, even those that may not orig- inally possess fast mixing properties. Further- more, our analysis, covering enormous discrete MCMC samplers based on Glauber dynamics and Hastings algorithms, demonstrates the broad applicability of our theoretical framework. Experiments on instances with quadratic uncon- strained binary objectives, including maximum independent set, maximum cut, and maximum clique problems, demonstrate consistent improve- ments in sampling efficiency across different dis- crete MCMC samplers.
(x) x e ((..) I (-1,1)
(I)
where 3 is the inverse temperature. This distribution class naturally arises in statistical physics such as Ising mod- els (Nishimori, 2001; Bauerschmidt & Dagallier, 2024), spin systems (Bauerschmidt & Bodineau, 2019) and in com- binatorial optimization as quadratic unconstrained binary optimization (QUBO) problems (Lucas, 2014; Glover et al., 2022a;b), making it a fundamental object of study in both theoretical and applied research. Sampling from such distri- butions poses significant challenges due to their discrete na- ture and complex dependencies (Sly & Sun, 2012). To sam- ple from such distributions, various sampling approaches have been proposed, including Markov Chain Monte Carlo (MCMC) methods (Metropolis et al., 1953; Titsias & Yau, 2017; Grathwohl et al., 2021; Sun et al., 2021; 2023b), sim- ulated annealing (Kirkpatrick et al., 1983; Sun et al., 2022; Sanokowski et al., 2023), diffusion models (Sanokowski et al., 2024) and variational inference (Koehler et al., 2022).
Recently, stochastic localization (SI.) has emerged promising sampling framework. In the continuous do- main, SLIPS (Grenioux et al., 2024) established theoret- ical guarantees by proving the "duality of log-concavity" on sampling from the posterior and marginal distribu- tions during SL iterations under certain assumptions, lead- ing to significant improvements in sampling efficiency using Metropolis-Adjusted Langevin Algorithm (MALA) (Roberts & Tweedie, 1996). Intuitively, rather than di- rectly sampling from the continuous target distribution, SL achieves sampling by iteratively adding Gaussian noise to posterior estimates of the target distribution. This results in posterior distributions that are Gaussian convolutions of the target distribution which effectively reduces sampling com- plexity by smoothing out the target distribution's 's irregular features (Huang et al., 2023; Chen et al., 2024). This idea of decomposing a difficult direct sampling task into sequence of sampling from simpler distributions is also prevalent in diffusion models for generative tasks and is considered one of the key factors behind their remarkable performance (Ho et al., 2020; Song al., 2020a;b; Rombach al., 2022).
"quual contribution 'School of Data Science, The Chinese University of Hong Kong, Shenzhen 'Shenzhen Research Insti- tute of Big Data "The Academy of Mathematics and Systems Science, Chinese Academy of Sciences "The School of Statistics and Data Science, LPMC KLMDASR, Nankai University. Cor- respondence to: Weichen Zhao <zhaoweichen @ maankai.cd..cm Tianshu Yu <yutianshu @du....d.......
Proceedings of the ndnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Sampling from Binary Quadratic Distributions via Stochastic Localization
However, this elegant theoretical machinery relies heav- ily on properties specific to continuous spaces and cannot be directly extended to discrete settings, where the fun- damental nature of the state space requires different ana- lytical approaches. While several pioneering works have explored SL-based sampling for specific discrete statistical physics models, including
2. Preliminaries
In this section, we introduce key concepts and notations that will be used throughout this paper.
2.1. Notations
-iiriiigtoorr (SK) models (El Alaoui et al.. 2022) and random field Ising models (Alaoui et al., 2023b), these efforts have often em- ployed model-specific techniques for posterior estimation or focused on distributions with particular structural prop- erties. For instance, El Alaoui et al. (2022) addresses SK models at specific temperature regimes using TAP free en- ergy (Nishimori, 2001) optimization to approximate poste- rior expectations in SL iterations. Consequently, a general framework for leveraging SL with standard, off-the-shelf discrete MCMC samplers and providing theoretical guaran- tees broadly applicable to the rich class of BQDs has been less explored. A natural question thus arises:
Throughout this paper, we consider a system of size N where [N]] == 1.2.. N denotes the index set and f2 = {-1, 11 represents the hypereube state space. For any configuration æ, use Eivi to denote x with site excluded, x² to denote the configuration after transition at site and I = y off j to denote = yi, ii, + j. We define the trivial metric as d(x,, y) = 1 where 1 Ixdy = if x * y. and 1œæy = 0 if x = y. We use || 11r to denote the total variation distance. The conditional distribution of a; is denoted by (-1z)) while E, represents expectation under measure Finally, (5)) denotes the standard inner product.
2.2. Discrete MCMC Samplers
Can SL reduce sampling difficulty for BODs, as it does in continuous settings, by constructing saill-samplable poste- rior distributions using general-purpost discrete MCMC?
In this part, we introduce three recent and effective dis- crete MCMC samplers, which will facilitate our theoretical analysis in Section 4: Gibbs With Gradients (GWG) (Grath- wohl et al., 2021), Path Auxiliary Sampler (PAS) (Sun et al., 2021), and Discrete Metropolis-adjusee Langevin Algo- rithm (DMALA) (Zhang et al., 2022). These samplers share a common foundation in locally balanced proposals, where they incorporate local information about the target distri- bution to construct more efficient transitions. Essentially, they can all be viewed as generalized Glauber dynamics that incorporate gradient- based information from target distribu- tion and different dimension update schemes, followed by an optional Metropolis- Haatopolss-Hastings (MH) adjustment.
In this work, affirmatively answer the question for gen- eral BQDs by establishing strong theoretical guarantees. Our core theoretical contribution is proving that after a cer- tain number of SL. iterations, the posterior distributions con- structed by SL satisfy Poincaré inequalities with probability close 1. This result crucial as it implies polynomial- time mixing for any underlying discrete MCMC sampler ap- plied to these posteriors. We explicitly derive bound on the required number of SL iterations, providing concrete guid- ance for practical implementation. Unlike prior results tied to specific cases, our framework applies to general BQDs (for arbitrary W and b), demonstrating the broad applicabil- ity of SL this discrete setting. Importantly, our guarantees hold for discrete MCMC samplers based on both Glauber dynamics and Eetropolis-Hastingg algorithms, encompass- ing most commonly used discrete sampling methods.
For GWG, the locally informed proposal is defined as:
p(x'lx) x e
1'EH(>))
(2)
where d(x:) = -2r 1) 1)Vlogu(a)) H(x) denotes the Hamming ball of size I around x, and the site to flip is
determined by sampling
Categorical(Softman d(ar)
To demonstrate the practical value of our theoretical in- sights, we conduct extensive experiments on three types of QUBO problems: maximum independent set, max- imum cut, and maximum clique problems, each evalu- ated across multiple datasets. We assess three represen- tative discrete MCMC samplers based on Glauber dynamics algorithms: Gibbs with Gradients
For PAS, the proposal is formulated as:
Py (x (x)) x g(e log logu(s),x'=a))
(3)
where g(.) is the local balancing function (specifically, g(t) = v in PAS) and y represents the current state as the starting point of the auxiliary path.
and Metropolis- (GWG) (Grathwohl et al., 2021), Path Auxiliary Sampler (PAS) (Sun et al., 2021), and Discrete Metropolis-Adjustel Langevin Algorithm (DMALA) (Zhang et al., 2022). Our experimental results demonstrate that SL consistently im- proves the sampling performance of all three samplers across every dataset, providing strong empirical support for our theoretical guarantees.
For DMALA, the proposal admits the conditional indepen- dence relationship p(x'|>>) = -II p(x[(x)) and takes the form:
N
p(211))= = II 1=1
Softmax (1 ( -x)))))))(dd -mi))
(4)
2

---

Sampling from Binary Quadratic Distributions via Stochastic Localization
where the quadratic term present in the original form be- comes negligible in the binary case.
Algorithm 1 SL with Discrete MCMC Samplers
Input: Discrete MCMC Sampler (DMS), time steps for SDE iterations {tz sample size for posterior estima- tion n, SL. parametess a(:), a Initialize Yo- ~ NO too21)
Each of these samplers may include an optional MH adjust- ment step with the acceptance ratio:
min (1 ((x')((pa)))
for i = 0 to T - 1 do
(5)
Set 6; = 4 t42 w, = a aft++1) a((,) Simulate {a) ~ P(X|V,) with DMS
2.3. SL for Sampling
Estimate the posterior expectation U/ 1 n -ー=
Simulate Y1+1~ ~N(; + o,, end for Output: o(tr)
EI Alaoui & Montanari (2022) established a connection between stochastic localization and information theory through an observation process (Yi)e20:
Y tx + B,,
(6)
Given the observation process in Equation 8, Bayes' theo- rem yields the posterior distribution of X given Y;:
where X ~ V, (Be)c20 is a standard Brownian motion independent of X. The conditional distribution ge of X given Y, follows a stochastic localization process, which by Theorem 7.12 of (Liptser& & Shiryaev, 2013), satisfies:
df (xll) x PÊ (v(z)v(z)
(10)
where pf (g/(z) is the Gaussian likelihood induced by the observation process. For the binary quadratic distribution (xx) defined in Equation (I), the posterior distribution takes the explicit form:
dY,- = un dY dB,, Yo- 0,
(7)
where uy(()= = xq (xly)dd. Grenioux et al. (2024) later generalized this to:
yr al)) BBB L [0, (0,Tm))) gon)),
(8)
&f (xly) x e - (e. of
(11)
with (ll)- = //2 g(1) satisfying certain regularity condi-
Note that the quadratic term associated with from the Gaussian likelihood pf (y(zz) vanishes since (ar, x) = 1 for
tions'. The corresponding SDE becomes:
x E {-1,1). In contrast to continuous settings, where x² terms persist and log-concavity can be analyzed through the Hessian of the log-likelihood, the discrete case presents unique challenges. Here, the posterior distribution differs from v(x) only in its linear term, and we cannot assess sampling difficulty through derivatives. This fundamental difference necessitates theoretical guarantees to understand how SL affects the mixing properties of discrete MCMC samplers.
dy = (()) )dl + odB,, Yo 0,
(9)
where (v) = f snget (xr) da. We refer more fundamental definitions of SL to Appendix B.I.
3. Binary Quadratic Sampling via Stochastic Localization
In this section, we present the SL-based sampling frame- work for binary quadratic distributions. Based on SL frame- work introduced in Section 2.3, estimating the posterior expectation of (y) = f x (xl y) y) is crucial for sampling. The most straightforward approach is to approximate this ex- pectation through Monte Carlo approximation using discrete MCMC samplers:
Physical Intuition Before delving into rigorous theoret- ical analysis, we provide an intuitive understanding from physical perspective. Our starting point is the following convergence result:
Theorem 3.1. Consider the observation process
V, = =a()) BBe
Ü
(v)
n
in the case ovt + +o0 as t - +oo, for arbitrary Ç > O and 0, there is T(s,E) large enough such that for > T, the observation process satisfies
sit)
where {- ~ of (zly). The algorithm is detailed in Algorithm 1. Understanding the properties of this posterior distribution becomes central to our analysis.
2( 2 1-6.
'Specifically, g E ([O, Teea), RR+) n C² ((0, Tgen), strictly increasing with g(t) C/8/2 as t for some g 2 1,C > 0, and Tim gt)) = oc.
Examining the linear term coefficient in the posterior dis- tribution (11), which serves as an effective external field
3

---

Sampling from Binary Quadratic Distributions via Stochastic Localization
he he = b+ a(t)Y, 2²t
analysis. Section 4.2 examines two warm-up cases, estab- lishing Poincaré inequalities for classical Glauber dynamics and Metropolis-Hastings algorithms. Building on these foundations, Section 4.3 extends our theoretical guarantees to more sophisticated sampling algorithms. All proofs are deferred to Appendix C.
(12)
The behavior of this term is intrinsically linked to the stochastic localization process. Specifically, the dynam- ics of the localization variable Y, are governed by the SL formulation arising from an observation process, as detailed in Section 2.3 (ef. Equation (8)) Theorem 3.1 provides a theoretical guarantee on the asymptotic behavior of this process under our chosen att) schedule. It proves that as ++ T-Tgn the term atf) X E (-1, 13 and the scaling
4.1. Setup and Key Assumptions
For simplicity, we represent the posterior distribution in equation (11) using the following Gibbs measure:
Tgen=
.o. +0c. As result, the magnitude of the ef- fective external field |he] grows infinitely. In physical terms, this corresponds to applying an increasingly strong external field to an interacting system. For some statistical physics models, the presence of a strong external field generally enhances mixing properties compared to the zero-field case (Martinelli et al., 1994; Martinelli & Olivieri, 1994; Keri- mov, 2012). Intuitively, when this field becomes sufficiently large, the quadratic interaction term becomes negligible in comparison, and the posterior distribution approximates to:
factor a(t)²
1/8 = c (((, E (13)
where 3 denotes the inverse temperature and Zp,n is the partition function. Based on the physical intuition provided in Section 3, the external field h in equation (13) grows to infinity, which motivates our fundamental assumption for all subsequent theoretical analysis:
Condition 4.1. The strong external field It satisfies
|h| Z 2B sup Σ 1Wik
(14)
*E[N] Aeppl
de (x(y) X (a.bb a00Ys oft
Remark 4.2. Theorem 3.1 guarantees that this condition holds with high probability after sufficient SL iterations. Moreover, for low-temperature models (large inverse tem- perature 3), this condition is naturally satisfied due to the dominance of the external field term
This simplifies to product of independent Bernoulli dis- tributions, which is significantly easier to sample. This property of a strong, growing external field is crucial for establishing favorable mixing properties of the posterior distribution at late times. A formal condition on the exter- nal field strength required for our subsequent theoretical guarantees is introduced later in Condition 4.1.
Following Condition 4.1 and Theorem 3.1, setting Ç = 2 (M) Exzz Wall and by choosing a sufficiently small >> Ó, we can ensure that for 2 T(a, e), the exter- nal field |Y:] in equation (11) is larger than Ç, and therefore exceeds 2 sup Exys |Wix with probability at least - E. In subsequent sections, we will demonstrate that when the external field is sufficiently large, certain Dis- crete MCMC samplers for Gibbs distribution (13) satisfy Poincaré inequalities. This theoretical guarantee, combined with the high pesbabbbbbbiltyy bound on the external field, estab- lishes that the Poincaré inequalities in Theorem 4.3 and The- orem 4.5 hold with probability close to 1, thereby ensuring polynomial time mixing² for sampling from the posterior distribution (11).
4. Theoretical Analysis
This section establishes theoretical guarantees for sampling from posterior distributions in the SL framework. The spec- tral gap Tgup determines the convergence rate of algorithm and takes different forms for each DMCMC sampler:
|b| JA
for Glauber dynamics;
1 2 hlle |hl for classical Metropolis chains;
for single-site gradient-informed MH
4.2. Warm-up Cases: Poincaré Inequality for Glauber Dynamics and Metropolis Chains
A
+
al algorithms:
In this subsection, we begin with presenting our theoret- ical results through two fundamental examples, Glauber dynamics and Metropolis chains. Here, we derive explicit coefficients for the Poincaré inequality that depend on the external field h.
for DULA (Zhang et al., 2022).
(e 1n
Notably, for all cases, Tgap increases with [b| and approaches 1 as [4| + +00
As shown in Theorem 20.6 of (Levin & Peres, 2017), stochas- tic dynamics satisfying Poincaré inequality exhibit polynomial mixing time.
We organize this section as follows. Section 4.1 introduces the essential definitions and assumptions that underpin our
4

---

Sampling from Binary Quadratic Distributions via Stochastic Localization
Glauber Dynamics Glauber dynamics, Gibbs sam- pling, provides fundamental approach for sampling from
and remains unchanged with probability: 1 P(xf x))
- min{ 1, 22x, Es Wisa;-2h,a;; }. For these Metropolis chains, we establish the following Poincaré inequality:
BQDs. The algorithm iteratively updates each spin i by sampling from its conditional distribution:
Theorem 4.3. For the Gibbs measure (13) satisfying the large field Condition (4.1), the following Poincaré inequality holds:
pa, Inii == e (o,
Emi=ire- e (ex,)))
Varvg, (8) S 1- 1-222ee--i EMPl (J.),
(16)
For Glauber dynamics, we establish the following theorem with spectral gap "geap =
IN
where EM J') is the Dirichles form (24) associated with MH algorithm on (V
Theorem 4.3. For the Gibbs measure (13) satisfying the large fiel Condition 4.1, the following Poincaré inequality holds:
4.3. Poincaré Inequality for Advanced DMCMC Algorithms
Varen, (f)
EcD(S.f)
(15)
1
While Section 4.2 provides warm-up cases for classical algo- rithms, here we analyze more sophisticated DMCMC sam- plers. We propose general condition that not only encom- passes these warm-up cases but also extends to advanced gradient-informed proposals introduced in Section 2.2. Un- der this natural condition, we establish similar Poincaré incqualities for these sampling methods.
31
where ffD(f.) f) is the Dirichlet form (23) associated with Glauber dynamics on (v3,h).
Building upon the established Poincaré inequality in Theo- rem 4.3, which quantifies the mixing rate of Glauber dynam- ics, we can further analyze the convergence properties of Monte Carlo estimators. Specifically, the spectral gap Ygap plays crucial role in deriving concentration inequalities for averages of samples generated by the dynamics. This leads us to the following corollary concerning the Chernoff- type error bound for our Monte Carlo estimator of the posterior mean.
Single-Site Metropolis- Hastings Algorithms Consider a MH algorithm that updates one site a time with transition kernel:
P(=7)>) (x'lzz) min {1. (B Vala)))
(17)
(
Corollary 4.4. Under condition of theorem 4.3, for a se- quence { (X1, X2,...,,,, ,,,,,
and remains at the current state with probability: P(a"(z) (x*1zz) min {1, 13, (z)==)//pp.((() where V denotes the proposal distribution. This formu- lation generalizes both the GWG transition kernel (2) and the PAS kernel (3) in their single-site update variants.
sampled from Glauber dynamics,
[x)]
for all & > 0, we have:
n X1 Exg [X]
Pg
2 S C n.
Theorem 4.6. For the MH kernel (17), assume the pro- posal (x x) is chosen such that P(x* x)) is Lipschitz continuous for all x = f off j:
where X1 ~ q is the initial distribution of samples, the spectral gap is "gap = constant, and Cr is a rational function.
e te- T. is absolute
(h)
3.5
P(x* x) - P(# 1) S
This established error bound demonstrates that the Monte Carlo estimator achieves exponential error reduction with respect to the sample size
where (B, h) decreases exponentially to 0 as the exter- nal field [h] tendy infinity. Then for the Gibbs measure (13) satisfying the large field Condition 4.1, the following Poincaré inequality holds:
Metropolis Chains. The Petropolis-Hastiinn (MH) algo- rithm is a cornerstone of MCMC sampling methods. As a warm-up case, we analyze the simplified Metropolis chains (Martinelli, 1999) where, for each site i [N], the transition - x occurs with probability:
1
Var (f) 1 CLCppp(8, h)]h Ef
(18)
where Em) is the Dirichlet form (24) associated with MH dynamics on L2 (Vv.v.)..
P(x" | (x) = min(1, P88 (x*))
Remark 4.7. Judging from the above warm-up cases and the calculation examples below, for the measure Va,a we are considering, the Lipschitz properties of general cases can be expected.
(x))(r))
min(1, e 28tr E, Eger Wejas- 2h/31),
5

---

Sampling from Binary Quadratic Distributions via Stochastic Localization
Particularly, for gradient-informed proposals
5. Related Work
(x | [x) : = (z),((z)
1 (U(=))(0-=))
Our work connects to two main research areas: discrete MCMC sampling and stochastic localization. Recent ad- vances in discrete MCMC sampling have moved beyond traditional Gibbs sampling (Dai et al., 2020; Wang & Cho, 2019) to gradient-informed methods, including Gibbs With Gradients (Grathwohl et al., 2021), Path Auxiliary Sampler (Sun et al., 2021), and Discrete Langevin Algorithm (Zhang et al., 2022). These methods enhance sampling efficiency by incorporating local structure information into proposal distributions. Stochastic localization (SL) was initially de- veloped for proving measure properties (Eldan, 2013; 2020) and has recently emerged powerful sampling framework (El Alaoui et al., 2022; Grenioux et al., 2024). While SL has shown success in continuous domains through SLIPS (Grenioux et al., 2024) and specific discrete models like SK models (El Alaoui al., 2022), theoretical analysis for general discrete distributions remains challenging due to their inherent structural constraints. For a comprehensive review of related work, please refer to Appendix A.
where (xx) = - Wx) + (z, ht,, we establish the fol- lowing result:
Theorem 4.8. For the Gibbs measure (13) satisfying the large field Condition 4.1, the following Poincaré inequality Metropolis
holds for the rithm:
Haaropolis-Hastingss Hastings algo-
1
Varvg, a 5
(19)
14
16
[E
where {m denotes the Dirichlet form associated with the MH algorithm on T.2 (vg,)))
DULA The Discrete Unadjusted Langevin Algorithm (DULA) performs simultancous updates across all sites. Its transition kernel takes the form:
Pzx = (x [x)= = II (x*)a,,
(20)
iE[M]
6. Empirical Results
with probability 1 V (z of remaining at the current state. The gradient-informed proposal for each site is given by:
In this section, we empirically validate the sampling perfor- mance of the SL framework. Following the DISCS bench- mark (Goshvadi et al., 2024) 3, we evaluate on three types of combinatorial optimization problems with the form of binary quadratic distributions: maximum independent set, maximum cut, and maximum clique problems, each contain- ing multiple diverse datasets (14 datasets in total). Detailed information about these problems and datasets is provided in Appendix D.1.
V (x x)::
1
e (c(a)((a'm))
(z))(x))
1
4
(z)
1
Bz, Eier Wizzy
(B, which aligns with the proposal (4). For this algorithm, we establish:
Experimental Settings We employ three advanced dis- crete MCMC samplers: Gibbs with Gradients (GWG) (Grathwohl et al., 2021), Path Auxiliary Sampler (PAS) (Sun et al., 2021), and Discrete Metropolis-Adjussee Langevin Algorithm (DMALA) (Zhang al., 2022), all incorpo- rating Glauber dynamics and Metropolis- algo- rithms. To align with our theoretical framework, we im- plement GWG and PAS with single-site updates, while us- adjusted version of DULA,
Theorem 4.9. For the Gibbs measure (13) satisfying the large field Condition 4. 1, the following Poincaré inequality holds:
1
Varva.n ( 1
E(f.),
(21)
1
In )a
(e
+e
where
ing the Metropolis-Hasting that is DMALA. For SL implementation, we adopt the GEOM(2,1) a schedule and uniform SDE time discretiza- tion from SLIPS (Grenioux et al., 2024). Hyperparameters are tuned through comprehensive search. For fair com- parison when estimating posterior expectations, SL uses
f(f.f)== 1 ( 2 ug (dr))
is the Dirichlet form associated with DULA on (VVg))) Remark 4.10. Similar to Corollary 4.4, for Metropolis chains, single-site gradient-informed MH algorithms, and DULA, the corresponding Chernoff-type error bounds of the Monte Carlo estimator for the posterior mean can also be obtained. These are derived from Theorems 4.5, 4.8, and 4.9, respectively. For detailed exposition, please refer to Appendix C.S.
"While MCMC samplers ideally generate i.idd samples from the target distribution after mixing. SL converges to a Dirac dis- tribution of a single sample from the target distribution, making effective sample size metrics from DISCS (Goshvadi et al., 2024) unsuitable for performance evaluation. Therefore, we do not com- pare different sampling algorithms traditional physics models under this metric.
6

---

Sampling from Binary Quadratic Distributions via Stochastic Localization
Table Objective values (t) on MIS benchmarks with different samplers and their variants, For each sampler, we compare the original method and its SL counterpart. Bold values indicate better performance between the paired methods.
ER-DENSITY
SATLIB
R-0.05
R-0.10
R-0.20
R-0.25
GWG
104.219 + 1.63
61.750 + 0.90
34.125 + 0.48
27.813 + 0.63
419.063 + 14.29
SL-GWG
104.375 + 1.52
61.938 = 0.93
34.375 = 0.74
28.000 + 0.56
419.165 + 14.39
PAS
104.375 + 1.64
61.750
0.94
34.063 = 0.61
27.813 0.46
419.539 + 14.39
SL-PAS
104.531 + 1.48
61.906 = 0.88
34.375 = 0.55
28.031 + 0.59
419.707 = 14.35
DMALA
103.063 = 1.62
61.000 = 0.83
33.813 = 0.68
27.438 0.56
415.722 + 14.51
SL-DMALA
103,594 + 1.80
61.344 = 0.96
34.000 = 0.56
27.750 + 0.66
415.718 + 14.38
identical parameters as the corresponding discrete MCMC sampler and maintains the same 10000 MCMC steps in total. Furthermore, motivated by our theoretical results showing that posterior distributions become easier to sample from as SL iterations proceed, the experimental results in Section 6.1 are obtained by exponentially decaying the allocation of 10000 MCMC steps across SL iterations. The impact of this allocation strategy is analyzed in Section 6.2. Detailed experimental settings are provided in the Appendix D.2.
Table 2. The percentage (%) (f) of the solution provided by DISCS (Goshvadi et al., 2024) on Maxclique benchmarks. Bold values indicate better performance between paired methods.
RB
TWITTER
GWG
87.509 6.19
100.000 + 0.00
SL-GWG
87.598 6.16
100.000 0.00
PAS
87.544 + 6.15
100.000 + 0.00
SL-PAS
87.649 + 6.14
100.000 + 0.00
6.1. Main Results
DMALA
87.231 + 6.14
100.000 + 0.00
SL-DMALA
87.310 = 6.15
100.000 + 0.00
In this section, we evaluate the SL framework against three discrete MCMC samplers (GWG, PAS, DMALA) on maxi- mum independent set (MIS), maximum cut (MaxCut), and maximum clique (MaxClique) problems. Following the setting in DISCS (Goshvadi et al., 2024), for MIS, we di- rectly report the objective values, while for MaxCut and MaxClique, we report the optimality gap bascline x 100%) where baseline values are obtained from classic solvers col- lected by DISCS benchmark. The best solution found during the entire sampling process is used for evaluation. To as- sess sampling performance, we implement SL using each MCMC sampler for posterior estimation, enabling direct comparison:
Results on MaxClique Table 2 presents results on two MaxClique datasets: RB and TWITTER, On the RB dataset, all SL variants demonstrate consistent improvements over their MCMC counterparts, with SL-PAS achieving the high- est optimality gap of 87.649%. For the TWITTER dataset, all methods achieve optimal solutions (100%), indicating its relative simplicity. The improvements on RB, while mod- est in magnitude, are consistent across all three MCMC samplers, further validating SL's effectiveness in enhancing sampling performance.
Results on MaxCut Table 3 presents results on seven MaxCut datasets, including Frdös-Rényi (ER) graphs, Barabási-Allert (BA) graphs with varying sizes 1256-1024 nodes), and OPTSICOM instances. SL variants consistently outperform their MCMC counterparts across most datasets, with particularly notable improvements on larger graphs. SL-PAS achieves the best overall performance, showing improvements of up to 0.045% on BA-512 and 0.038% on BA- 1024 compared to baseline PAS. On the OPTSICOM instance all methods achieve optimal solutions.
MCMC sampler vs. SL. + MCMC sampler
under identical MCMC steps.
Results on MIS Table 1 shows the performance compar- ison on MIS problems across five datasets, including four Erdös-Rényi random graphs with different densities (0.05- 0.25) and instances from SATLIB dataset. For each MCMC sampler, our SL variant consistently achieves better or com- parable objective values. The improvements are particularly noticeable on sparse graphs (R-0.05 and R-0.10), where SL-PAS outperforms baseline PAS by O. 151 and 0.25% respectively. Among all methods, SL-PAS demonstrates the strongest overall performance, achieving the highest objec- tive values on both random graphs and SATLIB instance.
The experimental results demonstrate the consistent effec- tiveness of our SL framework across different combinatorial optimization problems, datasets, and MCMC samplers. It is important to note that the DMCMC baselines employed are themselves highly effective and often perform near optimal-
7

---

Sampling from Binary Quadratic Distributions via Stochastic Localization
Table The percentage (%) (1) of the solution provided by DISCS (Goshvadi et al., 2024) on Maxcut benchmarks. Bold values indicate better performance between paired methods.
ER
BA 512-600
OPTSICOM
256-300
512-600
1024-1100
256-300
1024-1100
GWG 101.881 +: 1.76
100.144 + 0.12
100.098 +: 0.14
99,947 = 0.06
100.850 = 0.48
101.544 +: 0.38
100.000 +: 0.00
SL-GWG
101.924 1.76
100.161 + 0.12
100.101 + 0.13
99.972 + 0.06
100.889
0.49
101.562 + 0.37
100.000 0.00
PAS
101884 + 1.76
100.158 + 0.12
100.120 + 0.13
99.954 = 0.05
100.883 = 0.48
101.632 = 0.37
100,000 + 0.00
SL-PAS
101.920 + 1.76
100.174 + 0.12
100. + 0.14
99.975 + 0.05
100.928
0.48
101.670 + 0.37
100.000 + 0.00
DMALA
101881 1.76
100.130 0.12
100.074 0.14
99.946 0.06
100.763
0.50
101.243
0.39
100.000 0.00
SL-DMALA
101.922 1 1.76
100.144 0.12
100.078 1 0.14
99.965
0.06
100.792
0.49
101.228 1 0.38
100.000 0.00
Performance Comparison Across Different Models and Datasets
(rmy Allaniie with Unilirm Uhs
Sxrkal/beeiim Uniiom Uis
Doey Allessien with Ligh
MIS ER DENSIT
MIS ER. DENS/TY-0.10
MIS ER. DENSITY-0.31
MIS ER. DENSITY-0:25
MIS SATLIB
194.
01.2
343
1010
61.9
23.00
417
103.8
0144
23.30
185.
340
23.78
MAXCLIQQU RB
MAXCUT ER-255-300
MAXCUT ER-512-600
MAXCUT BA 25. 300
MAXCUT BA 512 600
$7.5
0.855
6.070
55.594
0.000
$6.012
87.4
0,820
55:108
$6.066
200.52
03816
0148
55.122
300.76
FAR
IMALA
0960
DMALA
080
15R
DMAALA
Figure 1. Ablation study comparing two design choices: (1) MCMC steps allocation strategies (Exponential Decay vs. Identical) and (2) SDE time discretization methods (Uniform vs. Log-SNR), Hatched bars indicate the best performing configuration for each algorithm- dataset combination.
ity on these challenging tasks, significantly outperforming commercial solvers like Gurobi (as shown in Table 3). The improvements shown by SL are achieved even when start- ing from these strong established methods, highlighting its ability to further boost performance. For comprehensive evaluation results, including the sampling trajectory, we refer readers to Appendix D.3.
cretization (our default choice) and Log-SNR discretization proposed in SLIPS (Grenioux et al., 2024). Under uniform discretization, time points are evenly spaced across the in- terval, while Log-SNR discretization allocates more SDE iterations smaller time points where posterior distribu- tions are theoretically more challenging to sample from.
6.2. Ablation Study
Impact of MCMC Step Allocation Our theory suggests that sampling becomes easier during SL iterations. To lever- age this insight, we compare two strategies for allocating MCMC steps across SI. iterations: exponential decay (our default choice) and uniform allocation. In exponential decay, earlier iterations receive more MCMC steps for posterior es- timation, while uniform allocation distributes steps equally.
In this part, we conduct ablation studies on two aspects: (1)
MCMC steps allocation strategies (Exponential Decay vs.
Identical) and (2) SDE time discretization methods (Uni-
form vs. Log-Su (NR), to validate our physical intuition pro- posed in Section and theoretical insights about sampling difficulty evolution proved in Section 4.
As shown in Figure 1, Exp. Decay Allocation with Uniform Disc. achieves superior performance in most test cases, which aligns well with our physical intuition and theoretical analysis. However, we observe several interesting excep-
Time Discretization Strategy We compare two strategies for discretizing the SDE integration interval: uniform dis-
8

---

Sampling from Binary Quadratic Distributions via Stochastic Localization
tions where alternative strategies perform marginally bet- ter, such in MAXCUT ER-256-300 with PAS algorithm where Exp. Decay Allocation with Log-SNR Disc. yields the best result, and in some MIS SATLIB cases where Iden- tical Allocation shows comparable performance. Despite these minor variations, the performance differences among the three strategies are generally modest (typically less than 1% in objective values or optimality gap), demonstrating the remarkable stability of SL. sampling framework across different configurations.
for the Central Universities, Nankai University (No.054- 63241437).
Impact Statement
This work has significant implications for both theoretical research and practical applications in discrete optimization and probabilistic inference. Our theoretical guarantees for SL in discrete domains open new avenues for developing more efficient sampling algorithms. The demonstrated im- provements in sampling efficiency across various discrete MCMC samplers suggest potential applications in diverse fields, including statistical physics, combinatorial optimiza- tion, and machine learning. As discrete optimization prob- lems continue to arise in emerging technologies such as quantum computing and molecular design, the practical impact of our theoretical advances is expected to grow sig- nificantly.
For more comprehensive ablation studies, including the im- pact of a-schedule in SL and the influence of hyperparame- ters on sampling performance, we refer readers to Appendix D.4, where we provide detailed experimental results and analyses.
7. Conclusion and Discussion
In this work, we have established the first theoretical frame- work for applying stochastic localization (SL) to binary quadratic distributions (BQDs), proving that the posterior distributions constructed by SL satisfy Poincaré inequalities with high probability after certain number of iterations. Our theoretical guarantees are particularly general, encom- passing both Glauber dynamics and Metropolis-Hastinne based discrete MCMC samplers without restrictive assump- tions on the underlying distributions. Extensive experiments on QUBO problems demonstrate that SL consistently im- proves the sampling efficiency of various discrete MCMC samplers, providing strong empirical support for our theo- retical results.
References
Alaoui, A. E.,, Montanari, A., and Sellke, M. Sampling from mean-field gibbs measures via diffusion processes. arXiv preprint 130002330 2023a.
Alaoui, A. E. K., Eldan, R., Gheissari, R., and Piana, A. Fast relaxation of the random field ising dynam- ics, ArXiv, abs/2311.06117 2023b. URL https: //api. www.anticscooollaa.............. org/CorpusID: 265128744.
Anari, N., Koehler, F., and Vuong, T.-D. Trickle-down in localization schemes and applications. In Proceedings of the 56th Annual ACM Symposium on Theory of Comput- ing. pp. 1094 1105, 2024.
These results also open several directions for future research. First, extending our framework beyond BQDs to distribu- tions with unknown forms (specifically, deep energy-base based models) remains challenging, potentially requiring efficient second-order Taylor approximations. Second, while our current theoretical analysis provides mixing guarantees for the posterior sampling step within SL, establishing rigor- ous theoretical guarantees for the convergence rate of the overall SL process to the final target distribution is a crucial and challenging problem that warrants future investigation. Third, generalizing our framework to handle discrete vari- ables with more than two states, moving beyond the binary case, an important direction.
Bauerschmidt, R. and Bodineau, T. A very simple proof of the Isi for high temperature spin systems. Journal of Functional Analysis, 276()):2582-2588 2019.
Bauerschmidt, R. and Dagallier, B. Log-sobolev inequality for near critical ising models. Communications on Pure and Applied Mathematics, 77(4):25682277, 2024.
Bertoin, J., Martinelli, F., Peres, Y., and Martinelli, F. Lec- tures on glauber dynamics for discrete spin models. Lec- tures on Probability Theory and Statistics: Ecole d' Eté de Probailités de Saimt-Flow XXVII- 1997, pp. 93-191, 1999.
Acknowledgments
This work was supported by the National Key R&D Program of China under grant 2022YFA1003900, the National Natu- ral Science Foundation of China (N4.1 12426303), the Guangdong Provincial Key Laboratory of Mathematical Foundations for Artificial Intelligence (2023B 121 12110001) and the Fundamental Research Funds
Chen, W., Zhang, M., Paige, B., Hernández-LLoatoo, J. M., and Barber, D. Diffuusive gibbs sampling. arXiv preprint arXhv.2402.03008, 2024.
12326611,
Chen, Y. An almost constant lower bound of the isoperi- metric coefficient in the kls conjecture. Geometric and Functional Analysis, 31:34-61, 2021.

---

Sampling from Binary Quadratic Distributions via Stochastic Localization
Chen, Y. and Eldan, R. Localization schemes: A frame- work for proving mixing bounds for markov chains. In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), pp. 110-122. IEEE, 2022.
Glover, F,, Kochenberger, G., Hennig, R., and Du, Y. Quan- tum bridge analyties i: tutorial formulating and using qubo models. Annals of Operations Research, 3 314(1): 141-183, 2022a.
Dai, H., Singh, R., Dai, B., Sutton, C., and Schuurmans, D. Learning discrete energy-based models via auxiliary- variable local exploration. Advances in Neural Informa- tion Processing Systems, 33: 15:144--10455, 2020.
Glover, F., Kochenberger, G., Ma, M., and Du, Y. Quantum bridge analytics ii: Qubo-plus, network optimization and combinatorial chaining for asset exchange. Annals of Operations Research, 3 314(():185-2)) 2022b.
Dobruschin, P. The description of random field by means of conditional probabilities and conditions of its regu- larity. Theory of Probability & Its Applications, 13(2): 197-224, 1968.
Goshvadi, K., Sun, H., Liu, X., Nova, A., Zhang, R., Grath- wohl, W., Schuurmans, D., and Dai, H. Dises: bench- mark for discrete sampling. Advances in Neural Informa- tion Processing Systems, 36, 2024.
Dobrushin, R. L. Prescribing a system of random variables by conditional distributions. Theory of Probability & Its Applications, 15(3):458-46, 1970.
Grathwohl, W., Swersky, K., Hashemi, M., Duvenaud, D., and Maddison, C. Oops took a gradient: Scalable sam- pling for discrete distributions. In International Con- ference on Machine Learning, pp. 3831-3841. PMLR, 2021.
Dubhashi, D. P. and Panconesi, A. Concentration of measure for the analysis of randomized algorithms. Cambridge University Press, 2009.
Grenioux, L., Noble, M., Gabrié, M., and Durmus, A. O. Stochastic localization via iterative posterior sampling. In Forty-first International Conference on Machine Learn- ing, ICML 2024, Vienna, Austria, July 21-27, 2024, 2024.
Dwivedi, R., Chen, Y., Wainwright, M. and Yu, B. Log- concave sampling: Metropolis-hastings algorithms are fast. Journal of Machine Learning Research, 20(183): 1-42, 2019.
Ho, J., Jain, A., and Abbeel, P. Denoising diffusion proba- bilistic models. Advances in neural information process- ing systems, 33:6840-6851) 2020.
El Alaoui, A. and Montanari, A. information-theoreee view of stochastic localization. IEEE Transactions on Information Theory, 68(1 (8(11))7423-7426, 2022.
Huang, B., Montanari, A., and Pham, H. T. Sampling from spherical spin glasses in total variation via algorithmic stochastic localization. arXiv preprint 2rXiv:240..15611 2024.
El Alaoui, A., Montanari, A., and Sellke, M. Sampling from the sherrington- -etrriinntoonkikkpatriikkk gibbs measure via algorithmic stochastic localization. In 2022 IEEE 63rd Annual Sym- posium Foundations of Computer Science (FOCS), pp. 323-334. IEEE, 2022.
Huang, X., Dong, H., Yifan, H., Ma, Y., and Zhang, T. Re-
verse diffusion monte carlo. In The Twelfth International Conference on Learning Representations, 2023.
Eldan, R. Thin shell implies spectral gap up polylog via stochastic localization scheme. Geometric and Func- tional Analysis, 23(2):532-566 2013.
Hubbard, J. Calculation of partition functions. Physical Review Letters, 3(2):77, 1959.
Eldan, R. Taming correlations through entropy entropy-efficient effficient measure decompositions with applications to ween-field approximation. Probability Theory and Related Fields, 176(3):737-755, 2020.
Kerimov, A. The one-dimensional long-range ferromagnetic ising model with periodic external field. Physica A: Statistical Mechanics and its Applications, 391((0):2931- 2935, 2012.
Eldan, R. and Shamir, O. Log concavity and concentration of lipschitz functions on the boolean hypercube. Journal functional analysis, 282(8): 109392, 2022.
Kirkpatrick, S., Gelatt Jr, C. D., and Vecchi, M. P. Opti- mization by simulated annealing. science, 220(4598); 671-680, 1983.
Eldan, R., Koehler, F., and Zeitouni, O. A spectral condition for spectral gap: fast mixing in high-temperature ising models. Probability theory and related fields, 182(3): 1035-1051, 2022.
Koehler, F., Lee, H., and Risteski, A. Sampling approxi- mately low-rank ising models: Meme meets variational methods. In Conference on Learning Theory, pp. 4945 4988. PMLR, 2022.
Gillman, D. A chernoff bound for random walks on ex- pander graphs. SIAM Journal on Computing, 27(4) 1220, 1998.
Langley, Crafting papers on machine learning. In Langley, P. (ed.), Proceedings of the 17th International Conference
10

---

Sampling from Binary Quadratic Distributions via Stochastic Localization
on Machine Learning (ICML 2000), pp. 1207-1216, Stan- ford, CA, 2000. Morgan Kaufmann.
Sanokowski, S., Berghammer, W., Hochreiter, S., and Lehner, S. Variational annealing graphs for combi- natorial optimization. Advances in Neural Information Processing Systems, 36:63907-6339 2023.
Levin, D. A. and Peres, Y. Markov chains and mixing times, volume 107. American Mathematical Soc., 2017.
Sanokowski, S., Hochreiter, S., and Lehner, S. A diffusion model framework for unsupervised neural combinatorial optimization. In Forty-first International Conference Machine Learning, ICML 2024, Vienna, Austria, July 21-27, 2024, 2024.
Lezaud, P. Chernoff-type bound for finite markov chains. Annals of Applied Probability, pp. 849-867, 1998.
Liptser, R. S. and Shiryaev, A. N. Statistics of random processes: I. General theory, volume 5. Springer Science & Business Media, 2013.
Sly, A. and Sun, N. The computational hardness counting two-spin models on d-regular graphs. 2012 IEEE 53rd Annual Symposium Foundations of Computer Science, pp. 361-369. IEEE, 2012.
Lucas, A. Ising formulations of many np problems. Fron- fiers in physics, 2:5, 2014.
Martinelli, F. Lectures on glauber dynamics for discrete spin models. Lectures on probability theory and statistics (Saint-FF Flour, 1997), 1717:93-199 1911, 1999.
Song. J., Meng, C., and Ernon, Denoising diffusion im- plicit models. arXiv preprint arXiv:2010.02500 2020a.
Martinelli, F. and Olivieri, E. Approach to equilibrium of glauber dynamics in the one phase region: I. the attractive case. Communications in Mathematical Physics, 161(3): 447 486, 1994.
Song, Y., Sohl-Dickstein, J., Kingma, D. P., Kumar, A., Er- mon, S., and Poolc. B. Score-based generative modeling through stochastic differential equations. arXiv preprint arXiv:201 1.3456,, 2020b.
Martinelli, F., Olivieri, E., and Schonmann, R. H. For 2-d lattice spin systems weak mixing implies strong mixing. Communications in Mathematical Physics, 165(():33-44 1994.
Sun, H., Dai, H., Xia, W., and Ramamurthy, A. Path auxil- iary proposal for meme in discrete space. In International Conference on Learning Representations, 2021.
Sun, H., Guha, E. K., and Dai, Annealed training for combinatorial optimization on graphs. In OPT 2022: Optimization for Machine Learning (NeurIPS 2022 Work- shop), 2022.
Metropolis, N., Rosenbluth, A. W., Rosenbluth, M. N., Teller, A. H., and Teller, E. Equation of state calculations by fast computing machines. The journal of chemical physics, 21 21(6):1087-1092 1953.
Sun, H., Dai, B., Sutton, C., Schuurmans, D., and Dai, H. Any-scale balanced samplers for discrete space. In The Eleventh International Conference Learning Repre- sentations, 2023a.
Montanari, A. Sampling, diffusions, and stochastic localiza- tion. arXiv preprint arXiv:2305.1063 2023.
Montanari, A. and Wu, Posterior sampling from the spiked models via diffusion processes. arXiv preprint arXiv:2304. 1149, 2023.
Sun, H., Dai, H., Dai, B., Zhou, H., and Schuurmans, D. Discrete langevin samplers via wasserstein gradient flow. In International Conference on Artificial Intelligence and Statistics, pp. 6290-6313. PMLR. 2023b.
Nishimori, H. Statistical physics of spin glasses and in- formation processing: an introduction. Number 111. Clarendon Press, 2001.
Titsias, M. K. and Yau, C. The hamming ball sampler. Journal of the American Statistical Association, 112(520): 1598-1611, 2017.
Rhodes, B. and Gutmann, M. based meme in discrete spaces. arXiv preprint arXiv:2208. 00040. 2022.
Enhanced gradient-
Wang. A. and Cho, K. Bert has mouth, and it must speak: Bert as markov random field language model. arXiv preprint arXiv:1902.04094, 2019.
Roberts, G. O. and Tweedie, R. L. Exponential convergence of langevin distributions and their discrete approxima- tions. 1996.
Wu, I.. Poincaré and transportation inequalities for gibbs measures under the dobrushin uniqueness condition. The Annals of Probability, 1960)-99999999 2006.
Rombach, R., Blattmann, A., Lorenz, D., Esser, P., and Ommer, B. High-resolution image synthesis with latent diffusson models. In Proceedings of the IEEE/CVF con- ference on computer vision and pattern recognition, pp. 10684-10695, 2022.
Zanella, G. Informed proposals for local meme in discrete spaces. Journal of the American Statistical Association, 115(530):852-865 2020.
pattern

---

Sampling from Binary Quadratic Distributions via Stochastic Localization
Zhang, R., Liu, X., and Liu, Q. A langevin-like sampler for discrete distributions. In International Conference Machine Learning, pp. 26375-26396. PMLR, 2022.
Zhang, Y., Ghahramani, Z., Storkey, A. J., and Sutton, C. Continuous relaxations for discrete hamiltonian monte carlo. Advances in Neural Information Processing Sys-
tems, 25, 2012.
12

---

Sampling from Binary Quadratic Distributions via Stochastic Localization
A. Related Work
Discrete MCMC Samplers The Gibbs sampling algorithm, which is equivalent to Glauber dynamics in statistical physics, has been widely used to study statistical physics models (refs) and train deep ameryy-based models (Dai et al., 2020; Wang & Cho, 2019). To improve sampling efficiency beyond traditional Gibbs sampling, recent works have focused on locally balanced proposals (Zanella, 2020) that leverage local information such gradient-like quantities. These methods modify the proposal distribution by incorporating local structure of the target distribution, leading to more informed transitions. Notable examples include Gibbs With Gradients (Grathwohl et al., 2021), which approximates probability ratios using well-defined gradient information in discrete space, Path Auxiliary Sampler (Sun et al., 2021), which constructs auxiliary paths to enable oongrrange transitions while maintaining detailed balance, and Metropolis-Adjuseee (Zhang et al., 2022) also introduces the gradient information and updates dimensions in parallel by factorizing the joint distribution. When second-order information of the target distribution is available, (Zhang et al., 2012: Rhodes & Gutmann, 2022; Sun et al., 2023a) leverage the Gaussian integral trick (Hubbard, 1959) to transform discrete sampling into continuous sampling, enabling the use of numerous well-developed continuous MCMC samplers.
Langevin Algorithm
Stochastic Localization Stochastic localization (SL) (Eldan, 2013; 2020; Chen, 2021; Eldan et al., 2022; Eldan & Shamir, 2022) is recent method for proving properties of measures such as concentration inequalities and measure decompositions. Chen & Eldan (2022) further developed it into a technique for studying mixing time of Markov chains. Additionally, it naturally produces a sampling framework which has attracted the research interest of many data scientists (El Alaoui et al., 2022; Montanari, 2023;
Grenioux et al., 2024; Anari et al., 2024).
The main challenge of sampling via SL lies on Bayes estimation of posterior expectation. For discrete targets, El Alaoui al. (2022) first use SL sampling from the an approximate message passing (AMP) algorithm and a process for minimizing the Aanuless-Anersoon--- Palmmer (TAP) free energy via natural gradient descent (NGD). Furthermore, they extended this approach to mean-field models (Alaoui et al., 2023a), spiked models (Montanari & Wu, 2023) and spherical spin glasses (Huang et al., 2024). For a certain class of non log-concave continuous distributions, SLIPS (Grenioux et al., 2024) samples from d via Merropolis-AAjustte Langevin Algorithm (Roberts & Tweedie, 1996) to estimate posterior mean. In continuous case, log-concavity of distribution implies easier sampling (Dwivedi et al., 2019). SLIPS proves duality of log-concavity to show its efficiency. However, for binary distributions, quadratic term will collapse into constant (x²2 = 1, {-1,1] 1))) or linear term (x² x, x E {0, 1)"), which poses difficulties for theoretical analysis.
(SK) model, where posterior estimation is obtained by
B. Background
In this section we will outline some background of stochastic dynamics of algorithms and our theoretical techniques.
B.1. Fundamental Definitions of Stochastic Localization
A stochastic localization process (v is defined as
du (x) (x)= = Fr (x),
dv
where the functions F3 solve following stochastic differential equations:
Fo(x) = 1, dFF(x)) =
: (x) - m(())) C,dB,), Va,
(22)
where m(v)= = f (dx),, (Ct), is an adapted process which takes values in the space of n x positive-definite matrices, (Bo) is a standard Brownian motion on RT. We can also use linear-tilt form describing stochastic localization process
(dxx) 2 (2
v(dx)
where ا - C.ds, w- 5x (C.dB, + Cmm(vs)ds) and Ze is a normalizing constant.
key property is that for any measurable set A C Ω stochastic localization process v/ (A) almost surely converges to either or as f. - oo and the concentrated point distributed according to the law v.
13

---

Sampling from Binary Quadratic Distributions via Stochastic Localization
Lemma B.1 (Proposition 10 of (Eldan Shamir, 2022)). Let at m((e), the process a, almost surely converges point in SI and d.e lime- 0g is distributed according the law v. Moreover, the measure Vt almost-surely weakly converges to Dirac measure at dee.
Lemma B.1 suggest samples 0es can be obtained by stochastic localization process.
B.2. Generator and Dirichlet Form of Glauber Dynamics and Metropolis- Algorithms Consider (F:, d) is polish space equipped with the Borel field B, and the Gibbs measures spin space F.T
Glauber Dynamics is Markov process of pure jumps. If the configuration present is z, then at each site i, it will change to x' according to the conditional distribution v(x; (rw))) The generator of Glauber dynamics is
- [oDI(x) = Σ ((x) X.1 = - ((x))
'ET
And the associated Dirichlet form of Glauber dynamics
EaD(f.) = EY,
[(E(J(() X..) )(x))²
(23)
SET
Hatropolis-Hasstin. Algorithms is a reversible Markov chain with transition function:
p y) Ply x) = (1 ()) min
if ty
My x)
and
( v) v(x) x))
Ply x)= = 1 Σ (y x)) min
if
az
where v/ is the proposal distribution. The generator of Metropolis- algorithms
(MHf(x) - = J Ply - -
FT
And the associated Dirichlet form of MetropolissHaatting algorithms is
EMH (f( 2 ET KET
v(dx) (f(x) -
(24)
B.3. Dobrushin Interdependence Matrix
Interdependence matrix serves as a fundamental tool in our analysis. providing rigorous way to characterize dependency relationships among random variables. This concept, deeply rooted in probability theory and statistical physics, allows us quantify the strength of interactions between variables. We now present its formal definition.
We-Wasserstein Distance Let (St d) be Polish space equipped with the Borel field B. For p 2 we denote by Pd. p(2) the space of probability measures on (2,, with finite p-th moment. For any Vi, 12 p(?),, the JP-Wasserstein distance is defined
Wna(Ui,, v2) = inf (N d(z, v) dy)
(25)
where the infimum taken over all probability measures π Q Ω with marginals 11 and vn respectively. the special case where d(z, y) Lessy we have
W Wi,(Fi, 12) sup (A) - 12(A) = 111 221TV.
AEB
14

---

Sampling from Binary Quadratic Distributions via Stochastic Localization
d-Dobrushin Interdependence Matrix For E [N], let (+(+2)) denote the conditional distribution of iy given Tui- The d-Dobrushin interdependence matrix C = [CI)). is defined by
Wi,a (1s( x).44( v)) d(zz.y0 Us)
Cj = sup -=y
2,J [N]
(26)
where each entry Ciy quantifies the influence site j on site The classical Dobrushin uniqueness condition (Dobruschin, 1968; Dobrushin, 1970), sup; Ej Cij 1, provides a sufficient condition for the uniqueness of Gibbs measures in spin glasses. For a more general generator on 1 given by
Cf(x)
Σ Σ SCIN -1,19
/
Js(a, -
(27)
where Js is a bounded nonnegative kemeel representing the local jump rate, the Dobrushin interdependence matrix takes the form
Cty = Σ cs(s).
(28)
iES
Here, cs 2 the optimal constant satisfying
sup w= d(z), v1) / ((ss)( - Js(y, dzs))l
ES
S (s( (9)(
for all Lipschitz continuous functions 9. where d,(g) sup su
19(0) -(x) d(yc..)) When d is the trivial metrie, we have
cs( S 2 x=y off
sup
-)) - Js(y. )lrv.
B.4. Poincaré Inequalities for Gibbs Measures under the Dobrushin Uniqueness Condition
In this subsection, we present the mathematical techniques employed in our study, For stochastic dynamics with given generator, Wu (2006) derives a sharp estimate of the spectral gap (or Poincaré constant) through the spectral radius analysis of the Dobrushin interdependence matrix.
Consider the generator
LS = IPn - S).
EE
where i4 := (4 (zx) is the local specification of Gibbs measure ET, that is, for each i T the conditional distribution of knowing Zy { coincides with the given p+(-(z). It generates Glauber dynamics. Then we have following Poincaré inequality for Glauber dynamics.
Lemma B.2 (Theorem 2.1 of (Wu, 2006)). Let (C) be the spectral radius of the Dobrushin interdependence matrix C = (Cg))see defined in (26) (which is an eigenvalue of C by the Perron-Frobenius theorem). If (Cp(C') < 1, then
(1 - (() E.
Σ Pdlss)) Aʃ (EE,,EET.0)
GET
where v(f.g) denotes the covariance of J. under u, and us vz = v;(sg) vz(s)s)))) is the conditional covariance of f, g under 14 with 2r fixed.
For more general generator (27)
C](x)= = Σ /
Js(a, dzs) f(x))
SCN
15

---

Sampling from Binary Quadratic Distributions via Stochastic Localization
Assume that for each S T and for every T, there some finite optimal constant Cs(j) 2 0,
/ g
g(zs) (Js(2, dzs)) Js d2s) S cs(s) Σ (g(g)
sup z=y ofl d(zz, v/)
iES
for all Lipschitz continuous function g on E" And
15(v) f(:)
6f(f)
sup
o=yotts d(vi. x.)
Lemma B.3 (Theorem 3.1 and Corollary 3.5 of (Wu, 2006)). Ler
1 inf inf Js(ez, E #ERT VET
S31
For Dobrushin interdependence matrix C defined in (28), assume Tsp (C) < 1. Then Markov semigroup P. = ell has unique invariant measure v such that fgr d(z, y)v(dy) < +00 every z. Moreover for each x E ET,
Wi,d (Pi(z.)),)) - of max I(e / d(z, d(a.g)v(dy) se tt ( f d(z, vlx.y)
FT
C. Proofs for Main Theorems
General Proof Sketch. Our proof of the Poincaré inequality follows three key steps.
First, we construct the d-Dobrushin interdependence matrix C' from the algorithm's transition kernel;
We then establish upper bounds on the matrix entries Cjj. which leads to a bound on the spectral radius of C.,
Finally, we leverage this spectral bound to establish the Poincaré inequality.
C.1. Proof for Theorem 3.1
Proof. Define the Gaussian integration
$(x)
1
e 2 dy.
V 2T -o0
By definition
a(t) 12
P(M 2 5) =P(Ia(t)X(+o0
+ 2 2) P
C - all - $
ove (-o-== =(())())
S
=1-
ove ovt)
Obviously,
0 x ( + a(1)
ovt ovt) + (- (-OVE ovt + a(l)
ove) s $ ( S
ove all $ (5
a(l) ovi)
Because a(t) ovt + +o0, there is T large enough, such that for T, we have
5 a(l)
<
o ovt) Ss.
Finally, we know that for arbitrary Ç > 0 and E > 0, when t 2 c)),c)
P(|| () > -
16

---

Sampling from Binary Quadratic Distributions via Stochastic Localization
C.2. Proof for Theorem 4.3
Proof. The conditional measure v(z; Iwii is
((,,Wx)+(a..))
(B [nii)
Ex E e ((o
e- Exzi War Wa k Whenyee Exg here
Em,=11 e Eeys Wazzex Wh: 4 Eniges Wy + huRk
c Enpi Warki
2 2ize Wirm + e Eizss Wi
Because
W1. W1,( (mne) uan (nm)) sup |1 xmme) V9 &wa)ll, AEB
where {0, (+1, {+1}, {-1}}. For == {+1}.
(2, +1 xnni)= - 1/3, (2;; = =+1 {ms))
c Extr, Wiansthi
- Exsry -h Woy
cooh
Exfis WOEK h4 2 W
cosh (-2 Exshos Wirk + h4 -
and for A= = {-1},
12,, 11 amd)) V3,1 - (
@# Eners Wo
c Enxrs Wi
2 cosh
(- Exyie Wi + h4 [
cosh (- Exyiss WarK + h4 14-4--0 Wiy
Consider function
ex
E 2 co)h(w))
(z)
-2((x) (
2 cooh((z)
we know that Taking ho such that
(x(x) = -bb()) = (e + e-0
Bsup
Wix 5 ho,
iET kii
then
8
ho
Σ
WK Wijar
2
S
sup iET kzi
Σ Wixl S
2
Hence, for h 2ho
3ho
h
ho
<
3
Σ
WaT - Wis + h -
8
ho 2
+ h.
2
2
2
2
kzijj
17

---

Sampling from Binary Quadratic Distributions via Stochastic Localization
and for h -2h0
ho
3
8 Wi - h
ho
3ho
h
I
Σ
W
+
2
2
2
2
kpid
Putting everything together we get for [h]] = 2ha
3
B
3h0
Σ
War
Wiy + /
2
2
2
2
and
3
B W Wiyzy + h
2
2
W Wk
2
+
Hence, for
2 sup iET
Σ
Wlal S |//,
light
we get
Wi.dV3,. |<ns). (3,1 {nws) = sup
(B A| xmns) (A &mwill
AEB
2
8
W., (3gg - (..)) -
2, W
2
which implies
Wi.a 12) 10,.1(1100
2 15
Cty := sup ==y
2, [N].
((I)))))
31h1
31A
e
Hence,
W 13
[h]
|C]| sup
Σ JE(N)
Cjj S sup
SINI
3|A
8Ihl
31h
JEIN] e
E
Therefore
sp (C) I ||
31
Combine with Lemma B.2, we have
Varvs. (
(fD(f.f)
36
31
C.3. Proof of Corollary 4.4
Proof. The following lemma gives Chernoff-type bound for Markov chains.
Lemma C.1 (Theorem 3.6 of (Dubhashi & Panconesi, 2009)). Let X2......., X,, be a sequence generated by a irreducible and reversible Markov chain on a fintte set with invariant distribution and spectral gap 7/. Then, for any initial distribution qi any positive integer n and all 0.
22n
Pg
Σ
f(x))
nT(() 28 S Cr..n.g exp
Cn.
where is an absolute constant and Cr.nnng a rational function. Lezaud (1998); Gillman (1998) also prove the same result.
18

---

Sampling from Binary Quadratic Distributions via Stochastic Localization
well-known that Glauber dynamics is reversible with respect Gibbs measure "3.6 (Bertoin al., 1999). And consider sampling from finite set {-1, 11,1%, thus Glauber dynamics is irreducible. From lemma C.I, we have
Pg
Eug. [X] 23 S
where Ygap is spectral gap of Glauber dynamics corresponding to vg Combining with Theorem 4.3, we have "gap
1
C.4. Proof of Theorem 4.5
Proof. For E T, x + with probability
P(a" x)) min 1/ (3)x((') (3)
min(1, e Egges Woya 22 },
and keep invariant with probability
1 P(x") xx) = min e 281; 2 Esrr Wesory-hhaap
Then
T
Cf(x) = (f(v) - f(x))p( (²) 12) = Σ / (f(x")- - P(x) xx)
ET
i=1
T (f(x)) - f(x)) min (1, 23n, Eyec W,y 22hre1 }.
minn(1,e
Define the local kernel as follows
220, Eses Weyzay221zz 1; vx(x, mmin=,,,mnn(1,, 20,,
Obviously, vs (x, E+) 1 for any then 17 1.
ci()) sup (x, :) u, :) Tv
sup sup (x, B) 14 B)1 z=2 off B
a=ã off
= sup (u A) - v;( A)I
==á off B;
max min 1, 202, Eeyie Wuzz 22 2hu0, min (1, 20 220, Exors 23. 2/,
sup
== oll
- + min(1, [1, 23v; Eeasi Wu 1orrs-2844 280 2hx -2hc2:: min(1, 29c, Entis -
}
min (0,1lec 28z. Ensir + 221 - min(1, 280, Eisrs Werre
(auea-28811. 28x, Wiy. 2hea
= sup == off
Because
233
Σ
WAT + 28W
S 2, sup ieT k
Σ
Wal S 2hn-
Hence, for h = 2hg
-3h 23
Σ
W Wart 2,W,,ar 2h < hh
k
-3h < 23
WInT 2,W 2h < -h,
19

---

Sampling from Binary Quadratic Distributions via Stochastic Localization
and for h -2h
2ho S 23
Σ
W. + 2,3W - -2h S 6ho
2hn 2B
Σ
WAATE 2,3W,,u3 2h 6ho-
Putting everything together we get for |/| = 2/o
23
Σ
War 28W 2h 2 2ho-
Hence,
a(i) = sup
min 1, e 20x, Eners +200, Wija, 22; min (1, 200; Eeas, 2, -2,22.)
== j
Se 2ha A, W.]] = - W-14l,.WWyll
Finally,
[1 sup Σ a(j) < 2///e= 1l, JE[N]
and by Lemma B.2, we can get
(1) 1 2) h1 1b| (f. (f:
C.5. Proof of Theorem 4.6
Proof. The transition matrix of Metropolis chain is
Ply a)) V(a,, v) min (v) v)
J. if + y.
(3) xx)
and
(z) v) <x) x))
P(y x) 1 Σ (z v) m1n
if y.
zzy
Particularly, on the configuration (+1,-1}* the dynamic flips one site each time, that is for Ir yl 2
Ply x) O,
and for i [N], x + o² with probability
(3)
M/.. (y) (x x.)
P(x x) = V((' (x) min(in
M3,n (x) (xr [x)
and keep invariant with probability
(a. (x |x') (x) V |x)
1 P(x" x)) = (aa"
()) min
20

---

Sampling from Binary Quadratic Distributions via Stochastic Localization
Then
- [f(x) = { (f(v) - f(x))(( x) Σ} ( (xx) xx)
FT
= (f())) m)) T(x') a(x') V x²)
T
(x)) xx)
1=1
Define the local kernel as follows
(r (ar' x) min (a.(("")\(aa xx))
Obviously, (2, E*) for any x, then 17 = 1.
For B = {+1, -1. +
c(j)
sup [, v1( 'rv
sup sup (u, v)
x=2 off
z=š off
= sup sup 1/ (Z A) - vi(imss:4) A)
æ=i off j B,
sup
m py (Ziis +1) 2/3 ( +1] |1),, (2: 1s (i -1]1}
==$ off
= sup max (xx' ()) min P/ (3 Va( x²)
V6 | ()) min ( 21)
1/3.1 (x) Vr x))
1/3 ( L 2)
a=á off
(=.n(r") x²)
(2*) (')
(xr 2)) min
1 4 () min
1/3, (8) V [))
VAA (x V (+))
M/ ( 11)
V(('" x)) min sup 2=
( ()) min(1,
1/..1 ( M (#f [t) $
CLip( h)/sW,y-- (.)
V/ (x) \z) [x)
Hence,
||]|,x = sup Σ a(i) CLip(B,h))b..
SE(N]
which implies the Poincaré inequality
Varvs. 5 1- Crip(B,
EMH(F (f.f)
C.6. Proof of Theorem 4.8 Proof. For Gibbs measure
e (()
V3.h
Zen
we consider the following with kernel
(x. [/ (x: xt)
P(z((z) (( (x) min(1,
13,6 (x) 4 (xr x))
where
1 +
Br; Eier Wiy hhn;
V (x" x))
(x)
(zz)
21

---

Sampling from Binary Quadratic Distributions via Stochastic Localization
and
Zp,((z) =1 + e0 Eiss Wis -hn;
then
(x" x) = (x)
1
(o: (a)-bb)) -a,b)
Aas Es Way -aar har
+ So Eiste Wisary-hur
e Eyes Wasery Shhn
6 2dl; Eبزب Wiy he, + ez Enzs Wisss hhx
and
e 3a. Eyer Wiyaytshas
(x x²))
c 20 Eii Wazs 2 hiz + dr: Ejni Wasy -
Hence,
(x xn)
e t.w Egeer Way
Sm: Sini Wejoy-- = = B2, Digs the.
(x [x)
Furthermore,
e Ha, Exsrr Wieas - Ba, Wajmy har,
(6 ())
f0, Eepis Wuxe+ Bz, Wo, gaz 38z; Exyr, Ware 30, W., h e ne. Exet, Wann + Ba, Wiymy+ home
(
(+)
titte Expii W hoz g00; (z; Exyiis Ware 38r,Wi;7, -
and
V (
8*
BR, Exres Wayay,tt
=6
V
1
②)
Besides.
(2²)
20w: Degir 22 -2az; 133,((") (f)
28a Eners
(z)
and
(x")
(x x²)
=t Be, Expr. Waze BB 200, 20 Expro W2xx+292,W 2hr
(2) (xt xx)
Bw, Exsrs Warz+ W,yay
Ms,h (a*) ( 21)
Bz, Exgry Wase-BaWay--aa
19.6 ( V
8)
Consider the function
1 - c
f(z,y) = 1 +exty
2
2(1 cuty)
then for yı, 1/2 E (-oc, -x) ((=x, +00)
(s yn) [(x, 5
81
(e
x+y
+ e
22

---

Sampling from Binary Quadratic Distributions via Stochastic Localization
for 1/1 -x S y2
1
(f f(z, s(f f(x, -z)1
31
(e zix
te 10=2 22
y2 V1l
2.
+
I )
Denote that
I = Bor
Σ
WR har
y = Sx, W.yaz.
Recall that for h = 2ho
ho
ho
3
8
h
hg
h
<
Σ
WH
-
Wayzy
+
2
2
2
2
2
2
2
2
kjij
and for -2o
h
hp
3
3
hp
hg
2
2
S
Σ
+
2
2
+
kfij
Putting everything together we get for |h|] = 2hu
3
B Wijay
h
ho
WREKE
+
2
2
2
Hence,
(x 2) min(1, (2' [z 22))
(3.n('') ( $1)
(0( 8) min(1,
1/ (x) xx)
Vo.n ( ( (6' ())
(
e (w-v) v)
min cnty}
min
e (a++)) e (z+9)
( e ()-ッ))
1
min 6-
min min c
+ e- (a+a)
1 + e
2
(e 2 + e 3
28 2
Ar, Exery WinTE hr, +BF, W
Be, Ekgi, Wip +ho, -Ar, W.y
161 (e 7 + )
Finally, we get the estimate
2 أز
a(f)
18 y2
(e +
Using Lemma B.2, have
1
Varuy, (f) 5
(fn(ff))
M
(0
23

---

Sampling from Binary Quadratic Distributions via Stochastic Localization
C.7. Proof of Theorem 4.9 Define the transition kernel Jr -x) follows
T
T
Bz. Eisi Wiyz--hu ha.
(x. -2) = II
M r
2 =
Gz Ezzpe W1 har
and
Ga: Exst Wisdis h
II v ())
+ e Ben Esui W,
where x 2 off j. Then
II
V
(x
II T (+ (&)
T
x))
V
(ar
xr) - ((0) xx)
(1* ())
T
Aog EESti Werer Wi,
T
Ba; Exzes Wirmy Ba, Wajay hzz
x))
BR, Exsro Wa v( (+)
II
1
Bx. Exprs Wise- Say, W.y her
ifj
N
fz()) 11 f()),
where
Bzx Engrrt Wase Dos
[i(x)
1 + e Gas Exsis Winzet Wajary har -ax; à # 5
and
Ba, Envis Wyxze -hay
Bwg Dess W Wyezether
fz(z) (((" x)
f,(8) V000 (
1 + Ras Exer Wynea hay
1 +e -ag Exzs W Wyyngtha
Recall that for ho 2 0 such that
Ssup
Σ
W S hos
GE
then
8 Σ
Wann + BWiy
3 sup Σ
Will ho-
iET kzpt
Hence, for h 2ho
-3ho 3 Σ
Waze + 3Wyz - 5 -ho-
kti.j
and for h -2hn
ho < 333 Σ
Wat + BWWr, - h S 3/o.
24

---

Sampling from Binary Quadratic Distributions via Stochastic Localization
Putting everything together we get for [h]
2ho
3
Σ
Wa BW h 2 ho.
For |v| 2 ho
0 v
-- t [e + + )²
dy
+ e2
Because for any E [N]. 0 < V((x x)) v 1, then
N
N = (x
N (a') 2) II
v
(a'
())
x
(x*
x)
(a xx)
1=2
2=2
+
(
2=2
1=1
N
NN
N
(1)
x)) ( E))
II
(ax
x²)
+
( ())
II
(x
x))
II
v
a)
NV
N
1/ (x [x) - V6 | { +
(x
xr)
II (a* (+)
N
Vi (x) (0* [T)
For # j
2 [W
(( x)) "0(''
(e
kp
For i =j
28 Σ
kyj W + 2/hl
(x x)
(8 |
233
Σ
W Va 2h
S
ha (e
2
(e - + + - 7)²
+ e
Hence
N II V (ar x)) II
23 W
23 Ex [W + 2/h
Cjj = (m(()==
sup
Va ())
x= off
(e
te )2
(e "p - -
R=1
i=1
23 29(E 1z4
Wesl + Σkej
Ws + 2/h|
4h
(e +
16
(e +e 11
Finally,
4|h
||C|| = sup Σ
-0)>
(e + + =
[N]
JEIN
Combine with Lemma B.2, we have
1
Var {
f(f.f).
AN
[6]
(e
+e
4" )
25

---

Sampling from Binary Quadratic Distributions via Stochastic Localization
C.8. Chernoff-type Error Bounds for DMCMC Samplers
This section details the derivation of Chernoff-type error bounds for the Monte Carlo estimators based on DMCMC samplers, expanding upon the theoretical results presented in Section 4. These bounds quantify the concentration of the sample average around the true posterior mean. For sequence of samples {_1,, X2..., Nn generated by DMCMC chain, establish the following corollary:
Corollary C.2. Let X1 q denote the initial distribution of the samples. Under the assumption that the Gibbs measure (13) satisfies the large field Condition 4.1, for any E > O, the following Chernoff- cerreoff-rypeee error bound holds:
Pg
Σ
X: Eup [X] 28 _8
S Cc
where e is an absolute constant, Co is a rational function, and the spectral gap "wop is specific to each DMCMC algorithm:
For classical Metropolis chains, "leap = 1 2// 11;
For the single-site gradient-inforee MH algorithm, "gap =
16 (e +
16
For DULA, Yggap
N + )2
Proof. Our approach leverages general results on the concentration of measure for Markov chains. A Hatropolis-Hastinge
(MH) kernel P(x'|t (z) is typically defined by:
P(=|=)) = (x min {1 Ma. (x/x')
(3, V (x'(x)
where (-I--) represents the proposal distribution. A key property of these MH kernels is their reversibility with respect to the target Gibbs measure V3 Furthermore, given that we are sampling from a finite state space ( 1,,, these MH algorithms are inherently irreducible.
These properties reversibility and irreducibility are precisely the conditions required for Lemma C.1 to apply. Lemma C.1 states that for reversible and irreducible Markov chain, Chernoff- type error bound of the form
1 Σ x. n
Pg
Evg, [X]
[X]
ZE
Crempnnge
holds, where Tgap is the spectral gap of the underlying Markov chain.
Finally, by incorporating the specific spectral gap calculations derived for each DMCMC variant-classice Metropolis chains (Theorem 4.5), single-site pradient-informer MH (Theorem 4.8), and DULA (Theorem 4.9) -we substitute their respective Tgp values into this general bound, thus completing the proof.
D. Experimental Miscellaneous
In this section, we first benchamrk the QUBO instances in section D.1 and provide detailed experimental settings for reproducibility in Section D.2. We then present additional experimental results in Section D.3 to further validate our framework's 's effectiveness. Finally, in Section D.4, we conduct comprehensive ablation studies on various components of our framework, such as the a-schedule in SL and the influence of hyperparameters on sampling performance and convergence properties.
D.1. QUBO Instances
In this section, we describe the form of Binary Quadratic Distributions for the QUBO instances used in our experiments. For instances with {0, 1 we transform them (-1,1)N through the mapping y = =+1 in our experimental setup.
26

---

Sampling from Binary Quadratic Distributions via Stochastic Localization
Maximum Independent Set Given a graph G -V, with N nodes, the Maximum Independent Set (MIS) problem can be formulated as:
N
max re0,1
c subject to 2,2j 0 for all (2. E E
which can be transformed into a BQD:
p(x) & e - -
where A is the adjacency matrix, 8 is the inverse temperature and À is the penalty coefficient ensuring constraint satisfaction. Following DISCS (Goshvadi et al., 2024), we set c = L, À = 1.000l and use their annealing schedule and post-processing method to obtain feasible solutions. The evaluation is conducted on five datasets: four from Erdös-Réng random graphs ER-[700-800] with densities (0.05, 0.10, 0.15, 0.25] and one from SATLIB.
Maximum Cut
The Maximum Cut (MaxCut) problem on a graph G (V,E) with D nodes can be formulated as:
Σ
1 2422
way(
SE 11))
2
(KJ))E
which corresponds to the following BQD:
p(x) x E - -(Cunee mey (-))))))))
where Wij = 1 in the experiments. Following DISCS (Goshvadi et al., 2024), we evaluate on seven datasets: three from different sizes Rényi random graphs with the density 0.15 (ER-256-300, ER-512-600, ER- 10-142--100),, three from different sizes of Barabási-Albert random graphs (ba-256-300, ba-512-600, ba- ba-1024-1100) and one from Optsicom.
Maximum Clique
The Maximum Clique problem graph G (V, E) with D nodes can be formulated as:
min xE(0.1)
c subject to r,4, = for (i,j) g E
1=1
which corresponds the following BQD:
p(z) x - ((-e"= =1"========"= Az))
Following DISCS (Goshvadi et al., 2024), we set 1, À 1.0001 and maintain the same post-processing method. We evaluate on two datasets: Twitter and RB.
D.2. Experimental Setting
In this part, we provide detailed experimental settings for the configuration of three key components in our framework: the discrete MCMC sampler settings, the Stochastic Localization algorithm parameters, and the exponential decay step allocation strategy.
Discrete MCMC Sampler Settings We employ three different discrete MCMC samplers in our experiments: Gibbs with Gradients (GWG) (Grathwohl et al., 2021). Path Auxiliary Sampler (PAS) (Sun et al., 2021), and Discrete Metropolis- Adjusted Langevin Algorithm (DMALA) (Zhang et al., 2022), for all samplers, we use adaptive step sizes with target acceptance rate of 0.574 and balancing function of g(t) = Vt. The specific configurations are as follows: For GWG and PAS, we configure it to flip one bit at each step. For DMALA, we set the initial step size to 0.2, schedule the step size adjustment every 100 steps, and reset the gradient estimate every 20 steps.
Exponential Decay Step Allocation Given the total number of SL SDE iterations K and total MCMC steps Nu. (10,000 in our work), we need to allocate N, MCMC steps for posterior estimation at each time step I, ensuring Σx N, = Nim- Our exponential decay allocation strategy works as follows: First, we assign a minimum number of steps Nmin to each time step. Then, we distribute the remaining steps N - KNNii exponentially according to N; = Nmin + c.tt/K where r is the decay rate and is a normalization constant ensuring the sum constraint. To handle discretization effects, we floor the continuous schedule to integers and carefully distribute the remaining steps maintain the exact total.
27

---

Sampling from Binary Quadratic Distributions via Stochastic Localization
Table 4. Results of ablative experiments for MIS ER-0.05 and MIS ER-O. 10.
Ablation
SL-GWG
SL-PAS
SL-DMALA
Ablation
SL-GWG
SL-PAS
SL-DMALA
CLASSIC
103.69 1. 1.57
104.31 1: 1.79
103.06 1 1.82
CLASSIC
60.25 1 0.79
61.63 1. 0.96
60,94 1: 1.06
1
103.97 1: 1.55
104.19 +: 1.67
103.41
1 1.85
61.47 1: 1.06
61.75
1: 0.83
60.88 1: 0.96
GEOM(2,1)
104.37 1. 1.52
104.53 1: 1.48
103.59
1 1.80
GEOM(2,1)
61.94 1 0.93
61.91 1 0.88
61.34 1. 0,96
K=256
104.19 +: 1.65
104.53 +: 1.48
103.34 +: 1.57
K=256
61.41 +:: 0.82
61.91 1: 0.88
60.78 1: 0.99
K=512
104.19 +: 1.65
104.19 +: 1.72
103.59 + 1,80
K=512
61.94 +: 0.93
61.78 4: 0.96
60.94 1: 1.00
K=1024
104.37 +:
104.22 +: 103.03
K=1024
61.53 +
61.69 +:
61.34 1:
a=1
103.25 +: 1.70
104.16 = 1.42
103.19 = 1.74
0=1
61.47 + 0.83
61.69 + 0.77
61.09 :: 1,16
o=5
103.81 +:
104,22 + 103.34 = a=10
o=5
61.69 +
+ 61.69
60.81 +: 1.04
6=10
104.00 = 1.54
104.34 = 1.81
103.28 = 1.64
61.66 + 0.92
61,50 + 0.83
61.22 +: 1.05
SL Settings For the alpha-schedule in Stochastic Localization, we adopt the GEOM(2,1) schedule a(t) = -)) as suggested in prior works. We uniform time discretization and employ exponential integrator for SDE integration. When performing posterior estimation in SL, we use the same MCMC sampler configurations as in their standalone sampling counterparts. Other hyperparameters are determined through extensive hyperparameter optimization. Specifically, we tune the following parameters: the number of discretization steps K E (256, 512, 1024), initial and final noise scales Cend E [10-4, 10- MCMC sample ratio (proportion of last samples used for posterior estimation) in [0.1, with step 0.1, MCMC step exponential decay rate in [10-4, 10-1), minimum MCMC steps Nmin E {2, 4, 6, 8, 16, 32), and noise parameter a e {1, 4, 6, 8, 10, 15, 20). The total number of MCMC steps fixed at 10,000. The optimal hyperparameters found through our search will be released with open-source code.
All experiments are conducted on single NVIDIA A40 GPU and an AMD EPYC 7513 CPU. The code is available at https///iiubbbomm//ooooouuusss//
D.3. Further Experimental Results
To provide a more comprehensive understanding of our framework's behavior, we visualize the sampling trajectories for both the base MCMC samplers (DMALA, GWG, and PAS) and the SL-enhanced framework across different test cases. The shaded areas in the trajectories, representing the variance across multiple instances, are generally narrow, indicating the stability of all methods. Most notably, SL-based samplers (solid lines) and their base MCMC counterparts (dashed lines) achieve comparable final performance across all test cases, demonstrating the reliability of both approaches.
D.4. Further Ablations
Based on the comprehensive ablation experiments shown in Tables 4 9, we analyze the impact of three key components in SL: the a-schedule, number of SL iterations K, and noise parameter a.
First, regarding the a-schedule, adopt the geometric schedule GEOM(a1, 022) from SLIPS (Grenioux al., 2024), defined as GEOM(a1, a2 az)(t) + (1 t)- " where E [0, 1] and a 1, 02 0. Both GEOM(I,1) and GEOM(2. demonstrate superior performance over the CLASSIC schedule (defined as a(t) = t) in MIS problems. However, this impact becomes negligible in MaxCut instances, where all schedules perform similarly with variations within 0.1%.
Second, the number of SL. iterations K shows a problem-dependent sensitivity pattern. While exhibits significant influence on performance MIS tasks, its impact becomes minimal MaxCut problems where the performance differences among K=256, 512, and 1024 are statistically insignificant (50.01% % variation).
Third, the noise parameter demonstrates similar problem-specific characteristics. In MIS instances, moderate noise levels (o 5) generally yield optimal performance with notable improvements over other settings. However, in MaxCut problems, the choice of a has minimal impact on the final performance, with variations typically less than 0.05%.
When comparing methods across problem types, SL-PAS exhibits superior performance in MIS tasks compared to SL-GWG and SL-DMALA. However, this advantage diminishes in MaxCut instances, where all three methods achieve nearly identical results.
28

---

Sampling from Binary Quadratic Distributions via Stochastic Localization
Table 5. Results of ablative experiments for MIS ER-0.20 and MIS ER-0.25.
Ablation
SL-GWG
SL-PAS
SL-DMALA
Ablation
SL-GWG
SL-PAS
SL-DMALA
CLASSIC
34.06 1 0.61
33,91 1: 0.58
33.03 1: 0.77
CLASSIC
27.88 1. 0.54
26.50 0.56
27.31 0.58
GEOM(1,1)
34.09 1: 0.63
34.06
1: 0.50
33.97
1: 0.64
GEOM(1.1)
27.56 1: 0.50
27.84 1 0.51
27.44 0.50
12
34.38 0.74
34.38 1 0.54
34.00
1: 0.56
GEOM(2,1)
28.00 0.56
28.03 0.59
27.75 0.66
K=256
34.19 - 0.73
34.25 +: 0,61
33.84 +: 0.62
K=256
27.84 +: 0.57
27.94 +: 0,50
27.41 0.55
K=512
34.03 0.53
34.09 1: 0.52
34.00 1: 0.56
K=512
27.88 1: 0.48
27.91 +: 0.63
27.47 0.56
K=1024
34.38
34.38 +: 0.54
33.72 +:
K=1024
28.00
28.03 0.59
27.75 0.66
0=1
33.72 0.57
33.69 0.58
33.84 + 0.67
a=1
27.81 0.53
27.72
27.06 0.50
0=5
34.22
34.00 +:
33.81 +:
o=5
27.72 0.57
27.94 0.43
27.47 0.50
a=10
34.00 0.43
34.22 + 0.54
33.88 + 0.65
0=10
27.88 + 0.65
27.94 4 0.61
27.75 0.66
Table 6. Results of ablative experiments for MIS SATLib and MaxClique RB.
Ablation
SL-GWG
SL-PAS
SL-DMALA
Ablation
SL-GWG
SL-PAS
SL-DMALA
CLASSIC
418.93
419.35 14.37
415.23
14.51
CLASSIC
87.52 1:
87.59 1:
87.16
GEOM(1,1)
419.03 14.31
419.61 14.37
415.72 = 14.48
G
87.52 = 6.14
87.43 - 6.11
87.10 +
GEOM(2,1)
419.16 14.39
419.71 + 14.35
415.72 = 14.37
GEOM(2.1)
87.60 = 6.16
87.65 = 6.14
87.31 + 6.15
K=256
419.03 14.32
419.71 + 14.35
415.57 +: 14.55
K=256
87.43 +: 6.16
87.65 +: 6.14
87.19 +: 6.08
K=512
419.16 14.39
419.62 + 14.37
415.72 = 14.37
K=512
87.42 = 6.09
87.41 + 6.13
87.18 + 6.06
K=1024
419.03 14.45
419.59 + 14.35
415.66 # 14.52
K=1024
87.60 = 6.16
87.56 6.17
87.31 + 6.15
r=1
418.85 14.31
419.51 + 14.33
415.43 + 14,29
a=1
86.77 = 6.11
87.35 + 6.13
87.08 + 6.11
o=S
419,00 14.37
419.55 + 14.35
415.70 # 14.39
o=5
87.42 = 6.18
87.55 + 6.20
87.26 + 6.16
o=10
419.01
419.71
415.72 14.37
a=10
87.42
87.45
87.31 +: 6.15
E. Computational Complexity Analysis
We analyze the computational complexity of the Stochastic Localization (SL) framework combined with Discrete MCMC (DMCMC) samplers, compared to using DMCMC alone. We consider the total operational cost terms of fundamental operations like function evaluations, for the target distributions consider. Let N be the dimension of the problem (number of binary variables), T be the total number of SI. iterations, and M be the total budget of DMCMC steps across all SL iterations.
-aaddett calculations, matrix operations, these often dominate the runtime
E.1. Baseline DMCMC Complexity
For standard DMCMC methods used as baselines in our study, such as Gibbs With Gradients (GWG) (Grathwohl et al., 2021), Path Auxiliary Sampler (PAS) (Sun et al., 2021), and Discrete Metropolis-adjustee Langevin Algorithm (DMALA) (Zhang et al., 2022), the dominant computational cost per MCMC step typically involves evaluating the target distribution's s sseudo-gradiens or related quantities. For many relevant models, including the Binary Quadratic Distribution (BQD) studied this paper, these operations scale at least quadratically with the dimension, O(N²). Given a total budget of M MCMC steps, the overall complexity baseline DMCMC method is thus O(M
E.2. SI. + DMCMC Complexity
When using SL with DMCMC, the total MCMC budget is distributed across SL iterations. The core cost associated with performing M DMCMC steps remains O(M in total. In addition the MCMC sampling, each of the SL iterations involves few key operations: (1) MC estimation of the conditional mean: This step involves drawing samples from the current posterior distribution and computing their mean. If draw fixed, relatively small number of samples per SI. iteration, this calculation takes O(N) time per iteration as it involves vector operations in R... (2) SDE simulation: Updating the localization variable Y according to the SDE involves vector additions and scaling, which takes O(N) time per iteration. The total computational overhead introduced by the SL process itself, over iterations, therefore O(T x (N + +N) = O(TN). Combining the cost of the total MCMC steps and the SL overhead, the total computational complexity of the SL+DMCMC framework O + TN).
29

---

Sampling from Binary Quadratic Distributions via Stochastic Localization
Table 7. Results of ablative experiments for MaxCut ER 256-300 and MaxCut BA 256-300.
Ablation
SL-GWG
SL-PAS
SL-DMALA
Ablation
SL-GWG
SL-PAS
SL-DMALA
CLASSIC
101.92 1. 1.76
101.91 1: 1.76
101.92 1 1,76
CLASSIC
99.96 1 0.07
99.97 1: 0.06
99.95 1 0.07
1
101.92 1: 1.76
101.92 1: 1.76
101.92 1 1.76
1
99.97 1 0.06
99.97
1: 0.06
99.95 1 0.08
GEOM(2,1)
101.92 1. 1.76
101.92 1: 1.76
101.92 à 1.76
GEOM(2,1)
99.97 1 0.05
99.98 1 0.05
99.96 1 0.05
K=256
101.91 d: 1.76
101.92 +: 1.76
101.91 +: 1.76
K=256
99.96 i: 0.07
99.97 : 0.06
99.96 +: 0.07
K=512
101.92 1: 1.76
101.92 =: 1.76
101.92 : 1,76
K=512
99.97 +: 0.06
99.97 1 0.06
99.96 + 0.07
K=1024
101.92
101.92 +:
101.92
K=1024
99.97 +:
+ 99.97
99.96
o=1
101.90 + 1.76
101.89 = 1.76
101.90 = 1.76
0=1
99.94 + 0.08
99.95 = 0.07
99.81 + 0.12
o=5
101.92 +:
101.92 + 101.92 = 1.76
o=5
99.97 +
= 99.97
99.95 +
6=10
101.92 # 1.76
101.92 = 1.76
101.92 = 1,76
0=10
99.97 + 0.06
99.97 = 0.06
99.96 + 0.07
Table 8. Results of ablative experiments for MaxCut ER 512-600 and MaxCut ER 1024-1100.
Ablation
SL-GWG
SL-PAS
SL-DMALA
Ablation
SL-GWG
SL-PAS
SL-DMALA
CLASSIC
100.16 +: 0.12
100.17 0.12
100.14 = 0.13
CLASSIC
100.08 0.14
100.12 0.14
100.06 0.14
GEOM(1.1)
100.16
100.17 =
100.14 =
GEOM(L.I)
100.10 0.14
100.12 0.13
100.07 0.14
GEOM(211)
100.16 + 0.12
100.17 = 0.12
100.14 0.12
GEOM(2.1)
100.10 0.13
100.12 0.14
100.08 0.14
K=256
100.15 +:
100.16 +
100.14 =
K=256
100.09
100.12 0.14
100.08 0.14
K=512
100.16 + 0.12
100.17 +: 0.12
100.14 = 0.12
K=512
100.09 0.14
100.12 0.14
100.07 0.14
K=1024
100.16 +: 0.12
100.17 +: 0.12
100.14 = 0.12
K=1024
100.10 0.14
100.12
0.14
100.07 0.14
100.15 1 0.12
100.16 +: 0.12
100.11 1 0.13
a=1
100.07 1:
100.11
= 0.13
100.07 0.14
5=5
100.16 1 0.12
100.17 1 0.12
100.14 1 0.13
o=5
100.10 1: 0.14
100.12 0.13
100.07 1 0.14
6=10
100.16 1 0.12
100.17 1 0.12
100.14 1 0.13
a=10
100.09 0.14
100.12 0.14
100.08 0.14
E.3. Comparison
Comparing the total complexity O(MN2+++ + 7N) with the baseline O2MN²), the SL framework adds an O(TN) overhead. In the high-dimensional settings where advanced MCMC methods are typically applied (N is large), and with practical choices for the number of iterations relative the total MCMC budget M, this overhead is often negligible. For example, in our experiments, we used T {256, 512, 1024) while the total MCMC steps M went up to 10, 000. In such scenarios, TN is much smaller than MN Thus, the SL framework allows for potential improvements in mixing and convergence properties by transforming the target distribution towards an easier-to-sample form over time, without introducing prohibitive increase in computational cost compared to the baseline DMCMC methods.
To validate our theoretical complexity analysis, we measured the actual running times across various benchmark problems, as shown in Tables 10 and 11. The results largely confirm our theoretical expectations. For MIS problems, the SL variants show a small overhead (typically 1-6%) compared to their base counterparts. This slight increase consistent with our complexity analysis predicting an additional O(TN) term. In some instances (e.g., MaxClique RB and TWITTER, and some larger MaxCut instances), the SL framework appears marginally faster than the base methods. However, these apparent improvements should be attributed to hardware-specine factors, implementation details, and measurement variability. Such minor variations are common in empirical runtime measurements and do not contradict our theoretical analysis. Overall, the empirical results demonstrate that the SL framework introduces only marginal computational overhead in practice, which aligns with our theoretical analysis where TN < M in high-diiensional settings.
30

---

Sampling from Binary Quadratic Distributions via Stochastic Localization
Table 9. Results of ablative experiments for MaxCut BA 512-600 and MaxCut BA 1024-1100.
Ablation
SL-GWG
SL-PAS
SL-DMALA
Ablation
SL-GWG
SL-PAS
SL-DMALA
CLASSIC
100.87 +
100.92 = 100.77 =
CLASSIC
101.53 0.38
101.66 0.38
101.21 0.39
GEOM(1,1)
100.88 + 0.48
100.92 = 0.48
100.78 = 0.48
1
101.56 + 0.37
101.66 0.37
101.23 + 0.39
GEOM(2,1)
100.89 1: 0.49
100.92 1: 0.48
100.79 +: 0.49
GEOM(2,1)
101.55 1: 0.37
101.66 0.37
101.23 1 0.38
K=256
100.87 = 0.49
100.92 = 0.48
100.78 = 0.49
K=256
101.55 + 0.38
101.66 = 0.37
101.22 + 0.38
K=512
100.88 1. 0.49
100.92 1: 0.48
100.79 1 0.49
K=512
101.56 1. 0.38
101.66 0.37
101.23 i 0.38
K=1024
100.89 1. 0.49
100.92 1: 0.48
100.78 1 0.49
K=1024
101.56 0.38
101.67 0.37
101.21 0.39
o=1
100.77 + 0.49
100.90 = 0.48
100.76 = 0.49
o=1
101.31 + 0.37
101.63 = 0.37
101.16 =
o=5
100.88 1: 0.48
100.92 1 0.49
100.78 + 0.49
o=5
101.55 0.37
101.66 0.37
101.22 0.39
o=10
100.88
100.92 + 100.78 +
a=10
101.55 0.37
101.67 0.37
101.22 0.39
Table 10. Running time (in seconds) on MIS and MaxClique benchmarks for various methods and their SL variants. Bold values indicate faster performance between paired methods.
MIS
MaxClique
Method
ER-0.05
ER-0.10
ER-0.20
ER-0.25
SATLIB
RB
TWITTER
DMALA
23.873
35.511
77.866
103.636
188.901
3025.712
120.634
SL-DMALA
24.997
37.621
78.494
104.367
200.743
3013.018
117,597
PAS
32.648
44.558
86.655
112.305
377.038
3049.668
125.222
SL-PAS
36.134
49.425
90.428
1 115.630
388.979
3041.619
125.502
GWG
27.249
37.743
79.305
104.461
326.739
3030.762
117.964
SL-GWG
28.056
40.556
81.412
106.017
330.687
3031.967
119.806
Table Running time (in seconds) on MaxCut benchmarks various methods SL variants. Bold values indicate faster performance between paired methods.
BA
OPTSICOM
Method
256-300
512-600
1024-1100
256-300
512-600
1024-1100
DMALA
167.341
755,462
2814.459
75.166
141.391
271.073
4.772
SL-DMALA
169.672
759.201
2807.121
81.436
148.428
284.511
7.459
PAS
196.667
815.633
2873.359
133.742
267.957
591.858
6.647
SL-PAS
201.665
820.853
2869.082
140.680
279.453
619.575
10.487
GWG
178.039
780.655
2943.244
714.469
2749,896
7872.727
6,476
SL-GWG
181.171
784.497
2936.596
710.698
2695.718
6802.453
9.146
31

---

Sampling from Binary Quadratic Distributions via Stochastic Localization
Sampling Trajectories: Comparison of Different Samplers Across Datasets
DENSITY ER
MIS-ER_DENSITYA
Objective
Objective
24
10
MCMC
Sceps
Steps
MIS-ER DENSITY-R-0.25
MIS-SATLIB
MAXCLIQUE-RB
Objective
Oblective
Best Ratio
204
204
4043
2000
MCMC Steps
MCMC Steps
MCMC Steps
MAXCLIQUE-TWITTER
MAXCUTERRAER--115-222--0-0
SANCUT-ER--ER-0.-----522222
Best Ratio %
Best Racio
Dest Ratio
3005
1002
4000
1004
94
2512
4330
6I0E
8600
20080
1000
CER
3981
MCMC Steps
MCMC Steps
MOMC Steps
MAXCUT-ER. R-ER ER 0.15 N-1024 1100
MAXCUT- OPTSICOM R-B
MAXCUT-BAA BA BA N-256-300
1.4
0.
Best Rabio %6
Best Ratio %
Best Ratio
80
2002
4023
4030
IICE
1000
06
2010
PICE
2000
233
1530
MCMC Steps
MCMC Steps
MCMC Steps
MAXCUT-BB -BA R-A-R-BA-4 1AA4--N-52 N-512-600
MAXCUT-BA- 4-B...N.. 1024-1100
Best Ralio %
Best Ratio
06
MCMC Steps
MCMC Steps
Figure 2. Sampling trajectories comparison between MCMC samplers (dash lines) and their SL-based counterparts (solid lines) across different datasets. The shaded areas in the trajectories, representing the variance across multiple instances
32


Reviews:
[{"review_id": "XR1y2WKftm", "reviewer": "Reviewer_4aF7", "summary": "This paper studies stochastic localization for sampling from binary quadratic distributions.\nAs a main theoretical contribution, the authors prove Poincare inequalities for the sampling procedure from the (discrete) posterior distribution \\\\(q_t(x \\mid y)\\\\) in stochastic localization, and thus establish the convergence rate of the posterior sampling step.\n\nA key implication is that the spectral gap for posterior distribution sampling increases as the time \\\\(t \\to +\\infty\\\\).\nThis is achieved by an asymptotic argument.\nAs a result, posterior distribution sampling becomes easier and easier in the later stage of stochastic localization.", "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": "We sincerely thank the reviewer for these insightful comments.\n\n## W1\nFrom an experimental perspective, the absolute improvements are indeed modest. However, we would like to emphasize two key points:\n1.  **Strong Baselines:** Our comparison is between standard DMCMC and SL combined with the *same* DMCMC sampler (SL+DMCMC). The base DMCMC samplers used are already highly effective, demonstrating strong performance on their own. As shown in Table 3, all DMCMC baselines significantly outperform the commercial solver Gurobi, indicating they are already operating near optimal performance levels for these challenging tasks. The fact that SL consistently provides further improvements, even on top of these powerful, well-established DMCMC methods, highlights its efficacy.\n2.  **Benchmark Standards:** Our experimental setup, comparison metrics, and implementation strictly follow the established DISCS benchmark [1]. As evidenced by Tables 5-7 in [1], even state-of-the-art DMCMC samplers often exhibit performance differences within one standard deviation of each other. Substantial performance overlap when considering one standard deviation is common in this domain. Therefore, comparing methods based on mean results is standard practice, as adopted in [1] and our work.\n\nThanks for highlighting this point. In the revised version, we will **add text to better characterize the near-optimality of these baselines** to properly contextualize SL's performance improvements and clarify the standard deviation reporting convention.\n\n[1] Goshvadi K, Sun H, Liu X, et al. DISCS: a benchmark for discrete sampling[J]. Advances in Neural Information Processing Systems, 2023, 36: 79035-79066.\n\n## W2\nThis is a profound but challenging problem. You are correct that our current theoretical results guarantee fast mixing (via Poincaré inequality) for the *posterior sampling step* within SL, but not the convergence rate of the *overall SL process* to the final target distribution. Analyzing the full SL process is difficult because $\\frac{Y_{t}}{\\alpha(t)}=X+\\frac{\\sigma B_{t}}{\\alpha(t)}$ is not a time-homogeneous Markov process, making standard convergence analysis tools like functional inequalities hard to apply directly to the overall dynamics.\n\nOne promising direction, as you note, involves analyzing the properties of $\\frac{Y_{t}}{\\alpha(t)}$. Since these random variables have densities with explicit expressions, calculating the KL-divergence between distributions at different times $t_1$ and $t_2$ might be feasible. This could potentially reduce the problem to estimating the ratio of partition functions of BQDs under varying external fields. A more general framework, perhaps using Wasserstein distance, might also be needed to characterize the convergence of the overall SL process. We acknowledge this limitation and consider establishing the convergence rate of the full SL sampler a key direction for **future work, which we will explicitly mention in the conclusion**.\n\n*(Typos addressed)*", "claims_and_evidence": "Yes, the claims are generally well-supported by evidences.\nI like the ablation study in Section 6.2 that verifies the intuition that posterior sampling becomes easier as \\\\(t \\to +\\infty\\\\).", "methods_and_evaluation_criteria": "Yes, the methods and evaluation criteria make sense.", "theoretical_claims": "I think the theoretical claims make sense.\nI have not checked their proofs, though.", "experimental_designs_or_analyses": "Yes, I read through the experiment section; see comments in Other Strengths And Weaknesses.", "relation_to_broader_scientific_literature": "This paper extends previous stochastic localization methods by El Alaoui & Montanari (2022) and Grenioux et al. (2024) to discrete distributions.", "essential_references_not_discussed": "Not that I am aware of.", "other_strengths_and_weaknesses": "1. I think the empirical results is not strong enough.\nThe experiments suggest that using stochastic localization for discrete distributions is better than directly using a discrete MCMC method.\nHowever, the performance gaps between them are tiny (I am assuming \\\\(\\pm\\\\)xxx in the tables represents one standard deviations).\nIndeed, the baseline performances are always within one standard deviation of stochastic localization.\n\n1. Another weakness is that this paper actually does not prove how fast the samples produced by stochastic localization converge to the target distributions.\nThe results in this paper only apply to the posterior sampling---an intermediate step in stochastic localization.", "other_comments_or_suggestions": "Line 166: \"e nhances\" -> \"enhances\"", "questions_for_authors": "None at this moment.", "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": "fvNSknQdr2", "reviewer": "Reviewer_fwS3", "summary": "The paper proposes a generic localization sampler for binary quadratic distributions. By simulating the observation process similar to [EAM23], the authors propose an unbiased scheme which is capable of sampling from the target faster than a generic MCMC scheme.", "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": "We are grateful to the reviewer for the thoughtful feedback.\n\n## Q1\nThe core challenge stems from the path-dependent behavior of Brownian motion. Given the observation process $Y_t = \\alpha(t)X + \\sigma B_t$, we know that $\\frac{Y_t}{\\alpha(t)} - X = \\frac{\\sigma B_t}{\\alpha(t)}$, which converges to 0 almost surely as $t$ approaches infinity. Unfortunately, establishing uniform convergence of this process presents significant difficulties.\nTo guarantee a sufficiently large external field after iterations (which would ensure the spectral gap), we need $|\\frac{Y_t}{\\alpha(t)}| \\geq 1 - \\frac{|\\sigma B_t|}{\\alpha(t)} \\geq c$ for some positive constant $c$ after a large time $t \\geq T$. This requires establishing upper bounds on $ \\frac{|B_t|}{\\alpha(t)}$. Analyzing the Law of the Iterated Logarithm reveals that we can only obtain upper bounds on $ \\frac{|B_t|}{\\alpha(t)}$ after some $T(\\omega)$ that depends on the specific sample path $\\omega \\in \\Omega$. \n\nHowever, by applying Egorov's theorem, it is promising to show that for any $\\varepsilon > 0$, there exists a subset $A$ with measure $P(A) < \\varepsilon$ such that $ \\frac{|B_t|}{\\alpha(t)}$ converges to 0 uniformly on $A^c$. This approach could potentially establish high-probability uniform convergence.\n\n## Q2\nSure! From line 838: \n> there exists $T$ large enough such that for $t \\geq T$, we have $0\\leq \\Phi\\left(\\frac{\\zeta}{\\sigma}-\\frac{\\alpha(t)}{\\sigma\\sqrt{t}}\\right)\\leq\\varepsilon$   (Note: We find the typos in lines 833 and 837 and they have been corrected from \"$\\pm$\" symbols to \"-\". )\n\nthis allows us to derive an explicit estimate of $T$ in terms of $\\varepsilon$ based on the convergence rate of $\\frac{\\alpha(t)}{\\sigma\\sqrt{t}}$ and properties of the normal CDF.\n\n\n## Q3\nIn practice, the algorithm proceeds with a *specific* realization $Y_t = y_t$. Theorem 3.1 guarantees that for a sufficiently large $t$, the generated $y_t$ will induce a large external field with high probability. Consequently, the posterior distribution $q_t(X|Y_t=y_t)$ that we actually sample from using DMCMC will satisfy the conditions for the Poincaré inequality (Assumption 4.1) **with high probability**. This means that the DMCMC sampler used for the posterior estimation will mix polynomially fast **with high probability** for sufficiently large $t$.\n\n## Q4\nYour intuition is correct. Our theory suggests posterior sampling becomes easier over iterations $t$. This motivates allocating the MCMC budget adaptively. In Section 6.2, under \"Impact of MCMC Step Allocation,\" we empirically validate this. We demonstrate that an adaptive allocation strategy (specifically, exponential decay allocation) **achieves superior performance** compared to a uniform allocation across the vast majority of cases (see Figure 1), confirming the practical benefit of adapting the budget.\n\n## Q5\nSure. Since DMCMC is an irreducible reversible Markov chain with finite state space {$-1,1$}$^N$, satisfying the conditions of Theorem 1.1 in [1], we can derive an error estimate for the estimator of the mean of $\\nu_{\\beta,h}$ that depends on the spectral gap:\n\n$$P_{q}\\left[\\left|\\left|\\frac{1}{n}\\sum_{i=1}^nX_i-E_{\\nu_{\\beta,h}} [X]\\right|\\right|<\\varepsilon\\right]\\geq1-2e^{\\gamma_{gap}/5}N_q\\exp\\left(-\\frac{n\\varepsilon^2\\gamma_{gap}}{4Var_{\\nu_{\\beta,h}}[X]\\cdot(1+g(5\\varepsilon/Var_{\\nu_{\\beta,h}}[X]))}\\right),$$\n\nwhere $X_1\\sim q$, $N_q=\\|\\|\\frac{q}{\\nu_{\\beta,h}}\\|\\|_2$ measures the error from sampling before the Markov chain reaches stationarity, and function $g(x)=\\frac{1}{2}\\left(\\sqrt{1+x}-(1-x/2)\\right)$.\n\nThank you for your insightful comment, we will add a discussion of this bound to the Appendix in the revision.\n\n---\n\n[1] Lezaud P. Chernoff-type bound for finite Markov chains[J]. Annals of Applied Probability, 1998: 849-867.", "claims_and_evidence": "The authors provide proofs for their claims as well as some empirical verification. However, the theory for the estimator does seem to be rather preliminary (or perhaps I have not understood it well enough), and I have proposed numerous questions for the authors.", "methods_and_evaluation_criteria": "Yes, the benchmarks are thorough and the comparison between methods seems fair.", "theoretical_claims": "The authors provide some rigorous spectral gap bounds under a heuristic assumption that the tilt generated by the observation measure is sufficiently large relative to the remaining terms. The proofs under this assumption are rigorous, while the heuristic holds almost surely asymptotically under Theorem 3.1, whose proof is also rigorous.\n\nI skimmed the proofs and they appear correct to me; the final results are also sensible.", "experimental_designs_or_analyses": "The paper benchmarks their method against the unlocalized samplers on a diverse suite of tasks. The results show convincingly that in practice, the localization scheme can lead to significant speed-ups.", "relation_to_broader_scientific_literature": "The primary references are discussed; this is an extension of the stochastic localization sampling schemes from [EAM23], which also appeared in earlier/other works [CE23], etc. The paper also engages with a wide array of discrete space MCMC methods.", "essential_references_not_discussed": "As far as I am aware, the most relevant references have been covered.", "other_strengths_and_weaknesses": "My comments can be found in the other sections, but speaking broadly:\n\n***Strengths***\n\nThe empirical results are very convincing.\n\nThe spectral gap results are very nice and cover a wide range of algorithms.\n\n***Weaknessess***\n\nThe theory is not truly end-to-end and relies on a heuristic assumption. I have asked some clarifying questions in the fields below.", "other_comments_or_suggestions": "Line 166: e nhances -> enhances", "questions_for_authors": "My questions are mainly relating to the theory of this work.\n\n1. What are the missing ingredients for proving a bona fide spectral gap almost surely over all iterations, or at least for a sufficiently large tilt? \n\n2. Similar to the question above, can the guarantees of Theorem 1 be made non-asymptotic?\n\n3. Furthermore, if one only has the spectral gap holding with high probability over the randomized measure, what can one infer about the resulting estimator overall for a given iteration budget?\n\n4. Is there any hope of being ``adaptive’’ in this budget, in case the posterior measure is difficult to sample from?\n\n5. How bad is the error from using a Monte Carlo estimator of the posterior mean (what type of error does it induce for the resulting sampler)? Is there any hope for computing closed forms in any of the instances given, similar to the work of El Alaoui et al. for the SK model?", "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": "woLjlX9JAL", "reviewer": "Reviewer_eLYf", "summary": "This paper introduces a sampling method for binary quadratic distributions using stochastic localization. It is claimed to be the first theoretical that extends stochastic localization to discrete MCMC samplers. They show polynomial mixing in Glauber dynamics and MH algorithm. Some experiments are provided.", "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": "Thanks for your valuable feedback. We have consolidated the main points and respond as follows:\n> No complexity bounds of SL and cost analysis comparisons\n\nSL introduces only minimal additional computation compared to MCMC methods. Please refer to our response to ```Reviewer mA2w's last point```.\n> Why can the results about spectral gap and Poincare inequality lead to practical efficiency?\n\nThe speed of DMCMC samplers is generally unknown, but SL decomposes the entire DMCMC sampling process into a series of posterior distribution samplings $P(X|Y_i)$ (see Algorithm 1). We prove that sampling from these posterior distributions satisfies Poincaré inequality with high probability, and the existence of Poincare inequality can ensure polynomial mixing, meaning the fast sampling.\n> Satisfiability of assumption 4.1\n\nPlease refer to our response to ```Reviewer mA2w's second point```. \n> Theorem 3.1 does not show that SL is beneficial in discrete setups. \n\nTheorem 3.1 describes the convergence of the observation process, which *induces* the SL dynamics (line 130). It provides the theoretical underpinning justifying *why* Assumption 4.1 holds with high probability, thus ensuring the Poincaré inequality and fast posterior mixing are applicable. We will improve the description surrounding Theorem 3.1 in the revision to make this connection clearer.\n>  Extend SL to general setting\n\nWhile algorithmic extension to general discrete settings is natural by adapting DMCMC samplers, the *theoretical analysis* (proving Poincaré inequalities) becomes significantly more complex (e.g., bounding Dobrushin interdependence matrix for sample space with more than two states). We focused on the binary case to maintain consistency between our algorithms and theoretical guarantees. We acknowledge this limitation and will **add the extension to general discrete distributions as a future work direction** in the conclusion.\n## Experiment Issues\n> Marginal improvements on the results and statistical confidence\n\nPlease refer to our response to ```Reviewer 4aF7's W1``` regarding empirical results.\n> Absence of Discrete HMC baseline and other methods\n\nThank you for this suggestion. To our knowledge, Discrete HMC is not a standard baseline in the discrete sampling literature or the benchmarks as we referenced. If the reviewer could provide references or implementations suitable for BQDs, we are happy to consider it for future comparisons.\n> Running time and MCMC steps comparison\n\nIn our experiments, SL and DMCMC samplers used identical MCMC steps for fair comparison, which results in similar runtimes with overhead $O(TN)$ for SL. We will add concrete runtime comparison results in our revision.\n> Dependence on alpha-schedule, step allocation, sensitivity analysis on hyper-params\n\nIn our main results, we use GEOM(2,1) $\\alpha$-schedule, exponential decay step allocation, and uniform time discretization for SDE. As detailed in Appendix D.2, we tune:\n- SDE iteration parameters: initial/final noise scale, sample ratio for posterior expectation estimation, number of SDE iterations, and noise level $\\sigma$. These parameters are essential for SDE iterations and were also optimized in SLIPS.\n- Two additional parameters for step allocation: decay rate and minimum MCMC steps\n\nGiven fixed DMCMC samplers, we believe this represents a minimal set of hyperparameters. Regarding sensitivity to some key hyperparameters:\n- Figure 1 provides comparisons for different step allocation strategies\n- Tables 4-9 present ablation studies for \\alpha-schedule, K, and \\sigma variations\n\nThese results indicate that while performance varies (expected), **SL consistently outperforms baselines across different settings, demonstrating robustness**.\n\n> Impact of temperature settings in MCMC and datasets \n\nWe used the *identical* temperature annealing schedule from the DISCS benchmark for *all* methods (Appendix D.1) for fair comparison.\nRegarding dataset characteristics impact, we studied:\n- Graph sparsity effects in Table 1 using ER datasets of different densities, analyzed in line 356 under \"Results on MIS\"\n- Problem size scaling in Table 3, showing results for different-sized datasets, analyzed in line 380 under \"Results on MaxCut\"\n\nIn all these diverse settings—varying graph densities and problem sizes—**SL consistently outperformed DMCMC across these variations.**\n> Explanation on the ablation on step allocation\n\nOur theory indicates posterior sampling becomes fast as iterations progress, motivating adaptively allocating more MCMC steps to earlier iterations might be better than uniform allocation. Figure 1 tests this: exponential decay allocation (blue bars, more steps early) generally outperforms uniform allocation (orange bars) for the same total MCMC budget, empirically validating the theoretical motivation. We will clarify this explanation in the caption/text.", "claims_and_evidence": "for the most part, as some claims lack empirical justification! For instance:\n1. This paper does not provide explicit complexity bounds and only shows polynomial-time mixing but claims that stochastic localization significantly speeds up sampling \n2. Stochastic localization does not show a huge improvement in real-world problems given the experiments provided in the paper (0.1-0.5%).\n3. This method is not a general purpose framework and can only be applied to binary quadratic distributions and how well it generalizes to other discrete sampling problems is not clear to me. \n4. Spectral gap bounds do not show that stochastic localization is computationally faster than other methods.", "methods_and_evaluation_criteria": "1. this paper should provide computational cost analysis and compare it to other MCMC models. \n2. No comparison to methods such as discrete HMC \n3. Despite the fact that this paper proves polynomial time mixing, there is no clear evidence that it performs better in real world problems and there is no comparison to other MCMC in runtime. Does stochastic localization reduce the number of MCMC steps?", "theoretical_claims": "1. the proofs look correct but some assumptions (4.1) can be violated easily in many settings. Seems like if the external field is not large enough, the mixing may fail. \n2. Theorem 3.1 is mostly based on the literature but it still does not show that stochastic localization is beneficial in discrete setups. \n3. The claim that Poincare inequality provides practical efficiency is not quite correct. it does guarantee ergodicity but does not necessarily imply better performance compared to other techniques.", "experimental_designs_or_analyses": "It has a variety of benchmarks and multiple MCMC methods are evaluated.good ablation study,  but a few things can be improved: \n1. There is no computational cost analysis\n2. no comparison to methods such as discrete HMC, Variational inference, etc. \n3. This method is heavily dependent on hyperparameters such as \\(\\alpha \\)-schedule and step allocation. the ablation study does not study different temperature settings in MCMC  or the impact of datasets such  as graph sparsity, problem size, etc\n4. Since it is claimed that this method outperforms baseline MCMC, the improvement is very small. having some statistical testing to examine the statistical significance can be helpful.", "relation_to_broader_scientific_literature": "This paper extends stochastic localization to BDDs which is built on top of the line of works on stochastic localization for continuous distribution.", "essential_references_not_discussed": "Yes, references are sufficient.", "other_strengths_and_weaknesses": "Strengths:\n1. It is easy to follow and the use of stochastic localization in a discrete setting is interesting. \n2. Applying it to many datasets is interesting and can confirm the theoretical claims.\n\nWeaknesses:\n1. While the polynomial mixing has strong theoretical results, the empirical improvements are not drastic. \n2. the theoretical assumptions may not hold. For instance, assumption 4.1 requires |h| to grow large which can be violated easily in many real world problems. \n3. Comparison is only done  against MCMC based models \n4. despite ablation studies, the hyperparameters must be studied more. For instance, do differnet settings change the performance drastically? or is the method robust?", "other_comments_or_suggestions": "mentioned in the previous sections.", "questions_for_authors": "1. Could the authors justify how polynomial time mixing implies practical efficiency?\n2. How does stochastic localization improve sampling intuitively? What happens if assumption 4.1 fails?\n3. Could authors please discuss runtime comparisons?\n4, How do results change with different MCCM step allocations? the ablation study seems a bit unclear to me.", "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": "lmkhQp02Mj", "reviewer": "Reviewer_mA2w", "summary": "This work addresses the problem of sampling from binary quadratic distributions. The authors apply a stochastic localization framework and focus on a key component—the counting/expectation of the posterior distribution. To this end, they establish Poincaré inequalities for the posterior, from which they derive a spectral gap. Experiments further demonstrate that stochastic localization consistently improves sampling efficiency.", "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": "We sincerely thank the reviewer for these insightful comments.\n> Overstating the novelty by emphasizing the use of SL in binary quadratic distributions\n\nWe appreciate the feedback on framing. While SL *concepts* have appeared in discrete settings (as discussed in Appendix A), prior works often focus on specific models (e.g., SK, Ising with specific structures) and employ model-specific techniques or assumptions. Our contribution lies in:\n- Developing an SL framework using **standard, general-purpose DMCMC samplers** for the posterior estimation step.\n- Providing **theoretical guarantees for general BQDs** without requiring additional model-specific structure beyond the quadratic form. This makes our analysis broadly applicable.\n\nWe agree our main theoretical novelty is the rigorous quantification of Poincaré inequalities for the posterior distributions within this general BQD setting. We will **revise the introduction** to state this more clearly and accurately reflect the relationship to prior discrete SL work, emphasizing the generality of our approach and theory.\n\n> Satisfiability of assumption 4.1\n\nAs detailed in Remark 4.2, the external field $h$ in the posterior (Eq. 12) is $b+\\frac{\\alpha(t)Y_t}{\\sigma^2t}$. Theorem 3.1 and the SL construction ensure that $|h|$ grows large as $t$ increases **with high probability** (explained around line 161). Therefore, Assumption 4.1 is **not a restrictive assumption on the problem instance, but rather a condition that holds naturally as a consequence of the SL dynamics** for sufficiently large $t$. We recognize that labeling it an \"Assumption\" caused confusion about its generality. We apologize and will **rename/rephrase this condition** (e.g., \"Condition 4.1\" or similar) and clarify its status in the revised version.\n> It would better to question in Line 66 as \"Can SL reduce sampling difficulty in the binary quadratic distributions, as it does in continuous settings, by constructing easily samplable posterior distributions?\" since there is various SL methods for discrete sampling tasks as discussed in Appendix A.\n\nThis is an excellent suggestion for better framing. We agree and will **revise the question in Line 66** accordingly in the next version.\n> Could you provide the convergence rate/query complexity/iteration complexity explicitly? and compare it with existing results?\n\nAnalyzing the convergence rate of the *overall* SL process to the target distribution remains an open and challenging theoretical problem. This difficulty arises from the time-inhomogeneous nature of the process, as discussed in our response to `Reviewer 4aF7's W2`.\n\nWe can analyze the operational complexity. Let $N$ be the dimension, $T$ be the number of SL iterations, and $M$ be the total MCMC step budget.\n- **Baseline DMCMC:** Methods like GWG, PAS, DMALA have complexity dominated by operations like gradient/difference calculations or matrix-vector products, typically scaling as $O(MN^2)$. \n- **SL + DMCMC:** SL adds two main steps per iteration: MC estimation (line 118, typically $O(N)$ using posterior samples) and SDE simulation (line 119, $O(N)$). Over $T$ iterations, the total overhead is $O(TN)$. The MCMC sampling itself uses the same total budget $M$, distributed across iterations.\n- **Comparison:** The total complexity for SL+DMCMC is roughly $O(MN^2 + TN)$. In typical high-dimensional settings relevant to MCMC ($N$ large), and practical choices of $T$ (e.g., $T \\in ${256, 512, 1024} in our experiments with $M$ up to 10,000), the $O(TN)$ overhead is **negligible** compared to the $O(MN^2)$ cost of the core MCMC sampling.\n\nThank you for prompting this; we will **add this explicit computational complexity analysis and comparison** to the revised manuscript (likely in the Appendix).", "claims_and_evidence": "The introduction seems to overstate the novelty of the work by emphasizing the use of stochastic localization in binary quadratic distributions, which has already been widely applied in discrete sampling. The primary theoretical contribution of the paper is the quantification of Poincaré inequalities for the posterior distributions.", "methods_and_evaluation_criteria": "Yes, the proposed methods and evaluation criteria are well-chosen. The framework leverages rigorous theoretical analysis (e.g., Poincaré inequalities and spectral gap bounds) tailored for discrete MCMC samplers, while the benchmark datasets (from common combinatorial optimization problems) effectively capture the challenges of sampling from binary quadratic distributions.", "theoretical_claims": "I don'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": "No, the paper appears to cite all the essential prior works. It covers key contributions in discrete MCMC sampling and stochastic localization, which are sufficient for understanding its context and contributions.", "other_strengths_and_weaknesses": "The theoretical guarantees rely on a strong external field assumption that may not hold in all practical scenarios, potentially limiting the generality of the results.", "other_comments_or_suggestions": "It would better to question in Line 66 as \"Can SL reduce sampling difficulty in the binary quadratic distributions, as it does in continuous settings, by constructing easily samplable posterior distributions?\" since there is various SL methods for discrete sampling tasks as discussed in Appendix A.", "questions_for_authors": "- Could you provide the convergence rate/query complexity/iteration complexity explicitly? and compare it with existing results?", "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: The authors study applying stochastic localization methods to binary quadratic distributions.  Their main result is a proof of Poincare inequalities for the sampling procedures used to estimate the expectations used in the SL procedure.  They show that this sampling step becomes easier as the SL process continues and propose a schedule to take advantage of this property, although as noted by Reviewer 4aF7, their results do not extend to providing information about the convergence of the overall process.  Experimental comparisons show pretty minor but consistent improvement over each sampling technique without SL.  Reviewers were generally positive, with some concerns about the impact of the theoretical contribution (narrow setting; results are not directly about the quality of the overall sampling procedure, experimental impact, and some presentation (connections to SL used in other discrete settings, etc.).
Decision: Accept (poster)