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.

  • $\begingroup$ 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? $\endgroup$
    – R B
    Mar 12, 2014 at 7:27
  • $\begingroup$ @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. $\endgroup$
    – O1155
    Mar 12, 2014 at 8:13
  • 1
    $\begingroup$ 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. $\endgroup$
    – R B
    Mar 12, 2014 at 8:40
  • $\begingroup$ 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". $\endgroup$
    – Kaveh
    Mar 12, 2014 at 8:46
  • $\begingroup$ @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. $\endgroup$
    – O1155
    Mar 12, 2014 at 8:56

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

  • $\begingroup$ 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)? $\endgroup$
    – O1155
    Mar 14, 2014 at 6:26
  • $\begingroup$ I wonder what would happen in the case of having noise with positive kurtosis... $\endgroup$
    – O1155
    Mar 14, 2014 at 6:37
  • $\begingroup$ 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. $\endgroup$
    – AMO
    Sep 26, 2014 at 11:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.