adaptive rejection sampling
(1.2 hours to learn)
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.
This concept has the prerequisites:
- rejection sampling
- exponential distribution (The proposal distribution is piecewise exponential.)
- 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)
→ Adaptive Rejection Sampling for Gibbs Sampling
Location: Section 2.2
- Section 2.2 provides core information but the rest of the Section 2 provides context and deeper discussion of ARS
→ 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)
- 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,
- create concept: shift + click on graph
- change concept title: shift + click on existing concept
- link together concepts: shift + click drag from one concept to another
- remove concept from graph: click on concept then press delete/backspace
- add associated content to concept: click the small circle that appears on the node when hovering over it
- other actions: use the icons in the upper right corner to optimize the graph placement, preview the graph, or download a json representation