Research map / Optimization / Optimizers
Gradient-based Discrete Sampling with Automatic Cyclical Scheduling
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.
Proposes Automatic Cyclical Sampler (ACS), a gradient-based discrete MCMC sampler with cyclical step-size and balancing-parameter schedules, auto-tuned by acceptance-rate targeting, with non-asymptotic convergence guarantees.
Problem
Gradient-based discrete samplers get trapped in local modes when sampling highly multimodal discrete distributions such as RBMs, energy-based models, and LLM-based text infilling.
Approach
Parameterize a gradient-informed proposal by step size alpha and balancing parameter beta, cycle both on a schedule (large steps explore, small steps exploit), pick beta per alpha to maximize acceptance, and auto-tune alpha_max/alpha_min to a target acceptance rate.
Key results
- On EBM learning, ACS reaches test log-likelihood of -91.487 on Omniglot vs -94.72 for GWG and -99.243 for DMALA.
- On Caltech Silhouettes EBM learning, ACS achieves -89.262 vs -96.20 for GWG.
- On text infilling (Grimm), ACS improves unique 2-gram/3-gram to 53.91/74.70 vs DMALA's 48.55/70.56 while having higher perplexity (369 vs 281).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use ACS instead of DMALA or GWG for EBM learning | Deep convolutional EBM · Static MNIST, Dynamic MNIST, Omniglot, Caltech | AIS log likelihood | Helped |
| Use ACS instead of DMALA | RoBERTa text infilling · Grimm and SST2 | perplexity | Hurt |
| Use ACS instead of DMALA | RoBERTa text infilling · Grimm and SST2 | CoLA | Helped |
| Use ACS instead of DMALA | RoBERTa text infilling · Grimm and SST2 | Self-BLEU | Helped |
| Use ACS instead of DMALA | RoBERTa text infilling · Grimm and SST2 | unique n-gram | Helped |
| Vary steps per cycle (ablation) | ACS RBM sampling · MNIST, kMNIST, eMNIST, Omniglot, and Caltech | log MMD | Mixed |
| Vary maximum balancing parameter (ablation) | ACS RBM sampling · MNIST, kMNIST, eMNIST, Omniglot, and Caltech | log MMD | Mixed |
| Vary the tested ACS hyperparameter settings (ablation) | ACS RBM sampling · Multiple RBM datasets | log MMD | Mixed |
Surprising findings
- Perplexity is worse for ACS in text infilling even though its diversity metrics are better, which the authors attribute to CoLA acceptability being higher.
Limitations
- Convergence proof requires twice differentiable, locally strongly concave energy and is not tied to the specific tuning algorithm.
- Some hyperparameters (beta_max, rho*, cycle length s) still need tuning; Caltech Silhouettes required a grid search over target acceptance rate.
- Cycle length s chosen from only two values without an automatic procedure.
Experimental setup
Datasets: MNIST Omniglot Caltech Silhouettes Grimm SST2 kMNIST eMNIST
Benchmarks: RBM sampling MMD vs Block Gibbs deep EBM sampling convergence EBM learning AIS log-likelihood on MNIST/Omniglot/Caltech text infilling diversity and perplexity
Metrics: maximum mean discrepancy AIS log-likelihood perplexity CoLA self-BLEU unique n-gram
Baselines: Gibbs-with-Gradient (GWG) Any-scale balanced sampler (AB) DMALA Block Gibbs random walk sampler
Builds on: Gibbs-with-Gradient any-scale balanced sampler DMALA cyclical step size schedule for continuous SGMCMC persistent contrastive divergence
Closest papers by meaning
- Scalable Discrete Diffusion Samplers: Combinatorial Optimization and Statistical Physics (ICLR 2025 · similarity 0.87)
- Jump Your Steps: Optimizing Sampling Schedule of Discrete Diffusion Models (ICLR 2025 · similarity 0.87)
- Align Your Steps: Optimizing Sampling Schedules in Diffusion Models (ICML 2024 · similarity 0.86)
- Learnable Sampler Distillation for Discrete Diffusion Models (NeurIPS 2025 · similarity 0.85)
- Adaptive Non-Uniform Timestep Sampling for Accelerating Diffusion Model Training (CVPR 2025 · similarity 0.85)
- Continuous-Time Distribution Matching for Few-Step Diffusion Distillation (NeurIPS 2026 · 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.