Research map / Probabilistic and scientific modeling / Variational and generative sampling
Sampling from Binary Quadratic Distributions via Stochastic Localization
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Applies stochastic localization to binary quadratic distributions and proves that, after enough SL iterations, posteriors have a large external field that yields Poincaré inequalities (polynomial mixing) for Glauber and Metropolis-type discrete MCMC samplers, with QUBO experiments on MIS, MaxCut and MaxClique.
Problem
Sampling from binary quadratic distributions (Ising-type Gibbs measures / QUBO) is hard; existing SL theory for discrete settings is limited to specific models (SK, random field Ising), and general discrete MCMC mixing guarantees under SL are missing.
Approach
SL posteriors on BQDs reduce to Gibbs measures with a linear external field h_t = b + alpha(t)Y_t/(sigma^2 t) that grows to infinity; once |h| exceeds a threshold relative to the interaction strength, Dobrushin-matrix arguments give Poincaré inequalities for Glauber dynamics, Metropolis chains, gradient-informed single-site MH, and DULA with high probability.
Key results
- SL-PAS improves over PAS by 0.15% and 0.25% on R-0.05 and R-0.10 MIS instances.
- SL variants improve over their MCMC counterparts on all 14 reported datasets, with gains on MaxCut BA-512 up to 0.045% for PAS.
- On MaxClique RB, SL-PAS reaches 87.649% optimality gap vs 87.544% for PAS; TWITTER all methods reach 100%.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Apply stochastic localization to PAS | PAS · MIS benchmarks | objective value: 104.375 $\pm$ 1.64 -> 104.531 $\pm$ 1.48; 61.750 $\pm$ 0.94 -> 61.906 $\pm$ 0.88; 34.063 $\pm$ 0.61 -> 34.375 $\pm$ 0.55 | Helped |
| Apply stochastic localization to PAS | PAS · MaxClique RB | optimality gap (%): 87.544 $\pm$ 6.15 -> 87.649 $\pm$ 6.14 | Helped |
| Apply stochastic localization to PAS | PAS · MaxClique TWITTER | optimality gap (%): 100.000 $\pm$ 0.00 -> 100.000 $\pm$ 0.00 | No clear effect |
| Apply stochastic localization to PAS | PAS · MaxCut ER and BA datasets | optimality gap (%): 101.884 $\pm$ 1.76 -> 101.920 $\pm$ 1.76; 100.158 $\pm$ 0.12 -> 100.174 $\pm$ 0.12; 100.120 $\pm$ 0.13 -> 100.123 $\pm$ | Helped |
| Apply stochastic localization to PAS | PAS · MaxCut OPTSICOM | optimality gap (%): 100.000 $\pm$ 0.00 -> 100.000 $\pm$ 0.00 | No clear effect |
| Use exponential-decay rather than identical MCMC-step allocation across SL iterations (ablation) | SL sampling framework · Combinatorial optimization benchmarks | objective value or optimality gap | Mixed |
| Use uniform rather than Log-SNR SDE time discretization (ablation) | SL sampling framework · Combinatorial optimization benchmarks | objective value or optimality gap | Mixed |
Limitations
- Improvements over baselines are small (often below 1%) and differences are within reported standard deviations.
- Theory covers only binary variables and does not prove convergence of the overall SL process to the target distribution.
- Extension to deep energy-based models with unknown forms is left open.
Experimental setup
Datasets: DISCS benchmark MIS (ER-density, SATLIB) DISCS MaxCut (ER, BA, OPTSICOM) DISCS MaxClique (RB, TWITTER)
Benchmarks: DISCS MIS DISCS MaxCut DISCS MaxClique
Metrics: objective value optimality gap percentage
Baselines: GWG PAS DMALA Gurobi
Builds on: SLIPS Gibbs With Gradients Path Auxiliary Sampler Discrete Metropolis-Adjusted Langevin Algorithm DISCS
Closest papers by meaning
- Stochastic Localization via Iterative Posterior Sampling (ICML 2024 · similarity 0.89)
- Faster Sampling via Stochastic Gradient Proximal Sampler (ICML 2024 · similarity 0.85)
- Nearly $d$-Linear Convergence Bounds for Diffusion Models via Stochastic Localization (ICLR 2024 · similarity 0.85)
- Faster Diffusion Sampling with Randomized Midpoints: Sequential and Parallel (ICLR 2025 · similarity 0.85)
- Zeroth-Order Sampling Methods for Non-Log-Concave Distributions: Alleviating Metastability by Denoising Diffusion (NeurIPS 2024 · similarity 0.85)
- Scalable Discrete Diffusion Samplers: Combinatorial Optimization and Statistical Physics (ICLR 2025 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.