# PACOH: Bayes-Optimal Meta-Learning with PAC-Guarantees

Jonas Rothfuss  Vincent Fortuin  Martin Josifoski  Andreas Krause

###### Abstract

Meta-learning can successfully acquire useful inductive biases from data. Yet,
its generalization properties to unseen learning tasks are poorly understood.
Particularly if the number of meta-training tasks is small, this raises
concerns about overfitting. We provide a theoretical analysis using the PAC-
Bayesian framework and derive novel generalization bounds for meta-learning.
Using these bounds, we develop a class of PAC-optimal meta-learning algorithms
with performance guarantees and a principled meta-level regularization. Unlike
previous PAC-Bayesian meta-learners, our method results in a standard
stochastic optimization problem which can be solved efficiently and scales
well. When instantiating our PAC-optimal hyper-posterior (PACOH) with Gaussian
processes and Bayesian Neural Networks as base learners, the resulting methods
yield state-of-the-art performance, both in terms of predictive accuracy and
the quality of uncertainty estimates. Thanks to their principled treatment of
uncertainty, our meta-learners can also be successfully employed for
sequential decision problems.

Machine Learning, ICML, Meta-Learning, Transfer Learning, Multi-task learning,
PAC-Bayes, Learning Theory, Life-Long learning

##  1 Introduction

_Meta-learning_ aims to extract prior knowledge from data, accelerating the
learning process for new learning tasks (Thrun & Pratt, 1998). Most existing
meta-learning approaches focus on situations where the number of tasks is
large (e.g., Finn et al., 2017; Garnelo et al., 2018). In many practical
settings, however, the number of tasks available for meta-training is rather
small. In those settings, there is a risk of overfitting to the meta-training
tasks (meta-overfitting, cf. Qin et al., 2018), thus impairing the performance
on yet unseen target tasks. Hence, a key challenge is how to regularize the
meta-learner to ensure its generalization to unseen tasks.

Figure 1: Overview of the described meta-learning framework with hyper-prior
$\mathcal{P}$, hyper-posterior $\mathcal{Q}$, target prior $P$ and target
posterior $Q$. The data-generating process in our setup is described by a
meta-learning environment $\mathcal{T}$, meta-train task distributions
$\mathcal{D}_{i}$, target task distribution $\mathcal{D}$, data sets $S$ and
data points $z=(x,y)$.

The PAC-Bayesian framework provides a rigorous way to reason about the
generalization performance of learners (McAllester, 1999). However, initial
PAC-Bayesian analyses of meta-learners (Pentina & Lampert, 2014; Amit & Meir,
2018) only consider bounded loss functions, which precludes important
applications such as regression or probabilistic inference, where losses are
typically unbounded. More crucially, they rely on a challenging nested
optimization problem, which is computationally much more expensive than
standard meta-learning approaches.

To overcome these issues, we derive the first PAC-Bayesian bound for meta-
learners with unbounded loss functions. For Bayesian learners, we further
tighten our PAC-Bayesian bounds, relating them directly to the marginal log-
likelihood of the Bayesian model and thus avoiding the reliance on nested
optimization. This allows us to derive the PAC-optimal hyper-posterior
(PACOH), which promises strong performance guarantees and a principled meta-
level regularization. Importantly, it can be approximated using standard
variational methods (Blei et al., 2016), giving rise to a range of scalable
meta-learning algorithms.

In our experiments, we instantiate our framework with Gaussian Processes (GPs)
and Bayesian Neural Networks (BNNs) as base learners. Across several
regression and classification environments, our proposed approach achieves
state-of-the-art predictive accuracy, while also improving the calibration of
the uncertainty estimates. Further, we demonstrate that PACOH effectively
alleviates the meta-overfitting problem, allowing us to successfully extract
inductive bias from as little as five tasks while reliably reasoning about the
learner’s epistemic uncertainty. Thanks to these properties, PACOH can also be
employed in a broad range of sequential decision problems, which we showcase
through a real-world Bayesian optimization task concerning the development of
vaccines.

##  2 Related Work

Meta-learning.  A range of methods in meta-learning attempt to learn the
“learning program” in form of a recurrent model (Hochreiter et al., 2001;
Andrychowicz et al., 2016; Chen et al., 2017), learn an embedding space shared
across tasks (Snell et al., 2017; Vinyals et al., 2016) or the initialization
of a NN so it can be quickly adapted to new tasks (Finn et al., 2017; Nichol
et al., 2018; Rothfuss et al., 2019b). A group of recent methods also use
probabilistic modeling to enable uncertainty quantification (Kim et al., 2018;
Finn et al., 2018; Garnelo et al., 2018). Though the mentioned approaches are
able to learn complex inference patterns, they rely on settings where meta-
training tasks are abundant and fall short of performance guarantees. While
the risk of meta-overfitting has previously been noted (Qin et al., 2018;
Fortuin & Rätsch, 2019; Yin et al., 2020), it still lacks a rigorous formal
analysis under realistic assumptions (e.g., unbounded loss functions).
Addressing this issue, we study the generalization properties of meta-learners
within the PAC-Bayesian framework, and, based on that, contribute a novel
meta-learning approach with principled meta-level regularization.

PAC-Bayesian theory.  Previous work presents generalization bounds for
randomized predictors, assuming a prior to be given exogenously (McAllester,
1999; Catoni, 2007; Germain et al., 2016; Alquier et al., 2016). Further work
explores data-dependent priors (Parrado-Hernandez et al., 2012; Dziugaite &
Roy, 2016) or extends previous bounds to the scenario where priors are meta-
learned (Pentina & Lampert, 2014; Amit & Meir, 2018). However, these meta-
generalization bounds are hard to optimize as they leave both the hyper-
posterior and posterior unspecified, which leads to difficult nested
optimization problems. In contrast, our bounds also hold for unbounded losses
and yield a tractable meta-learning objective without the reliance on nested
optimization.

##  3 Background: PAC-Bayesian Framework

Preliminaries and notation. A learning task is characterized by an unknown
data distribution $\mathcal{D}$ over a domain $\mathcal{Z}$ from which we are
given a set of $m$ observations $S=\left\\{z_{i}\right\\}_{i=1}^{m}$,
$z_{i}\sim\mathcal{D}$. By $S\sim\mathcal{D}^{m}$ we denote the i.i.d.
sampling of $m$ data points. In supervised learning, we typically consider
pairs $z_{i}=(x_{i},y_{i})$, where $x_{i}\in\mathcal{X}$ are observed input
features and $y_{i}\in\mathcal{Y}$ are target labels. Given a sample $S$, our
goal is to find a hypothesis $h\in\mathcal{H}$, typically a function
$h:\mathcal{X}\rightarrow\mathcal{Y}$ in some hypothesis space $\mathcal{H}$,
that enables us to make predictions for new inputs $x^{*}\sim\mathcal{D}_{x}$.
The quality of the predictions is measured by a loss function
$l:\mathcal{H}\times\mathcal{Z}\rightarrow\mathbb{R}$. Accordingly, we want to
minimize the expected error under the data distribution, that is,
$\mathcal{L}(h,\mathcal{D})=\mathbb{E}_{z^{*}\sim\mathcal{D}}\;l(h,z^{*})$.
Since $\mathcal{D}$ is unknown, we typically use the empirical error
$\hat{\mathcal{L}}(h,S)=\frac{1}{m}\sum_{i=1}^{m}l(h,z_{i})$ instead.

In the PAC-Bayesian framework, we consider randomized predictors, i.e.,
probability measures on the hypothesis space $\mathcal{H}$. This allows us to
reason about the predictor’s (epistemic) uncertainty, resulting from the fact
that only a finite number of data points are available for training. We
consider two such probability measures, the _prior_
$P\in\mathcal{M}(\mathcal{H})$ and the _posterior_
$Q\in\mathcal{M}(\mathcal{H})$. Here, $\mathcal{M}(\mathcal{H})$ denotes the
set of all probability measures on $\mathcal{H}$. While in Bayesian inference,
the prior and posterior are tightly connected through Bayes’ theorem, the PAC-
Bayesian framework makes fewer assumptions and only requires the prior to be
independent of the observed data (Guedj, 2019). In the following, we assume
that the Kullback-Leibler (KL) divergence $D_{KL}\left(Q\|P\right)$ exists.
Based on the error definitions above, we can define the so-called _Gibbs
error_ for a randomized predictor $Q$ as
$\mathcal{L}(Q,\mathcal{D})=\mathbb{E}_{h\sim Q}\;\mathcal{L}(h,\mathcal{D})$
and its empirical counterpart as $\hat{\mathcal{L}}(Q,S)=\mathbb{E}_{h\sim
Q}\;\hat{\mathcal{L}}(h,S)$.

PAC-Bayesian bounds. In practice, $\mathcal{L}(Q,\mathcal{D})$ is unknown.
Thus, one typically resorts to minimizing $\hat{\mathcal{L}}(Q,S)$ instead.
However, this may result in overfitting and poor generalization. Naturally,
the question arises whether we can bound the unknown generalization error
based on its empirical estimate. The PAC-Bayesian theory provides such a
guarantee:

######  Theorem 1.

(Alquier et al., 2016) Given a data distribution $\mathcal{D}$, hypothesis
space $\mathcal{H}$, loss function $l(h,z)$, prior $P$, confidence level
$\delta\in(0,1]$, and $\beta>0$, with probability at least $1-\delta$ over
samples $S\sim\mathcal{D}^{m}$, we have for all
$Q\in\mathcal{M}(\mathcal{H})$:

$\vspace{-2pt}\mathcal{L}(Q,\mathcal{D})\leq\hat{\mathcal{L}}(Q,S)+\frac{1}{\beta}\left[D_{KL}(Q||P)+\ln\frac{1}{\delta}+\Psi(\beta,m)\right]\vspace{3pt}$
(1)

with
$\Psi(\beta,m)=\ln\mathbb{E}_{P}\mathbb{E}_{\mathcal{D}^{m}}\exp\left[\beta\left(\mathcal{L}(h,\mathcal{D})-\hat{\mathcal{L}}(h,S)\right)\right]$

Here, $\Psi(\beta,m)$ is a log moment generating function that quantifies how
much the empirical error deviates from the Gibbs error. By making additional
assumptions about the loss function $l$, we can bound $\Psi(\beta,m)$ and
thereby obtain tractable bounds. For instance, if $l(h,z)$ is _bounded_ in
$[a,b]$, we can use Hoeffding’s lemma to obtain
$\Psi(\beta,m)\leq(\beta^{2}(b-a)^{2})/(8m)$. For unbounded loss functions,
one commonly assumes that their moments are bounded. In particular, a loss
function $l$ is considered _sub-gamma_ with variance factor $s^{2}$ and scale
parameter $c$, under a prior $\pi$ and data distribution $\mathcal{D}$, if it
can be described by a sub-gamma random variable
$V:=\mathcal{L}(h,\mathcal{D})-l(h,z)$. That is, its moment generating
function is upper-bounded by that of a Gamma distribution $\Gamma(s,c)$. For
details see Boucheron et al. (2013) and Germain et al. (2016). We can use the
sub-gamma assumption to obtain
$\Psi(\beta,m)\leq(\beta^{2}s^{2})/(2m(1-\frac{c\beta}{m}))$.

Connections between the PAC-Bayesian framework and Bayesian inference.
Typically, we are interested in a posterior distribution $Q$ that promises us
the lowest generalization error. In this sense, it seems natural to use the
$Q\in\mathcal{M}(\mathcal{H})$ that minimizes the bound in (1). Lemma 1 gives
us the closed-form solution to such a minimization problem:

######  Lemma 1.

(Catoni, 2007) Let $\mathcal{H}$ be a set,
$g:\mathcal{H}\rightarrow\mathbb{R}$ a (loss) function, and
$Q\in\mathcal{M}(\mathcal{H})$ and $P\in\mathcal{M}(\mathcal{H})$ probability
densities over $\mathcal{H}$. Then, for any $\beta>0$ and $h\in\mathcal{H}$,

$Q^{*}(h):=\frac{P(h)e^{-\beta g(h)}}{Z_{\beta}}=\frac{P(h)e^{-\beta
g(h)}}{\mathbb{E}_{h\sim P}\left[e^{-\beta g(h)}\right]}\vspace{-2pt}$ (2)

is the minimizing probability density of

$\operatorname*{arg\,min}_{Q\in\mathcal{M}(\mathcal{H})}~{}\beta\mathbb{E}_{h\sim
Q}\left[g(h)\right]+D_{KL}(Q||P)\;.\vspace{-2pt}$ (3)

The respective minimizing distribution is known as _optimal Gibbs posterior_
$Q^{*}$ (Catoni, 2007; Lever et al., 2013). As a direct consequence of Lemma
1, for fixed $P,S,m,\delta$, we can write the minimizer of (1) as

$Q^{*}(h)=P(h)e^{-\beta\hat{\mathcal{L}}(h,S)}/Z_{\beta}(S,P)\vspace{-2pt}$

where
$Z_{\beta}(S,P)=\int_{\mathcal{H}}P(h)e^{-\beta\hat{\mathcal{L}}(h,S)}dh$ is a
normalization constant. In a probabilistic setting, we typically use the
negative log-likelihood of the data as our loss function $l(\cdot)$, that is,
$l(h,z_{i}):=-\log p(z_{i}|h)$. In this case, the optimal Gibbs posterior
coincides with the _generalized Bayesian posterior_
$Q^{*}(h;P,S)=\frac{P(h)\,p(S\,|\,h)^{\beta/m}}{Z_{\beta}(S,P)}$ where
$Z_{\beta}(S,P)=\int_{\mathcal{H}}P(h)\left(\prod_{j=1}^{m}p(z_{j}|h)\right)^{\beta/m}\,dh$
is called the _generalized marginal likelihood_ of the sample $S$ (Guedj,
2019). For $\beta=m$ we recover the standard Bayesian posterior.

##  4 PAC-Bayesian Bounds for Meta-Learning

We now present our main theoretical contributions. The corresponding proofs
can be found in Appendix A. An overview of our proposed framework is depicted
in Figure 1.

Meta-Learning. In the standard learning setup (Sec. 3), we assumed that the
learner has prior knowledge in the form of a prior distribution $P$. When the
learner faces a new task, it uses the evidence in the form of a dataset $S$,
to update the prior into a posterior $Q$. We formalize such a _base learner_
$Q(S,P)$ as a mapping
$Q:\mathcal{Z}^{m}\times\mathcal{M}(\mathcal{H})\rightarrow\mathcal{M}(\mathcal{H})$
that takes in a dataset and prior and outputs a posterior.

In contrast, in meta-learning we aim to acquire such a prior $P$ in a data-
driven manner, that is, by consulting a set of $n$ statistically related
learning tasks $\\{\tau_{1},...,\tau_{n}\\}$. We follow the setup of Baxter
(2000) in which all tasks $\tau_{i}:=(\mathcal{D}_{i},S_{i})$ share the same
data domain $\mathcal{Z}:=\mathcal{X}\times\mathcal{Y}$, hypothesis space
$\mathcal{H}$ and loss function $l(h,z)$, but may differ in their (unknown)
data distributions $\mathcal{D}_{i}$ and the number of points $m_{i}$ in the
corresponding dataset $S_{i}\sim\mathcal{D}_{i}^{m_{i}}$. To simplify our
exposition, we assume w.l.o.g. that $m=m_{i}~{}\forall i$. Furthermore, each
task $\tau_{i}\sim\mathcal{T}$ is drawn i.i.d. from an _environment_
$\mathcal{T}$, a probability distribution over data distributions and
datasets. The goal is to extract knowledge from the observed datasets, which
can then be used as a prior for learning on new target tasks
$\tau\sim\mathcal{T}$. To extend the PAC-Bayesian analysis to the meta-
learning setting, we again consider the notion of probability distributions
over hypotheses. While the object of learning has previously been a hypothesis
$h\in\mathcal{H}$, it is now the prior distribution
$P\in\mathcal{M}(\mathcal{H})$. The meta-learner presumes a hyper-prior
$\mathcal{P}\in\mathcal{M}(\mathcal{M}(\mathcal{H}))$, that is, a distribution
over priors $P$. Combining the hyper-prior $\mathcal{P}$ with the datasets
$S_{1},...,S_{n}$ from multiple tasks, the meta-learner then outputs a hyper-
posterior $\mathcal{Q}$ over priors. Accordingly, the hyper-posterior’s
performance is measured via the expected Gibbs error when sampling priors $P$
from $\mathcal{Q}$ and applying the base learner, the so-called _transfer-
error:_

$\vspace{-2pt}\mathcal{L}(\mathcal{Q},\mathcal{T}):=\mathbb{E}_{P\sim\mathcal{Q}}\left[\mathbb{E}_{(\mathcal{D},m)\sim\mathcal{T}}\left[\mathbb{E}_{S\sim\mathcal{D}^{m}}\left[\mathcal{L}(Q(S,P),\mathcal{D})\right]\right]\right]$

While the transfer error is unknown in practice, we can estimate it using the
_empirical multi-task error_

$\vspace{-2pt}\hat{\mathcal{L}}(\mathcal{Q},S_{1},...,S_{n}):=\mathbb{E}_{P\sim\mathcal{Q}}\left[\frac{1}{n}\sum_{i=1}^{n}\hat{\mathcal{L}}\left(Q(S_{i},P),S_{i}\right)\right]\;.$

PAC-Bayesian meta-learning bounds. We now present our first main result: An
upper bound on the true transfer error $\mathcal{L}(\mathcal{Q},\mathcal{T})$,
in terms of the empirical multi-task error
$\hat{\mathcal{L}}(\mathcal{Q},S_{1},...,S_{n})$ plus several tractable
complexity terms.

######  Theorem 2.

Let
$Q:\mathcal{Z}^{m}\times\mathcal{M}(\mathcal{H})\rightarrow\mathcal{M}(\mathcal{H})$
be a base learner, $\mathcal{P}\in\mathcal{M}(\mathcal{M}(\mathcal{H}))$ some
fixed hyper-prior $\mathcal{P}$ and $\lambda,\beta>0$. For any confidence
level $\delta\in(0,1]$ the inequality

$\displaystyle\begin{split}\mathcal{L}(\mathcal{Q},\mathcal{T})\leq&~{}\hat{\mathcal{L}}(\mathcal{Q},S_{1},...,S_{n})+\left(\frac{1}{\lambda}+\frac{1}{n\beta}\right)D_{KL}(\mathcal{Q}||\mathcal{P})\\\
&+\frac{1}{n}\sum_{i=1}^{n}\frac{1}{\beta}\mathbb{E}_{P\sim\mathcal{Q}}\left[D_{KL}(Q(S_{i},P)||P)\right]\\\
&+C(\delta,\lambda,\beta)\end{split}$ (4)

holds uniformly over all hyper-posteriors
$\mathcal{Q}\in\mathcal{M}(\mathcal{M}(\mathcal{H}))$ with probability
$1-\delta$. If the loss function is bounded, that is,
$l:\mathcal{H}\times\mathcal{Z}\rightarrow[a,b]$, the above inequality holds
for
$C(\delta,\lambda,\beta)=\left(\frac{\lambda}{8n}+\frac{\beta}{8m}\right)(b-a)^{2}+\frac{1}{\sqrt{n}}\ln\frac{1}{\delta}$.
If the loss function is sub-gamma with variance factor $s_{\text{{I}}}^{2}$
and scale parameter $c_{\text{{I}}}$ for the data distributions
$\mathcal{D}_{i}$ and $s_{\text{{II}}}^{2}$, $c_{\text{{II}}}$ for the task
distribution $\cal{T}$, the inequality holds with
$C(\delta,\lambda,\beta)=\frac{\lambda
s_{\text{{II}}}^{2}}{2n(1-(c_{\text{{II}}}\lambda)/n)}+\frac{\beta
s_{\text{{I}}}^{2}}{2m(1-(c_{\text{{I}}}\beta)/m)}+\frac{1}{\sqrt{n}}\ln\frac{1}{\delta}$.

The proof of Theorem 2 consists of three main steps (see Appx. A.1). First, we
bound the base learner’s expected generalization error for each task when
given a prior $P\sim\mathcal{Q}$ and $m_{i}$ data samples (i.e., the error
caused by observing only a finite number of samples per task). Second, we
bound the generalization gap on the meta-level which is due to the fact that
the meta-learning only receives finitely many tasks $\tau_{i}$ from
$\mathcal{T}$. In these two steps, we employ the change of measure inequality
(Lemma 2) to obtain an upper bound of the generalization error in terms of the
empirical error, the KL-divergence and a cumulant-generating function. In the
final step, we use either use the bounded loss or sub-gamma assumption,
together with Markov’s inequality, to bound the cumulant-generating function
with high probability, giving rise to $C(\delta,\lambda,\beta)$.

For bounded losses, Theorem 2 provides a structurally similar, but tighter
bound than Pentina & Lampert (2014). In particular, by using an improved proof
technique, we are able to avoid a union bound argument, allowing us to reduce
the negative influence of the confidence parameter $\delta$. Unlike in the
bound of Amit & Meir (2018), the contribution of the KL-complexity term
$D_{KL}(\mathcal{Q}||\mathcal{P})$ vanishes as $n\rightarrow\infty$. As a
result, we find that the bound in Theorem 2 is much tighter than (Amit & Meir,
2018) for most practical instantiations. In contrast to Pentina & Lampert
(2014) and Amit & Meir (2018), our theorem also provides guarantees for
_unbounded_ loss functions under moment constraints (see Appendix A.1 for
details). This makes Theorem 2 particularly useful for probabilistic models in
which the loss function coincides with the inherently unbounded negative log-
likelihood.

Common choices for $\lambda$ and $\beta$ are either a) $\lambda=\sqrt{n}$,
$\beta=\sqrt{m}$ or b) $\lambda=n$, $\beta=m$ (Germain et al., 2016). Choice
a) yields consistent bounds, meaning that the gap between the transfer error
and the bound vanishes as $n,m\rightarrow\infty$. In case of b), the bound
always maintains a gap since $C(\delta,n,m)$ does not converge to zero.
However, the KL terms decay faster, which can be advantageous for smaller
sample sizes. For instance, despite their lack of consistency, sub-gamma
bounds with $\beta=m$ have been shown to be much tighter in simple Bayesian
linear regression scenarios with limited data ($m\lesssim 10^{4}$) (Germain et
al., 2016).

Previous work (Pentina & Lampert, 2014; Amit & Meir, 2018) proposes meta-
learning algorithms that minimize uniform meta-generalization bounds like the
one in Theorem 2. However, in practice, the posterior $Q(S,P)$ is often
intractable and thus the solution of a numerical optimization problem, like
variational inference in case of BNNs. Hence, minimizing the bound in (4)
turns into a difficult two-level optimization problem which becomes nearly
infeasible to solve for rich hypothesis spaces such as neural networks.

While Theorem 2 holds for any base learner $Q(S,P)$, we would preferably want
to use a base learner that gives us optimal performance guarantees. As
discussed in Sec. 3, the Gibbs posterior not only minimizes PAC-Bayesian error
bounds, but also generalizes the Bayesian posterior. Assuming a Gibbs
posterior as base learner, the bound in (4) can be restated in terms of the
partition function $Z_{\beta}(S_{i},P)$:

######  Corollary 1.

When choosing a Gibbs posterior $Q^{*}(S_{i},P)\\\
:=P(h)\exp(-\beta\hat{\mathcal{L}}(S_{i},h))/Z_{\beta}(S_{i},P)$ as a base
learner, under the same assumptions as in Theorem 2, we have

$\displaystyle\begin{split}\mathcal{L}(\mathcal{Q},\mathcal{T})&\leq~{}-\frac{1}{n}\sum_{i=1}^{n}\frac{1}{\beta}\mathbb{E}_{P\sim\mathcal{Q}}\left[\ln
Z_{\beta}(S_{i},P)\right]\\\
&+\left(\frac{1}{\lambda}+\frac{1}{n\beta}\right)D_{KL}(\mathcal{Q}||\mathcal{P})+C(\delta,\lambda,\beta)\;.\vspace{-2pt}\end{split}$
(5)

with probability at least $1-\delta$.

Since this bound assumes a _PAC-optimal base learner_ , it is tighter than the
bound in (4), which holds for any (potentially sub-optimal)
$Q\in\mathcal{M}(\mathcal{H})$. More importantly, (5) avoids the explicit
dependence on $Q(S,P)$, turning the previously mentioned two-level
optimization problem into a standard stochastic optimization problem.
Moreover, if we choose the negative log-likelihood as the loss function and
$\lambda=n,\beta_{i}=m_{i}$, then $\ln Z_{\beta}(S_{i},P)$ coincides with the
marginal log-likelihood, which is tractable for various popular learning
models, such as Gaussian processes.

The bound in Corollary 1 consists of the expected generalized marginal log-
likelihood under the hyper-posterior $\mathcal{Q}$ as well as the KL-
divergence term, which serves as a regularizer on the meta-level. As the
number of training tasks $n$ grows, the relative weighting of the KL term
shrinks. This is consistent with the general notion that regularization should
be strong if only little data is available and vanish asymptotically as
$n,m\rightarrow\infty$.

Meta-Learning the hyper-posterior. A natural way to obtain a PAC-Bayesian
meta-learning algorithm could be to minimize the bound in Corollary 1 w.r.t.
$\mathcal{Q}$. However, we can even derive the closed-form solution of such
PAC-Bayesian meta-learning problem, that is, the minimizing hyper-posterior
$\mathcal{Q}^{*}$. For that, we exploit once more the insight that the
minimizer of (5) can be written as a Gibbs distribution (cf. Lemma 1), giving
us the following result:

######  Proposition 1.

(PAC-Optimal Hyper-Posterior) Given a hyper-prior $\mathcal{P}$ and datasets
$S_{1},...,S_{n}$, the hyper-posterior minimizing the meta-learning bound in
(5) is given by

$\mathcal{Q}^{*}(P)=\frac{\mathcal{P}(P)\exp\left(\frac{\lambda}{n\beta+\lambda}\sum_{i=1}^{n}\ln
Z_{\beta}(S_{i},P)\right)}{Z^{\text{{II}}}(S_{1},...,S_{n},\mathcal{P})}$ (6)

with
$Z^{\text{{II}}}=\mathbb{E}_{P\sim\mathcal{P}}\left[\exp\left(\frac{\lambda}{n\beta+\lambda}\sum_{i=1}^{n}\ln
Z_{\beta}(S_{i},P)\right)\right]\;.$

This gives us a tractable expression for the PACOH $\mathcal{Q}^{*}(P)$ up to
the (level-II) partition function $Z^{\text{{II}}}$, which is constant with
respect to $P$. We refer to $\mathcal{Q}^{*}$ as PAC-optimal, as it provides
the best possible meta-generalization guarantees among all meta-learners in
the sense of Theorem 2.

##  5 Meta-Learning using the PACOH

After having introduced the closed-form solution of the PAC-Bayesian meta-
learning problem in Sec. 4, we now discuss how to translate the _PACOH_ into a
practical meta-learning algorithm when employing GPs and BNNs as base
learners.

###  5.1 Approximating the PACOH

Given the hyper-prior and (level-I) log-partition function $\ln Z(S_{i},P)$,
we can compute the PACOH $\mathcal{Q}^{*}$ up to the normalization constant
$Z^{\text{{II}}}$. Such a setup lends itself to approximate inference methods
(Blei et al., 2016). In particular, we employ _Stein Variational Gradient
Descent (SVGD)_ (Liu & Wang, 2016) which approximates $\mathcal{Q}^{*}$ as a
set of particles
$\hat{\mathcal{Q}}=\\{P_{\phi_{1}},...,P_{\phi_{K}}\\}$111Note that any other
approximate inference can be employed instead. We chose SVGD as we found it to
work best in practice.. Here, $P_{\phi}$ denotes a prior with parameters
$\phi$. Alg. 1 summarizes the resulting generic meta-learning procedure.
Initially, we sample $K$ particles $\phi_{k}\sim\mathcal{P}$ from the hyper-
posterior. For notational brevity, we stack the particles into a
$K\times\text{dim}(\phi)$ matrix $\bm{\phi}:=[\phi_{1},...,\phi_{K}]^{\top}$.
Then, in each iteration, we estimate the score of $\mathcal{Q}^{*}$,

$\displaystyle\nabla_{\phi_{k}}\ln\mathcal{Q}^{*}(\phi_{k})=\nabla_{\phi_{k}}\ln\mathcal{P}(\phi_{k})+\frac{\lambda}{n\beta+\lambda}\sum_{i=1}^{n}\nabla_{\phi_{k}}\ln
Z_{i,k}\vspace{-2pt}$

wherein $\ln Z_{i,k}=\ln Z_{\beta}(S_{i},P_{\phi_{k}})$, and update the
particle matrix using the SVGD update rule:

$\bm{\phi}\leftarrow\bm{\phi}+\eta~{}\mathbf{K}~{}\nabla_{\bm{\phi}}\mathbf{ln}\tilde{\mathcal{Q}}^{*}+\nabla_{\bm{\phi}}\mathbf{K}\;;\vspace{-2pt}$
(7)

where
$\nabla_{\bm{\phi}}\mathbf{ln}\tilde{\mathcal{Q}}^{*}:=[\nabla_{\phi_{1}}\ln\mathcal{Q}^{*}(\phi_{1}),...,\nabla_{\phi_{K}}\ln\mathcal{Q}^{*}(\phi_{K})]^{\top}$
denotes the matrix of stacked score gradients,
$\mathbf{K}:=[k(\phi_{k},\phi_{k^{\prime}})]_{k,k^{\prime}}$ the kernel matrix
induced by a kernel function $k(\cdot,\cdot)$ and $\eta$ the step size for the
SVGD updates.

To this point, how to parametrize the prior $P_{\phi}$ and how to estimate the
generalized marginal log-likelihood $\ln Z_{i,k}=\ln
Z_{\beta}(S_{i},P_{\phi_{k}})$ (MLL_Estimator) in Alg. 1 have remained
unspecified. In the following two subsections, we discuss these components in
more detail for GPs and BNNs.

Algorithm 1 PACOH with SVGD approximation of $\mathcal{Q}^{*}$

Input: hyper-prior $\mathcal{P}$, datasets $S_{1},...,S_{n}$

Input: SVGD kernel function $k(\cdot,\cdot)$, step size $\eta$

$\bm{\phi}:=[\phi_{1},...,\phi_{K}]\text{ , with }\phi_{k}\sim\mathcal{P}$ //
init prior particles

while not converged do

for $k=1,...,K$ do

for $i=1,...,n$ do

$\ln Z_{i,k}\leftarrow$ MLL_Estimator$(S_{i},\phi_{k},\beta)$

$\nabla_{\phi_{k}}\ln\tilde{\mathcal{Q}}^{*}\leftarrow\nabla_{\phi_{k}}\ln\mathcal{P}+\frac{\lambda}{\lambda+n\beta}\sum_{i=1}^{n}\nabla_{\phi_{k}}\ln
Z_{i,k}$

$\bm{\phi}\leftarrow\bm{\phi}+\eta~{}\mathbf{K}~{}\nabla_{\bm{\phi}}\mathbf{ln}\tilde{\mathcal{Q}}^{*}+\nabla_{\bm{\phi}}\mathbf{K}$
// SVGD update

Output: set of priors $\\{P_{\phi_{1}},...,P_{\phi_{K}}\\}$

###  5.2 Meta-Learning Gaussian Process Priors

Setup. In GP regression, each data point corresponds to a tuple
$z_{i,j}=(x_{i,j},y_{i,j})$. For the $i$-th dataset, we write
$S_{i}=(\mathbf{X}_{i},\mathbf{y}_{i})$, where
$\mathbf{X}_{i}=(x_{i,1},...,x_{i,m_{i}})^{\top}$ and
$\mathbf{y}_{i}=(y_{i,1},...,y_{i,m_{i}})^{\top}$. GPs are a Bayesian method
in which the prior
$P_{\phi}(h)=\mathcal{GP}\left(h|m_{\phi}(x),k_{\phi}(x,x^{\prime})\right)$ is
specified by a kernel
$k_{\phi}:\mathcal{X}\times\mathcal{X}\rightarrow\mathbb{R}$ and a mean
function $m_{\phi}:\mathcal{X}\rightarrow\mathbb{R}$. Similar to Wilson et al.
(2016) and Fortuin & Rätsch (2019), we instantiate $m_{\phi}$ and $k_{\phi}$
as neural networks, and aim to meta-learn the parameter vector $\phi$.
Moreover, we use $\lambda=n$, $\beta=m$, the negative log-likelihood as loss
function and a Gaussian hyper-prior
$\mathcal{P}=\mathcal{N}(0,\sigma^{2}_{\mathcal{P}}I)$ over the GP prior
parameters $\phi$.

Algorithm. In our setup, $\ln Z_{m}(S_{i},P_{\phi})=\ln
p(\mathbf{y}_{i}|\mathbf{X}_{i},\phi)$ is the marginal log-likelihood of the
GP which is available in closed form. In particular, the MLL_Estimator is
given by (48) in Appx. B. Thus, the score
$\nabla_{\phi}\ln\mathcal{Q}^{*}(\phi)$ is tractable, allowing us to perform
SVGD efficiently. Alg. 2 in Appx. D summarizes the proposed meta-learning
method which we refer to as _PACOH-GP_.

###  5.3 Meta-Learning Bayesian Neural Network Priors

Setup. Let $h_{\theta}:\mathcal{X}\rightarrow\mathcal{Y}$ be a function
parametrized by a neural network (NN) with weights $\theta\in\Theta$. Using
the NN mapping, we define a conditional distribution $p(y|x,\theta)$. For
regression, we may set
$p(y|x,\theta)=\mathcal{N}(y|h_{\theta}(x),\sigma^{2})$, where $\sigma^{2}$ is
the observation noise variance. We treat $\ln\sigma$ as a learnable parameter
similar to the neural network weights $\theta$ so that a hypothesis coincides
with a tuple $h=(\theta,\ln\sigma)$. For classification, we choose
$p(y|x,\theta)=\mathrm{Categorical}(\mathrm{softmax}(h_{\theta}(x)))$. Our
loss function is the negative log-likelihood $l(\theta,z)=-\ln p(y|x,\theta)$.

Next, we define a family of priors $\\{P_{\phi}:\phi\in\Phi\\}$ over the NN
parameters $\theta$. For computational convenience, we employ diagonal
Gaussian priors, that is,
$P_{\phi_{l}}=\mathcal{N}(\mu_{P_{k}},\text{diag}(\sigma_{P_{k}}^{2}))$ with
$\phi:=(\mu_{P_{k}},\ln\sigma_{P_{k}})$. Note that we represent
$\sigma_{P_{k}}$ in the log-space to avoid additional positivity constraints.
In fact, any parametric distribution that supports re-parametrized sampling
and has a tractable log-density (e.g., normalizing flows (c.f., Rezende &
Mohamed, 2015)) could be used. Moreover, we use a zero-centered, spherical
Gaussian hyper-prior $\mathcal{P}:=\mathcal{N}(0,\sigma_{\mathcal{P}}^{2}I)$
over the prior parameters $\phi$.

Approximating the marginal log-likelihood. Unlike for GPs, the (generalized)
marginal log-likelihood (MLL)

$\ln Z_{\beta}(S_{i},P_{\phi})=\ln\mathbb{E}_{\theta\sim
P_{\phi}}\left[e^{-\beta_{i}\hat{\mathcal{L}}(\theta,S_{i})}\right]$ (8)

is intractable for BNNs. Estimating and optimizing $\ln
Z_{\beta}(S_{i},P_{\phi})$ is not only challenging due to the high-dimensional
expectation over $\Theta$ but also due to numerical instabilities inherent in
computing $e^{-\beta_{i}\hat{\mathcal{L}}(\theta,S_{i})}$ when $\beta_{i}=m$
is large. Aiming to overcome these issues, we compute numerically stable Monte
Carlo estimates of $\nabla_{\phi}\ln Z_{\beta}(S_{i},P_{\phi_{k}})$ by
combining the LogSumExp (LSE) with the re-parametrization trick (Kingma &
Welling, 2014). In particular, the MLL_Estimator draws $L$ samples
$\theta_{l}:=f(\phi_{k},{\epsilon}_{l})=\mu_{P_{k}}+\sigma_{P_{k}}\odot{\epsilon}_{l},~{}{\epsilon}_{l}\sim
N(0,I)$ and computes the generalized MLL estimate as follows:

$\ln\tilde{Z}_{\beta_{i}}(S_{i},P_{\phi}):=~{}\text{LSE}_{l=1}^{L}\left(-\beta_{i}\hat{\mathcal{L}}(\theta_{l},S_{i})\right)-\ln
L\vspace{-2pt}$ (9)

Note that $\ln\tilde{Z}_{\beta}(S_{i},P_{\phi})$ is a consistent but not an
unbiased estimator of $\ln Z_{\beta}(S_{i},P_{\phi})$ (see Appx. D for
details).

Algorithm. Alg. 3 in Appx. D summarizes the proposed meta-learning method
which we henceforth refer to as _PACOH-NN_. To estimate the score
$\nabla_{\phi_{k^{\prime}}}\ln\mathcal{Q}^{*}(\phi_{k^{\prime}})$, we can even
use mini-batching on the task level. This mini-batched version, outlined in
Alg. 4, maintains $K$ particles to approximate the hyper-posterior, and in
each forward step samples $L$ NN-parameters (of dimensionaly $|\Theta|$) per
prior particle, that are deployed on a mini-batch of $n_{bs}$ tasks, to
estimate the score of $\mathcal{Q}^{*}$. As a result, the total space
complexity is on the order of $\mathcal{O}(|\Theta|K+L)$ and the computational
complexity of the algorithm for a single iteration is
$\mathcal{O}(K^{2}+KLn_{bs})$.

A key advantage of _PACOH-NN_ over previous methods for meta-learning BNN
priors (e.g., Pentina & Lampert, 2014; Amit & Meir, 2018) is that it turns the
previously nested optimization problem into a much simpler standard stochastic
optimization problem. This makes meta-learning not only much more stable but
also more scalable. In particular, we do not need to explicitly compute the
task posteriors $Q_{i}$ and can employ mini-batching over tasks. Thus, the
computational and space complexities do not depend on the number of tasks $n$.
In comparison, _MLAP_ (Amit & Meir, 2018) has a memory footprint of
$\mathcal{O}(|\Theta|n)$ making meta-learning prohibitive even for moderately
many (e.g., 50) tasks.

Figure 2: BNN posterior predictions with (top) standard Gaussian prior vs.
(bottom) meta-learned prior. Meta-learning with _PACOH-NN_ was conducted on
the _Sinusoids_ environment.

##  6 Experiments

We now empirically evaluate the two methods _PACOH-GP_ 222The source code for
_PACOH-GP_ is available at tinyurl.com/pacoh-gp-code. and _PACOH-NN_ 333An
implementation of _PACOH-NN_ can be found at tinyurl.com/pacoh-nn-code. that
were introduced in Section 5. Comparing them to existing meta-learning
approaches on various regression and classification environments, we
demonstrate that our _PACOH_ -based methods (i) outperform previous meta-
learning algorithms in predictive accuracy, (ii) improve the calibration of
uncertainty estimates, (iii) are much more scalable than previous PAC-Bayesian
meta-learners, and (iv) effectively combat meta-overfitting. Finally, we
showcase how meta-learned _PACOH-NN_ priors can be harnessed in a real-world
sequential decision making task concerning peptide-based vaccine development.

| Cauchy | SwissFel | Physionet-GCS | Physionet-HCT | Berkeley-Sensor
---|---|---|---|---|---
Vanilla GP | $0.275\pm 0.000$ | $0.876\pm 0.000$ | $2.240\pm 0.000$ | $2.768\pm 0.000$ | $0.276\pm 0.000$
Vanilla BNN (Liu & Wang, 2016) | $0.327\pm 0.008$ | $0.529\pm 0.022$ | $2.664\pm 0.274$ | $3.938\pm 0.869$ | $0.109\pm 0.004$
MLL-GP (Fortuin & Rätsch, 2019) | $0.216\pm 0.003$ | $0.974\pm 0.093$ | $1.654\pm 0.094$ | $2.634\pm 0.144$ | $0.058\pm 0.002$
MLAP (Amit & Meir, 2018) | $0.219\pm 0.004$ | $0.486\pm 0.026$ | $2.009\pm 0.248$ | $2.470\pm 0.039$ | $0.050\pm 0.005$
MAML (Finn et al., 2017) | $0.219\pm 0.004$ | $0.730\pm 0.057$ | $1.895\pm 0.141$ | $2.413\pm 0.113$ | $\mathbf{0.045\pm 0.003}$
BMAML (Kim et al., 2018) | $0.225\pm 0.004$ | $0.577\pm 0.044$ | $1.894\pm 0.062$ | $2.500\pm 0.002$ | $0.073\pm 0.014$
NP (Garnelo et al., 2018) | $0.224\pm 0.008$ | $0.471\pm 0.053$ | $2.056\pm 0.209$ | $2.594\pm 0.107$ | $0.079\pm 0.007$
PACOH-GP (ours) | $0.209\pm 0.008$ | $0.376\pm 0.024$ | $\mathbf{1.498\pm 0.081}$ | $\mathbf{2.361\pm 0.047}$ | $0.065\pm 0.005$
PACOH-NN (ours) | $\mathbf{0.195\pm 0.001}$ | $\mathbf{0.372\pm 0.002}$ | $\mathbf{1.561\pm 0.061}$ | $\mathbf{2.405\pm 0.017}$ | $\mathbf{0.043\pm 0.001}$

Table 1: Comparison of standard and meta-learning algorithms in terms of test
RMSE in 5 meta-learning environments for regression. Reported are mean and
standard deviation across 5 seeds. Our proposed method _PACOH_ achieves the
best performance across all tasks.

| Cauchy | SwissFel | Physionet-GCS | Physionet-HCT | Berkeley-Sensor
---|---|---|---|---|---
Vanilla GP | $0.087\pm 0.000$ | $0.135\pm 0.000$ | $0.268\pm 0.000$ | $\mathbf{0.277\pm 0.000}$ | $0.119\pm 0.000$
Vanilla BNN (Liu & Wang, 2016) | $0.055\pm 0.006$ | $0.085\pm 0.008$ | $0.277\pm 0.013$ | $0.307\pm 0.009$ | $0.179\pm 0.002$
MLL-GP (Fortuin & Rätsch, 2019) | $0.059\pm 0.003$ | $0.096\pm 0.009$ | $0.277\pm 0.009$ | $0.305\pm 0.014$ | $0.153\pm 0.007$
MLAP (Amit & Meir, 2018) | $0.086\pm 0.015$ | $0.090\pm 0.021$ | $0.343\pm 0.017$ | $0.344\pm 0.016$ | $0.108\pm 0.024$
BMAML (Kim et al., 2018) | $0.061\pm 0.007$ | $0.115\pm 0.036$ | $0.279\pm 0.010$ | $0.423\pm 0.106$ | $0.161\pm 0.013$
NP (Garnelo et al., 2018) | $0.057\pm 0.009$ | $0.131\pm 0.056$ | $0.299\pm 0.012$ | $0.319\pm 0.004$ | $0.210\pm 0.007$
PACOH-GP (ours) | $0.056\pm 0.004$ | $0.038\pm 0.006$ | $\mathbf{0.262\pm 0.004}$ | $0.296\pm 0.003$ | $0.098\pm 0.005$
PACOH-NN (ours) | $\mathbf{0.046\pm 0.001}$ | $\mathbf{0.027\pm 0.003}$ | $0.267\pm 0.005$ | $0.302\pm 0.003$ | $\mathbf{0.067\pm 0.005}$

Table 2: Comparison of standard and meta-learning methods in terms of the test
calibration error in 5 regression environments. We report the mean and
standard deviation across 5 random seeds. PACOH yields the best uncertainty
calibration in the majority of environments.

###  6.1 Experiment Setup

Regression environments. In our experiments, we consider two synthetic and
four real-world meta-learning environments for _regression_. As a synthetic
environment we employ _Sinusoids_ of varying amplitude, phase and slope as
well as a 2-dimensional mixture of _Cauchy_ distributions plus random GP
functions. As real-world environments, we use datasets corresponding to
different calibration sessions of the Swiss Free Electron Laser (_SwissFEL_)
(Milne et al., 2017; Kirschner et al., 2019b), as well as data from the
_PhysioNet_ 2012 challenge, which consists of time series of electronic health
measurements from intensive care patients (Silva et al., 2012), in particular
the Glasgow Coma Scale (_GCS_) and the hematocrit value (_HCT_). Here, the
different tasks correspond to different patients. Moreover, we employ the
Intel Berkeley Research Lab temperature sensor dataset (_Berkeley-Sensor_)
(Madden, 2004) where the tasks require auto-regressive prediction of
temperature measurements corresponding to sensors installed in different
locations of the building. Further details can be found in Appendix E.1.

Classification environments. We conduct experiments with the multi-task
_classification_ environment _Omniglot_ (Lake et al., 2015), consisting of
handwritten letters across 50 alphabets. Unlike previous work (e.g., Finn et
al., 2017) we do not perform data augmentation and do not recombine letters of
different alphabets, thus preserving the data’s original structure and
mitigating the need for prior knowledge. In particular, one task corresponds
to 5-way 5-shot classification of letters within an alphabet. This leaves us
with much fewer tasks (30 meta-train, 20 meta-test tasks), making the
environment more challenging and interesting for uncertainty quantification.
This also allows us to include _MLAP_ in the experiment which hardly scales to
more than 50 tasks.

Baselines. We use a _Vanilla GP_ with squared exponential kernel and a
_Vanilla BNN_ with a zero-centered, spherical Gaussian prior and SVGD
posterior inference (Liu & Wang, 2016) as baselines. Moreover, we compare our
proposed approach against various popular meta-learning algorithms, including
model-agnostic meta-learning (_MAML_) (Finn et al., 2017), Bayesian MAML
(_BMAML_) (Kim et al., 2018) and the PAC-Bayesian approach by Amit & Meir
(2018) (_MLAP_). For regression experiments, we also report results for neural
processes (_NPs_) (Garnelo et al., 2018) and a GP with neural-network-based
mean and kernel function, meta-learned by maximizing the marginal log-
likelihood (_MLL-GP_) (Fortuin & Rätsch, 2019). Among all, _MLAP_ is the most
similar to our approach as it is neural-network-based and minimizes PAC-
Bayesian bounds on the transfer error. Though, unlike _PACOH-NN_ , it relies
on nested optimization of the task posteriors $Q_{i}$ and the hyper-posterior
$\mathcal{Q}$. _MLL-GP_ is similar to _PACOH-GP_ insofar that it also
maximizes the sum of marginal log-likelihoods $\ln Z_{m}(S_{i},P_{\phi})$
across tasks. However, unlike _PACOH-GP_ it lacks any form of meta-level
regularization.

###  6.2 Experiment Results

Qualitative example. Figure 2 illustrates _BNN_ predictions on a sinusoidal
regression task with a standard Gaussian prior as well as a _PACOH-NN_ prior
meta-learned with 20 tasks from the Sinusoids environment. We can see that the
standard Gaussian prior provides poor inductive bias, not only leading to bad
mean predictions away from the test points but also to poor 95% confidence
intervals (blue shaded areas). In contrast, the meta-learned _PACOH-NN_ prior
encodes useful inductive bias towards sinusoidal function shapes, leading to
better predictions and uncertainty estimates, even with minimal training data.

PACOH improves the predictive accuracy. Using the meta-learning environments
and baseline methods that we introduced in Sec. 6.1, we perform a
comprehensive benchmark study. Table 1 reports the results on the regression
environments in terms of the root mean squared error (RMSE) on unseen test
tasks. Among the approaches, _PACOH-NN_ and _PACOH-GP_ consistently perform
best or are among the best methods. Similarly, _PACOH-NN_ achieves the highest
accuracy in the Omniglot classification environment (cf. Table 3). Overall,
this demonstrates that the introduced meta-learning framework is not only
sound, but also yields state-of-the-art empirical performance in practice.

| Accuracy | Calibration error
---|---|---
Vanilla BNN (Liu & Wang, 2016) | $0.795\pm 0.006$ | $0.135\pm 0.009$
MLAP (Amit & Meir, 2018) | $0.700\pm 0.0135$ | $0.108\pm 0.010$
MAML (Finn et al., 2017) | $0.693\pm 0.013$ | $0.109\pm 0.011$
BMAML (Kim et al., 2018) | $0.764\pm 0.025$ | $0.191\pm 0.018$
PACOH-NN (ours) | $\mathbf{0.885\pm 0.090}$ | $\mathbf{0.091\pm 0.010}$

Table 3: Comparison of meta-learning algorithms in terms of test accuracy and
calibration error on the _Omniglot_ environment. Among the methods, PACOH-NN
makes the most accurate and best-calibrated class predictions.

PACOH improves the predictive uncertainty. We hypothesize that by acquiring
the prior in a principled data-driven manner (e.g., with _PACOH_), we can
improve the quality of the GP’s and BNN’s uncertainty estimates. To
investigate the effect of meta-learned priors on the uncertainty estimates of
the base learners, we compute the probabilistic predictors’ calibration
errors, reported in Table 2 and 3. The calibration error measures the
discrepancy between the predicted confidence regions and the actual
frequencies of test data in the respective areas (Kuleshov et al., 2018). Note
that, since _MAML_ only produces point predictions, the concept of calibration
does not apply to it. We observe that meta-learning priors with _PACOH-NN_
consistently improves the Vanilla BNN’s uncertainty estimates. Similarly,
_PACOH-GP_ yields a lower calibration error than the Vanilla GP in the
majority of the envionments. For meta-learning environments where the task
similarity is high, like _SwissFEL_ and _Berkeley-Sensor_ , the improvement is
substantial.

PACOH is scalable. Unlike _MLAP_ (Amit & Meir, 2018), _PACOH-NN_ does not need
to maintain posteriors $Q_{i}$ for the meta-training tasks and can use mini-
batching on the task level. As a result, it is computationally much faster and
more scalable than previous PAC-Bayesian meta-learners. This is reflected in
its computation and memory complexity, discussed in Section 5. Figure 3
showcases this computational advantage during meta-training with _PACOH-NN_
and _MLAP_ on the _Sinusoids_ environment with varying number of tasks,
reporting the maximum memory requirements, as well as the training time. While
_MLAP’s_ memory consumption and compute time grow linearly and become
prohibitively large even for less than 100 tasks, _PACOH-NN_ maintains a
constant memory and compute load as the number of tasks grow.

Figure 3: Comparison of _PACOH-NN_ and _MLAP_ in memory footprint and compute
time, as the number of meta-training task grows. _PACOH-NN_ scales much better
in the number of tasks than _MLAP_.

PACOH combats meta-overfitting. As Qin et al. (2018) and Yin et al. (2020)
point out, many popular meta-learners (e.g., Finn et al., 2017; Garnelo et
al., 2018) require a large number of meta-training tasks to generalize well.
When presented with only a limited number of tasks, such algorithms suffer
from severe meta-overfitting, adversely impacting their performance on unseen
tasks from $\mathcal{T}$. This can even lead to negative transfer, such that
meta-learning actually hurts the performance when compared to standard
learning. In our experiments, we also observe such failure cases: For
instance, in the classification environment (cf. Table 3), _MAML_ fails to
improve upon the Vanilla BNN. Similarly, in the regression environments (cf.
Table 3) we find that _NPs_ , _BMAML_ and _MLL-GP_ often yield worse-
calibrated predictive distributions than the Vanilla BNN and GP respectively.
In contrast, thanks to its theoretically principled construction, _PACOH-NN_
is able to achieve positive transfer even when the tasks are diverse and small
in number. In particular, the hyper-prior acts as meta-level regularizer by
penalizing complex priors that are unlikely to convey useful inductive bias
for unseen learning tasks.

To investigate the importance of meta-level regularization through the hyper-
prior in more detail, we compare the performance of our proposed method
_PACOH-GP_ to _MLL-GP_ (Fortuin & Rätsch, 2019) which also maximizes the sum
of GP marginal log-likelihoods across tasks but has no hyper-prior nor meta-
level regularization. Fig. 4 shows that MLL-GP performs significantly better
on the meta-training tasks than on the meta-test tasks in both of our
synthetic regression environments. This gap between meta-train performance and
meta-test performance signifies overfitting on the meta-level. In contrast,
our method hardly exhibits this gap and consistently outperforms MLL-GP. As
expected, this effect is particularly pronounced when the number of meta-
training tasks is small (i.e., less than 100) and vanishes as $n$ becomes
large. Similar results for other meta-learning methods can be found in
Appendix E.5. Once more, this demonstrates the importance of meta-level
regularization, and shows that our proposed framework effectively addresses
the problem of meta-overfitting.

Figure 4:  Test RMSE on meta-training and meta-testing tasks as a function of
the number of meta-training tasks for PACOH-GP and MLL-GP. The performance gap
between the train and test tasks demonstrates overfitting in the MLL method,
while PACOH performs consistently better and barely overfits.

###  6.3 Meta-Learning for Sequential Decision Making

Finally, we showcase how a relevant real-world application such as vaccine
design can benefit from our proposed method. The goal is to discover peptides
which bind to major histocompatibility complex class-I molecules (MHC-I).
Following the Bayesian optimization (BO) setup of Krause & Ong (2011), each
task corresponds to searching for maximally binding peptides, a vital step in
the design of peptide-based vaccines. The tasks differ in their targeted MHC-I
allele, corresponding to different genetic variants of the MHC-I protein. We
use data from Widmer et al. (2010), which contains the standardized binding
affinities ($\text{IC}_{50}$values) of different peptide candidates (encoded
as 45-dimensional feature vectors) to the MHC-I alleles.

Figure 5: MHC-I peptide design task: Regret for different priors and bandit
algorithms. A meta-learned _PACOH-NN_ prior substantially improves the regret,
compared to a standard BNN/GP prior.

We use 5 alleles (tasks) to meta-learn a BNN prior with _PACOH-NN_ and leave
the most genetically dissimilar allele (A-6901) for our bandit task. In each
iteration, the experimenter (i.e., the Bayesian optimization algorithm)
chooses to test one peptide among the pool of more than 800 candidates and
receives its binding affinity as a reward feedback. In particular, we employ
UCB (Auer, 2002) and Thompson-Sampling (TS) (Thompson, 1933) as bandit
algorithms, comparing the BNN-based bandits with meta-learned prior (_PACOH-
UCB/TS_) against a zero-centered Gaussian BNN prior (_BNN-UCB/TS_) and a
Gaussian process (_GP-UCB_) (Srinivas et al., 2009).

Fig. 5 reports the respective average regret and simple regret over 50
iterations. Unlike the bandit algorithms with standard BNN/GP prior, _PACOH-
UCB/TS_ reaches near optimal regret within less than 10 iterations and after
50 iterations still maintains a significant performance advantage. This
highlights the importance of _transfer (learning)_ for solving real-world
problems and demonstrates the effectiveness of _PACOH-NN_ to this end. While
the majority of meta-learning methods rely on a large number of meta-training
tasks (Qin et al., 2018), _PACOH-NN_ allows us to achieve promising positive
transfer, even in complex real-world scenarios with only a handful (in this
case 5) of tasks.

##  7 Conclusion

We presented PACOH, a novel, theoretically principled, and scalable PAC-
Bayesian meta-learning approach. PACOH outperforms existing methods in terms
of predictive performance and uncertainty calibration, while providing PAC-
Bayesian guarantees without relying on costly nested optimization. It can be
used with different base learners (e.g., GPs or BNNs) and achieves positive
transfer in regression and classification with as little as five meta-tasks.
BNNs meta-learnt with PACOH can be effectively used for sequential decision
making, as demonstrated by our vaccine design application. We believe our
approach provides an important step towards learning useful inductive bias
from data in a flexible, scalable, and principled manner.

## Acknowledgements

This project has received funding from the European Research Council (ERC)
under the European Union’s Horizon 2020 research and innovation program grant
agreement No 815943 and was supported by Oracle Cloud Services. Vincent
Fortuin is funded by a PhD fellowship from the Swiss Data Science Center and
by the grant 2017-110 of the Strategic Focus Area “Personalized Health and
Related Technologies (PHRT)” of the ETH Domain. We thank David Lindner, Gideon
Dresdner, and Claire Vernade for their valuable feedback.

## References

  * Alquier et al. (2016) Alquier, P., Ridgway, J., Chopin, N., and Teh, Y. W.  On the properties of variational approximations of Gibbs posteriors.  _Journal of Machine Learning Research_ , 2016.
  * Amit & Meir (2018) Amit, R. and Meir, R.  Meta-learning by adjusting priors based on extended PAC-Bayes theory.  In _International Conference on Machine Learning_ , 2018.
  * Andrychowicz et al. (2016) Andrychowicz, M., Denil, M., Colmenarejo, S. G., Hoffman, M. W., Pfau, D., Schaul, T., Shillingford, B., and De Freitas, N.  Learning to learn by gradient descent by gradient descent.  In _Advances in Neural Information Processing Systems_ , 2016.
  * Auer (2002) Auer, P.  Using confidence bounds for exploitation-exploration trade-offs.  _Journal of Machine Learning Research_ , 3(Nov):397–422, 2002.
  * Baxter (2000) Baxter, J.  A model of inductive bias learning.  _Journal of Artificial Intelligence Research_ , 2000.
  * Bergstra et al. (2013) Bergstra, J., Yamins, D., and Cox, D.  Making a science of model search: Hyperparameter optimization in hundreds of dimensions for vision architectures.  In _International Conference on Machine Learning_ , 2013.
  * Blei et al. (2016) Blei, D. M., Kucukelbir, A., and McAuliffe, J. D.  Variational Inference: A Review for Statisticians.  _arXiv preprint arXiv:1601.00670_ , 2016.
  * Boucheron et al. (2013) Boucheron, S., Lugosi, G., and Massart, P.  Concentration inequalities : a nonasymptotic theory of independence.  chapter 2.4, pp. 27–30. Oxford University Press, 2013.
  * Catoni (2007) Catoni, O.  PAC-Bayesian supervised classification: the thermodynamics of statistical learning.  _arXiv_ , 2007.
  * Chen et al. (2017) Chen, Y., Hoffman, M. W., Colmenarejo, S. G., Denil, M., Lillicrap, T. P., Botvinick, M., and De Freitas, N.  Learning to Learn without Gradient Descent by Gradient Descent.  In _International Conference on Machine Learning_ , 2017.
  * Dziugaite & Roy (2016) Dziugaite, G. K. and Roy, D. M.  Computing nonvacuous generalization bounds for deep (stochastic) neural networks with many more parameters than training data.  In _Uncertainty in Artificial Intelligence_ , 2016.
  * Finn et al. (2017) Finn, C., Abbeel, P., and Levine, S.  Model-agnostic meta-learning for fast adaptation of deep networks.  In _International Conference on Machine Learning_ , 2017.
  * Finn et al. (2018) Finn, C., Xu, K., and Levine, S.  Probabilistic model-agnostic meta-learning.  In _Advances in Neural Information Processing Systems_ , 2018.
  * Fortuin & Rätsch (2019) Fortuin, V. and Rätsch, G.  Deep Mean Functions for Meta-Learning in Gaussian Processes.  _arXiv preprint: arXiv:1901.08098_ , 2019.
  * Fortuin et al. (2019) Fortuin, V., Rätsch, G., and Mandt, S.  Multivariate time series imputation with variational autoencoders.  _arXiv preprint arXiv:1907.04155_ , 2019.
  * Garnelo et al. (2018) Garnelo, M., Schwarz, J., Rosenbaum, D., Viola, F., Rezende, D. J., Eslami, S., and Teh, Y. W.  Neural processes.  _arXiv preprint arXiv:1807.01622_ , 2018.
  * Germain et al. (2016) Germain, P., Bach, F., Lacoste, A., and Lacoste-Julien, S.  Pac-bayesian theory meets bayesian inference.  In _Advances in Neural Information Processing Systems_ , 2016.
  * Guedj (2019) Guedj, B.  A primer on PAC-Bayesian learning.  In _2nd Congress of the French Mathematical Society_ , 2019.
  * Guo et al. (2017) Guo, C., Pleiss, G., Sun, Y., and Weinberger, K. Q.  On calibration of modern neural networks.  In _International Conference on Machine Learning_ , pp. 1321–1330, 2017.
  * Hochreiter et al. (2001) Hochreiter, S., Younger, A. S., and Conwell, P. R.  Learning To Learn Using Gradient Descent.  In _International Conference on Artificial Neural Networks_ , 2001\.
  * Kim et al. (2018) Kim, T., Yoon, J., Dia, O., Kim, S., Bengio, Y., and Ahn, S.  Bayesian model-agnostic meta-learning.  In _Advances in Neural Information Processing Systems_ , 2018.
  * Kingma & Welling (2014) Kingma, D. P. and Welling, M.  Auto-encoding variational bayes.  In _International Conference on Learning Representations_ , 2014.
  * Kirschner et al. (2019a) Kirschner, J., Mutný, M., Hiller, N., Ischebeck, R., and Krause, A.  Adaptive and Safe Bayesian Optimization in High Dimensions via One-Dimensional Subspaces.  In _International Conference on Machine Learning_ , 2019a.
  * Kirschner et al. (2019b) Kirschner, J., Nonnenmacher, M., Mutný, M., Hiller, N., Adelmann, A., Ischebeck, R., and Krause, A.  Bayesian Optimization for Fast and Safe Parameter Tuning of SwissFEL.  In _International Free-Electron Laser Conference (FEL2019)_ , 2019b.
  * Krause & Ong (2011) Krause, A. and Ong, C. S.  Contextual gaussian process bandit optimization.  In _Advances in Neural Information Processing Systems_ , 2011.
  * Kuleshov et al. (2018) Kuleshov, V., Fenner, N., and Ermon, S.  Accurate uncertainties for deep learning using calibrated regression.  In _International Conference on Machine Learning_ , 2018.
  * Lake et al. (2015) Lake, B. M., Salakhutdinov, R., and Tenenbaum, J. B.  Human-level concept learning through probabilistic program induction.  _Science_ , 2015.
  * Lever et al. (2013) Lever, G., Laviolette, F., and Shawe-Taylor, J.  Tighter PAC-Bayes bounds through distribution-dependent priors.  _Theoretical Computer Science_ , 473:4–28, feb 2013.  ISSN 0304-3975.  doi: 10.1016/J.TCS.2012.10.013.
  * Liu & Wang (2016) Liu, Q. and Wang, D.  Stein Variational Gradient Descent: A General Purpose Bayesian Inference Algorithm.  In _Advances in Neural Information Processing Systems_ , 2016.
  * Madden (2004) Madden, S.  Intel lab data.  http://db.csail.mit.edu/labdata/labdata.html, 2004.  Accessed: Sep 8, 2020.
  * McAllester (1999) McAllester, D. A.  Some PAC-Bayesian theorems.  _Machine Learning_ , 1999.
  * Milne et al. (2017) Milne, C. J., Schietinger, T., Aiba, M., Alarcon, A., Alex, J., Anghel, A., Arsov, V., Beard, C., Beaud, P., Bettoni, S., et al.  Swissfel: the swiss x-ray free electron laser.  _Applied Sciences_ , 2017.
  * Nichol et al. (2018) Nichol, A., Achiam, J., and Schulman, J.  On First-Order Meta-Learning Algorithms.  _arXiv preprint arXiv:1803.02999_ , 2018.
  * Parrado-Hernandez et al. (2012) Parrado-Hernandez, E., Ambroladze, A., Shawe-Taylor, J., and Sun, S.  PAC-Bayes Bounds with Data Dependent Priors.  _Journal of Machine Learning Research_ , 2012.
  * Pentina & Lampert (2014) Pentina, A. and Lampert, C.  A PAC-Bayesian bound for lifelong learning.  In _International Conference on Machine Learning_ , 2014.
  * Qin et al. (2018) Qin, Y., Zhang, W., Zhao, C., Wang, Z., Shi, H., Qi, G., Shi, J., and Lei, Z.  Rethink and redesign meta learning.  _arXiv preprint arXiv:1812.04955_ , 2018.
  * Rasmussen & Ghahramani (2001) Rasmussen, C. E. and Ghahramani, Z.  Occam’s Razor.  In _NIPS_ , volume 13, pp. 294—-300, 2001.
  * Rasmussen & Williams (2006) Rasmussen, C. E. and Williams, C. K. I.  _Gaussian processes in machine learning_.  2006\.
  * Rezende & Mohamed (2015) Rezende, D. J. and Mohamed, S.  Variational inference with normalizing flows.  _International Conference on Machine Learning_ , 2015.
  * Rothfuss et al. (2019a) Rothfuss, J., Ferreira, F., Boehm, S., Walther, S., Ulrich, M., Asfour, T., and Krause, A.  Noise Regularization for Conditional Density Estimation.  _arXiv preprint arXiv:1907.08982_ , 2019a.
  * Rothfuss et al. (2019b) Rothfuss, J., Lee, D., Clavera, I., Asfour, T., and Abbeel, P.  ProMP: Proximal Meta-Policy Search.  In _International Conference on Learning Representations_ , 2019b.
  * Silva et al. (2012) Silva, I., Moody, G., Scott, D. J., Celi, L. A., and Mark, R. G.  Predicting in-hospital mortality of icu patients: The physionet/computing in cardiology challenge 2012.  In _Computing in Cardiology_ , 2012.
  * Snell et al. (2017) Snell, J., Swersky, K., and Zemel, R.  Prototypical networks for few-shot learning.  In _Advances in Neural Information Processing Systems_ , 2017.
  * Srinivas et al. (2009) Srinivas, N., Krause, A., Kakade, S. M., and Seeger, M.  Gaussian process optimization in the bandit setting: No regret and experimental design.  In _International Conference on Machine Learning_ , 2009.
  * Thompson (1933) Thompson, W. R.  On the likelihood that one unknown probability exceeds another in view of the evidence of two samples.  _Biometrika_ , 1933.
  * Thrun & Pratt (1998) Thrun, S. and Pratt, L. (eds.).  _Learning to Learn_.  Kluwer Academic Publishers, 1998.
  * Vinyals et al. (2016) Vinyals, O., Blundell, C., Lillicrap, T., Wierstra, D., et al.  Matching networks for one shot learning.  In _Advances in Neural Information Processing Systems_ , 2016.
  * Widmer et al. (2010) Widmer, C., Toussaint, N. C., Altun, Y., and Rätsch, G.  Inferring latent task structure for multitask learning by multiple kernel learning.  _BMC bioinformatics_ , 2010.
  * Wilson et al. (2016) Wilson, A. G., Hu, Z., Salakhutdinov, R., and Xing, E. P.  Deep kernel learning.  In _Artificial Intelligence and Statistics_ , pp. 370–378, 2016\.
  * Yin et al. (2020) Yin, M., Tucker, G., Zhou, M., Levine, S., and Finn, C.  Meta-learning without memorization.  In _International Conference on Learning Representations_ , 2020.

## Appendix

##  Appendix A Proofs and Derivations

###  A.1 Proof of Theorem 2

######  Lemma 2.

(Change of measure inequality) Let $f$ be a random variable taking values in a
set $A$ and let $X_{1},...,X_{l}$ be independent random variables, with
$X_{k}\in A$ with distribution $\mu_{k}$. For functions $g_{k}:A\times
A\rightarrow\mathbb{R},k=1,...,l$, let
$\xi_{k}(f)=\mathbb{E}_{X_{k}\sim\mu_{k}}\left[g_{k}(f,X_{k})\right]$ denote
the expectation of $g_{k}$ under $\mu_{k}$ for any fixed $f\in A$. Then for
any fixed distributions $\pi,\rho$ $\in\mathcal{M}(A)$ and any $\lambda>0$, we
have that

$\displaystyle\mathbb{E}_{f\sim\rho}\left[\sum_{k=1}^{l}\xi_{k}(f)\
-g_{k}(f,X_{k})\right]\leq\frac{1}{\lambda}\left(D_{KL}(\rho||\pi)+\ln\mathbb{E}_{f\sim\pi}\left[e^{\lambda\big{(}\sum_{k=1}^{l}\xi_{k}(f)-g_{k}(f,X_{k})\big{)}}\right]\right).$
(10)

To prove the Theorem 2, we need to bound the difference between _transfer
error_ $\mathcal{L}(\mathcal{Q},\mathcal{T})$ and the _empirical multi-task
error_ $\hat{\mathcal{L}}(\mathcal{Q},S_{1},...,S_{n})$. To this end, we
introduce an intermediate quantity, the _expected multi-task error_ :

$\tilde{\mathcal{L}}(\mathcal{Q},\mathcal{D}_{1},...,\mathcal{D}_{n})=\mathbb{E}_{P\sim\mathcal{Q}}\left[\frac{1}{n}\sum_{i=1}^{n}\mathbb{E}_{S\sim
D_{i}^{m_{i}}}\left[\mathcal{L}(Q(S,P),\mathcal{D}_{i})\right]\right]$ (11)

In the following we invoke Lemma 2 twice. First, in step 1, we bound the
difference between
$\tilde{\mathcal{L}}(\mathcal{Q},\mathcal{D}_{1},...,\mathcal{D}_{n})$ and
$\hat{\mathcal{L}}(\mathcal{Q},S_{1},...,S_{n})$, then, in step 2, the
difference between $\mathcal{L}(\mathcal{Q},\mathcal{T})$ and
$\tilde{\mathcal{L}}(\mathcal{Q},\mathcal{D}_{1},...,\mathcal{D}_{n})$.
Finally, in step 3, we use a union bound argument to combine both results.

##### Step 1 (Task specific generalization)

First, we bound the generalization error of the observed tasks
$\tau_{i}=(\mathcal{D}_{i},m_{i})$, $i=1,...,n$, when using a learning
algorithm $Q:\mathcal{M}\times\mathcal{Z}^{m_{i}}\rightarrow\mathcal{M}$,
which outputs a posterior distribution $Q_{i}=Q(S_{i},P)$ over hypotheses $h$,
given a prior distribution $P$ and a dataset
$S_{i}\sim\mathcal{D}^{m_{i}}_{i}$ of size $m_{i}$. In that, we define
$\tilde{m}:=(\sum_{i=1}^{n}m_{i}^{-1})^{-1}$ as the harmonic mean of sample
sizes.

In particular, we apply Lemma 2 to the union of all training sets
$S^{\prime}=\bigcup_{i=1}^{n}S_{i}$ with $l=\sum_{i=1}^{n}m_{i}$. Hence, each
$X_{k}$ corresponds to one data point, i.e. $X_{k}=z_{ij}$ and
$\mu_{k}=\mathcal{D}_{i}$. Further, we set $f=(P,h_{1},...,h_{n})$ to be a
tuple of one prior and $n$ base hypotheses. This can be understood as a two-
level hypothesis, wherein $P$ constitutes a hypothesis of the meta-learning
problem and $h_{i}$ a hypothesis for solving the supervised task $\tau_{i}$.
Correspondingly, we take
$\pi=(\mathcal{Q},Q^{n})=\mathcal{P}\cdot\prod_{i=1}^{n}P$ and
$\rho=(\mathcal{Q},Q^{n})=\mathcal{Q}\cdot\prod_{i=1}^{n}Q_{i}$ as joint two-
level distributions and $g_{k}(f,X_{k})=\frac{1}{nm_{i}}l(h_{i},z_{ij})$ as
summand of the empirical multi-task error. We can now invoke Lemma 2 to obtain
that (12) and (15)

$\displaystyle\begin{split}\frac{1}{n}\sum_{i=1}^{n}\mathbb{E}_{P\sim\mathcal{Q}}\left[\mathcal{L}(Q_{i},D_{i})\right]\leq&\frac{1}{n}\sum_{i=1}^{n}\mathbb{E}_{P\sim\mathcal{Q}}\left[\mathcal{L}(Q_{i},S_{i})\right]+\frac{1}{\gamma}\bigg{(}D_{KL}\left[(\mathcal{Q},Q^{n})||(\mathcal{P},P^{n})\right]\\\
&+\ln\mathbb{E}_{P\sim\mathcal{P}}\mathbb{E}_{h\sim
P}\left[e^{\frac{\gamma}{n}\sum_{i=1}^{n}(\mathcal{L}(h,\mathcal{D}_{i})-\hat{\mathcal{L}}(h,S_{i})}\right]\bigg{)}\end{split}$
(12)

Using the above definitions, the KL-divergence term can be re-written in the
following way:

$\displaystyle D_{KL}\left[(\mathcal{Q},Q^{n})||(\mathcal{P},P^{n})\right]$
$\displaystyle=\mathbb{E}_{P\sim\mathcal{Q}}\left[\mathbb{E}_{h\sim
Q_{i}}\left[\ln\frac{\mathcal{Q}(P)\prod_{i=1}^{n}\prod
Q_{i}(h)}{\mathcal{P}(P)\prod_{i=1}^{n}P(h)}\right]\right]$ (13)
$\displaystyle=\mathbb{E}_{P\sim\mathcal{Q}}\left[\ln\frac{\mathcal{Q}(P)}{\mathcal{P}(P)}\right]+\sum_{i=1}^{n}\mathbb{E}_{P\sim\mathcal{Q}}\left[\mathbb{E}_{h\sim
Q_{i}}\left[\ln\frac{Q_{i}(h)}{P(h)}\right]\right]$ (14)
$\displaystyle=D_{KL}(\mathcal{Q}||\mathcal{P})+\sum_{i=1}^{n}\mathbb{E}_{P\sim\mathcal{Q}}\left[D_{KL}(Q_{i}||P)\right]$
(15)

Using (12) and (15) we can bound the expected multi-task error as follows:

$\displaystyle\begin{split}\tilde{\mathcal{L}}(\mathcal{Q},\mathcal{D}_{1},...,\mathcal{D}_{n})\leq&~{}\hat{\mathcal{L}}(\mathcal{Q},S_{1},...,S_{n})+\frac{1}{\gamma}D_{KL}(\mathcal{Q}||\mathcal{P})+\frac{1}{\gamma}\sum_{i=1}^{n}\mathbb{E}_{P\sim\mathcal{Q}}\left[D_{KL}(Q_{i}||P)\right]\\\
&+\underbrace{\frac{1}{\gamma}\ln\mathbb{E}_{P\sim\mathcal{P}}\mathbb{E}_{h\sim
P}\left[e^{\frac{\gamma}{n}\sum_{i=1}^{n}(\mathcal{L}(h,\mathcal{D}_{i})-\hat{\mathcal{L}}(h,S_{i}))}\right]}_{\Upsilon^{\text{{I}}}(\gamma)}\\\
\end{split}$ (16)

##### Step 2 (Task environment generalization)

Now, we apply Lemma 2 on the meta-level. For that, we treat each task as
random variable and instantiate the components as $X_{k}=\tau_{i}$, $l=n$ and
$\mu_{k}=\mathcal{T}$. Furthermore, we set $\rho=\mathcal{Q}$,
$\pi=\mathcal{P}$, $f=P$ and
$g_{k}(f,X_{k})=\frac{1}{n}\mathcal{L}(Q_{i},\mathcal{D}_{i})$. This allows us
to bound the transfer error as

$\mathcal{L}(\mathcal{Q},\mathcal{T})\leq\tilde{\mathcal{L}}(\mathcal{Q},\mathcal{D}_{1},...,\mathcal{D}_{n})+\frac{1}{\lambda}D_{KL}(\rho||\pi)+\Upsilon^{\text{{II}}}(\lambda)$
(17)

wherein
$\Upsilon^{\text{{II}}}(\lambda)=\frac{1}{\lambda}\ln\mathbb{E}_{P\sim\mathcal{P}}\left[e^{\frac{\lambda}{n}\sum_{i=1}^{n}\mathbb{E}_{(D,S)\sim\mathcal{T}}\left[\mathcal{L}(Q(P,S),\mathcal{D})\right]-\mathcal{L}(Q(P,S_{i}),\mathcal{D}_{i})}\right]$.

Combining (16) with (17), we obtain

$\displaystyle\begin{split}\mathcal{L}(\mathcal{Q},\mathcal{T})\leq&~{}\hat{\mathcal{L}}(\mathcal{Q},S_{1},...,S_{n})+\left(\frac{1}{\lambda}+\frac{1}{\gamma}\right)D_{KL}(\mathcal{Q}||\mathcal{P})\\\
&+\frac{1}{\gamma}\sum_{i=1}^{n}\mathbb{E}_{P\sim\mathcal{Q}}\left[D_{KL}(Q_{i}||P)\right]+\Upsilon^{\text{{I}}}(\gamma)+\Upsilon^{\text{{II}}}(\lambda)\end{split}$
(18)

##### Step 3 (Bounding the moment generating functions)

$\displaystyle\begin{split}e^{(\Upsilon^{\text{{I}}}(\gamma)+\Upsilon^{\text{{II}}}(\lambda))}=&\mathbb{E}_{P\sim\mathcal{P}}\left[e^{\frac{\lambda}{n}\sum_{i=1}^{n}\mathbb{E}_{(D,S)\sim\mathcal{T}}\left[\mathcal{L}(Q(P,S),\mathcal{D})\right]-\mathcal{L}(Q(P,S_{i}),\mathcal{D}_{i})}\right]^{1/\lambda}\cdot\\\
&\mathbb{E}_{P\sim\mathcal{P}}\mathbb{E}_{h\sim
P}\left[e^{\frac{\gamma}{n}\sum_{i=1}^{n}(\mathcal{L}(h,\mathcal{D}_{i})-\hat{\mathcal{L}}(h,S_{i})}\right]^{1/\gamma}\\\
=&\mathbb{E}_{P\sim\mathcal{P}}\left[\prod_{i=1}^{n}e^{\left(\frac{\lambda}{n}\mathbb{E}_{(D,S)\sim\mathcal{T}}\left[\mathcal{L}(Q(P,S),\mathcal{D})\right)\right]-\mathcal{L}(Q(P,S_{i}),\mathcal{D}_{i})}\right]^{1/\lambda}\cdot\\\
&\mathbb{E}_{P\sim\mathcal{P}}\mathbb{E}_{h\sim
P}\left[\prod_{i}^{n}\prod_{i}^{m_{i}}e^{\frac{\gamma}{nm_{i}}(\mathcal{L}(h,\mathcal{D}_{i})-l(h_{i},z_{ij}))}\right]^{1/\gamma}\\\
\end{split}$ (19)

Case I: bounded loss

If the loss function $l(h_{i},z_{ij})$ is bounded in $[a,b]$, we can apply
Hoeffding’s lemma to each factor in (19), obtaining:

$\displaystyle
e^{\Upsilon^{\text{{I}}}(\gamma)+\Upsilon^{\text{{II}}}(\lambda)}\leq$
$\displaystyle~{}\mathbb{E}_{P\sim\mathcal{P}}\left[e^{\frac{\lambda^{2}}{8n}(b-a)^{2}}\right]^{1/\lambda}\cdot\mathbb{E}_{P\sim\mathcal{P}}\mathbb{E}_{h\sim
P}\left[e^{\frac{\gamma^{2}}{8n\tilde{m}}(b-a)^{2}}\right]^{1/\gamma}$ (20)
$\displaystyle=$
$\displaystyle~{}e^{\left(\frac{\lambda}{8n}+\frac{\gamma}{8n\tilde{m}}\right)(b-a)^{2}}$
(21)

Next, we factor out $\sqrt{n}$ from $\gamma$ and $\lambda$, obtaining

$e^{\Upsilon^{\text{{I}}}(\gamma)+\Upsilon^{\text{{II}}}(\lambda)}=\left(e^{\Upsilon^{\text{{I}}}(\gamma\sqrt{n})+\Upsilon^{\text{{II}}}(\lambda\sqrt{n})}\right)^{\frac{1}{\sqrt{n}}}$
(22)

Using

$\mathbb{E}_{\cal{T}}\mathbb{E}_{\mathcal{D}_{1}}...\mathbb{E}_{\mathcal{D}_{n}}\left[e^{\Upsilon^{\text{{I}}}(\gamma\sqrt{n})+\Upsilon^{\text{{II}}}(\lambda\sqrt{n})}\right]\leq
e^{\left(\frac{\lambda}{8\sqrt{n}}+\frac{\gamma}{8\sqrt{n}\tilde{m}}\right)(b-a)^{2}}$
(23)

we can apply Markov’s inequality w.r.t. the expectations over the task
distribution $\mathcal{T}$ and data distributions $\mathcal{D}_{i}$ to obtain
that

$\Upsilon^{\text{{I}}}(\gamma)+\Upsilon^{\text{{II}}}(\lambda)\leq\underbrace{\frac{\lambda}{8n}(b-a)^{2}}_{\Psi^{\text{{I}}}(\lambda)}+\underbrace{\frac{\gamma}{8n\tilde{m}}(b-a)^{2}}_{\Psi^{\text{{II}}}(\gamma)}-\frac{1}{\sqrt{n}}\ln\delta$
(24)

with probability at least $1-\delta$.

Case II: sub-gamma loss

First, we assume that, $\forall i=1,...,n$ the random variables
$V^{\text{{I}}}_{i}:=\mathcal{L}(h,\mathcal{D}_{i})-l(h_{i},z_{i,j})$ are sub-
gamma with variance factor $s_{\text{{I}}}^{2}$ and scale parameter
$c_{\text{{I}}}$ under the two-level prior $(\mathcal{P},P)$ and the
respective data distribution $\mathcal{D}_{i}$. That is, their moment
generating function can be bounded by that of a Gamma distribution
$\Gamma(s_{\text{{I}}}^{2},c_{\text{{I}}})$:

$\mathbb{E}_{z\sim\mathcal{D}_{i}}\mathbb{E}_{P\sim\mathcal{P}}\mathbb{E}_{h\sim
P}\left[e^{\gamma(\mathcal{L}(h,\mathcal{D}_{i})-l(h,z))}\right]\leq\exp\left(\frac{\gamma^{2}s_{\text{{I}}}^{2}}{2(1-c_{\text{{I}}}\gamma)}\right)\quad\forall\gamma\in(0,1/c_{\text{{I}}})$
(25)

Second, we assume that, the random variable
$V^{\text{{II}}}:=\mathbb{E}_{(D,S)\sim\mathcal{T}}\left[\mathcal{L}(Q(P,S),\mathcal{D})\right]-\mathcal{L}(Q(P,S_{i}),\mathcal{D}_{i})$
is sub-gamma with variance factor $s_{\text{{II}}}^{2}$ and scale parameter
$c_{\text{{II}}}$ under the hyper-prior $\mathcal{P}$ and the task
distribution $\mathcal{T}$. That is, its moment generating function can be
bounded by that of a Gamma distribution
$\Gamma(s_{\text{{II}}}^{2},c_{\text{{II}}})$:

$\mathbb{E}_{(\mathcal{D},S)\sim\mathcal{T}}\mathbb{E}_{P\sim\mathcal{P}}\left[e^{\lambda~{}\mathbb{E}_{(D,S)\sim\mathcal{T}}\left[\mathcal{L}(Q(P,S),\mathcal{D})\right]-\mathcal{L}(Q(P,S),\mathcal{D})}\right]\leq\exp\left(\frac{\lambda^{2}s_{\text{{II}}}^{2}}{2(1-c_{\text{{II}}}\lambda)}\right)\quad\forall\lambda\in(0,1/c_{\text{{II}}})$
(26)

These two assumptions allow us to bound the expectation of (19) as follows:

$\displaystyle\mathbb{E}\left[e^{\Upsilon^{\text{{I}}}(\gamma)+\Upsilon^{\text{{II}}}(\lambda)}\right]\leq$
$\displaystyle~{}\exp\left(\frac{\gamma
s_{\text{{I}}}^{2}}{2n\tilde{m}(1-c_{\text{{I}}}\gamma/(n\tilde{m})}\right)\cdot\exp\left(\frac{\lambda
s_{\text{{II}}}^{2}}{2n(1-c_{\text{{II}}}\lambda/n)}\right)$ (27)

Next, we factor out $\sqrt{n}$ from $\gamma$ and $\lambda$, obtaining

$e^{\Upsilon^{\text{{I}}}(\gamma)+\Upsilon^{\text{{II}}}(\lambda)}=\left(e^{\Upsilon^{\text{{I}}}(\gamma\sqrt{n})+\Upsilon^{\text{{II}}}(\lambda\sqrt{n})}\right)^{\frac{1}{\sqrt{n}}}$
(28)

Finally, by using Markov’s inequality we obtain that

$\Upsilon^{\text{{I}}}(\gamma)+\Upsilon^{\text{{II}}}(\lambda)\leq\underbrace{\frac{\gamma
s_{\text{{I}}}^{2}}{2n\tilde{m}(1-c_{\text{{I}}}\gamma/(n\tilde{m})}}_{\Psi^{\text{{I}}}(\gamma)}+\underbrace{\frac{\lambda
s_{\text{{II}}}^{2}}{2n(1-c_{\text{{II}}}\lambda/n)}}_{\Psi^{\text{{II}}}(\lambda)}-\frac{1}{\sqrt{n}}\ln\delta$
(29)

with probability at least $1-\delta$.

To conclude the proof, we choose $\gamma=n\beta$ for $\beta>0$.

###  A.2 Proof of Corollary 1

When we choose the posterior $Q$ as the optimal Gibbs posterior
$Q^{*}_{i}:=Q^{*}(S_{i},P)$, it follows that

$\displaystyle\hat{\mathcal{L}}(\mathcal{Q},S_{1},...,S_{n})+\frac{1}{n}\sum_{i=1}^{n}\frac{1}{\beta}\mathbb{E}_{P\sim\mathcal{Q}}\left[D_{KL}(Q^{*}_{i}||P)\right]$
(30) $\displaystyle=~{}$
$\displaystyle\frac{1}{n}\sum_{i=1}^{n}\left(\mathbb{E}_{P\sim\mathcal{Q}}\mathbb{E}_{h\sim
Q^{*}_{i}}\left[\hat{\mathcal{L}}(h,S_{i})\right]+\frac{1}{\beta}\left(\mathbb{E}_{P\sim\mathcal{Q}}\left[D_{KL}(Q^{*}_{i}||P)\right]\right)\right)$
(31) $\displaystyle=~{}$
$\displaystyle\frac{1}{n}\sum_{i=1}^{n}\frac{1}{\beta}\left(\mathbb{E}_{P\sim\mathcal{Q}}\mathbb{E}_{h\sim
Q^{*}_{i}}\left[\beta\hat{\mathcal{L}}(h,S_{i})+\ln\frac{Q^{*}_{i}(h)}{P(h)}\right]\right)$
(32) $\displaystyle=~{}$
$\displaystyle\frac{1}{n}\sum_{i=1}^{n}\frac{1}{\beta}\left(\mathbb{E}_{P\sim\mathcal{Q}}\mathbb{E}_{h\sim
Q^{*}_{i}}\left[\beta\hat{\mathcal{L}}(h,S_{i})+\ln\frac{P(h)e^{-\beta\hat{\mathcal{L}}(h,S_{i})}}{P(h)Z_{\beta}(S_{i},P)}\right]\right)$
(33) $\displaystyle=~{}$
$\displaystyle\frac{1}{n}\sum_{i=1}^{n}\frac{1}{\beta}\left(-\mathbb{E}_{P\sim\mathcal{Q}}\left[\ln
Z_{\beta}(S_{i},P)\right]\right)\;.$ (34)

This allows us to write the inequality in (4) as

$\displaystyle\mathcal{L}(\mathcal{Q},\mathcal{T})\leq~{}$
$\displaystyle-\frac{1}{n}\sum_{i=1}^{n}\frac{1}{\beta}\mathbb{E}_{P\sim\mathcal{Q}}\left[\ln
Z_{\beta}(S_{i},P)\right]+\left(\frac{1}{\lambda}+\frac{1}{n\beta}\right)D_{KL}(\mathcal{Q}||\mathcal{P})+C(\delta,n,\tilde{m})\;.$
(35)

According to Lemma 1, the Gibbs posterior $Q^{*}(S_{i},P)$ is the minimizer of
(32), in particular $\forall P\in\mathcal{M}(\mathcal{H}),\forall i=1,...,n:$

$Q^{*}(S_{i},P)=\frac{P(h)e^{-\beta\hat{\mathcal{L}}(h,S_{i})}}{Z_{\beta}(S_{i},P)}=\operatorname*{arg\,min}_{Q\in\mathcal{M}(\mathcal{H})}\mathbb{E}_{h\sim
Q}\left[\hat{\mathcal{L}}(h,S_{i})\right]+\frac{1}{\beta}D_{KL}(Q||P)\;.$ (36)

Hence, we can write

$\displaystyle\mathcal{L}(\mathcal{Q},\mathcal{T})\leq$
$\displaystyle-\frac{1}{n}\sum_{i=1}^{n}\frac{1}{\beta}\mathbb{E}_{P\sim\mathcal{Q}}\left[\ln
Z_{\beta}(S_{i},P)\right]+\left(\frac{1}{\lambda}+\frac{1}{n\beta}\right)D_{KL}(\mathcal{Q}||\mathcal{P})+C(\delta,\lambda,\beta)$
(37) $\displaystyle=$
$\displaystyle~{}\frac{1}{n}\sum_{i=1}^{n}\mathbb{E}_{P\sim\mathcal{Q}}\left[\min_{Q\in\mathcal{M}(\mathcal{H})}\hat{\mathcal{L}}(Q,S_{i})+\frac{1}{\beta}D_{KL}(Q||P)\right]$
(38)
$\displaystyle+\left(\frac{1}{\lambda}+\frac{1}{n\beta}\right)D_{KL}(\mathcal{Q}||\mathcal{P})+C(\delta,n,\tilde{m})$
(39) $\displaystyle\leq$
$\displaystyle\frac{1}{n}\sum_{i=1}^{n}\mathbb{E}_{P\sim\mathcal{Q}}\left[\hat{\mathcal{L}}(Q,S_{i})+\frac{1}{\beta}D_{KL}(Q||P)\right]$
(40)
$\displaystyle+\left(\frac{1}{\lambda}+\frac{1}{n\beta}\right)D_{KL}(\mathcal{Q}||\mathcal{P})+C(\delta,\lambda,\beta)$
(41) $\displaystyle=$
$\displaystyle~{}\hat{\mathcal{L}}(\mathcal{Q},S_{1},...,S_{n})+\left(\frac{1}{\lambda}+\frac{1}{n\beta}\right)D_{KL}(\mathcal{Q}||\mathcal{P})$
(42)
$\displaystyle+\frac{1}{n}\sum_{i=1}^{n}\frac{1}{\beta}\mathbb{E}_{P\sim\mathcal{Q}}\left[D_{KL}(Q_{i}||P)\right]+C(\delta,\lambda,\beta)\;,$
(43)

which proves that the bound for Gibbs-optimal base learners in (35) and (5) is
tighter than the bound in Theorem 2 which holds uniformly for all
$Q\in\mathcal{M}(\mathcal{H})$.

###  A.3 Proof of Proposition 1: PAC-Optimal Hyper-Posterior

An objective function corresponding to (5) reads as

$J(\mathcal{Q})=-\mathbb{E}_{\mathcal{Q}}\left[\frac{\lambda}{n\beta+\lambda}\sum_{i=1}^{n}\ln
Z(S_{i},P)\right]+D_{KL}(\mathcal{Q}||\mathcal{P})\;.$ (44)

To obtain $J(\mathcal{Q})$, we omit all additive terms from (5) that do not
depend on $\mathcal{Q}$ and multiply by the scaling factor $\frac{\lambda
n\beta}{n\beta+\lambda}$. Since the described transformations are monotone,
the minimizing distribution of $J(\mathcal{Q})$, that is,

$\mathcal{Q}^{*}=\operatorname*{arg\,min}_{\mathcal{Q}\in\mathcal{M}(\mathcal{M}(\mathcal{H}))}J(\mathcal{Q})\;,$
(45)

is also the minimizer of (5). More importantly, $J(\mathcal{Q})$ is
structurally similar to the generic minimization problem in (3). Hence, we can
invoke Lemma 1 with $A=\mathcal{M}(\mathcal{H})$, $g(a)=-\sum_{i=1}^{n}\ln
Z(S_{i},P)$, $\beta=\frac{1}{\sqrt{n\tilde{m}}+1}$, to show that the optimal
hyper-posterior is

$\mathcal{Q}^{*}(P)=\frac{\mathcal{P}(P)\exp\left(\frac{\lambda}{n\beta+\lambda}\sum_{i=1}^{n}\ln
Z_{\beta}(S_{i},P)\right)}{Z^{\text{{II}}}(S_{1},...,S_{n},\mathcal{P})}\;,$
(46)

wherein

$\displaystyle
Z^{\text{{II}}}(S_{1},...,S_{n},\mathcal{P})=\mathbb{E}_{P\sim\mathcal{P}}\left[\exp\left(\frac{\lambda}{n\beta+\lambda}\sum_{i=1}^{n}\ln
Z_{\beta}(S_{i},P)\right)\right]\;.$

$\hfill\Box$

Technically, this concludes the proof of Proposition 1. However, we want to
remark the following result:

If we choose $\mathcal{Q}=\mathcal{Q}^{*}$, the PAC-Bayes bound in (5) can be
expressed in terms of the meta-level partition function $Z^{\text{{II}}}$,
that is,

$\displaystyle\mathcal{L}(\mathcal{Q},\mathcal{T})$
$\displaystyle\leq-\left(\frac{1}{\lambda}+\frac{1}{n\beta}\right)\ln
Z^{\text{{II}}}(S_{1},...,S_{n},\mathcal{P})+C(\delta,\lambda,\beta)\;.$ (47)

We omit a detailed derivation of (47) since it is similar to the one for
Corollary 1.

##  Appendix B Gaussian process regression

In GP regression, each data point corresponds to a feature-target tuple
$z_{i,j}=(x_{i,j},y_{i,j})\in\mathbb{R}^{d}\times\mathbb{R}$. For the $i$-th
dataset, we write $S_{i}=(\mathbf{X}_{i},\mathbf{y}_{i})$, where
$\mathbf{X}_{i}=(x_{i,1},...,x_{i,m_{i}})^{\top}$ and
$\mathbf{y}_{i}=(y_{i,1},...,y_{i,m_{i}})^{\top}$. GPs are a Bayesian method
in which the prior
$P_{\phi}(h)=\mathcal{GP}\left(h|m_{\phi}(x),k_{\phi}(x,x^{\prime})\right)$ is
specified by a positive definite kernel
$k_{\phi}:\mathcal{X}\times\mathcal{X}\rightarrow\mathbb{R}$ and a mean
function $m_{\phi}:\mathcal{X}\rightarrow\mathbb{R}$.

The empirical loss under the GP posterior $Q^{*}$ coincides with the negative
log-likelihood of regression targets $\mathbf{y}_{i}$, that is,
$\hat{\mathcal{L}}(Q^{*},S_{i})=-\frac{1}{m_{i}}\ln
p(\mathbf{y}_{i}|\mathbf{X}_{i})$. Under a Gaussian likelihood
$p(\mathbf{y}|\mathbf{h})=\mathcal{N}(\mathbf{y};h(\mathbf{x}),\sigma^{2}I)$,
the marginal log-likelihood $\ln Z(S_{i},P_{\phi})=\ln
p(\mathbf{y}_{i}|\mathbf{X}_{i},\phi)$ can be computed in closed form as

$\displaystyle\begin{split}\ln
p(\mathbf{y}|\mathbf{X},\phi)=&-\frac{1}{2}\left(\mathbf{y}-m_{\mathbf{X},\phi})\right)^{\top}\tilde{K}_{\mathbf{X},\phi}^{-1}\left(\mathbf{y}-m_{\mathbf{X},\phi}\right)-\frac{1}{2}\ln|\tilde{K}_{\mathbf{X},\phi}|-\frac{m_{i}}{2}\ln
2\pi\;,\end{split}$ (48)

where $\tilde{K}_{\mathbf{X},\phi}=K_{\mathbf{X},\phi}+\sigma^{2}I$, with the
kernel matrix $K_{\mathbf{X},\phi}=(k_{\phi}(x_{l},x_{k}))^{m_{i}}_{l,k=1}$,
observation noise variance $\sigma^{2}$, and mean vector
$m_{\mathbf{X},\phi}=(m_{\phi}(x_{1}),...,m_{\phi}(x_{m_{i}}))^{\top}$.

Previous work on Bayesian model selection in the context of GPs argues that
the log-determinant $\frac{1}{2}\ln|\tilde{K}_{\mathbf{X},\phi}|$ in the
marginal log-likelihood (48) acts as a complexity penalty (Rasmussen &
Ghahramani, 2001; Rasmussen & Williams, 2006). However, we suspect that this
complexity regularization is only effective if the class of considered priors
is restrictive, for instance if we only optimize a small number of parameters
such as the length- and output scale of a squared exponential kernel. If we
consider expressive classes of GP priors (e.g., our setup where the mean and
kernel function are neural networks), such a complexity penalty could be
insufficient to avoid meta-overfitting. Indeed, this is what we also observe
in our experiments (see Sec. 5.3).

##  Appendix C PACOH-GP: Meta-Learning of GP priors

In this section, we provide further details on PACOH-GP, introduced in Section
5 of the paper and employed in our experiments. Following Section 5.3, we
instantiate our framework with GP base learners. Since we are interested in
meta-learning, we define the mean and kernel function both as parametric
functions. Similar to Wilson et al. (2016) and Fortuin & Rätsch (2019), we
instantiate $m_{\phi}$ and $k_{\phi}$ as neural networks, where the parameter
vector $\phi$ can be meta-learned. To ensure the positive-definiteness of the
kernel, we use the neural network as feature map $\Phi_{\phi}(x)$ on top of
which we apply a squared exponential (SE) kernel. Accordingly, the parametric
kernel reads as
$k_{\phi}(x,x^{\prime})=\frac{1}{2}\exp\left(-||\Phi_{\phi}(x)-\Phi_{\phi}(x^{\prime})||_{2}^{2}\right)$.
Both $m_{\phi}(x)$ and $\Phi_{\phi}(x)$ are fully-connected neural networks
with 4 layers with each 32 neurons and $\tanh$ non-linearities. The parameter
vector $\phi$ represents the weights and biases of both neural networks. As
hyper-prior we choose a zero-mean isotropic Gaussian, that is,
$\mathcal{P}(\phi)=\mathcal{N}(0,\sigma_{\mathcal{P}}^{2}I)$. Further, we
choose $\lambda=n$ and $\beta_{i}=m_{i}$

###  C.1 Meta-training with PACOH-GP

SVGD (Liu & Wang, 2016) approximates $\mathcal{Q}^{*}$ as a set of particles
$\hat{\mathcal{Q}}=\\{P_{1},...,P_{K}\\}$. In our described setup, each
particle corresponds to the parameters of the GP prior, that is,
$\hat{\mathcal{Q}}=\\{\phi_{1},...,\phi_{K}\\}$. Initially, we sample random
priors $\phi_{k}\sim\mathcal{P}$ from our hyper-posterior. Then, the SVGD
iteratively transports the set of particles to match $\mathcal{Q}^{*}$, by
applying a form of functional gradient descent that minimizes
$D_{KL}(\hat{\mathcal{Q}}|\mathcal{Q}^{*})$ in the reproducing kernel Hilbert
space induced by a kernel function $k(\cdot,\cdot)$. We choose a squared
exponential kernel with length scale (hyper-)parameter $\ell$, that is,
$k(\phi,\phi^{\prime})=\
\exp\left(-\frac{||\phi-\phi^{\prime}||_{2}^{2}}{2\ell}\right)$. In each
iteration, the particles are updated by

$\phi_{k}\leftarrow\phi_{k}+\eta_{t}\psi^{*}(\phi_{k})~{},\quad\text{with}\quad\psi^{*}(\phi)=\frac{1}{K}\sum_{l=1}^{K}\left[k(\phi_{l},\phi)\nabla_{\phi_{l}}\ln\mathcal{Q}^{*}(\phi_{l})+\nabla_{\phi_{l}}k(\phi_{l},\phi)\right]\;.$

Here, we can again estimate $\nabla_{\phi_{l}}\ln\mathcal{Q}^{*}(\phi_{l})$
with a mini-batch of $H$ datasets $S_{1},...,S_{H}$:

$\nabla_{\phi_{l}}\ln\mathcal{Q}^{*}(\phi_{l})=\frac{n}{H}\cdot\sum_{h=1}^{H}\frac{1}{m_{h}+1}\nabla_{\phi_{l}}\ln
Z(S_{h},P_{\phi_{l}})+\nabla_{\phi_{l}}\ln\mathcal{P}(\phi_{l})\;.$

Importantly, $\nabla_{\phi_{l}}\ln\mathcal{Q}^{*}(\phi_{l})$ does not depend
on $Z^{\text{{II}}}$ which makes SVGD tractable. Algorithm 2 summarizes the
meta-training method for GP priors.

Algorithm 2 PACOH-GP: mini-batched meta-training

Input: hyper-prior $\mathcal{P}$, datasets $S_{1},...,S_{n}$

Input: SVGD kernel function $k(\cdot,\cdot)$, SVGD step size $\eta$, number of
particles $K$

$\\{\phi_{1},...,\phi_{K}\\}\sim\mathcal{P}$ // Initialize prior particles

while not converged do

$\\{T_{1},...,T_{n_{bs}}\\}\subseteq[n]$ // sample $n_{bs}$ tasks uniformly at
random

for $k=1,...,K$ do

for $i=1,...,n_{bs}$ do

$\ln
Z_{m_{i}}(S_{i},P_{\phi_{k}})\leftarrow-\frac{1}{2}\left(\mathbf{y}_{i}-m_{\mathbf{X}_{i},\phi_{k}}\right)^{\top}\tilde{K}_{\mathbf{X}_{i},\phi_{k}}^{-1}\left(\mathbf{y}_{i}-m_{\mathbf{X}_{i},\phi_{k}}\right)-\frac{1}{2}\ln|\tilde{K}_{\mathbf{X}_{i},\phi_{k}}|-\frac{m_{i}}{2}\ln
2\pi$ // compute MLL

$\nabla_{\phi_{k}}\ln\tilde{\mathcal{Q}}^{*}(\phi_{k})\leftarrow\nabla_{\phi_{k}}\ln\mathcal{P}(\phi_{k})+\frac{n}{n_{bs}}\sum_{i=1}^{n_{bs}}\frac{1}{m_{i}+1}\nabla_{\phi_{k}}\ln
Z_{m_{i}}(S_{i},P_{\phi_{k}})$ // compute score

$\phi_{k}\leftarrow\phi_{k}+\frac{\eta}{K}\sum_{k^{\prime}=1}^{K}\left[k(\phi_{k^{\prime}},\phi_{k})\nabla_{\phi_{k^{\prime}}}\ln\tilde{\mathcal{Q}}^{*}(\phi_{k^{\prime}})+\nabla_{\phi_{k^{\prime}}}k(\phi_{k^{\prime}},\phi_{k})\right]\forall{k\in[K]}$
// SVGD update

Output: set of GP priors
$\\{\mathcal{GP}\left(m_{\phi_{1}}(x),k_{\phi_{1}}(x,x^{\prime})\right),...,\mathcal{GP}\left(m_{\phi_{K}}(x),k_{\phi_{K}}(x,x^{\prime})\right)\\}$

###  C.2 Meta-Testing / Target-Training with PACOH-GP

Meta-learning with PACOH, as described above, gives us an approximation of
$\mathcal{Q}^{*}$. In target-testing (see Figure 1), the base learner is
instantiated with the meta-learned prior $P_{\phi}$, receives a dataset
$\tilde{S}=(\tilde{\mathbf{X}},\tilde{\mathbf{y}})$ from an unseen task
$\mathcal{D}\sim\mathcal{T}$ and outputs a posterior $Q$ as product of its
inference. In our GP setup, $Q$ is the GP posterior and the predictive
distribution $\hat{p}(y^{*}|x^{*},\tilde{\mathbf{X}},\tilde{\mathbf{y}},\phi)$
is a Gaussian (for details see Rasmussen & Williams, 2006).

Since the meta-learner outputs a distribution over priors, that is, the hyper-
posterior $\mathcal{Q}$, we may obtain different predictions for different
priors $P_{\phi}\sim\mathcal{Q}$, sampled from the hyper-posterior. To obtain
a predictive distribution under our meta-learned hyper-posterior, we
empirically marginalize $\mathcal{Q}$. That is, we draw a set of prior
parameters $\phi_{1},...,\phi_{K}\sim\mathcal{Q}$ from the hyper-posterior,
compute their respective predictive distributions
$\hat{p}(y^{*}|x^{*},\tilde{\mathbf{X}},\tilde{\mathbf{y}},\phi_{k})$ and form
an equally weighted mixture:

$\hat{p}(y^{*}|x^{*},\tilde{\mathbf{X}},\tilde{\mathbf{y}},\mathcal{Q})=\mathbb{E}_{\phi\sim\mathcal{Q}}\left[\hat{p}(y^{*}|x^{*},\tilde{\mathbf{X}},\tilde{\mathbf{y}},\phi)\right]\approx\frac{1}{K}\sum_{k=0}^{K}\hat{p}(y^{*}|x^{*},\tilde{\mathbf{X}},\tilde{\mathbf{y}},\phi_{k})~{},\quad\phi_{k}\sim\mathcal{Q}$
(49)

Since we are concerned with GPs, (49) coincides with a mixture of Gaussians.
As one would expect, the mean prediction under $\mathcal{Q}$ (i.e., the
expectation of (49)), is the average of the mean predictions corresponding to
the sampled prior parameters $\phi_{1},...,\phi_{K}$. In case of PACOH-VI, we
sample $K=100$ priors from the variational hyper-posterior
$\tilde{\mathcal{Q}}$. For PACOH-SVGD, samples from the hyper-posterior
correspond to the $K=10$ particles. PACOH-MAP can be viewed as a special case
of SVGD with $K=1$, that is, only one particle. Thus,
$\hat{p}(y^{*}|x^{*},\tilde{\mathbf{X}},\tilde{\mathbf{y}},\mathcal{Q})\approx\hat{p}(y^{*}|x^{*},\tilde{\mathbf{X}},\tilde{\mathbf{y}},\phi^{MAP})$
is a single Gaussian.

##  Appendix D PACOH-NN: Meta-Learning BNN priors

In this section, we summarize and further discuss our proposed meta-learning
algorithm _PACOH-NN_. An overview of our proposed framework is illustrated in
Figure 1. Overall, it consists of two stages _meta-training_ and _meta-
testing_ which we explain in more details in the following.

###  D.1 Meta-training

The hyper-posterior distribution $\mathcal{Q}$ that minimizes the upper bound
on the transfer error is given by

$\mathcal{Q}^{*}(P)=\frac{\mathcal{P}(P)\exp\left(\sum_{i=1}^{n}\frac{\lambda}{n\beta_{i}+\lambda}\ln\tilde{Z}(S_{i},P)\right)}{Z^{\text{{II}}}(S_{1},...,S_{n},\mathcal{P})}\vspace{-2pt}$
(50)

In that, we no longer assume that $m=m_{i}~{}\forall i=1,...,n$ which was done
in the theory section to maintain notational brevity. Thus, we use a different
$\beta_{i}$ for each och the tasks as we want to set $\beta_{i}=m_{i}$ or
$\beta_{i}=\sqrt{m_{i}}$. Provided with a set of datasets $S_{1},...,S_{n}$,
the meta-learner minimizes the respective meta-objective, in the case of
_PACOH-SVGD_ , by performing SVGD on the $\mathcal{Q}^{*}$. Algorithm 3
outlines the required steps in more detail.

Algorithm 3 PACOH-NN: meta-training

Input: hyper-prior $\mathcal{P}$, datasets $S_{1},...,S_{n}$, kernel
$k(\cdot,\cdot)$, step size $\eta$, number of particles $K$

$\\{\phi_{1},...,\phi_{K}\\}\sim\mathcal{P}$ // Initialize prior particles

while not converged do

for $k=1,...,K$ do

$\\{\theta_{1},...,\theta_{L}\\}\sim P_{\phi_{k}}$ // sample NN-parameters
from prior

for $i=1,...,n$ do

$\ln\tilde{Z}(S_{i},P_{\phi_{k}})\leftarrow\text{LSE}_{l=1}^{L}\left(-\beta_{i}\hat{\mathcal{L}}(\theta_{l},S_{i})\right)-\ln
L$ // estimate generalized MLL

$\nabla_{\phi_{k}}\ln\tilde{\mathcal{Q}}^{*}(\phi_{k})\leftarrow\nabla_{\phi_{k}}\ln\mathcal{P}(\phi_{k})+\sum_{i=1}^{n}\frac{\lambda}{n\beta_{i}+\lambda}\nabla_{\phi_{k}}\ln\tilde{Z}(S_{i},P_{\phi_{k}})$
// compute score

$\forall
k\in[K]:\phi_{k}\leftarrow\phi_{k}+\frac{\eta}{K}\sum_{k^{\prime}=1}^{K}\left[k(\phi_{k^{\prime}},\phi_{k})\nabla_{\phi_{k^{\prime}}}\ln\tilde{\mathcal{Q}}^{*}(\phi_{k^{\prime}})+\nabla_{\phi_{k^{\prime}}}k(\phi_{k^{\prime}},\phi_{k})\right]$
// SVGD update

Output: set of priors $\\{P_{\phi_{1}},...,P_{\phi_{K}}\\}$

Alternatively, to estimate the score of
$\nabla_{\phi_{k}}\tilde{\mathcal{Q}}^{*}(\phi_{k})$ we can use mini-batching
at both the task and the dataset level. Specifically, for a given meta-batch
size of $n_{bs}$ and a batch size of $m_{bs}$, we get Algorithm 4.

Algorithm 4 PACOH-NN-SVGD: mini-batched meta-training

Input: hyper-prior $\mathcal{P}$, datasets $S_{1},...,S_{n}$

Input: kernel function $k(\cdot,\cdot)$, SVGD step size $\eta$, number of
particles $K$

$\\{\phi_{1},...,\phi_{K}\\}\sim\mathcal{P}$ // Initialize prior particles

while not converged do

$\\{T_{1},...,T_{n_{bs}}\\}\subseteq[n]$ // sample $n_{bs}$ tasks uniformly at
random

for $i=1,...,n_{bs}$ do

$\tilde{S}_{i}\leftarrow\\{z_{1},...,z_{m_{bs}}\\}\subseteq S_{T_{i}}$ //
sample $m_{bs}$ datapoints from $S_{T_{i}}$ uniformly at random

for $k=1,...,K$ do

$\\{\theta_{1},...,\theta_{L}\\}\sim P_{\phi_{k}}$ // sample NN-parameters
from prior

for $i=1,...,n_{bs}$ do

$\ln\tilde{Z}(\tilde{S}_{i},P_{\phi_{k}})\leftarrow\text{LSE}_{l=1}^{L}\left(-\beta_{i}\hat{\mathcal{L}}(\theta_{l},\tilde{S}_{i})\right)-\ln
L$ // estimate generalized MLL

$\nabla_{\phi_{k}}\ln\tilde{\mathcal{Q}}^{*}(\phi_{k})\leftarrow\nabla_{\phi_{k}}\ln\mathcal{P}(\phi_{k})+\frac{n}{n_{bs}}\sum_{i=1}^{n_{bs}}\frac{\lambda}{n\beta_{i}+\lambda}\nabla_{\phi_{k}}\ln\tilde{Z}(S_{i},P_{\phi_{k}})$
// compute score

$\phi_{k}\leftarrow\phi_{k}+\frac{\eta}{K}\sum_{k^{\prime}=1}^{K}\left[k(\phi_{k^{\prime}},\phi_{k})\nabla_{\phi_{k^{\prime}}}\ln\tilde{\mathcal{Q}}^{*}(\phi_{k^{\prime}})+\nabla_{\phi_{k^{\prime}}}k(\phi_{k^{\prime}},\phi_{k})\right]\forall{k\in[K]}$
// SVGD update

Output: set of priors $\\{P_{\phi_{1}},...,P_{\phi_{K}}\\}$

###  D.2 Meta-testing

The meta-learned prior knowledge is now deployed by a base learner. The base
learner is given a training dataset $\tilde{S}\sim\mathcal{D}$ pertaining to
an unseen task $\tau=(\mathcal{D},m)\sim\mathcal{T}$. With the purpose of
approximating the generalized Bayesian posterior $Q^{*}(S,P)$, the base
learner performs (normal) posterior inference. Algorithm 5 details the steps
of the approximating procedure – referred to as _target training_ – when
performed via SVGD. For a data point $x^{*}$, the respective predictor outputs
a probability distribution given as
$\tilde{p}(y^{*}|x^{*},\tilde{S})\leftarrow\frac{1}{K\cdot
L}\sum_{k=1}^{K}\sum_{l=1}^{L}p(y^{*}|h_{\theta^{k}_{l}}(x^{*}))$. We evaluate
the quality of the predictions on a held-out test dataset
$\tilde{S}^{*}\sim\mathcal{D}$ from the same task, in a _target testing_ phase
(see Appendix E.2).

Algorithm 5 PACOH-NN: meta-testing

Input: set of priors $\\{P_{\phi_{1}},...,P_{\phi_{K}}\\}$, target training
dataset $\tilde{S}$, evaluation point $x^{*}$

Input: kernel function $k(\cdot,\cdot)$, SVGD step size $\nu$, number of
particles $L$

for $k=1,...,K$ do

$\\{\theta^{k}_{1},...,\theta^{k}_{L}\\}\sim P_{\phi_{k}}$ // initialize NN
posterior particles from $k$-th prior

while not converged do

for $l=1,...,L$ do

$\nabla_{\theta^{k}_{l}}Q^{*}(\theta^{k}_{l}))\leftarrow\nabla_{\theta^{k}_{l}}\ln
P_{\phi_{k}}(\theta^{k}_{l}))+\beta~{}\nabla_{\theta^{k}_{l}}\mathcal{L}(l,\tilde{S})$
// compute score

$\theta^{k}_{l}\leftarrow\theta^{k}_{l}+\frac{\nu}{L}\sum_{l^{\prime}=1}^{L}\left[k(\theta^{k}_{l^{\prime}},\theta^{k}_{l})\nabla_{\theta^{k}_{l^{\prime}}}\ln
Q^{*}(\theta^{k}_{l^{\prime}})+\nabla_{\theta^{k}_{l^{\prime}}}k(\theta^{k}_{l^{\prime}},\theta^{k}_{l})\right]\forall{l\in[L]}$
// update particles

Output: a set of NN parameters
$\bigcup_{k=1}^{K}\\{\theta_{1}^{k}\,...,\theta_{L}^{k}\\}$

###  D.3 Properties of the score estimator

Since the marginal log-likelihood of BNNs is intractable, we have replaced it
by a numerically stable Monte Carlo estimator
$\ln\tilde{Z}_{\beta}(S_{i},P_{\phi})$ in (9), in particular

$\ln\tilde{Z}_{\beta}(S_{i},P_{\phi}):=\ln\frac{1}{L}\sum_{l=1}^{L}e^{-\beta\hat{\mathcal{L}}(\theta_{l},S_{i})}=\text{LSE}_{l=1}^{L}\left(-\beta\hat{\mathcal{L}}(\theta_{l},S_{i})\right)-\ln
L~{},~{}~{}\theta_{l}\sim P_{\phi}~{}.$ (51)

Since the Monte Carlo estimator involves approximating an expectation of an
exponential, it is not unbiased. However, we can show that replacing $\ln
Z_{\beta}(S_{i},P_{\phi})$ by the estimator
$\ln\tilde{Z}_{\beta}(S_{i},P_{\phi})$, we still minimize a valid upper bound
on the transfer error (see Proposition 2).

######  Proposition 2.

In expectation, replacing $\ln Z_{\beta}(S_{i},P_{\phi})$ in (5) by the Monte
Carlo estimate
$\ln\tilde{Z}_{\beta}(S_{i},P):=\ln\frac{1}{L}\sum_{l=1}^{L}e^{-\beta\hat{\mathcal{L}}(\theta_{l},S_{i})},~{}\theta_{l}\sim
P$ still yields an valid upper bound of the transfer error. In particular, it
holds that

$\displaystyle\mathcal{L}(\mathcal{Q},\mathcal{T})$
$\displaystyle\leq-\frac{1}{n}\sum_{i=1}^{n}\frac{1}{\beta}\mathbb{E}_{P\sim\mathcal{Q}}\left[\ln
Z(S_{i},P)\right]+\left(\frac{1}{\lambda}+\frac{1}{n\beta}\right)D_{KL}(\mathcal{Q}||\mathcal{P})+C(\delta,n,\tilde{m})$
(52)
$\displaystyle\begin{split}&\leq-\frac{1}{n}\sum_{i=1}^{n}\frac{1}{\beta}\mathbb{E}_{P\sim\mathcal{Q}}\left[\mathbb{E}_{\theta_{1},...,\theta_{L}\sim
P}\left[\ln\tilde{Z}(S_{i},P)\right]\right]\\\
&\quad~{}+\left(\frac{1}{\lambda}+\frac{1}{n\beta}\right)D_{KL}(\mathcal{Q}||\mathcal{P})+C(\delta,\lambda,\beta).\end{split}$
(53)

###### Proof.

Firsts, we show that:

$\displaystyle\mathbb{E}_{\theta_{1},...,\theta_{L}\sim
P}\left[\ln\tilde{Z}_{\beta}(S_{i},P)\right]$
$\displaystyle=\mathbb{E}_{\theta_{1},...,\theta_{L}\sim
P}\left[\ln\frac{1}{L}\sum_{l=1}^{L}e^{-\beta\hat{\mathcal{L}}(\theta_{l},S_{i})}\right]$
$\displaystyle\leq\ln\frac{1}{L}\sum_{l=1}^{L}\mathbb{E}_{\theta_{l}\sim
P}\left[e^{-\beta\hat{\mathcal{L}}(\theta_{l},S_{i})}\right]$
$\displaystyle=\ln\mathbb{E}_{\theta\sim
P}\left[e^{-\beta\hat{\mathcal{L}}(\theta,S_{i})}\right]$ $\displaystyle=\ln
Z_{\beta}(S_{i},P)$ (54)

which follows directly from Jensen’s inequality and the concavity of the
logarithm. Now, Proposition 2 follows directly from (D.3). ∎

In fact, by the law of large numbers, it is straightforward to show that as
$L\rightarrow\infty$, the $\ln\tilde{Z}(S_{i},P)\xrightarrow[]{\text{a.s.}}\ln
Z(S_{i},P)$, that is, the estimator becomes asymptotically unbiased and we
recover the original PAC-Bayesian bound (i.e. (LABEL:eq:estimator_upper_bound)
$\xrightarrow[]{\text{a.s.}}$ (52)). Also it is noteworthy that the bound in
(LABEL:eq:estimator_upper_bound) we get by our estimator is, in expectation,
tighter than the upper bound when using the naive estimator

$\ln\hat{Z}_{\beta}(S_{i},P):=-\beta~{}\frac{1}{L}\sum_{l=1}^{L}\hat{\mathcal{L}}(\theta_{l},S_{i})\quad\theta_{l}\sim
P_{\phi}$

which can be obtained by applying Jensen’s inequality to
$\ln\mathbb{E}_{\theta\sim
P_{\phi}}\left[e^{-\beta\hat{\mathcal{L}}(\theta,S_{i})}\right]$. In the edge
case $L=1$ our LSE estimator $\ln\tilde{Z}_{\beta}(S_{i},P)$ falls back to
this naive estimator and coincides in expectation with
$\mathbb{E}[\ln\hat{Z}_{\beta}(S_{i},P)]=-\beta~{}\mathbb{E}_{\theta\sim
P}\hat{\mathcal{L}}(\theta_{l},S_{i})$. As a result, we effectively minimize
the looser upper bound

$\displaystyle\mathcal{L}(\mathcal{Q},\mathcal{T})$
$\displaystyle\leq\frac{1}{n}\sum_{i=1}^{n}\mathbb{E}_{\theta\sim
P}\left[\hat{\mathcal{L}}(\theta,S_{i})\right]+\left(\frac{1}{\lambda}+\frac{1}{n\beta}\right)D_{KL}(\mathcal{Q}||\mathcal{P})+C(\delta,n,\tilde{m}).$
(55) $\displaystyle=\mathbb{E}_{\theta\sim
P}\left[\frac{1}{n}\sum_{i=1}^{n}\frac{1}{m_{i}}\sum_{j=1}^{m_{i}}-\ln
p(y_{ij}|x_{ij},\theta)\right]+\left(\frac{1}{\lambda}+\frac{1}{n\beta}\right)D_{KL}(\mathcal{Q}||\mathcal{P})+C(\delta,n,\tilde{m})$
(56)

As we can see from (56), the boundaries between the tasks vanish in the edge
case of $L=1$, that is, all data-points are treated as if they would belong to
one dataset. This suggests that $L$ should be chosen greater than one. In our
experiments, we used $L=5$ and found the corresponding approximation to be
sufficient.

##  Appendix E Experiments

###  E.1 Meta-Learning Environments

In this section, we provide further details on the meta-learning environments
used in Section 5.3. Information about the numbers of tasks and samples in the
respective environments can be found in Table S1.

| Sinusoid | Cauchy | SwissFEL | Physionet | Berkeley
---|---|---|---|---|---
$n$ | 20 | 20 | 5 | 100 | 36
$m_{i}$ | 5 | 20 | 200 | 4 - 24 | 288
Table S1: Number of tasks $n$ and samples per task $m_{i}$ for the different
meta-learning environments.

####  E.1.1 Sinusoids

Each task of the sinusoid environment corresponds to a parametric function

$f_{a,b,c,\beta}(x)=\beta*x+a*\sin(1.5*(x-b))+c\;,$ (57)

which, in essence, consists of an affine as well as a sinusoid function. Tasks
differ in the function parameters $(a,b,c,\beta)$ that are sampled from the
task environment $\mathcal{T}$ as follows:

$a\sim\mathcal{U}(0.7,1.3),\quad b\sim\mathcal{N}(0,0.1^{2}),\quad
c\sim\mathcal{N}(5.0,0.1^{2}),\quad\beta\sim\mathcal{N}(0.5,0.2^{2})\;.$ (58)

(a) Sinusoid tasks

(b) Cauchy tasks

Figure S1: Depiction of tasks (i.e., functions) sampled from the Sinusoid and
Cauchy task environment, respectively. Note that the Cauchy task environment
is two-dimensional ($\text{dim}(\mathcal{X})=2$), while (b) displays a one-
dimensional projection.

Figure 1(a) depicts functions $f_{a,b,c,\beta}$ with parameters sampled
according to (58). To draw training samples from each task, we draw $x$
uniformly from $\mathcal{U}(-5,5)$ and add Gaussian noise with standard
deviation $0.1$ to the function values $f(x)$:

$x\sim\mathcal{U}(-5,5)~{},\qquad
y\sim\mathcal{N}(f_{a,b,c,\beta}(x),0.1^{2})\;.$ (59)

####  E.1.2 Cauchy

Each task of the Cauchy environment can be interpreted as a two dimensional
mixture of Cauchy distributions plus a function sampled from a Gaussian
process prior with zero mean and SE kernel function
$k(x,x^{\prime})=\exp\left(\frac{||x-x^{\prime}||_{2}^{2}}{2l}\right)$ with
$l=0.2$. The (unnormalized) mixture of Cauchy densities is defined as:

$m(x)=\frac{6}{\pi\cdot(1+||x-\mu_{1}||^{2}_{2})}+\frac{3}{\pi\cdot(1+||x-\mu_{2}||^{2}_{2})}\;,$
(60)

with $\mu_{1}=(-1,-1)^{\top}$ and $\mu_{2}=(2,2)^{\top}$.

Functions from the task environments are sampled as follows:

$f(x)=m(x)+g(x)~{},\qquad g\sim\mathcal{GP}(0,k(x,x^{\prime}))\;.$ (61)

Figure 1(b) depicts a one-dimensional projection of functions sampled
according to (61). To draw training samples from each task, we draw $x$ from a
truncated normal distribution and add Gaussian noise with standard deviation
$0.05$ to the function values $f(x)$:

$x:=\min\\{\max\\{\tilde{x},2\\},-3\\}~{},~{}~{}\tilde{x}\sim\mathcal{N}(0,2.5^{2})~{},\qquad
y\sim\mathcal{N}(f(x),0.05^{2})\;.$ (62)

####  E.1.3 SwissFEL

Free-electron lasers (FELs) accelerate electrons to very high speed in order
to generate shortly pulsed laser beams with wavelengths in the X-ray spectrum.
These X-ray pulses can be used to map nanometer scale structures, thus
facilitating experiments in molecular biology and material science. The
accelerator and the electron beam line of a FEL consist of multiple magnets
and other adjustable components, each of which has several parameters that
experts adjust to maximize the pulse energy (Kirschner et al., 2019a). Due do
different operational modes, parameter drift, and changing (latent)
conditions, the laser’s pulse energy function, in response to its parameters,
changes across time. As a result, optimizing the laser’s parameters is a
recurrent task.

Figure S2: Accelerator of the Swiss Free-Electron Laser (SwissFEL).

Overall, our meta-learning environment consists of different parameter
optimization runs (i.e., tasks) on the SwissFEL, an 800 meter long laser
located in Switzerland (Milne et al., 2017). A picture of the SwissFEL is
shown in Figure S2. The input space, corresponding to the laser’s parameters,
has 12 dimensions whereas the regression target is the pulse energy
(1-dimensional). For details on the individual parameters, we refer to
Kirschner et al. (2019b). For each run, we have around 2000 data points. Since
these data-points are generated with online optimization methods, the data are
non-i.i.d. and get successively less diverse throughout the optimization. As
we are concerned with meta-learning with limited data and want to avoid issues
with highly dependent data points, we only take the first 400 data points per
run and split them into training and test subsets of size 200. Overall, we
have 9 runs (tasks) available. 5 of those runs are used for meta-training and
the remaining 4 runs are used for meta-testing.

####  E.1.4 PhysioNet

The 2012 Physionet competition (Silva et al., 2012) published an open-access
dataset of patient stays on the intensive care unit (ICU). Each patient stay
consists of a time series over 48 hours, where up to 37 clinical variables are
measured. The original task in the competition was binary classification of
patient mortality, but due to the large number of missing values (around 80 %
across all features), the dataset is also popular as a test bed for time
series prediction methods, especially using Gaussian processes (Fortuin et
al., 2019).

In this work, we treat each patient as a separate task and the different
clinical variables as different environments. We use the Glasgow coma scale
(GCS) and hematocrit value (HCT) as environments for our study, since they are
among the most frequently measured variables in this dataset. From the
dataset, we remove all patients where less than four measurements of CGS (and
HCT respectively) are available. From the remaining patients we use 100
patients for meta-training and 500 patients each for meta-validation and meta-
testing. Here, each patient corresponds to a task. Since the number of
available measurements differs across patients, the number of training points
$m_{i}$ ranges between 4 and 24.

####  E.1.5 Berkeley-Sensor

We use data from 46 sensors deployed in different locations at the Intel
Research lab in Berkeley (Madden, 2004). The dataset contains 4 days of data,
sampled at 10 minute intervals. Each task corresponds to one of the 46 sensors
and requires auto-regressive prediction, in particular, predicting the next
temperature measurement given the last 10 measurement values. In that, 36
sensors (tasks) with data for the first two days are use for meta-training and
whereas the remaining 10 sensors with data for the last two days are employed
for meta-testing. Note, that we separate meta-training and -testing data both
temporally and spatially since the data is non-i.i.d. For the meta-testing, we
use the 3rd day as context data, i.e. for target training and the remaining
data for target testing.

###  E.2 Experimental Methodology

In the following, we describe our experimental methodology and provide details
on how the empirical results reported in Section 5.3 were generated. Overall,
evaluating a meta-learner consists of two phases, meta-training and meta-
testing, outlined in Appendix D. The latter can be further sub-divided into
target training and target testing. Figure 1 illustrates these different
stages for our PAC-Bayesian meta-learning framework.

The outcome of the training procedure is an approximation for the generalized
Bayesian posterior $Q^{*}(S,P)$ (see Appendix ), pertaining to an unseen task
$\tau=(\mathcal{D},m)\sim\mathcal{T}$ from which we observe a dataset
$\tilde{S}\sim\mathcal{D}$. In target-testing, we evaluate its predictions on
a held-out test dataset $\tilde{S}^{*}\sim\mathcal{D}$ from the same task. For
PACOH-NN, NPs and MLAP the respective predictor outputs a probability
distribution $\hat{p}(y^{*}|x^{*},\tilde{S})$ for the $x^{*}$ in
$\tilde{S}^{*}$. The respective mean prediction corresponds to the expectation
of $\hat{p}$, that is $\hat{y}=\hat{\mathbb{E}}(y^{*}|x^{*},\tilde{S})$. In
the case of MAML, only a mean prediction is available. Based on the mean
predictions, we compute the root mean-squared error (RMSE):

$\text{RMSE}=\sqrt{\frac{1}{|\tilde{S}^{*}|}\sum_{(x^{*},y^{*})\in
S^{*}}(y^{*}-\hat{y})^{2}}\;.$ (63)

and the calibration error (see Appendix E.2.1). Note that unlike e.g. Rothfuss
et al. (2019a) who report the test log-likelihood, we aim to measure the
quality of mean predictions and the quality of uncertainty estimate
separately, thus reporting both RMSE and calibration error.

The described meta-training and meta-testing procedure is repeated for five
random seeds that influence both the initialization and gradient-estimates of
the concerned algorithms. The reported averages and standard deviations are
based on the results obtained for different seeds.

####  E.2.1 Calibration Error

The concept of calibration applies to probabilistic predictors that, given a
new target input $x_{i}$, produce a probability distribution
$\hat{p}(y_{i}|x_{i})$ over predicted target values $y_{i}$.

Calibration error for regression. Corresponding to the predictive density, we
denote a predictor’s cumulative density function (CDF) as
$\hat{F}(y_{j}|x_{j})=\int_{-\infty}^{y_{j}}\hat{p}(y|x_{i})dy$. For
confidence levels $0\leq q_{h}<...<q_{H}\leq 1$, we can compute the
corresponding empirical frequency

$\hat{q}_{h}=\frac{|\\{y_{j}~{}|~{}\hat{F}(y_{j}|x_{j})\leq
q_{h},j=1,...,m\\}|}{m}\;,$ (64)

based on dataset $S=\\{(x_{i},y_{i})\\}_{i=1}^{m}$ of $m$ samples. If we have
calibrated predictions we would expect that $\hat{q}_{h}\rightarrow q_{h}$ as
$m\rightarrow\infty$. Similar to (Kuleshov et al., 2018), we can define the
calibration error as a function of residuals $\hat{q}_{h}-q_{h}$, in
particular,

$\text{calib-err}=\frac{1}{H}\sum_{h=1}^{H}|\hat{q}_{h}-q_{h}|\;.$ (65)

Note that we while (Kuleshov et al., 2018) reports the average of squared
residuals $|\hat{q}_{h}-q_{h}|^{2}$, we report the average of absolute
residuals $|\hat{q}_{h}-q_{h}|$ in order to preserve the units and keep the
calibration error easier to interpret. In our experiments, we compute (65)
with $M=20$ equally spaced confidence levels between 0 and 1.

Calibration error for classification. Our classifiers output a categorical
probability distribution $\hat{p}(y=k|x)$ for $k=1,...,C$ where
$\mathcal{Y}=\\{1,...,C\\}$ with $C$ denoting the number of classes. The
prediction of the classifier is the most probable class label, i.e.,
$\hat{y_{j}}=\operatorname*{arg\,max}_{k}\hat{p}(y_{j}=k|x_{j})$.
Correspondingly, we denote the classifiers confidence in the prediction for
the input $x_{j}$ as $\hat{p}_{j}:=\hat{p}(y_{j}=\hat{y_{j}}|x_{j})$.
Following, the calibraton error definition of Guo et al. (2017), we group the
predictions into $H=20$ interval bins of size $1/H$ depending on their
prediction confidence. In particular, let
$B_{h}=\\{j~{}|~{}p_{j}\in\left(\frac{h-1}{H},\frac{h}{H}\right]\\}$ be the
set of indices of test points $\\{(x_{j},y_{j})\\}_{j=1}^{m}$ whose prediction
fall into the interval $\left(\frac{h-1}{H},\frac{h}{H}\right]\subseteq(0,1]$.
Formally, we define the accuracy of within a bin $B_{h}$ as

$\text{acc}(B_{h})=\frac{1}{|B_{h}|}\sum_{j\in
B_{h}}\mathbf{1}(\hat{y_{i}}=y_{j})$ (66)

and the average confidence within a bin as

$\text{conf}(B_{h})=\frac{1}{|B_{h}|}\sum_{j\in B_{h}}\hat{p}_{j}\;.$ (67)

If the classifier is calibrated, we expect that the confidence of the
classifier reflects it’s accuracy on unseen test data, that is,
$\text{acc}(B_{h})=\text{conf}(B_{h})~{}\forall h=1,....,H$. As proposed of
Guo et al. (2017), we use the expected calibration error (ECE) to quantify how
much the classifier deviates from this criterion: More precisely, in Table 2,
we report the ECE with the following definition:

$\text{calib-
err}=\text{ECE}=\sum_{h=1}^{H}\frac{|B_{h}|}{m}\big{|}\text{acc}(B_{h})-\text{conf}(B_{h})\big{|}$
(68)

with $m$ denoting the overall number of test points.

###  E.3 Hyper-Parameter Selection

For each of the meta-environments and algorithms, we ran a separate hyper-
parameter search to select the hyper-parameters. In particular, we use the
hyperopt444http://hyperopt.github.io/hyperopt/ package (Bergstra et al., 2013)
which performs Bayesian optimization based on regression trees. As
optimization metric, we employ the average log-likelihood, evaluated on a
separate validation set of tasks.

The scripts for reproducing the hyper-parameter search for PACOH-GP are
included in our code
repository555https://github.com/jonasrothfuss/meta_learning_pacoh. For the
reported results, we provide the selected hyper-parameters and detailed
evaluation results under https://tinyurl.com/s48p76x.

###  E.4 Meta-Learning for Bandits - Vaccine Development

In this section, we provide additional details on the experiment in Section
6.3.

We use data from Widmer et al. (2010) which contains the binding affinities
($\text{IC}_{50}$ values) of many peptide candidates to seven different MHC-I
alleles. Peptides with $\text{IC}_{50}>500$nM are considered non-binders, all
others binders. Following Krause & Ong (2011), we convert the $\text{IC}_{50}$
values into negative log-scale and normalize them such that 500nM corresponds
to zero, i.e. $r:=-\log_{10}(\text{IC}_{50})+\log_{10}(500)$ with is used as
reward signal of our bandit.

Allele | A-0202 | A-0203 | A-0201 | A-2301 | A-2402
---|---|---|---|---|---
$m_{i}$ | 1446 | 1442 | 3088 | 103 | 196
Table S2: MHC-I alleles used for meta-training and their corresponding number
of meta-training samples $m_{i}$.

We use 5 alleles to meta-learn a BNN prior. The alleles and the corresponding
number of data points, available for meta-training, are listed in Table S2.
The most genetically dissimilar allele (A-6901) is used for our bandit task.
In each iteration, the experimenter (i.e. bandit algorithm) chooses to test
one peptide among the pool of 813 candidates and receives $r$ as a reward
feedback. Hence, we are concerned with a 813-arm bandit wherein the action
$a_{t}\ \in\\{1,...,813\\}=\mathcal{A}$ in iteration $t$ corresponds to
testing $a_{t}$-th peptide candidate. In response, the algorithm receives the
respective negative log-$\text{IC}_{50}$ as reward $r(a_{t})$.

As metrics, we report the _average regret_

$R^{avg.}_{T}:=\max_{a\in\mathcal{A}}r(a)-\frac{1}{T}\sum_{t=1}^{T}r(a_{t})$

and the _simple regret_

$R^{simple}_{T}:=\max_{a\in\mathcal{A}}r(a)-\max_{t=1,...,T}r(a_{t})$

To ensure a fair comparison, the prior parameters of the GP for GP-UCB and GP-
TS are meta-learned by minimizing the GP’s marginal log-likelihood on the five
meta-training tasks. For the prior, we use a constant mean function and tried
various kernel functions (linear, SE, Matern). Due to the 45-dimensional
feature space, we found the linear kernel to work the best. So overall, the
constant mean and the variance parameter of the linear kernel are meta-
learned.

###  E.5 Further Experimental Results

##### Meta-overfitting

In order to investigate whether the phenomenon of meta-overfitting, which we
have observed consistently for PACOH-MAP and MLL, is also relevant to other
meta-learning methods (MAML and NPs), we also report the meta-train test error
and the meta-test test error across different numbers of tasks. The results,
analogous to Figure 4, are plotted in Figure S3, showing a significant
difference between the meta-train and meta-test error that vanishes as the
number of tasks becomes larger. Once more, this supports our claim that meta-
overfitting is a relevant issue and should be addressed in a principled
manner.

Figure S3: Test RMSE measured on the meta-training tasks and the meta-testing
tasks as a function of the number of meta-training tasks for MAML and NPs. The
performance gap between the meta-train and meta-test tasks clearly
demonstrates overfitting on the meta-level for both methods.