# Is there a technique where we keep the proposal in Adaptive Rejection Sampling?

As I understand, the proposal distribution, which I'll call $h(x)$, in adaptive rejection sampling is a linear piece-wise function which converges to the true distribution as the number of iterations goes to infinity.

As I understand, in general, adaptive rejection sampling involves using the data sampled to perform inference on the distribution of interest, which I'll call $f(x)$. It would seem that since $h(x)$ converges to $f(x)$, it might, in certain circumstances, make sense to treat the proposal as an analytical approximation of our true distribution, after some large number of sampling iterations.

Because $h(x)$ is piece-wise linear, integrating it to get its normalizing constant should be easy, after which we essentially have an analytical representation of our distribution $f(x)$.

To put it another way, does anyone tune adaptive rejection sampling in order to change the proposal distribution as quickly as possible and, after a certain number of iterations, throw away the data and treat $h(x)$ as an approximation of $f(x)$?

Is this a technique used? If so, could you give me its name? And if not, could anyone explain why?

## 1 Answer

As I understand, the proposal distribution, which I'll call h(x), in adaptive rejection sampling is a linear piece-wise function which converges to the true distribution as time goes to infinity.

No, in adaptive rejection sampling the $\log$ of the envelope distribution is piecewise linear (and the squeeze function also).

To put it another way, does anyone tune adaptive rejection sampling in order to change the proposal distribution as quickly as possible and, after a certain number of iterations, through away the data and treat h(x) as their approximation of f(x)?

Not typically (at least not that I know of); the point of Gilks and Wild's adaptive rejection sampling algorithm is always to sample exactly from a target distribution via accept-reject, but to get better at it (more efficient) with each rejection.

One could of course stop at some point and say "my envelope is close enough, I'll just accept any proposal from now" but usually there's no need to do this.

1. For example, when using it in Gibbs sampling, once you accept a value, your next sample won't be from the same conditional distribution; long before you have a very good approximation, you've accepted and moved on. (In simple cases, like some fairly-well-behaved bivariate problems, you might be able to split the joint distribution up into strips and develop envelope and squeeze functions for the strip as a whole, so that the information is kept across iterations of the sampler, but in general you won't do this)

2. Outside of something like Gibbs sampling, you can use adaptive rejection in a straight accept-reject context and build up better and better approximations as you go, but generally there's little reason to stop improving it, since the additional cost to continue sampling from the exact distribution isn't very great.

And if not, could anyone explain why?

Primarily because you're no longer sampling exactly from $f$. It may not be clear, but adaptive rejection gives you samples exactly from $f$ without actually evaluating it anywhere but your proposal values*. Typically when using it one wants samples from $f$ rather than an approximation. One could stop updating the envelope (and squeeze) of course and still use plain accept-reject from there, but it's typically used when function evaluations are expensive compared to the cost of updating the approximation.

* (well the tangent version of the algorithm also evaluates the derivative of $\log f$ at those values)

In short - yes, you could do this (use the envelope as an approximation for $f$), but there's probably not much call for it.

(I vaguely seem to recall that I may have used something like this once - the tangent version, not the secant one - to get bounds on the integral of $f$, though the problem was pretty well behaved and I think perhaps we ended up just approximating the integral via standard numerical quadrature ideas and not worrying about the bounds. It wasn't important though because if I remember right there were several reasonable ways to do what we needed.)

I should add that there's also an adaptive rejection sampler suitable for situations where you don't have log-concavity, but have a unimodal density -- if you know where the mode is (you don't need to know the height of the density there as long as you can bound it); the idea seems to be due to Radford Neal (I don't think he's published it, but he does mention it online somewhere -- though I didn't know that when I later came up with essentially the same approach myself). Similar comments would apply to this one -- there's little reason to stop updating it either.

• I would add that ARS is not such a practical success because (a) it is unidimensional and (b) it requires a few attempts before the first simulation is produced which makes it costly in Gibbs situations where a single simulation is produced before moving to another target. Dec 7 '15 at 21:44
• @Glen_b: Thanks for your answer. That all makes sense. Dec 7 '15 at 21:58