adaptive rejection sampling
(1.2 hours to learn)
Summary
Adaptive rejection sampling (ARS) is a technique used to automatically choose and refine an envelope distribution, q(z), for rejection sampling of distribution p(z). ARS initially forms an envelope distribution, q(z), as a piecewise combination of intersecting line segments that outline p(z). These line segments are the tangents of log(p(z)) evaluated along a set of initial grid points and are guaranteed to enclose p(z) if p(z) is log-concave (the derivative of log(p(z)) is nonincreasing) -- this property holds for a large number of distributions. ARS then proceeds like rejection sampling, though if a sampled point is rejected at point x* then the tangent of log(p(x*)) is added to the envelope distributions, which shrinks the proposal distribution around the true distribution and leads to fewer rejected samples later on.
Context
This concept has the prerequisites:
- rejection sampling
- exponential distribution (The proposal distribution is piecewise exponential.)
Goals
- Be able to implement the adaptive rejection sampling algorithm.
- What is the advantage compared to standard rejection sampling?
Core resources (read/watch one of the following)
-Free-
→ Adaptive Rejection Sampling for Gibbs Sampling
Location:
Section 2.2
Other notes:
- Section 2.2 provides core information but the rest of the Section 2 provides context and deeper discussion of ARS
-Paid-
→ Pattern Recognition and Machine Learning
A textbook for a graduate machine learning course, with a focus on Bayesian methods.
Location:
section 11.1.3
Supplemental resources (the following are optional, but you may find them useful)
-Free-
→ Wikipedia
See also
- Adaptive Metropolis rejection sampling is a generalization of ARS that is applicable when the distribution is not log-concave
- ARS can be performed by computing secants (rather than tangents) and thus a can be accomplished without computing the derivative of the log density; see Gilks, W. R. (1992) Derivative-free adaptive rejection sampling for Gibbs sampling. Bayesian Statistics 4,