10

When and why use Bayesian optimization, instead of gradient descent?

Which one is better for which cases?

Sycorax
  • 76,417
  • 20
  • 189
  • 313
Mostafa
  • 205
  • 2
  • 6
  • 1
    Simple answer: when you want include prior information in your model. But of course there are also other answers. – Tim Jul 17 '15 at 10:26
  • 2
    @Tim: care to share them? – ocramz Jul 17 '15 at 10:54
  • @Mustafa, there are many possible interpretations of Bayesian optimization, one per author :D which one are you referring to? Also, as Tim says there should be a means to incorporate further information and a technically efficient way to perform large-size integrals, whereas gradient descent techniques are computationally lighter, once you know how to compute the gradient, that is. – ocramz Jul 17 '15 at 10:56

1 Answers1

17

I'm assuming that by Bayesian optimization you mean the standard method of fitting a Gaussian process or similar model to your observations, defining an acquisition function such as expected improvement or upper confidence bound, and querying the function at the maximum of that acquisition function.

The most immediate difference is that Bayesian optimization is applicable when you don't know the gradients. If you can cheaply compute gradients of your function, you'll want to use a method that can incorporate those, since they can be extremely helpful in understanding the function. If you can't easily compute gradients and need to resort to finite differences approximations, in most cases you really don't want to do that.

BO assumes that the function is fairly smooth (as defined by your kernel in the GP) but not convex. Gradient descent, if you want to find a global maximum, assumes convexity as well as some degree of smoothness (as used in the step size parameter).

BO tries to minimize the number of calls to the objective function. If it is expensive to calculate, e.g. because it requires a lot of computation or even some interaction with the outside world, this is highly desirable. If the objective is cheap to calculate, it may be faster to not bother with the amount of side computation needed.

BO typically does not scale well to high-dimensional functions, either statistically or computationally. Recent work has begun to address this issue, from various tacks. Gradient descent and similar methods often scale reasonably to higher dimensions, if you're careful.

BO also doesn't typically scale well to evaluating the function many times, since GP inference is cubic in the number of input points. There's been a lot of recent work on speeding up GPs or using similar more scalable methods, which may or may not address this problem for your needs.

Danica
  • 21,852
  • 1
  • 59
  • 115
  • 1
    By the objective function I mean the function $f$ that you’re trying to optimize (eg $\min_x f(x)$). BO schemes are generally used in the setting where $f$ is expensive to evaluate and so does a lot of computation to choose each new $x$ that it queries $f(x)$ for, while gradient descent does very little of this “side computation” to pick a new $x$. – Danica May 07 '19 at 20:15