  Bayesian Optimization is a sample-efficient black-box optimization procedure
that is typically applied to problems with a small number of independent
objectives. However, in practice we often wish to optimize objectives defined
over many correlated outcomes (or "tasks"). For example, scientists may want to
optimize the coverage of a cell tower network across a dense grid of locations.
Similarly, engineers may seek to balance the performance of a robot across
dozens of different environments via constrained or robust optimization.
However, the Gaussian Process (GP) models typically used as probabilistic
surrogates for multi-task Bayesian Optimization scale poorly with the number of
outcomes, greatly limiting applicability. We devise an efficient technique for
exact multi-task GP sampling that combines exploiting Kronecker structure in
the covariance matrices with Matheron's identity, allowing us to perform
Bayesian Optimization using exact multi-task GP models with tens of thousands
of correlated outputs. In doing so, we achieve substantial improvements in
sample efficiency compared to existing approaches that only model aggregate
functions of the outcomes. We demonstrate how this unlocks a new class of
applications for Bayesian Optimization across a range of tasks in science and
engineering, including optimizing interference patterns of an optical
interferometer with more than 65,000 outputs.
