Skip to main content
Back

HiSS Beats Gradient Samplers by Hopping Across Impossible Probability Gaps

A new MCMC sampler uses logistic noise to jump between disconnected modes in discrete distributions, beating parallel tempering on Ising models, TSP, and binary neural nets.

Pro

  • New AISTATS 2026 paper introduces HiSS, a discrete MCMC sampler for isolated modes.
  • Couples discrete variable with continuous auxiliary via a fat-tailed logistic kernel for mode-hopping.
  • Uses Metropolis-within-Gibbs then DMALA gradient refinement; proves detailed balance and uniform ergodicity.
  • Beats GWG, DMALA, ACS, and parallel tempering on Ising, TSP eil14, and binary Bayesian NNs.
  • Uses roughly 4x fewer energy evaluations than parallel tempering while converging faster.
  • Code at github.com/pinakirm/HiSS; main hyperparameter is logistic scale η.

Sampling from discrete distributions with many isolated peaks shows up everywhere: text generation, protein sequence prediction, binary neural networks, and combinatorial optimization. Gradient-based samplers are fast, but they follow the slope of the energy function, which is useless when the mode you want sits on the other side of a near-zero-probability wall. A new AISTATS 2026 paper from Pinaki Mohanty and Ruqi Zhang, Slithering Through Gaps, proposes a fix called HiSS (Hyperbolic Secant-squared Gibbs Sampling) that pairs the discrete state with a continuous auxiliary variable and a heavy-tailed logistic kernel to help the chain hop between disconnected regions.

Why gradient-based discrete samplers get stuck

The go-to methods for scalable discrete sampling in recent years, Gibbs-With-Gradient (GWG) and the Discrete Langevin Proposal / DMALA, extend Langevin-style dynamics onto discrete variables. They use gradients of a differentiable relaxation of the energy function to propose the next state. That works well on smooth landscapes, but gradient-based discrete samplers frequently get trapped in local modes when the energy is rugged or disconnected, which cripples mixing and convergence in high-dimensional multimodal spaces.

Existing workarounds have their own drawbacks. Parallel tempering runs several replicas at different temperatures and swaps between them, but raising the temperature does not help when the barrier probability is literally zero: if p(θ) = 0, then p(θ)^β is also zero for any β. Cyclical step-size schedules (ACS) help somewhat by alternating exploration and exploitation phases, yet they still rely on local gradient information to move.