How far can the ideas behind the No-U-Turn Sampler really go?
We’ve been thinking about this question for some time, and it motivates recent work with my student Zichu Wang (Courant Institute, NYU):
From Continuous to Discrete: A No-U-Turn Sampler for Permutations
The No-U-Turn Sampler (NUTS) is most often viewed as a tool specific to Hamiltonian Monte Carlo (HMC): an elegant way to adaptively choose trajectory lengths and avoid inefficient backtracking in continuous state spaces. But at a deeper level, NUTS reflects a more general principle about how efficient sampling algorithms are designed.
This project grew out of a broader effort to understand how far that principle extends beyond continuous HMC. In particular, we were drawn to discrete-space settings, where several of the key ingredients behind NUTS actually appeared much earlier, albeit in different guises.
Classic auxiliary-variable methods, such as the Swendsen-Wang algorithm, show how enlarging the state space can turn slow, local random walks into efficient global moves. Their effectiveness comes from how augmentation reshapes the geometry seen by the sampler, enabling long-range moves that would be difficult or unlikely in the original variables. This mirrors the philosophy behind HMC, where momentum augmentation similarly reshapes the geometry to enable coherent, long-range exploration while preserving reversibility.
In this paper, we make that perspective concrete for permutation-valued targets. We construct long, reversible trajectories using NUTS-style auxiliary variables, adapt trajectory growth in a discrete setting, and connect these constructions to modern trajectory-based MCMC ideas in a principled way. To begin analyzing the resulting Markov chains, we use tools such as path coupling to obtain a first rigorous understanding of their behavior.
At a high level, the message is a unifying one: auxiliary-variable augmentation can reshape the effective geometry of a sampling problem, making efficient long-range exploration natural, even in discrete spaces.
Projects like this capture one of the most rewarding aspects of advising: seeing a student take an idea that’s been in the air for a while and develop it in a genuinely new direction.