Dirac Delta Function in Bayesian Optimization

Question

I am reading a paper on Bayesian optimization which aims at selecting the batch of points $x_0,x_1,..,x_k$ to sample to obtain maxima or minima of the GP. So the first batch element is normal acquisition function and optimizing the argmax will lead to first sampling element as follows:

$${x}_{1}= \textrm{argmax} \ \mathcal{\alpha} (\mathbf{x}; I_{0})$$ $ \mathcal{\alpha} (\mathbf{x}; I_{0})$ is just symbolic term for any acquisition function such as Expected Improvement, Probability of Improvement etc.

For second element of the batch we need to marginalize (integrate out previous element) as well as optimize (argmax for new element) as follows $${x}_{2}= \textrm{argmax} \int \mathcal{\alpha} (\mathbf{x}; I_{1})p(y_{1}|x_{1},I_0)p(x_{1}|I_0)dx_1dy_1$$ where, $ p(y_{1}|x_{1},I_0)$ is predictive distribution of the GP

$p(x_{1}|I_0)$ = $\delta (x_{1}-\textrm{argmax} \ \mathcal{\alpha} (\mathbf{x}; I_{0}))$

Similarly for the third element of the batch $x_3$ we need to marginalize the first two and optimize and for kth element marginalize all the previous k-1 and then optimize as shown by equation 2 in the attached paper.

---

Now as per the post here marginalization makes sense because we are using predictive distribution of the GP and when we predict the future point we need to account for uncertainty based on previous predictions. but what I dont understand is what is the role of the delta function here? This post provides intuition of using delta function but I still cant make a connection.

$$\delta (x_{1}-\textrm{argmax} \ \mathcal{\alpha} (\mathbf{x}; I_{0}))$$

Shouldn't the above expression evaluate to $\delta (0)$?

Answer 1

I believe the role of the dirac delta in the linked post is a way to frame optimisation of the hyperparameters in a Bayesian way; that is, so that marginalisation of the hyperparameters can be expressed using the same notation for both cases.

I'm going to try to put together a more notationally simple example than that in the linked question, but one which is still hopefully identical in practical terms.

---

Let's say we have a function, $f$, from which we have some samples, $x$, and corresponding responses, $y$, which together constitute some data, $\mathcal{D}$.

We opt to use some (arbitrary) model, $M$, that is parametrised by some hyperparameters, $\theta$, which in turn have some prior distribution, $\pi$.

Assuming we wish to make a prediction, $y^*$, at a new point, $x^*$, we could write the predictive distribution as follows:

$p(y^* | x^*, \mathcal{D}, \theta) = M(x^*|\mathcal{D}, \theta)$

But this is conditional on a specific value of $\theta$.

An alternative suggestion is to compute the distribution of $\theta$, and integrate it (that is, marginalise) over this distribution:

$p(y^* | x^*, \mathcal{D}) = \displaystyle\int_{\theta} M(x^*|\mathcal{D}, \theta) p(\theta | \mathcal{D}) d\theta$

This requires computation of the distribution $p(\theta | \mathcal{D})$, and this is where I believe the source of your confusion is:

In the case of MCMC, this distribution is approximated by drawing samples from a distribution proportional to $p(\theta|\mathcal{D})$.

An alternative strategy is to optimise $p(\mathcal{D}|\theta)$ as a function of $\theta$, thus summarising $p(\mathcal{D}|\theta)$ by a single point, $\theta^*$.

The dirac delta can be used here to describe this process as a "prior" (in scare quotes because as the linked answer details, it is not strictly a prior in the philosophical sense), such that the notation between both MCMC and optimisation is consistent: if $p(\theta|\mathcal{D})$ is described by the dirac delta function at $x^*$, one can perform the integration described above and arrive at the desired answer.

---

What is the role of the dirac delta for batch bayesian optimisation?

Unless I also misunderstand, I am struggling to identify one.

Marginalisation for batch allocation makes sense, as you suggest, but doing this via some kind of optimisation (which assumes the distribution of the thing you want to marginalise over is well summarised by it's mode), does not, which is where the dirac delta function would be used.

---

Addressing Batch Allocation

I am at least tangentially familiar with batch Bayesian optimisation, so I will try to offer an intuitive explanation. If this explanation doesn't help, you can consider posting it as part of another (!) question with an explanation of what is unclear and I'm sure someone will be able to help.

When performing batch Bayesian optimisation, we aim to select a series of $B$ points, $x_1, \dots, x_B$, which jointly maximise some measure of expected utility (the "acquisition function"), with $B$ being the batch size.

In order to pose this problem properly, the desired measure of utility needs some notion of "repulsion" between sample points. This tends to be accomplished in one of two ways:

1. By explicitly including some kind of "virtual" observation in the GP predictive distribution. Since the acquisition function is a function of the GP predictive distribution, this naturally encodes some notion of repulsion.
2. By imposing some kind of penalty function designed to imitate the effect of the above. Examples include the local penalisation method in the paper you linked (Gonzalez et. al.), and rather more complex methods such as repulsion simulated using determinantal point processes (Kathuria et. al.).

Now, let's say we were going to use a sequential strategy to choose a batch of points using method 1 (that is, introducing virtual observations to induce repulsion between our batch points). Assuming we have a GP model, the procedure looks something like this:

1. Maximise the acquisition function to find the point of highest utility. Let's call this $x'$.
2. Add $x'$ to our batch of points.
3. Update our GP model with a virtual observation for $y' = f(x')$, using the predictive distribution at $x'$.
4. (Temporarily) augment the GP with new data: $x'$ and $y'$. By temporarily I mean that this is not "real" data and can be forgotten after the batch points are selected.
5. Repeat 1 - 4 until $B$ points have been selected.

Now, item 3 presents a problem: $y'$, given our model, is uncertain, and subsequent steps clearly depend on the value we choose. One strategy is to repeat all subsequent steps a number of times to "marginalise" the uncertainty in $y'$. This is where I believe your questions regarding marginalisation come from.

This is unfortunately very expensive (due to repeat optimisation of the acquisition function with different virtual observations), which is why methods which model repulsion (rather than the posterior itself) are more common (at least as far as my understanding goes).

In fact, for even moderately large batch sizes, this method is intractably expensive -- even when exploiting quadrature to perform the marginalisation -- since the number of required optimisations grows exponentially with the batch size. A way of getting around this is to approach the problem in a rather more dynamic than sequential way, which is explored by Lam et. al. and Gonzalez et. al..