Let $p_{1}, \ldots, p_{N}$ be a collection of points in $\mathbb{R}^{n}$. I would like to sample uniformly from the convex hull of these $N$ points in an `efficienct' way. In my setting, I have $n$ moderate (e.g. $n \approx 500$) but $N$ very large (e.g. $N \approx 2^{n^{2}}$).

I am aware that there is a great deal of work by Lovasz et. al. on using hit-and-run algorithms for doing this type of sampling. Unfortunately, to my knowledge that algorithm is impractical in my setting: when $N$ is very large compared to $n$, the cost of running the algorithm is dominated by the (large) cost of finding the boundaries of the convex body along a slice. In particular, this work suggests that around $n^{3}$ steps of a Markov chain are required to get a single good sample, but each step still seems to require at least $N$ operations.

I do have one advantage in this setting: I can sample a random element of $p_{1}, \ldots, p_{N}$ quite quickly (e.g. in time $O(\log(N))$. I thought that perhaps a "nonreversible" hit-and-run sampler might be possible, but so far don't have anything particularly general in that direction.

Thanks for any help!