Sampling from Binary Quadratic Distributions via Stochastic Localization

We sincerely thank the reviewer for these insightful comments.

Overstating the novelty by emphasizing the use of SL in binary quadratic distributions

We 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:

• Developing an SL framework using standard, general-purpose DMCMC samplers for the posterior estimation step.
• Providing theoretical guarantees for general BQDs without requiring additional model-specific structure beyond the quadratic form. This makes our analysis broadly applicable.

We 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.

Satisfiability of assumption 4.1

As 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.

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.

This is an excellent suggestion for better framing. We agree and will revise the question in Line 66 accordingly in the next version.

Could you provide the convergence rate/query complexity/iteration complexity explicitly? and compare it with existing results?

Analyzing 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.

We 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.

• 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)$.
• 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.
• 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.

Thank you for prompting this; we will add this explicit computational complexity analysis and comparison to the revised manuscript (likely in the Appendix).

Thanks for your valuable feedback. We have consolidated the main points and respond as follows:

No complexity bounds of SL and cost analysis comparisons

SL introduces only minimal additional computation compared to MCMC methods. Please refer to our response to Reviewer mA2w's last point.

Why can the results about spectral gap and Poincare inequality lead to practical efficiency?

The 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.

Satisfiability of assumption 4.1

Please refer to our response to Reviewer mA2w's second point.

Theorem 3.1 does not show that SL is beneficial in discrete setups.

Theorem 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.

Extend SL to general setting

While 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.

Experiment Issues

Marginal improvements on the results and statistical confidence

Please refer to our response to Reviewer 4aF7's W1 regarding empirical results.

Absence of Discrete HMC baseline and other methods

Thank 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.

Running time and MCMC steps comparison

In 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.

Dependence on alpha-schedule, step allocation, sensitivity analysis on hyper-params

In 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:

• 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.
• Two additional parameters for step allocation: decay rate and minimum MCMC steps

Given fixed DMCMC samplers, we believe this represents a minimal set of hyperparameters. Regarding sensitivity to some key hyperparameters:

• Figure 1 provides comparisons for different step allocation strategies
• Tables 4-9 present ablation studies for \alpha-schedule, K, and \sigma variations

These results indicate that while performance varies (expected), SL consistently outperforms baselines across different settings, demonstrating robustness.

Impact of temperature settings in MCMC and datasets

We used the identical temperature annealing schedule from the DISCS benchmark for all methods (Appendix D.1) for fair comparison. Regarding dataset characteristics impact, we studied:

• Graph sparsity effects in Table 1 using ER datasets of different densities, analyzed in line 356 under "Results on MIS"
• Problem size scaling in Table 3, showing results for different-sized datasets, analyzed in line 380 under "Results on MaxCut"

In all these diverse settings—varying graph densities and problem sizes—SL consistently outperformed DMCMC across these variations.

Explanation on the ablation on step allocation

Our 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.

We are grateful to the reviewer for the thoughtful feedback.

Q1

The 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. To 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$.

However, 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.

Q2

Sure! From line 838:

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 "-". )

this 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.

Q3

In 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$.

Q4

Your 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.

Q5

Sure. 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:

$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),$

where $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)$.

Thank you for your insightful comment, we will add a discussion of this bound to the Appendix in the revision.

---

[1] Lezaud P. Chernoff-type bound for finite Markov chains[J]. Annals of Applied Probability, 1998: 849-867.

We sincerely thank the reviewer for these insightful comments.

W1

From an experimental perspective, the absolute improvements are indeed modest. However, we would like to emphasize two key points:

1. 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.
2. 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.

Thanks 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.

[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.

W2

This 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.

One 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.

(Typos addressed)