# Bridging the Gap Between Practice and PAC-Bayes Theory in Few-Shot Meta-
Learning

Nan Ding
Google Research
Venice, CA 90291
<EMAIL_ADDRESS>&Xi Chen
Harvard University
Cambridge, MA 02138
<EMAIL_ADDRESS>&Tomer Levinboim
Google Research
Venice, CA 90291
<EMAIL_ADDRESS>&Sebastian Goodman
Google Research
Venice, CA 90291
<EMAIL_ADDRESS>&Radu Soricut
Google Research
Venice, CA 90291
<EMAIL_ADDRESS>Part of work was done during the internship at Google.

###### Abstract

Despite recent advances in its theoretical understanding, there still remains
a significant gap in the ability of existing PAC-Bayesian theories on meta-
learning to explain performance improvements in the few-shot learning setting,
where the number of training examples in the target tasks is severely limited.
This gap originates from an assumption in the existing theories which supposes
that the number of training examples in the observed tasks and the number of
training examples in the target tasks follow the same distribution, an
assumption that rarely holds in practice. By relaxing this assumption, we
develop two PAC-Bayesian bounds tailored for the few-shot learning setting and
show that two existing meta-learning algorithms (MAML and Reptile) can be
derived from our bounds, thereby bridging the gap between practice and PAC-
Bayesian theories. Furthermore, we derive a new computationally-efficient
PACMAML algorithm, and show it outperforms existing meta-learning algorithms
on several few-shot benchmark datasets.

##  1 Introduction

Recent advances in machine learning and neural networks have resulted in
effective but parameter-bloated, data-hungry models. When the training data
for a target task of interest is insufficient, such overparameterized models
may easily overfit to the training data and exhibit poor generalization
abilities. To address this problem, several research efforts have focused on
designing a learning strategy that can leverage the training data of other
tasks for the sake of improving the performance of some specific target
task(s). Specifically, in the meta-learning (also called learning-to-learn or
lifelong-learning) setting (Baxter, 1998; Ravi and Larochelle, 2017), a meta-
learner first extracts knowledge from a set of observed (meta-training) tasks
and subsequently, this knowledge enables a base-learner to better adapt to the
new, possibly data-limited target (meta-testing) task. The meta-learning
framework has been successfully applied and made significant practical impact
on computer vision (Russakovsky et al., 2015), language understanding (Devlin
et al., 2019), reinforcement learning (Finn et al., 2017) and many other
research fields.

In parallel to its impressive empirical success, a series of theoretical works
(Tripuraneni et al., 2020; Pentina and Lampert, 2014; Amit and Meir, 2018;
Rothfuss et al., 2020) study how meta-learning utilizes the knowledge obtained
from the observed task data and how it generalizes to the unseen target task.
Among the generalization bounds, PAC-Bayes bounds (McAllester, 1999; Germain
et al., 2009) are considered especially tight and have already been proposed
for meta-learning (Pentina and Lampert, 2014; Amit and Meir, 2018; Rothfuss et
al., 2020). However, there still remains a gap between these existing PAC-
Bayesian bounds and their practical application (especially in the few-shot
setting), which originates from the assumption that the observed task
environment $\tilde{T}$ and the target task environment $T$ are the same. In
the PAC-Bayesian meta-learning setting, a task environment $T$ is a
distribution from which $(D,m)$ is drawn from, where $D$ is the data
distribution and $m$ is the number of training examples for the task. Although
there is research work studying the case of general environment change (e.g.
(Pentina and Lampert, 2015)) or data domain change (e.g. Germain et al.
(2016b)), to the best of our knowledge, there is little work focusing on the
case where only the number of training examples $\tilde{m}$ in the observed
tasks and $m$ in the target task do not follow the same distribution. In
practice, such mismatch commonly happens, because there is usually
significantly more data in observed tasks than the target tasks, especially in
the few-shot case. Without explicitly addressing this mismatch, the scope of
the current theory is severely limited, and it prohibits a useful analysis on
practical meta-learning algorithms such as MAML Finn et al. (2017). For
example, when the number of training examples $m$ in the target task is small,
the existing bounds yield a large generalization gap which grows with
$O(1/m)$. In this paper, we bring the theory closer to practice by studying
the setting where there are significantly more training examples in the
observed task than in the target task (i.e., $\tilde{m}\gg m$). In Section
3.1, we study two practical meta-training strategies and provide their PAC-
Bayesian bounds in Theorem 3 and Theorem 4. Both results are able to bring
down the scaling coefficient of the bound from $O(1/m)$ to $O(1/\tilde{m})$.
However, Theorem 3 introduces a penalty term in the bound that captures the
discrepancy between the observed and target task environment. Motivated by
MAML Finn et al. (2017), we show with Theorem 4 that we can eliminate the
penalty term by utilizing a subsampling strategy, yielding a much tighter
bound.

This theoretical work also bridges the gap from practice to theory, as we
further show that the maximum-a-posteriori (MAP) estimates of our bounds (in
which the base-learner and the hyper-posterior are both approximated by Dirac-
measures) yield various popular meta-learning algorithms, including multi-task
pretraining (Russakovsky et al., 2015), Reptile (Nichol et al., 2018) and MAML
(Finn et al., 2017). In that sense, our PAC-Bayesian theories provide a
different perspective for understanding and justifying these commonly used
algorithms (Section 3.2).

Lastly, in Section 4, we propose PACMAML, a novel PAC-Bayesian meta-learning
algorithm based on Theorem 4. As opposed to MAML, our algorithm does not have
higher-order derivatives in the gradient, and therefore represents a
significant improvement in computational efficiency. In Section 5, we conduct
numerical experiments that empirically support the correctness of our
theorems, and report the effectiveness of the new PACMAML algorithm, which
obtains superior results on several few-shot benchmark datasets.

##  2 Preliminaries

We begin by reviewing the background and settings of the existing PAC-Bayesian
bounds for meta-learning. Our notation mainly follows that of (Rothfuss et
al., 2020), which is itself adapted from (Pentina and Lampert, 2014; Amit and
Meir, 2018; Baxter, 1998).

#### PAC-Bayesian for Supervised Learning

In supervised learning, a learning task is characterized by a data
distribution $D$ over a data domain $Z$ where every example $z=(x,y)$. A
hypothesis $h$ from the hypothesis space $H$ allows us to make predictions
based on inputs $x$. The quality of the predictions is measured by a loss
function $l(h,z)$, where the goal is to minimize the expected loss
$L(h,D)=\operatorname{\mathbb{E}}_{z\sim D}l(h,z)$. Typically, $D$ is unknown
and instead we are given a set of $m$ observations $S\sim D^{m}=\\{z_{i}\sim
D\\}_{i=1}^{m}$, in which case the empirical error on $S$ is simply
$\hat{L}(h,S)=\frac{1}{m}\sum_{i=1}^{m}l(h,z_{i})$.

In the PAC-Bayesian setting, we assume that the learner has prior knowledge of
the hypothesis space $H$ in the form of a prior distribution $P(h)$. When the
learner observes a training dataset $S$, it updates the prior into a posterior
distribution $Q$. We formalize such a _base learner_ $Q(S,P)$ that takes a
dataset and a prior as input and outputs a posterior.

The expected error of the posterior $Q$ is called the Gibbs error
$L(Q,D)=\operatorname{\mathbb{E}}_{h\sim Q}L(h,D)$, and its empirical
counterpart is $\hat{L}(Q,S)=\operatorname{\mathbb{E}}_{h\sim Q}\hat{L}(h,S)$.
The PAC-Bayesian framework provides the following bound over $L(Q,D)$ based on
its empirical estimate $\hat{L}(Q,S)$.

######  Theorem 1 ((Alquier et al., 2016; Germain et al., 2009))

Given a data distribution $D$, a hypothesis space $H$, a prior $P$, a
confidence level $\delta\in(0,1]$, and $\beta>0$, with probability at least
$1-\delta$ over samples $S\sim D^{m}$, we have for all posterior $Q$,

$\displaystyle
L(Q,D)\leq\hat{L}(Q,S)+\frac{1}{\beta}\left(D_{KL}(Q\|P)+\log\frac{1}{\delta}\right)+\frac{m}{\beta}\Psi(\frac{\beta}{m})$
(1)

where $\Psi(\beta)=\log\operatorname{\mathbb{E}}_{h\sim
P}\operatorname{\mathbb{E}}_{z\sim D}\exp(\beta(l(h,z)-L(h,D)))$.

#### PAC-Bayesian for Meta-Learning

In the meta-learning setting, the meta-learner observes different tasks
$\tau_{i}=(D_{i},m_{i}$) during the meta-training stage, where all tasks share
the same data domain $Z$, hypothesis space $H$ and loss function $l(h,z)$. For
each observed task $\tau_{i}$, the meta-learner observes a training set
$S_{i}$ of size $m_{i}$ which is assumed to be sampled i.i.d. from its
respective data distribution $D_{i}$ (that is, $S_{i}\in D_{i}^{m_{i}}$). We
further assume that each task $\tau_{i}=(D_{i},m_{i})$ is drawn i.i.d. from an
environment $T$, which itself is a probability distribution over the data
distributions and the sample sizes. The goal of meta-learning is to extract
knowledge from the observed tasks $\tau_{i}$, which can then be used as prior
knowledge for learning on new (yet unobserved) target tasks $\tau=(D,m)\sim
T$. This prior knowledge is represented as a prior distribution $P(h)$ over
learning hypotheses $h$, and it is subsequently used by the base learner
$Q(S,P)$ for inference over the target tasks.

In the meta-learning PAC-Bayes framework, the meta-learner presumes a hyper-
prior $\operatorname{\mathcal{P}}(P)$ as a distribution over priors $P$. Upon
observing datasets $S_{1},\ldots,S_{n}$ from multiple tasks, the meta-learner
updates the hyper-prior to a hyper-posterior $\operatorname{\mathcal{Q}}(P)$.
The performance of this hyper-posterior, also called the transfer-error, is
measured as the expected Gibbs error when sampling priors $P$ from
$\operatorname{\mathcal{Q}}$ and applying the base learner:

$\displaystyle R(\operatorname{\mathcal{Q}},T)$
$\displaystyle:=\operatorname{\mathbb{E}}_{P\sim\operatorname{\mathcal{Q}}}\operatorname{\mathbb{E}}_{(D,m)\sim
T}\operatorname{\mathbb{E}}_{S\sim D^{m}}\left[L(Q(S,P),D)\right].$ (2)

While $R(\operatorname{\mathcal{Q}},T)$ is unknown in practice, it can be
estimated using the empirical error,

$\displaystyle\hat{R}(\operatorname{\mathcal{Q}},S_{i=1}^{n}):=\operatorname{\mathbb{E}}_{P\sim\operatorname{\mathcal{Q}}}\left[\frac{1}{n}\sum_{i=1}^{n}\hat{L}(Q(S_{i},P),S_{i})\right].$
(3)

In (Pentina and Lampert, 2014; Rothfuss et al., 2020), the following PAC-
Bayesian meta-learning bound is provided:

######  Theorem 2 ((Pentina and Lampert, 2014; Rothfuss et al., 2020))

Given a task environment $T$ and a set of $n$ observed tasks
$(D_{i},m_{i})\sim T$, let $\operatorname{\mathcal{P}}$ be a fixed hyper-prior
and $\lambda>0$, $\beta>0$, with probability at least $1-\delta$ over samples
$S_{1}\in D_{1}^{m_{1}},\ldots,S_{n}\in D_{n}^{m_{n}}$, we have, for all base
learner $Q$ and all hyper-posterior $\operatorname{\mathcal{Q}}$,

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

Here $C(\delta,\lambda,\beta,n,m_{i})$ contains $\Psi$ and $\frac{1}{\delta}$
terms as in Eq.(1) (see Appendix A.1), and can be bounded by a function that
is independent of $\operatorname{\mathcal{Q}}$ for both bounded and unbounded
loss functions under moment constraints (see details in (Rothfuss et al.,
2020)). From a Bayesian perspective, meta-learning attempts to learn a good
hyper-posterior $\operatorname{\mathcal{Q}}$ such that for all tasks in the
task environment $T$, the divergence terms ${D_{KL}(Q(S_{i},P)\|P)}$ would be
substantially smaller in expectation when $P\sim\operatorname{\mathcal{Q}}$
compared to when $P\sim\operatorname{\mathcal{P}}$, such as in the ordinary
supervised learning setting of Eq.(1).

The hyperparameters $\lambda$ and $\beta$ can be adjusted to balance between
the first three terms of the bound and the $C$ function. Defining the harmonic
mean of $m_{i}$ as $\tilde{m}=(\sum_{i=1}^{n}1/nm_{i})^{-1}$, a common choice
is $\lambda\propto n$ and $\beta\propto\tilde{m}$***Another common choice is
$\lambda\propto\sqrt{n}$ and $\beta\propto\sqrt{\tilde{m}}$, so that the bound
is asymptotically consistent, and scales with $O(\frac{1}{\sqrt{\tilde{m}}})$.
However, in practice the bound with $\beta\propto\tilde{m}$ is usually tighter
(Germain et al., 2016a).. In this case, the generalization gap
$R(\operatorname{\mathcal{Q}},T)-\hat{R}(\operatorname{\mathcal{Q}},S_{i=1}^{n})$
becomes at least $O(\frac{1}{\tilde{m}})$ (from the 3rd-term on the RHS of
Eq.4). In the next section, we examine an assumption in this bound which makes
it impractical for the few-shot setting.

##  3 Bridging the Gap between Practice & Theory of Few-Shot Meta-Learning

The previous PAC-Bayesian meta-learning bound (Theorem 2) assumes that the
number of training examples $m_{i}$ for the observed tasks $\tau_{i}$ and the
number of training examples $m$ for the target task $\tau$ are drawn from the
same distribution (i.e.
$\operatorname{\mathbb{E}}_{T}[m_{i}]=\operatorname{\mathbb{E}}_{T}[m]$).
However, practical applications of meta-learning such as (Russakovsky et al.,
2015; Devlin et al., 2019) operate in a setting where there are far more
training examples in the observed tasks than in the target task. Moreover,
focusing on the few-shot setting (where $m$ is particularly small) exposes a
gap between theory and practice – Theorem 2 is unable to use the large number
of observed samples and can only produce a loose bound of $O(\frac{1}{m})$
which is ineffective at explaining the impressive generalization performance
of meta-learning as reported in practice.

In this section we attempt to close this gap by deriving an effective PAC-
Bayesian bound (Theorem 4) tailored for the few-shot setting. Interestingly,
the bounds derived in this section also provide PAC-Bayesian justifications
for two practical algorithms, Reptile and MAML.

###  3.1 Practical PAC-Bayesian Bounds for Few-Shot Meta-Learning

A first attempt at leveraging the larger number of examples $m_{i}$ in the
observed tasks is to directly follow the learning strategy of Theorem 2, by
bounding $R(\operatorname{\mathcal{Q}},T)$ using the empirical risk
$\hat{R}(\operatorname{\mathcal{Q}},S_{i=1}^{n})$, with $S_{i}\in
D_{i}^{m_{i}}$ and $(D_{i},m_{i})\sim\tilde{T}$, despite the change of task
environment from $T$ to $\tilde{T}$. This slight generalization leads to the
following bound (with proof in Appendix A.2):

###### Theorem 3

For a target task environment $T$ and an observed task environment $\tilde{T}$
where
$\operatorname{\mathbb{E}}_{\tilde{T}}[D]=\operatorname{\mathbb{E}}_{T}[D]$
and
$\operatorname{\mathbb{E}}_{\tilde{T}}[m]\geq\operatorname{\mathbb{E}}_{T}[m]$,
let $\operatorname{\mathcal{P}}$ be a fixed hyper-prior and $\lambda>0$,
$\beta>0$, then with probability at least $1-\delta$ over samples $S_{1}\in
D_{1}^{m_{1}},\ldots,S_{n}\in D_{n}^{m_{n}}$ where
$(D_{i},m_{i})\sim\tilde{T}$, we have, for all base learners $Q$ and hyper-
posterior $\operatorname{\mathcal{Q}}$,

$\displaystyle R(\operatorname{\mathcal{Q}},T)\leq$
$\displaystyle\hat{R}(\operatorname{\mathcal{Q}},S_{i=1}^{n})+\left(\frac{1}{\lambda}+\frac{1}{n\beta}\right)D_{KL}(\operatorname{\mathcal{Q}}\|\operatorname{\mathcal{P}})$
$\displaystyle+\frac{1}{n\beta}\sum_{i=1}^{n}\operatorname{\mathbb{E}}_{P\sim\operatorname{\mathcal{Q}}}\left[D_{KL}(Q(S_{i},P)\|P)\right]+C(\delta,\lambda,\beta,n,m_{i})+\Delta_{\lambda}(\operatorname{\mathcal{P}},T,\tilde{T}),$
(5)

where
$\Delta_{\lambda}(\operatorname{\mathcal{P}},T,\tilde{T})=\frac{1}{\lambda}\log\operatorname{\mathbb{E}}_{P\in\operatorname{\mathcal{P}}}e^{\lambda(R(P,T)-R(P,\tilde{T}))}$.

When
$\operatorname{\mathbb{E}}_{\tilde{T}}[\tilde{m}]=\operatorname{\mathbb{E}}_{\tilde{T}}[m_{i}]\gg\operatorname{\mathbb{E}}_{T}[m]$,
this decoupling of the task environments seems beneficial at first, because
$O(\frac{1}{\tilde{m}})$ is smaller compared to Eq.(4) when
$\beta\propto\tilde{m}$. Unfortunately however, Eq.(5) introduces an
additional penalty term $\Delta_{\lambda}$, which increases as
$\operatorname{\mathbb{E}}_{\tilde{T}}[\tilde{m}]$ gets larger.

To understand the influence of $\Delta_{\lambda}$, we plot the (blue) bound of
Eq.(5) in Fig.1 by using the synthetic Sinusoid regression task (see details
in Section 5.1 and in Appendix D.4) where we fixed $m=5$ and varied $m_{i}$
from 5 to 100. When $m_{i}=m=5$, Eq.(5) reduces to Eq.(4) and
$\Delta_{\lambda}=0$. Contrary to intuition, increasing $m_{i}$ does not
reduce the bound, but instead makes it worse due to the rapid increase of
$\Delta_{\lambda}$.

Figure 1: The PAC-Bayesian bounds of Theorems 2, 3, & 4 as evaluated over the
Sinusoid dataset. Some constant terms are neglected (see Appendix D.4 for more
details).

Can we utilize more training examples without introducing a penlty term such
as $\Delta_{\lambda}$? In the definition of
$\hat{R}(\operatorname{\mathcal{Q}},S_{i=1}^{n})$ (Eq.(3)), we note that the
training dataset $S_{i}$ of the observed task $\tau_{i}$ is used twice: first
in training the base-learner $Q(S_{i},P)$, and then, in evaluating the
empirical risk $\hat{L}(Q,S_{i})$. In analyzing the proof of the theorem (see
Appendix A.2), it can be seen that the penalty term arises exactly because
$Q(S_{i},P)$ is trained over more samples compared to $Q(S,P)$ of the target
task.

This motivates us to develop a MAML-inspired learning strategy, in which we
maintain the same target-task training environment $T$ for the base-learners
of the observed tasks: we first sample a subset $S_{i}^{\prime}\in
D_{i}^{m_{i}^{\prime}}$ from $S_{i}$ where
$\operatorname{\mathbb{E}}[m_{i}^{\prime}]=\operatorname{\mathbb{E}}_{T}[m]<\operatorname{\mathbb{E}}_{\tilde{T}}[m_{i}]$
and then use only the subset $S_{i}^{\prime}$ to train the base-learner
$Q(S_{i}^{\prime},P)$. At the same time, all examples of $S_{i}\in
D_{i}^{m_{i}}$ are used for evaluating the empirical risk $\hat{L}(Q,S_{i})$,
so that the larger $m_{i}$ in the empirical risk $\hat{L}(Q,S_{i})$ help
tightening the generalization gap. This new strategy leads to the following
bound (proof in Appendix A.3):

###### Theorem 4

For a target task environment $T$ and an observed task environment $\tilde{T}$
where
$\operatorname{\mathbb{E}}_{\tilde{T}}[D]=\operatorname{\mathbb{E}}_{T}[D]$
and
$\operatorname{\mathbb{E}}_{\tilde{T}}[m]\geq\operatorname{\mathbb{E}}_{T}[m]$,
let $\operatorname{\mathcal{P}}$ be a fixed hyper-prior and $\lambda>0$,
$\beta>0$, then with probability at least $1-\delta$ over samples $S_{1}\in
D_{1}^{m_{1}},\ldots,S_{n}\in D_{n}^{m_{n}}$ where
$(D_{i},m_{i})\sim\tilde{T}$, and subsamples $S_{1}^{\prime}\in
D_{1}^{m_{1}^{\prime}}\subset S_{1},\ldots,S_{n}^{\prime}\in
D_{n}^{m_{n}^{\prime}}\subset S_{n}$, where
$\operatorname{\mathbb{E}}[m_{i}^{\prime}]=\operatorname{\mathbb{E}}_{T}[m]$,
we have, for all base learner $Q$ and all hyper-posterior
$\operatorname{\mathcal{Q}}$,

$\displaystyle R(\operatorname{\mathcal{Q}},T)\leq$
$\displaystyle\operatorname{\mathbb{E}}_{P\sim\operatorname{\mathcal{Q}}}\left[\frac{1}{n}\sum_{i=1}^{n}\hat{L}(Q(S_{i}^{\prime},P),S_{i})\right]+\left(\frac{1}{\lambda}+\frac{1}{n\beta}\right)D_{KL}(\operatorname{\mathcal{Q}}\|\operatorname{\mathcal{P}})$
$\displaystyle+\frac{1}{n\beta}\sum_{i=1}^{n}\operatorname{\mathbb{E}}_{P\sim\operatorname{\mathcal{Q}}}\left[D_{KL}(Q(S_{i}^{\prime},P)\|P)\right]+C(\delta,\lambda,\beta,n,m_{i}).$
(6)

This bound is still $O(\frac{1}{\tilde{m}})$ when choosing
$\beta\propto\tilde{m}$, but unlike Eq.(5), it does not have an additional
penalty term in Eq.(6), which is due to the shared training environment $T$ of
the base-learners in both observed and target tasks. Importantly, the
resulting bound is effective in the few-shot setting as an increase in the
number of observed examples $m_{i}$ monotonically tightens the generalization
gap. This is visually demonstrated in Fig.1 in which the (orange) bound of
Eq.(6) in Theorem 4 is monotonically decreasing as $m_{i}$ increases, while
the bound in Theorem 2 is limited only to $m_{i}=5$ and the bound of Theorem 3
grows.

###  3.2 Justifying Reptile and MAML using PAC-Bayesian Bounds

It is worth noting that Theorems 3 and 4 not only address more practical
scenarios in which observed (meta-training) examples are more abundant than
the target examples, but they also serve as a justification for popular and
practical meta-learning algorithms: Reptile (Nichol et al., 2018) and MAML
(Finn et al., 2017).

To show this, let us consider the maximum-a-posteriori (MAP) approximations on
the hyper-posterior $\operatorname{\mathcal{Q}}(P)$ and base-leaner
$Q_{i}(h),\forall i=1,\ldots,n$, with Dirac measures. In addition, we use the
isotropic Gaussian priors with variance hyperparameter $\sigma_{0}^{2}$ and
$\sigma^{2}$ for the hyper-prior $\operatorname{\mathcal{P}}(P)$ and the prior
$P(h)$. The hypothesis $h$ is parameterized by $\operatorname{\mathbf{v}}$.
Then we have

$\displaystyle\operatorname{\mathcal{P}}(P)$
$\displaystyle=\operatorname{\mathcal{N}}(\operatorname{\mathbf{p}}|0,\sigma_{0}^{2}),\;\operatorname{\mathcal{Q}}(P)=\delta(\operatorname{\mathbf{p}}=\operatorname{\mathbf{p}}_{0}),\;P(h_{\operatorname{\mathbf{v}}})=\operatorname{\mathcal{N}}(\operatorname{\mathbf{v}}|\operatorname{\mathbf{p}},\sigma^{2}),\;Q_{i}(h_{\operatorname{\mathbf{v}}})=\delta(\operatorname{\mathbf{v}}=\operatorname{\mathbf{q}}_{i}),$

and the goal of MAP approximation is to find the optimal meta-parameters
$\operatorname{\mathbf{p}}_{0}$. With the above assumptions, the PAC-Bayesian
bound (denoted PacB) of Eq.(5) and Eq.(6) with respect to
$\operatorname{\mathbf{p}}_{0}$ becomes (up to a constant, see Appendix B),

$\displaystyle PacB(\operatorname{\mathbf{p}}_{0})=$
$\displaystyle\frac{1}{n}\sum_{i=1}^{n}\hat{L}(\operatorname{\mathbf{q}}_{i},S_{i})+\frac{\tilde{\xi}\|\operatorname{\mathbf{p}}_{0}\|^{2}}{2\sigma_{0}^{2}}+\frac{1}{n\beta}\sum_{i=1}^{n}\frac{\|\operatorname{\mathbf{p}}_{0}-\operatorname{\mathbf{q}}_{i}\|^{2}}{2\sigma^{2}},$
(7)

where $\tilde{\xi}=\frac{1}{\lambda}+\frac{1}{n\beta}$. Here,
$\operatorname{\mathbf{q}}_{i}$ can be any function of
$\operatorname{\mathbf{p}}_{0}$ and $S_{i}$ for Eq.(5) (or
$\operatorname{\mathbf{p}}_{0}$ and $S_{i}^{\prime}$ for Eq.(6)), such that
the only free variable in Eq.(7) is $\operatorname{\mathbf{p}}_{0}$. Indeed,
by setting $\operatorname{\mathbf{q}}_{i}$ according to the choices below, we
can derive the gradients of several meta-learning algorithms.

When $\operatorname{\mathbf{q}}_{i}=\operatorname{\mathbf{p}}_{0}$, the
gradient of Eq.(7) reduces to that of multi-task pretraining (Russakovsky et
al., 2015; Devlin et al., 2019),

$\displaystyle\lim_{\operatorname{\mathbf{q}}_{i}\to\operatorname{\mathbf{p}}_{0}}\frac{d(PacB)}{d\operatorname{\mathbf{p}}_{0}}=\frac{\tilde{\xi}\operatorname{\mathbf{p}}_{0}}{\sigma_{0}^{2}}+\frac{1}{n}\sum_{i=1}^{n}\frac{d}{d\operatorname{\mathbf{p}}_{0}}\hat{L}(\operatorname{\mathbf{p}}_{0},S_{i}).$

On the other hand, if we use the optimal Dirac-base-learner
$\operatorname{\mathbf{q}}_{i}^{*}$ of $\operatorname{\mathbf{p}}_{0}$ and
$S_{i}$, such that

$\displaystyle\operatorname{\mathbf{q}}_{i}^{*}=$
$\displaystyle\operatorname*{\mathop{\mathrm{argmin}}}_{\operatorname{\mathbf{q}}_{i}}\left[\hat{L}(\operatorname{\mathbf{q}}_{i},S_{i})+\frac{\|\operatorname{\mathbf{p}}_{0}-\operatorname{\mathbf{q}}_{i}\|^{2}}{2\beta\sigma^{2}}\right],$
(8)

then the gradient of Eq.(7) becomes substantially simpler (see details in the
Appendix B),

$\displaystyle\frac{d(PacB)}{d\operatorname{\mathbf{p}}_{0}}$
$\displaystyle=\frac{\tilde{\xi}\operatorname{\mathbf{p}}_{0}}{\sigma_{0}^{2}}+\frac{1}{n}\sum_{i=1}^{n}\frac{\operatorname{\mathbf{p}}_{0}-\operatorname{\mathbf{q}}_{i}^{*}}{\beta\sigma^{2}},$
(9)

and in fact, Eq.(9) is equivalent to the meta-update rule of the Reptile
algorithm (Nichol et al., 2018), whose inner-loop is an approximate algorithm
for solving the optimal Dirac-base-learner
$\operatorname{\mathbf{q}}_{i}^{*}$.

Lastly, when $\operatorname{\mathbf{q}}_{i}$ is a few gradient descent steps
of $\hat{L}(\operatorname{\mathbf{q}}_{i},S_{i}^{\prime})$ with initial
$\operatorname{\mathbf{q}}_{i}=\operatorname{\mathbf{p}}_{0}$, the gradient of
Eq.(7) reduces to that of the MAML algorithm†††A slight difference is that
MAML usually assumes $S_{i}\cap S_{i}^{\prime}=\emptyset$; while in our
setting, we assume $S_{i}^{\prime}\subset S_{i}$. However, Theorem 4 still
holds when $S_{i}\cap S_{i}^{\prime}=\emptyset$.  (Finn et al., 2017) as
$\sigma^{2}\to\infty$,

$\displaystyle\lim_{\sigma^{2}\to\infty}\frac{d(PacB)}{d\operatorname{\mathbf{p}}_{0}}=\frac{\tilde{\xi}\operatorname{\mathbf{p}}_{0}}{\sigma_{0}^{2}}+\frac{1}{n}\sum_{i=1}^{n}\frac{d}{d\operatorname{\mathbf{p}}_{0}}\hat{L}(\operatorname{\mathbf{q}}_{i},S_{i}).$

One observation here is that, since $\operatorname{\mathbf{q}}_{i}$ is
function of the gradient of $\operatorname{\mathbf{p}}_{0}$,
$d\operatorname{\mathbf{q}}_{i}/d\operatorname{\mathbf{p}}_{0}$ involves high-
order gradient w.r.t. $\operatorname{\mathbf{p}}_{0}$, which would result in a
computationally intensive algorithm. In the next section we present a
computationally efficient algorithm which relies only on first-order
derivatives.

##  4 PAC-Bayesian Meta-Learning Algorithms in the Few-Shot Setting

In this section we present two PAC-Bayesian based Meta-Learning algorithms
with non-Dirac base-learners. We first derive their objective functions from
the RHS of Eq.(5) and Eq.(6), and then derive low-variance gradient estimators
for their optimization.

First, since Eq.(4) and Eq.(5) only differ by $\Delta_{\lambda}$, we follow
(Rothfuss et al., 2020) and plug in their proposed Gibbs posterior based base-
learner
$Q^{*}(S_{i},P)(h)=P(h)\exp(-\beta\hat{L}(h,S_{i}))/Z_{\beta}(S_{i},P)$ into
Eq.(5), which minimizes Eq.(5) w.r.t. $Q$. This yields that, with at least
$1-\delta$ probability,

$\displaystyle R(\operatorname{\mathcal{Q}},T)\leq$
$\displaystyle\frac{1}{n}\sum_{i=1}^{n}\operatorname{\mathbb{E}}_{P\sim\operatorname{\mathcal{Q}}}\underbrace{\left[-\frac{1}{\beta}\log
Z_{\beta}(S_{i},P)\right]}_{W_{1}}+\tilde{\xi}D_{KL}(\operatorname{\mathcal{Q}}\|\operatorname{\mathcal{P}})+\Delta_{\lambda}+C$
(10)

where $\tilde{\xi}=\frac{1}{\lambda}+\frac{1}{n\beta}$ and $C$ is the same
constant from the previous bounds. Since $\Delta_{\lambda}$ is independent of
$\operatorname{\mathcal{Q}}$ and can be neglected during inference or
optimization of $\operatorname{\mathcal{Q}}$, it reduces to the same PACOH
objective as in (Rothfuss et al., 2020).

On the other hand, the same Gibbs posterior cannot be used as the base learner
of Eq.(6), because the Gibbs posterior would depend on $S_{i}$, while the base
learner in Eq.(6) should only be dependent on $S_{i}^{\prime}\subset S_{i}$.
Therefore, we use the following posterior $Q_{i}^{\alpha}$ with hyperparameter
$\alpha$,

$\displaystyle
Q_{i}^{\alpha}(S_{i}^{\prime},P)(h)=\frac{P(h)\exp(-\alpha\hat{L}(h,S_{i}^{\prime}))}{Z_{\alpha}(S_{i}^{\prime},P)}.$

Plugging into Eq.(6) (derivations in Appendix) yields that, with at least
$1-\delta$ probability,

$\displaystyle R(\operatorname{\mathcal{Q}},T)\leq$
$\displaystyle\frac{1}{n}\sum_{i=1}^{n}\operatorname{\mathbb{E}}_{P\sim\operatorname{\mathcal{Q}}}\underbrace{\left[-\frac{1}{\beta}\log
Z_{\alpha}(S_{i}^{\prime},P)+\hat{L}^{\Delta}_{\frac{\alpha}{\beta}}(Q^{\alpha}_{i},S_{i},S_{i}^{\prime})\right]}_{W_{2}}+\tilde{\xi}D_{KL}(\operatorname{\mathcal{Q}}\|\operatorname{\mathcal{P}})+C.$
(11)

where
$\hat{L}^{\Delta}_{\frac{\alpha}{\beta}}(Q^{\alpha}_{i},S_{i},S_{i}^{\prime})\triangleq\hat{L}(Q^{\alpha}_{i},S_{i})-\frac{\alpha}{\beta}\hat{L}(Q_{i}^{\alpha},S_{i}^{\prime})$.
We refer to the RHS of this equation as the PACMAML objective, because Eq.(11)
comes from the PAC-Bayesian bound of Eq.(6), which is similar to MAML in
subsampling the training data for base-learners.

Given these two objectives, the next step is to estimate the gradients of
$W_{1}$ and $W_{2}$, which can then be plugged into Monte-Carlo methods for
estimating a hyper-posterior distribution of $\operatorname{\mathcal{Q}}$ (or
optimization methods for finding an MAP solution).

#### Gradient Estimation

In $W_{1}$ and $W_{2}$, the terms
$Z_{\beta},Z_{\alpha},\hat{L}^{\Delta}_{\frac{\alpha}{\beta}}(Q^{\alpha}_{i},S_{i},S_{i}^{\prime})$
all involve integrations over $h$. When $P(h)$ is Gaussian and
$\hat{L}(h,S_{i})$ is a squared loss, such integrations have closed form
solutions and the gradients can be analytically obtained. However, when
$\hat{L}(h,S_{i})$ is not a squared loss (such as the softmax loss), the
integration does not have a closed form solution and we resort to
approximations. For example, Rothfuss et al. (2020) directly approximates the
objective $W_{1}$ with Monte-Carlo sampling, which however results in a biased
gradient estimator.

Here, we follow an alternative approach from the REINFORCE algorithm
(Williams, 1992), which instead approximates _the gradient of the objective_
with Monte-Carlo methods, and has the benefit that the resulting gradient
estimator is unbiased. Assuming that the model hypothesis $h$ is parameterized
by $\operatorname{\mathbf{v}}$ such that
$\hat{L}(h,S_{i})\triangleq\hat{L}(\operatorname{\mathbf{v}},S_{i})$, and
$\operatorname{\mathbf{v}}$ has prior
$P(\operatorname{\mathbf{v}})=\operatorname{\mathcal{N}}(\operatorname{\mathbf{v}}|\operatorname{\mathbf{p}},\sigma^{2})$
with meta-parameter $\operatorname{\mathbf{p}}$, then

$\displaystyle\log
Z_{\beta}(S_{i},\operatorname{\mathbf{p}})=\log\int\operatorname{\mathcal{N}}(\operatorname{\mathbf{v}}|\operatorname{\mathbf{p}},\sigma^{2})\exp(-\beta\hat{L}(\operatorname{\mathbf{v}},S_{i}))d\operatorname{\mathbf{v}}.$

Note that $\operatorname{\mathbf{p}}$ appears in the probability distribution
$\operatorname{\mathcal{N}}(\operatorname{\mathbf{v}}|\operatorname{\mathbf{p}},\sigma^{2})$
of the expectation, and the naive Monte-Carlo estimator of the gradient w.r.t.
$\operatorname{\mathbf{p}}$ is known to exhibit high variance. To reduce the
variance, we apply the reparameterization trick (Kingma and Welling, 2013) and
rewrite
$\operatorname{\mathbf{v}}=\operatorname{\mathbf{p}}+\operatorname{\mathbf{w}}$
with
$\operatorname{\mathbf{w}}\sim\operatorname{\mathcal{N}}(\operatorname{\mathbf{w}}|{\bf
0},\sigma^{2})$. This leads to the following gradient of $W_{1}$,

$\displaystyle\frac{dW_{1}}{d\operatorname{\mathbf{p}}}$
$\displaystyle=-\frac{1}{\beta}\frac{d}{d\operatorname{\mathbf{p}}}\log
Z_{\beta}(S_{i},\operatorname{\mathbf{p}})=\int
Q^{\beta}_{i}(\operatorname{\mathbf{w}};S_{i})\frac{\partial\hat{L}(\operatorname{\mathbf{p}}+\operatorname{\mathbf{w}},S_{i})}{\partial\operatorname{\mathbf{p}}}d\operatorname{\mathbf{w}},$
(12)
$\displaystyle\text{where,}\;\;Q^{\beta}_{i}(\operatorname{\mathbf{w}};S_{i})\propto\operatorname{\mathcal{N}}(\operatorname{\mathbf{w}}|{\bf
0},\sigma^{2})\exp(-\beta\hat{L}(\operatorname{\mathbf{p}}+\operatorname{\mathbf{w}},S_{i})).$

As for $W_{2}$, we also need to evaluate the gradient of
$\hat{L}^{\Delta}_{\frac{\alpha}{\beta}}(Q^{\alpha}_{i},S_{i},S_{i}^{\prime})$,
where

$\displaystyle\frac{d}{d\operatorname{\mathbf{p}}}\hat{L}^{\Delta}_{\frac{\alpha}{\beta}}(Q^{\alpha}_{i},S_{i},S_{i}^{\prime})$
$\displaystyle=\int
Q_{i}^{\alpha}(\operatorname{\mathbf{w}};S_{i}^{\prime})\frac{\partial\hat{L}^{\Delta}_{\frac{\alpha}{\beta}}(\operatorname{\mathbf{p}}+\operatorname{\mathbf{w}},S_{i},S_{i}^{\prime})}{\partial\operatorname{\mathbf{p}}}d\operatorname{\mathbf{w}}+\int\frac{\partial
Q_{i}^{\alpha}(\operatorname{\mathbf{w}};S^{\prime}_{i})}{\partial\operatorname{\mathbf{p}}}\hat{L}^{\Delta}_{\frac{\alpha}{\beta}}(\operatorname{\mathbf{p}}+\operatorname{\mathbf{w}},S_{i},S_{i}^{\prime})d\operatorname{\mathbf{w}}.$
(13)

The first term of Eq.(13) is similar to the gradient in Eq.(12). The Monte-
Carlo gradient estimator of the second term, however, exhibits the same high-
variance problem as in the policy gradient method. As a remedy, we approximate
the gradient with the one from the Softmax Policy Gradient (Ding and Soricut,
2017), which yields a low-variance approximate gradient of $W_{2}$ (details in
Appendix):

$\displaystyle\frac{dW_{2}}{d\operatorname{\mathbf{p}}}$
$\displaystyle\simeq\int
Q_{i}^{\alpha}(\operatorname{\mathbf{w}};S_{i}^{\prime})\frac{\partial\hat{L}(\operatorname{\mathbf{p}}+\operatorname{\mathbf{w}};S_{i})}{\partial\operatorname{\mathbf{p}}}d\operatorname{\mathbf{w}}+\frac{\alpha}{\beta}\int\left(Q_{i}^{\beta}(\operatorname{\mathbf{w}};S_{i})-Q_{i}^{\alpha}(\operatorname{\mathbf{w}};S_{i}^{\prime})\right)\frac{\partial\hat{L}(\operatorname{\mathbf{p}}+\operatorname{\mathbf{w}};S_{i}^{\prime})}{\partial\operatorname{\mathbf{p}}}d\operatorname{\mathbf{w}}.$
(14)

The first-term in Eq.(14) is similar to the gradient of the First-order MAML
(FOMAML, Finn et al. (2017)). The second term involves $Q_{i}^{\beta}$ and
$Q_{i}^{\alpha}$, which are similar to the leader and the chaser in BMAML
(Yoon et al., 2018). Intuitively, the second term provides additional
information that plays a similar role to the high-order derivatives in MAML.
However, unlike MAML and BMAML, Eq.(14) only involves partial derivatives over
$\operatorname{\mathbf{p}}$ (since $\operatorname{\mathbf{w}}$ is not a
function of $\operatorname{\mathbf{p}}$) and therefore relies only on first-
order derivatives which contribute to its efficiency and stability.

To estimate Eq.(12) and Eq.(14) in practice, we first draw samples
$\operatorname{\mathbf{w}}_{(n)}^{\alpha}\sim
Q_{i}^{\alpha}(\operatorname{\mathbf{w}};S_{i}^{\prime})$ and
$\operatorname{\mathbf{w}}_{(n)}^{\beta}\sim
Q_{i}^{\beta}(\operatorname{\mathbf{w}};S_{i})$ using the Monte-Carlo sampling
(e.g. SGLD (Welling and Teh, 2011) or SVGD (Liu and Wang, 2016)). After
plugging the samples into
$\hat{L}(\operatorname{\mathbf{p}}+\operatorname{\mathbf{w}};S_{i})$ and
$\hat{L}(\operatorname{\mathbf{p}}+\operatorname{\mathbf{w}};S^{\prime}_{i})$,
we can apply automatic gradient computations (with Tensorflow (Abadi et al.,
2015) or Pytorch (Paszke et al., 2019)) over $\operatorname{\mathbf{p}}$ to
get the stochastic gradient estimator of $W_{1}$ and $W_{2}$.

##  5 Experiments

In this section, we evaluate the two PAC-Bayesian algorithms as they were
derived in the previous section: PACOH (Rothfuss et al., 2020) of Eq.(10) and
PACMAML of Eq.(11). We use several few-shot learning benchmarks (both
synthetic and real), and compare them against other existing meta-learning
algorithms, including MAML (Finn et al., 2017), Reptile (Nichol et al., 2018),
and BMAML (Yoon et al., 2018). To fairly compare with other meta-learning
algorithms that optimize a single model, we consider only the empirical Bayes
method for PACOH and PACMAML, in which a single MAP solution of
$\operatorname{\mathcal{Q}}$ is used, instead of Bayesian ensembles of
$\operatorname{\mathcal{Q}}$.

###  5.1 Few-Shot Regression Problem

Our first set of experiments are based on the synthetic regression environment
setup from (Rothfuss et al., 2020), where the gradient can be obtained
analytically.

Figure 2: Generalization error (RMSE) on the Sinusoid dataset: PACMAML and
MAML continue to improve as $m_{i}$ increases.

The base-learners $Q(S,P)$ are modeled using Gaussian Process (GP) regression
with a prior $P_{\mathchar 28946\relax}(h)=\mathcal{GP}(h|m_{\mathchar
28946\relax}(x),k_{\mathchar 28946\relax}(x,x^{\prime}))$, where the mean
function $m_{\mathchar 28946\relax}$ and the kernel function $k_{\mathchar
28946\relax}$ are instantiated as neural networks as in (Rothfuss et al.,
2020). For every example $z_{j}=(x_{j},y_{j})$ and a hypothesis $h$, the loss
function is $l(h,z_{j})=\|h(x_{j})-y_{j}\|_{2}^{2}$ and the empirical risk is
$\hat{L}(h,S_{i})=\frac{1}{m_{i}}\sum_{j=1}^{m_{i}}l(h,z_{j})$. The hyper-
prior $\operatorname{\mathcal{P}}(P_{\mathchar
28946\relax}):=\operatorname{\mathcal{P}}(\mathchar
28946\relax)=\operatorname{\mathcal{N}}(\mathchar
28946\relax|0,\sigma_{0}^{2}I)$ is an isotropic Gaussian defined over the
network parameters $\mathchar 28946\relax$. The MAP approximated hyper-
posterior takes the form of a delta function, where
$\operatorname{\mathcal{Q}}_{\mathchar 28946\relax_{0}}(P_{\mathchar
28946\relax}):=\operatorname{\mathcal{Q}}_{\mathchar
28946\relax_{0}}(\mathchar 28946\relax)=\delta(\mathchar 28946\relax=\mathchar
28946\relax_{0})$. As a result, we have that
$D_{KL}(\operatorname{\mathcal{Q}}_{\mathchar
28946\relax_{0}}\|\operatorname{\mathcal{P}})=\|\mathchar
28946\relax_{0}\|^{2}/2\sigma_{0}^{2}$, where we use $\sigma_{0}^{2}=3$ in our
experiments.

We experiment with the synthetic Sinusoid environment (details in Appendix
D.2), where we fix the number of observed tasks $n=20$, and vary the number of
examples per observed tasks from $m_{i}\in\left\\{5,10,30,50,100\right\\}$.
The number of training examples for each target task is fixed to be $m=5$, and
another 100 examples for each target task are used as a test set to evaluate
the generalization error. We report the averaged generalization error over 40
models, with the hyperparameters selected by 4-fold cross-validation over the
20 target tasks. Each model is trained on 1 of the 8 pre-sampled meta-training
sets (each containing $n=20$ observed tasks) and each set is run with 5 random
seeds for network initialization. $\alpha$ and $\beta$ are chosen based on the
cross-validation from the grid $\beta/m_{i}\in\left\\{10,30,100\right\\}$, and
$\alpha/m_{i}\in\left\\{10,20,30,40,50,60\right\\}$.

Figure 2 shows the averaged generalization errors (RMSE) as $m_{i}$ changes,
for the Reptile (with optimal $\operatorname{\mathbf{q}}_{i}^{*}$), MAML,
PACOH, and PACMAML algorithms. The size of $S_{i}^{\prime}$ used for base-
learner training in MAML and PACMAML is $m_{i}^{\prime}=5$ for all $m_{i}$.
The hyperparameter values, the validation errors and the standard errors are
reported in the Appendix D.3. As can be seen from the figure, the
generalization errors of Reptile (blue) and PACOH (green), both derived from
Theorem 3, have a U-shaped curve. That is, increasing the meta-training data
$m_{i}$ initially improves generalization in the few-shot target tasks,
however, as $m_{i}$ continues to grows well beyond $m$, generalization
suffers. This confirms our conjecture from Theorem 3, that larger $m_{i}$ has
a mixed effect on its generalization behavior due to the penalty term
$\Delta_{\lambda}$. In contrast, the generalization error of MAML and PACMAML,
both derived from Theorem 4, is monotonically decreasing as desired. Both the
generalization error and the bound (in Fig.1) demonstrate that PACMAML is the
most effective strategy of utilizing larger meta-training data for few-shot
learning.

###  5.2 Few-shot Classification Problems

In addition to the regression problems where the gradients have closed-form,
our next experiments evaluate how PACMAML perform on classification tasks
using softmax losses with gradient estimators from Eq.(12) and Eq.(14). In
order to fairly compare with MAML, which has only one set of inner adaptive
parameters, we also only use one sample for approximating the inner posterior
distribution $\operatorname{\mathcal{Q}}_{i}^{\alpha}$ and
$\operatorname{\mathcal{Q}}_{i}^{\beta}$.

#### Image Classification

Our first classification experiment is based on the miniImagenet
classification task (Vinyals et al., 2016) involving a task adaptation of
5-way classification with a single training example per class (1-shot). The
dataset consists of 60,000 color images of 84×84 dimension. The examples
consist of total 100 classes that are partitioned into 64, 12, and 24 classes
for meta-train, meta-validation, and meta-test, respectively. We generated the
tasks following the same procedure as in (Finn et al., 2017) and used the same
feature extraction model which contains 4 convolutional layers. Although the
original MAML adapted the entire network in the inner loop, (Raghu et al.,
2019) showed similar results by adapting only the top layer, which
significantly reduced computational complexity. We follow the same "almost no
inner loop" (ANIL) setting as (Raghu et al., 2019), and compare MAML with
BMAML, PACOH and PACMAML. Reptile is not included, because it requires full
model adaptation.

For all algorithms, we optimize for 6 steps in the inner loop to obtain the
inner adaptive parameter (or a posterior sample $\operatorname{\mathbf{w}}$).
The data sizes of the observed tasks are varied from
$m_{i}=\left\\{10,20,40,80\right\\}$ and $m_{i}^{\prime}=m=5$ (one shot for
each of 5 classes). We fixed $\alpha/\beta=m_{i}^{\prime}/m_{i}$ and perform
grid search on $\alpha$ as well as the meta and inner learning rate on the
meta-validation dataset. Other hyperparameters followed the setting in (Finn
et al., 2017). Further details are reported in the Appendix.

| FOMAML | MAML | BMAML | PACOH | PACMAML
---|---|---|---|---|---
$m_{i}=10$ | 41.8 $\pm$ 0.9 | 47.3 $\pm$ 0.9 | 29.9 $\pm$ 0.9 | 31.2 $\pm$ 0.8 | 47.8 $\pm$ 0.9
$m_{i}=20$ | 44.3 $\pm$ 0.9 | 48.0 $\pm$ 0.9 | 34.3 $\pm$ 0.9 | 37.0 $\pm$ 0.9 | 49.1 $\pm$ 0.9
$m_{i}=40$ | 46.2 $\pm$ 1.0 | 47.8 $\pm$ 0.9 | 41.5 $\pm$ 0.9 | 41.6 $\pm$ 0.9 | 48.9 $\pm$ 0.9
$m_{i}=80$ | 45.7 $\pm$ 0.9 | 48.1 $\pm$ 0.9 | 44.2 $\pm$ 0.9 | 44.6 $\pm$ 0.9 | 50.1 $\pm$ 0.9
Table 1: Averaged Generalization error and standard error in the ANIL setting.

The main meta-testing results are presented in Table 1. We find that PACOH
performs significantly worse than PACMAML. One explanation for this is that in
PACOH the base-learner (for top layer) is exposed to all $S$ data, and may
have already overfit on $S$ and the meta-learner (for lower layers) is unable
to learn further. The overfitting of the base-learner is more severe when
$m_{i}$ is small. Surprisingly, we find that BMAML behaves similarly poor in
the ANIL 1-particle setting. In FOMAML, MAML and PACMAML, the base-learner is
only trained on $S^{\prime}$ and the meta-learner can learn from the unseen
examples in $S$ and therefore no overfitting happens. Both MAML and PACMAML
performs significantly better than FOMAML when $m_{i}$ is small, but their
performances saturate and improve little for larger $m_{i}$, which may due to
the domain change between meta-training and testing (as the image class
changes). Overall, PACMAML as a first-order method not only significantly
outperforms FOMAML, but also marginally outperforms the high-order MAML, which
demonstrates the effectiveness of PACMAML and its gradient estimator.

#### Natural Language Inference

Lastly, we evaluate the meta-learning algorithms on the large-scale BERT-base
(Devlin et al., 2019) model containing 110M parameters. Our experiment
involves 12 practical natural language inference tasks from (Bansal et al.,
2019) which include:‡‡‡Data available at: https://github.com/iesl/leopard. (1)
entity typing: CoNLL-2003, MIT-Restaurant; (2) rating classification: the
review ratings from the Amazon Reviews dataset in the domain of Books, DVD,
Electronics, Kitchen; (3) text classification: social-media datasets from
crowdflower that include Airline, Disaster, Emotion, Political Bias, Political
Audience, Political Message.

Following (Bansal et al., 2019), we used the pretrained BERT-base model as our
base model (hyper-prior), and used GLUE benchmark tasks (Wang et al., 2018)
for meta-training the models and meta-validation for hyperparameter search,
before fine-tuning them for the 12 target tasks. The fine-tuning data contains
$k\in\left\\{4,8,16\right\\}$-shot data for each class in each task. For every
$k$, 10 fine-tuning datasets were sampled for each target task. The final
reported result is the average of the 10 models fine-tuned over these 10
datasets (for each task and each $k$ separately), and evaluated on the entire
test set for each target task (Bansal et al., 2019). The data size of the
observed tasks are fixed to be $m_{i}=256$, where the data points for each
observed task are randomly sampled from the training data of one of the GLUE
tasks. Because the number of classes in these 12 few-shot tasks varies from 2
to 12, we choose the inner data size $m_{i}^{\prime}$ from
$\left\\{32,64\right\\}$ for MAML, BMAML and PACMAML. As in (Bansal et al.,
2019), we also partition the set of model parameters to task-specific and
task-agnostic. For the 12-layer BERT-base model, we consider a hyper-parameter
$v\in\left\\{6,9,11,12\right\\}$, where only the layers higher than the $v$-th
layer are considered task-specific and will be adapted in the inner loop. When
$v=12$, only the top classification layers are adaptable. For BMAML, PACOH and
PACMAML, we performed grid search on $\alpha$ and fixed
$\alpha/\beta=m_{i}^{\prime}/m_{i}$.

$k$ | H-SMLMT (Bansal et al., 2020) | MAML | BMAML | PACOH | PACMAML
---|---|---|---|---|---
4 | 48.61 | 48.21 | 47.27 | 50.47 | 51.58
8 | 52.92 | 53.52 | 52.08 | 54.83 | 55.68
16 | 57.90 | 57.38 | 56.53 | 58.22 | 59.18

|  $v$=6 |  $v$=9 |  $v$=11 |  $v$=12
---|---|---|---|---
MAML | 120G | 57G | 16G | 4G
BMAML | 121G | 59G | 19G | 4G
PACMAML | 33G | 16G | 8G | 4G

Table 2: Top: Averaged Generalization error over the 12 NLI tasks. Bottom: The
comparison of TPU memory (High Bandwidth Memory) usage with different adaptive
layer thresholds $v$.

Due to space limitation, we only report the averaged generalization error over
the 12 tasks in Table 2 (top). The detailed results of the 12 NLI tasks, their
standard errors, as well as the hyperparameter selections are all included in
the Appendix. We also include the SOTA results from (Bansal et al., 2020) for
comparison and note that PACMAML is consistently the best performer over all
three few-shot settings $k=4,8,16$. In comparison, MAML and BMAML perform
worse, possibly due to sensitivity to learning rates, as suggested by (Bansal
et al., 2019). Beyond generalization errors, in Table 2 (bottom) we also
compare the memory usage of MAML/BMAML against PACMAML over different adaptive
layer thresholds $v$. These results emphasize the computational advantage of
PACMAML by showing that as more layers are adapted (lower $v$), MAML consumes
significantly more memory due to its high-order derivatives.

##  6 Discussion

We studied two PAC-Bayesian bounds for meta-learning in the few-shot case,
where the number of examples in the target task is significantly smaller than
that in the observed tasks. As opposed to previous bounds, our bound in
Theorem 4 remains tight in this scenario. We instantiated these new bounds and
related them to the Reptile and MAML algorithms and furthermore derived the
PACMAML algorithm, and showed its efficiency and effectiveness over several
meta-learning benchmarks. Broadly speaking, our work falls into the category
of PAC-Bayesian theories of non-i.i.d data (Pentina and Lampert, 2015);
however, our study case is more specific and our bounds are based on practical
strategies. One major limitation of the work is that we do not take into
account a data domain shift (e.g. (Germain et al., 2016b)), which is often
present in practice. However, the study of domain shift from a theoretical
perspective requires additional assumptions and knowledge about the target
data, which do not always exist in practice. We leave a deeper discussion and
exploration on these topics to future work.

## References

  * Abadi et al. (2015) M. Abadi, A. Agarwal, P. Barham, E. Brevdo, Z. Chen, C. Citro, G. S. Corrado, A. Davis, J. Dean, M. Devin, S. Ghemawat, I. Goodfellow, A. Harp, G. Irving, M. Isard, Y. Jia, R. Jozefowicz, L. Kaiser, M. Kudlur, J. Levenberg, D. Mané, R. Monga, S. Moore, D. Murray, C. Olah, M. Schuster, J. Shlens, B. Steiner, I. Sutskever, K. Talwar, P. Tucker, V. Vanhoucke, V. Vasudevan, F. Viégas, O. Vinyals, P. Warden, M. Wattenberg, M. Wicke, Y. Yu, and X. Zheng.  TensorFlow: Large-scale machine learning on heterogeneous systems, 2015\.  URL https://www.tensorflow.org/.  Software available from tensorflow.org.
  * Alquier et al. (2016) P. Alquier, J. Ridgway, and N. Chopin.  On the properties of variational approximations of gibbs posteriors.  _The Journal of Machine Learning Research_ , 17(1):8374–8414, 2016.
  * Amit and Meir (2018) R. Amit and R. Meir.  Meta-learning by adjusting priors based on extended PAC-Bayes theory.  In J. Dy and A. Krause, editors, _Proceedings of the 35th International Conference on Machine Learning_ , volume 80 of _Proceedings of Machine Learning Research_ , pages 205–214, Stockholmsmässan, Stockholm Sweden, 10–15 Jul 2018. PMLR.
  * Bansal et al. (2019) T. Bansal, R. Jha, and A. McCallum.  Learning to few-shot learn across diverse natural language classification tasks.  _arXiv preprint arXiv:1911.03863_ , 2019.
  * Bansal et al. (2020) T. Bansal, R. Jha, T. Munkhdalai, and A. McCallum.  Self-supervised meta-learning for few-shot natural language classification tasks.  _arXiv preprint arXiv:2009.08445_ , 2020.
  * Baxter (1998) J. Baxter.  Theoretical models of learning to learn.  In _Learning to learn_ , pages 71–94. Springer, 1998.
  * Devlin et al. (2019) J. Devlin, M.-W. Chang, K. Lee, and K. Toutanova.  BERT: Pre-training of deep bidirectional transformers for language understanding.  In _Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers)_ , June 2019.
  * Ding and Soricut (2017) N. Ding and R. Soricut.  Cold-start reinforcement learning with softmax policy gradient.  In _Proceedings of the 31st International Conference on Neural Information Processing Systems_ , pages 2814–2823, 2017.
  * Finn et al. (2017) C. Finn, P. Abbeel, and S. Levine.  Model-agnostic meta-learning for fast adaptation of deep networks.  _arXiv preprint arXiv:1703.03400_ , 2017.
  * Germain et al. (2009) P. Germain, A. Lacasse, F. Laviolette, and M. Marchand.  PAC-bayesian learning of linear classifiers.  In _Proceedings of the 26th Annual International Conference on Machine Learning_ , pages 353–360, 2009.
  * Germain et al. (2016a) P. Germain, F. Bach, A. Lacoste, and S. Lacoste-Julien.  PAC-bayesian theory meets bayesian inference.  _Advances in Neural Information Processing Systems_ , 29:1884–1892, 2016a.
  * Germain et al. (2016b) P. Germain, A. Habrard, F. Laviolette, and E. Morvant.  A new pac-bayesian perspective on domain adaptation.  In _International conference on machine learning_ , pages 859–868. PMLR, 2016b.
  * Kingma and Welling (2013) D. P. Kingma and M. Welling.  Auto-encoding variational bayes.  _arXiv preprint arXiv:1312.6114_ , 2013.
  * Liu and Wang (2016) Q. Liu and D. Wang.  Stein variational gradient descent: A general purpose bayesian inference algorithm.  _arXiv preprint arXiv:1608.04471_ , 2016.
  * McAllester (1999) D. A. McAllester.  Some PAC-bayesian theorems.  _Machine Learning_ , 37(3):355–363, 1999.
  * Nichol et al. (2018) A. Nichol, J. Achiam, and J. Schulman.  On first-order meta-learning algorithms.  _arXiv preprint arXiv:1803.02999_ , 2018.
  * Paszke et al. (2019) A. Paszke, S. Gross, F. Massa, A. Lerer, J. Bradbury, G. Chanan, T. Killeen, Z. Lin, N. Gimelshein, L. Antiga, A. Desmaison, A. Kopf, E. Yang, Z. DeVito, M. Raison, A. Tejani, S. Chilamkurthy, B. Steiner, L. Fang, J. Bai, and S. Chintala.  Pytorch: An imperative style, high-performance deep learning library.  In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett, editors, _Advances in Neural Information Processing Systems 32_ , pages 8024–8035. Curran Associates, Inc., 2019.  URL http://papers.neurips.cc/paper/9015-pytorch-an-imperative-style-high-performance-deep-learning-library.pdf.
  * Pentina and Lampert (2014) A. Pentina and C. H. Lampert.  A pac-bayesian bound for lifelong learning.  In _Proceedings of the 31st International Conference on International Conference on Machine Learning - Volume 32_ , ICML’14, page II–991–II–999, 2014.
  * Pentina and Lampert (2015) A. Pentina and C. H. Lampert.  Lifelong learning with non-iid tasks.  _Advances in Neural Information Processing Systems_ , 28:1540–1548, 2015.
  * Raghu et al. (2019) A. Raghu, M. Raghu, S. Bengio, and O. Vinyals.  Rapid learning or feature reuse? towards understanding the effectiveness of maml.  _arXiv preprint arXiv:1909.09157_ , 2019.
  * Ravi and Larochelle (2017) S. Ravi and H. Larochelle.  Optimization as a model for few-shot learning.  In _ICLR_ , 2017.
  * Rothfuss et al. (2020) J. Rothfuss, V. Fortuin, and A. Krause.  PACOH: Bayes-optimal meta-learning with pac-guarantees, 2020.
  * Russakovsky et al. (2015) O. Russakovsky, J. Deng, H. Su, J. Krause, S. Satheesh, S. Ma, Z. Huang, A. Karpathy, A. Khosla, M. Bernstein, et al.  Imagenet large scale visual recognition challenge.  _International journal of computer vision_ , 115(3):211–252, 2015.
  * Tripuraneni et al. (2020) N. Tripuraneni, M. I. Jordan, and C. Jin.  On the theory of transfer learning: The importance of task diversity.  _arXiv preprint arXiv:2006.11650_ , 2020.
  * Vinyals et al. (2016) O. Vinyals, C. Blundell, T. Lillicrap, K. Kavukcuoglu, and D. Wierstra.  Matching networks for one shot learning.  _arXiv preprint arXiv:1606.04080_ , 2016.
  * Wang et al. (2018) A. Wang, A. Singh, J. Michael, F. Hill, O. Levy, and S. R. Bowman.  Glue: A multi-task benchmark and analysis platform for natural language understanding.  _arXiv preprint arXiv:1804.07461_ , 2018.
  * Welling and Teh (2011) M. Welling and Y. W. Teh.  Bayesian learning via stochastic gradient langevin dynamics.  In _Proceedings of the 28th international conference on machine learning (ICML-11)_ , pages 681–688. Citeseer, 2011.
  * Williams (1992) R. J. Williams.  Simple statistical gradient-following algorithms for connectionist reinforcement learning.  In _Machine Learning_ , pages 229–256, 1992.
  * Yoon et al. (2018) J. Yoon, T. Kim, O. Dia, S. Kim, Y. Bengio, and S. Ahn.  Bayesian model-agnostic meta-learning.  In _Proceedings of the 32nd International Conference on Neural Information Processing Systems_ , pages 7343–7353, 2018.

##  Appendix A Proofs

In this section, we provide proofs of the main theorems presented in the
paper. We also provide a brief overview of the proof of Theorem 2 from
[Pentina and Lampert, 2015, Rothfuss et al., 2020], since the bound
decomposition strategy will also be used in the new theorems of the paper.

###  A.1 Brief Proof of Theorem 2 [Pentina and Lampert, 2015, Rothfuss et al.,
2020]

Given a task environment $T$ and a set of $n$ observed tasks
$(D_{i},m_{i})\sim T$, let $\operatorname{\mathcal{P}}$ be a fixed hyper-prior
and $\lambda>0$, $\beta>0$, with probability at least $1-\delta$ over samples
$S_{1}\in D_{1}^{m_{1}},\ldots,S_{n}\in D_{n}^{m_{n}}$, we have for all base
learner $Q$ and all hyper-posterior $\operatorname{\mathcal{Q}}$,

$\displaystyle R(\operatorname{\mathcal{Q}},T)\leq$
$\displaystyle\hat{R}(\operatorname{\mathcal{Q}},S_{i=1}^{n})+\tilde{\xi}D_{KL}(\operatorname{\mathcal{Q}}\|\operatorname{\mathcal{P}})$
$\displaystyle+\frac{1}{n\beta}\sum_{i=1}^{n}\operatorname{\mathbb{E}}_{P\sim\operatorname{\mathcal{Q}}}\left[D_{KL}(Q(S_{i},P)\|P)\right]+C(\delta,\lambda,\beta,n,m_{i}),$

where $\tilde{\xi}=\frac{1}{\lambda}+\frac{1}{n\beta}$.

Proof  The bound in Theorem 2 was proved by decomposing it into two
components:

  * •

"Task specific generalization bound", that bounds the generalization error
averaged over all observed tasks $\tau_{i}$:

$\displaystyle\operatorname{\mathbb{E}}_{P\sim\operatorname{\mathcal{Q}}}[\frac{1}{n}\sum_{i=1}^{n}L(Q(S_{i},P),D_{i})]$
$\displaystyle\leq$
$\displaystyle\hat{R}(\operatorname{\mathcal{Q}},S_{i=1}^{n})+\frac{1}{n\beta}D_{KL}(\operatorname{\mathcal{Q}}\|\operatorname{\mathcal{P}})+\frac{1}{n\beta}\sum_{i=1}^{n}\operatorname{\mathbb{E}}_{P\sim\operatorname{\mathcal{Q}}}\left[D_{KL}(Q(S_{i},P)\|P)\right]$
$\displaystyle+\frac{1}{n\beta}\log\frac{1}{\delta}+\frac{1}{n}\sum_{i=1}^{n}\frac{m_{i}}{\beta}\Psi_{1}(\frac{\beta}{m_{i}})$
(15)

where

$\displaystyle\hat{R}(\operatorname{\mathcal{Q}},S_{i=1}^{n})$
$\displaystyle=\operatorname{\mathbb{E}}_{P\sim\operatorname{\mathcal{Q}}}[\frac{1}{n}\sum_{i=1}^{n}\hat{L}(Q(S_{i},P),S_{i})],$
$\displaystyle\Psi_{1}(\beta)$
$\displaystyle=\log\operatorname{\mathbb{E}}_{P\sim\operatorname{\mathcal{P}}}\operatorname{\mathbb{E}}_{\operatorname{\mathbf{h}}\sim
P}\operatorname{\mathbb{E}}_{z_{ij}\sim
D_{i}}\left[e^{\beta(\operatorname{\mathbb{E}}_{z_{i}\sim
D_{i}}[l(h_{i},z_{i})]-l(h_{i},z_{ij}))}\right].$

  * •

"Task environment generalization bound", that bounds the transfer error from
the observed tasks to the new target tasks:

$\displaystyle R(\operatorname{\mathcal{Q}},T)\leq$
$\displaystyle\frac{1}{n}\sum_{i=1}^{n}\operatorname{\mathbb{E}}_{P\sim\operatorname{\mathcal{Q}}}\left[L(Q(S_{i},P),D_{i})\right]$
$\displaystyle+\frac{1}{\lambda}\left(D_{KL}(\operatorname{\mathcal{Q}}\|\operatorname{\mathcal{P}})+\log\frac{1}{\delta}\right)+\frac{n}{\lambda}\Psi_{2}(\frac{\lambda}{n}).$
(16)

where

$\displaystyle\Psi_{2}(\lambda)$
$\displaystyle=\log\operatorname{\mathbb{E}}_{P\sim\operatorname{\mathcal{P}}}\operatorname{\mathbb{E}}_{D_{i}\sim
T,S_{i}\sim
D_{i}^{m_{i}}}\left[e^{\lambda(\operatorname{\mathbb{E}}_{D_{i}\sim
T,S_{i}\sim D_{i}^{m_{i}}}[R_{S_{i}}(P)]-R_{S_{i}}(P))}\right].$

Detailed proofs of these two generalization bounds can be found in the
appendices of [Pentina and Lampert, 2015, Rothfuss et al., 2020].
Subsequently, combining Eq.(15) with Eq.(16), it is straightforward to get
Eq.(4), with

$\displaystyle
C(\delta,\lambda,\beta,n,m_{i})=\tilde{\xi}\log\frac{1}{\delta}+\frac{1}{n}\sum_{i=1}^{n}\frac{m_{i}}{\beta}\Psi_{1}(\frac{\beta}{m_{i}})+\frac{n}{\lambda}\Psi_{2}(\frac{\lambda}{n}).$
(17)

###  A.2 Proof of Theorem 3

For a target task environment $T$ and an observed task environment $\tilde{T}$
where
$\operatorname{\mathbb{E}}_{\tilde{T}}[D]=\operatorname{\mathbb{E}}_{T}[D]$
and
$\operatorname{\mathbb{E}}_{\tilde{T}}[m]\geq\operatorname{\mathbb{E}}_{T}[m]$,
let $\operatorname{\mathcal{P}}$ be a fixed hyper-prior and $\lambda>0$,
$\beta>0$, then with probability at least $1-\delta$ over samples $S_{1}\in
D_{1}^{m_{1}},\ldots,S_{n}\in D_{n}^{m_{n}}$ where
$(D_{i},m_{i})\sim\tilde{T}$, we have, for all base learners $Q$ and hyper-
posterior $\operatorname{\mathcal{Q}}$,

$\displaystyle R(\operatorname{\mathcal{Q}},T)\leq$
$\displaystyle\hat{R}(\operatorname{\mathcal{Q}},S_{i=1}^{n})+\tilde{\xi}D_{KL}(\operatorname{\mathcal{Q}}\|\operatorname{\mathcal{P}})+\frac{1}{n\beta}\sum_{i=1}^{n}\operatorname{\mathbb{E}}_{P\sim\operatorname{\mathcal{Q}}}\left[D_{KL}(Q(S_{i},P)\|P)\right]$
$\displaystyle+C(\delta,\lambda,\beta,n,m_{i})+\Delta_{\lambda}(\operatorname{\mathcal{P}},T,\tilde{T}),$

where
$\Delta_{\lambda}(\operatorname{\mathcal{P}},T,\tilde{T})=\frac{1}{\lambda}\log\operatorname{\mathbb{E}}_{P\in\operatorname{\mathcal{P}}}e^{\lambda(R(P,T)-R(P,\tilde{T}))}$,
and $\tilde{\xi}=\frac{1}{\lambda}+\frac{1}{n\beta}$.

Proof  The "task specific generalization bound" has the same form as Eq.(15).

For the "task environment generalization bound", define the "meta-training"
generalization error of a given prior $P$ on the observed task
$(D_{1},m_{1}),\ldots,(D_{n},m_{n})\sim\tilde{T}$ as

$\displaystyle R_{S_{\tilde{T}}}(P)\triangleq$
$\displaystyle\frac{1}{n}\sum_{i=1}^{n}L(Q(S_{i},P),D_{i})$ $\displaystyle=$
$\displaystyle\frac{1}{n}\sum_{i=1}^{n}\operatorname{\mathbb{E}}_{z_{i}\sim
D_{i}}\operatorname{\mathbb{E}}_{h_{i}\sim Q(h_{i}|P,S_{i})}[L(h_{i},z_{i})],$

where $S_{i}\sim D_{i}^{m_{i}}$ and
$S_{\tilde{T}}=\left\\{S_{1},\ldots,S_{n}\right\\}$. Similarly, the
generalization error on the target task environment $T$ is

$\displaystyle R(P,T)=\operatorname{\mathbb{E}}_{(D,m)\sim
T}\operatorname{\mathbb{E}}_{S\sim D^{m}}\operatorname{\mathbb{E}}_{z\in
D}\operatorname{\mathbb{E}}_{h\sim Q(h|P,S)}[L(h,z)].$

Using the Markov Inequality, with at least $1-\delta$ probability,

$\displaystyle\operatorname{\mathbb{E}}_{P\sim\operatorname{\mathcal{P}}}\left[e^{\lambda(R(P,T)-R_{S_{\tilde{T}}}(P))}\right]$
$\displaystyle\leq$
$\displaystyle\frac{1}{\delta}\operatorname{\mathbb{E}}_{P\sim\operatorname{\mathcal{P}}}\operatorname{\mathbb{E}}_{D_{i}\sim
T,S_{i}\sim
D_{i}^{m_{i}}}^{i=1,\ldots,n}\left[e^{\lambda(R(P,T)-R_{S_{\tilde{T}}}(P))}\right].$

The left-hand side can be lower bounded by,

$\displaystyle\log\operatorname{\mathbb{E}}_{P\sim\operatorname{\mathcal{P}}}\left[e^{\lambda(R(P,T)-R_{S_{\tilde{T}}}(P))}\right]$
$\displaystyle=$
$\displaystyle\log\operatorname{\mathbb{E}}_{P\sim\operatorname{\mathcal{Q}}}\frac{\operatorname{\mathcal{P}}(P)}{\operatorname{\mathcal{Q}}(P)}e^{\lambda(R(P,T)-R_{S_{\tilde{T}}}(P))}$
$\displaystyle\geq$
$\displaystyle\operatorname{\mathbb{E}}_{P\sim\operatorname{\mathcal{Q}}}\log\frac{\operatorname{\mathcal{P}}(P)}{\operatorname{\mathcal{Q}}(P)}+\lambda\operatorname{\mathbb{E}}_{P\sim\operatorname{\mathcal{Q}}}[R(P,T)-R_{S_{\tilde{T}}}(P)]$
$\displaystyle=$ $\displaystyle-
D_{KL}(\operatorname{\mathcal{Q}}\|\operatorname{\mathcal{P}})+\lambda(R(\operatorname{\mathcal{Q}},T)-\operatorname{\mathbb{E}}_{P\sim\operatorname{\mathcal{Q}}}[R_{S_{\tilde{T}}}(P)]).$

The right-hand side is upper bounded by

$\displaystyle\log\frac{1}{\delta}\operatorname{\mathbb{E}}_{P\sim\operatorname{\mathcal{P}}}\operatorname{\mathbb{E}}_{D_{i}\sim
T,S_{i}\sim
D_{i}^{m_{i}}}^{i=1,\ldots,n}\left[e^{\lambda(R(P,T)-R_{S_{\tilde{T}}}(P))}\right]$
$\displaystyle=$
$\displaystyle\log\frac{1}{\delta}+\log\operatorname{\mathbb{E}}_{P\sim\operatorname{\mathcal{P}}}\operatorname{\mathbb{E}}_{D_{i}\sim
T,S_{i}\sim
D_{i}^{m_{i}}}^{i=1,\ldots,n}\left[e^{\lambda(R(P,T)-R_{S_{\tilde{T}}}(P))}\right]$
$\displaystyle=$
$\displaystyle\log\frac{1}{\delta}+\log\operatorname{\mathbb{E}}_{P\sim\operatorname{\mathcal{P}}}\left[e^{\lambda(R(P,T)-\operatorname{\mathbb{E}}_{S_{\tilde{T}}\sim\tilde{T}}[R_{S_{\tilde{T}}}(P)])}\right]$
$\displaystyle+\log\operatorname{\mathbb{E}}_{P\sim\operatorname{\mathcal{P}}}\operatorname{\mathbb{E}}_{D_{i}\sim
T,S_{i}\sim
D_{i}^{m_{i}}}^{i=1,\ldots,n}\left[e^{\lambda(\operatorname{\mathbb{E}}_{S_{\tilde{T}}}[R_{S_{\tilde{T}}}(P)]-R_{S_{\tilde{T}}}(P))}\right]$
$\displaystyle\leq$
$\displaystyle\log\frac{1}{\delta}+\log\operatorname{\mathbb{E}}_{P\sim\operatorname{\mathcal{P}}}\left[e^{\lambda(R(P,T)-\operatorname{\mathbb{E}}_{S_{\tilde{T}}}[R_{S_{\tilde{T}}}(P)])}\right]+n\Psi_{2}(\frac{\lambda}{n}),$
(18)

where,

$\displaystyle\operatorname{\mathbb{E}}_{S_{\tilde{T}}}[R_{S_{\tilde{T}}}(P)]$
$\displaystyle\triangleq$
$\displaystyle\operatorname{\mathbb{E}}_{(D_{i},m_{i})\sim\tilde{T},S_{i}\sim
D_{i}^{m_{i}}}^{i=1,\ldots,n}[R_{S_{\tilde{T}}}(P)]$ $\displaystyle=$
$\displaystyle\frac{1}{n}\sum_{i=1}^{n}\operatorname{\mathbb{E}}_{(D_{i},m_{i})\sim\tilde{T}}\operatorname{\mathbb{E}}_{S_{i}\sim
D_{i}^{m_{i}}}\operatorname{\mathbb{E}}_{z_{i}\in
D_{i}}\operatorname{\mathbb{E}}_{h_{i}\sim Q(h_{i}|P,S_{i})}[L(h_{i},z_{i})]$
$\displaystyle=$
$\displaystyle\operatorname{\mathbb{E}}_{(D,m)\sim\tilde{T}}\operatorname{\mathbb{E}}_{S\sim
D^{m}}\operatorname{\mathbb{E}}_{z\in D}\operatorname{\mathbb{E}}_{h\sim
Q(h|P,S)}[L(h,z)]$ $\displaystyle=$ $\displaystyle R(P,\tilde{T}).$

Combining the left-hand and right-hand bounds together, we have with at least
probability $1-\delta$,

$\displaystyle R(\operatorname{\mathcal{Q}},T)\leq$
$\displaystyle\frac{1}{n}\sum_{i=1}^{n}\operatorname{\mathbb{E}}_{P\sim\operatorname{\mathcal{Q}}}\left[L(Q(S_{i},P),D_{i})\right]$
$\displaystyle+\frac{1}{\lambda}\left(D_{KL}(\operatorname{\mathcal{Q}}\|\operatorname{\mathcal{P}})+\log\frac{1}{\delta}+n\Psi_{2}(\frac{\lambda}{n})\right)$
$\displaystyle+\frac{1}{\lambda}\log\operatorname{\mathbb{E}}_{P\in\operatorname{\mathcal{P}}}e^{\lambda(R(P,T)-R(P,\tilde{T}))}.$
(19)

Lastly, combining Eq.(19) with Eq.(15) yields Eq.(5).
Furthermore, from Theorem 3, it is straightforward to obtain the following
corollary.

###### Corollary 5

For a target task environment $T$ and an observed task environment $\tilde{T}$
where
$\operatorname{\mathbb{E}}_{\tilde{T}}[D]=\operatorname{\mathbb{E}}_{T}[D]$
and
$\operatorname{\mathbb{E}}_{\tilde{T}}[m]\geq\operatorname{\mathbb{E}}_{T}[m]$,
let $\operatorname{\mathcal{P}}$ be a fixed hyper-prior and $\lambda>0$,
$\beta>0$, then with probability at least $1-\delta$ over samples $S_{1}\in
D_{1}^{m_{1}},\ldots,S_{n}\in D_{n}^{m_{n}}$ where
$(D_{i},m_{i})\sim\tilde{T}$, we have, for all base learners $Q$ and hyper-
posterior $\operatorname{\mathcal{Q}}$,

$\displaystyle R(\operatorname{\mathcal{Q}},T)\leq$
$\displaystyle\hat{R}(\operatorname{\mathcal{Q}},S_{i=1}^{n})+\tilde{\xi}D_{KL}(\operatorname{\mathcal{Q}}\|\operatorname{\mathcal{P}})+\frac{1}{n\beta}\sum_{i=1}^{n}\operatorname{\mathbb{E}}_{P\sim\operatorname{\mathcal{Q}}}\left[D_{KL}(Q(S_{i},P)\|P)\right]$
$\displaystyle+C(\delta,\lambda,\beta,n,m_{i})+\Delta_{\lambda}(\operatorname{\mathcal{P}},\operatorname{\mathcal{Q}},T,\tilde{T}),$
(20)

where
$\Delta_{\lambda}(\operatorname{\mathcal{P}},\operatorname{\mathcal{Q}},T,\tilde{T})=\min\left\\{\frac{1}{\lambda}\log\operatorname{\mathbb{E}}_{P\in\operatorname{\mathcal{P}}}e^{\lambda(R(P,T)-R(P,\tilde{T}))},R(\operatorname{\mathcal{Q}},T)-R(\operatorname{\mathcal{Q}},\tilde{T})\right\\}$,
and $\tilde{\xi}=\frac{1}{\lambda}+\frac{1}{n\beta}$.

Proof  Similar to (16), we have

$\displaystyle R(\operatorname{\mathcal{Q}},\tilde{T})\leq$
$\displaystyle\frac{1}{n}\sum_{i=1}^{n}\operatorname{\mathbb{E}}_{P\sim\operatorname{\mathcal{Q}}}\left[L(Q(S_{i},P),D_{i})\right]$
$\displaystyle+\frac{1}{\lambda}\left(D_{KL}(\operatorname{\mathcal{Q}}\|\operatorname{\mathcal{P}})+\log\frac{1}{\delta}+n\Psi_{2}(\frac{\lambda}{n})\right).$

A simple reorganization of the terms leads to,

$\displaystyle R(\operatorname{\mathcal{Q}},T)\leq$
$\displaystyle\frac{1}{n}\sum_{i=1}^{n}\operatorname{\mathbb{E}}_{P\sim\operatorname{\mathcal{Q}}}\left[L(Q(S_{i},P),D_{i})\right]$
$\displaystyle+\frac{1}{\lambda}\left(D_{KL}(\operatorname{\mathcal{Q}}\|\operatorname{\mathcal{P}})+\log\frac{1}{\delta}+n\Psi_{2}(\frac{\lambda}{n})\right)+(R(\operatorname{\mathcal{Q}},T)-R(\operatorname{\mathcal{Q}},\tilde{T})).$
(21)

Combining Eq.(21) with Eq.(19) and Eq.(15) gives the bound in Eq.(20).
Note that although Eq.(20) gives a potentially tighter bound than Eq.(5),
empirically it makes little difference because
$R(\operatorname{\mathcal{Q}},T)-R(\operatorname{\mathcal{Q}},\tilde{T})$ is
inestimable in practice and cannot be directly optimized as a function of
$\operatorname{\mathcal{Q}}$. We will only numerically estimate its value in
synthetic datasets in order to estimate the bound.

###  A.3 Proof of Theorem 4

For a target task environment $T$ and an observed task environment $\tilde{T}$
where
$\operatorname{\mathbb{E}}_{\tilde{T}}[D]=\operatorname{\mathbb{E}}_{T}[D]$
and
$\operatorname{\mathbb{E}}_{\tilde{T}}[m]\geq\operatorname{\mathbb{E}}_{T}[m]$,
let $\operatorname{\mathcal{P}}$ be a fixed hyper-prior and $\lambda>0$,
$\beta>0$, then with probability at least $1-\delta$ over samples $S_{1}\in
D_{1}^{m_{1}},\ldots,S_{n}\in D_{n}^{m_{n}}$ where
$(D_{i},m_{i})\sim\tilde{T}$, and subsamples $S_{1}^{\prime}\in
D_{1}^{m_{1}^{\prime}}\subset S_{1},\ldots,S_{n}^{\prime}\in
D_{n}^{m_{n}^{\prime}}\subset S_{n}$, where
$\operatorname{\mathbb{E}}[m_{i}^{\prime}]=\operatorname{\mathbb{E}}_{T}[m]$,
we have, for all base learner $Q$ and all hyper-posterior
$\operatorname{\mathcal{Q}}$,

$\displaystyle R(\operatorname{\mathcal{Q}},T)\leq$
$\displaystyle\operatorname{\mathbb{E}}_{P\sim\operatorname{\mathcal{Q}}}\left[\frac{1}{n}\sum_{i=1}^{n}\hat{L}(Q(S_{i}^{\prime},P),S_{i})\right]+\tilde{\xi}D_{KL}(\operatorname{\mathcal{Q}}\|\operatorname{\mathcal{P}})+\frac{1}{n\beta}\sum_{i=1}^{n}\operatorname{\mathbb{E}}_{P\sim\operatorname{\mathcal{Q}}}\left[D_{KL}(Q(S_{i}^{\prime},P)\|P)\right]$
$\displaystyle+C(\delta,\lambda,\beta,n,m_{i}),$

where $\tilde{\xi}=\frac{1}{\lambda}+\frac{1}{n\beta}$.

Proof  The "task environment generalization bound" is the same as the one in
Theorem 2, because the base-learner in observed and target task have the same
task environment $T$. Therefore, we have

$\displaystyle R(\operatorname{\mathcal{Q}},T)\leq$
$\displaystyle\frac{1}{n}\sum_{i=1}^{n}\operatorname{\mathbb{E}}_{P\sim\operatorname{\mathcal{Q}}}\left[L(Q(S^{\prime}_{i},P),D_{i})\right]+\frac{1}{\lambda}\left(D_{KL}(\operatorname{\mathcal{Q}}\|\operatorname{\mathcal{P}})+\log\frac{1}{\delta}\right)+\frac{n}{\lambda}\Psi_{2}(\frac{\lambda}{n}).$
(22)

As for the "task-specific generalization bound", define,

$\displaystyle\hat{L}(\operatorname{\mathbf{h}})$
$\displaystyle=\frac{1}{n}\sum_{i=1}^{n}\frac{1}{m_{i}}\sum_{j=1}^{m_{i}}l(h_{i},z_{ij}),\;\;L(\operatorname{\mathbf{h}})=\frac{1}{n}\sum_{i=1}^{n}\operatorname{\mathbb{E}}_{z_{i}\sim
D_{i}}l(h_{i},z_{i}),$

where $z_{ij}\in S_{i}$ which is sampled from $D_{i}$. According to the Markov
inequality, with at least $1-\delta$ probability, we have

$\displaystyle\operatorname{\mathbb{E}}_{P\sim\operatorname{\mathcal{P}}}\operatorname{\mathbb{E}}_{\operatorname{\mathbf{h}}\sim
P^{n}}\left[e^{n\beta(L(\operatorname{\mathbf{h}})-\hat{L}(\operatorname{\mathbf{h}}))}\right]\leq\frac{1}{\delta}\operatorname{\mathbb{E}}_{P\sim\operatorname{\mathcal{P}}}\operatorname{\mathbb{E}}_{\operatorname{\mathbf{h}}\sim
P^{n}}\operatorname{\mathbb{E}}_{\operatorname{\mathbf{S}}\sim\operatorname{\mathbf{D}}^{\operatorname{\mathbf{m}}}}\left[e^{n\beta(L(\operatorname{\mathbf{h}})-\hat{L}(\operatorname{\mathbf{h}}))}\right]$

Now take the logarithm of both sides, and transform the expectation over
$\operatorname{\mathcal{P}},P$ to $\operatorname{\mathcal{Q}},Q$, where we use
base-learner $Q(S_{i}^{\prime},P)$ with $S^{\prime}_{i}\in
D_{i}^{m^{\prime}_{i}}$. Then the LHS becomes

$\displaystyle\log\operatorname{\mathbb{E}}_{P\sim\operatorname{\mathcal{P}}}\operatorname{\mathbb{E}}_{\operatorname{\mathbf{h}}\sim
P^{n}}\left[e^{n\beta(L(\operatorname{\mathbf{h}})-\hat{L}(\operatorname{\mathbf{h}}))}\right]$
$\displaystyle=$
$\displaystyle\log\operatorname{\mathbb{E}}_{P\sim\operatorname{\mathcal{Q}}}\operatorname{\mathbb{E}}_{\operatorname{\mathbf{h}}\sim\operatorname{\mathbf{Q}}(\operatorname{\mathbf{S}}^{\prime},P)}[\frac{\operatorname{\mathcal{P}}(P)\prod_{i=1}^{n}P(h_{i})}{\operatorname{\mathcal{Q}}(P)\prod_{i=1}^{n}Q_{i}(h_{i}|S_{i}^{\prime},P)}e^{n\beta(L(\operatorname{\mathbf{h}})-\hat{L}(\operatorname{\mathbf{h}}))}]$
$\displaystyle\geq$ $\displaystyle-
D_{KL}(\operatorname{\mathcal{Q}}\|\operatorname{\mathcal{P}})-\sum_{i=1}^{n}\operatorname{\mathbb{E}}_{P\sim\operatorname{\mathcal{Q}}}\left[D_{KL}(Q(S_{i}^{\prime},P)\|P)\right]$
$\displaystyle\quad+\beta\operatorname{\mathbb{E}}_{P\sim\operatorname{\mathcal{Q}}}[\sum_{i=1}^{n}L(Q(S_{i}^{\prime},P),D_{i})]-\beta\operatorname{\mathbb{E}}_{P\sim\operatorname{\mathcal{Q}}}[\sum_{i=1}^{n}\hat{L}(Q(S_{i}^{\prime},P),S_{i})].$

The first equation uses the fact that the hyper-prior
$\operatorname{\mathcal{P}}$ and hyper-posterior $\operatorname{\mathcal{Q}}$
as well as the prior $P$ are shared across all $n$ observed tasks. The
inequality uses Jensen’s inequality to move the logarithm inside expectation.

The RHS is

$\displaystyle\log\frac{1}{\delta}+\log\operatorname{\mathbb{E}}_{P\sim\operatorname{\mathcal{P}}}\operatorname{\mathbb{E}}_{\operatorname{\mathbf{h}}\sim
P^{n}}\operatorname{\mathbb{E}}_{\operatorname{\mathbf{S}}\sim\operatorname{\mathbf{D}}^{\operatorname{\mathbf{m}}}}\left[e^{n\beta(L(h)-\hat{L}(h))}\right]$
$\displaystyle=$
$\displaystyle\log\frac{1}{\delta}+\log\operatorname{\mathbb{E}}_{P\sim\operatorname{\mathcal{P}}}\operatorname{\mathbb{E}}_{\operatorname{\mathbf{h}}\sim
P^{n}}\prod_{i=1}^{n}\prod_{j=1}^{m_{i}}\operatorname{\mathbb{E}}_{z_{ij}\sim
D_{i}}\left[e^{\frac{\beta}{m_{i}}(\operatorname{\mathbb{E}}_{z_{i}\sim
D_{i}}[l(h_{i},z_{i})]-l(h_{i},z_{ij}))}\right]$ $\displaystyle=$
$\displaystyle\log\frac{1}{\delta}+\sum_{i=1}^{n}m_{i}\Psi_{1}(\frac{\beta}{m_{i}}).$

Now, combining the LHS and RHS together, we get that with at least $1-\delta$
probability,

$\displaystyle\operatorname{\mathbb{E}}_{P\sim\operatorname{\mathcal{Q}}}[\frac{1}{n}\sum_{i=1}^{n}L(Q(S^{\prime}_{i},P),D_{i})]$
$\displaystyle\leq$
$\displaystyle\operatorname{\mathbb{E}}_{P\sim\operatorname{\mathcal{Q}}}\left[\frac{1}{n}\sum_{i=1}^{n}L(Q(S^{\prime}_{i},P),S_{i})\right]+\frac{1}{n\beta}D_{KL}(\operatorname{\mathcal{Q}}\|\operatorname{\mathcal{P}})+\frac{1}{n\beta}\sum_{i=1}^{n}\operatorname{\mathbb{E}}_{P\sim\operatorname{\mathcal{Q}}}\left[D_{KL}(Q(S^{\prime}_{i},P)\|P)\right]$
$\displaystyle+\frac{1}{n\beta}\log\frac{1}{\delta}+\frac{1}{n}\sum_{i=1}^{n}\frac{m_{i}}{\beta}\Psi_{1}(\frac{\beta}{m_{i}}).$
(23)

Combining Eq.(22) with Eq.(23) immediately yields Eq.(6).

##  Appendix B Derivations of MAML and Reptile

In this section, we derive a couple of meta-learning algorithms based on the
MAP estimation of PAC-Bayesian bounds. To this end, we assume that the
distribution families of the hyper-posterior $\operatorname{\mathcal{Q}}(P)$
and posterior $Q_{i}(h)$ are from delta functions. In addition, we use the
isotrophic Gaussian priors for the hyper-prior $\operatorname{\mathcal{P}}(P)$
and the prior $P(h)$ on all model parameters,

$\displaystyle\operatorname{\mathcal{P}}(P)$
$\displaystyle=\operatorname{\mathcal{N}}(\operatorname{\mathbf{p}}|0,\sigma_{0}^{2})$
$\displaystyle\operatorname{\mathcal{Q}}(P)$
$\displaystyle=\delta(\operatorname{\mathbf{p}}=\operatorname{\mathbf{p}}_{0})$
$\displaystyle P(h)$
$\displaystyle=\operatorname{\mathcal{N}}(\operatorname{\mathbf{h}}|\operatorname{\mathbf{p}},\sigma^{2})$
$\displaystyle Q_{i}(h)$
$\displaystyle=\delta(\operatorname{\mathbf{h}}=\operatorname{\mathbf{q}}_{i})\;\;\forall
i=1,\ldots,n.$

This way we have a closed form solution for the two KL terms, which are (up to
a constant)

$\displaystyle
D_{KL}(\operatorname{\mathcal{Q}}\|\operatorname{\mathcal{P}})=$
$\displaystyle\int
d\operatorname{\mathbf{p}}\delta(\operatorname{\mathbf{p}}=\operatorname{\mathbf{p}}_{0})\cdot\left(\frac{\|\operatorname{\mathbf{p}}\|^{2}}{2\sigma_{0}^{2}}+\frac{k}{2}\log(2\pi\sigma_{0}^{2})+\log\delta(\operatorname{\mathbf{p}}=\operatorname{\mathbf{p}}_{0})\right)$
$\displaystyle=$
$\displaystyle\frac{\|\operatorname{\mathbf{p}}_{0}\|^{2}}{2\sigma_{0}^{2}}+\frac{k}{2}\log(2\pi\sigma_{0}^{2})+c,$

where $k$ is the dimension of $\operatorname{\mathbf{p}}$ and $c$ is a
constant. Similarly,

$\displaystyle\operatorname{\mathbb{E}}_{P\sim\operatorname{\mathcal{Q}}}[D_{KL}(Q_{i}|P)]$
$\displaystyle=$ $\displaystyle\int
d\operatorname{\mathbf{p}}\delta(\operatorname{\mathbf{p}}=\operatorname{\mathbf{p}}_{0})\int
d\operatorname{\mathbf{h}}\delta(\operatorname{\mathbf{h}}=\operatorname{\mathbf{q}}_{i})\cdot\left(\frac{\|\operatorname{\mathbf{h}}-\operatorname{\mathbf{p}}\|^{2}}{2\sigma^{2}}+\frac{k}{2}\log(2\pi\sigma^{2})+\log\delta(\operatorname{\mathbf{h}}=\operatorname{\mathbf{q}}_{i})\right)$
$\displaystyle=$ $\displaystyle\int
d\operatorname{\mathbf{p}}\delta(\operatorname{\mathbf{p}}=\operatorname{\mathbf{p}}_{0})\cdot\frac{\|\operatorname{\mathbf{p}}-\operatorname{\mathbf{q}}_{i}\|^{2}}{2\sigma^{2}}+\frac{k}{2}\log(2\pi\sigma^{2})+c$
$\displaystyle=$
$\displaystyle\frac{\|\operatorname{\mathbf{p}}_{0}-\operatorname{\mathbf{q}}_{i}\|^{2}}{2\sigma^{2}}+\frac{k}{2}\log(2\pi\sigma^{2})+c.$

Plugging in the above results, the PAC-Bayesian bound ($PacB$) in Eq.(5) and
Eq.(6) are both of the form of,

$\displaystyle
PacB=\frac{1}{n}\sum_{i=1}^{n}L(\operatorname{\mathbf{q}}_{i},S_{i})+\frac{\tilde{\xi}\|\operatorname{\mathbf{p}}_{0}\|^{2}}{2\sigma_{0}^{2}}+\frac{1}{n\beta}\sum_{i=1}^{n}\frac{\|\operatorname{\mathbf{p}}_{0}-\operatorname{\mathbf{q}}_{i}\|^{2}}{2\sigma^{2}}+C^{\prime},$

where the constant $C^{\prime}$ corresponding to Eq.(5) and Eq.(6) are
different by $\Delta_{\lambda}$. The only free variable of $PacB$ is
$\operatorname{\mathbf{p}}_{0}$. The base-learner
$\operatorname{\mathbf{q}}_{i}$ can be any function of
$\operatorname{\mathbf{p}}_{0}$ and $S_{i}$ for Eq.(5) or $S_{i}^{\prime}$ for
Eq.(6). One could find the MAP estimation of $PacB$ by gradient descent with
respect to $\operatorname{\mathbf{p}}_{0}$.

Note that in Eq.(5), for a given $\operatorname{\mathbf{p}}_{0}$ and $S_{i}$,
there exists an optimal base-learner $\operatorname{\mathbf{q}}_{i}^{*}$ in
the form of,

$\displaystyle\operatorname{\mathbf{q}}_{i}^{*}=\operatorname*{\mathop{\mathrm{argmin}}}_{\operatorname{\mathbf{q}}_{i}}(PacB)=\operatorname*{\mathop{\mathrm{argmin}}}_{\operatorname{\mathbf{q}}_{i}}\left[L(\operatorname{\mathbf{q}}_{i},S_{i})+\frac{\|\operatorname{\mathbf{p}}_{0}-\operatorname{\mathbf{q}}_{i}\|^{2}}{2\beta\sigma^{2}}\right].$

Given the optimal $\operatorname{\mathbf{q}}_{i}^{*}$, the full derivative of
$PacB$ with respect to $\operatorname{\mathbf{p}}_{0}$ is substantially
simpler,

$\displaystyle\frac{d(PacB)}{d\operatorname{\mathbf{p}}_{0}}$
$\displaystyle=\frac{\partial(PacB)}{\partial\operatorname{\mathbf{p}}_{0}}+\left\langle\frac{\partial\operatorname{\mathbf{q}}_{i}^{*}}{\partial\operatorname{\mathbf{p}}_{0}},\frac{\partial(PacB)}{\partial\operatorname{\mathbf{q}}_{i}^{*}}\right\rangle$
$\displaystyle=\frac{\partial(PacB)}{\partial\operatorname{\mathbf{p}}_{0}}=\frac{\tilde{\xi}\operatorname{\mathbf{p}}_{0}}{\sigma_{0}^{2}}+\frac{1}{n}\sum_{i=1}^{n}\frac{\operatorname{\mathbf{p}}_{0}-\operatorname{\mathbf{q}}_{i}^{*}}{\beta\sigma^{2}},$
(24)

where the 2nd equation is because
$\frac{\partial(PacB)}{\partial\operatorname{\mathbf{q}}_{i}^{*}}=0$ for the
optimal base-leaner $\operatorname{\mathbf{q}}_{i}^{*}$. Eq.(24) is the
equivalent to the meta-update of the Reptile algorithm [Nichol et al., 2018],
except that Reptile does not solve for the optimal base learner
$\operatorname{\mathbf{q}}_{i}^{*}$.

From the optimal condition, the base-learner
$\operatorname{\mathbf{q}}_{i}^{*}$ satisfies,

$\displaystyle\frac{\operatorname{\mathbf{p}}_{0}-\operatorname{\mathbf{q}}_{i}^{*}}{\beta\sigma^{2}}=\nabla_{\operatorname{\mathbf{q}}_{i}^{*}}L(\operatorname{\mathbf{q}}_{i}^{*},S_{i}).$

Therefore, we can rewrite Eq.(24) in the form of the _implicit gradient_ ,

$\displaystyle\frac{d(PacB)}{d\operatorname{\mathbf{p}}_{0}}=\frac{\tilde{\xi}\operatorname{\mathbf{p}}_{0}}{\sigma_{0}^{2}}+\frac{1}{n}\sum_{i=1}^{n}\nabla_{\operatorname{\mathbf{q}}^{*}_{i}}L(\operatorname{\mathbf{q}}_{i}^{*},S_{i}).$

In contrast, the standard multi-task objective uses the _explicit gradient_ ,
where $\operatorname{\mathbf{q}}_{i}=\operatorname{\mathbf{p}}_{0}$ and

$\displaystyle\frac{d(PacB)}{d\operatorname{\mathbf{p}}_{0}}=\frac{\tilde{\xi}\operatorname{\mathbf{p}}_{0}}{\sigma_{0}^{2}}+\frac{1}{n}\sum_{i=1}^{n}\nabla_{\operatorname{\mathbf{p}}_{0}}L(\operatorname{\mathbf{p}}_{0},S_{i}).$

##  Appendix C Derivations of PACMAML

For Theorem 4, we use the following posterior as the base-learner for observed
task $\tau_{i}$,

$\displaystyle
Q_{i}(S_{i}^{\prime},P)(h)=\frac{P(h)\exp(-\alpha\hat{L}(h,S_{i}^{\prime}))}{Z_{\alpha}(S_{i}^{\prime},P)}.$

Plugging this $Q_{i}$ into Eq.(6), we have

$\displaystyle R(\operatorname{\mathcal{Q}},T)$ $\displaystyle\leq$
$\displaystyle\operatorname{\mathbb{E}}_{P\sim\operatorname{\mathcal{Q}}}\left[\frac{1}{n}\sum_{i=1}^{n}\hat{L}(Q_{i},S_{i})\right]+\tilde{\xi}D_{KL}(\operatorname{\mathcal{Q}}\|\operatorname{\mathcal{P}})+\frac{1}{n\beta}\sum_{i=1}^{n}\operatorname{\mathbb{E}}_{P\sim\operatorname{\mathcal{Q}}}\left[D_{KL}(Q_{i}\|P)\right]+C$
$\displaystyle=$
$\displaystyle\frac{1}{n}\sum_{i=1}^{n}\operatorname{\mathbb{E}}_{P\sim\operatorname{\mathcal{Q}}}\left[\hat{L}(Q_{i},S_{i})+\frac{1}{\beta}D_{KL}(Q_{i}\|P)\right]+\tilde{\xi}D_{KL}(\operatorname{\mathcal{Q}}\|\operatorname{\mathcal{P}})+C$
$\displaystyle=$
$\displaystyle\frac{1}{n}\sum_{i=1}^{n}\operatorname{\mathbb{E}}_{P\sim\operatorname{\mathcal{Q}}}\operatorname{\mathbb{E}}_{h\sim
Q_{i}}\left[\hat{L}(h,S_{i})+\frac{1}{\beta}\log Q_{i}(h)-\frac{1}{\beta}\log
P(h)\right]+\tilde{\xi}D_{KL}(\operatorname{\mathcal{Q}}\|\operatorname{\mathcal{P}})+C$
$\displaystyle=$
$\displaystyle\frac{1}{n}\sum_{i=1}^{n}\operatorname{\mathbb{E}}_{P\sim\operatorname{\mathcal{Q}}}\operatorname{\mathbb{E}}_{h\sim
Q_{i}}\left[\hat{L}(h,S_{i})-\frac{\alpha}{\beta}\hat{L}(h,S_{i}^{\prime})-\frac{1}{\beta}\log
Z_{\alpha}(S_{i}^{\prime},P))\right]+\tilde{\xi}D_{KL}(\operatorname{\mathcal{Q}}\|\operatorname{\mathcal{P}})+C$
$\displaystyle=$
$\displaystyle\frac{1}{n}\sum_{i=1}^{n}\operatorname{\mathbb{E}}_{P\sim\operatorname{\mathcal{Q}}}[-\frac{1}{\beta}\log
Z_{\alpha}(S_{i}^{\prime},P)+\hat{L}(Q_{i},S_{i})-\frac{\alpha}{\beta}\hat{L}(Q_{i},S_{i}^{\prime})]+\tilde{\xi}D_{KL}(\operatorname{\mathcal{Q}}\|\operatorname{\mathcal{P}})+C.$

where
$C=\tilde{\xi}\log\frac{2}{\delta}+\frac{n}{\lambda}\Psi(\frac{\lambda}{n})+\frac{1}{n}\sum_{i=1}^{n}\frac{m_{i}}{\beta}\Psi(\frac{\beta}{m_{i}})$.

###  C.1 The Gradient Estimator of PACOH and PACMAML

Assuming that the model hypothesis $h$ is parameterized by
$\operatorname{\mathbf{v}}$ such that
$\hat{L}(h,S_{i})\triangleq\hat{L}(\operatorname{\mathbf{v}},S_{i})$, and
$\operatorname{\mathbf{v}}$ has prior
$P(\operatorname{\mathbf{v}})=\operatorname{\mathcal{N}}(\operatorname{\mathbf{v}}|\operatorname{\mathbf{p}},\sigma^{2})$
with meta-parameter $\operatorname{\mathbf{p}}$, then

$\displaystyle\log
Z_{\beta}(S_{i},\operatorname{\mathbf{p}})=\log\int\operatorname{\mathcal{N}}(\operatorname{\mathbf{v}}|\operatorname{\mathbf{p}},\sigma^{2})\exp(-\beta\hat{L}(\operatorname{\mathbf{v}},S_{i}))d\operatorname{\mathbf{v}}.$

Note that the parameter $\operatorname{\mathbf{p}}$ appears in the probability
distribution of the expectation, and the naive Monte-Carlo gradient estimator
of such gradient is known to exhibit high variance. To reduce the variance, we
apply the reparameterization trick [Kingma and Welling, 2013] and rewrite
$\operatorname{\mathbf{v}}=\operatorname{\mathbf{p}}+\operatorname{\mathbf{w}}$
with
$\operatorname{\mathbf{w}}\sim\operatorname{\mathcal{N}}(\operatorname{\mathbf{w}}|{\bf
0},\sigma^{2})$, then

$\displaystyle\log
Z_{\beta}(S_{i},\operatorname{\mathbf{p}})=\log\int\operatorname{\mathcal{N}}(\operatorname{\mathbf{w}}|{\bf
0},\sigma^{2})\exp(-\beta\hat{L}(\operatorname{\mathbf{p}}+\operatorname{\mathbf{w}},S_{i}))d\operatorname{\mathbf{w}}.$

This leads to the gradient of $W_{1}$ in the following form,

$\displaystyle\frac{d}{d\operatorname{\mathbf{p}}}W_{1}$
$\displaystyle=-\frac{1}{\beta}\frac{d}{d\operatorname{\mathbf{p}}}\log
Z_{\beta}(S_{i},\operatorname{\mathbf{p}})=\int
Q^{\beta}_{i}(\operatorname{\mathbf{w}};S_{i})\frac{\partial\hat{L}(\operatorname{\mathbf{p}}+\operatorname{\mathbf{w}},S_{i})}{\partial\operatorname{\mathbf{p}}}d\operatorname{\mathbf{w}},$
$\displaystyle\text{where,}\;\;Q^{\beta}_{i}(\operatorname{\mathbf{w}};S_{i})\propto\operatorname{\mathcal{N}}(\operatorname{\mathbf{w}}|{\bf
0},\sigma^{2})\exp(-\beta\hat{L}(\operatorname{\mathbf{p}}+\operatorname{\mathbf{w}},S_{i})).$

As for $W_{2}$, the first term is simlar to $W_{1}$, but we also need to
evaluate the gradient of
$\hat{L}^{\Delta}_{\frac{\alpha}{\beta}}(Q^{\alpha}_{i},S_{i},S_{i}^{\prime})$,
which is

$\displaystyle\frac{d}{d\operatorname{\mathbf{p}}}\hat{L}^{\Delta}_{\frac{\alpha}{\beta}}(Q^{\alpha}_{i},S_{i},S_{i}^{\prime})$
$\displaystyle=\int
Q_{i}^{\alpha}(\operatorname{\mathbf{w}};S_{i}^{\prime})\frac{\partial\hat{L}^{\Delta}_{\frac{\alpha}{\beta}}(\operatorname{\mathbf{p}}+\operatorname{\mathbf{w}},S_{i},S_{i}^{\prime})}{\partial\operatorname{\mathbf{p}}}d\operatorname{\mathbf{w}}+\int\frac{\partial
Q_{i}^{\alpha}(\operatorname{\mathbf{w}};S^{\prime}_{i})}{\partial\operatorname{\mathbf{p}}}\hat{L}^{\Delta}_{\frac{\alpha}{\beta}}(\operatorname{\mathbf{p}}+\operatorname{\mathbf{w}},S_{i},S_{i}^{\prime})d\operatorname{\mathbf{w}}.$
(25)

The second term of Eq.(25) is equivalent to,

$\displaystyle\int\frac{\partial
Q_{i}^{\alpha}(\operatorname{\mathbf{w}};S_{i}^{\prime})}{\partial\operatorname{\mathbf{p}}}\hat{L}^{\Delta}_{\frac{\alpha}{\beta}}(\operatorname{\mathbf{p}}+\operatorname{\mathbf{w}},S_{i},S_{i}^{\prime})d\operatorname{\mathbf{w}}$
$\displaystyle=$
$\displaystyle-\frac{1}{\beta}\frac{\partial}{\partial\operatorname{\mathbf{p}}}\int
Q_{i}^{\alpha}(\operatorname{\mathbf{w}};S_{i}^{\prime})\text{stop\\_grad}\left(-\beta\hat{L}^{\Delta}_{\frac{\alpha}{\beta}}(\operatorname{\mathbf{p}}+\operatorname{\mathbf{w}},S_{i},S_{i}^{\prime})\right)d\operatorname{\mathbf{w}}.$

The Monte-Carlo gradient estimator of this has the same high-variance problem
as in the policy gradient method, which causes unreliable inference without
warm-start. Instead, we apply the cold-start policy gradient method by
approximating the loss with the one from the softmax value function [Ding and
Soricut, 2017] as follows,

$\displaystyle-\frac{1}{\beta}\int
Q_{i}^{\alpha}(\operatorname{\mathbf{w}};S_{i}^{\prime})\text{stop\\_grad}\left(-\beta\hat{L}^{\Delta}_{\frac{\alpha}{\beta}}(\operatorname{\mathbf{p}}+\operatorname{\mathbf{w}},S_{i},S_{i}^{\prime})\right)d\operatorname{\mathbf{w}}$
$\displaystyle\geq$ $\displaystyle-\frac{1}{\beta}\log\int
Q_{i}^{\alpha}(\operatorname{\mathbf{w}};S_{i}^{\prime})\exp\left(\text{stop\\_grad}\left(-\beta\hat{L}^{\Delta}_{\frac{\alpha}{\beta}}(\operatorname{\mathbf{p}}+\operatorname{\mathbf{w}},S_{i},S_{i}^{\prime})\right)\right)d\operatorname{\mathbf{w}}.$

Then we take the gradient of the softmax value function,

$\displaystyle-\frac{1}{\beta}\frac{\partial}{\partial\operatorname{\mathbf{p}}}\log\int
Q_{i}^{\alpha}(\operatorname{\mathbf{w}};S_{i}^{\prime})\exp\left(\text{stop\\_grad}\left(-\beta\hat{L}^{\Delta}_{\frac{\alpha}{\beta}}(\operatorname{\mathbf{p}}+\operatorname{\mathbf{w}},S_{i},S_{i}^{\prime})\right)\right)d\operatorname{\mathbf{w}}$
$\displaystyle=$ $\displaystyle-\frac{1}{\beta}\int
Q_{i}^{\beta}(\operatorname{\mathbf{w}};S_{i})\frac{\partial\log
Q_{i}^{\alpha}(\operatorname{\mathbf{w}};S_{i}^{\prime})}{\partial\operatorname{\mathbf{p}}}d\operatorname{\mathbf{w}}$
$\displaystyle=$
$\displaystyle\frac{\alpha}{\beta}\int\left(Q_{i}^{\beta}(\operatorname{\mathbf{w}};S_{i})-Q_{i}^{\alpha}(\operatorname{\mathbf{w}};S_{i}^{\prime})\right)\frac{\partial\hat{L}(\operatorname{\mathbf{p}}+\operatorname{\mathbf{w}},S^{\prime}_{i})}{\partial\operatorname{\mathbf{p}}}d\operatorname{\mathbf{w}}.$

This yields the overall gradient of $W_{2}$ to be,

$\displaystyle\frac{d}{d\operatorname{\mathbf{p}}}W_{2}\simeq$
$\displaystyle\frac{\alpha}{\beta}\int
Q_{i}^{\beta}(\operatorname{\mathbf{w}};S_{i})\frac{\partial\hat{L}(\operatorname{\mathbf{p}}+\operatorname{\mathbf{w}};S_{i}^{\prime})}{\partial\operatorname{\mathbf{p}}}d\operatorname{\mathbf{w}}+\int
Q_{i}^{\alpha}(\operatorname{\mathbf{w}};S_{i}^{\prime})\frac{\partial\hat{L}^{\Delta}_{\frac{\alpha}{\beta}}(\operatorname{\mathbf{p}}+\operatorname{\mathbf{w}},S_{i},S_{i}^{\prime})}{\partial\operatorname{\mathbf{p}}}d\operatorname{\mathbf{w}}$
$\displaystyle=$ $\displaystyle\int
Q_{i}^{\alpha}(\operatorname{\mathbf{w}};S_{i}^{\prime})\frac{\partial\hat{L}(\operatorname{\mathbf{p}}+\operatorname{\mathbf{w}};S_{i})}{\partial\operatorname{\mathbf{p}}}d\operatorname{\mathbf{w}}+\frac{\alpha}{\beta}\int\left(Q_{i}^{\beta}(\operatorname{\mathbf{w}};S_{i})-Q_{i}^{\alpha}(\operatorname{\mathbf{w}};S_{i}^{\prime})\right)\frac{\partial\hat{L}(\operatorname{\mathbf{p}}+\operatorname{\mathbf{w}};S_{i}^{\prime})}{\partial\operatorname{\mathbf{p}}}d\operatorname{\mathbf{w}}.$

##  Appendix D Experiment Details of the Regression Problem

###  D.1 Gaussian Process Model Details

We use the Gaussian process prior, where $P_{\mathchar
28946\relax}(h)=\mathcal{GP}(h|m_{\mathchar 28946\relax}(x),k_{\mathchar
28946\relax}(x,x^{\prime}))$ and $k_{\mathchar
28946\relax}(x,x^{\prime})=\frac{1}{2}\exp{(-\|\phi_{\mathchar
28946\relax}(x)-\phi_{\mathchar 28946\relax}(x^{\prime})\|^{2}})$. Both
$m_{\mathchar 28946\relax}(x)$ and $\phi_{\mathchar 28946\relax}(x)$ are
instantiated to be neural networks. The networks are composed of an input
layer of size $1\times 32$, a hidden layer of size $32\times 32$.
$m_{\mathchar 28946\relax}$ and $\phi_{\mathchar 28946\relax}$ has an output
layer of size $32\times 1$ and $32\times 2$, respectively.

We focused on regression problems where for every example
$z_{j}=(x_{j},y_{j})$ and a hypothesis $h$, the $l_{2}$-loss function is used
so that $l(h,z_{j})=\|h(x_{j})-y_{j}\|_{2}^{2}$. This leads to a Gaussian
likelihood function. Assuming there are $m$ examples in the dataset, we have

$\displaystyle P(y|h,x)=$
$\displaystyle\operatorname{\mathcal{N}}(h,\frac{m}{2\alpha}I)$
$\displaystyle=$ $\displaystyle\frac{1}{(\pi
m/\alpha)^{m/2}}\exp\left(-\frac{\alpha}{m}\sum_{j=1}^{m}(h(x_{j})-y_{j})^{2}\right).$

As a result, the partition function $Z_{\alpha}(S,P)$ is,

$\displaystyle Z_{\alpha}(S,P)$ $\displaystyle=(\pi
m/\alpha)^{m/2}\int_{h}dhP(y|h,x)P_{\mathchar 28946\relax}(h)$
$\displaystyle=(\pi m/\alpha)^{m/2}\operatorname{\mathcal{N}}(y|m_{\mathchar
28946\relax}(x),k_{\mathchar 28946\relax}(x,x^{\prime})+\frac{m}{2\alpha}I),$

We apply the GP base-learner $Q$ on the the observed data $S_{i}$ of task
$\tau_{i}$. For notation simplicity, let us denote
$Q_{i}(h^{i}|S_{i},P)=\mathcal{N}(\mu_{i},K_{i})$, where $h^{i}$ denotes the
model hypothesis (predictions) of the $m_{i}$ examples in $S_{i}$. Then we
have,

$\displaystyle\hat{L}(Q_{i},S_{i})=$ $\displaystyle\frac{1}{m_{i}}\int
Q_{i}(h^{i})(y^{i}-h^{i})^{\top}(y^{i}-h^{i})dh^{i}$ $\displaystyle=$
$\displaystyle\frac{1}{m_{i}}\left(y^{i\top}y^{i}-2\mu_{i}^{\top}y^{i}+\mu_{i}^{\top}\mu_{i}+\text{tr}(K_{i})\right),$

where $y^{i}$ denotes the labels of the $m_{i}$ examples in $S_{i}$.

The hyper-prior $\operatorname{\mathcal{P}}(P_{\mathchar
28946\relax}):=\operatorname{\mathcal{P}}(\mathchar
28946\relax)=\operatorname{\mathcal{N}}(\mathchar
28946\relax|0,\sigma_{0}^{2}I)$ is an isotropic Gaussian defined over the
network parameters $\mathchar 28946\relax$, where we take $\sigma_{0}^{2}=3$
in our numerical experiments. The MAP approximated hyper-posterior takes the
form of a delta function, where $\operatorname{\mathcal{Q}}_{\mathchar
28946\relax_{0}}(P_{\mathchar
28946\relax}):=\operatorname{\mathcal{Q}}_{\mathchar
28946\relax_{0}}(\mathchar 28946\relax)=\delta(\mathchar 28946\relax=\mathchar
28946\relax_{0})$. As a result, we have

$\displaystyle D_{KL}(\operatorname{\mathcal{Q}}_{\mathchar
28946\relax_{0}}\|\operatorname{\mathcal{P}})$ $\displaystyle=$
$\displaystyle\int d\mathchar 28946\relax\delta(\mathchar
28946\relax=\mathchar 28946\relax_{0})\left(\frac{\|\mathchar
28946\relax\|^{2}}{2\sigma_{0}^{2}}+\frac{k}{2}\log(2\pi\sigma_{0}^{2})+\log\delta(\mathchar
28946\relax=\mathchar 28946\relax_{0})\right)$ $\displaystyle=$
$\displaystyle\frac{\|\mathchar
28946\relax_{0}\|^{2}}{2\sigma_{0}^{2}}+\frac{k}{2}\log(2\pi\sigma_{0}^{2})+c,$

which combined with $\tilde{\xi}$ becomes the regularizer on the parameters
$\mathchar 28946\relax_{0}$.

###  D.2 Experiment Details

In the Sinusoid experiment, the number of available examples per observed task
$m_{i}\in\left\\{5,10,30,50,100\right\\}$. Under the setting of PACOH (Theorem
3), for each different $m_{i}$, we did a grid search on
$\beta/m_{i}\in\left\\{10,30,100\right\\}$. Under the setting of PACMAML
(Theorem 4), for each different $m_{i}$, we did a grid search on
$\beta/m_{i}\in\left\\{10,30,100\right\\}$ and
$\alpha/\beta\in\left\\{0.1,0.2,0.3,0.4,0.5,0.6\right\\}$. We use a subsect
$S_{i}^{\prime}\subset S_{i}$ with $m_{i}^{\prime}=m$ to train the base-
learner in PACMAML. For each hyperparameter setting $\beta$ (and $\alpha$), we
trained 40 models. Each model is trained on 1 of the 8 pre-sampled meta-
training sets (each containing $n=20$ observed tasks) and each set is run with
5 random seeds of network initialization. The ultimate result for each $\beta$
(and $\alpha$) is the averaged result across all models of that setting. The
hyperparameters $\tilde{\xi}$ and $\sigma_{0}^{2}$ in the hyper-prior
($\operatorname{\mathcal{P}}(\mathchar
28946\relax)=\operatorname{\mathcal{N}}(\mathchar
28946\relax|0,\sigma_{0}^{2}I)$) are chosen to be $\tilde{\xi}=1/(n\beta)$ and
$\sigma_{0}^{2}=3$. To find the optimal model parameter $\mathchar
28946\relax_{0}$, we used the ADAM optimizer with learning rate $3\times
10^{-3}$. The number of tasks per batch is fixed to 5 across all experiments.
We run 8000 iterations for each experiment.

The experiments ran in parallel on several 56-core Intel CLX processors and
each experiment runs on a single core. Each iteration in the PACOH and PACMAML
setting takes about 0.03-0.06s and 0.07-0.14s to run, respectively, with the
exact run-time varying for different number of tasks $n$ and number of
examples $m_{i}$.

###  D.3 Additional Results

We performed the 4-fold cross validation over the 20 target tasks to determine
the optimal $\beta$ for PACOH (Theorem 3) or the optimal $\alpha$ and $\beta$
for PACMAML (Theorem 4). For the selected $\alpha$ and $\beta$ form
validation, we report the lowest test error the corresponding models can
achieve. The results are plotted in Figure 3. For each setting, both the
validation and test errors show the same trend, where the error with PACOH
setting saturates earlier than that with PACMAML setting.

Figure 3: The validation and test error (error bars corresponding to standard
errors) on the Sinusoid dataset under the settings of PACOH and PACMAML.

Figure 4: Left: $\beta$-dependence of the RMSE validation error under the PACOH (Theorem 3) setting. Middle and Right: $\beta$\- and $\alpha$-dependence of the RMSE validation error under the PACMAML (Theorem 4) setting. $\alpha$ is chosen as the optimal $\alpha$ in the middle plot. $\beta=30*m_{i}$ in the right plot. $m_{i}$ | 5 | 10 | 30 | 50 | 100
---|---|---|---|---|---
$\beta/m_{i}$ | 100 | 100 | 30 | 30 | 100
Table 3: Optimal $\beta$ under the setting of PACOH, based on the results of a 4-fold cross validation. $m_{i}$ | 10 | 30 | 50 | 100
---|---|---|---|---
$\alpha/\beta$ | 0.2 | 0.2 | 0.2 | 0.1
$\beta/m_{i}$ | 100 | 100 | 100 | 100
Table 4: Optimal $\alpha$ and $\beta$ values under the setting of PACMAML,
based on the results of a 4-fold cross validation.

In Table 3 and Table 4, we provide the optimal $\beta$ (and $\alpha$) for
PACOH and PACMAML, respectively. In Fig. 4, we plotted the validation error
for three different values of $\beta$ we used. We see that for both PACOH and
PACMAML, the error is large for a small $\beta/m_{i}=10$. The error with
$\beta/m_{i}=30$ and $\beta/m_{i}=100$ are similar for PACOH. For PACMAML, the
error with $\beta/m_{i}=100$ is slightly and consistently better than the
error with $\beta/m_{i}=30$. From the right figure of Fig. 4 we see that for
PACMAML, given $\beta/m_{i}=30$, $\alpha/\beta$ around $0.2$ achieves lowest
validation error.

###  D.4 Generalization Bound of PACMAML

When $\beta/m_{i}$ is held as a constant, the $\Psi_{1}$ and $\Psi_{2}$ terms
of $C(\delta,\lambda,\beta,n,m_{i})$ in Eq.(17) becomes the same across all
$m_{i}$ and both PACOH (Eq. (10)) and PACMAML (Eq. (11)). Thus, we exclulde
the $\Psi_{1}$ and $\Psi_{2}$ terms when comparing the bound values for
different $m_{i}$ and different setups PACOH and PACMAML. In Fig. 5 and 6 we
show the value of each term and the total bound for PACOH and PACMAML obtained
from the same set of experiments for Fig. 2-4. For both PACOH and PACMAML, all
three terms $W$, $\tilde{\xi}D_{KL}$ and $\tilde{\xi}\log(1/\delta)$ tend to
decrease with larger $m_{i}$. For PACOH, with the extra term
$\Delta_{\lambda}$ that panalizes larger $m_{i}$, the total bound either
always increases with $m_{i}$ or first increases then saturates. For PACMAML,
without the $\Delta_{\lambda}$ term, the total bound
$W_{2}+\tilde{\xi}D_{KL}+\tilde{\xi}\log(1/\delta)$ monotonically decreases
vs. $m_{i}$.

In Fig. 7, we show the comparison between the total bound of PACOH and
PACMAML. We see that for all $m_{i}>5$, PACMAML has lower bound for all
choices of $\beta$.

Figure 5: Values of $W_{1}$, $\tilde{\xi}D_{KL}$ and $\Delta$ terms in the
PACOH bound and the total value of the bound for
$\beta/m_{i}\in\left\\{10,30,100\right\\}$.

Figure 6: Values of $W_{2}$ and $\tilde{\xi}D_{KL}$ terms in the PACMAML bound
and the total value of the bound for
$\beta/m_{i}\in\left\\{10,30,100\right\\}$. $\alpha$ for each $m_{i}$ is set
to the optimal value according to Fig. 4.

Figure 7: Comparison of the values of PACOH and PACMAML bound for
$\beta/m_{i}\in\left\\{10,30,100\right\\}$. $\alpha$ for each $m_{i}$ for
PACMAML is set to the optimal value according to Fig. 4.

###  D.5 Experiment for Reptile and MAML

We also experimented with meta-learning algorithms that use Dirac-measure
base-learners, by implementing the Reptile (with optimal
$\operatorname{\mathbf{q}}^{*}$) and the MAML algorithms following the
equations of Section 3.2.

Reptile follows the same experiment setting as PACOH. MAML follows the same
experiment setting as PACMAML where $S_{i}^{\prime}\subset S_{i}$,
$m_{i}^{\prime}=m$. In order to compute the optimal
$\operatorname{\mathbf{q}}_{i}^{*}$ for Reptile, we use an L-BFGS optimizer in
the inner loop with lr = 5e-3, history_size = 10, max_iter =10. Other
experiment setting and hyperparameter selection procedure are the same as
those in Section D.3.

The results of the 4-fold cross validation are plotted in Fig. 8. The errors
of Reptile and MAML follow a very similar trend to the ones with non-Dirac
measure base-learners under PACOH and PACMAML setting, respectively (Fig. 3).
However, the models with non-Dirac measure base-learners appear to have lower
generalization errors than the ones with Dirac measure base-learners (i.e.
Reptile and MAML).

Figure 8: Mean and standard error of the validation and the test result for
Reptile and MAML on Sinusoid. The results are obtained from cross-validation.
The error bars in the figures represent the standard errors.

##  Appendix E Experiment Details of Image Classification

For most hyperparameters, we followed the same default values as in [Finn et
al., 2017]. In Table 5, we listed the hyperparameters that we did grid search,
and their chosen value based on the meta-validation performance. For the inner
learning rate, the search space was $\left\\{0.1,0.03,0.001,0.003\right\\}$
for FOMAML, MAML, and PACMAML; the search space was
$\left\\{0.1,0.03,0.001,0.003,0.001,0.0003,0.0001\right\\}$ for BMAML and
PACOH. For the meta-learning rate, we used the default 0.001 for FOMAML, MAML
and PACMAML; and searched over $\left\\{0.001,0.0003,0.0001,0.00003\right\\}$
for BMAML and PACOH. For $\alpha$, we searched over
$\left\\{10,1.0,0.1\right\\}$ for BMAML, PACOH, PACMAML. We also tried two
gradient descent methods in the inner loop: Vanilla GD and ADAGRAD . We found
that FOMAML and MAML worked better with Vanilla GD; while BMAML, PACOH and
PACMAML worked better with ADAGRAD. $\sigma^{2}$ was fixed to 1 for PACOH and
PACMAML. The number of task per batch was 4 and the network filter size was
64. The total number of meta-training iterations was 60000 for all algorithms.
We ran these tasks with 1 NVIDIA P100 GPU per job and each job takes about 2-3
hours to finish.

$m_{i}$ | Hyper-parameter | FOMAML | MAML | BMAML | PACOH | PACMAML
---|---|---|---|---|---|---
| outer learning rate | 0.001 | 0.001 | 0.0001 | 0.0001 | 0.001
10 | inner learning rate | 0.1 | 0.1 | 0.003 | 0.01 | 0.03
| $\alpha$ | - | - | 1.0 | 10 | 1.0
| outer learning rate | 0.001 | 0.001 | 0.0001 | 0.0001 | 0.001
20 | inner learning rate | 0.03 | 0.1 | 0.003 | 0.003 | 0.01
| $\alpha$ | - | - | 0.1 | 1.0 | 1.0
| outer learning rate | 0.001 | 0.001 | 0.0001 | 0.0001 | 0.001
40 | inner learning rate | 0.03 | 0.03 | 0.003 | 0.003 | 0.01
| $\alpha$ | - | - | 0.1 | 1.0 | 10
| outer learning rate | 0.001 | 0.001 | 0.0001 | 0.0001 | 0.001
80 | inner learning rate | 0.03 | 0.03 | 0.0003 | 0.003 | 0.01
| $\alpha$ | - | - | 0.1 | 1.0 | 1.0
Table 5: The final hyper-parameters of the algorithms in the Mini-imagenet
task.

##  Appendix F Experiment Details of Natural Language Inference

We fixed $\sigma^{2}=0.0004$, which equals to the variance of the BERT
parameter initialization. The hyper-parameter $\alpha$ is decided by a grid
search over $\left\\{10^{2},10^{3},10^{4},10^{5},10^{6},10^{7}\right\\}$ based
on the performance on the meta-validation dataset. The inner loop learning
rate is $0.001$ for all algorithms. We used 50-step Adagrad optimizer in the
inner-loop because it has automatic adaptive learning rate for individual
variables which is beneficial for training large models. For the outer-loop
optimization, we used the ADAM optimizer with learning rate $10^{-5}$. The
final hyperparameters are reported in Table 6. In the few-shot learning phase,
we ran the ADAM optimizer for 200 steps with learning rate $10^{-5}$ on the
adaptable layers. We ran the tasks with 16 TPUs(v2) per job.

Hyper-parameter | MAML | BMAML | PACOH | PACMAML
---|---|---|---|---
inner learning rate | 0.001 | 0.001 | 0.001 | 0.001
$v$ | 12 | 12 | 12 | 11
$m_{i}^{\prime}$ | 32 | 64 | 256 | 64
$m_{i}$ | 256 | 256 | 256 | 256
$\alpha$ | - | $10^{3}$ | $10^{4}$ | $10^{4}$
tasks per batch | 1 | 1 | 1 | 1
meta-training iteration | 10000 | 10000 | 10000 | 10000
Table 6: The final hyper-parameters in the NLI tasks.

In Table 7 we report the detailed classification accuracy on the 12 NLI tasks
with their standard errors.

Task name | $N$ | $k$ | MAML | BMAML | PACOH | PACMAML
---|---|---|---|---|---|---
|  | 4 | 63.0$\pm$1.4 | 61$\pm$2.3 | 62.1$\pm$2.2 | 68.8$\pm$1.6
CoNLL | 4 | 8 | 74.1$\pm$1.8 | 68$\pm$1.9 | 74.9$\pm$1.2 | 79.5$\pm$1.1
|  | 16 | 81.6$\pm$0.6 | 77.9$\pm$1.4 | 83$\pm$0.7 | 84.5$\pm$0.6
|  | 4 | 51.3$\pm$1.8 | 47.5$\pm$1.9 | 55.9$\pm$1.6 | 60.6$\pm$1
MITR | 8 | 8 | 69.1$\pm$2.1 | 64.2$\pm$1.3 | 71.8$\pm$0.8 | 70.9$\pm$1
|  | 16 | 78.7$\pm$1.1 | 72.2$\pm$1.3 | 78.1$\pm$0.6 | 80$\pm$0.6
|  | 4 | 60.1$\pm$2.0 | 53$\pm$2.7 | 60.1$\pm$3.1 | 60.5$\pm$1.9
Airline | 3 | 8 | 64.7$\pm$2.7 | 67.4$\pm$2.2 | 65$\pm$1.5 | 65.4$\pm$1.7
|  | 16 | 68.4$\pm$2.2 | 66.7$\pm$2.6 | 69.6$\pm$1.3 | 69.9$\pm$1.1
|  | 4 | 56.3$\pm$0.5 | 58.7$\pm$3.1 | 58.7$\pm$2.6 | 63.3$\pm$1.3
Disaster | 2 | 8 | 61.5$\pm$0.7 | 64.1$\pm$2.3 | 64.1$\pm$2.4 | 63.9$\pm$2.9
|  | 16 | 67.7$\pm$0.4 | 69.4$\pm$2.0 | 71.3$\pm$1.7 | 71.1$\pm$1.6
|  | 4 | 13.7$\pm$2.1 | 13.9$\pm$0.5 | 13.8$\pm$0.5 | 13.7$\pm$0.7
Emotion | 13 | 8 | 15.8$\pm$1.9 | 14.6$\pm$1.1 | 15$\pm$0.6 | 15.8$\pm$0.6
|  | 16 | 16.7$\pm$0.9 | 15.6$\pm$0.7 | 17.2$\pm$0.7 | 16.8$\pm$0.5
|  | 4 | 58$\pm$2.1 | 58$\pm$2.0 | 58.8$\pm$2.6 | 59.9$\pm$2.1
Political Bias | 2 | 8 | 60.7$\pm$1.9 | 61$\pm$1.9 | 62.1$\pm$1.5 | 62$\pm$1.9
|  | 16 | 64.6$\pm$0.9 | 63.5$\pm$1.2 | 63.8$\pm$1.2 | 66$\pm$1
|  | 4 | 52.2$\pm$0.9 | 54.9$\pm$0.7 | 53.1$\pm$0.9 | 53.4$\pm$1.3
Political Audience | 2 | 8 | 56.1$\pm$1.5 | 55.9$\pm$1.1 | 56$\pm$1.3 | 56$\pm$1.2
|  | 16 | 56.5$\pm$1.2 | 56.9$\pm$1.3 | 60$\pm$0.9 | 59.6$\pm$1
|  | 4 | 18.9$\pm$0.8 | 17.4$\pm$0.6 | 19.2$\pm$0.7 | 19.3$\pm$0.6
Political Message | 9 | 8 | 22.3$\pm$0.7 | 19.3$\pm$0.8 | 22.3$\pm$0.6 | 22.6$\pm$0.5
|  | 16 | 24.3$\pm$0.8 | 21.6$\pm$0.4 | 24.9$\pm$0.4 | 25.5$\pm$0.8
|  | 4 | 58.7$\pm$2.1 | 56.2$\pm$2.8 | 59$\pm$2.3 | 56.8$\pm$3
Rating Books | 3 | 8 | 61.3$\pm$2.7 | 55.1$\pm$2.7 | 64.2$\pm$2 | 61.6$\pm$1.5
|  | 16 | 62$\pm$1.3 | 66.6$\pm$2.1 | 63$\pm$2.1 | 60.4$\pm$2.7
|  | 4 | 49.5$\pm$3.0 | 53.7$\pm$2.7 | 53.7$\pm$2.1 | 52.4$\pm$1.5
Rating DVD | 3 | 8 | 53.2$\pm$1.6 | 51.8$\pm$2.4 | 54.7$\pm$2 | 56$\pm$2
|  | 16 | 54.7$\pm$1.2 | 57.2$\pm$1.5 | 55.4$\pm$1.3 | 60$\pm$1.4
|  | 4 | 46.9$\pm$3.1 | 44.6$\pm$1.9 | 53.3$\pm$1.7 | 52.4$\pm$2
Rating Electronics | 3 | 8 | 52.5$\pm$1.6 | 54.1$\pm$1.6 | 55.6$\pm$2 | 56.1$\pm$1.3
|  | 16 | 54.7$\pm$1.8 | 56.6$\pm$1.8 | 57.5$\pm$1.5 | 58.2$\pm$0.7
|  | 4 | 49.9$\pm$2.4 | 48.3$\pm$2.1 | 57.9$\pm$1.3 | 57.8$\pm$2
Rating kitchen | 3 | 8 | 50.9$\pm$2.8 | 49.5$\pm$3.1 | 52.3$\pm$2.2 | 58.3$\pm$1.5
|  | 16 | 58.7$\pm$1.5 | 54.2$\pm$1.8 | 54.8$\pm$1.8 | 58.1$\pm$2.5
|  | 4 | 48.21 | 47.27 | 50.47 | 51.58
Overall average | - | 8 | 53.52 | 52.08 | 54.83 | 55.68
|  | 16 | 57.38 | 56.53 | 58.22 | 59.18
Table 7: Classification accuracy and standard error on the 12 NLI tasks.