No-U-Turn sampler (original slice formulation)
Algorithms AIMech:OriginalNoUTurnSampler DRAFT
The original 2014 slice-based NUTS algorithm, which adapts a Hamiltonian trajectory’s length through randomly directed binary-tree doubling and selects a valid next state while enforcing subtree U-turn and reversibility conditions.
Identity Notes & Concept Scope
This record is restricted to Hoffman and Gelman’s 2014 slice formulation, principally efficient Algorithm 3. Algorithm 2 is its simpler uniform-selection derivation. The paper’s acronym NUTS is context, not an asserted exact alias for every later algorithm with that name. Dual-averaging step-size warmup is separable from the fixed-step-size NUTS transition. No normalized identity match was found across all 442 pinned AIO labels/scoped synonyms and 153 prior native IDs/names/aliases. Both checkout text searches included ignored and hidden files and returned no matches for the selected exact IDs, full labels, aliases and source titles. Existing HMM and Markov random field records describe probability models, not these sampling or tuning procedures.
Claims & Grounded Evidence
2 Claims
Mechanism
#method
Refresh standard Gaussian momentum and draw a slice variable below the current joint density. Build a balanced trajectory tree by randomly extending forward or backward through 1, 2, 4 and further powers of two leapfrog steps. Check both endpoint dot products for the balanced subtrees; stop if either turns negative or the slice-relative joint log density falls below the allowed energy-error threshold. States outside the slice cannot be next samples. A stopping condition inside the newly added half-tree excludes that half-tree from candidate selection; a U-turn only at the completed whole-tree boundary permits its valid candidates. Efficient Algorithm 3 samples a representative within each new subtree in proportion to valid-state counts, then updates the retained candidate with probability min(1,n_new/n_old) when that new subtree is valid. Its transition preserves the uniform distribution over the valid candidate set; it is not simply uniform selection from the final whole tree.
Limitation
#nuts-domain
The paper limits direct use to differentiable continuous coordinates, discusses transformations and separate treatment of discrete variables, and identifies mass-matrix changes as extensions rather than the unit-mass formulation itself.
⚠️ Curated Limitations & Negative Results
- Stopping one forward trajectory at its first U-turn without the paper’s balanced-tree construction and candidate exclusions is not the defined valid NUTS kernel.
- The source mechanism uses identity mass and its corresponding Euclidean dot-product criterion. Nonidentity or position-dependent metrics require an appropriate formulation; no generalized metric rule is inferred here.
- Eliminating a preset leapfrog-step count does not eliminate step size, numerical-divergence handling, model geometry, convergence assessment or implementation resource limits.
- The efficient top-level candidate transition and uniform selection within a subtree are different operations. Zero valid-candidate counts require guarded implementation; no literal zero-over-zero probability is asserted.
- This is not a specification of later multinomial NUTS or current Stan defaults. No author implementation was executed or performance result reproduced.
Artificial Intelligence Ontology (AIO) Grounding
Mapped AIO Classes
| AIO Target Class | Mapping Relation | Mapping Rationale |
|---|---|---|
AIO:MarkovChain
Markov Chain
|
related_match | This procedure constructs transitions of a Markov chain to sample a specified target distribution. The exact AIO CLASS describes a stochastic process/model with dependence on the preceding state and is exported beneath Network. The method-to-process relationship is related_match, not equivalence, subclass membership or a claim that the sampler is a trained network. |
Evidence Sources & Primary Literature
2 Sources| Source ID | Publication / Document | Type / Access | Reference & Checksum |
|---|---|---|---|
method-source
|
Matthew D. Hoffman, Andrew Gelman
|
primary paper
full_text
|
ID: https://www.jmlr.org/papers/v15/hoffman14a.html
sha256:bf2a5592015b…
|
nuts-domain
|
Matthew D. Hoffman, Andrew Gelman
|
primary paper
full_text
|
ID: https://www.jmlr.org/papers/v15/hoffman14a.html
sha256:bf2a5592015b…
|
Curation Provenance
Curator: Codex
Method: ai_assisted
Model: GPT-6
Created: 2026-10-11T06:48:02Z
Updated: 2026-10-11T06:48:02Z
Source File:
data/curated/OriginalNoUTurnSampler.yaml