###### tags: `one-offs` `rejection sampling`

# Univariate Log-Concave Rejection Sampling is Solved

**Overview**: In this note, I describe some results of Luc Devroye on rejection sampling from log-concave densities in dimension one. I also comment on some more recent results which show that Devroye's construction is essentially optimal.

## Prelude

Today, I stumbled upon a paper of Luc Devroye entitled "Random variate generation for the generalized inverse gaussian distribution" (link [here](http://luc.devroye.org/Devroye-RNG-GIG-2012.pdf). Despite the title giving a fairly narrow impression of its scope, the paper actually contains a very nice result which is much more general, essentially tackling the problem of log-concave rejection sampling in one dimension. I have since found out that this particular result is contained in earlier work of Devroye, though I do not know an appropriate earliest reference.

## The Result

The solution is essentially as follows: with a well-chosen piecewise-log-linear envelope to the target, using only three pieces, once can obtain a good acceptance rate. The construction is actually remarkably simple: first, find the mode of the density. Then, looking to either side of the mode, find points at which the density is reduced by a constant factor (say $\mathrm{e}^{-1}$), relative to the density at the mode. Draw tangents to the log-density at these three points, and use these to form a piecewise-log-linear upper envelope to the target. Optimising this "constant factor" can be done agnostically to the target, and gives a good method, in the sense that $\mathbf{P}\left(\mathrm{accept}\right)\geqslant1-\mathrm{e}^{-1}>0$, for **any** log-concave density in one dimension.

## Some Recent Advances

A recent work of Chewi and coauthors studies the complexity of this algorithm in the setting of well-conditioned log-concave targets. The extra work for their positive result is to show that under these assumptions, one can find these 'points of lower density' efficiently. They also use a slightly different envelope, which instead has Gaussian tails, though I suspect that this is not strictly necessary for controlling the acceptance rate. For the matching negative result, they also show complexity lower bounds, verifying that this method is rate-optimal.

## Conclusion

For me, this says that if a sampling problem is reducible to a sampling from a one-dimensional log-concave probability measure, then the problem can be solved simply and efficiently. It is not a surprising result, but it is nice to know what problems can safely be internalised as 'solved', and this result essentially accomplishes that.