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

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.

• Is the noise persistent? Is it correlated between points? i.e. if I give the same coordinate twice (or with a negligible perturbation), do I get the same result? – R B Mar 12 '14 at 7:27
• @RB No, the noise is not persistent according to the model here. Each "sampling event" can be understood as drawing an iid random variable from the stated Gaussian distribution. – O1155 Mar 12 '14 at 8:13
• Then you can use multiple samplings for each gradient iteration, thereby reducing the noise till its small (w.r.t. $f$) and then do a gradient step. – R B Mar 12 '14 at 8:40
• I edited the question to make it easier to understand what is going on. Please check to make sure I haven't introduced errors. ps: I am not sure what you mean by "on average". – Kaveh Mar 12 '14 at 8:46
• @Kaveh Yes, the rewrite appears accurate (still looking it over, it's quite late here), and actually I quite like it. Saying "On average how well can we do?" in the original posting was sloppy, and the comment asking about the mean error (or a probability distribution for the error) should suffice. – O1155 Mar 12 '14 at 8:56

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$).