# Exploring Non-Convex Discrete Energy Landscapes: An Efficient Langevin-Like Sampler with Replica Exchange

arXiv: https://arxiv.org/abs/2501.17323 · HTML: https://mlsanity.com/paper/2501.17323/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 25 of its 59 references that are in the map.
- First posted on arXiv 28 Jan 2025.

## Builds on (most cited first, 25 of 25)

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [U-Net: Convolutional Networks for Biomedical Image Segmentation](https://mlsanity.com/paper/1505.04597/) (2015)
- [Efficient Estimation of Word Representations in Vector Space](https://mlsanity.com/paper/1301.3781/) (2013)
- [Discrete Diffusion Modeling by Estimating the Ratios of the Data Distribution](https://mlsanity.com/paper/2310.16834/) (2023)
- [Hard Prompts Made Easy: Gradient-Based Discrete Optimization for Prompt Tuning and Discovery](https://mlsanity.com/paper/2302.03668/) (2023)
- [Deep Generative Modelling: A Comparative Review of VAEs, GANs, Normalizing Flows, Energy-Based and Autoregressive Models](https://mlsanity.com/paper/2103.04922/) (2021)
- [Cyclical Stochastic Gradient MCMC for Bayesian Deep Learning](https://mlsanity.com/paper/1902.03932/) (2019)
- [Non-asymptotic convergence analysis for the Unadjusted Langevin Algorithm](https://mlsanity.com/paper/1507.05021/) (2015)
- [Score-based Continuous-time Discrete Diffusion Models](https://mlsanity.com/paper/2211.16750/) (2022)
- [Log-concave sampling: Metropolis-Hastings algorithms are fast](https://mlsanity.com/paper/1801.02309/) (2018)
- [Generative Flow Networks for Discrete Probabilistic Modeling](https://mlsanity.com/paper/2202.01361/) (2022)
- [Oops I Took A Gradient: Scalable Sampling for Discrete Distributions](https://mlsanity.com/paper/2102.04509/) (2021)
- [Consistency and fluctuations for stochastic gradient Langevin dynamics](https://mlsanity.com/paper/1409.0578/) (2014)
- [Optimal dimension dependence of the Metropolis-Adjusted Langevin Algorithm](https://mlsanity.com/paper/2012.12810/) (2020)
- [Beyond ELBOs: A Large-Scale Evaluation of Variational Methods for Sampling](https://mlsanity.com/paper/2406.07423/) (2024)
- [On the Convergence of Stochastic Gradient MCMC Algorithms with High-Order Integrators](https://mlsanity.com/paper/1610.06665/) (2016)
- [Non-convex Learning via Replica Exchange Stochastic Gradient MCMC](https://mlsanity.com/paper/2008.05367/) (2020)
- [Beyond Log-concavity: Provable Guarantees for Sampling Multi-modal Distributions using Simulated Tempering Langevin Monte Carlo](https://mlsanity.com/paper/1710.02736/) (2017)
- [Stochastic Runge-Kutta Accelerates Langevin Monte Carlo and Beyond](https://mlsanity.com/paper/1906.07868/) (2019)
- [Learning Discrete Energy-based Models via Auxiliary-variable Local Exploration](https://mlsanity.com/paper/2011.05363/) (2020)
- [Accelerating Nonconvex Learning via Replica Exchange Langevin Diffusion](https://mlsanity.com/paper/2007.01990/) (2020)
- [Stochastic Quasi-Newton Langevin Monte Carlo](https://mlsanity.com/paper/1602.03442/) (2016)
- [Accelerating Convergence of Replica Exchange Stochastic Gradient MCMC via Variance Reduction](https://mlsanity.com/paper/2010.01084/) (2020)
- [Gradient-based Discrete Sampling with Automatic Cyclical Scheduling](https://mlsanity.com/paper/2402.17699/) (2024)

## Abstract (arXiv)

Gradient-based Discrete Samplers (GDSs) are effective for sampling discrete energy landscapes. However, they often stagnate in complex, non-convex settings. To improve exploration, we introduce the Discrete Replica EXchangE Langevin (DREXEL) sampler and its variant with Adjusted Metropolis (DREAM). These samplers use two GDSs at different temperatures and step sizes: one focuses on local exploitation, while the other explores broader energy landscapes. When energy differences are significant, sample swaps occur, which are determined by a mechanism tailored for discrete sampling to ensure detailed balance. Theoretically, we prove that the proposed samplers satisfy detailed balance and converge to the target distribution under mild conditions. Experiments across 2d synthetic simulations, sampling from Ising models and restricted Boltzmann machines, and training deep energy-based models further confirm their efficiency in exploring non-convex discrete energy landscapes.