AI Glossary / Probabilistic machine learning / Advanced
Adaptive rejection sampling
Definition
Adaptive rejection sampling, or ARS, draws from a target distribution by constructing and refining an upper envelope used for rejection sampling. The classical tangent-based method applies to univariate log-concave densities. It builds bounds on the log density, samples from an easily handled envelope, and accepts candidates using tests that preserve the target distribution rather than simply returning draws from an approximation.
What it means
Sometimes a probability density can be evaluated up to an unknown normalizing constant, yet sampling from it directly is inconvenient. Rejection sampling solves this by proposing candidates from a simpler distribution and accepting an appropriate fraction of them.
ARS improves the proposal as it learns more about the density. Its adaptation tightens the envelope instead of changing the distribution one wants to sample. The standard method's log-concavity requirement matters: a curve can be unimodal without being log-concave, so seeing one peak is not enough to justify the construction.
How it works
For a positive unnormalized density g, write h = log(g). Concavity makes tangents to h upper bounds, while chords between evaluated points provide lower bounds on the intervening intervals. Exponentiating produces a piecewise exponential upper envelope and an optional lower squeezing function.
A candidate is drawn from the normalized upper envelope. A uniform random number determines acceptance, first through the cheap lower bound if possible and otherwise through the evaluated target-to-envelope ratio. New evaluations can refine the bounds. Initialization must make the envelope integrable, including suitable tail slopes on unbounded domains.
For a fixed target, correctly implemented ARS can generate independent target draws. When used within Gibbs sampling, however, the sequence of joint states generally remains dependent.
Three practical examples
- A Bayesian analyst uses ARS for a scalar full conditional with a known log-concave form but no convenient direct sampler. The surrounding Gibbs algorithm still requires its own convergence assessment.
- An engineering researcher tests a custom one-dimensional density whose log density and derivative are available. ARS provides draws while avoiding explicit calculation of the target's normalizing constant.
- A software team benchmarks probability calculations against simulated values from a suitable reference density. It records envelope evaluations and acceptance counts to distinguish computational savings from changes in sample quality.
Think of it this way
Imagine fitting a roof above a curved hill and using random points under the roof to select locations under the hill. A closer roof leaves less empty space and wastes fewer proposals. The roof must remain above the entire hill: a very close-looking fit that dips below it can invalidate the sampling procedure.
Worked example
Consider the original teaching example g(x) = exp(−x²/2) on the real line. Its log density h(x) = −x²/2 is concave. Tangents at x = −1 and x = 1 are x + 0.5 and −x + 0.5. Their lower envelope is u(x) = 0.5 − |x|, which remains above h everywhere.
The envelope exp(u(x)) integrates to 2 exp(0.5), approximately 3.2974. The target integrates to sqrt(2 pi), approximately 2.5066. Therefore this initial envelope's overall acceptance probability is 2.5066/3.2974, approximately 0.7602. ARS itself does not need the target integral; it is available here to check the example.
At a candidate x = 0, the target-to-envelope ratio is exp(−0.5), approximately 0.6065. The chord between the two support points has value −0.5, giving a squeezing ratio exp(−1), approximately 0.3679. A uniform value 0.5 fails the squeeze but passes the full acceptance test. Failing the squeeze therefore does not mean rejecting the candidate.
Adding the evaluated point zero introduces the tangent h(0) = 0. The new upper hull is min(0, 0.5 − |x|), whose exponential integrates to 3. Its overall acceptance probability becomes approximately 0.8355. This is an exact mathematical comparison of two envelopes, not a measured software speedup.
Illustrative case study
Fictional modeling firm ScalarWorks wants to accelerate repeated conditional draws in a custom Bayesian program. A developer proposes ARS because plotted conditionals appear to have one peak. A reviewer checks the mathematical log densities and finds that this visual argument is insufficient.
The team applies the classical method only to conditionals for which the assumptions and envelope construction are justified. It tests tail handling and acceptance logic against densities with known properties, and continues monitoring the larger Gibbs run. This fictional case describes engineering checks; it does not report a real implementation or promise that ARS is the fastest available method.
Common misconceptions and mistakes
The upper envelope is a proposal device, not a replacement target. Returning every proposal would sample the envelope distribution and generally give the wrong answer. Similarly, a lower squeezing test can safely accept some candidates, but failure of that test calls for further evaluation rather than immediate rejection.
Another mistake is confusing ARS with adaptive rejection Metropolis sampling. Methods that add a Metropolis step have different applicability and dependence properties. Classical ARS should not be applied unchanged to an arbitrary non-log-concave density. Incorrect derivatives, unsupported tail bounds, and numerical overflow can also invalidate an otherwise sound mathematical design.
Business use
ARS can be useful inside specialized probabilistic software when suitable scalar distributions occur repeatedly and density evaluations are expensive. Assess total cost, including derivative calculations, initialization, and envelope maintenance. For an existing standard distribution, a direct sampler may already be simpler and faster. Preserve the mathematical justification and numerical checks with the implementation, and evaluate the precision of final business quantities rather than judging success solely by acceptance rate.
People also ask
Must the normalizing constant be known?
No; a consistently scaled unnormalized density is sufficient for the rejection comparisons.
Does adaptation make the result approximate?
The envelope is approximate, but valid rejection tests produce the target law in exact arithmetic. Numerical implementation still matters.
Does ARS make a Gibbs chain independent?
No. Each conditional draw can be exact while successive joint states remain dependent.
Check your understanding
Why do tangents provide an upper bound in the example?
Answer: The log density is concave.
What happens when the squeeze fails but the full test passes?
Answer: The candidate is accepted after evaluating the target.
Why did the tighter envelope improve acceptance?
Answer: It reduced envelope mass while preserving the same target mass and a valid upper bound.
Related terms
- Rejection sampling
- Gibbs sampling
- Monte Carlo simulation
- log-concavity
- envelope distribution
- squeezing function
- unnormalized density
- adaptive rejection Metropolis sampling
Learn next
Work through ordinary rejection sampling before studying tangent intersections and sampling from piecewise exponential distributions. Then examine how a conditional sampling method fits into a complete Gibbs algorithm.
More in Probabilistic machine learning
- Acyclic directed mixed graph - An acyclic directed mixed graph, or ADMG, contains directed edges such as X → Y and bidirected edges such as X ↔ Y, with no cycle made entirely of...
- Adaptive Markov chain Monte Carlo - Adaptive Markov chain Monte Carlo, or adaptive MCMC, changes aspects of a sampling algorithm using information gathered during its run.
- Adaptive resampling - Adaptive resampling, in sequential Monte Carlo and particle filtering, means deciding whether to resample a population of weighted particles using its...
- Advantage actor-critic - Advantage actor-critic is a reinforcement-learning approach in which an actor learns a policy and a critic helps estimate whether an action performed better...
- Alpha divergence - Alpha divergence is a parameterized family of measures for comparing probability distributions. Changing alpha changes how discrepancies are penalized.
- Amortized variational inference - Amortized variational inference learns a shared function that maps observations or other relevant context to parameters of approximate posterior distributions.
Sources
Gilks and Wild, Adaptive Rejection Sampling for Gibbs Sampling, 1992, original research paper: https://hedibert.org/wp-content/uploads/2013/12/1992GilksWild.pdf
Previous: Adaptive redaction Next: Adaptive resampling