Random sampling from a super level set I have a random sampler from a region $X$. Suppose, I have a function $f: X \to \mathbb{R}$, where I can explicitly evaluate $f(x)$ and also obtain the gradient $\frac{\partial f}{\partial x}$ easily (I mean less computational time).
What I want is random sampler from a super level set $X_{>\tau}=\{x \in X | f(x) > \tau\}$. Is there any good algorithm to do this?
I'm currently doing this by sampling from $X$ and then accepts if $x \in X_{>\tau}$ and otherwise reject. The problem is volume of $X_{>\tau}$ is so tiny and takes a lot of time for sampling from this region.

It would help to know a bit more about $f$. For example, if you knew it was Lipschitz continuous, you could determine around each sample $x\notin X_{>\tau}$ a ball $B_x$ which would definitely be disjoint of $X_{>\tau}$, i.e. $B_x \cap X_{>\tau} = \emptyset$. And then you would only sample from $X\setminus \bigcap_{k=1}^K B_{x_k}$, where $x_k, k=1,\ldots, K$ are all the samples that did not happen to lie in $X_{>\tau}$.
