Gradient descent-like optimization on a convex landscape with noisy sampling

Question

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:

1. Alice provides Bob a point $s$ such that $|s-p_{min}|<r$.
2. Bob provides Alice a point $p$.
3. 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.

The copy of the question on MathOverflow.

Answer 1

The problem you describe is called "stochastic convex optimization in the bandit setting". This is the problem considered and solved here: http://arxiv.org/pdf/1107.1744v2.pdf

They show that after $k$ queries, you can get within $O(1/\sqrt{k})$ of the minimum value of the function (ignoring a poly$(d)$ dependence on the dimension $d$ of the domain of the function $f$).