Pith. sign in

REVIEW 4 major objections 5 minor 64 references

Sampling from Binary Quadratic Distributions via Stochastic Localization

T0 review · 4 major / 5 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read After enough stochastic-localization steps the posterior's external field grows without bound, so Glauber, Metropolis, and Langevin samplers on binary quadratic distributions satisfy Poincaré inequalities and mix in polynomial time, the…

desk verdict Conditional Poincaré bounds for SL posteriors on BQDs are real, but the headline polynomial-time claim rests on a coordinatewise strong-field condition the paper never establishes. read the letter →

arxiv 2505.19438 v1 pith:NKTF5DFE submitted 2025-05-26 math.ST stat.TH

Chenguang Wang , Kaiyuan Cui , Weichen Zhao , Tianshu Yu This is my paper · ORCID
classification math.STstat.TH MSC 60J2260J2782B2065C05
keywords stochasticlocalizationbinaryquadraticdistributionsGlauberdynamicsMetropolis-HastingsPoincaréinequalityspectralgapQUBOMCMC
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Stochastic localization (SL) solves hard sampling problems by observing a copy of the target through noise and then sampling the sequence of posterior distributions; in continuous spaces this approach is established, and this paper aims to carry it over to binary quadratic distributions (BQDs), the Gibbs measures behind Ising models and QUBO optimization. The central assertion is that after enough SL iterations the posterior's external field becomes effectively infinite, and in that large-field regime the posterior is easy for standard discrete MCMC samplers. To back this up, the paper proves Poincaré inequalities, with explicit spectral gap formulas, for Glauber dynamics, classical Metropolis chains, gradient-informed single-site Metropolis-Hastings, and the discrete unadjusted Langevin algorithm. The paper concludes that SL turns an off-the-shelf discrete sampler into a polynomially mixing sampler even when the original BQD has no fast mixing. Experiments on maximum independent set, maximum cut, and maximum clique instances show the SL versions consistently match or outperform their base samplers at equal MCMC step budgets.

What carries the argument

The machinery is the SL posterior together with the Dobrushin interdependence matrix. The posterior $\nu_{\beta,h}$ is the original Gibbs measure with an added external field $h_t$; because $x^2=1$ on the hypercube, the Gaussian observation contributes only this linear field. The proofs bound each entry $c_{ij}$ of the transition kernel's Dobrushin interdependence matrix by a small multiple of $\beta|W_{ij}|$ divided by a growing denominator such as $e^{3|h|/4}+e^{-3|h|/4}$, and then use Wu's theorem (Lemma B.2) to convert the spectral radius bound $\mathrm{r}_{\mathrm{sp}}(C)<1$ into a Poincaré inequality with the quoted gap. This is the step that turns a large external field into a quantitative mixing guarantee, since a spectral gap implies polynomial mixing time by the standard Levin-Peres result.

What would settle it

Run the SL observation process on an explicit $N \ge 2$ BQD, record the trajectory of $h_t$, and check at the time $T$ promised by Theorem 3.1 whether $\min_i |h_{t,i}| \ge 2\beta \sup_i \sum_{k\ne i}|W_{ik}|$ on typical runs. If the scalar magnitude $|h_t|$ is large while some coordinate stays below threshold, the stated assumptions do not apply; a numerical spectral-gap estimate of Glauber dynamics at that field configuration would then show whether the Poincaré conclusion survives anyway.

Watch

Extended reading notes

Core claim

The paper's central claim is that stochastic localization removes the discrete-sampling bottleneck for general binary quadratic distributions. Writing the SL posterior as $\nu_{\beta,h}(x) \propto \exp(-\tfrac{\beta}{2}\langle x, W x\rangle + \langle x, h\rangle)$ with $h = b + \alpha(t)Y_t/(\sigma^2 t)$, the quadratic term from the Gaussian likelihood collapses to a constant because $x^2=1$ on $\{-1,1\}^N$, so SL acts entirely through a growing linear tilt. Theorems 4.3 through 4.9 show that when this tilt satisfies the strong-field condition $|h| \ge 2\beta \sup_i \sum_{k\ne i}|W_{ik}|$, each of the four discrete MCMC families obeys a Poincaré inequality whose spectral gap increases with $|h|$ and tends to $1$; Theorem 3.1 is used to establish that $|Y_t|$ grows without bound with probability close to $1$, so the condition holds at late SL times. The conclusion is polynomial-time mixing for the inner sampler and exponential concentration for the Monte Carlo estimate of the posterior mean.

Load-bearing premise

The load-bearing premise is that every individual binary variable ends up with a large tilt, not merely that the overall tilt magnitude is large; the paper's guarantee that this happens is proved in Appendix C.1 through a one-dimensional observation calculation, while the Poincaré theorems need the field to be large coordinatewise.

Editorial extensions

If this is right

  • If the central claim holds, the inner MCMC chain at late SL iterations mixes polynomially, so an off-the-shelf Glauber, Metropolis, GWG, PAS, or DULA sampler can be wrapped by SL without model-specific posterior estimators.
  • The explicit spectral gap formulas give finite-$N$ control on the Poincaré constant: the gap approaches $1$ as the field grows, so the number of inner samples needed for a fixed error tolerance is polynomial in $N$ and in the inverse tolerance.
  • The guarantee is stated for arbitrary $W$ and $b$, so SL should help BQDs that do not mix fast on their own; the only requirement is that the SL schedule drive the field past the threshold.
  • The Chernoff-type bounds in Corollary 4.4 and Appendix C.8 mean the posterior-mean estimate used to advance the SDE concentrates exponentially with the number of MCMC samples, which is what makes the full SL loop practically stable.
  • The empirical QUBO results on maximum independent set, max-cut, and max-clique show the SL variants at least match the base samplers at equal MCMC budgets, with total added cost only $O(TN)$ on top of the $O(MN^2)$ MCMC cost.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The paper proves mixing of the inner posterior sampler, not an end-to-end total-variation guarantee for the full SL algorithm; combining these Poincaré inequalities with discretization and posterior-estimation error would complete the overall convergence story, a direction the paper itself leaves open.
  • A testable implication of the coordinatewise-field concern is that SL's gain should be smallest on instances where some spin's local field stays near zero through most of the schedule; varying the row norms of $W$ in QUBO benchmarks could probe this prediction.
  • The same large-field mechanism suggests a natural extension to $k$-state and higher-order interaction models: wherever the likelihood tilt dominates the interaction term, the posterior becomes nearly independent, so the core argument may survive without the specific $x^2=1$ collapse.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

4 major / 5 minor

Summary. The paper proposes a stochastic localization (SL) framework for sampling from binary quadratic distributions (BQDs) of the form ν(x) ∝ exp(−β/2 ⟨x,Wx⟩ + ⟨x,b⟩). The main theoretical claim is that, after sufficiently many SL iterations, the external field h_t of the SL posterior grows large, so the posterior satisfies a Poincaré inequality with high probability, which implies polynomial-time mixing for inner discrete MCMC samplers. The authors prove spectral-gap bounds for Glauber dynamics (Theorem 4.3), classical Metropolis chains (Theorem 4.5), a generic single-site Metropolis–Hastings kernel (Theorem 4.6), gradient-informed single-site MH (Theorem 4.8), and DULA (Theorem 4.9), all under a strong-field condition (Condition 4.1). They also report experiments on MIS, MaxCut, and MaxClique benchmarks showing modest consistent improvements of SL-augmented samplers over their non-SL counterparts.

Significance. If the main claim were established, the paper would be a valuable contribution: it would give the first general theoretical analysis of SL for discrete BQD sampling with explicit, field-dependent spectral gap bounds, and it would identify a practically relevant regime in which inner MCMC steps mix fast. The paper also ships an organized application of Wu's Dobrushin-based Poincaré framework to several discrete MCMC algorithms and provides a broad experimental comparison with code. However, the central theoretical chain contains a load-bearing gap: Condition 4.1 is stated with a scalar norm, whereas the proofs require coordinatewise large fields, and Theorem 3.1 is proved only for a scalar observation. Thus, as written, the high-probability large-field premise for the N-dimensional posterior is not established. This makes the main claim currently unsupported, though the gap appears fixable.

major comments (4)
  1. [Condition 4.1 and proofs of Theorems 4.3, 4.5, 4.8, 4.9 (Appendix C)] Condition 4.1 is stated as |h| ≥ 2β sup_i Σ_{k≠i}|W_ik| with an unspecified norm, but the proofs require a coordinatewise condition. In the proof of Theorem 4.3 (Appendix C.2), the key estimate on g_1'(x) is applied at x = −β/2 Σ_{k≠i,j} W_ik x_k − β/2 W_ij x_j + h_i; the inequality |x| ≥ 3h0/2 is obtained only if |h_i| = 2h0 for the specific coordinate i. A large Euclidean (or any single) norm of the vector h does not imply |h_i| is large for every i. The same coordinatewise dependence appears in C.4, C.6, and C.7. Therefore the Poincaré inequalities do not follow from Condition 4.1 as written. The authors should either state Condition 4.1 coordinatewise as min_i |h_i| ≥ 2β sup_i Σ_{k≠i}|W_ik|, or prove that the scalar-norm condition implies the coordinatewise lower bounds used in the proofs; the latter is generally false.
  2. [Theorem 3.1 and Appendix C.1] Theorem 3.1 is proved only for a scalar observation. The proof writes P(|Y_t| ≥ ζ) = P(|B_t ± α(t)/σ| ≥ ζ/σ) and estimates with a one-dimensional Gaussian CDF. For X ∈ {−1,1}^N and Y_t ∈ R^N, these identities do not apply; |Y_t| is the Euclidean norm of a vector with random signs, and the argument does not show that all N coordinates of Y_t are simultaneously large. The statement actually needed for the posterior field h_t in equation (12) is a coordinatewise bound, e.g., P(min_i |Y_{t,i}| ≥ ζ) ≥ 1−ε, or at least a bound on all coordinates entering h_t. Without this, Remark 4.2's claim that Theorem 3.1 guarantees Condition 4.1 with high probability is not justified.
  3. [Section 7 (Conclusion and Discussion)] The paper explicitly states that "establishing rigorous theoretical guarantees for the convergence rate of the overall SL process to the final target distribution" remains future work. Consequently, the headline claim of "polynomial-time mixing" applies only to the posterior distributions used inside the SL iterations, not to the full SL algorithm that produces the final sample. This is an important scope limitation that should be stated in the abstract and introduction; as it stands, a reader could reasonably infer a stronger guarantee for the whole sampler than the paper actually proves.
  4. [Theorem 4.6 and Remark 4.7] Theorem 4.6 is conditional on an assumption that the transition kernel P(x^i|x) is Lipschitz with a constant C_Lip(β,h) that decreases exponentially as |h| grows, but no verifiable condition or proof is given for the proposals used in the experiments (GWG and PAS). Remark 4.7 only says this property "can be expected" from the warm-up cases. For the paper's claim of covering "enormous discrete MCMC samplers," the relevant Lipschitz condition should be verified for the actual single-site gradient-informed proposals, or the scope should be restricted to the kernels covered by Theorems 4.8 and 4.9.
minor comments (5)
  1. [Abstract] The phrase "covering enormous discrete MCMC samplers" is odd; something like "covering a broad range of discrete MCMC samplers" would be clearer.
  2. [Section 3, text after Theorem 3.1] The sentence "It proves that as t→T_gen, Y_t/α(t)→X ∈ {−1,1}^N" is stronger than what Theorem 3.1 states; the theorem only gives a high-probability norm lower bound for large t.
  3. [Condition 4.1 and Section 4 spectral-gap formulas] The notation |h| is used for a vector h without specifying the norm; the spectral-gap formulas in Section 4 (e.g., |h|/(e^{3|h|/4}+e^{-3|h|/4})) depend on which norm is intended, and this is not clarified in the main text.
  4. [Appendix D.1] There is a typo: "benchamrk" should be "benchmark".
  5. [References] The reference spelling is inconsistent: "Dobruschin" in the bibliography entries for Dobruschin (1968) and Dobrushin (1970) should be unified to "Dobrushin".

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the Poincare guarantees are conditional on a separately established large-field bound; external citations (Wu 2006, SLIPS) are not load-bearing self-citations.

full rationale

The derivation chain is self-contained and non-circular. The central claim has two independent links: (i) Theorem 3.1 shows that the observation process Y_t = alpha(t)X + sigma B_t has |Y_t| >= zeta with probability at least 1-epsilon once alpha(t)/(sigma sqrt(t)) -> infinity, and the paper then notes that the posterior field h_t = b + alpha(t)Y_t/(sigma^2 t) grows in magnitude; this is a genuine probabilistic estimate, not an assumption of the conclusion. (ii) The Poincare inequalities in Theorems 4.3-4.9 are stated conditionally on the large-field Condition 4.1, and the proofs bound Dobrushin interdependence matrix entries using Wu (2006), an external theorem, to convert the spectral-radius bound into a spectral-gap bound. The large-field condition is not fitted to the target data and is not a renamed version of the Poincare conclusion. No load-bearing self-citation appears: references to SLIPS and El Alaoui et al. are external works by different authors, and no uniqueness theorem by the present authors is invoked to force a choice. The paper honestly flags that a full convergence-rate guarantee for the overall SL process remains open (Section 7), and the experimental hyperparameters are tuned on the same benchmarks (Appendix D.2), which weakens the empirical demonstration but does not enter the theoretical derivation. The main rigor concern noted by the reviewer is that Condition 4.1 uses an unspecified norm |h| while the pointwise proofs require coordinatewise large fields, and Theorem 3.1 is proved in scalar form; this is a correctness gap or an omitted proof detail, not circularity, because the scalar argument extends coordinatewise with a union bound and the field growth is derived, not assumed.

Assumptions & free parameters 6 free parameters · 4 assumptions · 0 invented entities

The theoretical chain rests on Wu's Poincaré inequality and the strong-field condition; no new entities are postulated. The experimental claims depend on a set of tuned SL hyperparameters.

free parameters (6)
  • noise_level_sigma
    SL noise parameter σ; optimized over {1,2,4,6,8,10,15,20} in experiments, affecting posterior field dynamics and empirical results.
  • num_sl_iterations_K
    Number of SL discretization steps; optimized over {256,512,1024}; the theoretical bound on T is not instantiated.
  • mcmc_step_decay_rate_r
    Exponential decay rate for allocating the 10,000 MCMC steps across SL iterations; optimized in [1e-4,1e-1].
  • min_mcmc_steps_Nmin
    Minimum MCMC steps per SL iteration; optimized over {2,4,6,8,16,32}.
  • initial_and_final_noise_scales
    ε and ε_end tuned in [1e-4,1e-1] for the SDE discretization; not fixed by theory.
  • mcmc_sample_ratio
    Proportion of last MCMC samples used for posterior estimation; optimized in [0.1,1].
assumptions (4)
  • standard math Dobrushin uniqueness condition: spectral radius r_sp(C) < 1 implies a Poincaré inequality (Lemma B.2, Wu 2006).
    Used in all Poincaré proofs (Section B.4).
  • domain assumption The SL observation process Y_t = α(t)X + σB_t with α(t) satisfying the regularity conditions of SLIPS, and the posterior formula q_t ∝ exp(-β/2⟨x,Wx⟩ + ⟨x, b + α(t)Y_t/(σ^2 t)⟩).
    Defines the BQD sampling setup; relies on Bayes and the quadratic term vanishing for binary x.
  • ad hoc to paper Condition 4.1: the external field h satisfies |h| ≥ 2β sup_i Σ_{k≠i}|W_{ik}| in the norm required by the proofs.
    The paper's central sufficient condition; its coordinatewise verification is incomplete because Theorem 3.1 is shown for scalar observations and the norm is unspecified.
  • ad hoc to paper Lipschitz continuity assumption on the MH transition kernel in Theorem 4.6.
    Assumed to extend Poincaré bounds to GWG and PAS; Remark 4.7 only says it can be expected.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Sampling from Binary Quadratic Distributions via Stochastic Localization." pith.science (2026). https://pith.science/paper/NKTF5DFE

@misc{pith2026250519438,
  author       = {Pith},
  title        = {Pith review of: Sampling from Binary Quadratic Distributions via Stochastic Localization},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/NKTF5DFE}},
  note         = {Machine review of arXiv:2505.19438}
}
read the original 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\'e 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.

Figures

Figures reproduced from arXiv: 2505.19438 by the authors.

Figure 1
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 [PITH_FULL_IMAGE:figures/full_fig_p008_1.png] view at source ↗
Figure 2
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 [PITH_FULL_IMAGE:figures/full_fig_p032_2.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

64 extracted references · 51 canonical work pages

  1. [1]

    E., Montanari, A., and Sellke, M

    Alaoui, A. E., Montanari, A., and Sellke, M. Sampling from mean-field gibbs measures via diffusion processes. arXiv preprint arXiv:2310.08912, 2023 a

    arXiv 2023

  2. [2]

    Alaoui, A. E. K., Eldan, R., Gheissari, R., and Piana, A. Fast relaxation of the random field ising dynamics. ArXiv, abs/2311.06171, 2023 b . URL https://api.semanticscholar.org/CorpusID:265128744

    work page Pith review arXiv 2023

  3. [3]

    Trickle-down in localization schemes and applications

    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 Computing, pp.\ 1094--1105, 2024

    work page 2024

  4. [4]

    and Bodineau, T

    Bauerschmidt, R. and Bodineau, T. A very simple proof of the lsi for high temperature spin systems. Journal of Functional Analysis, 276 0 (8): 0 2582--2588, 2019

    work page 2019

  5. [5]

    and Dagallier, B

    Bauerschmidt, R. and Dagallier, B. Log-sobolev inequality for near critical ising models. Communications on Pure and Applied Mathematics, 77 0 (4): 0 2568--2576, 2024

    work page 2024

  6. [6]

    Lectures on glauber dynamics for discrete spin models

    Bertoin, J., Martinelli, F., Peres, Y., and Martinelli, F. Lectures on glauber dynamics for discrete spin models. Lectures on Probability Theory and Statistics: Ecole d’Et \'e de Probailit \'e s de Saint-Flour XXVII-1997 , pp.\ 93--191, 1999

    work page 1997

  7. [7]

    M., and Barber, D

    Chen, W., Zhang, M., Paige, B., Hern \'a ndez-Lobato, J. M., and Barber, D. Diffusive gibbs sampling. arXiv preprint arXiv:2402.03008, 2024

    arXiv 2024

  8. [8]

    An almost constant lower bound of the isoperimetric coefficient in the kls conjecture

    Chen, Y. An almost constant lower bound of the isoperimetric coefficient in the kls conjecture. Geometric and Functional Analysis, 31: 0 34--61, 2021

    work page 2021

Show all 64 references
  1. [9]

    and Eldan, R

    Chen, Y. and Eldan, R. Localization schemes: A framework for proving mixing bounds for markov chains. In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), pp.\ 110--122. IEEE, 2022

    2022

  2. [10]

    Learning discrete energy-based models via auxiliary-variable local exploration

    Dai, H., Singh, R., Dai, B., Sutton, C., and Schuurmans, D. Learning discrete energy-based models via auxiliary-variable local exploration. Advances in Neural Information Processing Systems, 33: 0 10443--10455, 2020

    2020

  3. [11]

    The description of a random field by means of conditional probabilities and conditions of its regularity

    Dobruschin, P. The description of a random field by means of conditional probabilities and conditions of its regularity. Theory of Probability & Its Applications, 13 0 (2): 0 197--224, 1968

    1968

  4. [12]

    Dobrushin, R. L. Prescribing a system of random variables by conditional distributions. Theory of Probability & Its Applications, 15 0 (3): 0 458--486, 1970

    1970

  5. [13]

    Dubhashi, D. P. and Panconesi, A. Concentration of measure for the analysis of randomized algorithms. Cambridge University Press, 2009

    2009

  6. [14]

    J., and Yu, B

    Dwivedi, R., Chen, Y., Wainwright, M. J., and Yu, B. Log-concave sampling: Metropolis-hastings algorithms are fast. Journal of Machine Learning Research, 20 0 (183): 0 1--42, 2019

    2019

  7. [15]

    and Montanari, A

    El Alaoui, A. and Montanari, A. An information-theoretic view of stochastic localization. IEEE Transactions on Information Theory, 68 0 (11): 0 7423--7426, 2022

    2022

  8. [16]

    Sampling from the sherrington-kirkpatrick gibbs measure via algorithmic stochastic localization

    El Alaoui, A., Montanari, A., and Sellke, M. Sampling from the sherrington-kirkpatrick gibbs measure via algorithmic stochastic localization. In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), pp.\ 323--334. IEEE, 2022

    2022

  9. [17]

    Thin shell implies spectral gap up to polylog via a stochastic localization scheme

    Eldan, R. Thin shell implies spectral gap up to polylog via a stochastic localization scheme. Geometric and Functional Analysis, 23 0 (2): 0 532--569, 2013

    2013

  10. [18]

    Taming correlations through entropy-efficient measure decompositions with applications to mean-field approximation

    Eldan, R. Taming correlations through entropy-efficient measure decompositions with applications to mean-field approximation. Probability Theory and Related Fields, 176 0 (3): 0 737--755, 2020

    2020

  11. [19]

    and Shamir, O

    Eldan, R. and Shamir, O. Log concavity and concentration of lipschitz functions on the boolean hypercube. Journal of functional analysis, 282 0 (8): 0 109392, 2022

    2022

  12. [20]

    A spectral condition for spectral gap: fast mixing in high-temperature ising models

    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 0 (3): 0 1035--1051, 2022

    2022

  13. [21]

    A chernoff bound for random walks on expander graphs

    Gillman, D. A chernoff bound for random walks on expander graphs. SIAM Journal on Computing, 27 0 (4): 0 1203--1220, 1998

    1998

  14. [22]

    Quantum bridge analytics i: a tutorial on formulating and using qubo models

    Glover, F., Kochenberger, G., Hennig, R., and Du, Y. Quantum bridge analytics i: a tutorial on formulating and using qubo models. Annals of Operations Research, 314 0 (1): 0 141--183, 2022 a

    2022

  15. [23]

    Quantum bridge analytics ii: Qubo-plus, network optimization and combinatorial chaining for asset exchange

    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, 314 0 (1): 0 185--212, 2022 b

    2022

  16. [24]

    Discs: a benchmark for discrete sampling

    Goshvadi, K., Sun, H., Liu, X., Nova, A., Zhang, R., Grathwohl, W., Schuurmans, D., and Dai, H. Discs: a benchmark for discrete sampling. Advances in Neural Information Processing Systems, 36, 2024

    2024

  17. [25]

    Oops i took a gradient: Scalable sampling for discrete distributions

    Grathwohl, W., Swersky, K., Hashemi, M., Duvenaud, D., and Maddison, C. Oops i took a gradient: Scalable sampling for discrete distributions. In International Conference on Machine Learning, pp.\ 3831--3841. PMLR, 2021

    2021

  18. [26]

    Grenioux, L., Noble, M., Gabri \' e , M., and Durmus, A. O. Stochastic localization via iterative posterior sampling. In Forty-first International Conference on Machine Learning, ICML 2024, Vienna, Austria, July 21-27, 2024 , 2024

    2024

  19. [27]

    Denoising diffusion probabilistic models

    Ho, J., Jain, A., and Abbeel, P. Denoising diffusion probabilistic models. Advances in neural information processing systems, 33: 0 6840--6851, 2020

    2020

  20. [28]

    Huang, B., Montanari, A., and Pham, H. T. Sampling from spherical spin glasses in total variation via algorithmic stochastic localization. arXiv preprint arXiv:2404.15651, 2024

    2024 arXiv

  21. [29]

    Reverse diffusion monte carlo

    Huang, X., Dong, H., Yifan, H., Ma, Y., and Zhang, T. Reverse diffusion monte carlo. In The Twelfth International Conference on Learning Representations, 2023

    2023

  22. [30]

    Calculation of partition functions

    Hubbard, J. Calculation of partition functions. Physical Review Letters, 3 0 (2): 0 77, 1959

    1959

  23. [31]

    The one-dimensional long-range ferromagnetic ising model with a periodic external field

    Kerimov, A. The one-dimensional long-range ferromagnetic ising model with a periodic external field. Physica A: Statistical Mechanics and its Applications, 391 0 (10): 0 2931--2935, 2012

    2012

  24. [32]

    D., and Vecchi, M

    Kirkpatrick, S., Gelatt Jr, C. D., and Vecchi, M. P. Optimization by simulated annealing. science, 220 0 (4598): 0 671--680, 1983

    1983

  25. [33]

    Sampling approximately low-rank ising models: Mcmc meets variational methods

    Koehler, F., Lee, H., and Risteski, A. Sampling approximately low-rank ising models: Mcmc meets variational methods. In Conference on Learning Theory, pp.\ 4945--4988. PMLR, 2022

    2022

  26. [34]

    Crafting papers on machine learning

    Langley, P. Crafting papers on machine learning. In Langley, P. (ed.), Proceedings of the 17th International Conference on Machine Learning (ICML 2000), pp.\ 1207--1216, Stanford, CA, 2000. Morgan Kaufmann

    2000

  27. [35]

    Levin, D. A. and Peres, Y. Markov chains and mixing times, volume 107. American Mathematical Soc., 2017

    2017

  28. [36]

    Chernoff-type bound for finite markov chains

    Lezaud, P. Chernoff-type bound for finite markov chains. Annals of Applied Probability, pp.\ 849--867, 1998

    1998

  29. [37]

    Liptser, R. S. and Shiryaev, A. N. Statistics of random processes: I. General theory, volume 5. Springer Science & Business Media, 2013

    2013

  30. [38]

    Ising formulations of many np problems

    Lucas, A. Ising formulations of many np problems. Frontiers in physics, 2: 0 5, 2014

    2014

  31. [39]

    Lectures on glauber dynamics for discrete spin models

    Martinelli, F. Lectures on glauber dynamics for discrete spin models. Lectures on probability theory and statistics (Saint-Flour, 1997), 1717: 0 93--191, 1999

    1997

  32. [40]

    and Olivieri, E

    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 0 (3): 0 447--486, 1994

    1994

  33. [41]

    Martinelli, F., Olivieri, E., and Schonmann, R. H. For 2-d lattice spin systems weak mixing implies strong mixing. Communications in Mathematical Physics, 165 0 (1): 0 33--47, 1994

    1994

  34. [42]

    W., Rosenbluth, M

    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 0 (6): 0 1087--1092, 1953

    1953

  35. [43]

    Sampling, diffusions, and stochastic localization

    Montanari, A. Sampling, diffusions, and stochastic localization. arXiv preprint arXiv:2305.10690, 2023

    2023 arXiv

  36. [44]

    and Wu, Y

    Montanari, A. and Wu, Y. Posterior sampling from the spiked models via diffusion processes. arXiv preprint arXiv:2304.11449, 2023

    2023 arXiv

  37. [45]

    Statistical physics of spin glasses and information processing: an introduction

    Nishimori, H. Statistical physics of spin glasses and information processing: an introduction. Number 111. Clarendon Press, 2001

    2001

  38. [46]

    and Gutmann, M

    Rhodes, B. and Gutmann, M. Enhanced gradient-based mcmc in discrete spaces. arXiv preprint arXiv:2208.00040, 2022

    2022 arXiv

  39. [47]

    Roberts, G. O. and Tweedie, R. L. Exponential convergence of langevin distributions and their discrete approximations. 1996

    1996

  40. [48]

    High-resolution image synthesis with latent diffusion models

    Rombach, R., Blattmann, A., Lorenz, D., Esser, P., and Ommer, B. High-resolution image synthesis with latent diffusion models. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pp.\ 10684--10695, 2022

    2022

  41. [49]

    Variational annealing on graphs for combinatorial optimization

    Sanokowski, S., Berghammer, W., Hochreiter, S., and Lehner, S. Variational annealing on graphs for combinatorial optimization. Advances in Neural Information Processing Systems, 36: 0 63907--63930, 2023

    2023

  42. [50]

    A diffusion model framework for unsupervised neural combinatorial optimization

    Sanokowski, S., Hochreiter, S., and Lehner, S. A diffusion model framework for unsupervised neural combinatorial optimization. In Forty-first International Conference on Machine Learning, ICML 2024, Vienna, Austria, July 21-27, 2024 , 2024

    2024

  43. [51]

    and Sun, N

    Sly, A. and Sun, N. The computational hardness of counting in two-spin models on d-regular graphs. In 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science, pp.\ 361--369. IEEE, 2012

    2012

  44. [52]

    Denoising diffusion implicit models

    Song, J., Meng, C., and Ermon, S. Denoising diffusion implicit models. arXiv preprint arXiv:2010.02502, 2020 a

    2010 arXiv

  45. [53]

    P., Kumar, A., Ermon, S., and Poole, B

    Song, Y., Sohl-Dickstein, J., Kingma, D. P., Kumar, A., Ermon, S., and Poole, B. Score-based generative modeling through stochastic differential equations. arXiv preprint arXiv:2011.13456, 2020 b

    2011 arXiv

  46. [54]

    Path auxiliary proposal for mcmc in discrete space

    Sun, H., Dai, H., Xia, W., and Ramamurthy, A. Path auxiliary proposal for mcmc in discrete space. In International Conference on Learning Representations, 2021

    2021

  47. [55]

    K., and Dai, H

    Sun, H., Guha, E. K., and Dai, H. Annealed training for combinatorial optimization on graphs. In OPT 2022: Optimization for Machine Learning (NeurIPS 2022 Workshop), 2022

    2022

  48. [56]

    Any-scale balanced samplers for discrete space

    Sun, H., Dai, B., Sutton, C., Schuurmans, D., and Dai, H. Any-scale balanced samplers for discrete space. In The Eleventh International Conference on Learning Representations, 2023 a

    2023

  49. [57]

    Discrete langevin samplers via wasserstein gradient flow

    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, 2023 b

    2023

  50. [58]

    Titsias, M. K. and Yau, C. The hamming ball sampler. Journal of the American Statistical Association, 112 0 (520): 0 1598--1611, 2017

    2017

  51. [59]

    and Cho, K

    Wang, A. and Cho, K. Bert has a mouth, and it must speak: Bert as a markov random field language model. arXiv preprint arXiv:1902.04094, 2019

    1902 arXiv

  52. [60]

    Poincar \'e and transportation inequalities for gibbs measures under the dobrushin uniqueness condition

    Wu, L. Poincar \'e and transportation inequalities for gibbs measures under the dobrushin uniqueness condition. The Annals of Probability, 34 0 (5): 0 1960--1989, 2006

    1960

  53. [61]

    Informed proposals for local mcmc in discrete spaces

    Zanella, G. Informed proposals for local mcmc in discrete spaces. Journal of the American Statistical Association, 115 0 (530): 0 852--865, 2020

    2020

  54. [62]

    A langevin-like sampler for discrete distributions

    Zhang, R., Liu, X., and Liu, Q. A langevin-like sampler for discrete distributions. In International Conference on Machine Learning, pp.\ 26375--26396. PMLR, 2022

    2022

  55. [63]

    J., and Sutton, C

    Zhang, Y., Ghahramani, Z., Storkey, A. J., and Sutton, C. Continuous relaxations for discrete hamiltonian monte carlo. Advances in Neural Information Processing Systems, 25, 2012

    2012

  56. [64]

    write newline

    " write newline "" before.all 'output.state := FUNCTION n.dashify 't := "" t empty not t #1 #1 substring "-" = t #1 #2 substring "--" = not "--" * t #2 global.max substring 't := t #1 #1 substring "-" = "-" * t #2 global.max substring 't := while if t #1 #1 substring * t #2 gl...

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.