Research map / Probabilistic and scientific modeling / Variational and generative sampling
Sampling Binary Data by Denoising through Score Functions
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.
Extends score-based denoising and walk-jump sampling to binary data on the Boolean hypercube using Bernoulli sign-flip noise, deriving a binary Tweedie-type formula and discrete Langevin samplers with contraction guarantees.
Problem
Sampling distributions on the Boolean hypercube {-1,1}^d via smoothing and denoising, since Gaussian smoothing is not available for purely binary data.
Approach
Use Bernoulli random sign-flip noise as the smoothing device; the optimal Hamming-loss denoiser equals (1/alpha) times the score of the noisy marginal, giving a binary analogue of Tweedie-Miyasawa. Sampling uses one-stage and two-stage discrete Langevin kernels, and multiple independent Bernoulli measurements reduce effective noise to m*alpha.
Key results
- Theory: one-stage and two-stage discrete Langevin kernels are exponentially contractive in Wasserstein distance under conditions like alpha <= 1/(4 sqrt(d)).
- Denoising error bounded by d*exp(-m*alpha) with m measurements, so effective noise drops as m grows.
- On binarized MNIST, the sampler mixes well at alpha=0.5 with step size 1/alpha, while alpha=2 is reported to break down.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Increase the number of Bernoulli measurements (ablation) | Optimal denoising · Synthetic binary mixtures | Wasserstein distance to the clean distribution | Helped |
| Use the two-stage instead of the one-stage discrete Langevin sampler (ablation) | Discrete Langevin sampling · Synthetic binary mixtures, small α | Denoising performance of stationary samples | Helped |
| Set the step size to η = 1/α instead of using a step size that is too small (ablation) | Discrete Langevin sampling · Synthetic binary mixtures | Mixing time | Helped |
| Increase Bernoulli noise by decreasing α (ablation) | Two-stage discrete Langevin sampler · Binarized MNIST | Mixing performance | Helped |
| Increase Bernoulli noise by decreasing α (ablation) | Denoiser · Binarized MNIST | Denoising performance | Hurt |
| Use α = 2 instead of the higher-noise settings (ablation) | Discrete Langevin sampler · Binarized MNIST | Sampling performance | Hurt |
| Use Bernoulli noise instead of Gaussian noise at the same α | Denoising · Synthetic data | Denoising performance | No clear effect |
| Use high noise with a strong prior | Optimal denoiser · Synthetic binary mixtures | Denoising performance | Helped |
| Use high noise with a weak prior | Optimal denoiser · Synthetic binary mixtures | Denoising performance | No clear effect |
| Increase α (ablation) | Discrete Langevin sampling and denoising · Synthetic binary mixtures | Denoising performance of stationary samples | Mixed |
Surprising findings
- The Bernoulli-noise denoising error bound goes exponentially to zero as alpha grows, unlike the Gaussian case.
- The sampler breaks down at alpha=2 on binarized MNIST, showing a sweet spot at high noise.
Limitations
- Stationary distribution of the one-stage discrete Langevin chain may not approach the target even as step size vanishes.
- Denoising performance is only partially improved by multiple measurements; bounds are loose compared with experiments.
- Experiments limited to d=6-8 synthetic data and binarized MNIST.
Experimental setup
Datasets: MNIST synthetic binary mixture data
Benchmarks: synthetic binary mixture (d=8, d=6) binarized MNIST
Metrics: Wasserstein distance (Hamming) mean-square error of denoising mixing time 1/(1-lambda_2)
Baselines: one-stage discrete Langevin sampler Gaussian-noise smoothing (comparison)
Builds on: walk-jump sampling Tweedie-Miyasawa formula sequential multi-measurement sampling discrete Langevin MCMC
Closest papers by meaning
- BGDB: Bernoulli-Gaussian Decision Block with Improved Denoising Diffusion Probabilistic Models (AAAI 2025 · similarity 0.89)
- Provable Posterior Sampling with Denoising Oracles via Tilted Transport (NeurIPS 2024 · similarity 0.88)
- Adapting to Unknown Low-Dimensional Structures in Score-Based Diffusion Models (NeurIPS 2024 · similarity 0.88)
- Test-Time Scaling of Diffusion Models via Noise Trajectory Search (NeurIPS 2025 · similarity 0.88)
- Bernoulli Flow Models: Self-Consistent Generative Modeling for Binary Data (NeurIPS 2026 · similarity 0.88)
- Noise Conditional Variational Score Distillation (ICML 2025 · similarity 0.87)
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.