Source-linked AI summary
Optimal Slice-Adaptive Tuning of Hybrid Slice Sampling
Trevor Campbell
TL;DR
Slice sampling adapts to local slice size, but the slice is unknown and the cost of approximating it depends on the starting window width. This paper analyzes per-iteration evaluation costs and develops automated tuning schemes; simulations show reliable near-optimal tuning with no noticeable dependence on the initial width.
Problem
The slice is unknown, so implementations grow an approximate slice from a window whose width affects the sampler’s long-run computational cost.
Source: §1 · pp. 1–2Method
Results
Simulations show that the tuning schemes reliably achieve near-optimal tuning with no noticeable dependence on the initial w.
Source: §1 · p. 2Takeaways & Limitations
The schemes require no user input, supporting automated use in probabilistic programming libraries.
Source: §1 · p. 2Tuning uses bounds on slice width at each iteration rather than the width λ itself.
Source: §5 · p. 14
Abstract
from arXiv · showhide
Slice sampling is a Markov chain Monte Carlo algorithm that draws its next state uniformly from a "slice"---a super-level set of the target density function---at each iteration, thereby providing automatic local adaptivity to the scale of the target. In practice the exact slice is not known, so general-purpose implementations use an approximate slice that is grown from a starting interval of length $w>0$, with a computational cost that depends on $w$. This work presents an analysis of the average per-iteration number of target density evaluations, as a function of $w$, of hybrid slice sampling with various slice-finding schemes for targets with contiguous slices. The paper uses the results of the analysis to develop automated, slice-adaptive tuning schemes along with suboptimality bounds and asymptotic convergence guarantees. Simulations demonstrate that the tuning schemes reliably yield near-optimal slice-adaptive tuning with essentially no dependence on the initial setting of $w$.
1. Introduction.
Slice sampling adapts locally, but its slice is unknown and the approximate slice’s cost depends on the initial window width. This work characterizes that cost and develops automated tuning schemes for the width.
1. Introduction.
- The slice sampler draws a level and then a state uniformly from the corresponding super-level set along a chosen direction, adapting move scale to local slice size.Appropriate direction distributions recover hit-and-run or Gibbs sampling.Source: §1 · p. 1
- The oracle-optimal window is proportional to slice width: w = 1.358λ for stepping out, 3.211λ for cached doubling, and 2.277λ for lazy cached doubling.Their average per-iteration target-density evaluation costs are 4.715, 5.901, and 5.410, respectively.Source: §1 · p. 2
- One-shot and gradient-based schemes tune w as a function of u, with suboptimality bounds and convergence in probability to their respective surrogate optima under mild additional assumptions.Simulations yield near-optimal tuning without noticeable dependence on the initial w, and tuning cost vanishes relative to slice sampling’s base cost.Source: §1 · p. 2
- Because slice width λ varies conditional on slice level u, the oracle settings are generally unattainable; practical tuning instead uses conditional-width means or quantiles, or tractable surrogate objectives.The one-shot formulas use conditional means or quantiles; gradient-based schemes use convex, smooth objectives.Source: §1 · p. 2
- Prior work developed hybrid schemes and several adaptive variants; this work adds exact cost characterization, tractable surrogate objectives with guarantees, and automated slice-adaptive tuning.The authors describe their contribution as orthogonal to much of the prior adaptive slice-sampling literature and potentially combinable with it.Source: §1 · p. 2
2. Hybrid slice sampling with lazy cached doubling.
Lazy cached doubling uses stored density evaluations and short-circuit evaluation to avoid unnecessary target calls. Its savings are especially large for small initial windows and remain substantial near well-tuned settings.
2. Hybrid slice sampling with lazy cached doubling.
- The methods retain Neal’s stepping-out and shrinkage implementations, while introducing cached and lazy-cached variants for doubling and its acceptance check.The pseudocode establishes notation and precise target-evaluation counts for the subsequent analysis.Source: §2 · p. 3
- Lazy cached doubling combines cached densities with short-circuit evaluation during slice growth and acceptance, avoiding evaluations already known or unnecessary.Simple cached doubling uses the cache without lazy evaluation and is retained because it is more amenable to analysis.Source: §2 · p. 3
- Lazy caching saves around 1–2 evaluations, or about 15–25% of overall cost, for well-tuned w; savings are substantial for small w.The comparison is against Neal’s original doubling scheme.Source: §2 · p. 3
3. Analysis.
The analysis characterizes per-iteration evaluation costs for hybrid slice samplers under contiguous-slice conditions. It compares stepping out with cached and lazy cached doubling, including their costs and slice-adaptive tuning.
3. Analysis.
- Under Assumption 3.1, stepping and doubling produce iterates distributed as ideal slice sampling, terminate in finite time almost surely, and obey a law of large numbers for integrable functions.The analysis assumes contiguous slices and conditions that exclude pathological zero-width slices; its main results also apply to multivariate targets whose one-dimensional slices are contiguous.Source: §3 · pp. 3–4
3.1. Shrinkage.
- The expected shrinkage cost has a closed-form expression derived by solving a partial differential equation, and depends on the approximate-slice boundary exceedances.The resulting expression is combined with the exceedance distributions for stepping out and doubling to analyze their total costs.Source: §3.1 · p. 5
3.2. Stepping Out.
- For stepping out, the analysis combines slice-finding cost 2 + N, zero acceptance-check cost, and expected shrinkage cost to characterize total per-iteration cost.The result uses the stepping-out iteration and right-exceedance distributions and defines fstep(x) = 1 + x + 2(x + 1)log(1 + 1/x).Source: §3.2 · p. 6
3.3. Doubling.
- Cached doubling receives an exact expected-cost characterization, while lazy cached doubling is analyzed through continuity and asymptotic properties that guarantee its optimum can be approximated on a finite interval.Numerical optimization gives lazy cached doubling’s slice-adaptive width w⋆ = αλ with α ≈2.277 and expected cost ≈5.410.Source: §3.3 · pp. 7–8
3.4. Summary and comparison of hybrid methods.
- Lazy cached doubling is at most ≈25% more expensive than stepping out, while stepping out can be arbitrarily worse than either doubling method; lazy doubling is recommended for robust automated tuning.When w/λ is small, the methods’ costs are approximately λ/w for stepping, 2log2(λ/w) for cached doubling, and (5/6)log2(λ/w) for lazy cached doubling; when w/λ is large, all have asymptotic cost ≈2log(w/λ).Source: §3.4 · p. 8
4. Slice-adaptive tuning.
The section turns ideal width choices proportional to slice width into tractable slice-adaptive tuning, including schemes based on known or MCMC-estimated conditional width distributions. Simulations report near-oracle costs with little dependence on initial width, and increasing benefit from slice-adaptivity as slice widths vary more.
4. Slice-adaptive tuning.
- The ideal width is proportional to slice width, but because λ varies conditional on u, practical tuning chooses w(u) by minimizing expected cost given u.This applies when slices are contiguous and the Markov chain law of large numbers holds.Source: §4 · pp. 8–9
- Because direct cost minimization is generally nonconvex and nonsmooth, the paper uses surrogate costs for one-shot and gradient-based tuning, with suboptimality bounds.The one-shot surrogates permit closed-form minimization, while the gradient surrogates are convex and locally smooth.Source: §4 · p. 9
4.1. Tuning with known slice width distribution.
- For stepping-out cost, bwstep is (3,0)-optimal and ewstep is (1,0)-optimal; for cached and lazy cached doubling costs, bwcache and bwlazy are (1,4)-optimal, while ewcache and ewlazy are (1,0.7)-optimal.The optimization problems in ewstep, ewcache, and ewlazy are tractable.Source: §4.1 · p. 10
4.2. Tuning with MCMC draws.
- With MCMC draws, the algorithm estimates λ given u in bins and refines a piecewise-constant window function using the known-distribution tuning results.It thins and sorts draws by slice value, then uses empirical distributions within bins.Source: §4.2 · pp. 10–11
- Under mild assumptions, the MCMC-based procedure’s per-iteration cost converges to the slice-adaptive optimum for each surrogate cost function.The theorem uses a finite set of candidate widths within each bin.Source: §4.2 · p. 11
- Tuning work is sublinear in iteration count, while evaluating w(u) adds a logarithmic binary-search factor to sampling cost.The paper notes that the search is typically much faster than a density evaluation and can be bounded by limiting the number of bins.Source: §4.2 · p. 11
4.3. Simulations.
- Proposed tuning reaches near-oracle per-iteration costs across univariate, multidimensional, and multimodal settings, largely regardless of initial w.The simulations include hit-and-run sampling and show convergence after about 100 iterations for stepping out and lazy cached doubling.Source: Figure 5 · p. 12, §4.3 · pp. 12–13, Figure 6 · p. 13
- As slice widths vary more, slice-adaptive tuning provides increasing benefit over tuned constant w; lazy cached doubling is more robust to mistuning than stepping out.Stepping out often became too expensive to run during early tuning rounds.Source: §4.3 · p. 13, Figure 7 · p. 14
5. Conclusion.
The paper analyzes slice-sampling cost and develops automated, near-optimal tuning, with asymptotic convergence guarantees. It identifies bounds-based tuning and covariance adaptation as directions for further work.
5. Conclusion.
- The work combines per-iteration cost characterizations, improved lazy cached doubling, and automated tuning with suboptimality guarantees and asymptotic convergence in probability to surrogate optimal cost.The convergence guarantee concerns tuning methods using draws from Markov chain Monte Carlo.Source: §5 · p. 14
- A natural multivariate extension makes the initial width depend on both slice value u and direction ρ, using the conditional slice-width distribution given both.For slice sampling within Gibbs, the authors suggest tuning a separate width function for each coordinate direction because model variables may have different posterior scales.Source: §5 · p. 14
- Current tuning uses bounds on slice width at each iteration rather than the slice width λ itself.The authors identify rigorous handling of this unobservability without substantially increasing computational cost as future work.Source: §5 · p. 14
APPENDIX A: SURROGATE APPROXIMATIONS
The appendix establishes approximation guarantees for surrogate cost functions used in slice-adaptive tuning. It describes how different surrogate properties support closed-form or gradient-based optimization and validates the error bounds by simulation.
Surrogate design
- The tuning methods use surrogate approximations of fstep, fcache, and flazy to obtain tractable optimization problems given the conditional distribution of λ.The paper uses approximation results to analyze suboptimality for its one-shot and gradient-based tuning strategies.Source: Appendix A · pp. 16–17
- The b-surrogates are designed to give closed-form optima for one-shot tuning, while the e-surrogates are designed to be convex and locally smooth for gradient optimization.The tuning procedures optimize surrogate costs when the conditional distribution of slice width λ given u is known.Source: Appendix A · pp. 16–17
Approximation guarantees
- bfstep is a (0.5,0)-approximation of fstep, while bfcache and bflazy are each (0,2)-approximations of their corresponding costs.efcache and eflazy are each (0,0.35)-approximations of their corresponding costs; fstep ◦exp, efcache ◦exp, and eflazy ◦exp are convex and locally smooth.Source: Appendix A · p. 17
- All plotted normalized approximation errors are at most 1, matching the bounds from Lemma A.2.Fig. 8 plots each surrogate's error normalized by εf + δ using the ε and δ values from the lemma.Source: Appendix A · p. 17, Figure 8 · p. 18
APPENDIX B: PROOFS
The appendix proves the hybrid sampler’s equivalence to ideal slice sampling and almost-sure termination, and establishes irreducibility, uniqueness, and convergence results under the stated conditions. It also derives cost bounds and optimality guarantees for window choices across the analyzed slice-finding schemes, including lazy slice sampling.
PROOF OF LEMMA 3.2
- The hybrid sampler matches ideal slice sampling in distribution, and its bounding and shrinkage steps terminate in finite time almost surely.The proof relies on contiguous finite-length slices; the shrinkage step removes only invalid proposals and samples uniformly from the slice conditional on u.Source: Appendix B · p. 18
LLN proof
- The ideal slice sampler is irreducible and dominated by π, supporting the positive-Harris-recurrence argument used to establish the LLN.The proof concludes that any set A with π(A) > 0 can be reached in one step.Source: Appendix B · pp. 18–19
PROOF OF LEMMA 3.3
- The appendix proves uniqueness of the PDE solution satisfying the stated symmetry and boundary condition by showing its energy is identically zero.The resulting zero difference between any two solutions establishes uniqueness.Source: Appendix B · pp. 19–20
PROOF OF THEOREM 3.6
- α ≈ 1.358 gives the height-adaptive optimal initial window w⋆ = αλ.The appendix identifies α using the lower branch of the Lambert W function.Source: Appendix B · p. 21
PROOF OF THEOREM 3.8
- 5.901 is the optimal expected cost when w ≥ λ; this is lower than the minimum cost of approximately 7.42 for n0 ≥ 1.The optimum in the w ≥ λ regime occurs at c0 ≈ 0.3115.Source: Appendix B · p. 25
LEMMA B.3
- For lazy cached doubling with w ≥ λ, the expected slice cost is bounded below by 2 and above by 2 + 5 times the sum of the two edge-miss probabilities.When the initial window covers the slice, doubling uses exactly two evaluations; otherwise the proof bounds the expansion wait by a geometric variable.Source: Appendix B · p. 26
APPENDIX B: PROOFS
- f_lazy(x) ∼ -2 log x as x → 0 and ∼ (5/6)log2 x as x → ∞, while f_lazy(x) ≥ 7 for x ≤ 2^-4.Source: Appendix B · p. 32
- A numerical evaluation gives cost 5.92 at w = λ and places the minimum of f_lazy on [2^-4, 2^6].Source: Appendix B · p. 32
- Surrogate approximation bounds use asymptotic expansions outside a compact region, Lipschitz bounds within it, and fine-grid numerical checks; convexity and smoothness follow from second-derivative bounds.Source: Appendix B · p. 32
- The proofs certify proposed initial windows as (3,0)-optimal and (1,4)-optimal, and show efstep is (1,0)-optimal while efcache and eflazy are (1,0.7)-optimal.Source: Appendix B · p. 34
- Theorem 4.3’s proof controls dependence using geometric ergodicity, then combines order-statistic concentration, tightness, and continuity conditions to bound the cost with probability tending to one.The continuity conditions include contiguous slices and continuity of E[h(λ)|u].Source: Appendix B · pp. 37–39
APPENDIX C: PSEUDOCODE
The pseudocode implements a slice-sampling transition by finding an approximate slice, shrinking it to draw a new state, and tracking density evaluations and slice-bound information. The slice-finding options include stepping out, cached doubling, and lazy cached doubling.
Algorithm 1: SliceSampleStep
- A transition draws a slice value u and direction ρ, finds an approximate slice using window w(u), shrinks it to draw y, and returns the updated state and tracked bounds.The returned state is x + ρy.Source: Appendix C · p. 39
Bound tracking
- Eval records points inside the slice as inner bounds and stores outside points for later use in estimating the slice-edge bounds.GetBounds uses stored points to return the outer bounds together with the inner bounds.Source: Appendix C · p. 40
Slice-finding algorithms
- Stepping out expands the initial window in increments of w until the slice is bounded, while cached doubling repeatedly doubles the window and stores endpoint density values.The cached doubling procedure expands left or right and returns the resulting bounds, endpoint densities, and cache.Source: Appendix C · pp. 40–41
Shrinkage and acceptance
- Shrinkage repeatedly proposes a uniform point within the current interval, accepts valid proposals, and otherwise narrows the interval.The acceptance checks use cached values and boundary information to assess whether a proposal is valid.Source: Appendix C · pp. 41, 42, 44
Slice-finding algorithms
- Lazy cached doubling defers some endpoint evaluations during expansion, using cached or null values to decide whether to continue doubling.Its pseudocode returns the slice bounds, endpoint densities, and cache once both endpoints are below the slice value.Source: Appendix C · p. 43