Consider an unknown function $f(x,y)$, where $x$ and $y$ are just two scalar numbers in $[0,1]$. $f(x,y)$ is an increasing function of $y$ and is between $0$ and $1$ but is unknown.

At each time I pick a value $y$ and process a value in a stream of $x$ numbers $x_i$, $i=1, 2, ...$ and need to find the minimum $y$ such that $f(x,y)>0.8$.

Is there any principled way to optimize the choices of $y$ assuming $x_i$s does not change fast?

It may be related more to the control theory, but I thought a solution similar to binary search may work:

Increase $y$ if $f(x,y)<0.8$ and decrease it if $f(x,y)>0.8$ using a step size. Now to ensure fast convergence double the step size if $f(A,B)$ does not change status and halve it if it passes $0.8$. The difference with one-sided binary search is that binary search will always halve the step after it passes the bound once, but here we don't do that as the $x$ values might change.

  • $\begingroup$ Is there an oracle letting you know whether $f(x,y) > 0.8$, where you can't control $x$ (though it changes slowly) but you can control $y$? Please make that clear. Otherwise, binary search seems like a good idea, though you're relying on the continuity of $f$ and hoping for the best. Also, what do you mean by "finding the minimum $y$ such that $f(x,y)>0.8$"? For what value of $x$? $\endgroup$ – Yuval Filmus Jan 21 '14 at 13:54
  • $\begingroup$ Yes, there is an oracle (black box) that tells me the output. I select y as one input, then the black box reads an x value and gives the output. I know that with y=1, f(x,y) will be >0.8 but it has costs so I want to minimize y while f(x,y) remains >0.8. $\endgroup$ – Masood_mj Jan 21 '14 at 17:55
  • $\begingroup$ I found a related paper that defines smoothness of f(x,y) and a gain function of y. For the case that f(x,y)<0.8 gain is 0 and for f(x,y)>=0.8 gain is 1-y. Then they propose MIMD solution for y. The paper is "A Randomized Online Algorithm for Bandwidth Utilization" form SANJEEV ARORA. But I don't understand why they don't do MIMD on the change step size instead of value y. $\endgroup$ – Masood_mj Jan 21 '14 at 17:58

Your Answer

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

Browse other questions tagged or ask your own question.