3
$\begingroup$

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.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
0
$\begingroup$

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}$.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thanks for your answer. In my situation $X$ is not continuous, so ball cannot be defined ... $\endgroup$
    – orematasaburo
    Commented Oct 15, 2022 at 8:00
  • $\begingroup$ @orematasaburo How do you then define the gradient $\frac{\partial f}{\partial x}$? $\endgroup$
    – frank
    Commented Oct 15, 2022 at 9:03
  • $\begingroup$ I'm sorry. I was wrong. $X$ is continuous. Creating a union of ball is interesting idea. Problem is $X$ is 1600 dimensional space. So, covering the region by balls seems to be intractable $\endgroup$
    – orematasaburo
    Commented Oct 16, 2022 at 12:56
0
$\begingroup$

Nested sampling is an algorithm based on simulations from the prior over level sets $$\{x;\ f(x)>f(x_0)\}$$where $f$ stands for the likelihood. The way the constraint is implemented is via a Markov chain Monte Carlo algorithm that starts from $x_0$ and makes a uniform proposal in the vicinity of $x_0$, &tc.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.