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.

• By definition queries will be much less as BO is a derivative-free approach. But probably it makes more justice to restrict this question to two very specific algorithms. It is too generic, while BO and GD are family of algorithms. Jun 25, 2021 at 8:49

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.

• Let me give an example. Recently there's been development in differentiable simulation, where a complex physical simulator can run a (lengthy) simulation and returns the output and the gradient of the output w.r.t. the initial condition and input. One can use a grad descent algorithm to optimize the IC and input to minimize some cost function w.r.t. the output. But that could result in many simulation runs. So I think BO can be useful here (and the GP used for GP can incorporate the gradient). I'm interested in any results in the literature on the sample efficiency b/w BO & GD in such a case. Jun 26, 2021 at 18:04
• @Truong but as with comparing any optimization algorithms, the answer would be problem-specific. Even for solving simple, well-researched problems we don’t have definite answers like that. Moreover, as said above, Bayesian optimization pays more attention to exploration & approximate results vs GD tries going directly to minimum, so they have different priorities.
– Tim
Jun 26, 2021 at 18:25

I'm more an expert on the gradient descent side, but here's a couple thoughts.

Tim mentions that BO is approximating the function, but gradient descent does this as well, by framing it as an optimization problem: We approximate the function by minimizing the error in our approximation.

We now also have a host of sampling tricks to allow us to optimize the parameters of various distributions directly, a trend which IIUC started with variational autoencoders (the 'reparamaterization trick'). For example, we can model an arbitrary normal distribution as mu + sigma * N(0, 1), which allows us to keep the gradient for mu and sigma, where it's lost if we simply write N(mu, sigma). These sorts of tricks allow us to apply gradient descent in a lot of contexts where we couldn't ten years ago.

This /should/ let us abstract away the method for finding the parameters of the model and focus on the model itself. In theory, I shouldn't have to care whether the model was fit with GD or MCMC, though in practice I find MCMC to be fickle, difficult to reason about, and difficult to debug. (but I imagine there's a bunch of folks who say the same about GD.)