This is a rewrite of the original positing (below), and is crossposted to (https://cstheory.stackexchange.com/questions/21496/gradient-descent-like-optimization-on-a-convex-landscape-with-noisy-sampling):

I have a strictly convex function $f(x,y)$, i.e. something like $f(\theta,\phi) \approx t_1 Sin[\theta] + t_2 Sin[\phi]$ (where $(\theta,\phi) \in [0,\pi]$ and $(t_1,t_2) \in \mathbb{R}^+$), with a global minimum at some $h_{min}=(x_{min},y_{min})$.

We now play a kind of guessing game where you provide me some $h^*$ on a plane that is guaranteed to be within a distance $R$ of $h_{min}$, and I provide you with a coordinate $c_i = (x_i,y_i)$ that corresponds to a "guess" for the value of $h_{min}$. You then provide me the value $j_i = f(x_i,y_i) + q_i$ where $q_i \in \mathbb{R}$ corresponds to Gaussian noise drawn from a distribution with parameters $(\mu_n,\sigma_n)$, e.g. we could have $(\mu_n,\sigma_n) = (0,1)$. If it simplifies things, I suppose we could instead draw $q_i$ from some uniform distribution s.t. $q_i \in [A,B]$.

If you only allow me to perform $k$ guesses: what is my optimal strategy for guessing a set of coordinates $(c_1, c_2, ..., c_k)$ s.t. $c_k$ minimizes $\delta = (h_{min} - c_k)$? On average, how well can I do? Provided this optimal strategy, can we write down something like a probability distribution for $\delta$ as a function of $k$?

Original posting:

I have a bivariate Gaussian distribution $f(x,y)$ with mean $\mu$, covariance matrix $M$, and square roots of the eigenvalues of the covariance matrix $(\sigma_1,\sigma_2)$. We now play a kind of guessing game where you provide me some $\mu^*$ on a plane that is guaranteed to be within a distance $R$ of $\mu$, and I provide you with a coordinate $c_i = (x_i,y_i)$ that corresponds to a "guess" for the value of $\mu$. You then provide me the value $j_i = f(x_i,y_i) + q_i$ where $q_i \in \mathbb{R}$ corresponds to Gaussian noise drawn from a distribution with parameters $(\mu_n,\sigma_n)$, e.g. we could have $(\mu_n,\sigma_n) = (0,1)$. If it simplifies things, I suppose we could instead draw $q_i$ from some uniform distribution s.t. $q_i \in [A,B]$.

If you only allow me to perform $k$ guesses: what is my optimal strategy for guessing a set of coordinates $(c_1, c_2, ..., c_k)$ s.t. $c_k$ minimizes $\delta = (\mu - c_k)$? On average, how well can I do? Provided this optimal strategy, can we write down something like a probability distribution for $\delta$ as a function of $k$?

Update -- I understand that the bivariate Gaussian distribution $f(x,y)$ is not a convex function, so perhaps I shouldn't be using the "convex-optimization" tag, though this feels most relevant to this problem. That said, I would be happy to recast $f(x,y)$ as a convex or strictly convex function and ask the same question above, with the hope that convex optimization methods can be relevant and helpful.

Update 2 -- To simplify things, let's specifically call $f(x,y)$ a strictly convex function, i.e. something like $f(\theta,\phi) \approx c_1 Sin[\theta] + c_2 Sin[\phi]$ where $(\theta,\phi) \in [0,\pi]$ and $(c_1,c_2) \in \mathbb{R}^+$. The question now is, what is the best gradient descent-like strategy provided a strictly convex landscape with the aforementioned sampling noise, and how well can we do with this algorithm after some number of steps (guesses) $k$?