We have a strictly convex function $f(x,y)$ with a global minimum at $p_{min}$. The goal is to approximate the minimum. E.g. $$f: [0,\pi]^2 \to \mathbb{R}$$ $$f(\theta,\phi) = t_1 \sin \theta + t_2 \sin \phi$$ where $t_1,t_2$ are constants in $\mathbb{R}^+$.
We want to find the best possible approximation for the minimum $p_{min}$, but we only have noisy black-box access to the function $f$.
We can think of the setting as a game with two players Alice and Bob as follows:
- Alice provides Bob a point $s$ such that $|s-p_{min}|<r$.
- Bob provides Alice a point $p$.
- Alice provides Bob information about the value of the function on $p$. However, the information is noisy: Bob gets $v \sim f(p) + N(\mu,\sigma)$.
If Bob can pick $k$ points adoptively, what would be an optimal strategy for choosing the points s.t. the last one is as close as possible to the minimum?
On average, how well can Bob do?
What would be the dependency of the error on $k$?
If it simplifies things, we can use uniform distribution $U[a,b]$ in place of Gaussian distribution for noise.