Sampling from the joint when computing qNoisyExpectedHypervolumeImprovement

[exs-hkenlay]

In the forward of qNoisyExpectedHypervolumeImprovement, the input X of shape num_samples, q, d is concatenated to X_baseline of shape num_baseline_points, d to give X_full of shape num_samples, q + num_baseline_points, d. The docstring has the following:

# Note: it is important to compute the full posterior over `(X_baseline, X)`
# to ensure that we properly sample `f(X)` from the joint distribution `
# `f(X_baseline, X) ~ P(f | D)` given that we can already fixed the sampled
# function values for `f(X_baseline)`.
# TODO: improve efficiency by not recomputing baseline-baseline
# covariance matrix.

I'm not sure I fully understand the last bit of the note (given that we can already fixed the sampled function values for f(X_baseline)), wouldn't this justify not recomputing f(X_baseline)?

For inductive methods such a BNNs the concatenation step seems unnecessary and computationally expensive if for example X_baseline is the training set (particularly when sequential=True). Would it be possible/sensible to add a compute_joint = True parameter to the __init__ so this concatenation can be turned off? I'd be happy to make an Issue and PR. Or perhaps this should be handled inside the Model class?

[saitcakmak]

@sdaulton Can you take a look at this?

[Balandat]

I'm not sure I fully understand the last bit of the note (given that we can already fixed the sampled function values for f(X_baseline)), wouldn't this justify not recomputing f(X_baseline)?

First of all, apologies for the messed up docstring ("given that we can already fixed").

So the main point here is that in order to properly account for the covariance between the new X points and X_baseline points, we need to use the full posterior for drawing samples. So here we compute the covariance across the set of points (X_train, X_baseline, X). Since X_train and X_baseline don't change between iterations (but X does), we potentially are wasting a lot of compute by re-computing the covariance across the points (X_train, X_baseline) every time. The comment "# TODO: improve efficiency by not recomputing baseline-baseline covariance matrix." reminds us to improve things here by caching that upper left 2 x 2 block of the full 3 x 3 block matrix.

given that we can already fixed the sampled function values for `f(X_baseline)

I am not actually sure I understand this myself. I think this may be referring to the setting where the base_samples are fixed. But it may happen that as the size of X changes these get redraws. So I think without some additional work / assumptions we may not just simply cache the function samples (but we could cache potentially large parts of the covariance matrix as I mentioned above).

[exs-hkenlay]

Thank you @Balandat for explaining, conceptually it makes complete sense. In the code where does X_train get concatenated?

Do you have any thoughts on the final paragraph of my post? I think the solution would just be changing the first line of forward to

if self.compute_joint:
    X_full = torch.cat([match_batch_shape(self.X_baseline, X), X], dim=-2)
else:
    X_full = X

[saitcakmak]

In the code where does X_train get concatenated?

That would typically happen in GPyTorch while computing the model posterior.

I think the solution would just be changing the first line of forward to

Could you achieve the same effect by setting X_baseline to an empty (i.e., 0 x d-dim) tensor?

[SebastianAment]

For inductive methods such a BNNs the concatenation step seems unnecessary

Could you elaborate on this? Is it the case that it is much more efficient for a BNN to carry out inference over the entire batch of points at once?

(particularly when sequential=True)

An important point to note is that the hypervolume computations in q(Noisy)ExpectedHypervolumeImprovement scale exponentially with q if sequential=False, whereas it scales polynomially with q if sequential=True, see the associated publication for details.

If you you need a multi-objective acquisition function that scales well without sequential optimization, I'd recommend a scalarization-based approach (see e.g. BoTorch's get_chebyshev_scalarization).

Please note that qNEHVI with sequential = True allows you to scale to larger q while maintaining good sample-efficiency, even though it might be computationally more expensive for your inference procedure.

[exs-hkenlay]

Thank you both for your response.

Could you achieve the same effect by setting X_baseline to an empty (i.e., 0 x d-dim) tensor?

This is what I initially tried, but I think it changes how the acquisition function scores inputs. For example if your task had two non-negative output objectives that you wanted to maximise and the training set and baseline was a single point with label (1, 2), then the acquisition function will prefer a point mapping to (2, 1) over one mapping to (1, 2) (desirable behaviour), whereas without a baseline both points would be considered to have the same hyper-volume improvement (assuming a reference point of (0, 0)).

Could you elaborate on this? Is it the case that it is much more efficient for a BNN to carry out inference over the entire batch of points at once?

Yes sorry I could have written this more clear, let me try and explain with an example. If we have X_baseline of shape (9, d) which represent 9 points of dimension d. Assume we already have access to the ground truth label of these points, and we've done inference to find our BNN weight distribution. Because we know these points, we want to improve hyper-volume relative to these points so we set X_baseline in the acquisition function. If sequential=True then X passed into the forward is of shape B x 1 x d and X_full will be of shape B x 10 x d. Unlike GPs, the samples X_full[:, :9, :] (from X_baseline) have no influence on X_full[:, 9, :] (the points we're computing acquisition values for). A reasonable BNN implementation would pass all num_samples x 10 inputs through the network, resulting in 10x more computation than is needed. To address your second question, BNNs are more efficient in the sense that predicting the distribution of a new point does not scale with the number of training points like with GPs.

An important point to note is that the hypervolume computations in q(Noisy)ExpectedHypervolumeImprovement scale exponentially with q if sequential=False, whereas it scales polynomially with q if sequential=True, see the associated publication for details.

If you you need a multi-objective acquisition function that scales well without sequential optimization, I'd recommend a scalarization-based approach (see e.g. BoTorch's get_chebyshev_scalarization).

Please note that qNEHVI with sequential = True allows you to scale to larger q while maintaining good sample-efficiency, even though it might be computationally more expensive for your inference procedure.

Thank you for the information. I've benchmarked qNEHVI for values of q and m I'm interested in (always using sequential=True), and its fast enough for my use case. The benchmarking reflects the wall-clock times shown in Figure 2 of the paper. I'm also experimenting for qNParEGO, but would like to experiment with qNEHVI too.