Thread by @TivadarDanka

What if you want to optimize a function, but every evaluation costs you $100 and takes a day to execute?

Algorithms like gradient descent build on two key assumptions:

• function is differentiable,
• and you can calculate it on demand.

What if this is not the case?

🧵 👇🏽

For example, you want to tune the hyperparameters of a model that requires 24 hours of GPU time to train.

Can you find a good enough value under reasonable time and budget?

One method is the so-called Bayesian optimization.

Essentially, the method works as follows.

1️⃣ Model the expensive function with a Gaussian process.

Gaussian processes are easy to compute and offer a way to quantify uncertainty in the predictions.

2️⃣ Estimate the information gain of evaluating the function at each unknown value.

3️⃣ Evaluate the function where this gain is maximal. Go back to the first step until the budget is exhausted.

The process looks simple enough.

There are multiple ways to estimate the potential information gain, but we will take a look at the simplest: the probability of improvement.

The formula looks scary, so let me explain!

First, μ(𝑥) and σ(𝑥) are the mean and variance of the Gaussian process used to estimate our unknown function 𝑓.

Our currently known best optimum is at 𝑥⁺. We wish to improve this.

Finally, ψ(𝑥) is the cumulative distribution function for a standard Gaussian distribution.

How do they add up?

Let's start from the outside in. We want to maximize the probability of improvement.

For this, we estimate the improvement with what is on the inside, then put it into the CDF of a Gaussian distribution with mean 0 and variance 1.

(Note that from an optimization perspective, ψ(𝑥) can be omitted, since it is increasing. Though, from a theoretical perspective, it is important.)

On the inside, we calculate that for a given unknown value 𝑥, how much is our estimated improvement, based on the Gaussian process modeling our knowledge.

μ(𝑥) is what we think the function looks like, 𝑓(𝑥⁺) is the current optimum.

So, μ(𝑥) - 𝑓(𝑥⁺) is the improvement.

Since our knowledge about 𝑓 is very incomplete, we have to take uncertainties into account.

This is where the σ(𝑥) in the denominator comes into play: it expresses the uncertainty.

The lower it is, the more we can trust that μ(𝑥) - 𝑓(𝑥⁺) estimates improvement well.

The last piece of the puzzle is the parameter ξ in the numerator.

It encourages Bayesian estimation to experiment and explore new areas where our Gaussian process doesn't necessarily predict an improvement.

ξ is called the tradeoff between exploration and exploitation.

Without ξ, the Bayesian optimization process would be stuck in the same area, exploring a single local optimum.

This is suboptimal because our incomplete information based on a few known values of the function can introduce a severe bias to the process.

This is how a few queries look like.

On the top, you can see the function to be optimized and the Gaussian process. On the bottom, the probability of improvement is shown at each step.

Of course, these are just the very fundamentals of the topic. If you are interested in more, here is an awesome introductory article by Eric Brochu, Vlad M. Cora, and Nando de Freitas!

arxiv.org/abs/1012.2599