Optimizing black box functions without Bayesian Optimization

I have a black box system which accepts a data instance $\boldsymbol{x}$ and outputs a corresponding $y$. I don not know the exact mathematical formula of the system. What I want to do is maximizing $y$ by tweaking $\boldsymbol{x}$. Since I don't have the exact formula of the system, I cannot use gradient descent to do this. One idea in my mind is to add random noise to $\boldsymbol{x}$ which results in $\hat{\boldsymbol{x}}$, and then sample corresponding $\hat{y}$ from the system. By doing this I could use Bayesian Optimizaton to find an $\hat{\boldsymbol{x}}$ which maximizes $\hat{y}$.

My question is: Is there any other methods to tackle this problem? Can you point me out any paper/book/tutorial?

Thank you

• Some of the content of this thread will apply (admittedly most of it is about BO). stats.stackexchange.com/questions/193306/… – Sycorax Mar 14 '17 at 17:02
• @Sycorax Thank you very much! I will look at that answer. – MarsPlus Mar 14 '17 at 17:03
• Also, the dirt-simple approach of random search has some nice properties. I can't find the specific paper that compares it to BO, but such a paper does exist. If I find it, I'll post an answer. – Sycorax Mar 14 '17 at 17:09
• @Tavrock Thanks for your comment. Can you clarify what a uniform set of $x$ is? Does that mean I should add white gaussian noise to generate such $x$? – MarsPlus Mar 14 '17 at 17:11
• @Tavrock That's essentially what BO does, but it tries to choose the points $x$ a little more efficiently than just a uniform grid, since black box evaluations are often expensive. – Dougal Mar 14 '17 at 17:25