Bayesian Optimization vs. gradient descent I don't know if this is the right place to ask this question. If you think this question is better asked in another StackExchange, please point me to that.
This question is about the sampling efficiency of Bayesian Optimization (BO) vs. Gradient descent (GD) (or an accelerated version of it like Nesterov's AGD). Says $f(x)$ is an unknown function (could be convex as a special case), differentiable. Its gradient $\nabla f(x)$ is available, however evaluating $f(x)$ and its gradient by an "oracle" is expensive. I want to minimize $f(x)$ with no constraints. Typically I will use GD/AGD to minimize it to a certain accuracy from an initial $x_0$, resulting in a number $N_{GD}$ of queries to the oracle (the number of evaluations of $f$ and $\nabla f$).
I can also use BO to achieve the same. Since the gradient is available, I assume that the derivative information can be incorporated into the GP for BO (GP with derivative observations / information) to improve the learning. The BO algorithm needs a number $N_{BO}$ of queries to the oracle to achieve the same accuracy from the same initial $x_0$ as GD.
My question is: is there any result (like a theorem) in the literature regarding the sampling efficiency between BO and GD/AGD in this scenario or similar scenarios? By that I mean whether and in what conditions we have the guarantee that $N_{BO} < N_{GD}$, and how much smaller.
 A: Such comparison wouldn't make much sense, because those algorithms serve different purposes. Gradient descent is one of many algorithms that directly optimizes a function. Bayesian optimization, on another hand, approximates the optimized function and uses the approximation to suggest parameter values that should you explore. Next, you evaluate the function on the suggested point to learn what is the actual value of the function at this point. Each time you evaluate the function and record the result, this information is used to update and improve your approximation, so it can propose the next value to explore. This is illustrated in the gif below that shows Thompson sampling using Gaussian process to approximate the optimized function. As you can see, the function guessed by the algorithm (blue), differs from the true function (red), hence it doesn't optimize it directly. You can find code and some other examples in this Julia notebook I created.

You may wonder why do we use Bayesian optimization to approximate the optimized function, rather than doing it directly? This is where the algorithms serve different purposes. If your function is cheap to evaluate, you would optimize it directly. On another hand, if it is expensive to evaluate, you would use Bayesian optimization. To give an example, let's say you need to tune hyperparameters of a deep neural network that needs 12 hours to train. If you used gradient descent with 5000 steps, it would take thousands of hours to obtain the result. Bayesian optimization makes educated guesses when exploring, so the result is less precise, but it needs fewer iterations to reasonably explore the possible values of the parameters.
Gradient descent is fast because by optimizing the function directly. Bayesian optimization is fast by making good educated guesses to guide the optimization. They are however solving different problems and are fast in doing slightly different things, so it is a kind of comparing apples to oranges. Moreover, Bayesian optimization is more computationally costly as compared to algorithms like gradient descent, so if the optimized function is even more expensive, the cost is worth it, otherwise, it would add unnecessary overhead.
