Gradient descent-like optimization on a convex landscape with noisy sampling
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$).