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

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

CC BY-SA 3.0
2014-03-14T06:26:41.583Z
Thank you for pointing out this terrific paper.  What's your understanding as the importance of the noise assumptions in this paper?  It seems that the authors are assuming that the noise is subgaussian (i.e. that the kurtosis is negative)?
O1155
CC BY-SA 3.0
2014-03-14T06:37:38.557Z
I wonder what would happen in the case of having noise with positive kurtosis...
O1155
CC BY-SA 3.0
2014-09-26T11:16:43.223Z
It will probably work poorly for noise with positive kurtosis. The algorithm is based on probabilistic bounds for sub-gaussian noise (i.e with negative kurtosis), so I think it would have to be significantly modified to account for the "fat tails" found in noise with positive kurtosis. Note that normally distributed noise with expectation zero is sub-gaussian, so this should work fine in your case.
AMO
CC BY-SA 3.0
2014-03-14T00:51:59.797Z
2014-03-14T00:51:59.797Z
Aaron Roth
<p>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}^+$.  </p>

<p>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$.</p>

<p>We can think of the setting as a game with two players Alice and Bob as follows:</p>

<ol>
<li>Alice provides Bob a point $s$ such that $|s-p_{min}|&lt;r$.</li>
<li>Bob provides Alice a point $p$.  </li>
<li>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)$.</li>
</ol>

<p>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?</p>

<p>On average, how well can Bob do? </p>

<p>What would be the dependency of the error on $k$?</p>

<p>If it simplifies things, we can use uniform distribution $U[a,b]$ in place of Gaussian distribution for noise.</p>

<p><a href="https://mathoverflow.net/questions/159789/gradient-descent-like-optimization-on-a-convex-landscape-with-noisy-sampling">The copy of the question on MathOverflow.</a></p>

CC BY-SA 3.0
2014-03-12T07:27:30.483Z
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
CC BY-SA 3.0
2014-03-12T08:13:08.953Z
@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
CC BY-SA 3.0
2014-03-12T08:40:55.740Z
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
CC BY-SA 3.0
2014-03-12T08:46:57.810Z
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
CC BY-SA 3.0
2014-03-12T08:56:53.570Z
@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
<approximation-algorithms><optimization><convex-optimization>
Gradient descent-like optimization on a convex landscape with noisy sampling
O1155
# Gradient descent-like optimization on a convex landscape with noisy sampling

(Asked by: username_0 on 2014-03-12)

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}|- 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.

[The copy of the question on MathOverflow.](https://mathoverflow.net/questions/159789/gradient-descent-like-optimization-on-a-convex-landscape-with-noisy-sampling)

**Tags:** approximation-algorithms, optimization, convex-optimization

> **Comments:**
> **username_1**: 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?  
> **username_0**: @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.  
> **username_1**: 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.  
> **username_2**: 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".  
> **username_0**: @username_2 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.  

---

## 1 answers

### Answer by username_3 on 2014-03-14. Score: 5 | Accepted answer

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

> **Comments:**
> **username_0**: Thank you for pointing out this terrific paper.  What's your understanding as the importance of the noise assumptions in this paper?  It seems that the authors are assuming that the noise is subgaussian (i.e. that the kurtosis is negative)?  
> **username_0**: I wonder what would happen in the case of having noise with positive kurtosis...  
> **username_4**: It will probably work poorly for noise with positive kurtosis. The algorithm is based on probabilistic bounds for sub-gaussian noise (i.e with negative kurtosis), so I think it would have to be significantly modified to account for the "fat tails" found in noise with positive kurtosis. Note that normally distributed noise with expectation zero is sub-gaussian, so this should work fine in your case.  

---

