Bridging the Gap Between Practice and PAC-Bayes Theory in Few-Shot Meta-Learning
Authors: Nan Ding
Xi Chen
Tomer Levinboim
Sebastian Goodman
Radu Soricut
Venue: NeurIPS 2021 Poster (2021)
Keywords: meta-learning
few-shot learning
PAC-Bayesian theory

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.

Bridging the Gap Between Practice and PAC-Bayes Theory in Few-Shot Meta-Learning
Nan Ding Google Research
Xi Chen Google Research
Tomer Levinboim Google Research
cingnan@google. com
chi chiLxxiche@@googee.. com
t ome @emeer@@oogle..o com
Sebastian Goodman
Radu Soricut
Google Research
Google Research
seabasa@google.. com
rsoricut@googgee. com
Abstract
Despite recent advances in its theoretical understanding, there still remains sig- nificant 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 origi- nates from assumption in the existing theories which supposes that the number of training examples in the observed tasks and the number of training examples 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--ffiee PACMAML algorithm, and show it outperforms existing meta-learning algorithms on several few-shot benchmark datasets.
Introduction
Recent advances in machine learning and neural networks have resulted in effective but parameter- bloated, data- lata-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 leverage the training data of other tasks for the sake of improving the performance of some specific target (s). Specifically, in the meta-learning (also called learning-to-lent lifelong-learning) setting 66 211. meta-learner first extracts knowledge from set of observed (meta- training) tasks and subsequently, this knowledge enables 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 and many other research fields.
or
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 [5] 12 are considered especially tight and have already been proposed for meta-learning [18] 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 7 and the target task environment T are the same. In the PAC-Bayesian meta-learning setting, task environment is a distribution from which (D,m) is drawn from, where is the data distribution
In parallel to its impressive empirical success, series theoretical works 24 18 3
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

and m is the number of training examples for the task. Although there is research work studying the case of general environment change (c.g. [9]] or data domain change (e.g. [.]) to the best of our knowledge, there is little work focusing on the case where only the number of training examples in in the observed tasks and m 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 useful analysis 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 ((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., mn >> m). In Section 3.T. we study two practical meta-training strategies and provide their PAC-Bayesian bounds in Theorem and Theorem 4 Both results are able to bring down the scaling coefficient of the bound from O(1/m m. to (l) However, Theorem 3 introduces penalty term in the bound that captures the discrepancy between the observed and target task environment. Motivated by MAML (9. show with Theorem 4 that we can eliminate the penalty term by utilizing a subsampling strategy, yielding much tighter bound.
practical
This theoretical work also bridges the gap from practice to theory, as we further show that the maximum- a p--poteerooii (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 algorithmss, 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.
2
Preliminaries
We begin by reviewing the background and settings of the existing PAC-Bayesian bounds for meta- leamiing Our notation mainly follows that of (22, which is itself adapted from [8 3 6).
PAC-Bayesian for Supervised Learning In supervised learning. a learning task is characterized
by a data distribution over a data domain Z where every example x = (z, y). A hypothesis make predictions based inputs
h from the hypothesis space H allows the predictions is measured by a loss function I(h, 2), where the goal is to minimize the expected loss [(h, D) EzeD [(h, 2). Typically, D is unknown and instead we are given set of m
The quality of
observations S ~ D {2 Dm in which case the empirical error on is simply L(h, = 1 EE. ((h,22)
m
In the PAC-Bayesian setting, we assume that the learner has prior knowledge of the hypothesis space H in the form of prior distribution P(h). When the learner observes 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 prior input and outputs posterior.
The expected error of the posterior Q called the Gibbs error L(Q,D) = En-q L(h, D), and its empirical counterpart is [(Q = En-o L(h,, S). The PAC-Bayesian framework provides the following bound over (Q, D) based on its empirical estimate i.)
Theorem (2) Given a data distribution D, hypothesis space H. prior P, confidence level 8 E (0, 1]. and B > 0, with probability at least 1 over samples S ~ Dmm, we have for all posterior Q
L(Q, < L(Q,S+++ 1 (DxL(QIP)+ + +oo 3)) 3 where (33 = En EEND exp()(((h,2) ((h,D)))
m v
(1)
m
2

---

PAC-Bayesian for Meta-Learning In the meta leatn-e setting, the meta-learne observes differ- ent tasks T; = (D, m,) during the meta-training stage. where all tasks share the same data domain Z, hypothesis space H and loss function 1(h, z). For each observed task T;, the meta-learne observes training set S; of size m, which assumed to be sampled i.i.d. from its respective data distribution Dj (that is, S, E .. We further assume that each task environment T, which itself is probability distribution over the data distributions and the sample sizes. The goal of meta-learning is to extract knowledge from the observed tasks Tr, which can then be used as prior knowledge for learning on new (yet unobserved) target tasks 7 = (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.
(Di m,) is drawn i.i.d. from an
In the meta-learning PAC-Bayes framework, the meta-learner presumes a byper-prior P(P) as distribution over priors P. Upon observing datasets S1, Sn from multiple tasks, the meta-learner updates the hyper-prior to hyper-posterior Q(P). The performance of this hyper-posterion also called the transfer-error, is measured as the expected Gibbs error when sampling priors from Q and applying the base learner:
R(Q,T) == E B(D.)) ES-D" [L(Q(S, P), D)]
While R(Q,T) T) is unknown in practice, it can be estimated using the empirical error,
n Σ P).
: ((O = E
(3)
n
In 18 22 the following PAC-Bayesian meta-learning bound is provided:
Theorem 2 (1I8. 221) Given task environment T and set of observed tasks (D,. T, let P be fixed hyper-prior and 0.3 > O, with probability at least 1 6 over samples S E DTm ,,..,,, Sn E Dmn, , we have, for all base learner Q and all hyper-posterior Q.
R(Q,T) SRO 1 + (++ m13)) DKI(Q1P)
nB B [DKI(Q(S, ().,P) + C(8.A,
(4)
Here C(6, A, 3, n, m.) contains v/ and J terms as Eq (see Appendix A.1). and can be bounded by a function that is independent of Q 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-posterion Q such that for all tasks in the task environment T, the divergence terms DEL (Q(S,, P)) would be substantially smaller expectation when Q compared to when P P P. such in the ordinary supervised learning setting of [q.
The hyperparameters and 3 can be adjusted balance between the first three terms of the bound and the C' function. Defining the harmonic mean of m4 as m = (E 1/nm,)) -1 a common choice is A and B x m In this case, the generalization gap R(Q,T) R(Q, ST becomes least O ((+) (from the 3rd-term the RHS of Eq 4). In the next section, we examine assumption in this bound which makes it impractical for the seo-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; for the observed tasks r; and the number of training examples m for the target task are drawn from the same distribution (i.c. Er [m.]] Ey [m]). However, practical applications setting where there are far more training examples in the few-shot setting (where m is particularly small) exposes a gap between theory and practice - Theorem is unable to use the large
of meta-lcarning such as 23 7 operate the observed tasks than in the target task. Moreover, focusing
number of observed samples and can only produce loose bound of O ) which is ineffective at explaining the impressive generalization performance of meta-learning as reported in practice.
Another common choice is À σ vn and 9 & Vm. so that the bound is asymptotically consistent, and scales with O ( However, in practice the bound with 8 in is usually tighter [10].
3

---

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 MAMI..
3.1 Practical PAC-Bayesian Bounds for Few-Shot Meta-I.errning
A first attempt at leveraging the larger number of examples m, in the observed tasks is to directly follow the learning strategy of Theorem 2 by bounding R( Q, T)) using the empirical risk R( Q, S with S. E t and (Di, m,) ~ T, despite the change of task environment from T T. This slight generalization leads to the following bound (with proof in Appendix A.2
Theorem 3 For target task environment T and observed task environment T where Eyy(D) Er [D] and Ep[m] 2 Er[m], let P be a fixed hyper-prior and X > 0, 3 > 0, then with probability at least 1 8 over samples St E D Sn D where (Di, ma) ~ T, we have, for all base
learners Q and hyper-posterior 2
(* nB n15) (xI(21IP)
1 n
E (C0
(S)
where
3 log EpEP R(P.).))
When Ey[m:] > Er [r[m]] this decoupling of the task environments seems beneficial at first, because x smaller compared to 4 when 8 x m. Unfortunately however, Eq. (5) introduces
additional penalty term Ax which increases as [m] gets larger.
To understand the influence of Ax. we plot the (blue) bound of (5 in Fig by using the synthetic
Sinusoid regression task (see details Section 5.1 and in Appendix D.4) where we fixed m
and varied my from 5 to 100. When m, = m 5, Eq. reduces to Eq.44 and A = O. Contrary to intuition, increasing m; does not reduce the bound, but instead makes worse due the rapid increase of Ax.
Can utilize more training examples without introducing penalty term such as Ax? In the definition of (2(2, S (3). , we note that the training dataset S; of the observed task Tú used twice: first in training the base- learner QS,, P). and then, in evaluating the empirical risk L(Q, S.). In ama- lyzing the proof of the theorem (see Appendix A.2), it can be seen that the penalty term arises exactly because (SS,, P) is trained over more samples compared to QS,, P) of the target task, which results in the more powerful lesenees during meta-traine meta-training than the one for the target task.
0.126
0.100
Dound
0.078
Theorem (m-5)
Theorwm
0.050
Theorom
0.025
20
m
Figure 1: The PAC PAC-Bayesian bounds of Theorems 2 3 & as evaluated over the Sinusoid dataset. Some con- stant terms are neglected (see Ap- pendix D.4 for more details).
This motivates us to develop MAML-innspied learning strat- egy, in which we maintain the same target-task training envi- ronment 7 for the base-learners of the observed tasks: we first sample subset S D." from S; where m and m follow the same distribution and m4 Mi. Then we use only the subset S to train the base-learner ((S,,)) P). ). At the same time, all examples of S; E 1 are used for evaluating the empirical risk iLQ St). so that the larger m, in the empirical risk i(Q, S:) help tightening the generalization gap. This new strategy leads to the following bound (proof Appendix A.3):
Theorem For a target task environment T and an observed task environment T where E+ID] ET [D] and [m]m]] 2 Er(m), let P be fixed hyper-prior and X > 0, B > O, then with probability at least 1 8 over samples S1 D ,..., ,...,,, D where (D:, m.) T, and subsamples St E DT c S,,...,y, E DTT C Sm, where E(m[]] Ey [m], we have, for all base learner Q

---

and all
Q
MQQS P).)) (
1 m3) (xI(211P)
R(Q,7) T) R
E Er-o (xxr P)]P)] +
(6)
1
This bound is still ((2) when choosing B x m, but unlike Eq. it does not have additional penalty term in Eq.(), which due to the shared training environment T of the base-learners in
both observed and target tasks. Importantl, the resulting bound effective in the few-shot setting as an increase in the number of observed examples m, monotonically tightens the generalization gap. This is visually demonstrated in Fig I in which the (orange) bound of (q. in Theorem is monotonically decreasing as my increases, while the bound in Theorem 2 is limited only to = 5 and the bound of Theorem grows.
3.2 Justifying Reptile and MAML using PAC-Bayesian Bounds
is worth noting that Theorems B and and only address more practical scenarios in which observed (meta-training) examples are more abundant than the target examples, but they also serve as justification for popular and practical meta-learning algorithms: Reptile [16] and MAML 9
To show this, us consider the maximum-a-posterion (MAP) approximations on the hyper-pone pepee-poteeroor ((P) and base-leaner Qi),), Vi = -,,..., n, with Dirac measures. In addition, we use the isotropic Gaussian priors with variance hyperparameter of and o² for the hyper-prior P(P) and the prior P(h). The hypothesis is parameterized by v. Then we have
P(P) = (Npp J0, ..). Q(P) 8(p = Pa). P(hv) = NV(lpp,)) Qi(1v)) 8(v = q.).
and the goal of MAP approximation is to find the optimal meta-parameters Po- With the above assumptions, the PAC-Bayesian bound (denoted PacB) of (5. and (q.(6) with respect to Po becomes (up to constant, see Appendix B
a iq. S.) +
E 11
n
Po q 11
PacB(pa)
20
nB
20²
where E nz. Here, q, can be any function of Po and S; for 5q. (or Po and S for 6))
such that the only free variable in (7) is Po- Indeed, by setting q; according to the choices below, we can derive the gradients several meta-learning algorithms.
When q: = Po. the gradient of (7 reduces to that of multi task pretraining 23
lim d(PacB) E q: Po
Σ
1
n
d
(P S.).
d d
of
dP
On the other hand, if we the optimal Dirac-base-Beee base-leaee-eee of of Po and S. such that
q argmin L(q. + Po q
(8)
280z
then the gradient of Eq. becomes substantially simpler (see details in the Appendix B).
d(PacB) Po 6
Pp q
(9)
dP
3
and in fact, Eq. ( equivalent the meta-update rule of the Reptile algorithm [16], whose inner-loop is an approximate algorithm for solving the optimal Dirac-base-learner q.
Lastly, when q; is a few gradient descent steps of L(q S)) with initial q, = Pa. the gradient of Eq. reduces that of the MAML algorithm
30.
d(PacB) d
<
lim 20-000
L(q,SS)
o
Po
A slight difference is that MAML usually assumes S, n S 0: while in our setting, we assume S C S.. However, Theorem 4 still holds when S; n S. 0.
5

---

One observation here is that, since q, is function of the gradient of Po- dq. /d involves high-orde high-order gradient w.r.t. Pn- which would result in a computationally intensive algorithm. In the next section we present 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- base- learners. We first derive their objective functions from the RHS of (5. and (q. and then derive low-variance gradient estimators for their optimization.
First, since Eq. 4 and Eq. ( only differ by Ax. we follow 22 and plug in their proposed Gibbs posterior based base-learner (S, (h) = P(h) exp(- S,)) (Z))) (S,, P) into Eq. which minimizes Eq. 5 w.r.t. Q. This yields that, with at least 1 5 probability,
T)
S 7 Σ E
log (a P)
+
(10)
W1
where { + ap and the same constant from the previous bounds. Since A is independent of 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.(o), because the Gibbs posterior would depend on S;, while the base learner in (q,(6) should only be dependent on S C S, Therefore, we the following posterior O with hyperparameter a.
(S), P(h) cxp(-aL(h,, S))
Plugging into (6. (derivations in Appendix) yields that, with at least probability,
R(2, T) < Σ B
1
log (S P) i.g( (QP, St, St)
1)D +C.
(11)
3
A ((FF,S)) - St). We refer to the RHS of this equation as the PACMAML objective, because EI. comes from the PAC-Bayesian bound of Eq. ( which is similar to MAML in subsampling the training data for base-learners.
where L
Given these objectives, the next step is estimate the gradients of W1 and W2, which can then be plugged into Monte-Carlo methods for estimating hyper-posterior distribution of Q (or optimization methods for finding an MAP solution).
Gradient Estimation In W1 and W2. the terms Zo, Za. Za. (Q S,, S;) all involve integrations
over h. When P(h) is Gaussian and i.(h, St) is a squared loss, such integrations have closed form solutions and the gradients can be analytically obtained. However, when i(h S;) is not squared loss (such as the softmax loss), the integration does not have closed form solution and we resort to approximations. For example, [22] directly approximates the objective W, with Monte-Carke sampling, which however results biased gradient estimator.
Here, we follow an alternative approach from the REINFORCE algorithm 23 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 such that L(h, St) è Î(v, v. Si), and v has prior P(v) = -V(v o²) with meta- peta-para p. then
log Zs(S,, = log N (3i(p S.))dv.
Note that p appears in the probability distribution A/ p, o²) of the expectation, and the naive Monte-Carle estimator of the gradient w.r.. p is known exhibit high variance. To reduce the

---

variance, we apply the reparameterization trick [3 and rewrite v P with w ~ ~N(w 00, This leads the following gradient of WT
dW1 1 d log Zo = 0 dp
@L(p w. + f (w; St)
dw,
(12)
ddp
Op
where, (w; & N(w 0, o²) exp( 1-p(--((pppp (p+ w, w.).
As for W2, we also need to evaluate the gradient of L (0+ S₁ St), where
dLa (p S.
d L [q. S0 S., - Q7 (w; (w; dp
(Q: (1) ig (p w, St, St)d 0p
dw
0p
(13)
The first term of Eq. 13 is similar to the gradient in Eq The Monte-Carlo gradient estimator of the second term, however, exhibits the same high-variance problem in the policy gradient method. As remedy, we approximate the gradient with the one from the Softmax Policy Gradient (8), which yields lariaari approximate gradient of W2 (details in Appendix):
/ dW2
dw dw dw+ $ (Q. Oi (3) of + w: S.) dp ~ f oi - ww;
dw. (14)
0p
Op
The first-term in Eq. 14 is similar to the gradient of the First-order MAML (FOMAML, 9 The second term involves Q and Q which are similar the leader and the chaser in BMAML 22 Intuitively, the second term provides additional information that plays similar role to the high- order derivatives in MAML. However, unlike MAML and BMAML. Eq.(14) only involves partial derivatives over (since w is not 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)
(W; St) and w(.)
of (w: S,) using the Monte-Carlo sampling (e.g. SGLD 27 or SVGD (4). After plugging the samples into [(p + w; St) and ((p + w; 5)), we can apply automatic gradient computations (with Tensorflow Pytorch 17 over p to get the stochastic gradient estimator of W1 and W2.
5 Experiments
In this section, we evaluate the two PAC-Bayesian algorithms as they were derived in the previous section: PACOH [22] TT) and PACMAML of Eq. (T). We use several few-shot learning bench- marks (both synthetic and real), and compare them against other existing meta-learning algorithmss, including MAML [9]. Reptile [16]. and BMAML [29]. To fairly compare with other meta-lcarning algorithms that optimize single model, consider only the empirical Bayes method for PACOH and PACMAMI, in which a single MAP solution of Q is used, instead of Bayesian ensembles Q.
5.1 Few-Shot Regression Problem
Our first set of experiments based on the synthetic regression environment setup from 22 where the gradient can be obtained analytically. The base-learners QSS, P) are modeled using Gaussian Process (GP) regression with prior (h) GP(A)mg (1, x')). where the mean function and the kernel function Ka are instantiated as neural networks as in (22). For every example 2j (Iz, and hypothesis h, the loss function is ((h, 2,) |/(xr,) ر Il' and the empirical risk
L(h, S.) = 1 ΣØ 24), The hyper-prior P(Pa) := P(0) = (_0(00, oī is an isotropic Gaussian defined over the network parameters 0. The MAP approximated hyper-posterion takes the form of delta function, where Qo, (P') 2o, (0) = 6(0 0g). As result, we have that DKL So, PP) | /223. where we use of = 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 vn; {5, 10, 30, 50, 1003. The number of training examples for each target task is fixed to be = 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
7

---

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
20 observed tasks) and each set is run with random seeds for network initialization. a and & are chosen based on the cross-validation from the grid 8/m; E (10,30, 100), and a/m; E {10, 20, 30, 40, 50, 60).
Figure 2 shows the averaged generalization errors (RMSE) as my changes, for the Reptile (with optimal q,), MAML, PA-
0.40
Sinusoid
Generalizatinn Error
Reptie
MAME PACOH
COH, and PACMAML algorithms. The size of S used for base-leamnr training in MAML and PACMAML m = 5 for all m,. The hyperparameter values, the validation errors and
0.35
0.30
the standard errors are reported in the Appendix [.3 As can be seen from the figure, the generalization errors of Reptile (blue)
0.25
and PACOH (green), both derived from Theorem g have a U-shaped curve. That is, increasing the meta-training data initially improves generalization in the few-shot target tasks, however, m, continues to grows well beyond m, general- ization suffers. This confirms our conjecture from Theorem 3 that larger m, has mixed effect on its generalization behavior due to the penalty term y 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 !
20
40
60
80
100
mi
Generalization error (RMSE) on the Sinusoid dataset: PACMAMI. and MAMI. continue to improve as m, increases.
Figure 2:
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 esti- mators from (2. and (q.(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 2.eh and O."
Image Classification Our first classification experiment is based on the minilmagenet 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 84x84 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 m; = {10, 20, 40, 80) and m² = = 5 (one shot for each of 5 classes). We fixed a/ = m m, and perform grid search on a as well as the meta and inner learning rate on the mela-validation dataset. Other hyperparameters followed the setting in [9. Further details are reported in the Appendix.
FOMAML
MAML
BMAML
PACOH
PACMAML
m; 10
41.8 = 0.9
47.3
0.9
29.9 0.9
31.2
47.8 = 0.9
m. 20
44.3 0.9
48.0 0.9
0.9
3.90
49.1 + 0.9
m. = 40
46.2 1.0
47.8 0.9
4.
0.9
48.9 + 0.9
m. = 80
45.7 + 0.9
48.1 + 0.9
44.2 0.9
44.6 0.9
50.1 + 0.9
Table 1: Averaged test accuracy and standard error in the ANIL setting.
The main meta-testing results are presented in Table I
We find that PACOH performs significantly worse than PACMAMI. One explanation for this is that in PACOH the base-learner (for top layer) exposed to all 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 my is small.
8

---

Surprisingly, we find that BMAML behaves similarly poor in the ANIL 1 1-particle setting. In FOMAML, MAML and PACMAML, the base-leamner is only trained on S' and the meta-leamer can learn from the unseen examples in S and therefore no overfitting happens. Both MAMI and PACMAMI. performs significantly better than FOMAMI. when m, is small, but their performances saturate and improve little for larger m, which may due to the domain change between meta-training and testing (as the image class changes). Overall, PACMAML as first-order method not only significantly outperforms FOMAML, but also marginally outperforms the high-order MAML, which demonstrates the effectivvness 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: CoNNLL-2003,
(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.
we used the pretrained BERT-base model as our base model (byper-prion, and used GLUE benchmark tasks [26] for meta- meta-training the models and meta-validation for hyperparameter search, before fine-tuning them for the 12 target tasks. The fine-tuning data contains { (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 l separately). and evaluated on the entire test set for each target task 4 The data size of the observed tasks are fixed to be m, = 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 from {32, 64) for MAML. BMAML and PACMAML. As in 4
Following 4.
also partition the set of model parameters to task-specific and task-agnostic. For the 12-layer BERT-base model, we consider a hyper-paane parameter E {6, 9, 11, 12), where only the layers higher than the v-th layer are considered task specifcc and will be adapted in the inner loop. When e = 12, only the top classification layers are adaptable. For BMAML, PACOH and PACMAML, performed grid search and fixed a/3 /m4-
k
H SMLMI 5
MAML
BMAML
PACOH
PACMAML
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
u=9
v=11
U=12
MAML
120G
57G
16G
4G
BMAML
121G
59G
19G
4G
PACMAML
33G
16G
8G
4G
Table 2: Top: Averaged test accuracy over the memory (High Bandwidth Memory) usage with different adaptive layer thresholds v.
IIJ tasks.
Bottom: The comparison of TPU
Due to space limitation, we only report the averaged generalization error over the 12 tasks in Table (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 = 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 (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
Data available at:

---

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 PACMAMI. 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 [9];; 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. (T), 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 deeper discussion and exploration on these topics to future work.
References
[1] M. Abadi, A. Agarwal, P. Barham, E. Brevdo, Z. Chen, C. Citro, G. S. Corrado, A. Davis, J. Dean, M. Devin, S. Ghemawat, Goodfellow, A. Harp. G. Irving, M. Isard, Y. Jia, R. Joze- fowicz, 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. Va- sudevan, 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. Software available from tensorflow.org.
[2] Alquier, Ridgway, and N. Chopin. On the properties of variational approximations of gibbs posteriors. The Journal of Machine Learning Research, 17(1):8374-8414 2016.
[3] R. Amit and R. Meir. Meta-leamnng by adjusting priors based extended PAC-Bayes the- ory. 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.
[4] T. Bansal, R. Jha, and A. McCallum. Learning to few-shot learn across diverse natural language classification tasks. arXiv preprint arXiv: 2019.
[5] 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.
[6] J. Baxter. Theoretical models of learning to learn. In Learning to learn, pages 71-94. Springer, 1998.
[7] Devlin, M.-W. Chang. K. Lee, and 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 I (Long and Short Papers), June 2019.
[8] 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 281 2823, 2017.
[9] C. Finn, P. Abbeel, and S. Levine. Model-agnostic meta-learning for fast adaptation of deep networks. arXiv preprint
2017.
[10] P. Germain, F. Bach, A. Lacoste, and S. Lacoste-Julien. PAC-bayesian theory meets bayesian inference. Advances in Neural Information Processing Systems, 29: 99:1884-1888 1892, 2016.
[11) P. Germain, A. Habrard, F. Laviolette, and F. Morvant. A new pac-bayesian perspective on domain adaptation. In International conference on machine learning, pages 859-868. PMLR, 2016.
[12] 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.
[13] D. P. Kingma and M. Welling. Auto-encoding variational bayes. arXiv preprint K31:11322.611 2013.
10

---

[14] Q. Liu and D. Wang. Stein variational gradient descent: A general purpose bayesian inference algorithm. arXiv preprint arXiv:1608.044// 04441,, 2016.
[15] D. A. McAllester. Some PAC-bayesian theorems. Machine Learning, 37(3):355-363, 1999.
[16] A. Nichol, J. Achiam, and J. Schulman. On first-order meta-learning algorithms. arXiv preprint arXiv:/803.02999, 2018.
[17] A. Paszke, S. Gross, F. Massa, A. Lever, J. Bradbury, G. Chanan, T. Killeen, Z. Lin, N. Gimelshein, I.. Antiga, A. Desmaison, A. Kopf, E. Yang. 7. DeVito, M. Raison, A. Te- jani, S. Chilamkurthy, B. Steiner, L. Fang. Bai, and S. Chintala. Pytorch: An imperative style, pigh-performance deep learning library. In H. Wallach, H. Larochelle, A. Beygelzimer, d' d'Alché-Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems 32, pages 8024 8035. Curran Associates, Inc., 2019.
(18) A. Pentina and C. H. Lampert. A pac-bayesian bound for lifelong learning. In Proceedings of the st International Conference on International Conference on Machine Learning Volume 32, ICML' 14, page [1-991-I1-999 2014.
[19] A. Pentina and C. H. Lampert. Lifelong learning with non-iid tasks. Advances in Neural Information Processing Systems, 28: 1540-1548, 2015.
[20] A. Raghu, M. Raghu, S. Bengio, and O. Vinyals. Rapid learning or feature reuse? towards understanding the effectiveness of maml. arXiv preprini arXiv: 19X0:09999 2019.
[21] Ravi and Larochelle. Optimization as a model for few-shot learning. ICLR, 2017.
[22] Rothfuss, V. Fortuin, and A. Krause. PACOH: Bayes-optimal meta-learning with pac- guarantees, 2020.
[23] 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, 1 2015. 2015.
[24] N. Tripuraneni, M. I. Jordan, and C. Jin. On the theory of transfer learning: The importance of task diversity. arXiv preprint arXiv:2006. 1650, 2020.
[25] O. Vinyals, C. Blundell, T. Lillicrap. K. Kavukcuoglu, and D. Wierstra. Matching networks for one shot learning. arXiv preprint arXiv: 04080, 2016.
[26] A. Wang, Singh, Michael, F. Hill, O. Levy, and S. R. Bowman. Glue: multi- task benchmark and analysis platform for natural language understanding. arXiv preprint 18Xiv:1804.00 07461, 2018.
[27] M. Welling and Y. W. Teh. Bayesian learning via stochastic gradient langevin dynamics. In Proceedings of the 28th international conference machine learning (ICML-II), pages 681-688. Citeseer, 2011.
cnameacttoiistrriiffcceeeee [28] R. J. Williams. Simple statistical gradient-following algorithms for connectionist reinforcement learning. In Machine Learning, pages 229-256. 1992.
[29] Yoon. T. Kim, O. Dia, Kim, Y. Bengio, and S. Ahn. Bayesian agnel-ag meta-learning. In Proceedings of the 32nd International Conference on Neural Infomation Processing Systems, pages 7343-7353, 2018


Reviews:
[{"review_id": "_UYzLyUkueP", "reviewer": "Reviewer_pWqh", "summary": "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. \nIn 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.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Originality\n-------- \nUnderstanding few-shot learning methods is still challenging and this work participates to a better understanding of this framework, which represents an important value. \nExisting PAC-Bayesian settings for few-shot/meta-learning do not handle the difference in terms of training size between source and target tasks, so there is a novel aspect here that has the advantage to be more realistic for the few-shot learning setting.\nAnother property of the framework is to allow to interpret MAML and REPTILE, which also new and offers some justification for these two algorithms, even though this may benefit from more discussion.\nAn algorithm is derived, using a base strategy borrowed from the PACOH paper, anyway a specific novel formulation is derived.\n\nOverall, the novelty of the paper is rather fair.\n\n\nQuality \n------\nThe results are solid and well justified. All claims are justified by proofs and derivations, sometimes included in the Appendix.\nThe experimental evaluation is rather large and solid.\n\n\nClarity\n------\nThe paper is globally clear and convincing.\nI had a problem for interpreting the term $\\Delta_\\lambda$ in Thm3, I would appreciate if the authors can comment more on it.\nMaybe the assumptions on T and \\hat{T} could be more precisely discussed to avoid any misunderstanding.\n\nSignificance\n----------\nI think that the paper provides a significant contribution for studying the few-shot learning in PAC-Bayes, mainly in three aspects: (i) a framework that takes into account the different sizes between observed and target tasks, (ii) the capacity of the framework to allow an interpretation of two existing algorithms, (iii) the derivation of a new algorithm that provides better results in comparison to other approaches ) related to Pac-Bayes though.\n\nThe significance outside the PAC-Bayesian community is not clear but at least the work contributes to the understanding of few-short problem which is important.\n\nSome methodological aspects and results could be more discussed anyway.\n\n\nComments\n-----------\n\n-line 130: Definition and differences of $T$ and $\\tilde{T}$ should require a bit more precision on the expected differences in terms of tasks environment. Is it just that the samples are draws with less examples, or can we imagine more (structural) differences?\nAccording to assumptions of Thm3, line 132/133, if I understood correctly, the environment can output the same distributions, so in other words, the same tasks, but the difference is that in T the expected number of observed samples is smaller.\n\nline 136: I am not sure to understand/interpret correctly the $\\Delta_\\lambda$ term. From the hypothesis of line 132/133, I understand that the 2 environments provide the same tasks, in expectation, so I would have appreciated more precision in order to explain  why $R(P,T)-R(P,\\tilde{T})$ should not be 0 in expectation? One explanation coud that the tasks weights are different between the two environnements (related to my question above but this probably not the case), but my interpretation is that when using smaller samples the base algorithms would produce less powerful base classifiers which cannot be compensated by the posterior, but I may have  wrongly interpreted the notation. I would appreciate if the authors could comment on it.\n\nline 137, first equation: you expect that the number of instances samples in the observed tasks tends to the observed harmonic mean?\n\n-Table 1: the results seem to correspond to accuracy and not generalization error (since the true error cannot be estimated anyway), same for Table2.\n\n-Fig 2, line 279. The U-shaped can indeed shows the beginning of an overfitting situation where the learners starts overfitting on the source tasks. That being said, this could be explained by the fact that the base learners are not chosen, parameterized or regularized correctly for the problem considered. This may indicates that some information are still missing in the proposed bound.\n\n-The analysis of the generalization bounds is deferred to Appendix with the conclusion that PACMAML exhibits better generalization bound than the competitor PACOH in the context of the synthetic experiments. I would be interested in knowing the bounds for MAML or REPTILE for example, to see if the bounds can be informative to perform algorithm selection for some problems. Note also that showing bounds for the other tasks is interesting.\n\n-The bounds provides PAC-Bayesian guarantees and allows to deduce some algorithms, which is good. Maybe something that is missing is to have some information about a structure on the posterior, for example maybe some diversity should be observed on the base learners and when this occurs maybe the guarantees can be better. Maybe extensions that would incorporate such a property would be interested.\n\n-For PACMAML, a particular formulation of the Gibbs posterior is used. This is expected since otherwise one cannot expect to have a tractable approach. However, I would expect a little discussion on the expressiveness of this choice and maybe some possible other alternatives. \n\nIn practice a Monte-Carlo sampling is used, but this implies probably high computational costs, what happened on existing image and natural language benchmarks?\n\n-The bound proposed by the paper uses the frameworks of Pentina et al. and Rothfuss et al. that rely on the McAllester version of a PAC-Bayes bound. However, there exist tighter version, like the Seeger one, which may help to have even tighter bound, but at a price of a higher complexity and to derive new specific studies.\n\n-line 157 and also l166, the distribution on which expectation of m'_i is not indicated, should you define an other environment that depends on S_i and D_i.\n\n-A point that is a bit puzzling is that since the framework can be interpreted for deriving the algorithms MAML and REPTILE, one can then learn with these algorithms while optimizing a PAC-Bayes bound. I would then expect a better behavior for these 2 approaches.\nThat being said, if we reinterpret these two algorithms with the proposed framework, can we explain by the bound why these algorithms would perform worse than PACMAML? Is it because of the optimization problem that is significantly harder to optimize, or is it because the considered Gibbs posterior is not well adapted for these algorithms, or maybe there is another reason?\n \n\n-----\nAfter rebuttal\n-----\nThank you for the answers provided.\n\nOn the remark about information on the posterior, maybe considering bounds that involve information on the diversity of the voters can be interesting, such as:  \n*the C-bound: Pascal Germain, Alexandre Lacasse, François Laviolette, Mario Marchand, and Jean-Francis Roy.\nRisk bounds for the majority vote: From a PAC-Bayesian analysis to a learning algorithm. Journal\nof Machine Learning Research, 16, 2015.  \n*or 2nd order bounds: Andres R. Masegosa, Stephan S. Lorenzen, Christian Igel, Yevgeny\nSeldin. Second Order PAC-Bayesian Bounds for the Weighted Majority Vote. \nNeurIPS 2020.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "In the conclusion, the authors mention a limitation related to the fact that the method does not consider the domain shift setting.\n\nThis was not mentioned in the paper, but this work is mainly fundamental and is not subject directly to negative social impact. \n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "95R7MYXFgw0", "reviewer": "Reviewer_587T", "summary": "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).\nIn Thm 4, the paper suggests a learning strategy that omits the extra distribution shift of Thm 3, by using a smaller data set. \nThe 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.", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "\nStrengths\n- The paper is well written. The structure is logical and easy to follow.\n- Interesting observation from theory - tighter meta-test bound can sometimes be achieved if the base learner uses FEWER samples  (the same number of samples as in meta-training), this seems counter-intuitive, but helps to mitigate the distributional shift in the distribution over the number of samples.\n- Experimental results show the suggested algorithm has favorable performance in few-shot tasks.\n**************************************************************\nWeakness\n- There is an issue that is not addressed. The empirical error increases if fewer samples are used (since we have a base-learner that was trained with fewer samples).  Is it ensured that this increase does not negate the reduction in the complexity term? The paper does not seem to discuss this issue.\n-The derivation of the gradient estimators is not clear. For example: (1) below line 602 in the appendix, there is an inequality, but the final result is equality. (2) I couldn’t understand the transitions below line 603.\n- The sampling from the distribution $Q(w, S)$ is not trivial (since it involves an exponent of the empirical loss). However, the paper doesn’t elaborate on the sampling method used besides referencing SGLD and SVGD. Since there are only approximated methods for sampling, with advantages and disadvantages, I believe this part should be investigated more in-depth. Furthermore, there is no pseudocode of the full algorithm, and so readers can not recarate the results.  \n**************************************************************\nQuestions\n- Line 317 - “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”. This sentence is not clear. How is it guaranteed that there is no overfitting?\n**************************************************************\nMinor comments: \n- Line 88 - possible typo -  $S_i \\sim D$ instead of  $S_i \\in D$\n- Line 130 - \\tilde{T} is undefined\n- Lines 137-138 are not clear.\n- Line 225, I think REINFORCE is not the name of the method used since it usually uses the log-derivative trick.\n- Figure 2 lacks error bars.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The limitations are discussed in the main review. There is no potential negative societal impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "9"}, "extra_text": {}}, {"review_id": "5AcQTIVPj8P", "reviewer": "Reviewer_Jt6H", "summary": "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.", "questions": "", "limitations": "", "rating": 8, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "### Positives\n\nWhile I am not an expert in meta-learning or PAC-Bayes, this work seems well motivated (fixing the issue of uniformity in the sample sizes of previous PAC bounds), well executed / technically correct, and novel.  \n\n\n### Negatives\n\nI was confused a bit by the experimental section.  I thought that the paper would experimentally validate the derived bound, comparing it not only to the empirical generalization error but also the bounds previously derived for meta-learning.  This is done for the synthetic data in Figure 1 but no where else.  Why aren't the bounds empirically studied?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "There are no negative societal implications.  The major limitations are identified in the text: \"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.\"", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}]

Author rebuttal:

Meta-review: All reviewers and myself agree on the interest of the topic for the NeurIPS community, on the significance of the results, and on the clarity of the contributions. The discussion phase allowed to satisfactorily address the few concerns expressed by the reviews. As pointed out by a reviewer, the submission provides valuable insights on meta-learning generalisation bounds when the base learner has access to small amounts of data, which in some cases leads to tighter bounds. This observation helps to mitigate the distributional shift in the distribution over the number of samples.
Decision: Accept (Poster)