3
$\begingroup$

Let $f:[0,1] \to [0,1]$ be a smooth, monotonically increasing function. I want to find the smallest $x$ such that $f(x) \ge 1/2$.

If I had a way to compute $f(x)$ given $x$, I could simply use binary search on $x$. However, I don't have a way to compute $f(x)$. Instead, I have a black box that, on input $x$, flips a biased coin and outputs 1 with probability $f(x)$ and 0 with probability $1-f(x)$. I can invoke the black box as many times as I want.

I'm looking for a query-efficient strategy to approximate $x^* = \min \{x : f(x) \ge 1/2\}$. Is there an efficient algorithm? I would be happy with strategies where we assume a fixed upper bound on $f'(x)$.

Informally, we can summarize the problem as: I have a coin whose heads probability depends in some unknown but monotonic way on a parameter; how can I choose the minimum value of that parameter to ensure the coin is biased in my favor?


A naive approach is to estimate $f(x)$ for any $x$ by invoking the black box $k$ times on the same input $x$, then use binary search with this estimator. However, I suspect this makes more queries than necessary. Intuitively, it makes many queries in regimes where $|x-1/2|$ is large, and the estimator for $f(x)$ doesn't use information from the black box on queries $x'$ that are near to $x$.

I suspect something like the following might be better, for some constant $1/2 < \alpha < 1$:

  1. Set $x := 1/2$ and $d := \alpha$.
  2. Repeat some fixed number of times:
    • Query the black box on $x$. If it returns 1, set $x := x + d$, otherwise set $x := x - d$.
    • Clip $x$ to the range $[0,1]$. Set $d := \alpha d$.

However I'm not sure how to set $\alpha$ or how to analyze this approach. (Note that if $\alpha=1/2$ and the black box returned whether or not $f(x)\ge 1/2$, this strategy would devolve to binary search.)

Is there a good way to choose $\alpha$? Or, is there a better strategy?

$\endgroup$
4
$\begingroup$

This is addressed in the following paper of Karp and Kleinberg:

Karp, Richard M.; Kleinberg, Robert. Noisy binary search and its applications. Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 881--890, ACM, New York, 2007.

You can find a copy on Kleinberg's website.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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