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

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.

heading: 1 Introduction
text: Recent advances in machine learning and neural networks have resulted in effective but parameterbloated, 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 [6, 21], a meta-learner first extracts knowledge from a set of observed (metatraining) 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 [23], language understanding [7], reinforcement learning [9] and many other research fields.
In parallel to its impressive empirical success, a series of theoretical works [24, 18, 3, 22] 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 [15, 12] are considered especially tight and have already been proposed for meta-learning [18, 3, 22]. 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 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
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
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. [19]) or data domain change (e.g. [11]), to the best of our knowledge, there is little work focusing on the case where only the number of training examples 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 [9]. 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., m̃ 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/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 [9], 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 hyperposterior are both approximated by Dirac-measures) yield various popular meta-learning algorithms, including multi-task pretraining [23], Reptile [16] and MAML [9]. 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.

heading: 2 Preliminaries
text: We begin by reviewing the background and settings of the existing PAC-Bayesian bounds for metalearning. Our notation mainly follows that of [22], which is itself adapted from [18, 3, 6].
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) = Ez∼D l(h, z). Typically, D is unknown and instead we are given a set of m observations S ∼ Dm = {zi ∼ D}mi=1, in which case the empirical error on S is simply L̂(h, S) = 1 m ∑m i=1 l(h, zi).
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) = Eh∼Q L(h,D), and its empirical counterpart is L̂(Q,S) = Eh∼Q L̂(h, S). The PAC-Bayesian framework provides the following bound over L(Q,D) based on its empirical estimate L̂(Q,S).
Theorem 1 ([2, 12]) Given a data distribution D, a hypothesis space H , a prior P , a confidence level δ ∈ (0, 1], and β > 0, with probability at least 1− δ over samples S ∼ Dm, we have for all posterior Q,
L(Q,D) ≤ L̂(Q,S) + 1 β
( DKL(Q‖P ) + log 1
δ
) + m
β Ψ(
β m ) (1)
where Ψ(β) = logEh∼P Ez∼D exp(β(l(h, z)− L(h,D))).
PAC-Bayesian for Meta-Learning In the meta-learning setting, the meta-learner observes different tasks τi = (Di,mi) 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 τi, the meta-learner observes a training set Si of size mi which is assumed to be sampled i.i.d. from its respective data distribution Di (that is, Si ∈ Dmii ). We further assume that each task τi = (Di,mi) 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 τi, which can then be used as prior knowledge for learning on new (yet unobserved) target tasks τ = (D,m) ∼ 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 P(P ) as a distribution over priors P . Upon observing datasets S1, . . . , Sn from multiple tasks, the meta-learner updates the hyper-prior to a hyper-posterior 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 Q and applying the base learner:
R(Q, T ) := EP∼Q E(D,m)∼T ES∼Dm [L(Q(S, P ), D)] . (2)
While R(Q, T ) is unknown in practice, it can be estimated using the empirical error,
R̂(Q, Sni=1) := EP∼Q
[ 1
n n∑ i=1 L̂(Q(Si, P ), Si)
] . (3)
In [18, 22], the following PAC-Bayesian meta-learning bound is provided:
Theorem 2 ([18, 22]) Given a task environment T and a set of n observed tasks (Di,mi) ∼ T , let P be a fixed hyper-prior and λ > 0, β > 0, with probability at least 1 − δ over samples S1 ∈ Dm11 , . . . , Sn ∈ Dmnn , we have, for all base learner Q and all hyper-posterior Q,
R(Q, T ) ≤R̂(Q, Sni=1) + ( 1
λ +
1
nβ
) DKL(Q‖P)
+ 1
nβ n∑ i=1 EP∼Q [DKL(Q(Si, P )‖P )] + C(δ, λ, β, n,mi). (4)
Here C(δ, λ, β, n,mi) contains Ψ and 1δ terms as in Eq.(1) (see Appendix A.1), and can be bounded by a function that is independent ofQ for both bounded and unbounded loss functions under moment constraints (see details in [22]). From a Bayesian perspective, meta-learning attempts to learn a good hyper-posterior Q such that for all tasks in the task environment T , the divergence terms DKL(Q(Si, P )‖P ) would be substantially smaller in expectation when P ∼ Q compared to when P ∼ P , such as in the ordinary supervised learning setting of Eq.(1). The hyperparameters λ and β can be adjusted to balance between the first three terms of the bound and the C function. Defining the harmonic mean of mi as m̃ = ( ∑n i=1 1/nmi)
−1, a common choice is λ ∝ n and β ∝ m̃*. In this case, the generalization gap R(Q, T )− R̂(Q, Sni=1) becomes at least O( 1m̃ ) (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.

heading: 3 Bridging the Gap between Practice & Theory of Few-Shot Meta-Learning
text: The previous PAC-Bayesian meta-learning bound (Theorem 2) assumes that the number of training examples mi for the observed tasks τi and the number of training examples m for the target task τ are drawn from the same distribution (i.e. ET [mi] = ET [m]). However, practical applications of meta-learning such as [23, 7] 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( 1m ) which is ineffective at explaining the impressive generalization performance of meta-learning as reported in practice.
*Another common choice is λ ∝ √ n and β ∝ √ m̃, so that the bound is asymptotically consistent, and
scales with O( 1√ m̃ ). However, in practice the bound with β ∝ m̃ is usually tighter [10].
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.

heading: 3.1 Practical PAC-Bayesian Bounds for Few-Shot Meta-Learning
text: A first attempt at leveraging the larger number of examples mi in the observed tasks is to directly follow the learning strategy of Theorem 2, by boundingR(Q, T ) using the empirical risk R̂(Q, Sni=1), with Si ∈ Dmii and (Di,mi) ∼ T̃ , despite the change of task environment from T to 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 T̃ where ET̃ [D] = ET [D] and ET̃ [m] ≥ ET [m], let P be a fixed hyper-prior and λ > 0, β > 0, then with probability at least 1− δ over samples S1 ∈ Dm11 , . . . , Sn ∈ Dmnn where (Di,mi) ∼ T̃ , we have, for all base learners Q and hyper-posterior Q,
R(Q, T ) ≤R̂(Q, Sni=1) + ( 1
λ +
1
nβ
) DKL(Q‖P)
+ 1
nβ n∑ i=1 EP∼Q [DKL(Q(Si, P )‖P )] + C(δ, λ, β, n,mi) + ∆λ(P, T, T̃ ), (5)
where ∆λ(P, T, T̃ ) = 1λ logEP∈P e λ(R(P,T )−R(P,T̃ )).
When ET̃ [mi] ET [m], this decoupling of the task environments seems beneficial at first, because O( 1m̃ ) is smaller compared to Eq.(4) when β ∝ m̃. Unfortunately however, Eq.(5) introduces an additional penalty term ∆λ, which increases as ET̃ [m̃] gets larger. To understand the influence of ∆λ, 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 mi from 5 to 100. When mi = m = 5, Eq.(5) reduces to Eq.(4) and ∆λ = 0. Contrary to intuition, increasing mi does not reduce the bound, but instead makes it worse due to the rapid increase of ∆λ.
Can we utilize more training examples without introducing a penalty term such as ∆λ? In the definition of R̂(Q, Sni=1) (Eq.(3)), we note that the training dataset Si of the observed task τi is used twice: first in training the base-learnerQ(Si, P ), and then, in evaluating the empirical risk L̂(Q,Si). In analyzing the proof of the theorem (see Appendix A.2), it can be seen that the penalty term arises exactly because Q(Si, P ) is trained over more samples compared to Q(S, P ) of the target task, which results in the more powerful base-learners during meta-training than the one for 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 ∈ D m′i i from Si where m ′ i and m follow the same distribution and m′i ≤ mi. Then we use only the subset S′i to train the base-learner Q(S ′ i, P ). At the same time,
all examples of Si ∈ Dmii are used for evaluating the empirical risk L̂(Q,Si), so that the larger mi in the empirical risk L̂(Q,Si) 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 T̃ where ET̃ [D] = ET [D] and ET̃ [m] ≥ ET [m], let P be a fixed hyper-prior and λ > 0, β > 0, then with probability at least 1 − δ over samples S1 ∈ Dm11 , . . . , Sn ∈ Dmnn where (Di,mi) ∼ T̃ , and subsamples S′1 ∈ D m′1 1 ⊂ S1, . . . , S′n ∈ D m′n n ⊂ Sn, where E[m′i] = ET [m], we have, for all base learner Q
and all hyper-posterior Q,
R(Q, T ) ≤EP∼Q
[ 1
n n∑ i=1 L̂(Q(S′i, P ), Si)
] + ( 1
λ +
1
nβ
) DKL(Q‖P)
+ 1
nβ n∑ i=1 EP∼Q [ DKL(Q(S ′ i, P )‖P ) ] + C(δ, λ, β, n,mi). (6)
This bound is still O( 1m̃ ) when choosing β ∝ 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 mi 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 mi increases, while the bound in Theorem 2 is limited only to mi = 5 and the bound of Theorem 3 grows.

heading: 3.2 Justifying Reptile and MAML using PAC-Bayesian Bounds
text: 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 [16] and MAML [9].
To show this, let us consider the maximum-a-posteriori (MAP) approximations on the hyper-posterior Q(P ) and base-leaner Qi(h),∀i = 1, . . . , n, with Dirac measures. In addition, we use the isotropic Gaussian priors with variance hyperparameter σ20 and σ
2 for the hyper-prior P(P ) and the prior P (h). The hypothesis h is parameterized by v. Then we have
P(P ) = N (p |0, σ20), Q(P ) = δ(p = p0), P (hv) = N (v |p, σ 2), Qi(hv) = δ(v = qi),
and the goal of MAP approximation is to find the optimal meta-parameters p0. With the above assumptions, the PAC-Bayesian bound (denoted PacB) of Eq.(5) and Eq.(6) with respect to p0 becomes (up to a constant, see Appendix B),
PacB(p0) = 1
n n∑ i=1 L̂(qi, Si) + ξ̃‖p0 ‖2 2σ20 + 1 nβ n∑ i=1 ‖p0−qi ‖2 2σ2 , (7)
where ξ̃ = 1λ + 1 nβ . Here, qi can be any function of p0 and Si for Eq.(5) (or p0 and S ′ i for Eq.(6)), such that the only free variable in Eq.(7) is p0. Indeed, by setting qi according to the choices below, we can derive the gradients of several meta-learning algorithms.
When qi = p0, the gradient of Eq.(7) reduces to that of multi-task pretraining [23, 7],
lim qi→p0
d(PacB) dp0 = ξ̃ p0 σ20 + 1 n n∑ i=1 d dp0 L̂(p0, Si).
On the other hand, if we use the optimal Dirac-base-learner q∗i of p0 and Si, such that
q∗i = argmin qi
[ L̂(qi, Si) + ‖p0−qi ‖2
2βσ2
] , (8)
then the gradient of Eq.(7) becomes substantially simpler (see details in the Appendix B),
d(PacB) dp0 = ξ̃ p0 σ20 + 1 n n∑ i=1 p0−q∗i βσ2 , (9)
and in fact, Eq.(9) is equivalent to the meta-update rule of the Reptile algorithm [16], whose inner-loop is an approximate algorithm for solving the optimal Dirac-base-learner q∗i .
Lastly, when qi is a few gradient descent steps of L̂(qi, S ′ i) with initial qi = p0, the gradient of Eq.(7) reduces to that of the MAML algorithm† [9] as σ2 →∞,
lim σ2→∞
d(PacB) dp0 = ξ̃ p0 σ20 + 1 n n∑ i=1 d dp0 L̂(qi, Si).
†A slight difference is that MAML usually assumes Si ∩ S′i = ∅; while in our setting, we assume S′i ⊂ Si. However, Theorem 4 still holds when Si ∩ S′i = ∅.
One observation here is that, since qi is function of the gradient of p0, dqi /dp0 involves high-order gradient w.r.t. p0, 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.

heading: 4 PAC-Bayesian Meta-Learning Algorithms in the Few-Shot Setting
text: In this section we present two PAC-Bayesian based Meta-Learning algorithms with non-Dirac baselearners. 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 ∆λ, we follow [22] and plug in their proposed Gibbs posterior based base-learner Q∗(Si, P )(h) = P (h) exp(−βL̂(h, Si))/Zβ(Si, P ) into Eq.(5), which minimizes Eq.(5) w.r.t. Q. This yields that, with at least 1− δ probability,
R(Q, T ) ≤ 1 n n∑ i=1 EP∼Q [ − 1 β logZβ(Si, P ) ] ︸ ︷︷ ︸
W1
+ξ̃DKL(Q‖P) + ∆λ + C (10)
where ξ̃ = 1λ + 1 nβ and C is the same constant from the previous bounds. Since ∆λ is independent
of Q and can be neglected during inference or optimization of Q, it reduces to the same PACOH objective as in [22].
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 Si, while the base learner in Eq.(6) should only be dependent on S′i ⊂ Si. Therefore, we use the following posterior Qαi with hyperparameter α,
Qαi (S ′ i, P )(h) = P (h) exp(−αL̂(h, S′i)) Zα(S′i, P ) .
Plugging into Eq.(6) (derivations in Appendix) yields that, with at least 1− δ probability,
R(Q, T ) ≤ 1 n n∑ i=1 EP∼Q [ − 1 β logZα(S ′ i, P ) + L̂ ∆ α β (Qαi , Si, S ′ i) ] ︸ ︷︷ ︸
W2
+ξ̃DKL(Q‖P) + C. (11)
where L̂∆α β (Qαi , Si, S ′ i) , L̂(Q α i , Si) − αβ L̂(Q α i , S ′ i). 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 W1 and W2, which can then be plugged into Monte-Carlo methods for estimating a hyper-posterior distribution of Q (or optimization methods for finding an MAP solution).
Gradient Estimation In W1 and W2, the terms Zβ , Zα, L̂∆α β (Qαi , Si, S ′ i) all involve integrations over h. When P (h) is Gaussian and L̂(h, Si) is a squared loss, such integrations have closed form solutions and the gradients can be analytically obtained. However, when L̂(h, Si) 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, [22] directly approximates the objective W1 with Monte-Carlo sampling, which however results in a biased gradient estimator.
Here, we follow an alternative approach from the REINFORCE algorithm [28], 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 v such that L̂(h, Si) , L̂(v, Si), and v has prior P (v) = N (v |p, σ2) with meta-parameter p, then
logZβ(Si,p) = log ∫ N (v |p, σ2) exp(−βL̂(v, Si))dv .
Note that p appears in the probability distribution N (v |p, σ2) of the expectation, and the naive Monte-Carlo estimator of the gradient w.r.t. p is known to exhibit high variance. To reduce the
variance, we apply the reparameterization trick [13] and rewrite v = p+w with w ∼ N (w |0, σ2). This leads to the following gradient of W1,
dW1 dp = − 1 β d dp logZβ(Si,p) =
∫ Qβi (w;Si) ∂L̂(p+w, Si)
∂ p dw, (12)
where, Qβi (w;Si) ∝ N (w |0, σ 2) exp(−βL̂(p+w, Si)).
As for W2, we also need to evaluate the gradient of L̂∆α β (Qαi , Si, S ′ i), where
d
dp L̂∆α β (Qαi , Si, S ′ i) =
∫ Qαi (w;S ′ i) ∂L̂∆α β (p+w, Si, S ′ i)
∂ p dw+
∫ ∂Qαi (w;S ′ i)
∂ p L̂∆α β (p+w, Si, S ′ i)dw .
(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 [8], which yields a low-variance approximate gradient of W2 (details in Appendix):
dW2 dp
' ∫ Qαi (w;S ′ i) ∂L̂(p+w;Si)
∂ p dw+
α
β
∫ ( Qβi (w;Si)−Q α i (w;S ′ i) ) ∂L̂(p+w;S′i)
∂ p dw . (14)
The first-term in Eq.(14) is similar to the gradient of the First-order MAML (FOMAML, [9]). The second term involves Qβi and Q α i , which are similar to the leader and the chaser in BMAML [29]. Intuitively, the second term provides additional information that plays a similar role to the highorder derivatives in MAML. However, unlike MAML and BMAML, Eq.(14) only involves partial derivatives over p (since w is not a function of 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 wα(n) ∼ Q α i (w;S ′ i) and w β (n) ∼ Qβi (w;Si) using the Monte-Carlo sampling (e.g. SGLD [27] or SVGD [14]). After plugging the samples into L̂(p+w;Si) and L̂(p+w;S′i), we can apply automatic gradient computations (with Tensorflow [1] or Pytorch [17]) over p to get the stochastic gradient estimator of W1 and W2.

heading: 5 Experiments
text: In this section, we evaluate the two PAC-Bayesian algorithms as they were derived in the previous section: PACOH [22] 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 [9], Reptile [16], and BMAML [29]. 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 Q is used, instead of Bayesian ensembles of Q.

heading: 5.1 Few-Shot Regression Problem
text: Our first set of experiments are based on the synthetic regression environment setup from [22], where the gradient can be obtained analytically. The base-learners Q(S, P ) are modeled using Gaussian Process (GP) regression with a prior Pθ(h) = GP(h|mθ(x), kθ(x, x′)), where the mean function mθ and the kernel function kθ are instantiated as neural networks as in [22]. For every example zj = (xj , yj) and a hypothesis h, the loss function is l(h, zj) = ‖h(xj)− yj‖22 and the empirical risk is L̂(h, Si) = 1mi ∑mi j=1 l(h, zj). The hyper-prior P(Pθ) := P(θ) = N (θ|0, σ20I) is an isotropic Gaussian defined over the network parameters θ. The MAP approximated hyper-posterior takes the form of a delta function, where Qθ0(Pθ) := Qθ0(θ) = δ(θ = θ0). As a result, we have that DKL(Qθ0 ‖P) = ‖θ0‖2/2σ20 , where we use σ20 = 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 mi ∈ {5, 10, 30, 50, 100}. 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. α and β are chosen based on the cross-validation from the grid β/mi ∈ {10, 30, 100}, and α/mi ∈ {10, 20, 30, 40, 50, 60}.
Figure 2 shows the averaged generalization errors (RMSE) as mi changes, for the Reptile (with optimal q∗i ), MAML, PACOH, and PACMAML algorithms. The size of S′i used for base-learner training in MAML and PACMAML is m′i = 5 for all mi. 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 mi initially improves generalization in the few-shot target tasks, however, as mi continues to grows well beyond m, generalization suffers. This confirms our conjecture from Theorem 3, that larger mi has a mixed effect on its generalization behavior due to the penalty term ∆λ. 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.

heading: 5.2 Few-shot Classification Problems
text: 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 Qαi and Q β i .
Image Classification Our first classification experiment is based on the miniImagenet classification task [25] 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 [9] and used the same feature extraction model which contains 4 convolutional layers. Although the original MAML adapted the entire network in the inner loop, [20] 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 [20], 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 w). The data sizes of the observed tasks are varied from mi = {10, 20, 40, 80} and m′i = m = 5 (one shot for each of 5 classes). We fixed α/β = m ′ i/mi and perform grid search on α as well as the meta and inner learning rate on the meta-validation dataset. Other hyperparameters followed the setting in [9]. Further details are reported in the Appendix.
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 mi 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′ 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 mi is small, but their performances saturate and improve little for larger mi, 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 [7] model containing 110M parameters. Our experiment involves 12 practical natural language inference tasks from [4] which include:‡ (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 [4], we used the pretrained BERT-base model as our base model (hyper-prior), and used GLUE benchmark tasks [26] 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 ∈ {4, 8, 16}- 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 [4]. The data size of the observed tasks are fixed to be mi = 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 from {32, 64} for MAML, BMAML and PACMAML. As in [4], 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 ∈ {6, 9, 11, 12}, 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 α and fixed α/β = m′i/mi.
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 [5] 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 [4]. 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.

heading: 6 Discussion
text: 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
‡Data available at: https://github.com/iesl/leopard.
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 [19]; 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. [11]), 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.

Review summaries:
This paper studies the Few-shot meta-learning setting according to PAC-Bayes theory. The authors focus on a context where the number of examples from source tasks and the target ones do not follow the same distribution. The authors develop two PAC-Bayes bounds tailored for the few-shot learning setting. Additionally, two existing and famous few-shot learning algorithms (MAML and Reptile) can be derived from the proposed bounds.  In that sense, the work aims at reducing the gap between theory and practice by proposing a theory that can justify some existing and efficient algorithms. A new algorithm is also derived from the proposed framework PACMAML. An experimental evaluation on a synthetic problem and on existing benchmarks is presented.

Previous PAC-Bayesian Meta-learning bounds assume the number of samples per task follows the same distribution in the meta-training and in meta-testing.  This paper relaxes this assumption, allowing for a shift in the number-of-samples distribution from meta-training to meta-testing (Thm 3). In Thm 4, the paper suggests a learning strategy that omits the extra distribution shift of Thm 3, by using a smaller data set.  The paper shows how the popular meta-learning algorithms, Reptile, and MAML can be justified using the PAC-Bayes framework, and also introduces a new algorithm called PACMAML.  Experimental results show the method outperforms other algorithms on several few-shot benchmarks.

Existing meta-learning techniques assume that the number of samples for teach task are drawn from the same distribution.  Theorem 3 shows that a naive decoupling of the number of samples introduces a term to the gap that penalizes additional samples.  The paper bypasses this issue by introducing a fix-sized subset that is used to train a base model.  The additional samples are then used to evaluate the empirical risk, thus removing the aforementioned unsatisfactory term.  The MAML and Reptile algorithms are recovered by considering the derived bound and normal priors along with both delta posteriors (ie MAP solutions) and normal posteriors.  Results are reported on synthetic regression, image classification, and product review classification.